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 -