计算机学科专业基础综合数据结构-711286.pdfVIP

计算机学科专业基础综合数据结构-7

一、单项选择题(总题数：28，分数：74.00)

1.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平

均查找长度ASL为______。

A.(n-1)/2

B.n/2

C.(n+1)/2√

D..n

此结论需要考生当作定理一样的牢记。

顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为______，二分法查找只适用于查找

顺序存储的有序表，平均比较次数为______。在此假定N为线性表中结点数，且每次查找都是成功的。（分

数：4.00）

A.N+1

B.2log2N

C.log2N

D.N/2√

E.Nlog2N

F..N2

A.N+1

B.2log2N

C.log2N√

D.N/2

E.Nlog2N

F..N2

2.下面关于二分查找的叙述正确的是______。

A.表必须有序，表可以顺序方式存储，也可以链表方式存储

B.表必须有序且表中数据必须是整型、实型或字符型

C.表必须有序，而且只能从小到大排列

D.表必须有序，且表只能以顺序方式存储√

二叉查找树的查找效率与二叉树的______有天，在______时查找效率最低。（分数：4.00）

A.高度

B.结点的多少

C.树形√

D.结点的位置

A.结点太多

B.完全二叉树

C.呈单枝树√

D.结点太复杂

3.当采用分块查找时，数据的组织方式为______。

A.数据分成若干块，每块内数据有序

B.数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大(或最小)的数据组成索引块√

C.数据分成若干块，每块内数据有序，每块内最大(或最小)的数据组成索引块

D.数据分成若干块，每块(除最后一块外)中数据个数需相同

本题主要考查分块查找的相关概念。

4.如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用下列哪一种查找方法?______

A.分块√

B.顺序

C.二分法

D.哈希

由于题目只说明是线性表，因此排除二分法。哈希算法虽然有最快的查找效率，但建立哈希表无法适应动

态变化的要求。在数据量大的查找中，顺序查找显然缺乏效率，因此应选择使用分块查找方法。

5.对于有n个数据元素的顺序存储的表，一个递增有序，另一个无序，查找一个元素时采用顺序算法，对

有序表从头开始查找，发现当前运算已小于待查找元素时停止查找，确定查找不成功。已知查找任何一个

元素的概率相同，则在两种表中成功查找______。

A.平均时间后者小

B.无法确定

C.平均时间前者小

D.平均时间相同√

顺序查找算法的性能与查找表是否有序无关，注意题目中所问是成功查找的效率。

6.下面关于B-树和B+树的叙述中，不正确的是______。

A.B-树和B+树都是平衡的多分树

B.B-树和B+树都可用于文件的索引结构

C.都能有效地支持随机检索

D.都能有效地支持顺序检索√

因为B+树所有的叶子结点中包含了全部关键字信息，以及指向含有这些关键字记录的指针，且叶子结点

本身依关键字的大小自小而大顺序链接，所以支持从根结点开始的随机检索和直接从叶子结点开始的顺序

检索，但是B-树不具有这种结构特性，所以只支持从根结点开始的随机检索，而不支持直接从叶子结点开

始的顺序检索。

7.关于B-树，下列说法不正确的是______。

A.B-树是一种查找树

B.所有的叶结点具有相同的高度

C.2-3树中，所有非叶子结点有1或者3个孩子结点√

D.通常情况下，B-树不是二叉树

B-树定义如下：

一棵m阶B-树，或者是空树，或者是满足以下性质的m叉树：

(1)根结点或者是叶子结果，或者至少有两棵子树，至多有m棵子树；

(2)除根结点外，所有非终端结点至少有1棵子树，至多有m棵子树；

(3)所有叶子结点都在树的同一层上；

(4)每个结点应包含如下信息：(n，A，K，A，A，A，…，K，A)其中：