句完成在散列表hashtalbe中查找关键字值等于k的结点，成功时返回指向关键字的指针，不成功时返回标志0。

typedef struct node {int key; struct node *next;} lklist; void createlkhash(lklist *hashtable[ ]) {

int i,k; lklist *s;

for(i=0;i<m;i++)_____________________; for(i=0;i<n;i++) {

s=(lklist *)malloc(sizeof(lklist)); s->key=a[i];

k=a[i] % p; s->next=hashtable[k];_______________________; } }

三、算法设计题(28分)

1． 设单链表中有仅三类字符的数据元素(大写字母、数字和其它字符)，要求利用原单链表中结点空间设计出三个单链表的算法，使每个单链表只包含同类字符。

2. 设计在链式存储结构上交换二叉树中所有结点左右子树的算法。 3. 在链式存储结构上建立一棵二叉排序树。

数据结构试卷（四）参考答案

一、选择题 1．C 2．D 6．A

7．B

二、填空题

1. O(n2)，O(nlog2n)

2. p>llink->rlink=p->rlink; p->rlink->llink=p->rlink 3. 3 4. 5. 6. 7. 8.

2k-1 n/2 50，51

m-1，(R-F+M)%M n+1-i，n-i

3．D 8．A

4．B 9．C

5．C 10．A

9. (19，18，16，20，30，22) 10. (16，18，19，20，32，22) 11. A[i][j]=1 12. 等于

13. BDCA

14. hashtable[i]=0，hashtable[k]=s

三、算法设计题

1. 设单链表中有仅三类字符的数据元素(大写字母、数字和其它字符)，要求利用原单链表中结点空间设计出三个单链表的算法，使每个单链表只包含同类字符。 typedef char datatype;