山东专升本计算机专业数据结构练习题 - 图文

济南铁道职业技术学院 专升本辅导教材 数据结构

(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，14 C．10，15，16，18，19 D．10，15，11，13，14 (14)在某序列中采用折半查找方法查找某个元素，依次被比较过的元素在该序列中的位置不可能是——。 A．10，5，7，8，9 B．10，5，2，1 C．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．索引项按关键字值有序，并且由系统提供

第 49 页 共 63 页

济南铁道职业技术学院 专升本辅导教材 数据结构

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．树型查找方法 7．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+树上通常有两个头指针(即查找的人口指针)，其中一个指向——，另一个指向——。

第 50 页 共 63 页