数据结构总复习

10.实现在带头结点的单链表尾部插入新元素X的操作。

1 int instail(linklist*head,datatype x) 1分 {linklist *p,*s; p=head; 1分

s=(linklist*)malloc(sizeof(linklist)); 1分

if(s==NULL) {printf(“malloc failure!”); return NULL;} s->data=x; 1分 s->next=NULL; 1分 while(p->next!=NULL) 1分 p=p->next; 2分 p->next=s; 2分 return TRUE; }

11.以二叉链表为存储结构，试编写求二叉树高度的算法。

int depth(bitree* t) 1分 { int dep1,dep2;

if(t==NULL) return 0; 1分 else {

dep1=depth(t->lchild); 2分 dep2=depth(t->rchild); 2分

if(dep1>dep2) return(dep1+1) ; 2分 else return(dep2+1); 2分 } }

- 16 -

12设计一个求结点x在二叉树中的双亲结点算法。

13. 设计在链式存储结构上建立一棵二叉树的算法。

14. 设计判断一棵二叉树是否是二叉排序树的算法。

15.设有一组初始记录关键字序列（K1，K2，…，Kn），要求设计一个算法能够在O(n)的时间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于Ki，右半部分的每个关键字均大于等于Ki。

15. 设有两个集合A和集合B，要求设计生成集合C=A∩B的算法，其中集合A、B和C用链

式存储结构表示。

- 17 -

17设计在单链表中删除值相同的多余结点的算法。

18.下列算法实现在顺序散列表中查找值为x的关键字，请在下划线处填上正确的语句。

struct record{int key; int others;};

int hashsqsearch(struct record hashtable[ ],int k) {

int i,j; j=i=k % p;

while (hashtable[j].key!=k&&hashtable[j].flag!=0){j=(____) %m; if (i==j) return(-1);} if (_______________________ ) return(j); else return(-1); }

19.下列算法实现在二叉排序树上查找关键值k，请在下划线处填上正确的语句。

typedef struct node{int key; struct node *lchild; struct node *rchild;}bitree; bitree *bstsearch(bitree *t, int k) {

if (t==0 ) return(0);else while (t!=0)

if (t->key==k)_____________; else if (t->key>k) t=t->lchild; else_____________; }

20.设计在链式存储结构上交换二叉树中所有结点左右子树的算法。

- 18 -