数据结构第七章参考答案
- 格式：doc
- 大小：141.50 KB
- 文档页数：4
习题7
1. 填空题
（1）由10000个结点构成的二叉排序树，在等概率查找的条件下，查找成功时的平均查找长度的最大值可能达到（___________）。
答案：5000.5
（2）长度为11的有序序列：1，12，13，24，35，36，47，58，59，69，71进行等概率查找，如果采用顺序查找，则平均查找长度为（___________），如果采用二分查找，则平均查找长度为（___________），如果采用哈希查找，哈希表长为15，哈希函数为H（key）＝key%13，采用线性探测解决地址冲突，即di=(H(key)+i)%15，则平均查找长度为（保留1位小数）（___________）。
答案：6，3，1.6
（3）在折半查找中，查找终止的条件为（___________）。
答案：找到匹配元素或者low>high?
（4）某索引顺序表共有元素275个，平均分成5块。若先对索引表采用顺序查找，再对块元素进行顺序查找，则等概率情况下，分块查找成功的平均查找长度是（___________）。
答案：31
（5）高度为8的平衡二叉树的结点数至少是（___________）。
答案： 54 计算公式：F(n)=F(n-1)+F(n-2)+1
（6）对于这个序列{25，43，62，31，48，56}，采用的散列函数为H(k)=k%7，则元素48的同义词是（___________）。
答案：62
（7）在各种查找方法中，平均查找长度与结点个数无关的查找方法是（___________）。
答案：散列查找
（8）一个按元素值排好的顺序表（长度大于2），分别用顺序查找和折半查找与给定值相等的元素，平均比较次数分别是s和b，在查找成功的情况下，s和b的关系是（___________）；在查找不成功的情况下，s和b的关系是（___________）。
答案：(1)(2s-1)b=2s([log2(2s-1)]+1)-2[log2(2s-1)]+1+1
(2)分两种情况考虑，见解答。
解： (1)设所有元素的个数为n，显然有s=n*(n+1)/(2n),则
n=2s-1
设折半查找树高度为k，则前k-1层是满二叉树，最后一层的节点数为
n-(2k-1 -1）
因此，总比较次数
nb=20*1+21*2+22*3+…+2k-2*(k-1)+(n-(2k-1 -1))*k,
而
20*1+21*2+22*3+…+2k-2*(k-1)=2k-1*k-2k+1
因此
nb=2k-1*k-2k+1+(n-(2k-1-1))*k=(n+1)k-2k+1
又k=[log2n]+1,n=2s-1,所以有
(2s-1)b=2s([log2(2s-1)]+1)-2[log2(2s-1)]+1+1
(2)查找不成功，对于顺序查找有：s=n。对于折半查找，找不到的情况有n+1种,查找到每个叶子节点或度为1的节点后就不再查找，设折半查找树高度为k，则第k-1层的节点数x=2k-2，第k层的节点数y=n-(2k-1 -1）
（a）当第k层的节点数y小于等于第k-1层的节点数x时，
则第k-1层有y结点度为1，其余x-y个结点度为0。
则查找次数为：(n+1)b=2yk+2(x-y)(k-1)+y(k-1)=2x(k-1)+yk
(n+1)b=2k-1 *(k-1)+(n-(2k-1 -1))*k
（b）当第k层的节点数y大于第k-1层的节点数x时，
则第k-1层不存在度为0的结点，有2x-y个结点度为1，其余y-x个结点度为2
则查找次数为：(n+1)b=2yk+(2x-y)(k-1)=2x(k-1)+y(k+1)
(n+1)b=2k-1 *(k-1)+(n-(2k-1 -1))*(k+1)
将k=[log2n]+1，n=s分别代入（a）（b）两个等式即得。
2. 选择题
（1）从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较（ ）个结点。
A. n B. n/2 C. (n-1)/2 D. (n+1)/2
（2）对一个长度为50的有序表进行折半查找，最多比较（ ）次就能查找出结果。
A. 6 B. 7 C. 8 D. 9
（3）对有18个元素的有序表做折半查找，则查找A[3]（下标从1开始）的比较序列的下标依次为（ ）。
A. 1-2-3 B. 9-5-2-3 C. 9-5-3 D. 9-4-2-3
（4）在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡点为A，并已知A的左孩子的平衡因子为－1，右孩子的平衡因子为0，则做（ ）型调整以使其平衡。
A. LL B. LR C. RL D. RR
（5）理论上，散列表的平均比较次数为（ ）次。
A. 1 B. 2 C. 4 D. n
（6）二叉排序树中，最小值结点的（ ）。
A. 左指针一定为空 B. 右指针一定为空
C. 左、右指针均为空 D. 左、右指针均不为空
（7）散列技术中的冲突指的是（ ）。
A.两个元素具有相同的序号 B. 两个元素的键值不同，而其他属性相同
C. 数据元素过多 D. 不同键值的元素对应于相同的存储地址
（8）散列表表长m=14，散列函数H(k)=k%11。表中已有15，38，61，84四个元素，如果用线性探测法处理冲突，则元素49的存储地址是（ ）。
A. 8 B. 3 C. 5 D. 9
（9）采用线性探测法处理冲突所构成的闭散列表上进行查找，可能要探测多个位置，在查找成功的情况下，所探测的这些位置的键值（ ）。
A. 一定都是同词义词 B. 一定都不是同义词
C. 不一定都是同义词 D. 都相同
（10）静态查找与动态查找的根本区别在于（ ）。
A. 它们的逻辑结构不一样
B. 施加在其上的操作不同
C. 所包含的数据元素的类型不一样
D. 存储实现不一样
3．设一个散列表包含hashSize=13个表项，其下标从0到12，采用线性探查法解决冲突，请按以下要求，将关键码{10，100，32，45，58，126，3，29，200，400，0}散列到表中。
（1）散列函数采用除留余数法，用%hashSize(取余运算)将各关键码映像到表中，请指出每一个产生冲突的关键码可能产生多少次冲突。
答案：如下表，
H(key) 0 1 2 3 4 5 6 7 8 9 10 11 12
key 0 3 29 200 32 45 58 100 10 126 400
产生冲突的关键码有：29－1次，45－1次，58－2次，126－2次，400－2次
（2）散列函数采用先将关键码各位数字折叠相加，再用%hashSize将相加的结果映像到表中的办法，请指出每一个产生冲突的关键码可能产生多少次冲突。
答案：如下表，
H(key) 0 1 2 3 4 5 6 7 8 9 10 11 12
key 58 10 100 3 200 32 400 0 45 126 29
产生冲突的关键码有：100－1次，200－2次，400－2次，0－7次，126－1次
4．试编写一个函数，完成拉链法解决冲突的散列表上删除一个指定结点的算法。
5．设散列表的长度为13，散列函数为H(k)=k%13，给定的关键字序列为：19，14，23，01，68，20，84，27，55，11，10，79。试画出分别用拉链法和线性探测查找解决冲突时所构造的散列表，并求出在等概率情况下，这两种方法的查找成功和查找不成功的平均查找长度。
答案：拉链法：
1367101119142316820842755111079
平均查找次数：成功时是21/12=1.75次，不成功时是(4+2+2+2+1+2+1)/13=12/13=0.92次（在这里查找比较是指元素值的比较。如果指针为空，则不进行查找比较，此时不算查找）。
线性探测法：
H(key) 0 1 2 3 4 5 6 7 8 9 10 11 12
key 14 01 68 27 55 19 20 84 79 23 11 10
冲突次数 0 1 0 3 2 0 0 2 8 0 0 2
成功时的比较 1 2 1 4 3 1 1 3 9 1 1 3 次数
不成功时的比较次数 0 12 11 10 9 8 7 6 5 4 3 2 1
平均查找次数：成功时是2.5次，不成功时ASL=（0+12+11+10+9+8+7+6+5+4+3+2+1）/13 =
6次。
