数据结构练习8

1、第八章 查找 习 题 91 判断题(在你认为正确的题后的括号中打，否则打X)。 (1)用来惟一区分文件中不同记录的属性或属性组称为主关键字。 ( ) (2)查找成功与否的关键在于是否按主关键字查找。 ( ) (3)顺序文件必须用一片地址连续的存储空间来存放。 ( ) (4)只有在顺序存储结构上才能采用顺序查找方法。 ( ) (7)只要按值有序排列的线性表采用顺序存储结构就可以采用折半查找方法。 ( ) (8)建立稠密索引的优点是节省存储空间。 ( ) (9)分块查找的效率与文件中的记录被分成多少块有关。 ( ) (10)分块查找过程是首先查找索引表，然后再到相应的块中具体查找记录。 ( ) (

2、11)B-树和B十树都是用来实现动态索引的。 ( ) (12)在B-树上可以进行顺序查找。 ( 1 (13)在B+树上可以进行顺序查找。 1 (14)采用散列方法存储线性表，不能存储数据元素之间的关系。 ( ) (15)在散列文件中进行查找不涉及关键字的比较。 ( ) (16)散列冲突是指同一个关键字对应了多个不同的散列地址。 ( ) (17)散列表的负载因子等于存人散列表中的关键字的个数。 ( ) (18)在散列表的查找过程中，关键字的比较次数与表中关键字的数目直接相关。 ( )(19)在利用线性探测法处理冲突的散列表中，散列函数值相同的关键字总是存放在一片地址连续的存储单元中。 (20)在

3、采用链地址法处理冲突的散列表中，散列函数值相同的关键字是链接在同一个链表中的。 ( ) 92单项选择题。 (1)衡量查找算法性能好坏的主要标准是 。 A参加比较的关键字值的多少 B被查找的关键字值在关键字序列中的位置 C.关键字序列中是否存在被查找关键字值 D关键字值的平均比较次数的多少 (2)顺序查找方法的优点之一是 。 · A对于被查找对象几乎没有限制 B适合排序连续顺序文件的查找 C.适合链接顺序文件的查找 D查找时间效率高 (3)对线性表采用折半查找，该线性表必须 。 A元素按值有序排列 B采用顺序结构 C元素按值有序排列，并且采用顺序存储结构 n元素按值有序排列，并且采用链

4、式存储结构 (4)下面的说法中，不正确的是。 A折半查找方法不适用于按值有序链接的链表的查找 B折半查找方法适用于按值有序的顺序表的查找 C.折半查找方法适用于按关键字值大小有序排列的顺序文件的查找 D折半查找方法适用于排序连续顺序文件的查找 (5)在有序表(k1，k2，k9，)中采用折半查找方法查找99次，其中，至少有一个元素被比较了99次，该元素是。 AK99 Bk50 CK49 Dk1 (6)为了实现分块查找，线性表必须采用结构。 A顺序存储 B链式存储 C索引存储 D散列存储 (7)只能在顺序存储结构上才能实现的查找方法是 法。 A顺序查找 B树型查找 C折半查找 D散列查找 (8)在

5、具有15个记录的排序连续顺序文件上采用折半查找方法查找一个文件中不存在的记录，需要进行次关键字的比较。 A0 B4 C5 D15 (9)若在100个记录中查找其中任意一个记录，最多只要比较5次，则所采用的查找方法可能是。 A折半查找 B树型查找 C分块查找 D散列查找 (10)若在n个记录中查找其中任意一个记录至少要比较2次，则所采用的查找方法可能是 A分块查找 B折半查找 C树型查找 D散列查找 (11)折半查找过程可以利用一棵称之为判定树的二叉树来描述。在长度为12的序列中进行折半查找对应的判定树的根结点的右孩子的值(某元素在序列中的位置)是。 A7 B8 C9 D10 (12)若在序列中

6、采用折半查找方法进行查找，用来描述该查找过程的判定树的形状与有关。 A序列中元素的值 B序列中元素的排列次序 C序列中元素的类型 D序列中元素的个数 (13)在某序列中采用折半查找方法查找某个元素，依次被比较过的元素在该序列中的位置只能是。 A10，15，12，18，19 B10，15，12，13，14 C10，15，16，18，19 D10，15，11，13，14 (14)在某序列中采用折半查找方法查找某个元素，依次被比较过的元素在该序列中的位置不可能是。 A10，5，7，8，9 B10，5，2，1 C10，5，6，7，8 D10，5，7，6 (15)将数据元素2，4，6，8，10，12，1

7、4，16，18，20依次存放于一个一维数组中，然后采用折半查找方法查找元素12，被比较过的数组元素的下标依次为。 A10，16，12 B10，12，16 C4，7，5 D4，5，7 (16)索引文件中的索引表具有的特点是。 A索引项按关键字值有序，并且由用户提供 B索引项按关键字值有序，并且由系统提供 C索引项按关键字值无序，并且由用户提供 D索引项按关键宇值无序，并且由系统提供 (17)m阶B-树中的m是指。 A每个结点至少具有m棵子树 B每个结点最多具有m棵子树 C分支结点中包含的关键字的个数 Dm阶B-树的深度 (18)下面关于B-树和B+树的叙述中，不正确的是。 AB-树和B+树都是平

8、衡的多分树 BB-树和B+树都可以用于文件的索引结构 DB树和B+树都能有效地支持随机检索 (19)下面的命题中，不成立的是 。 Am阶B-树中的每一个分支结点的子树的数量都小于或等于m。 Bm阶B-树中的每一个分支结点的子树的数量都大于或等于m2上取整 Cm阶B-树中的任何一个结点的子树的深度都相等。 Dm阶B树中有k个子树的分支结点包含k1个关键字。 (20)评价散列函数质量好坏的标准是。 A函数是否简单 B计算是否快 C是否是解析式 D函数的取值是否均匀 (21)在一个初始状态为空的散列表中依次插入关键字序列(MON，TUE，WED，THU，FRI， SAT，SUN)，散列函数为H(ke

9、y)：i7，其中，i为关键字key的第一个字母在英文字母表中的序号，地址值域为0：6，采用线性再散列法处理冲突。 (22)在具有n个元素的序列中进行查找，平均查找长度为O(n)的方法是。 A顺序查找方法 B散列查找方法 C分块查找方法 D树型查找方法 93 填空题。 (1)文件的逻辑结构是指，文件的物理结构是指。 (2)文件在物理结构中通常有、和三种组织方式。 (3)文件的关键字是。 (4)文件最基本操作是 和 。 (5)对线性表采用折半查找方法，该线性表必须采用存储结构，并且。 (6)在按值有序的线性表(5，8，11，12，15，20，32，41，57)中采用折半查找法查找20需要进行次元素

10、间的比较。 (7)具有n个结点的判定树的深度h = 。 (8)若每个记录的查找概率相等，则在具有n个记录的顺序文件中采用顺序查找法的平均查 找长度ASL=。 (9)在具有n个记录的排序连续顺序文件中采用折半查找法的平均查找长度ASL=？ (10)索引文件的索引表中的一个索引项是之间的对照关系。 (11)索引文件包括和两个部分。 (12)索引表的特点是，并且。 (13)在索引文件中查找一个记录的过程是先查，然后。 (14)具有144项的表分成块最好，若每块的最佳长度为8，则平均查找长度为 (15)在3阶B-树上，每个分支结点包含的子树的数目最多为，最少为。 (16)一棵B+树上通常有两个头指针(

11、即查找的人口指针)，其中一个指向，另一个指向。 (17)散列函数建立了之间的对应关系。 (18)设计一个散列表通常应包括三个内容，分别是、和。 (19)一个好的散列函数是指。处理冲突的方法通常有、和一O (20)一个待散列存储的线性表为K二(18，25，63，50，42，32，9)，散列函数为H(k)：k9，则与元素18发生冲突的元素有个。 94 试叙述索引顺序文件与顺序文件相比较的优缺点，指出一种适用于索引顺序文件的外存设备。 95 已知一个长度为12的线性表(Dec，Feb，Nov，Oct，Jul，Sept，Aug,Apr，May,Jun,Jan，Mar)。 (1)按该线性表中元素的顺序构

12、造出一棵二叉排序树； (2)若每个元素的查找概率均等，查找此二叉排序树中任意一个结点的平均查找长度ASL是多少? (3)若对线性表的元素按字典顺序从小到大排列以后，再用折半查找方法，则查找其中任意一个元素的平均查找长度ASL是多少? (4)画出相应的平衡二叉树。 96 折半查找过程可以利用一棵判定树来描述。请画出n13时的判定树。 97 何谓散列冲突?何谓冲突处理?简要说明冲突处理的过程。 98 已知散列函数为H(k)二k7，并采用线性探测再散列方法处理冲突，所建立的散列表如下所示，请依次将关键字17，27填人表中。 99 在初始为空的散列表中依次插入以下关键字序列：Jan，Feb，Mar,A

13、pr，May，Jun，Jul，Aug，Sept，Oct，Nov，Dec。散列函数为H(k)：ip，其中，i为关键字的第一个字母在英文字母表中的序号。请分别画出按以下两种情况构成的散列表： (1)散列地址空间为0，12，p=13，用线性再散列法处理冲突； (2)散列地址空间为0，6，p=7，用链地址法处理冲突。 910 在散列函数与散列地址范围都分别相同的前提下，采用链地址法处理冲突比采用开放地址法处理冲突的时间效率要高，为什么? 911 已知有长度为M的散列表HT0，M-1，散列函数为H(k)，并且采用线性探测再散列方法处理冲突。请写出在该散列表中查找关键字值为key的元素存在与否的算法。若存

14、在，则给出它在表中的位置，否则给出相应的信息。 912 请写出一个从散列文件中删除一个记录的算法。设所用的散列函数为H(k)，处理冲突的方法为线性再散列法。 913 请写出一个从散列文件中删除一个记录的算法。设所用的散列函数为H(k)，处理冲突的方法为链地址法。 914 已知一长度为n的线性表A和待散列地址空间为0，m1)，其中mn。若采用除留余数法构造散列函数与步长为根号下N下取整的线性探测再散列法处理冲突，请分别写出建立该散列表和在该散列表上进行查找的算法。 915 已知散列函数为H(k)=(3*k)11，采用线性探测再散列法处理冲突。对下列关键字值序列构造一个散列地址空间为0，10的散列

15、表，并求出ASL。 (22，41，53，8，46，30，1，3l，66)历年考试题11若用二分查找法取得的中间位置元素键值大于被查找值，说明被查找值位于中间值的前面，下次的查找区间为从原开始位置至（）A该中间位置B该中间位置1C该中间位置1D该中间位置212散列文件不能（）A随机存取B索引存取C按关键字存取D直接存取13若检索顺序文件各个记录的概率相同，设文件占用的页块数为n，则按关键字存取时的平均访问外存次数为（）An/2BnCn/4Dlog n10在最坏的情况下，查找成功时二叉排序树的平均查找长度（）A小于顺序表的平均查找长度B大于顺序表的平均查找长度C与顺序表的平均查找长度相同D无法与顺

16、序表的平均查找长度比较11闭散列表中由于散列到同一个地址而引起的“堆积”现象，是由（）A同义词之间发生冲突引起的B非同义词之间发生冲突引起的C同义词之间或非同义词之间发生冲突引起的D散列表“溢出”引起的12从外存设备的观点看，存取操作的基本单位是（）A逻辑记录B数据元素C文件D物理记录13对文件进行检索操作时，每次都要从第一个记录开始的文件是（）A顺序文件B索引文件C顺序索引文件D散列文件5、考虑具有如下性质的二叉树：除叶子结点外，每个结点的值都大于其左子树上的一切结点的值，并小于等于其右子树上的一切结点的值。 现把9个数1，2，3，8，9填入下图所示的二叉树的9个结点中，并使之具有上述性质。

17、此时，n1的值是A，n2的值是B，n9的值是C。现欲把101/2放入此树，并使该树保持前述性质，增加的一个结点可以放在D或E。 o n1 / o n2 o n3 / o n4 o n5 o n6 / o n7 o n8 o n9供选择的答案AC：1 2 3 4 5 6 7 8 9 D、E：n7下面 n8下面 n9下面 n6下面 n1与n2之间 n2与n4之间 n5与n9之间 n3与n6之间1、散列法存储的基本思想是根据_A_来决定_B_ , 碰撞 (冲突) 指的是_C_ , _D_越大, 发生碰撞的可能性也越大。 处理碰撞的两类主要方法是_E_。供选择的答案A 、B 、D ：存储地址 元素的序

18、号 元素个数 关键码值非码属性 平均检索长度 负载因子 散列表空间C ： 两个元素具有相同序号 两个元素的关键码值不同, 而非码属性相同 不同关键码值对应到相同的存储地址 负载因子过大 数据元素过多E ： 线性探查法和双散列函数法 建溢出区法和不建溢出区法 除余法和折叠法 拉链法和开地址法(试题1)如图所示的二叉树，有下列性质：除叶子结点外，每个结点的值都大于其左子树上的一切结点的值，并小于等于其右子树上一切结点的值。这是一棵_A_树。现有一菲波那契数列an,a0=a1=1,ak=ak-1+ak-2,k=2,3。若把a1,a2,a9填入该二叉树，一般可采用_B_遍历法遍历该树上全部结点，得到由

19、结点的值组成的从小到大顺序排列的序列。对本题给出的二叉树图形填入a1,a9后，其结点n8的值为_C_，根结点的值为_D_。若欲插入a1,a9的平均值，则应该在_E_增加一个结点。 o n1 / o n2 o n3 / o n4 o n5 o n6 / o n7 o n8 o n9供选择的答案：穿线树 最佳查找树 树 查找树：前序 中序 后序 广度： 21 57： 21 34 66：n2与n4之间 n6下 n与n9之间 n9下已知一个线性表(38，25，74，63，52，48)，采用的散列函数为H(Key)=Key mod 7，将元素散列到表长为7的哈希表中存储。若采用线性探测的开放定址法解决冲

20、突，则在该散列表上进行等概率成功查找的平均查找长度为 (11) ；若利用拉链法解决冲突，则在该散列表上进行等概率成功查找的平均查找长度为 (12) 。 (11) A、1.5 B、1.7 C、2.0 D、2.3 (12) A、1.0 B、7/6 C、4/3 D、3/2(试题5 )在二叉排序树中，每个结点的关键码值_A_，_B_一棵二叉排序树，即可得到排序序列。同一个结点集合，可用不同的二叉排序树表示，人们把平均检索长度最短的二叉排序树称作最佳二叉排序树，最佳二叉排序树在结构上的特点是_C_，_D_不是二叉排序树，_E_是最佳二叉排序树。 供选择的答案 A： 比左子树所有结点的关键码值大，比右子树

21、所有结点的关键码值小； 比左子树所有结点的关键码值小，比右子树所有结点的关键码值大； 比左右子树的所有结点的关键码值大 ； 与左子树所有结点的关键码值和右子树所有结点的关键码值无必然的大小关系。 B： 前序遍历 中序（对称）遍历 后序遍历 层次遍历C： 除最下两层可以不满外，其余都是充满的 ； 除最下一层可以不满外，其余都是充满的； 每个结点的左右子树的高度之差的绝对值不大于1 ； 最下层的叶子必须在左边 。D、E：如图所示。 / / / / / / / / / / / / / / / / / / / / / / / / 24在含20个关键字的3阶B树（23树）上查找一个关键字，至多需要访问_次外存。23动态查找表在开散列表上通常采用_来解决冲突问题。24对于有10个元素的有序表采用二分查找，需要比较3次方可找到其对应的键值，则该元素在有序表中的位置可能是_。25查找表的逻辑结构与线性结构、树型结构等相比，根本区别在于_。23查找表的数据结构有别于线性表、树型结构等，其逻辑结构为_。24长度为L的顺序表，采用设置岗哨方式顺序查找，若查找不成功，其查找长度为_。25在开散列表上查找某元素时，通常分两