《数据结构练习8》由会员分享，可在线阅读，更多相关《数据结构练习8（9页珍藏版）》请在金锄头文库上搜索。
1、第八章 查找习题9. 1判断题(在你认为正确的题后的括号中打V,否则打X)。(1) 用来惟一区分文件中不同记录的属性或属性组称为主关键字。( )(2) 查找成功与否的关键在于是否按主关键字查找。( )(3) 顺序文件必须用一片地址连续的存储空间来存放。( )(4) 只有在顺序存储结构上才能采用顺序查找方法。( )(7) 只要按值有序排列的线性表采用顺序存储结构就可以采用折半查找方法。( )(8) 建立稠密索引的优点是节省存储空间。( )(9) 分块查找的效率与文件中的记录被分成多少块有关。( )(10) 分块查找过程是首先查找索引表,然后再到相应的块中具体查找记录。( )(11) B-树和B十
2、树都是用来实现动态索引的。()(12) 在B-树上可以进行顺序查找。(1(13) 在B+树上可以进行顺序查找。/ 1(14) 采用散列方法存储线性表,不能存储数据元素之间的关系。( )(15) 在散列文件中进行查找不涉及关键字的比较。( )(16) 散列冲突是指同一个关键字对应了多个不同的散列地址。( )(17) 散列表的负载因子等于存人散列表中的关键字的个数。( )(18) 在散列表的查找过程中,关键字的比较次数与表中关键字的数目直接相关。( )(19) 在利用线性探测法处理冲突的散列表中,散列函数值相同的关键字总是存放在一片 地址连续的存储单元中。(20) 在采用链地址法处理冲突的散列表中
3、,散列函数值相同的关键字是链接在同一个链 表中的。 ( )9. 2 单项选择题。(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 次，该元素是。AK99Bk50CK49Dk1(6) 为了实现分块查找，线性表必须采用结构。A. 顺序存储B.链式存储C索引存储D散列存储(7) 只能在顺序存储结构上才能实现的查找方法是法。A. 顺序查找B.树型查找C.折半查找 D.散列查找(8) 在具有 15 个记录的排序连续顺
5、序文件上采用折半查找方法查找一个文件中不存在的记 录，需要进行次关键字的比较。A. 0 B. 4C. 5 D. 15(9) 若在 100个记录中查找其中任意一个记录，最多只要比较5 次，则所采用的查找方法 可能是。A.折半查找B.树型查找C.分块查找 D.散列查找(10) 若在 n 个记录中查找其中任意一个记录至少要比较2 次，则所采用的查找方法可能是A分块查找B 折半查找C树型查找 D散列查找(11) 折半查找过程可以利用一棵称之为判定树的二叉树来描述。在长度为12 的序列中进 行折半查找对应的判定树的根结点的右孩子的值(某元素在序列中的位置)是。A. 7 B. 8C. 9 D. 10(12
6、) 若在序列中采用折半查找方法进行查找，用来描述该查找过程的判定树的形状与 有关。A.序列中元素的值B.序列中元素的排列次序C.序列中元素的类型 D.序列中元素的个数(13) 在某序列中采用折半查找方法查找某个元素，依次被比较过的元素在该序列中的位置 只能是。A. 10，15，12，18，19B. 10，15，12，13，14C. 10，15，16，18，19D. 10，15，11，13，14(14) 在某序列中采用折半查找方法查找某个元素，依次被比较过的元素在该序列中的位置 不可能是。A. 10，5，7，8，9B. 10，5，2，1C. 10，5，6，7，8D. 10，5，7，6(15) 将
7、数据元素 2，4，6，8，10，12，14，16，18，20 依次存放于一个一维数组中，然 后采用折半查找方法查找元素 12，被比较过的数组元素的下标依次为。A. 10，16，12 B. 10，12，16C. 4，7，5D. 4，5，7(16) 索引文件中的索引表具有的特点是。A. 索引项按关键字值有序，并且由用户提供B. 索引项按关键字值有序，并且由系统提供C. 索引项按关键字值无序，并且由用户提供D. 索引项按关键宇值无序，并且由系统提供(17) m阶B-树中的m是指。A. 每个结点至少具有m棵子树B. 每个结点最多具有m棵子树C. 分支结点中包含的关键字的个数D. m阶B-树的深度(18
8、) 下面关于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个子树的分支结点包含k1个关键字。(20) 评价散列函数质量好坏的标准是。A.函数是否简单B.计算是否快C. 是否是解析式D.函数的取值是否均匀(21 )在一个初始状态为空的散列表中依次插
9、入关键字序列(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) 对线性表采用折半查找方法，该线性表必须采用一一存储结构，并且一一
10、。(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项的表分成块最好,若每
11、块的最佳长度为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 试叙述索引顺序文件与顺序文件相比较的优缺点,指出一种适用于索引顺序文件的外存设
12、备。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.
13、 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 在散列函数与散列地址范围都分别相同
14、的前提下,采用链地址法处理冲突比采用 开放地址法处理冲突的时间效率要高,为什么？9. 11已知有长度为M的散列表HT0, M-1,散列函数为H(k)，并且采用线性探测再 散列方法处理冲突。请写出在该散列表中查找关键字值为key的元素存在与否的算法。若存 在,则给出它在表中的位置,否则给出相应的信息。9. 12请写出一个从散列文件中删除一个记录的算法。设所用的散列函数为H(k)，处理 冲突的方法为线性再散列法。9. 13请写出一个从散列文件中删除一个记录的算法。设所用的散列函数为H(k)，处理 冲突的方法为链地址法。9. 14已知一长度为n的线性表A和待散列地址空间为0, m1)，其中m三n。若
15、采用 除留余数法构造散列函数与步长为根号下 N 下取整的线性探测再散列法处理冲突,请分别 写出建立该散列表和在该散列表上进行查找的算法。9. 15已知散列函数为H(k)=(3*k)%11,采用线性探测再散列法处理冲突。对下列关键字 值序列构造一个散列地址空间为0, 10的散列表,并求出 ASL。(22, 41, 53, 8, 46, 30, 1, 3l, 66)历年考试题11.若用二分查找法取得的中间位置元素键值大于被查找值,说明被查找值位于中间值的前 面,下次的查找区间为从原开始位置至( )B.该中间位置一1D.该中间位置/ 2B.索引存取D.直接存取A.该中间位置C.该中间位置+ 112 .散列文件不能()A.随机存取C.按关键字存取 13.若检索顺序文件各个记录的概率相同，设文件占用的
