数据结构Ch9习题答案

1、Ch9查找一、单项选择题1 .顺序查找法适合于存储结构为B的线性表。A.散列存储B.顺序存储或链接存储C .压缩存储D.索引存储2. 对线性表进行二分查找时，要求线性表必须CoA .以顺序方式存储B.以链接方式存储C.以顺序方式存储，且结点按关键字有序排序D.以链接方式存储，且结点按关键字有序排序3. 采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为C oA. nB. n/2C. (n+1)/2D . (n-1)/24. 采用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为D oA . O(n2)B . O(nl og2 n)C . O( n)D . O(log2

2、n)5 .二分查找和二叉排序树的时间性能BoA.相同B.不相同就平均时间性能而言，二叉排序树上的查找和二分查找差不多 就维护表的有序性而言，二叉排序树无须移动结点，只需修改指针即可完成插入和删除操作，且其平均的执行时间均为O(log 2n)，因此更有效。二分查找所涉及的有序表是一个向量，若有插入和删除结点的操作，则维护表的有序性所花的代价 是O(n)。当有序表是静态查找表时，宜用向量作为其存储结构，而采用二分查找实现其查找操作；若有序表里动态查找表， 则应选择二叉排序树作为其存储结构。6 .有一个有序表为1，3, 9，12, 32，41, 45，62, 75，77，82, 95，100，当二分

3、查找值 82为的结点时，C次比较后查找成功。A . 1 B . 2 C . 4 D . 8456789101112 B4175957有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下 查找成功所需的平均比较次数为 BoA. 35/12B . 37/12C. 39/12D . 43/12 8根据一组记录(56, 42, 50, 64, 48 )依次插入结点生成一棵 AVL树(高度平衡的二叉搜索 树)时，当插入到值为50的结点时需要进行旋转调整。9. 向一棵二叉搜索树中插入一个新元素时，若该新元素的值大于根结点的值，则应把它插入 到根结点右子树上。10. 根据一组记录(

4、56, 42, 73, 50, 64, 48, 22 )依次插入结点生成一棵 AVL树(高度平衡的二 叉搜索树)时，当插入到值为 48的结点时才出现不平衡，需要进行旋转调整。11 以顺序搜索方法从长度为n的顺序表或单链表中搜索一个元素时，其时间复杂度为O(n)12在一棵AVL树(高度平衡的二叉搜索树)中，每个结点的左子树高度与右子树高度之差 的绝对值不超过1。13在线性表的散列存储中，装载因子 a又称为装载系数，若用m表示散列表的长度，n表 示待散列存储的元素的个数，则 a等于n/m。14以折半搜索方法从长度为n的有序表中搜索一个元素时，时间复杂度为O(log2n)。15假定一个顺序表的长度为

5、40,并假定搜索每个元素的概率都相同，则在搜索成功情况下 的平均搜索长度为20.5。16假定要对长度n = 100的线性表进行散列存储，并采用开散列法处理冲突，则对于长度m =20的散列表，每个散列地址的同义词子表(单链表)的长度平均为5。17假定对长度n = 50的有序表进行折半搜索，则对应的判定树中最后一层的结点数为19个。1 2 4 8 16 1918根据n个元素建立一棵二叉搜索树(二叉排序树)的时间复杂度性大致为 0(nlog2n)。19从一棵二叉搜索树中搜索一个元素时，若给定值小于根结点的值，则需要向左子树 继续搜索。20、 假定一个线性表为(” abed”，” baabc”，” b

6、eef”，” cfg ”，” ahij”，” bkwte”，” ccdt”，” aayb ),若按照字符串的第一个字母进行划分，使得第一个字母相同的字符串被划分在一个 子表中，则得到的以a为第一个字母的子表长度 3 o21、 假设在有序线性表A1. 20上进行二分查找，则比较一次查找成功的结点数为1，则比 较二次查找成功的结点数为2,则比较三次查找成功的结点数为 4,则比较四次查找成功的结 点数为8,则比较五次查找成功的结点数为 5,平均查找长度为3. 7o22、 对于长度为n的线性表，若进行顺序查找，则时间复杂度为O(n);若采用二分法查找， 则时间复杂度为O(log2n) o23、对长度为

7、3的顺序表进行搜索，若搜索第一个元素的概率为1/2,搜索第二个元素的概率为1/3,搜索第三个元素的概率为1/6,则搜索到表中任一元素的平均搜索长度为A oA. 5/3B. 2 C. 7/3 D. 4/31/2*3+1/3*2+1/6*1=9/6+4/6+1/6=7/31/2*1+1/3*2+1/6*3=3/6+4/6+3/6=5/324、向一棵AVL树(高度平衡的二叉搜索树)插入元素时，可能引起对最小不平衡子树的双向旋转的调整过程，此时需要修改相关C个结点指针域的值。A. 2 B . 3C. 4 D . 525、向一棵AVL树(高度平衡的二叉搜索树)插入元素时，可能引起对最小不平衡子树的调整过

8、程，此调整分为C种旋转类型。A . 2 B . 3C . 4 D . 526、向一棵AVL树(高度平衡的二叉搜索树)插入元素时，可能引起对最小不平衡子树的左单或右单旋转的调整过程，此时需要修改相关C个结点指针域的值。A . 2 B . 3C . 4 D . 5三、判断题：1 . ( X )对二叉搜索树进行前序遍历得到的结点序列是一个有序序列。2 . (V)折半搜索所对应的判定树，既是一棵二叉搜索树，又是一棵理想平衡二叉树(它的特点是除最底层结点外其他各层结点数都是满的，最底层的若干结点可能散布在该层各处)。3 . (V)装载因子是散列表的一个重要参数，它反映了散列表的装满程度。4 . (V)对

9、于两棵具有相同记录集合而具有不同结构的二叉搜索树，按中序遍历得到的结点序 列是相同的。三、综合练习题：1 .画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找 长度。2345678910J S1 L1 bmII1 mhhhIF i m hh等概率时查找成功的平均查找长度 =(1*1+2*2+4*3+3*4)/10=2 . 92.已知一组关键字49, 38, 65, 97, 76, 13, 27, 44, 82, 35, 50，画出由此生成的二叉 排序树和平衡二叉树。平衡二叉树:二叉排序树：49)876»7)©977649(27：76西)2776(

10、1365657(97=9713651328657：3565134444；822844828250Q8)縫双向旋转| >49(49 ©5：(65：双向旋转 /汽双向旋转® c= B05)3 设某字典组成如下：D=016, 087, 154, 170, 275, 426, 503, 509, 512, 612, 653, 677, 703, 765, 897, 908依次顺序表示在内存中，现用二分法的方法查找字典中是否有元素612,问需要进行多少次比较才能得到结论？每次选择的比较对象是什么元素？解：比较次数为3次，第一次和509比较，第二次和677比较，第三次和612比较

11、。10016037 154170275426503509512612653677 703 76589790812345678910 11 1213 14 1516t ht hntI m h t m t mlrrlht mf hmI m hXT mA A * 从m t ht ht ht h 社I m t m twIm h t mt m *111 I I m hAVL树时四种调整平衡操作4.试给出一个关键码序列，使构造 行一次，并画出其构造过程。(LL, LR, RR, RL )各至少执:解：设输入序列为12，6，4，16,24，15，13，1，35.设顺序表中关键字是递增有序的，试写一顺序查找算

12、法，将哨兵设在表的高下标端 解:Search_Seq(SSTable ST, KeyType key)顺序查找的算法，n号元素为监视哨ST. elemn. key=key; / 哨兵for (i=0; !EQ(ST . elemi. key,key);+i);return i;6. 什么叫静态查找？什么叫动态查找？什么样的存储结构适宜于进行静态查找？什么样的存 储结构适宜于进行动态查找？7. 什么叫平均查找长度？写出平均查找长度的定义。8. 已知一个个数为 12 的数据元素序列为Dec, Feb, Nov, Oct, June, Sept, Aug, Apr, May, July, Jan,

13、Mar，要求：(1)按各数据元素的顺序构造一棵二叉排序树。(2)设各数据元素的查找 概率相等，给出该二叉排序树的平均查找长度。(注：字母的大小是指字母的ASCII码数值大 小)(3)按各数据元素的顺序构造一棵平衡二叉树。解：(1)构造的二叉排序树：(2) 平均查找长度为：(1*1+2*2+2*3+2*4+3*5+2*6 ) /12=46/12=23/6(3) 构造的平衡二叉树：9.使用散列函数hash (x) = x %11,把一个整数值转换成散列表地址。 现要把数据1, 13, 12, 34, 38, 33, 27, 22插入到散列表中。(1) 使用线性探查再散列法来构造散列表。(2) 使用

14、链地址法构造散列表。针对这两种情况，确定其装载因子，搜索成功所需的平均探查次数，以及搜索不成功所需的 平均探查次数。解：(1)Hash(1)=1 ；成功hash(13)=2 成功hash(12)=1；冲突；hash(12)=2；冲突；hash(12)=3;成功；hash(34)=1 ； hash(34)=2 冲突；hash(34)=3;冲突；hash(34)=3;冲突；hash(34)=4；成功 hash(38)=5;成功hash(33)=0 成功hash(27)=5;冲突；hash(27)=6;成功hash(22)=0;冲突；hash(22)=1;冲突；hash(22)=2 冲突；hash(22)=3;冲突；hash(22)=4; 冲突；hash(22)=5;冲突；hash(22)=6;冲突；hash(22)=7;成功线性探查再散列法来构造的散列表01234567891033113123