10.散列表中解决冲突的两种方法是_____________和_____________。

四、算法设计题(20分) １． 设计在顺序有序表中实现二分查找的算法。 ２． ３．

设计判断二叉树是否为二叉排序树的算法。 在链式存储结构上设计直接插入排序算法

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

一、选择题 1．D 6．D 11．C

2．A 7．B

3．A 8．A 14．D

4．A 9．C

5．D 10．B

12．A 13．B 15．B

二、判断题 1．错 6．错

2．对 7．对

3．对 8．错

4．对 9．对

5．错 10．对

三、填空题 1. O(n)

2. s->next=p->next; p->next=s 3. (1，3，2，4，5) 4. n-1 5. 129 6. 7. 8. 9. 10.

F==R

p->lchild==0&&p->rchild==0 O(n2)

O(nlog2n)， O(n)

开放定址法，链地址法

四、算法设计题

1. 设计在顺序有序表中实现二分查找的算法。 struct record {int key; int others;}; int bisearch(struct record r[ ], int k) {

int low=0,mid,high=n-1; while(low<=high) {

mid=(low+high)/2;

if(r[mid].key==k) return(mid+1); else if(r[mid].key>k) high=mid-1; else low=mid+1; }

return(0);

}

2. 设计判断二叉树是否为二叉排序树的算法。

int minnum=-32768,flag=1;

typedef struct node{int key; struct node *lchild,*rchild;}bitree;