数据结构练习（三）参考。
一、选择题。
1.顺序查找法适合于存储结构为的线性表。
a）哈希存储t': span', c': b', r': r_8'},顺序存储或链式存储。
c）压缩存储d）索引存储。
2.一个长度为100的已排好序的表，用二分查找法进行查找，若查找不成功，至少比较___次。
a）9b）8c）7t': span', c': d', r': r_12'},6
3.采用顺序查找方法查找长度为n的线性表时，平均比较次数为 。
a）nb）n/2t': span', c': c', r': r_8'},n+1）/2d）（n-1）/2
4.对线性表进行折半查找时，要求线性表必须 。
a）以顺序方式存储t': span', c': b', r': r_8'},以顺序方式存储，且结点按关键字有序排列。
c）以链表方式存储 d）以链表方式存储，且结点按关键字有序排列。
5.采用二分查找法查找长度为n的线性表时，每个元素的平均查找长度为 。
a）o（n2） b）o（nlog2n） c）o（nt': span', c': d', r': r_8'},o（log2n）
6.有一个长度为12的有序表r[0…11]，按折半查找法对该表进行查找，在表内各元素等概率查找情况下查找成功所需的平均比较次数为 。
a）35/12t': span', c': b', r': r_8'},37/12c）39/12d）43/12
7.有一个有序表为，当采用折半查找法查找关键字为82的元素时， 次比较后查找成功。
a）1b.2t': span', c': c', r': r_8'},4d）8
8.当采用分块查找时，数据的组织方式为 。
a）数据分成若干块，每块内存数据有序， ]数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大(或最小)的数据组成索引块。
c）数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块。
d）数据分成若干块，每块（出最后一块外）中的数据个数需相同。
9.采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应有个结点最佳。
a）10t': span', c': b', r': r_3'},25c）6d）625
10. 不能生成右图所示二叉排序树的关键字序列是___45312 b）42531 c）45213 d）42315
11.按___遍历二叉排序树，可以得到按值递增或递减次序的关键码序列。
a）先序t': span', c': b', r': r_9'},中序 c）后序d）层序。
12.在一棵平衡二叉树中，每个结点的平衡因子的取值范围是 。,1—1 b）-2—2 c）1—2d）0—1
13.具有5层结点的**l树至少有个结点。
a）10t': span', c': b', r': r_3'},12c）15d）17
14.在含有15个结点的平衡二叉树上，查找关键字为28的结点，则依次比较的关键字可能是 。
a）30，36b）38，48，28 , 48，18，38，28d）60，30，50，40，38，36
15.一棵深度为k的平衡二叉树，其每个非叶子结点的平衡因子均为0，则该树共有个结点。
a）2k-1-1 b）2k-1c）2k-1 +1t': span', c': d', r': r_3'},2k-1
16.查找效率最高的二叉排序树是 。
a．所有结点的左子树都为空的二叉排序树。
b．所有节点的右子树都为空的二叉排序树， ]平衡二叉树d．没有左子树的二叉排序树。
17.下面关于b-树和b+树的叙述中，不正确的结论是 。,b-树和b+树都能有效地支持顺序查找。
b）b-树和b+树都能有效地支持随机查找。
c）b-树和b+树都是平衡的多分支树。
d）b-树和b+树都可用于文件索引结构。
18.设有n个关键字，哈希查找法的平均查找长度是 。,o（1） b）o（nc）o（log2n） d）o（n2）
19.将10个元素散列到100000个单元的哈希表，则产生冲突。
a）一定会 b）一定不会t': span', c': c', r': r_3'},仍可能会 d）以上都不对。
20.设哈希表长 m=14，哈希函数h（key）=key mod 11.表中已有4个结点h（15）=4，h（38）=5，h（61）=6，h（84）=7，其余地址为空，如用二次探测再散列法处理冲突，则关键字为49的结点的地址是 。
a）8b）3c）5t': span', c': d', r': r_3'},9
21.假设有k个关键字互为同义词，若用线性探测再散列法把这k个关键字存入哈希表中，至少要进行次探查。
a）k-1b）kc）k+1t': span', c': d', r': r_3'},k（k+1）/2
22.若采用链地执法构造哈希表，哈希函数为h（key）=key mod 17，则需 （1） 个链表，这些链表的首指针构成一个指针数组，该数组的下标范围为 （2）。
1）[,17b）13c）16d）任意。
2）a）0—17b）1—17 [,0—16 d）1—16
23.直接插入排序在最好情况下的时间复杂度为 。,o（n） b）o（nlog2n） c）o（log2n） d）o（n2）
24.稳定的排序算法是 。,直接插入排序 b）直接选择排序 c）堆排序 d）快速排序。
25.数据序列只能是算法的两趟排序后的结果。
a）直接选择排序 b）冒泡排序 [,直接插入排序 d）堆排序。
26.对数据序列进行排序，进行一趟后数据的排序变为，则采用的是算法。
a）直接选择排序 b）冒泡排序t': span', c': c', r': r_3'},直接插入排序 d）堆排序。
27.以下排序方法中， 在初始序列已基本有序的情况下，排序效率最高。
a）归并排序t': span', c': b', r': r_3'},直接插入排序 c）快速排序 d）堆排序。
28.不稳定的排序方法是 。
a）冒泡排序 b）直接插入排序 [,希尔排序 d）归并排序。
29.以下排序算法中， 不能保证每趟排序至少能将一个元素放到其最终位置上。
a）快速排序t': span', c': b', r': r_3'},希尔排序 c）堆排序 d）冒泡排序。
30.在以下排序方法中，关键字比较的次数与记录的初始排列次序无关的是 。
a）希尔排序 b）冒泡排序 c）插入排序 [,直接选择排序。
31.在排序算法中，每次从未排序的记录中选取最小（或最大）关键字的记录，加入到已排序记录的末尾，该排序方法是 。
a）希尔排序 b）冒泡排序 c）插入排序t': span', c': d', r': r_3'},直接选择排序。
32.采用直接选择排列，比较次数与移动次数分别是 。
a）o（n），o（log2nb）o（log2n），o（n2）, o（n2），o（nd）o（n log2n），o（n）
33.以下序列不是堆的是 。a）b）
c）, 34.堆排序是 （1） 类排序，堆排序平均时间复杂度和需要附加的存储空间复杂度分别是 （2） 。
1）.a）插入b）交换c）归并t': span', c': d', r': r_3'},选择。
2）.a）o（n2）和o（1t': span', c': b', r': r_3'},o（nlog2n）和o（1）
c）o（nlog2n）和o（nd）o（n2）和o（n）
35.对n个记录的文件进行堆排序，最坏情况下的执行时间是 。
a）o（log2n） b）（nt': span', c': c', r': r_3'},o（nlog2n） d）o（n2）
36.设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用排序法。
a）冒泡排序 b）快速排序 [,堆排序 d）基数排序。
37.在非空m阶b－树上，除根结点以外的所有其他非终端结点 。
a）至少有[m/2\\end\ight\floor', altimg': w': 60', h':
28'}]棵子树b）至多有[m/2\\end\ight\floor', altimg': w': 60', h':
28'}]棵子树， ]至少有[m/2\\end\ight\ceil', altimg': w': 60', h':
28'}]棵子树c）至少有[m/2\\end\ight\ceil', altimg': w': 60', h':
28'}]棵子树。
38.对于哈希函数h(key)=key%13，被称为同义词的关键字是___
a）35和41b）23和39c）15和44t': span', c': d', r': r_17'},25和51
39.堆的形状是一棵___
a）二叉排序树 b）满二叉树 [,完全二叉树 d）不是二叉树。
40.以下法在数据基本有序时效率最好。
a）快速排序t': span', c': b', r': r_4'},冒泡排序 c）堆排序 d）希尔排序。
41.快速排序在情况下最不利于发挥其长处。
a）要排序的数据量太大b）要排序的数据中含有多个相同值。
c）要排序的数据个数为奇数t': span', c': d', r': r_4'},要排序的数据已基本有序。
42.下列序列中，__是执行第一趟快速排序后得到的序列(关键字为字符串)
][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.一个记录的关键字为，采用快速排序以第一个记录为基准得到的第一次划分结果为___
a） b）,
44.对下列关键字序列用快速排序法进行排序时，速度最快的情形是___
a） b）,
45.下列排序方法中， 在一趟结束后不一定能选出一个元素放在其最终位置上。
a）直接选择排序 b）冒泡排序t': span', c': c', r': r_4'},归并排序 d）堆排序。
46.将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是 。,nb）2n-1c）2nd）n-1
二、填空题：
1.在n个记录的有序顺序表中进行折半查找，最大的比较次数是 log2n +1 。
2.设线性表的元素的值从小到大排列，对一个给定的k的值用二分法查找线性表，在查找不成功的情况下至多需要比较 log2n +1 次。
数据结构练习3答案
数据结构练习 三 参考。一 选择题。1.顺序查找法适合于存储结构为的线性表。a 哈希存储t span c b r r 8 顺序存储或链式存储。c 压缩存储d 索引存储。2.一个长度为100的已排好序的表，用二分查找法进行查找，若查找不成功，至少比较 次。a 9b 8c 7t span c d r r...
数据结构练习答案
数据结构测验。一 填空题。1 数据结构一般包括逻辑结构 物理结构和数据操作三个方面的内容。2 无向图的三种常存储表示方法邻接矩阵 邻接表 邻接多重表 3 广义表 a b j，d 的表头是 a 表尾是 b j，d 4 由一棵二叉树的前序序列和中序序列可唯一确定这棵二叉树。5 栈顶的位置是随着入栈和出栈...
数据结构练习1 09答案
一 填空题 直接前驱。直接后继。元素个数。一个指针域。前驱。后继。指针域。next 指针域 头结点。相互间存在一种或多种特定关系。结构。集合线性结构树形结构图形结构。逻辑结构 09数据结构练习一参考。一 填空题 二 选择题。三 判断题。五 算法设计。1 设有一个顺序表l，其元素为整形数据，设计一个算...