数据结构练习（三）参考
一、选择题
1.顺序查找法适合于存储结构为 的线性表 A）哈希存储 B）顺序存储或链式存储 C）压缩存储 D）索引存储
2.一个长度为100的已排好序的表，用二分查找法进行查找，若查找不成功，至少比较________次。 A）9
B）8
C）7
D）6
D）（n-1）/2
3.采用顺序查找方法查找长度为n的线性表时，平均比较次数为 。 A）n
B）n/2
C）（n+1）/2
4.对线性表进行折半查找时，要求线性表必须 。 A）以顺序方式存储 C）以链表方式存储 为 。 A）O（n2）
B）O（nlog2n）
C）O（n）
D）O（log2n）
6.有一个长度为12的有序表R[0…11]，按折半查找法对该表进行查找，在表内各元素等概率查找情况下查找成功所需的平均比较次数为 。 A）35/12
B）37/12
C）39/12
D）43/12
7.有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，99}，当采用折半查找法查找关键字为82的元素时， 次比较后查找成功。 A）1
B.2
C）4
D）8
8.当采用分块查找时，数据的组织方式为 。 A）数据分成若干块，每块内存数据有序
B）数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大(或最小)的数据组成索引块
C）数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块
D）数据分成若干块，每块（出最后一块外）中的数据个数需相同
9.采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，
1
B）以顺序方式存储，且结点按关键字有序排列 D）以链表方式存储，且结点按关键字有序排列
5.采用二分查找法查找长度为n的线性表时，每个元素的平均查找长度
假设采用顺序查找来确定结点所在的块时，每块应有 个结点最佳。 A）10
B）25
C）6
D）625
10. 不能生成右图所示二叉排序树的关键字序列是_____。 A）45312 B）42531 C）45213 D）42315
11.按____遍历二叉排序树，可以得到按值递增或递减次序的关键码序列。 A）先序
B）中序 B）-2—2 B）12
C）后序 C）1—2 C）15
D）层序 D）0—1 D）17
12.在一棵平衡二叉树中，每个结点的平衡因子的取值范围是 。 A）-1—1 A）10
13.具有5层结点的AVL树至少有 个结点
14.在含有15个结点的平衡二叉树上，查找关键字为28的结点，则依次比较的关键字可能是 。 A）30，36
B）38，48，28
D）60，30，50，40，38，36
C）48，18，38，28 共有 个结点。 A）2k-1-1 B）2k-1
C）2k-1 +1
D）2k-1
16.查找效率最高的二叉排序树是 。 A．所有结点的左子树都为空的二叉排序树 B．所有节点的右子树都为空的二叉排序树 C．平衡二叉树
D．没有左子树的二叉排序树
17.下面关于B-树和B+树的叙述中，不正确的结论是 。 A）B-树和B+树都能有效地支持顺序查找 B）B-树和B+树都能有效地支持随机查找 C）B-树和B+树都是平衡的多分支树 D）B-树和B+树都可用于文件索引结构
18.设有n个关键字，哈希查找法的平均查找长度是 。 A）O（1） A）一定会
2
15.一棵深度为k的平衡二叉树，其每个非叶子结点的平衡因子均为0，则该树
B）O（n） B）一定不会
C）O（log2n） C）仍可能会
D）O（n2） D）以上都不对
19.将10个元素散列到100000个单元的哈希表，则 产生冲突。
20.设哈希表长 m=14，哈希函数H（key）=key Mod 11.表中已有4个结点H（15）=4，H（38）=5，H（61）=6，H（84）=7，其余地址为空，如用二次探测再散列法处理冲突，则关键字为49的结点的地址是 。 A）8
B）3
C）5
D）9 21.假设有k个关键字互为同义词，若用线性探测再散列法把这k个关键字存入哈希表中，至少要进行 次探查。 A）k-1
B）k
C）k+1
D）k（k+1）/2
22.若采用链地执法构造哈希表，哈希函数为H（key）=key Mod 17，则需 （1） 个链表，这些链表的首指针构成一个指针数组，该数组的下标范围为 （2）。 （1）A）17
B）13
C）16
D）任意 D）1—16
D）O（n2）
（2）A）0—17 A）O（n）
B）1—17 C）0—16
23.直接插入排序在最好情况下的时间复杂度为 。
B）O（nlog2n）
C）O（log2n）
24.稳定的排序算法是 。
A）直接插入排序 B）直接选择排序 C）堆排序 后的结果。
A）直接选择排序 B）冒泡排序
C）直接插入排序
D）堆排序
26.对数据序列{15，9，7，8，20，-1，4}进行排序，进行一趟后数据的排序变为{9，15，7，8，20，-1，4}，则采用的是 算法。 A）直接选择排序 B）冒泡排序 A）归并排序 A）冒泡排序 位置上。
A）快速排序 B）希尔排序 C）堆排序 是 。
3
D）快速排序
25.数据序列{8，9，10，4，5，6，20，1，2}只能是 算法的两趟排序
C）直接插入排序 D）堆排序
D）堆排序
27.以下排序方法中， 在初始序列已基本有序的情况下，排序效率最高。
B）直接插入排序 C）快速排序
28.不稳定的排序方法是 。
B）直接插入排序 C）希尔排序 D）归并排序
29.以下排序算法中， 不能保证每趟排序至少能将一个元素放到其最终D）冒泡排序
30.在以下排序方法中,关键字比较的次数与记录的初始排列次序无关的
A）希尔排序 B）冒泡排序 C）插入排序 D）直接选择排序
31.在排序算法中，每次从未排序的记录中选取最小（或最大）关键字的记录，加入到已排序记录的末尾，该排序方法是 。 A）希尔排序
B）冒泡排序
C）插入排序
D）直接选择排序
32.采用直接选择排列，比较次数与移动次数分别是 。 A）O（n），O（log2n） C）O（n2），O（n）
B）O（log2n），O（n2） D）O（n log2n），O（n）
33.以下序列不是堆的是 。
A）{100，85，98，77，80，60，82，40，20，10，66} B）{100，98，85，82，80，77，66，60，40，20，10} C）{10，20，40，60，66，77，80，82，85，98，100} D）{100，85，40，77，80，60，66，98，82，10，20}
34.堆排序是 （1） 类排序，堆排序平均时间复杂度和需要附加的存储空间复杂度分别是 （2） 。 （1）.A）插入
B）交换
C）归并
D）选择
（2）.A）O（n2）和O（1）
B）O（nlog2n）和O（1）
C）O（nlog2n）和O（n） D）O（n2）和O（n） 35.对n个记录的文件进行堆排序，最坏情况下的执行时间是 。 A）O（log2n） B）（n） C）O（nlog2n） D）O（n2）
36.设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用 排序法。 A）冒泡排序
B）快速排序 C）堆排序 D）基数排序
37.在非空m阶B－树上，除根结点以外的所有其他非终端结点 。 A）至少有?m/2?棵子树 B）至多有?m/2?棵子树 C）至少有?m/2?棵子树 C）至少有?m/2?棵子树
38.对于哈希函数H(key)=key，被称为同义词的关键字是________。 A）35和41
B）23和39 B）满二叉树
C）15和44
D）25和51
39.堆的形状是一棵________。 A）二叉排序树
C）完全二叉树
D）不是二叉树
40.以下 法在数据基本有序时效率最好。
4
A）快速排序 B）冒泡排序
C）堆排序 D）希尔排序
41.快速排序在 情况下最不利于发挥其长处。 A）要排序的数据量太大 C）要排序的数据个数为奇数
B）要排序的数据中含有多个相同值 D）要排序的数据已基本有序
42.下列序列中，__是执行第一趟快速排序后得到的序列(关键字为字符串) A. [da,ax,eb,cd,bb]ff[ha,gc] B. [cd,eb,ax,da]ff[ha,gc,bb] C. [gc,ax,eb,cd,bb]ff[da,ha] D. [ax,bb,cd,da]ff[eb,gc,ha] 43.一个记录的关键字为{46，79，56，38，40，84}，采用快速排序以第一个记录为基准得到的第一次划分结果为________。 A）{38,40,46,56,38,79,84} C）{40,38,46,56,79,84}
B）{40,38,46,79,56,84} D）{40,38,46,56,79}
44.对下列关键字序列用快速排序法进行排序时，速度最快的情形是____。 A）{21，25，5，17，9，23，30} B）{25,23,30,17,21,5,9} C）{21,9,17,30,25,23,5} 位置上。
A）直接选择排序 是 。 A）n
二、填空题：
1.在n个记录的有序顺序表中进行折半查找,最大的比较次数是 ?log2n ?+1 。 2.设线性表{a1，，…，a500}的元素的值从小到大排列，对一个给定的K的，，a2，值用二分法查找线性表，在查找不成功的情况下至多需要比较 ? log2n ? +1 次
3.在直接插入排序、希尔排序、直接选择排序、快速排序、堆排序和归并排序中，平均比较次数最少的排序方法是 快速排序 。
4.一棵深度为h的B-树，任一个叶子结点所处的层数为 h ，当向B-树插入一个新关键字时，为检索插入位置需读取 h-1 个结点。
5
D）{5,9,17,21,23,25,30}
45.下列排序方法中， 在一趟结束后不一定能选出一个元素放在其最终B）冒泡排序
C）归并排序
D）堆排序
46.将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数
B）2n-1
C）2n
D）n-1