数据结构练习3答案

数据结构练习（三）参考、选择题1顺序查找法适合于存储结构为的线性表A）哈希存储|B）顺序存储或链式存储C）压缩存储D）索引存储2. 一个长度为100的已排好序的表，用二分查找法进行查找，若查找不成功， 至少比较次。A）9B）8C）7D）63采用顺序查找方法查找长度为n的线性表时，平均比较次数为。A）nB）n/2回（n+1） /2D）（n-1） /24. 对线性表进行折半查找时，要求线性表必须。A）以顺序方式存储 B）以顺序方式存储，且结点按关键字有序排列 C）以链表方式存储 D）以链表方式存储，且结点按关键字有序排列5. 采用二分查找法查找长度为 n的线性表时，每个元素的平均查找长度为。A） O （n2）B） O （nlog2n）C） O （n）D）|O （log2n）6有一个长度为12的有序表R0ll,按折半查找法对该表进行查找，在表 内各元素等概率查找情况下查找成功所需的平均比较次数为。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）D） 88当采用分块查找时，数据的组织方式为。A）数据分成若干块，每块内存数据有序数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或 最小）的数据组成索引块C）数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索 引块D）数据分成若干块，每块（出最后一块外）中的数据个数需相同9. 采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应有个结点最佳。A) 10B)25C) 6D) 62510. 不能生成右图所示二叉排序树的关键字序列是。叵45312 B)42531 C)45213 D)4231511. 按遍历二叉排序树，可以得到按值递增或递减次序的关键码序列。A)先序 B)中序 C)后序D)层序12在一棵平衡二叉树中，每个结点的平衡因子的取值范围是。A)-11B)-22C)12D)0113. 具有5层结点的AVL树至少有个结点A)10B)12C)15D)1714. 在含有15个结点的平衡二叉树上，查找关键字为28的结点，则依次比较的关键字可能是。A) 30， 36B) 38， 48， 28C)48，18，38，28D)60，30，50，40，38，3615. 一棵深度为k的平衡二叉树，其每个非叶子结点的平衡因子均为0，则该树共有个结点。A)2k-1-1B)2k-1C)2k-1+1D)2k-116查找效率最高的二叉排序树是。A. 所有结点的左子树都为空的二叉排序树B. 所有节点的右子树都为空的二叉排序树匸平衡二叉树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） 8B）3C）5D）21. 假设有k个关键字互为同义词，若用线性探测再散列法把这k个关键字存入哈希表中，至少要进行次探查。A） k-1B）kC） k+1D）k （k+1） /222. 若采用链地执法构造哈希表，哈希函数为H（key） =key Mod 17,则需（1） 个链表，这些链表的首指针构成一个指针数组，该数组的下标范围为丄）(1) A) 17B) 13C) 16D）任意(2) A) 017B) 117C) 016D) 11623直接插入排序在最好情况下的时间复杂度为。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）归并排序直接插入排序 C）快速排序D）堆排序28.不稳定的排序方法是。A）冒泡排序B）直接插入排序 C）希尔排序 D）归并排序29以下排序算法中，不能保证每趟排序至少能将一个元素放到其最终位置上。A）快速排序希尔排序C）堆排序D）冒泡排序30. 在以下排序方法中，关键字比较的次数与记录的初始排列次序无关的 是。A）希尔排序B）冒泡排序 C）插入排序 D）直接选择排序31. 在排序算法中，每次从未排序的记录中选取最小（或最大）关键字的记录, 加入到已排序记录的末尾，该排序方法是。A）希尔排序 B）冒泡排序 C）插入排序直接选择排序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）插入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）至少有Lm/2棵子树B）至多有Lm/2棵子树C）至少有m/2棵子树C）至少有m/2棵子树38. 对于哈希函数H（key）二key%13，被称为同义词的关键字是。A） 35 和 41B） 23 和 39C） 15 和 44回25 和 5139. 堆的形状是一棵。A） 二叉排序树B）满二叉树巨完全二叉树D）不是二叉树40. 以下法在数据基本有序时效率最好。C）堆排序 D）希尔排序A）快速排序回冒泡排序41. 快速排序在情况下最不利于发挥其长处。A）要排序的数据量太大B）要排序的数据中含有多个相同值C）要排序的数据个数为奇数D）要排序的数据已基本有序42. 下列序列中，是执行第一趟快速排序后得到的序列（关键字为字符串）A. da,ax,eb,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,84巨40,38,46,56,79,84D） 40,3& 46,56,7944. 对下列关键字序列用快速排序法进行排序时，速度最快的情形是_。A）21，25，5，17，9，23，30B）25,23,30,17,21,5,9巨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. 设线性表a1，a2，a500的元素的值从小到大排列，对一个给定的K的 值用二分法查找线性表，在查找不成功的情况下至多需要比较_L 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,9&36 。三、判断题0顺序查找法适用于存储结构为顺序或链式存储的线性表2顺序查找方法只能在顺序存储结构上进行3折半查找可以在有序的双向链表上进行4. 分块查找的效率与线性表被分成多少块有关5在二叉排序树中，每个结点的关键字都比左孩子关键字大，比右孩子关键字 小6. 每个结点的关键字都比左孩子关键字大，比右孩子关键字小，这样的二叉树 都是二叉排序树7在二叉排序树中，新插入的关键字总是处于最低层凰在二叉排序树中，新结点总是作为叶子结点来插入的9. 二叉排序树的查找效率和二叉排序树的高度有关10在平衡二叉排序树中，每个结点的平衡因子值都是相等的回在平衡二叉排序树中，以每个分支结点为根的子树都是平衡的。 回哈希存储法只能存储数据元素的值，不能存储数据元素之间的关系。13. 哈希冲突是指同一个关键字对应多个不同的哈希地址。14. 哈希查找过程中，关键字的比较次数和哈希表中关键字的个数直接相关。15. 在用线性探测法处理冲突的哈希表中，哈希函数值相同的关键字总是存在 一片连续的存储单元中。16若哈希表的装填因子aKT讦ASL= (1+1+1+1+2+1+2+3) /8=12/8=0.7515.请为17题数列构造一棵平衡的二叉排序树，并计算ASL。ASL=(1+2*2+4*3+5*3)/10=32/10=3.2716有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， 20201211312435 42 62 71 50111220 312435 42 62 7150111220243135 42 6271 50111220243135 42 5062 712) 4312 4312 43 50123143501231435071123135435071122431354350711224313543506271111224313543506271111220243135435062 713)43，12，50，31，71，35，24，62，11，203512501120432462317111123124204335625071111220243135435062714)43，12，50，31，71，35，24，62，11，20111250317135246243201112503171352462432011122031713524624350111220247135316243501112202431357162435011122024313571624350111220243135436271501112202431354350716211122024313543506271五、算法设计题：1.若线性表中各节点的查找概率不等，则可用如下策略提高顺序查找的效率， 若找到指定的结点，将该结点与其前驱（若存在）结点交换，使得经常被查找 的结点尽量位于表的前端。设计出满足上述策略的顺序查找算法（注意必须从 表头开始向后扫描）2. 设计一个算法，递增有序输出一棵二叉排序树的所有结点的关键字。3设计一个算法，从大到小输出二叉排序树中所有其他值不小于k的关键字。4. 设计一个算法，求出给定二叉排序树中最小和最大的关键字。5. 给定一组关键字，创建一个带头结点的单链表，设计一个直接插入排序算法 对这个单链表进行递增序列。