数据结构习题集及参考答案(重要)(7)

③ 冲突处理 ④ 散列函数和冲突处理

三、算法设计题

1． 若线性表中各结点的查找概率不等，则可用如下策略提高顺序查找的效率，若找到指定结点则将该结点和

其前驱结点（如果存在）交换。设计在顺序存储结构上实现上述策略的顺序查找算法。 2． 设计在链式存储结构上建立二叉排序树的算法。 3． 设计判断一棵二叉树是否为二叉排序树的算法。 4． 设计指定结点在二叉排序树中所在层次的算法。

5． 设散列表采用线性探测解决冲突，设计在散列表中查找指定关键字的算法。 6． 设散列表采用链地址法解决冲突，设计在散列表中查找指定关键字的算法。

31

第八章参考答案

一、填空题

1. 1，2，4，8，5，3.7 2. 6.5，37/12 3. 9

4. 索引表，块，和

5. O(n)，O(log2n)，O(n1/2) 6. 大于等于，n/m，大，小 7. 开放定址法，链地址法 8. 16/9，13/9

9. O(log2n)，O(log2n) 10. 中序 11. 25

12. n(n-1)/2

分析：关键字k1需要0次，k2需要1次，k3需要2次，?，kn需要n-1次，则总共需要n(n-1)/2次。

二、选择题 1. (3) 2. (2) 3. (2) 4. (2) 5. (4)

三、算法设计题

1. 若线性表中各结点的查找概率不等，则可用如下策略提高顺序查找的效率，若找到指定结点则将该结点和

其前驱结点（如果存在）交换。设计在顺序存储结构上实现上述策略的顺序查找算法。 int sqsearch(int a[n],int x) {

for(i=0;i<=n-1;i++)

if (a[i]==x){t=a[i];a[i]=a[i-1];a[i-1]=t; return(i);} return(0); }

2. 设计在链式存储结构上建立二叉排序树的算法。

分析：建立二叉排序树的过程实际上就是在空二叉排序树的基础上不断插入新结点的过程，因此本算法主要部分是在二叉排序树上插入结点的算法。

void bstinsert(bitree *&bt,int key) {

if (bt==0){bt=(bitree *)malloc(sizeof(bitree)); bt->key=key;bt->lchild=bt->rchild=0;} else if (bt->key>key) bstinsert(bt->lchild,key); else bstinsert(bt->rchild,key); }

void createbsttree(bitree *&bt) {

int i;

for(i=1;i<=n;i++) bstinsert(bt,random(100)); }

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

32

分析：根据二叉排序树的特性可知中序遍历二叉排序树可以得到一个有序的序列，因此本算法的思想是根据中序遍历时前驱结点的值（根结点的前驱结点值可设置为机内最小的整数）是否小于等于当前结点的值来判断是否是二叉排序树。

int minnum=-32768,flag=1;

typedef struct node{int key; struct node *lchild,*rchild;}bitree; void inorderjudge(bitree *bt) {

if (bt!=0) {

inorderjudge(bt->lchild);

if(minnum>bt->key)flag=0; minnum=bt->key; inordergudge(bt->rchild); } }

4. 设计指定结点在二叉排序树中所在层次的算法。

分析：本题的算法思想是在查找的过程中记录下结点所在的层次，当到某个结点的左子树或右子树中查找时则层数加1，如果找到结点则改变标志变量flag的值并返回。

typedef struct node{int key; struct node *lchild,*rchild;}bitree; int lev=0,flag=0;

void level(bitree *bt,int x) {

if (bt!=0) {

lev++;

if (bt->key==x) {flag=1;return;}

else if (bt->key>x) level(bt->lchild,x); else level(bt->rchild,x); } }

5. 设散列表采用线性探测解决冲突，设计在散列表中查找指定关键字的算法。

struct record {int key; int flag;};

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

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

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

6. 设散列表采用链地址法解决冲突，设计在散列表中查找指定关键字的算法。

typedef struct node {int key; struct node *next;} lklist; lklist *hashlksearch(lklist *hashtable[ ],int k) {

int i=k % p; lklist *s;

for(s=hashtable[i]->next; s!=0; s=s->next) if (s->key==k) return(s); return(0); }

33

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构习题集及参考答案(重要)(7)在线全文阅读。