第八章查找习题9．1 判断题(在你认为正确的题后的括号中打√，否则打X)。
(1)用来惟一区分文件中不同记录的属性或属性组称为主关键字。
( )(2)查找成功与否的关键在于是否按主关键字查找。
( )(3)顺序文件必须用一片地址连续的存储空间来存放。
( )(4)只有在顺序存储结构上才能采用顺序查找方法。
( )(7)只要按值有序排列的线性表采用顺序存储结构就可以采用折半查找方法。
( )(8)建立稠密索引的优点是节省存储空间。
( )(9)分块查找的效率与文件中的记录被分成多少块有关。
( )(10)分块查找过程是首先查找索引表，然后再到相应的块中具体查找记录。
( )(11)B-树和B十树都是用来实现动态索引的。
( )(12)在B-树上可以进行顺序查找。
( 1(13)在B+树上可以进行顺序查找。
／ 1(14)采用散列方法存储线性表，不能存储数据元素之间的关系。
( )(15)在散列文件中进行查找不涉及关键字的比较。
( )(16)散列冲突是指同一个关键字对应了多个不同的散列地址。
( )(17)散列表的负载因子等于存人散列表中的关键字的个数。
( )(18)在散列表的查找过程中，关键字的比较次数与表中关键字的数目直接相关。
( )(19)在利用线性探测法处理冲突的散列表中，散列函数值相同的关键字总是存放在一片地址连续的存储单元中。
(20)在采用链地址法处理冲突的散列表中，散列函数值相同的关键字是链接在同一个链表中的。
( )9．2单项选择题。
(1)衡量查找算法性能好坏的主要标准是。
A．参加比较的关键字值的多少B．被查找的关键字值在关键字序列中的位置C.关键字序列中是否存在被查找关键字值D．关键字值的平均比较次数的多少(2)顺序查找方法的优点之一是—。
·A．对于被查找对象几乎没有限制B．适合排序连续顺序文件的查找C.适合链接顺序文件的查找D．查找时间效率高(3)对线性表采用折半查找，该线性表必须。
A．元素按值有序排列B．采用顺序结构C．元素按值有序排列，并且采用顺序存储结构n元素按值有序排列，并且采用链式存储结构(4)下面的说法中，不正确的是——。
A．折半查找方法不适用于按值有序链接的链表的查找B．折半查找方法适用于按值有序的顺序表的查找C.折半查找方法适用于按关键字值大小有序排列的顺序文件的查找D．折半查找方法适用于排序连续顺序文件的查找(5)在有序表(k1，k2，…，k9，)中采用折半查找方法查找99次，其中，至少有一个元素被比较了99次，该元素是——。
A．K99 B．k50 C．K49 D．k1(6)为了实现分块查找，线性表必须采用——结构。
A．顺序存储B．链式存储C．索引存储D．散列存储(7)只能在顺序存储结构上才能实现的查找方法是法。
A．顺序查找B．树型查找C．折半查找D．散列查找(8)在具有15个记录的排序连续顺序文件上采用折半查找方法查找一个文件中不存在的记录，需要进行——次关键字的比较。
A．0 B．4 C．5 D．15(9)若在100个记录中查找其中任意一个记录，最多只要比较5次，则所采用的查找方法可能是——。
A．折半查找B．树型查找C．分块查找D．散列查找(10)若在n个记录中查找其中任意一个记录至少要比较2次，则所采用的查找方法可能是A．分块查找B‘折半查找C．树型查找D．散列查找(11)折半查找过程可以利用一棵称之为判定树的二叉树来描述。
在长度为12的序列中进行折半查找对应的判定树的根结点的右孩子的值(某元素在序列中的位置)是——。
A．7 B．8 C．9 D．10(12)若在序列中采用折半查找方法进行查找，用来描述该查找过程的判定树的形状与——有关。
A．序列中元素的值B．序列中元素的排列次序C．序列中元素的类型D．序列中元素的个数(13)在某序列中采用折半查找方法查找某个元素，依次被比较过的元素在该序列中的位置只能是——。
A．10，15，12，18，19 B．10，15，12，13，14C．10，15，16，18，19 D．10，15，11，13，14(14)在某序列中采用折半查找方法查找某个元素，依次被比较过的元素在该序列中的位置不可能是——。
A．10，5，7，8，9 B．10，5，2，1C．10，5，6，7，8 D．10，5，7，6(15)将数据元素2，4，6，8，10，12，14，16，18，20依次存放于一个一维数组中，然后采用折半查找方法查找元素12，被比较过的数组元素的下标依次为——。
A．10，16，12 B．10，12，16 C．4，7，5 D．4，5，7(16)索引文件中的索引表具有的特点是————。
A．索引项按关键字值有序，并且由用户提供B．索引项按关键字值有序，并且由系统提供C．索引项按关键字值无序，并且由用户提供D．索引项按关键宇值无序，并且由系统提供(17)m阶B-树中的m是指——。
A．每个结点至少具有m棵子树B．每个结点最多具有m棵子树C．分支结点中包含的关键字的个数D．m阶B-树的深度(18)下面关于B-树和B+树的叙述中，不正确的是——。
A．B-树和B+树都是平衡的多分树B．B-树和B+树都可以用于文件的索引结构D．B—树和B+树都能有效地支持随机检索(19)下面的命题中，不成立的是。
A．m阶B-树中的每一个分支结点的子树的数量都小于或等于m。
B．m阶B-树中的每一个分支结点的子树的数量都大于或等于m／2上取整C．m阶B-树中的任何一个结点的子树的深度都相等。
D．m阶B—树中有k个子树的分支结点包含k—1个关键字。
(20)评价散列函数质量好坏的标准是——。
A．函数是否简单B．计算是否快C．是否是解析式D．函数的取值是否均匀(21)在一个初始状态为空的散列表中依次插入关键字序列(MON，TUE，WED，THU，FRI，SAT，SUN)，散列函数为H(key)：i％7，其中，i为关键字key的第一个字母在英文字母表中的序号，地址值域为[0：6]，采用线性再散列法处理冲突。
(22)在具有n个元素的序列中进行查找，平均查找长度为O(n)的方法是——。
A．顺序查找方法B．散列查找方法C．分块查找方法D．树型查找方法9．3 填空题。
(1)文件的逻辑结构是指——，文件的物理结构是指——。
(2)文件在物理结构中通常有——、——和——三种组织方式。
(3)文件的关键字是——。
(4)文件最基本操作是和。
(5)对线性表采用折半查找方法，该线性表必须采用——存储结构，并且——。
(6)在按值有序的线性表(5，8，11，12，15，20，32，41，57)中采用折半查找法查找20需要进行——次元素间的比较。
(7)具有n个结点的判定树的深度h = ——。
(8)若每个记录的查找概率相等，则在具有n个记录的顺序文件中采用顺序查找法的平均查找长度ASL=——。
(9)在具有n个记录的排序连续顺序文件中采用折半查找法的平均查找长度ASL=？(10)索引文件的索引表中的一个索引项是——之间的对照关系。
(11)索引文件包括——和——两个部分。
(12)索引表的特点是——，并且——。
(13)在索引文件中查找一个记录的过程是先查——，然后——。
(14)具有144项的表分成——块最好，若每块的最佳长度为8，则平均查找长度为——(15)在3阶B-树上，每个分支结点包含的子树的数目最多为——，最少为——。
(16)一棵B+树上通常有两个头指针(即查找的人口指针)，其中一个指向——，另一个指向——。
(17)散列函数建立了——之间的对应关系。
(18)设计一个散列表通常应包括三个内容，分别是——、——和——。
(19)一个好的散列函数是指——。
处理冲突的方法通常有——、——和——一O(20)一个待散列存储的线性表为K二(18，25，63，50，42，32，9)，散列函数为H(k)：k％9，则与元素18发生冲突的元素有——个。
9．4 试叙述索引顺序文件与顺序文件相比较的优缺点，指出一种适用于索引顺序文件的外存设备。
9．5 已知一个长度为12的线性表(Dec，Feb，Nov，Oct，Jul，Sept，Aug,Apr，May,Jun,Jan，Mar)。
(1)按该线性表中元素的顺序构造出一棵二叉排序树；(2)若每个元素的查找概率均等，查找此二叉排序树中任意一个结点的平均查找长度ASL是多少?(3)若对线性表的元素按字典顺序从小到大排列以后，再用折半查找方法，则查找其中任意一个元素的平均查找长度ASL是多少?(4)画出相应的平衡二叉树。
9．6 折半查找过程可以利用一棵判定树来描述。
请画出n‘13时的判定树。
9．7 何谓散列冲突?何谓冲突处理?简要说明冲突处理的过程。
9．8 已知散列函数为H(k)二k％7，并采用线性探测再散列方法处理冲突，所建立的散列表如下所示，请依次将关键字17，27填人表中。
9．9 在初始为空的散列表中依次插入以下关键字序列：Jan，Feb，Mar,Apr，May，Jun，Jul，Aug，Sept，Oct，Nov，Dec。
散列函数为H(k)：i％p，其中，i为关键字的第一个字母在英文字母表中的序号。
请分别画出按以下两种情况构成的散列表：(1)散列地址空间为[0，12]，p=13，用线性再散列法处理冲突；(2)散列地址空间为[0，6]，p=7，用链地址法处理冲突。
9．10 在散列函数与散列地址范围都分别相同的前提下，采用链地址法处理冲突比采用开放地址法处理冲突的时间效率要高，为什么?9．11 已知有长度为M的散列表HT[0，M-1]，散列函数为H(k)，并且采用线性探测再散列方法处理冲突。
请写出在该散列表中查找关键字值为key的元素存在与否的算法。
若存在，则给出它在表中的位置，否则给出相应的信息。
9．12 请写出一个从散列文件中删除一个记录的算法。
设所用的散列函数为H(k)，处理冲突的方法为线性再散列法。
9．13 请写出一个从散列文件中删除一个记录的算法。
设所用的散列函数为H(k)，处理冲突的方法为链地址法。
9．14 已知一长度为n的线性表A和待散列地址空间为[0，m—1)，其中m≥n。
若采用除留余数法构造散列函数与步长为根号下N下取整的线性探测再散列法处理冲突，请分别写出建立该散列表和在该散列表上进行查找的算法。
9．15 已知散列函数为H(k)=(3*k)％11，采用线性探测再散列法处理冲突。
对下列关键字值序列构造一个散列地址空间为[0，10]的散列表，并求出ASL。
(22，41，53，8，46，30，1，3l，66)历年考试题11．若用二分查找法取得的中间位置元素键值大于被查找值，说明被查找值位于中间值的前面，下次的查找区间为从原开始位置至（）A．该中间位置B．该中间位置－1C．该中间位置＋1 D．该中间位置／212．散列文件不能（）A．随机存取B．索引存取C．按关键字存取D．直接存取13．若检索顺序文件各个记录的概率相同，设文件占用的页块数为n，则按关键字存取时的平均访问外存次数为（）A．n/2 B．nC．n/4 D．log n10．在最坏的情况下，查找成功时二叉排序树的平均查找长度（）A．小于顺序表的平均查找长度B．大于顺序表的平均查找长度C．与顺序表的平均查找长度相同D．无法与顺序表的平均查找长度比较11．闭散列表中由于散列到同一个地址而引起的“堆积”现象，是由（）A．同义词之间发生冲突引起的B．非同义词之间发生冲突引起的C．同义词之间或非同义词之间发生冲突引起的D．散列表“溢出”引起的12．从外存设备的观点看，存取操作的基本单位是（）A．逻辑记录B．数据元素C．文件D．物理记录13．对文件进行检索操作时，每次都要从第一个记录开始的文件是（）A．顺序文件B．索引文件C．顺序索引文件D．散列文件5、考虑具有如下性质的二叉树：除叶子结点外，每个结点的值都大于其左子树上的一切结点的值，并小于等于其右子树上的一切结点的值。