数据结构练习(三)1252
19、立志宜思真品格，读书须尽苦功夫——阮元
数据结构练习（三）参考
一、选择题
1.顺序查找法适合于存储结构为 的线性表
A）哈希存储 B）顺序存储或链式存储
C）压缩存储 D）索引存储
2.一个长度为100的已排好序的表，用二分查找法进行查找，若查找不成功，至少比较________次
A）9 B）8 C）7 D）6
3.采用顺序查找方法查找长度为n的线性表时，平均比较次数为
A）n B）n/2 C）（n+1）/2 D）（n-1）/2
4.对线性表进行折半查找时，要求线性表必须
A）以顺序方式存储 B）以顺序方式存储，且结点按关键字有序排列
C）以链表方式存储 D）以链表方式存储，且结点按关键字有序排列
5.采用二分查找法查找长度为n的线性表时，每个元素的平均查找长度为
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个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应有 个结点最佳
A）10 B）25 C）6 D）625
10. 不能生成右图所示二叉排序树的关键字序列是_____
A）45312 B）42531 C）45213 D）42315
11.按____遍历二叉排序树，可以得到按值递增或递减次序的关键码序列
A）先序 B）中序 C）后序 D）层序
12.在一棵平衡二叉树中，每个结点的平衡因子的取值范围是
A）-1-1 B）-2-2 C）1-2 D）0-1
13.具有5层结点的AVL树至少有 个结点
A）10 B）12 C）15 D）17
14.在含有15个结点的平衡二叉树上，查找关键字为28的结点，则依次比较的关键字可能是
A）30.36 B）38.48.28
C）48，18，38，28 D）60，30，50，40，38，36
15.一棵深度为k的平衡二叉树，其每个非叶子结点的平衡因子均为0，则该树共有 个结点
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） B）O（n） C）O（log2n） D）O（n2）
19.将10个元素散列到100000个单元的哈希表，则 产生冲突
A）一定会 B）一定不会 C）仍可能会 D）以上都不对
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）任意
（2）A）0-17 B）1-17 C）0-16 D）1-16
23.直接插入排序在最好情况下的时间复杂度为
A）O（n） B）O（nlog2n） C）O（log2n） D）O（n2）
24.稳定的排序算法是
A）直接插入排序 B）直接选择排序 C）堆排序 D）快速排序
25.数据序列{8，9，10，4，5，6，20，1，2}只能是 算法的两趟排序后的结果
A）直接选择排序 B）冒泡排序 C）直接插入排序 D）堆排序
26.对数据序列{15，9，7，8，20，-1，4}进行排序，进行一趟后数据的排序变为{9，15，7，8，20，-1，4}，则采用的是 算法
A）直接选择排序 B）冒泡排序 C）直接插入排序 D）堆排序
27.以下排序方法中， 在初始序列已基本有序的情况下，排序效率最高
A）归并排序 B）直接插入排序 C）快速排序 D）堆排序
28.不稳定的排序方法是
A）冒泡排序 B）直接插入排序 C）希尔排序 D）归并排序
29.以下排序算法中， 不能保证每趟排序至少能将一个元素放到其最终位置上
A）快速排序 B）希尔排序 C）堆排序 D）冒泡排序
30.在以下排序方法中,关键字比较的次数与记录的初始排列次序无关的是
A）希尔排序 B）冒泡排序 C）插入排序 D）直接选择排序
31.在排序算法中，每次从未排序的记录中选取最小（或最大
）关键字的记录，加入到已排序记录的末尾，该排序方法是
A）希尔排序 B）冒泡排序 C）插入排序 D）直接选择排序
32.采用直接选择排列，比较次数与移动次数分别是
A）O（n），O（log2n） B）O（log2n），O（n2）
C）O（n2），O（n） 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）至少有棵子树 B）至多有棵子树
C）至少有棵子树 C）至少有棵子树
38.对于哈希函数H(key)=key%13，被称为同义词的关键字是________
A）35和41 B）23和39 C）15和44 D）25和51
39.堆的形状是一棵________
A）二叉排序树 B）满二叉树 C）完全二叉树 D）不是二叉树
40.以下 法在数据基本有序时效率最好
A）快速排序 B）冒泡排序 C）堆排序 D）希尔排序
41.快速排序在 情况下最不利于发挥其长处
A）要排序的数据量太大 B）要排序的数据中含有多个相同值
C）要排序的数据个数为奇数 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} B）{40,38,46,79,56,84}
C）{40,38,46,56,79,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} D）{5,9,17,21,23,25,30}
45.下列排序方法中， 在一趟结束后不一定能选出一个元素放在其最终位置上
A）直接选择排序 B）冒泡排序 C）归并排
序 D）堆排序
46.将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是
A）n B）2n-1 C）2n D）n-1
二、填空题：
1.在n个记录的有序顺序表中进行折半查找,最大的比较次数是 ?log2n ?+1
2.设线性表{a1，，，a2，，...，a500}的元素的值从小到大排列，对一个给定的K的值用二分法查找线性表，在查找不成功的情况下至多需要比较 ? log2n ? +1 次
3.在直接插入排序、希尔排序、直接选择排序、快速排序、堆排序和归并排序中，平均比较次数最少的排序方法是 快速排序
4.一棵深度为h的B-树，任一个叶子结点所处的层数为 h ，当向B-树插入一个新关键字时，为检索插入位置需读取 h-1 个结点
5.评价哈希表好坏的标准是 哈希表的均匀性
6.在各种查找方法中，其平均查找长度与结点个数n无关的查找方法是 哈希表查找
7.设用希尔排序对数序{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的不长（也称增量序列）依次是4、2、1，则排序需 3 趟，写出第一趟结束后，数序中数据的排列次序是 10,7,-9,0,47,23,1,8,98,36
三、判断题
1.顺序查找法适用于存储结构为顺序或链式存储的线性表
2.顺序查找方法只能在顺序存储结构上进行
3.折半查找可以在有序的双向链表上进行
4.分块查找的效率与线性表被分成多少块有关
5.在二叉排序树中，每个结点的关键字都比左孩子关键字大，比右孩子关键字小
6.每个结点的关键字都比左孩子关键字大，比右孩子关键字小，这样的二叉树都是二叉排序树
7.在二叉排序树中，新插入的关键字总是处于最低层
8.在二叉排序树中，新结点总是作为叶子结点来插入的
9.二叉排序树的查找效率和二叉排序树的高度有关
10.在平衡二叉排序树中，每个结点的平衡因子值都是相等的
11.在平衡二叉排序树中，以每个分支结点为根的子树都是平衡的
12.哈希存储法只能存储数据元素的值，不能存储数据元素之间的关系
13.哈希冲突是指同一个关键字对应多个不同的哈希地址
14.哈希查找过程中，关键字的比较次数和哈希表中关键字的个数直接相关
15.在用线性探测法处理冲突的哈希表中，哈希函数值相同的关键字总是存在一片连续的存储单元中
16.若哈希表的装填因子a<<1,则可避免冲突的发生
17.哈希表的查找效率主要取决于哈希表造表时选取的哈希函数和处理冲突的方法
四、简答题：
1.若对具有n个元素的有序的顺序表和无序的顺序表分别进行顺序查找，试在下述两种情况下分别讨论两者在等概率时的平均查找长度；
（1）查找不成功，即表中无关键字等于给定
值k的记录
（2）查找成功，即表中有关键字等于给定值k的记录
2.已知一个有序表为{12，18，20，25，29，32，40，62，83，90，95，98}，当折半查找值 29和90的元素时，分别需要多少次比较才能查找成功？若采用顺序查找时（从前往后找），分别需要多少次比较才能成功？ 4，4，5，10
3.比较静态查找表的3种查找方法
4.请回答下列关于堆的问题
（1）堆的存储表示是顺序的，还是链接的？
（2）设有一个最小堆(小根堆)，即堆中任意结点的关键字均小于它的左孩子和右孩子的关键字
其具有最大关键字的元素可能在什么地方？ 叶子
5.指出堆和二叉排序树的区别
6.二叉排序树的结构如图所示，其中各结点的关键字依次为32-40，请你标出各结点的关键字
7.关键字序列为：{1，2，6，7，11，4，8，13，10，5，17，9，16，20，3，12，14，16，18，19，15}，创建一棵5阶B-树，对于该B-树，给出删除8，16，15，4等4个关键字的过程
8.已知一组关键字为{21，33，12，40，68，59，25，51}，试依次插入关键字生成一棵3阶B-树；如果此后删除40，画出每一步执行后B-树的状态
9.已知哈希函数H(k)=2*k Mod 11，用二次探测再散列法处理冲突，为关键字序列（6，8，10，17，20，23，53，41，54，57）构造哈希表，并计算查找成功、不成功时的平均查找长度
10.比较直接插入排序和希尔排序的不同点
11.在实现插入排序过程中，可以用折半查找来确定第i个元素在前i-1个元素中的可能插入位置，这样做能否改善插入排序的时间复杂度？为什么？
12.在堆排序、快速排序和归并排序中：
（1）若只从存储空间考虑，则应首先选取哪种排序方法，其次选取哪种排序方法，最后选取哪种排序方法？堆排序、快速排序、归并排序
（2）若只从排序结果的稳定性考虑，则应选取哪种排序方法？归并排序
（3）若只从平均情况下排序最快考虑，则应选取哪种排序方法？快速排序
（4）若只从最坏情况下排序最快并且要节省内存考虑，则应选取哪种排序方法？堆排序
13.判别以下序列是否是大顶堆，如果不是，则把它调整为大顶堆
86，48，73，35，39，42，57，66，21，100
不是
14.已知哈希表地址空间为0到7，哈希函数为H(k)=k %8，采用线性探测再散列法和链地址法处理冲突，将以下各数依次存入该哈希表中，请分别构造哈希表，并分别计算平均查找长度
240,29,345,189,100,20,21,35
ASL=（1+1+1+2+1+4+6+1）/8=17/8
ASL=（1+1+1+1+2+1+2+3）/8=12/8=0.75
15.请为17题数列构造一棵平衡的二叉排序树，并计算ASL
ASL=(1+2*2+4*3+5*3)/10=32/10=3.2
16.有n个有序的数据构成一个数列，查找某个元素时最多要进行几次
比较？当n=12，在等概率情况下查找成功的平均查找长度是多少？
[log2n]+1
ASL=(1+2*2+4*3+5*4)/12=37/12
17.对如下数据：43，12，50，31，71，35，24，62，11，20
（1）写出采用快速排序算法的每一趟排序的结果
（2）写出执行直接插入排序算法，每趟排序的结果
（3）写出执行希尔排序算法，每趟排序的结果（增量序列为5、3、1）
（4）写出执行选择排序算法，每趟排序的结果
(1) 43，12，50，31，71，35，24，62，11，20
{20 12 11 31 24 35} 42 {62 71 50}
{11 12} 20 {31 24 35} 42 {62 71 50}
11 12 20 24 31 35 42 {62 71 50}
11 12 20 24 31 35 42 50 62 71
（2） 43
12 43
12 43 50
12 31 43 50
12 31 43 50 71
12 31 35 43 50 71
12 24 31 35 43 50 71
12 24 31 35 43 50 62 71
11 12 24 31 35 43 50 62 71
11 12 20 24 31 35 43 50 62 71
（3）43，12，50，31，71，35，24，62，11，20
35 12 50 11 20 43 24 62 31 71
11 12 31 24 20 43 35 62 50 71
11 12 20 24 31 35 43 50 62 71
（4）43，12，50，31，71，35，24，62，11，20
11 12 50 31 71 35 24 62 43 20
11 12 50 31 71 35 24 62 43 20
11 12 20 31 71 35 24 62 43 50
11 12 20 24 71 35 31 62 43 50
11 12 20 24 31 35 71 62 43 50
11 12 20 24 31 35 71 62 43 50
11 12 20 24 31 35 43 62 71 50
11 12 20 24 31 35 43 50 71 62
11 12 20 24 31 35 43 50 62 71
五、算法设计题：
1.若线性表中各节点的查找概率不等，则可用如下策略提高顺序查找的效率，若找到指定的结点，将该结点与其前驱（若存在）结点交换，使得经常被查找的结点尽量位于表的前端
设计出满足上述策略的顺序查找算法（注意必须从表头开始向后扫描）
2.设计一个算法，递增有序输出一棵二叉排序树的所有结点的关键字
3.设计一个算法，从大到小输出二叉排序树中所有其他值不小于k的关键字
4.设计一个算法，求出给定二叉排序树中最小和最大的关键字
5.给定一组关键字，创建一个带头结点的单链表，设计一个直接插入排序算法对这个单链表进行递增序列
??
??
??
??
1
19、立志宜思真品格，读书须尽苦功夫——阮元