2022年数据结构考前复习推荐 .pdf

1 第九章查找一、 选择题1. 若查找每个记录的概率均等， 则在具有 n 个记录的顺序表中采用顺序查找法查找一个记录，其平均查找长度ASL为( C )。A (n-1)/2 B. n/2 C. (n+1)/2 D. n ASL=Pi+ 2Pi+3Pi+ +nPi=n（n+1）/2n 4. 下面关于二分查找的叙述正确的是 ( D ) A. 表必须有序，表可以顺序方式存储，也可以链表方式存储 C. 表必须有序，而且只能从小到大排列B. 表必须有序且表中数据必须是整型，实型或字符型 D. 表必须有序，且表只能以顺序方式存储还必须按关键字的大小有序排列7. 用二分（对半）查找表的元素的速度比用顺序法( D ) A必然快 B. 必然慢 C. 相等 D. 不能确定8当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度 ( C ) A必定快 B.不一定 C. 在大部分情况下要快 D. 取决于表递增还是递减9. 具有 12个关键字的有序表，折半查找的平均查找长度（ A ） A. 3.1 B. 4 C. 2.5 D. 5 ASL=（1+2+2+3+3+3+3+4+4+4+4+4+4+5）/12=3.1 11当采用分块查找时，数据的组织方式为 ( B ) A数据分成若干块，每块内数据有序B数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块D. 数据分成若干块，每块（除最后一块外）中数据个数需相同12. 既希望较快的查找又便于线性表动+态变化的查找方法是 ( A ) A顺序查找 B. 折半查找 C. 索引顺序查找 D. 哈希法查找18分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( C ) A （100，80， 90 ， 60 ， 120 ，110，130） B. （100，120，110，130，80， 60 ，90）C.（100，60， 80 ， 90 ， 120 ，110，130） D. (100，80， 60 ， 90 ， 120，130，110) 30. 关于杂凑查找说法不正确的有几个( B ) （1）采用链地址法解决冲突时，查找一个元素的时间是相同的（2）采用链地址法解决冲突时，若插入规定总是在链首，则插入任一个元素的时间是相同的（3）用链地址法解决冲突易引起聚集现象（4）再哈希法不易产生聚集A. 1 B. 2 C. 3 D. 4 35. 散列表的地址区间为0-17, 散列函数为 H(K)=K mod 17。采用线性探测法处理冲突，名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 8 页 - - - - - - - - - 2 并将关键字序列26，25，72，38，8，18，59依次存储到散列表中。（1）元素 59 存放在散列表中的地址是（ D ） 。A 8 B. 9 C. 10 D. 11 （2）存放元素 59需要搜索的次数是（ C ） 。A 2 B. 3 C. 4 D. 5 有 0-17 共 18 个格子 ,mod 是取余操作 ,26mod17=9,则 26 放 9 号,25mod17=8,25 放 8号,72mod17=4,72放 4 号,38mod17=4, 由于 4 号被 27 占用,所以（4+1）mod17=5，38 放在5 号,8mod17=8,由于 8 号被 25 占用, （8+1） mod17=9,9号又给 26占用, （9+1） mod17=10，8 最终放在 10 号,18mod17=1,18放 1 号,59mod17=8,应该是放 8 号,由于 25 已经占用 8 号,因此尝试放 9 号,9 号被 26 占用,尝试放 10 号,10 号被 8 占用,因此最终放在 11号二、 判断题13. 顺序查找法适用于存储结构为顺序或链接存储的线性表。14. 折半查找法的查找速度一定比顺序查找法快。15. 就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。顺序查找成功的平均查找长度为（n+1）/2 折半查找的平均查找长度为(n+1）/n)*log2(n+1)- 1log2(n+1)- 1索引顺序查找平均查找长度为(n/s)+s)/2)+1 备注：s 为表分块后每一块的记录个数二叉树查找类似于折半查找，哈希（hash ）查找的平均查找长度与查找表中元素个数 n 无关的16对无序表用二分法查找比顺序查找快。20在查找树（二叉树排序树）中插入一个新结点，总是插入到叶结点下面。22对一棵二叉排序树按前序方法遍历得出的结点序列是从小到大的序列。三、填空题1. 顺序查找 n 个元素的顺序表，若查找成功，则比较关键字的次数最多为_n _ 次；当使用监视哨时，若查找失败，则比较关键字的次数为_n+1 _ 。2. 在顺序表（ 8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找关键码值20，需做的关键码比较次数为_ 4. 3在有序表 A1.12中，采用二分查找算法查等于A12 的元素，所比较的元素下标依次为_ 6,9,11,12_。7. 给定一组数据 6 ，2，7，10，3，12以它构造一棵哈夫曼树，则树高为_5_，带权路径长度 WPL 的值为 _96_。9. 己知有序表为 (12,18,24,35,47,50,62,83,90,115，134)当用二分法查找90 时，需_2_次查找成功， 47 时_4_成功，查 100 时，需_3_次才能确定不成功。10. 哈希表是通过将查找码按选定的_哈希函数 _和 _ 解决冲突的方法 _，把结点按查找码转换为地址进行存储的线性表。 哈希方法的关键是 _ 选择好的哈希函数_和 _ 处理冲突的方法_。一个好的哈希函数其转换地址应尽可能_ 均匀 _，而且函数运算应尽可能_ 简单_。四、应用题1. 名词解释：哈希表名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 8 页 - - - - - - - - - 3 2. 回答问题并填空（1） （2 分）散列表存储的基本思想是什么？散列表存储的基本思想是用关键字的值决定数据元素的存储地址（2） （4 分）散列表存储中解决碰撞的基本方法有哪些？ 开放定址法 再散列法 链地址法 建立公共溢出区2. 如何衡量 hash 函数的优劣 . 要叙述 hash表技术中的冲突概念，并指出三种解决冲突的方法。评价哈希函数优劣的因素有：能否将关键字均匀影射到哈希空间上，有无好的解决冲突的方法计算哈希函数是否简单高效。由于哈希函数是压缩映像，冲突难以避免。5在采用线性探测法处理冲突的散列表中，所有同义词在表中是否一定相邻？不一定相邻。哈希地址为i（0i m-1）的关键字，和为解决冲突形成的探测序列i 的同义词，都争夺哈希地址i。49. 依次输入表 (30,15,28,20,24,10,12,68,35,50,46,55)中的元素，生成一棵二叉排序树(1) 试画出生成之后的二叉排序树; (2) 对该二叉排序树作中序遍历，试写出遍历序列; (3) 假定每个元素的查找概率相等，试计算该二叉排序树的平均查找长度。50. 已知关键字序列R=11,4,3,2,17,30,19，请按算法步骤：（1）构造一棵哈夫曼树，并计算出它的带权路径长度WPL （7 分）（2）构造一棵二叉排序树，如果对每个关键字的查找概率相同，求查找成功时的平均查找长度 ASL 。 （8 分）第 9 章排序一、选择题1某内排序方法的稳定性是指( D )。A该排序算法不允许有相同的关键字记录 B该排序算法允许有相同的关键字记录C 平均时间为 0（n log n ）的排序方法 D以上都不对7如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。 （C，E ）就是不稳定的排序方法。A起泡排序 B归并排序 C Shell 排序 D 直接插入排序 E 简单选择排序11下列内部排序算法中：A快速排序 B.直接插入排序 C. 二路归并排序 D. 简单选择排序 E. 起泡排序 F. 堆排序（1）其比较次数与序列初态无关的算法是（ D，C ）（2）不稳定的排序算法是（ A，D ，F ）（3）在初始序列已基本有序（除去n 个元素中的某k 个元素后即呈有序， kn）的情况下，排序效率最高的算法是（B ）（4）排序的平均时间复杂度为O(n?logn) 的算法是（ A，C，F ）为 O(n?n)的算法是（ B，D ，E ）12排序趟数与序列的原始状态有关的排序方法是( C ，D ) 排序法。 A 插入 B. 选择 C. 冒泡 D. 快速13下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是。( A ) A选择排序法 B. 插入排序法 C. 快速排序法 D. 堆积排序法名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 8 页 - - - - - - - - - 4 19对一组数据（ 84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为（1）84 47 25 15 21 （2）15 47 25 84 21 （3）15 21 25 84 47 （4）15 21 25 47 84 则采用的排序是 ( A )。A. 选择 B. 冒泡 C. 快速 D. 插入20对序列 15，9，7，8，20，-1，4 进行排序，进行一趟后数据的排列变为4，9，-1 ，8，20，7，15；则采用的是（ C ）排序。A. 选择 B. 快速 C. 希尔 D. 冒泡21若上题的数据经一趟排序后的排列为9，15，7，8，20，-1，4，则采用的是（ C ）排序。A选择 B. 堆 C. 直接插入 D. 冒泡22下列排序算法中 ( B )不能保证每趟排序至少能将一个元素放到其最终的位置上。A.快速排序 B. shell排序 C. 堆排序 D.冒泡排序25有一组数据（ 15，9，7，8，20，-1，7，4） 用快速排序的划分方法进行一趟划分后数据的排序为 (A )（按递增序）。A下面的 B，C，D都不对。 B9，7，8，4，-1 ，7，15，20 C20，15，8，9，7，-1，4，7 D. 9，4，7，8，7，-1 ，15，20 26一组记录的关键码为（46，79，56，38，40，84） ，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（C ） 。A.(38,40,46,56,79,84) B.(40,38,46,79,56,84) C.(40,38,46,56,79,84) D. (40,38,46,84,56,79) 27. 在下面的排序方法中，辅助空间为O （n）的是 ( D ) 。 A希尔排序 B. 堆排序 C. 选择排序 D. 归并排序28下列排序算法中，在待排序数据已有序时，花费时间反而最多的是( C )排序。 A 冒泡 B. 希尔 C. 快速 D. 堆29. 下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是：（ B ）。A. 直接插入排序 B. 快速排序 C. 直接选择排序 D. 堆排序31. 就平均性能而言，目前最好的内排序方法是( D )排序法。A. 冒泡 B. 希尔插入 C. 交换 D. 快速34下列排序算法中，（ D ）算法可能会出现下面情况：在最后一趟开始之前，所有元素都不在其最终的位置上。 A. 堆排序 B. 冒泡排序 C. 快速排序 D. 插入排序36从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为( A )排序法。A. 插入 B. 选择 C. 希尔 D. 二路归并37. 在排序算法中，每次从未排序的记录中挑出最小（或最大）关键码字的记录，加入到已排序记录的末尾，该排序方法是（ A ） 。 A. 选择 B. 冒泡 C. 插入 D. 堆38用直接插入排序方法对下面四个序列进行排序（由小到大），元素比较次数最少的是（ C ） 。A 94,32,40,90,80,46,21,69 B 32,40,21,46,69,94,90,80 C 21,32,46,40,80,69,90,94 D 90,69,80,46,21,32,94,40 39直接插入排序在最好情况下的时间复杂度为（B ） A O(logn) B O(n) C O(n*logn) D O(n2) 40. 若用冒泡排序方法对序列10,14,26,29,41,52从大到小排序，需进行（C ）次名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 8 页 - - - - - - - - - 5 比较。A. 3 B. 10 C. 15 D. 25 41. 采用简单选择排序，比较次数与移动次数分别为( C )。 A. O（ n） ,O(logn) B. O(logn),0(n*n) C. 0(n*n),0(n) D. 0(nlogn),0(n) 42. 对序列 15，9，7，8，20，-1，4， 用希尔排序方法排序，经一趟后序列变为15，-l ，4，8，20，9，7 则该次采用的增量是 ( B ) A. l B. 4 C. 3 D. 2 43对下列关键字序列用快速排序法进行排序时，速度最快的情形是（A ） 。A 21,25,5,17,9,23,30 B25,23,30,17,21,5,9 C 21,9,17,30,25,23,5 5,9,17,21,23,25,30 44对关键码序列28，16，32，12，60，2，5，72 快速排序，从小到大一次划分结果为（ B ） 。A. (2,5,12,16)26(60,32,72) B. (5,16,2,12)28(60,32,72) C. (2,16,12,5)28(60,32,72) D. (5,16,2,12)28(32,60,72) 45 对 n 个记录的线性表进行快速排序为减少算法的递归深度，以下叙述正确的是（ A ）A每次分区后，先处理较短的部分 B 每次分区后，先处理较长的部分C与算法每次分区后的处理顺序无关 D以上三者都不对60设要将序列（ q,h,c,y,p,a,m,s,r,d,f,x）中的关键码按字母升序重新排序，（1）（B ）是初始步长为 4 的 shell排序一趟扫描的结果；（2）（ D ）是对排序初始建堆的结果；（3）（B ）是以第一个元素为分界元素的快速一趟扫描的结果。从下面供选择的答案中选出正确答案填入括号内。A. f ,h ,c ,d ,p ,a ,m ,q ,r ,s ,y ,x B. p ,a ,c ,s ,q ,d ,f ,x ,r ,h ,m ,y C. a ,d ,c ,r ,f ,q ,m ,s ,y ,p ,h ,x D. h ,c ,q ,p ,a ,m ,s ,r ,d ,f ,x ,y E. h ,q ,c ,y ,a ,p ,m ,s ,d ,r ,f ,x 二、判断题：1当待排序的元素很大时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂度的主要因素。（ ）2内排序要求数据一定要以顺序方式存储。（ ）3排序算法中的比较次数与初始元素序列的排列无关。（ ）4排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。（ ）5在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。（ ）6直接选择排序算法在最好情况下的时间复杂度为O （N） 。（ ）8在初始数据表已经有序时，快速排序算法的时间复杂度为O(nlog2n ) 。（ ）10 当待排序记录已经从小到大排序或者已经从大到小排序时，快速排序的执行时间最省。（ ）11 快速排序的速度在所有排序方法中为最快, 而且所需附加空间也最少。（ ）19 冒泡排序和快速排序都是基于交换两个逆序元素的排序方法, 冒泡排序算法的最坏时间复杂性是O(n*n), 而快速排序算法的最坏时间复杂性是O(nlog2n), 所以快速排序比冒泡排序算法效率更高。（ ）20交换排序法是对序列中的元素进行一系列比较，当被比较的两个元素逆序时，进行交换，冒泡排序和快速排序是基于这类方法的两种排序方法，冒泡排序算法的最坏时间复杂性是 O （n*n） ，而快速排序算法的最坏时间复杂性是O （nlog2n） ；所以快速排序比名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 8 页 - - - - - - - - - 6 冒泡排序效率更高。（ ）三、填空题1若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的_比较_和记录的 _移动5不受待排序初始序列的影响，时间复杂度为O(N2) 的排序算法是 _简单选择排序 _，在排序算法的最后一趟开始之前，所有元素都可能不在其最终位置上的排序算法是_直接插入排序（最小的元素在最后时）_。6直接插入排序用监视哨的作用是_免去查找过程中每一步都要检测整个表是否查找完毕，提高了查找效率。7对n 个记录的表r1.n进行简单选择排序，所需进行的关键字间的比较次数为n(n-1)/210下面的排序算法的思想是：第一趟比较将最小的元素放在r1 中，最大的元素放在rn 中，第二趟比较将次小的放在r2 中，将次大的放在rn-1中， , 依次下去，直到待排序列为递增序。 （注： ）代表两个变量的数据交换） 。void sort(SqList &r,int n) i=1; while( in-i+1 ) min=max=1; for (j=i+1;j=n-i+1 ; +j) if( rj.keyrmax.key) max=j; if( min!=I ) rmin rj; if(max!=n-i+1)if ( rmaxrn-i+1 ) rmin rn-i+1; else (6)_); i+; /sort 12. 设用希尔排序对数组 98，36，-9，0，47，23，1，8，10，7进行排序，给出的步长（也称增量序列）依次是4，2，1 则排序需 3 趟，写出第一趟结束后，数组中数据的排列次序 (10,7,-9,0,47,23,1,8,98,36)13从平均时间性能而言，快速排序最佳。14对于 7 个元素的集合 1 ，2，3，4，5，6，7进行快速排序，具有最小比较和交换次数的初始排列次序为 .(4,1,3,2,6,5,7)15快速排序在最好每次划分能得到两个长度相等的子文件。设文件长度 n=2k-1，第一遍划分得到两个长度n/2 的子文件，第二遍划分得到4 个长度 n/4 的子文件，以此类推，总共进行 k=log2(n+1)遍划分，各子文件长度均为1，排序结束的情况下最易发挥其长处。26下列算法为奇偶交换排序，思路如下：第一趟对所有奇数的i, 将 ai 和 ai+1 进行比较, 第二趟对所有偶数的i, 将 ai和 ai+1 进行比较 , 每次比较时若 aiai+1,将二者交换 ; 以后重复上述二趟过程 , 直至整个数组有序。void oesort (int an) int flag,i,t; do flag=0; for(i=1;iai+1) flag=(1; t=ai+1; ai+1=ai; ai:=t; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 8 页 - - - - - - - - - 7 for (i=2;iai+1) flag=1_;t=ai+1; ai+1=ai; ai=t; whileflag 四、应用题1. 内部排序（名词解释）。假设含 n 个记录的序列为 R1, R2, ， Rn ， 其相应的关键字序列为 K1, K2, ， Kn ，这 些 关 键 字 相 互 之 间 可 以 进 行 比 较 ， 即 在 它 们 之 间 存 在 着 这 样 一 个 关 系Ks1Ks2 Ksn，按此固有关系将 n 个记录序列重新排列为 Rs1, Rs2, ，Rsn 。若整个排序过程都在内存中完成，则称此类排序问题为内部排序。2。在各种排序方法中，哪些是稳定的？哪些是不稳定的？并为每一种不稳定的排序方法举出一个不稳定的实例。排序方法平均时间最坏情况辅助空间稳定性不稳定排序举例直接插入排序O （n2）O （n2）O （1）稳定折半插入排序O （n2）O （n2）O （1）稳定二路插入排序O （n2）O （n2）O （n）稳定表插入排序O （n2）O （n2）O （1）稳定起泡排序O （n2）O （n2）O （1）稳定直接选择排序O （n2）O （n2）O （1）不稳定2,2 ,1 希尔排序O （n1.3 ）O （n1.3 ）O （1）不稳定 3,2,2,1(d=2,d=1) 快速排序O （nlog2n ）O （n2）O （log2n ）不稳定2,2 ,1 堆排序O （nlog2n ） O （nlog2n ）O （1）不稳定2,1,1 ( 极大堆 ) 2-路归并排序O （nlog2n ） O （nlog2n ）O （n）稳定基数排序 O ( d*(rd+n) ) O ( d*(rd+n) ) O (rd ) 稳定7以下概念的区别：拓扑排序与冒泡排序。拓扑排序，是有向图的顶点依照弧的走向，找出一个全序集的过程，主要是根据与顶点连接的弧来确定顶点序列；冒泡排序是借助交换思想通过比较相邻结点关键字大小进行排序的算法。8简述直接插入排序，简单选择排序的基本思想以及在时间复杂度和排序稳定性上的差别。直接插入排序的基本思想是基于插入，开始假定第一个记录有序， 然后从第二个记录开始， 依次插入到前面有序的子文件中。 即将记录 Ri(2=i=n) 插入到有序子序列R1.i-1中，使记录的有序序列从R1.i-1 变为 R1.i ，最终使整个文件有序。 共进行 n-1 趟插入。最坏时间复杂度是0(n2)，平均时间复杂度是0(n2)，空间复杂度是O(1)，是稳定排序。简单选择排序的基本思想是基于选择，开始有序序列长度为零， 第 i(1=in) 趟简单选择排序是，从无序序列Ri.n 的 n-i+1 记录中选出关键字最小的记录，和第i 个记录交换，使有序序列逐步扩大，最后整个文件有序。共进行n-1 趟选择。最坏时间复杂度是0(n2)，名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 8 页 - - - - - - - - - 8 平均时间复杂度是0(n2)，空间复杂度是 O(1)，是不稳定排序。二路并归排序的基本思想是基于归并，开始将具有 n 个待排序记录的序列看成是n 个长度为 1 的有序序列，然后进行两两归并，得到 n/2 个长度为 2 的有序序列，再进行两两归并，得到 n/4 个长度为 4 的有序序列。如此重复，经过 log2n 趟归并，最终得到一个长度为 n 的有序序列。最坏时间复杂度和平均时间复杂度都是0(nlog2n)，空间复杂度是O(n)，是稳定排序。9快速排序，堆排序和希尔排序是时间性能较好的排序方法，也是稳定的排序方法。判断正误并改错。错误。快速排序，堆排序和希尔排序是时间性能较好的排序方法，但都是不稳定的排序方法。20. 设要求从大到小排序。问在什么情况下冒泡排序算法关键字交换的次数为最大。对冒泡算法而言，初始序列为反序时交换次数最多。若要求从大到小排序，则表现为初始是上升序。26（1）. （冒泡）排序过程中，有的关键字在某趟排序中可能朝着与最终排序相反的方向移动，试举例说明之。快速排序过程中有没有这种现象？（2）在执行某个排序算法过程中，出现了排序关键字朝着最终排序序列相反的方向的移动，从而认为该算法是不稳定的。这种说法对么？为什么？.这种看法不对。本题的叙述与稳定性的定义无关，不能据此来判断排序中的稳定性。例如 5,4,1,2,3 在第一趟冒泡排序后得到4,1,2,3,5。其中 4 向前移动，与其最终位置相反。但冒泡排序是稳定排序。快速排序中无这种现象。27. 对下面数据表，写出采用SHELL 排序算法排序的每一趟的结果，并标出数据移动情况。 （125，11，22， 34，15，44，76，66，100，8，14，20，2，5，1） 。125，11，22，34，15，44，76，66，100，8，14，20，2，5，1 设 D=71，11，8，14，15，2，5，66，100，22，34，20，44，76，125 D=3 1，11，2，5，15，8，14，34，20，22，66，100，44，76，125 D=1 1，2，5，8，11，14，15，20，22，34，44，66，76，100，125 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 8 页 - - - - - - - - -