数据结构习题及答案2009年12月14日

一．选择题 1.C 2.B 3.A 4.C 5.C 6.D

二．判断题 1.× 2.√ 3.× 4.× 5.√ 6.× 7.D 8.D 7.√ 2．不能说哪种哈希函数的选取方法最好，各种选取方法有自己的适用范围。 三．填空题

1．n+1 2．4 3．5 4．AVL树 5．结点的左子树的高度减去结点的右子树的高度 6．直接定址法 7．插入 删除 四．应用题

1．不一定相邻。哈希地址为i（0≤i≤m-1）的关键字，和为解决冲突形成的探测序列i的同义词，都争夺哈希地址i。 2．

哈希地址 0 关键字 14 比较次数 1 1 01 1 2 9 1 3 23 2 4 84 5 27 6 55 1 7 20 2 8 9 3 4 平均查找长度：ASLsucc=（1+1+1+2+3+4+1+2）/8=15/8

以关键字27为例：H（27）=27%7=6（冲突） H1=（6+1）=7（冲突）

23

H2=（6+2）=0（冲突） H3=（6+3）=5 所以比较了4次。 3．（1） 哈希地址 0 1 2 3 4 关键字 比较次数 1 1 2 5 1 6 1 7 2 8 3 9 1 10 11 1 3 12 3 0 3 29 200 32 45 58 100 10 126 400 关键字29和45各发生一次冲突，关键字58,126和400各发生两次冲突，其余关键字无冲突。 （2）

哈希地址 0 关键字 比较次数 1 1 1 2 2 3 4 1 3 5 1 6 3 7 8 9 8 1 10 2 11 12 1 58 10 100 3 200 32 400 0 45 126 29 发生冲突次数：100，126一次；200，400两次；0七次。其余关键字无冲突。 五．算法设计题

1．非递归建立二叉排序树，在二叉排序树上插入的结点都是叶子结点。 void Creat_BST（BiTree bst，datatype K[]，int n）

// 以存储在数组K中的n个关键字，建立一棵初始为空的二叉排序树。 {for（i=1；i≤n；i++）

{p=bst；f=null；//在调用Creat_BST时，bst=null while（p!=null）

if（p->dataRLINK； } // f是p的双亲 else if（p->data>K[i]）{ f=p；p=p->LLINK；} s=（BiTree）malloc（sizeof （BiNode））；// 申请结点空间 s->data=K[i]；s->LLINK=null；s->RLINK=null； if（f==null）bst=s； //根结点 else if（s->datadata）f->LLINK=s；//左子女

else f->RLINK=s；//右子树根结点的值大于等于根结点的值

25

}//算法结束

第9章 排序

一、选择题 1.B 2.B 3.D 4.A 5.B 6.C 7.D 8.D 9.A 10.A 11.C 12.B 13.D 14.D 二、判断题

1.× 2.× 3.× 4.× 5.× 6.√ 7.× 8.× 9.× 10.× 10.错误。待排序序列为正序时，简单插入排序比归并排序快。 三、填空题

1.比较,移动 2.免去查找过程中每一步都要检测整个表是否查找完毕，提高了查找效率。 3.n(n-1)/2 4.

{D,Q,F,X,A,P,B,N,M,Y,C,W} 四、应用题 1. 排序方法 直接插入排序 折半插入排序 起泡排序 简单选择排序 希尔排序 快速排序 堆排序 2-路归并排序 基数排序 平均时间 2最坏情况 2辅助空间 稳定性 不稳定排序举例 O（n） O（n） O（1） 22O（n） O（n） O（1） 22O（n） O（n） O（1） 22O（n） O（n） O（1） 1.31.3O（n） O（n） O（1） 2O（nlog2n） O（n） O（log2n） O（nlog2n） O（nlog2n） O（1） O（nlog2n） O（nlog2n） O（n） O(d*(rd+n)) O(d*(rd+n)) O (rd ) 稳定 稳定 稳定 不稳定 2,2’,1 不稳定 3,2,2’,1(d=2,d=1) 不稳定 2,2’,1 不稳定 2,1,1’(极大堆) 稳定 稳定 2.这种说法不对。因为排序的不稳定性是指两个关键字值相同的元素的相对次序在排序前、

后发生了变化，而题中叙述和排序中稳定性的定义无关，所以此说法不对。对4，3，2，1起泡排序就可否定本题结论。

3.(1)堆排序，快速排序，归并排序 (2)归并排序 (3)快速排序 (4)堆排序

4.用堆排序方法。从序列{59，11，26，34，14，91，25}得到{11，17，25}共用14次比较。其中建堆输出11比较8次，调堆输出17和25各需要比较4次和2次。 5. (1)排序结束条件为没有交换为止

第一趟奇数：35,70,33,65,21,24,33 第二趟偶数：35,33,70,21,65,24,33 第三趟奇数：33,35,21,70,24,65,33 第四趟偶数：33,21,35,24,70,33,65 第五趟奇数：21,33,24,35,33,70,65 第六趟偶数：21,24,33,33,35,65,70 第七趟奇数：21,24,33,33,35,65,70(无交换) 第八趟偶数：21,24,33,33,35,65,70(无交换) 结束 五.算法设计题

1. void BubbleSort2(int a[],int n) //相邻两趟向相反方向起泡的冒泡排序算法

{ change=1;low=0;high=n-1; //冒泡的上下界

while(low

{ change=0; //设不发生交换 for(i=low;i

26

if(a[i]>a[i+1]){a[i]<-->a[i+1];change=1;} //有交换，修改标志change high--; //修改上界

for(i=high;i>low;i--) //从下向上起泡

if(a[i]a[i-1];change=1;} low++; //修改下界 }//while

}//BubbleSort2

[算法讨论]题目中“向上移”理解为向序列的右端，而“向下移”按向序列的左端来处理。

27