数据结构第九章习题

《数据结构第九章习题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第九章查找一、选择题1.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为（C）oB.n/2C.(n+l)/2D.n2.下面关于二分查找的叙述正确的是A.表必须有序，表可以顺序方式存储，也可以链表方式存储C.表必须有序，而且只能从小到大排列B.表必须有序且表中数据必须是整型，实型或字符型D.表必须有序，且表只能以顺序方式存储3.用二分（对半）查找表的元素的速度比用顺序法A.必然快B.必然慢C.相等D.不能确定4.具有12个关键字的有序表，折半查找的平

2、均查找长度（A）A.3.1B.4C.2.5D.55・当采用分块查找时，数据的组织方式为（B）A.数据分成若干块，每块内数据有序B・数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块C.数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块A.数据分成若干块，每块(除最后一块外)中数据个数需相同B.结点的多少D.结点的位置(2):A.结点太多B.完全二叉树呈单枝树D.结点太复杂。c.6.二叉查找树的查找效率与二叉树的(C(l))有关,在((2)C)时其查找效

3、率最低c.(1):A.高度树型7.对大小均为n的有序表和无序表分别进行顺序查找，在等概率查找的情况下,对于查找失败，它们的平均查找长度是(B(l)),对于查找成功，他们的平均查找长度是(A(2))供选择的答案：A.相同的B.不同的序列所构造的结果不同的是(A.(100,80,90,60,(100,120,110,130,80,C.(100,60,80,90,9.分别以下列序列构造二叉排序树，与用其它三个)120,110,130)B.60,90)120,110,130)D.(100,80,60,90,120,

4、130,110)三、填空题1.顺序查找n个元素的顺序表，若查找成功，贝!)比较关键字的次数最多为n次;当使用监视哨时,若查找失败，则比较关键字的次数为n+1。2・在有序表AE1..12］中，采用二分查找算法查等于A［12］的元素，所比较的元素下标依次为_691112o8.如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为_(n+l)/2o10.平衡因子的定义是14・可以唯一的标识一个记录的关键字称为15.动态查找表和静态查找表的重要区别在于前者包含有和运算，

5、而后者不包含这两种运算。k应用题9.输入一个正整数序列(53,17,12,66,58,70,87,25,56,60),试完成下列各题。(1)按次序构造一棵二叉排序树BSo(2)依此二叉排序树，如何得到一个从大到小的有序序列？(3)假定每个元素的查找概率相等，试计算该二叉排序树的平均查找长度(4)画出在此二叉排序树中删除“66”后的树结构。12.假定对有序表：(3,4,5,7,24,30,42,54,63,72,87,95)进行折半查找，试回答下列问题：(1)•画出描述折半查找过程的判定树；(2)・若查找元素

6、54,需依次与那些元素比较？(3)・若查找元素90,需依次与那些元素比较？(4)•假定每个元素的查找概率相等，求查找成功时的平均查找长度。