数据结构练习3答案

1、数据结构练习（三）参考、选择题1. 顺序查找法适合于存储结构为的线性表A ）哈希存储B）顺序存储或链式存储C）压缩存储D）索引存储2. 一个长度为 100 的已排好序的表，用二分查找法进行查找，若查找不成功，至少比较 次。A）9B） 8C）7D)63.采用顺序查找方法查找长度为A ）nB）n/2n 的线性表时，平均比较次数为 C）（n+1）/2D）（n-1） /24. 对线性表进行折半查找时，要求线性表必须A ）以顺序方式存储B）以顺序方式存储，且结点按关键字有序排列C）以链表方式存储D）以链表方式存储，且结点按关键字有序排列5. 采用二分查找法查找长度为n 的线性表时，每个元素的平均查找长度

2、 为。A ）O（n2）B）O（ nlog2n）C）O（n）D） O（ log2n）6. 有一个长度为 12 的有序表 R0 11，按折半查找法对该表进行查找，在表 内各元素等概率查找情况下查找成功所需的平均比较次数为 。A ）35/12B）37/12C） 39/12D）43/127. 有一个有序表为 1 ，3，9，12，32，41，45，62，75，77，82，95，99， 当采用折半查找法查找关键字为 82 的元素时，次比较后查找成功。A）1B.2C） 4D）88. 当采用分块查找时，数据的组织方式为。A）数据分成若干块，每块内存数据有序B ）数据分成若干块， 每块内数据不必有序， 但块间必

3、须有序， 每块内最大 （或 最小）的数据组成索引块C）数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索 引块D）数据分成若干块，每块（出最后一块外）中的数据个数需相同9. 采用分块查找时，若线性表中共有 625 个元素，查找每个元素的概率相同， 假设采用顺序查找来确定结点所在的块时，每块应有 个结点最佳A )10B) 25C)6D)62510. 不 能生成右图所示二叉排序树的关键字序列是 。A) 45312 B)42531 C)45213 D)4231511. 按遍历二叉排序树，可以得到按值递增或递减次序的关键码序列A) 先序B)中序C)后序D)层序12. 在一棵平衡二叉树中，

4、每个结点的平衡因子的取值范围是A )-11B)-22C)12D)0 113. 具有 5 层结点的 AVL 树至少有个结点D)1728 的结点，则依次比较A )10B) 12C)1514. 在含有 15 个结点的平衡二叉树上，查找关键字为 的关键字可能是A)30，36C)48，18，38，28B) 38，48，28D)60，30，50，40，38，3615.一棵深度为 k 的平衡二叉树，其每个非叶子结点的平衡因子均为0，则该树共有 个结点k-1 k-1A )2k-1-1B)2k-1k-1C)2k-1 +1D)2k-116. 查找效率最高的二叉排序树是A所有结点的左子树都为空的二叉排序树 B所有节

5、点的右子树都为空的二叉排序树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 M

6、od 11.表中已有 4 个结点 H （15）=4，H（38）=5，H（61）=6，H（84）=7，其余地址为空，如用二次 探测再散列法处理冲突，则关键字为 49 的结点的地址是 。A）8B）3C）5D） 921. 假设有 k 个关键字互为同义词，若用线性探测再散列法把这 k 个关键字存 入哈希表中，至少要进行 次探查。A）k-1B）kC）k+1D） k（k+1）/222. 若采用链地执法构造哈希表， 哈希函数为 H（key）=key Mod 17，则需 （1） 个链表，这些链表的首指针构成一个指针数组，该数组的下标范围为（2）。（1）A）17（2）A）017B）13B）117C）16D）任意

7、D）116C）01623.直接插入排序在最好情况下的时间复杂度为。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. 以下排序方法中，在初始序

8、列已基本有序的情况下，排序效率最高。A ）归并排序 B）直接插入排序 C）快速排序 D）堆排序28. 不稳定的排序方法是。A ）冒泡排序B）直接插入排序 C）希尔排序 D ）归并排序29. 以下排序算法中，不能保证每趟排序至少能将一个元素放到其最终位置上。A ）快速排序B）希尔排序C）堆排序D）冒泡排序30. 在以下排序方法中 , 关键字比较的次数与记录的初始排列次序无关的A ）希尔排序B）冒泡排序C）插入排序 D）直接选择排序31. 在排序算法中，每次从未排序的记录中选取最小（或最大）关键字的记录， 加入到已排序记录的末尾，该排序方法是 。A ）希尔排序 B）冒泡排序C）插入排序D）直接选择

9、排序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，66B）100，98，85，82，80，77，66，60，40，20，10C）10，20，40，60，66，77，80，82，85，98，100D）100，85，40，77，80，60，66，98，82，10，2034. 堆排序是（ 1） 类排序，堆排序平均时间复杂度和需要附加的存储空间复杂度分别是（2） 。（1）.A）

10、插入B）交换（2）.A）O（n2）和 O（1）C） O（nlog2n）和 O（ n）C）归并D）选择B）O（nlog2n）和 O（1）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 棵

11、子树 C ）至少有 m/2 棵子树38. 对于哈希函数 H（key）=key%13，被称为同义词的关键字是 。A）35和41B）23和39C）15和 44D）25和5139. 堆的形状是一棵 。A）二叉排序树B）满二叉树 C）完全二叉树D）不是二叉树40. 以下 法在数据基本有序时效率最好。A ）快速排序B）冒泡排序C）堆排序D）希尔排序41. 快速排序在情况下最不利于发挥其长处。A ）要排序的数据量太大B）要排序的数据中含有多个相同值C）要排序的数据个数为奇数D）要排序的数据已基本有序42. 下列序列中， _ 是执行第一趟快速排序后得到的序列 （ 关键字为字符串 ） A. da,ax,eb,

12、cd,bbffha,gcB. cd,eb,ax,daffha,gc,bbC. gc,ax,eb,cd,bbffda,haD. ax,bb,cd,daffeb,gc,ha43. 一个记录的关键字为 46，79，56，38，40，84，采用快速排序以第一个 记录为基准得到的第一次划分结果为 。A） 38,40,46,56,38,79,84B）40,38,46,79,56,84C） 40,38,46,56,79,84D）40,38,46,56,7944. 对下列关键字序列用快速排序法进行排序时，速度最快的情形是 。A）21 ，25，5，17，9，23，30 B）25,23,30,17,21,5,9C

13、） 21,9,17,30,25,23,5D）5,9,17,21,23,25,3045. 下列排序方法中，在一趟结束后不一定能选出一个元素放在其最终位置上。A ）直接选择排序B）冒泡排序C）归并排序 D）堆排序46. 将两个各有 n 个元素的有序表归并成一个有序表，其最少的比较次数 是。A ）nB）2n-1C）2nD）n-1二、填空题：1. 在n 个记录的有序顺序表中进行折半查找 ,最大的比较次数是 log2n +1 。2. 设线性表 a 1，a2， a500 的元素的值从小到大排列，对一个给定的 K 的 值用二分法查找线性表，在查找不成功的情况下至多需要比较log2n +1次3. 在直接插入排

14、序、希尔排序、直接选择排序、快速排序、堆排序和归并排序 中，平均比较次数最少的排序方法是 快速排序 。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,2

15、3,1,8,98,36 。三、判断题1. 顺序查找法适用于存储结构为顺序或链式存储的线性表2. 顺序查找方法只能在顺序存储结构上进行3. 折半查找可以在有序的双向链表上进行4. 分块查找的效率与线性表被分成多少块有关5. 在二叉排序树中， 每个结点的关键字都比左孩子关键字大， 比右孩子关键字 小6. 每个结点的关键字都比左孩子关键字大，比右孩子关键字小，这样的二叉树 都是二叉排序树7. 在二叉排序树中，新插入的关键字总是处于最低层8. 在二叉排序树中，新结点总是作为叶子结点来插入的9. 二叉排序树的查找效率和二叉排序树的高度有关10. 在平衡二叉排序树中，每个结点的平衡因子值都是相等的11.

16、在平衡二叉排序树中，以每个分支结点为根的子树都是平衡的。12. 哈希存储法只能存储数据元素的值，不能存储数据元素之间的关系。13. 哈希冲突是指同一个关键字对应多个不同的哈希地址。14. 哈希查找过程中，关键字的比较次数和哈希表中关键字的个数直接相关。15. 在用线性探测法处理冲突的哈希表中，哈希函数值相同的关键字总是存在 一片连续的存储单元中。16. 若哈希表的装填因子 a1,则可避免冲突的发生。17. 哈希表的查找效率主要取决于哈希表造表时选取的哈希函数和处理冲突的 方法。四、简答题：1. 若对具有 n 个元素的有序的顺序表和无序的顺序表分别进行顺序查找， 试在 下述两种情况下分别讨论两者

17、在等概率时的平均查找长度；（1）查找不成功，即表中无关键字等于给定值 k 的记录（2）查找成功，即表中有关键字等于给定值 k 的记录2. 已知一个有序表为 12 ，18，20，25，29，32，40，62，83，90，95，98， 当折半查找值 29 和 90 的元素时，分别需要多少次比较才能查找成功？若采 用顺序查找时（从前往后找） ，分别需要多少次比较才能成功？ 4，4，5，103. 比较静态查找表的 3 种查找方法4. 请回答下列关于堆的问题（1）堆的存储表示是顺序的，还是链接的？（2）设有一个最小堆 （小根堆 ），即堆中任意结点的关键字均小于它的左孩子 和右孩子的关键字。其具有最大关键

18、字的元素可能在什么地方？ 叶子5. 指出堆和二叉排序树的区别。6. 二叉排序树的结构如图所示，其中各结点的关键 字依次为 3240，请你标出各结点的关键字。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 M

19、od 11 ，用二次探测再散列法处理冲突，为关键字 序列（ 6，8，10，17，20，23，53，41，54，57）构造哈希表，并计算查找成 功、不成功时的平均查找长度。10. 比较直接插入排序和希尔排序的不同点。11. 在实现插入排序过程中，可以用折半查找来确定第 i 个元素在前 i-1 个元素 中的可能插入位置，这样做能否改善插入排序的时间复杂度？为什么？12. 在堆排序、快速排序和归并排序中：（1）若只从存储空间考虑，则应首先选取哪种排序方法，其次选取哪种排序 方法，最后选取哪种排序方法？ 堆排序、快速排序、归并排序 （2）若只从排序结果的稳定性考虑，则应选取哪种排序方法？归并排序（3）

20、若只从平均情况下排序最快考虑，则应选取哪种排序方法？快速排序（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,35ASL=(1+1+1+2+1+4+6+1)/8=17/8ASL=（1+1+1+1+2+1

21、+2+3）/8=12/8=0.7515.请为 17 题数列构造一棵平衡的二叉排序树，并计算 ASLASL=（1+2*2+4*3+5*3）/10=32/10=3.216.有 n 个有序的数据构成一个数列，查找某个元素时最多要进行几次比较？当 n=12，在等概率情况下查找成功的平均查找长度是多少？log2n+1ASL=（1+2*2+4*3+5*4）/12=37/1217.对如下数据： 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，209201211312435 42 62 71 501112 20 312435 42 62 71 50111220243135 42 62 71 50111220