计算机专业基础综合数据结构

《计算机专业基础综合数据结构》由会员分享，可在线阅读，更多相关《计算机专业基础综合数据结构（7页珍藏版）》请在装配图网上搜索。

1、计算机专业基础综合数据结构（排序）-试卷 1（总分：58.00，做题时间：90 分钟）一、 单项选择题（总题数：16，分数：32.00）1. 单项选择题 1-40 小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。解析：2. 下面给出的4 种排序方法中，（ ）排序法是不稳定性排序法。（分数：2.00）A. 插入B. 冒泡C. 二路归并D. 堆丿解析：解析：此题考查的知识点是排序算法的稳定性问题。如果待排序的文件中，存在多个关键字相同的 记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，则称这种排序是稳定的排序：反 之，若具有相同关键字的记录之间的相对次序发生变化，则

2、称这种排序是不稳定的排序。是否稳定与算法 有关，相邻数据比较的算法是稳定的，不相邻数据比较会出现不稳定。选项A、B、C都是相邻元素比较， 是稳定的。所以选Do3. 下列内部排序算法中，其比较次数（或交换次数）与序列初态无关的算法是（ ）。（分数：2.00）A. 快速排序B. 直接插入排序C. 二路归并排序丿D. 冒泡排序解析：解析：此题考查的知识点是各类排序算法的思想。冒泡排序方法就是自底向上检查这个序列，若两 个相邻的元素的顺序不对，则交换。直到所有元素处理完为止。与序列初态有关，D错。直接插入排序思 想是假设待排序的记录存放在数组Rn+1中，排序过程中的某一时刻，R被分成两个子区间Ri 一

3、 1 和Ri,Rn，其中，前一个子区间是已排好序的有序区；后一个子区间是当前未排序的无序区。 直接插入排序的基本操作是将当前无序区的第i个记录Ri插入到有序区中的适当位置，使得R1到Ri 变为新的有序区。首先比较Ri和Ri1，如果Ri 一 lWRi，则Rl. i已排好序，第i遍处理 就结束了；否则交换Ri与Ri 一 1的位置，继续比较Ri1和Ri 一 2,直到找到某一个位置j（lWjWi 一 1）使得RjWRj+l时为止。与序列初态有关，B错。快速排序是通过基准元素v把表（文件，数据集 合）划分成左、右两部分，使得左边的各记录的关键字都小于v；右边的各记录的关键字都大于等于v；重 复该过程直到

4、排好序。与序列初态有关，A错。二路归并是首先把每个记录看成是一个有序序列，共n个， 将它们两两合并成n/2个分类序列，每个序列长度为2（当n为奇数时，最后一个序列长度为1）；对n / 2个分类序列，再两两归并在一起；如此进行，直到归并成一个长度为n的分类序列为止。与序列初态 无关，所以选Co4下列内部排序算法中，在初始序列已基本有序（除去n个元素中的某k个元素后即呈有序，kn）的情 况下，排序效率最高的算法是（ ）o（分数： 2.00）A. 冒泡排序B. 堆排序C. 直接插入排序丿D. 二路归并排序解析：解析：此题考查的知识点是各类排序算法的效率。起泡排序比较n（n 一 1） /2次，没有交换

5、次数； 堆排序一次比较log n次，共需要n轮；直接插入排序比较n1次，没有交换；二路归并排序一次比较2log n次，共需要n轮。综上，应选Co25.下列排序算法中，（ ）每一趟都能选出一个元素放在最终位置上，并且是不稳定的。 （分数：2.00）A. 冒泡排序B. 希尔排序C. 简单选择排序丿D. 直接插入排序解析：解析：本题考查各种内部排序算法的比较，考生一定要熟记下面这张表格。6下列排序方法中，时间复杂性不受数据初始状态影响，恒为O（nlog 2 n）的是（）。（分数：2.00）A. 堆排序丿B. 冒泡排序C. 直接选择排序D. 快速排序 解析：解析：由这些排序方法的特点可知本题答案为Ao

6、7. 下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是（ ） （分数： 2.00）A. 选择排序B. 冒泡排序C. 归并排序丿D. 堆排序解析：解析：此题考查的知识点是各类排序算法的思想。应选Co8. 下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响 的是（ ）o分数： 2.00）A. 直接插入排序丿B. 归并排序C. 直接选择排序D. 堆排序 解析：解析：此题考查的知识点是各类排序算法的思想。应选Ao对初始状态为递增序列的表按递增顺序排序，最省时间的是（1）算法，最费时间的是（2）算法。（分 数： 4.00）（1）.（1）（分数：

7、2.00）A. 堆排序B. 快速排序C. 插入排序丿D. 归并排序解析：（2）.（2）（分数： 2.00）A. 堆排序B. 快速排序丿C. 插入排序D. 归并排序解析：解析：此题考查的知识点是各类排序算法的思想。应选C，Bo9如果只想得到1 000个元素组成的序列中第5个最小元素之前的部分排序的序列，用（）方法最快。 （分数： 2.00）A. 冒泡排序B. 快速排序C. 简单选择排序D. 堆排序丿解析：解析：此题考查的知识点是各类排序算法的思想。冒泡排序和简单选择排序每次要比较n 一 i次， 快速排序结束后才能得到结果，堆排序可以在选择5次后得到结果，每次比较元素次数为log 2n。所以应 选

8、 D。10. 数据表A中有10 000个元素，如果仅要求求出其中最大的10个元素，则采用（）方法最节省时间。 （分数： 2.00）A. 堆排序丿B. 希尔排序C. 快速排序D. 直接选择排序 解析：解析：只有堆排序每次输出一个堆顶元素（即最大或最小值的元素），然后对堆再进行调整，保证堆 顶元素总是当前剩下元素的最大或最小的，本题答案为A。11. 若对序列（tang，deng，an，wang，shi，bai，fang，liu）采用简单选择排序法按字典顺序进行排序, 下面给出的四个序列中，第三趟的结果是（ ）。（分数： 2.00）A. an ， bai， deng， wang， tang， fan

9、g， shi， liuB an， bai， deng， wang， shi， tang， fang， liu VC. an， bai， deng， wang， fang， shi， tang， liuD. an， bai， deng， wang， shi， liu， tang， fang解析：解析：本题根据简单选择排序法的算法思想可得答案B。12. 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合 适位置，该排序方法称为（ ） 排序法。（分数： 2.00）A. 插入 VB. 选择C. 希尔D. 二路归并解析：解析：此题考查的知识点是各类排序算法的思想。

10、应选A。13. 若用冒泡排序方法对序列10， 14， 26， 29， 41， 52从大到小排序，需进行（ ）次比较。（分数： 2.00）A. 3B. 10C. 15VD. 25第5趟比较1次，结束。共15次，应选Co解析：解析：此题考查的知识点是冒泡算法的思想及过程。第一趟比较5次，第2趟比较4次，第3趟比 较3次，第4趟比较2次（分数：2.00）A.19，75，34，26，97，56B.97，26，34，75，19 ，56C.19，56，26，97，34，75D.19，34，26，97，56，75解析：解析：完全二叉树中所V、右孩子结点的值，则此序列可得出答案为Do14. 下列（）是一个堆。

11、称为堆。据此，可画出二叉树，如下图所示：15. 若一组记录的关键码为（46， 79， 56， 38， 40， 84），则利用快速排序的方法，以第1 个记录为基准得到 的一次划分结果为（ ） o（分数： 2.00）A.38， 40， 46， 56， 79， 84B. 40，38，46，79，56，84C. 40, 38, 46, 56, 79, 84 丿D. 40， 38， 46， 84， 56， 79解析：解析：对于（46, 79, 56, 38, 40, 84）,取出46,对（79, 56, 38, 40, 84）进行划分,先将79与 40交换,得到（40, 56, 38, 79, 84）,

12、再将56与38交换,得到（40, 38, 56, 79, 84）,将46插入得到 （40, 38, 46, 56, 79, 84）,本题答案为 C。二、 综合应用题（总题数：13,分数：26.00）16. 综合应用题41-47小题。（分数：2.00）解析：17. 在执行某种排序算法的过程中出现了排序码朝着最终排序序列相反的方向移动,从而认为该排序算法是 不稳定的,这种说法对吗?为什么?（分数：2.00） 正确答案：（正确答案：这种说法不对。因为排序的不稳定性是指两个关键字值相同的元素的相对次序在排序前后发生了变化,而题中叙述和排序中稳定性的定义无关,所以此说法不对。）解析：18. 设有5个互不

13、相同的元素a, b, c, d, e,能否通过7次比较就将其排好序，7如果能，请列出其比较过程：如果不能,则说明原因。（分数：2.00） 正确答案：（正确答案：可以做到。取a与b进行比较，c与d进行比较。设ab, cd（ab和cd情 况类似），此时需2次比较，取b和d比较，若bd,则有序abd；若bd时则有序cdb,此时 已进行了3次比较。再把另外两个元素按折半插入排序方法,插入到上述某个序列中共需4次比较,从而 共需 7 次比较。 ）解析：19. 对一个由n个关键字不同的记录构成的序列，能否用比2n 一 3少的次数选出该序列中关键字取最大值 和关键宇取最小值的记录?请说明如何实现?在最坏的情

14、况下至少要进行多少次比较?（分数： 2.00） 正确答案：（正确答案：将n个元素对称比较，即第一个元素与最后一个元素比较，第二个元素与倒数第二 个元素比较比较中的小者放前半部，大者放后半部，用了n/2次比较。再在前后两部分中分别简单选 择最小和最大元素，备用（n/2） 1次比较。总共用了（3n/2） 2次比较。显然，当n3时，（2n 3） （3n/2） 2.用分治法求解再给出另一参考答案。对于两个数x和y,经一次比较可得到最大值和最小 值；对于三个数x, y, z,最多经3次比较可得最大值和最小值；对于n个数（n3），将分成长为n 一 2 和2的前后两部分A和B,分别找出最大者和最小者：Max

15、A, Min A, MaxB, Min B,最后Max=MaxA, MaxB和Min=Min A, Min B。对A使用同样的方法求出最大值和最小值，直到元素个数不超过3。设C（n）是所需的最多比较次数，根据上述原则，当n3时有如下关系式:,可以得到： C（n）=（3n/ 2） 一 2。显然，当n3时，2n 一 3（3n/2） 2。事实上（3n/2） 2是解决这一问题的比较次数的下 限。 ）解析：20. 利用比较的方法进行排序,在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明 （分数： 2.00） 正确答案：（正确答案：假定待排序的记录有n个。由于含n个记录的序列可能出现的状态有n!

16、个，则描 述n个记录排序过程的判定树必须有n!个叶子结点。因为若少一个叶子，则说明尚有两种状态没有分辨出 来。我们知道，若二又树高度是h,则叶子结点个数最多为2 h-1 ；反之，若有u个叶子结点，则二叉树的 高度至少为（log u）+1。这就是说，描述n个记录排序的判定树必定存在一条长度为log （n!）的路径。22即任何一个借助“比较”进行排序的算法，在最坏情况下所需进行的比较次数至少是log(n!)。根据斯2特林公式，有log(n!)=O(nlog n)。即借助于“比较”进行排序的算法在最坏情况下能达到的最好时22间复杂度为0(nlog n)。提示：此题考查的知识点是基于比较的排序算法效率

17、。)2解析：21. 已知下列各种初始状态(长度为n)元素，试问当利用直接插入法进行排序时，至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)？(1)关键字自小到大有序(key Vkey VVkey )；12n(2)关键字自大到小逆序(key key key )；(3)奇数关键字顺序有序，偶数关键字顺序有序12n(key key，key key )；(4)前半部分元素按关键字顺序有序，后半部分元素按关键1324字顺序逆序(key key keykey， m为中间位置)。12mm+1m+2n(分数： 2.00)正确答案： (正确答案：本题主要考查直接插入法的算法思想及性能分析。 根

18、据题目所给出的条件，最好 情况下的比较次数即为最少比较次数。(1)在关键字自小到大有序的情况下，插入第i个(2WiWn)元素的 比较次数为1，因此，总的比较次数为l+l+l+l=n 1。 (2)在关键字自大到小有序的情况下，插入第 i个(2WiWn)元素的比较次数为i，因此，总的比较次数为2+3+4+n=n(n+l)/ 2 1=(n 一 1)(n+2) 2。 (3)在奇数关键字顺序有序和偶数关键字顺序有序的情况下，比较次数最少的情况是所有记录关键字 均按升序排列，这时，总的比较次数为n 一 1。(4)在前半部分元素按关键字有序，后半部分按关键字逆序的情况下，后半部分元素的关键字均大于前半部分元

19、素的关键字时比较次数最少，此时前半部分的比较 次数为m1，后半部分的比较次数为(nm1)(n 一 m+2) / 2，因此，总的比较次数为m 1+(nm 一 1)(n 一 m+2) / 2=(n 一 2)(n+8) / 8(假设 n 为偶数， m=n/ 2).)解析：22对于n个元素组成的线性表进行快速排序时，所需进行的比较次数与这n个元素的初始排序有关。问： 当n=7时，在最好情况下需进行多少次比较?请说明理由。(2)当n=7时，给出一个最好情况的初始排 序的实例。(3)当n=7时，在最坏情况下需进行多少次比较?请说明理由。(4)当n=7时，给出一个最坏情 况的初始排序的实例。(分数： 2.0

20、0) 正确答案：(正确答案：(1)在最好情况下，假设每次划分能得到两个长度相等的子文件，文件的长度n=2k 一 1，那么第一遍划分得到两个长度均为n/2的子文件，第二遍划分得到4个长度均为n/4的子文件， 以此类推，总共进行k=log (n+1)遍划分，各子文件的长度均为1，排序完毕。当n=7时，k=3，在最好2情况下，第一遍需比较6次，第二遍分别对两个子文件(长度均为3, k=2)进行排序，各需2次，共10次 即可. (2)在最好情况下快速排序的原始序列实例： 4， 1， 3， 2， 6， 5， 7。 (3)在最坏情况下，若每次用 来划分的记录的关键字具有最大值(或最小值)，那么只能得到左(

21、或右) 子文件，其长度比原长度少1。因 此，若原文件中的记录按关键字递减次序排列，而要求排序后按递增次序排列时，快速排序的效率与冒泡 排序相同，其时间复杂度为0(n 2 )。所以当n=7时，最坏情况下的比较次数为21次。(4)在最坏情况下 快速排序的初始序列实例： 7， 6， 5， 4， 3， 2， 1，要求按递增排序。 提示：此题考查的知识点是快速排 序的思想。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据 都比另一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以 递归进行，以此达到整个数据变成有序序列。 )解析：23.

22、 关于堆的一些问题： (1)堆的存储表示是顺序的，还是链接的? (2)设有一个最小堆，即堆中任意结点 的关键字均大于它的左孩子和右孩子的关键字。其具有最大值的元素可能在什么地方？(3)对n个元素进行 初始建堆的过程中，最多做多少次数据比较(不用大0表示法)?(分数： 2.00) 正确答案： (正确答案： (1)堆的存储是顺序的。 (2)最大值元素一定是叶子结点，在最下两层上。 (3)在 建含有n个元素、深度为h的堆时，其比较次数不超过4n，推导如下：由于第i层上的结点数至多是2 i-1， 以它为根的二叉树的深度为h 一 i+1，则调用n/2次筛选算法时总共进行的关键字比较次数不超过下式之值K，

23、n,三K解析提示：此题考查的知识点是堆的基本定义及效率。堆定义为 n 个关键字序列 K ，K ，12i当且仅当该序列满足如下性质（简称为堆性质）：（l）k WK 且k WK 或（2）k三K 且ki 2i i2i+1（lWiWn）。k 相当于二叉树的非叶结点，k 则是左孩子，k是右孩子。）2i+1 i 2i 2i+124. 若有N个元素已构成一个小根堆，那么如果增加一个元素为K，请用文字简要说明如何在log nn+12的时间内将其重新调整为一个堆。分数： 2.00）正确答案：（正确答案：KK是堆，在K加入后，将K -k 调成堆。设c=n+l，f=c/2，若1 nn+11n+1k WK ，则调整完

24、成。否则K 与K 交换之后，c=f,f=c/2，继续比较，直到K WK 或f=0，f cfcf c即为根结点，调整结束。 ）解析：25. 冒泡排序方法是把大的元素向上移（气泡的上浮），也可以把小的元素向下移（气泡的下沉）。请给出上浮和下沉过程交替的冒泡排序算法。（分数： 2.00）正确答案： （正确答案： void BubbleSort2（int a， int n） /相邻两趟向相反方向起泡的冒泡排序算 法 int change=l； low=0； high=n1； / 冒泡的上下界 while（lowhigh&change） change=0; / / 交换标志 for（i=low； ihi

25、gh； i+） /从上向下起泡 if（aiai+l）ai+ai+l ； change=1； /有交换，修改标志change high 一一； /修改上界for（i=high； ilow； i 一一）/从下向上 起泡 if（ai ai+lai+ai 1 ； change=1； low+；/修改下界 提示：此题考查的知识点是双向冒泡算法。题目中“向上移”理解为向序列的右端，而“向下移”按向序列的左端来处理。 ） 解析：26. 有一种简单的排序算法，叫做计数排序（Count sorting）。这种排序算法对一个待排序的表（用数组表示） 进行排序，并将排序结果存放到另一个新的表中。必须注意的是，表中所

26、有待排序的关键字互不相同，计 数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键字比该记录的关键 字小。假设针对某一个记录，统计出的计数值为c，那么，这个记录在新的有序表中的合适的存放位置即 为c。设计实现计数排序的算法。对于有n个记录的表，关键字的比较次数是多少?与简单选择排序相比 较，这种方法是否更好?为什么?（分数： 2.00）正确答案： （正确答案： typedef struct int key； datatype info RecType： void CountSort（RecType a，b，int n） /计数排序算法,将 a 中记录排序放入 b 中 i

27、nt i，j，cnt： for（i=0； in； i+） / / 对每一个元素 for（j=0，cnt=0； jn； j+） if（aj.keya i. key）cnt+； /统计关键字比它 小的元素个数Bcnt=ai ； 对于有n个记录的表，关键字比较n 2次。简单选择排序算法比本算法好。简单选择排序的比较次数是n（n 一 1） /2,且只用一个交换记录的空间：而这种方法的比较次数是n 2 ，且需要另一数组空间。 ）解析：27. 某个待排序的序列是一个可变长度的字符串序列，这些字符串一个接一个地存储于唯一的字符数组中。 请改写快速排序算法，对这个字符串序列进行排序。（分数： 2.00）28.

28、 设有一个数组中存放了一个无序的关键字序列K , K ，K 。现要求将K 放在将元素排序后12nn 的正确位置上，试编写实现该功能的算法，要求比较关键字的次数不超过 n。(分数：2.00) 正确答案：(正确答案：int Partition(RecType K， int m， int n) /交换记录子序列Kl. n中 的记录，使枢轴记录到位，并返回其所在位置 此时，在它之前(后)的记录均不大(小)于它 int i=m， j=n, K0=Kj, x=Kj. key； while(ij) while(ij&Ki. key=x)i+： if(ij)Kj=Ki； wh il e(i j &Kj. key=X)j 一； if(i j)Ki=Kj: / wh ile Ki=K0 ； return i： 提 示：此题考查的知识点是快速排序的思想。以 K 为枢轴的一趟快速排序。以最后一个关键字为枢轴先从 n前向后再从后向前快速排序。 )解析：