数据结构习题课.pdf

《数据结构习题课.pdf》由会员分享，可在线阅读，更多相关《数据结构习题课.pdf（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1.下列排序算法中，其中（A.堆排序，冒泡排序 C.直接选择排序，归并排序）是稳定的。B.快速排序，堆排序 D.归并排序，冒泡排序 的时间内完成对数组的排序，且要求排序是稳定的，贝 U 可选择）O 3排序趟数与序列的原始状态有关的排序方法是（）排序法。C冒泡 D快速 15，21）排序，数据的排列次序在排序的过程中 （2）15 47 25 84 21（3）15 21 25 84 47（4）9,8,20,7,15;则采用的是（A.选择 B.快速 若上题的数据经 20,-1,4,则采用的 9,15,7,8,D.冒泡 7.在文 件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是（）A.直接插入

2、排序 B.冒泡排序 C.简单选择排序 8.下列排序算法中，（）算法可能会出现下面情况：在最后 一趟开始之前，所有元素都不在其最终的位置上。A.堆排序 B.冒泡排序 C.快速排序 D.插入排序 9.下列排序算法中，占用辅助空间最多的是：A.归并排序 B.快速排序 C.希尔排序 D.堆排序 10.用直接插入排序方法对下面四个 序列进行排序（由小到大），元素比较次数最少的是（）O 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 A.快速排序

3、B.堆排序 C.归并排序 D.直接插入排序 15 21 25 47 84 则采用的排序是（）A.选择 B.冒泡 C.快速 5.对序列15,9,7,8,20,-1,D.插入 4）进行排序，进行一趟后数据的排列变为4,2若需在 O（nlog2n）A.插入 B.选择 4对一组数据（84,47,25,的变化为（1）84 47 25 15 21）排序。C.希尔 D.冒泡 6.一趟排序后的排列为 是（）排序。A.选择 B.堆 C.直接插入 11.冒泡排序方法对序列10,14,26,29,41,52从大到小排序，需进行（若用）12.对 n 个记录的线性表进行快速排序为减少算法的递归深度，以下叙述正确 的是(

4、)A 每次分区后，先处理较短的部分 B 每次分区后，先处理较长的部分 C 与算法每次分区后的处理顺序无关 D 以上三者都不对 13在含有 n 个关键字的小根堆(堆顶元素最小)中，关键字最大的记录有可能存储在()位置上。A.n/2 B.n/2-1 C.1|D.n/2+2 14.对 n 个记录的文件进行堆排序，最坏情况下的执行时间是多少？()A.O(Iog2n)B.O(n)C.O(nlog2n)D.O(n*n)15.就排序算法所用的辅助空间而言，堆排序，快速排序，归并排序的关系是()A.堆排序快速排序归并排序 B.堆排序归并排序快速排序 C.堆排序归并排序快速排序 D.堆排序 快速排序 归并排序

5、16 如果只想得到 1000 个元素组成的序列中第 5 个最小元素之前的部分排序的 序列，用()方法最快。A.起泡排序 B 快速排列 C.Shell 排序 D 堆排序 E 简单选择排序 17 数据序列(8,9,10,4,5,6,20,1,2)只能是下列排序算法中的()的两趟排序后的结果。A 选择排序 B.冒泡排序 C.插入排序 D.堆排序 18 分别采用堆排序，快速排序，冒泡排序和归并排序，对初态为有序的表，则最省时间的是 _ 法，最费时间的是 _ 法。答：冒泡，快速 19设用希尔排序对数组98,36,9,0,47,23,1,8,10,7进行排序，给岀的 步长(也称增量序列)依次是 4,2,1

6、 则排序需 _ ,写出第一 趟结束后，数组中数据的排列次序 _ o 答：3,(107,-9,0,47,23,1,8,98,36)20 堆是一种有用的数据结构。试判断下面的关键码序列中哪一个是堆 16,72,31,23,94,53 94,53,31,72,16,23 16,53,23,94,31,72 16,31,23,94,53,72 94,31,53,23,16,72 次比较。A.3 B.10 C.15 D.25 堆排序是一种(1)类型的排序,它的一个基本问题是如何建堆，常用的建 堆算法是 1964 年 Floyd 提出的，对含有 n 个元素的序列进行排序时，堆排序的时 间复杂度是(3),所

7、需要的附加结点是(4)o 答：是堆 选择 筛选法(3)0(nlog2 n)(4)0(1)21 关键码序列(Q,H,C,丫，Q,A,M,S,R,D,F,X),要按照关键 码值递增的次序进行排序，若采用初始步长为 4 的 Shell 排序法，则一趟扫描的 结果是_；若采用以第一个元素为分界元素的快速排序法，则扫描一趟的结 果是 O 答:(Q,A,C,S,Q,D,F,X,R,H,M,Y),(F,H,C,D,Q,A,M,Q,R,S,Y,X)22.算法模拟 设待排序的记录共 7 个，排序码分别为 8,3,2,5,9,1,6o(1)用直接插入排序。试以排序码序列的变化描述形式说明排序全过程(动态过程)要求

8、按递减顺序排序。(2)用直接选择排序。试以排序码序列的变化描述形式说明排序全过程(动 态过程)要求按递减顺序排序。(3)直接插入排序算法和直接选择排序算法的稳定性如何?(3)直接插入排序是稳定排序，直接选择排序是不稳定排序 o 23已知某文件的记录关键字集为50,10,50,40,45,85,80,选择一种从 平均性能而言是最佳的排序方法进行排序，且说明其稳定性。解答：平均性能最佳的排 序方法是快速排序，该排序方法不稳定。初始序列:50,10,50,40,45,85,80 一趟排序：45,10,50,40 50 85,80二趟排序：40,10 45 50 50 80 85 三趟排序：10,40

9、,45,50,50,80,85 24 对给定文件(28,07,39,10,65,14,61,17,50,21)选择第一个 元素 28 进行划分，写出其快速排序第一遍的排序过程。解答：初始序列：28,0 乙 39,10,65,14,61,17,50,21 21 移动：21,07,39,10,65,14,61,17,50,0 39 移动：21,0 乙 0,10,65,14,61,17,50,39 17 移动:21,07,17,10,65,14,61,(,50,39 65 移动:21,07,17,10,14,61,65,50,39 14 移动：21,07,17,10,14,28,61,65,50,3

10、9 25.已知一关键码序列为：3,87,12,61,70,97,26,45。试根据堆排序 解答：(1)直接插入排序 第一趟(3)8,3,2,5,9 丄 6 第三趟(5)8,533,239,1,6 第五趟 9,8,5,3,2,1,6 第二趟8,3,2,5,9,1,6 第四趟（9）9,855,352,1,6（(2)直接选择排序(第六趟后仅剩一个元 是最小的，直接选择排序结束)第一趟（9）9,3,乙 5,8 丄 6 第三趟（6）9,8,6,5,3,1,2 第五趟（3）9,8,6,5,3,1,2 第二趟（8）9,8,2,5,3 丄 6 第四趟（5）9,8,6,5,3,1,2 第六趟原 理，填写下示各步

11、骤完整结果。建立堆结构:交换与调整：(1)87 7026 61 45 12 3 97;(2);(3)61 4526 3 1270 87 97;(4);(5)26 123 45 61 70 87 97;(6);(刀 3 12 26 45 6170 87 97;解答:建立堆结构:97,87,26,61,70,12,3,45(2)70,61,26,3,45,12,87,97(4)45,12,26,3,61,70,87,97(6)12,3,26,45,61,70,87,97 26已知待排序的序列为(503,87,512,61,908,170,897,完成下列各题。(1)根据以上序列建立一个堆(画出第一

12、步和最后堆的结果图)小值。(2)输出最小值后，解答：27给出一组关键字T=(12,2,16,30,8,28,4,10,20,6,18)出用下列算法从小到大排 序时 第一趟结束时的序列；(1)希尔排序(第一趟排序的增量为 5)(2)快速排序(选第一个记录为枢轴(分隔)(3)链式基数排序(基数为 10)解答：一趟希尔排序 20,6,18,4,16,30,8,28(D=5)(2)趟快速排序：6,2,10,4,8,12,28,30,20,16,18(3)链式基数排序 LSD 0123456789 275,653,462),试,希望先输出最 如何得到次小值。(并画出相应结果图)(2)求次小值 87 12

13、 46 51 分配 30 12 4 16 8 10 2 6 28 20 18 收集：30102012 24166 8 2818 2&请写出应填入下列叙述中()内的正确答案。排序有各种方法，如插入排序、快速排序、堆排序等。29.写出一趟快速排序算法。int Partition(RecType R,int I,int h)/趟快速排序 算法，枢轴记录到位，并返回其所在位置，int i=l;j=h;R0=Ri;x=Ri.key;while(ij)while(i=x)j-;if(ij)Ri=Rj;while(ij&Ri.key=x)i+;if(ij)Rj=Ri;/while Ri=R0;return

14、i;/Partition 30设有一个数组中存放了一个无序的关键序列 K1、K2、Kn。现要求将 Kn 放在将元素排序后的正确位置上，试编写实现该功能的算法，要求比较关键字的次 数不超过 n。(注：用程序实现)题目分析以 Kn 为枢轴的一趟快速排序。将上题算法改为以最后一个为枢轴先 从前向 后再从后向前。int Partition(RecType K,int I,int n)/交换记录子序列 Kl.n中的记录，使枢轴记录到位，并返回其所在位 置，此 时，在它之前(后)的记录均不大(小)于它 int i=l;j=n;K0=Kj;x=Kj.key;while(ij)while(ij&Ki.key=

15、x)i+;if(ij)K0=Ki;while(i=x)j-;if(ij)Ki=KU;/while Ki=K0;return i;/Partition 31.二路插入排序是将待排关键字序列 r1.n中关键字分二路分别按序插入到辅助 向量 d1.n前半部和后半部(注：向量 d 可视为循环表)，其原则为，先将 rl赋给 d1,再从r2记录开始分二路插入。编写实现二路插入排序算法。void BilnsertSort(RecType R,int n)/二路插入排序的算法 intdn+1;辅助存储 d1=R1;first=1;final=1;设一数组中原有数据如下：15 13,序方法进行一遍排序后的结果。

16、()排序的结果为：12 13 15()排序的结果为：13 15 18()排序的结果为：13 15 20()排序的结果为：12 13 20 解答：快速排序 冒泡排序 18 20,60 12 20,60 18 12,60 18 15,60 直接插入排序 堆排序 20,18,12,60o 下面是一组由不同排 for(i=2;i=d1.key)/插入后部 low=1;high=final;while(low=high)折半查找插入位置 m=(low+high)/2;if(Ri.key=high+1:j-)dj+1=dj;/移动元素 dhigh+1=Ri;final+;/插入有序位置 else 插入前部 if(first=1)first=n;dn=Ri;else low=first;high=n;while(low=high)m=(low+high)/2;if(Ri.key dm.key)high=m;else low=m+1;/while for(j=first;jv=high;j+)dj-1=dj；/移动元素 dhigh=Ri;first-;/if/if/for R1=dfisrt;for(i=first%n+1,j=2;i!=fisrt;i=i%n+1,j+)Rj=di;/将序列复制回去/BilnsertSort