数据结构与算法复习题及参考答案

2016《数据结构域算法》复习题

if(p==NULL){

s=(Node*)malloc(sizeof(Node)); s->data=k; r->next=s; r=s i++; } }

return head; }

7.设H是带表头结点的单向链表的表头指针，将链表中数值重复的结点删除。

答：

LinkList DleReapeatValue(LinkList H){ Node *p=H->next,*q,*s; While(p){ s= p;

q=s->next; while(q){

if(p->data==q->data){

s->next=q->next; free(q); q=s->next;

} s=s->next; q=q->next; } p=p->next; } }

8. 设有一带头结点的单链表，编程将链表颠倒过来。要求不用另外的数组或结点完成。

解：设链表结点的数据类型为： typedef struct Node{

ElemType data; //自定义类型 struct Node *next; }Node;

假定链表的头指针为H，如下的函数实现链表的倒置： void RevLinkList(Node* H){ Node *p=H->next; Node * q=NULL; H->next=NULL; while(p) {

q=p->next; //保存下一个节点的指针

13

2016《数据结构域算法》复习题

p->next=H->next;

H->next=p; //把取出的节点插入到头节点的后面 p=q; } }

9. 统计出单链表HL中结点的值等于给定值X的结点数。

解：设链表结点的数据类型为： typedef struct Node{

ElemType data; //自定义类型 struct Node *next; }Node;

假定链表的头指针为HL，如下的函数统计链表中接点值为X的结点数目： Int CountNodeX(Node * HL, ElemType x){ Int n;

Node* p=HL->next; While(p){

If(p->data==x) n++; P=p->next; }

Return p; }

11．已知非空线性链表的第一个结点的指针为head，请写一个算法，将该链表中数据域值最小的结点移动到链表的最前端。

编写的函数具有如下原型：void func(TLinkNode *head),其中链结点的结构如下： struct TLinkNode { int data; TLinkNode *next; } 请完成该算法。

12. 编写递归算法，计算二叉树中叶子结点的数目。

解：假定二叉树用二叉链表存储，并假定二叉树的结点类型定义如下 struct node { char data;

struct node *lchild, rchild; }node, BiTree*;

再假定n是一个全局整型变量，用来存放二叉树中叶子结点的数目。

如下的函数统计出二叉树t（为指向给定二叉树根的指针）中叶子结点的数目： Int CountLeafNum(BiTree t){

If(t){

CountLeafNum(t->lchild); CountLeafNum(t->lchild); If(!t->lchild && !t->rchild) n++; }

14

2016《数据结构域算法》复习题

}

15