计算机专业基础综合(排序)模拟试卷3

(总分：54.00，做题时间：90分钟)

一、单项选择题1-40小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。(总题数：15，分数：30.00)

1.下面给出的4种排序方法中，( )排序法是不稳定性排序法。 A.插入 B.冒泡 C.二路归并 D.堆 √

此题考查的知识点是排序算法的稳定性问题。如果待排序的文件中，存在多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，则称这种排序是稳定的排序；反之，若具有相同关键字的记录之间的相对次序发生变化，则称这种排序是不稳定的排序。是否稳定与算法有关，相邻数据比较的算法是稳定的，不相邻数据比较会出现不稳定。选项A、B、C都是相邻元素比较，是稳定的。所以选D。

2.下列内部排序算法中，其比较次数(或交换次数)与序列初态无关的算法是( )。 A.快速排序 B.直接插入排序 C.二路归并排序 √ D.冒泡排序

此题考查的知识点是各类排序算法的思想。 冒泡排序方法就是自底向上检查这个序列，若两个相邻的元素的顺序不对，则交换。直到所有元素处理完为止。与序列初态有关，D错。 直接插入排序思想是假设待排序的记录存放在数组R[n+1]中，排序过程中的某一时刻，R被分成两个子区间[R[1]，R[i—1/]/]和[R[i]，R[n/]/]，其中，前一个子区间是已排好序的有序区；后一个子区间是当前未排序的无序区。直接插入排序的基本操作是将当前无序区的第i个记录R[i]插入到有序区中的适当位置，使得R[1]到R[i]变为新的有序区。首先比较R[i]和R[i—1]，如果R[i—1]≤R[i]，则R[1．．i]已排好序，第i遍处理就结束了；否则交换R[i]与R[i—1]的位置，继续比较R[i—1]和R[i一2]，直到找到某一个位置j(1≤j≤i—1)使得R[j]≤R[j+1]时为止。与序列初态有关，B错。 快速排序是通过基准元素v把表(文件，数据集合)划分成左、右两部分，使得左边的各记录的关键字都小于v；右边的各记录的关键字都大于等于v；重复该过程直到排好序。与序列初态有关，A错。 二路归并是首先把每个记录看成是一个有序序列，共n个，将它们两两合并成[n／2]个分类序列，每个序列长度为2(当n为奇数时，最后一个序列长度为1)；对[n／2]个分类序列，再两两归并在一起；如此进行，直到归并成一个长度为n的分类序列为止。与序列初态无关，所以选C。

3.下列内部排序算法中，在初始序列已基本有序(除去n个元素中的某k个元素后即呈有序，k< A.冒泡排序 B.堆排序

C.直接插入排序 √ D.二路归并排序

此题考查的知识点是各类排序算法的效率。起泡排序比较n(n—1)／2次，没有交换次数；堆排序一次比较log 2 n次，共需要凡轮；直接插入排序比较n一1次，没有交换；二路归并排序一次比较log 2 n次，共需要n轮。综上，应选C。

4.下列排序算法中，( )每一趟都能选出一个元素放在最终位置上，并且是不稳定的。 A.冒泡排序 B.希尔排序 C.简单选择排序 √ D.直接插入排序

本题考查各种内部排序算法的比较，考生一定要熟记下面这张表格。 A.堆排序 √ B.冒泡排序 C.直接选择排序 D.快速排序

由这些排序方法的特点可知本题答案为A。

5.下列排序方法中，时间复杂性不受数据初始状态影响，恒为O(nlog 2 n)的是( )。

6.下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是( )。 A.选择排序 B.冒泡排序 C.归并排序 √ D.堆排序

此题考查的知识点是各类排序算法的思想。应选c。

7.下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是( )。

A.直接插入排序 √ B.归并排序 C.直接选择排序 D.堆排序

此题考查的知识点是各类排序算法的思想。应选A。

8.对初始状态为递增序列的表按递增顺序排序，最省时间的是( (1) )算法，最费时间的是( (2) )算法。 A.堆排序 直接选择排序 B.冒泡排序 直接插入排序 C.插入排序 快速排序 √ D.归并排序 希尔排序

此题考查的知识点是各类排序算法的思想。应选C。

9.如果只想得到1 000个元素组成的序列中第5个最小元素之前的部分排序的序列，用( )方法最快。 A.冒泡排序 B.快速排序 C.简单选择排序 D.堆排序 √

此题考查的知识点是各类排序算法的思想。冒泡排序和简单选择排序每次要比较n—i次，快速排序结束后才能得到结果，堆排序可以在选择5次后得到结果，每次比较元素次数为log 2 n。所以应选D。 10.数据表A中有10 000个元素，如果仅要求求出其中最大的10个元素，则采用( )方法最节省时间。 A.堆排序 √ B.希尔排序 C.快速排序 D.直接选择排序

只有堆排序每次输出一个堆顶元素(即最大或最小值的元素)，然后对堆再进行调整，保证堆顶元素总是当前剩下元素的最大或最小的，本题答案为A。

11.若对序列(tang，deng，an，wang，shi，bai，fang，liu)采用简单选择排序法按字典顺序进行排序，下面给出的四个序列中，第三趟的结果是( )。 A.an，bai，deng，wang，tang，fang，shi，liu B.an，bai，deng，wang，shi，tang，fang，liu √ C.an，bai，deng，wang，fang，shi，tang，liu D.an，bai，deng，wang，shi，liu，tang，fang 本题根据简单选择排序法的算法思想可得答案B。

12.从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为( )排序法。 A.插入 √ B.选择 C.希尔 D.二路归并

此题考查的知识点是各类排序算法的思想。应选A。

13.若用冒泡排序方法对序列{10，14，26，29，41，52}从大到小排序，需进行( )次比较。 A.3 B.10 C.15 √ D.25

此题考查的知识点是冒泡算法的思想及过程。第一趟比较5次，第2趟比较4次，第3趟比较3次，第4趟比较2次，第5趟比较1次，结束。共15次，应选C。 14.下列( )是一个堆。 A.19，75，34，26，97，56 B.97，26，34，75，19，56 C.19，56，26，97，34，75 D.19，34，26，97，56，75 √

D。完全二叉树中所有非终端结点的值均不大于(或不小于)其左、右孩子结点的值，则此序列可称为堆。据此，可画出二叉树，如下图所示：的一次划分结果为( )。 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

对于(46，79，56，38，40，84)，取出46，对(79，56，38，40，84)进行划分，先将79与40交换，得到(40，56，38，79，84)，再将56与38交换，得到(40，38，56，79，84)，将46插入得到(40，38，46，56，79，84)，本题答案为C。

得出答案为D。

15.若一组记录的关键码为(46，79，56，38，40，84)，则利用快速排序的方法，以第1个记录为基准得到

二、综合应用题41-47小题。(总题数：12，分数：24.00)

16.在执行某种排序算法的过程中出现了排序码朝着最终排序序列相反的方向移动，从而认为该排序算法是不稳定的，这种说法对吗?为什么?

__________________________________________________________________________________________ 正确答案：(正确答案：这种说法不对。因为排序的不稳定性是指两个关键字值相同的元素的相对次序在排序前后发生了变化，而题中叙述和排序中稳定性的定义无关，所以此说法不对。)

17.设有5个互不相同的元素a，b，c，d，e，能否通过7次比较就将其排好序?如果能，请列出其比较迎程；如果不能，则说明原因。

__________________________________________________________________________________________ 正确答案：(正确答案：可以做到。取a与b进行比较，c与d进行比较。设a＞b，c＞d(a＜b和c＜d情况类似)，此时需2次比较，取b和d比较，若b＞d，则有序a＞b＞d；若b＜d时则有序c＞d＞b，此时已进行了3次比较。再把另外两个元素按折半插入排序方法，插入到上述某个序列需4次比较，从而共需7次比较。)

18.对一个由n个关键字不同的记录构成的序列，能否用比2n一3少的次数选出该序列中关键字取最大值和关键字取最小值的记录?请说明如何实现?在最坏的情况下至少要进行多少次比较?

__________________________________________________________________________________________ 正确答案：(正确答案：将n个元素对称比较，即第一个元素与最后一个元素比较，第二个元素与倒数第二个元素比较……比较中的小者放前半部，大者放后半部，用了n／2次比较。再在前后两部分中分别简单选

择最小和最大元素，各用(n／2)一1次比较。总共用了(3n／2)一2次比较。显然，当n≥3时，(2n一3)＞(3n／2)一2。 用分治法求解再给出另一参。 对于两个数x和y，经一次比较可得到最大值和最小值；对于三个数x，y，z，最多经3次比较可得最大值和最小值；对于凡个数(n＞3)，将分成长为n一2和2的前后两部分A和B，分别找出最大者和最小者：Max A，Min A，Max B，Min B，最后Max={Max A，Max B}和Min={Min A，MinB}。对A使用同样的方法求出最大值和最小值，直到元素个数不超过3。 设C(n)是所需的最多比较次数，根据上述原则，当n＞3时有如下关系式：限。)

19.利用比较的方法进行排序，在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。 __________________________________________________________________________________________ 正确答案：(正确答案：假定待排序的记录有n个。由于含n个记录的序列可能出现的状态有n!个，则描述n个记录排序过程的判定树必须有n!个叶子结点。因为若少一个叶子，则说明尚有两种状态没有分辨出来。我们知道，若二叉树高度是h，则叶子结点个数最多为2 ；反之，若有u个叶子结点，则二叉树的高度至少为(log 2 u)+1。这就是说，描述n个记录排序的判定树必定存在一条长度为log 2 (n!)的路径。即任何一个借助“比较”进行排序的算法，在最坏情况下所需进行的比较次数至少是log 2 (n!)。根据斯特林公式，有log 2 (n!)=O(nlog 2 n)。即借助于“比较”进行排序的算法在最坏情况下能达到的最好时间复杂度为O(nlog 2 n)。 提示：此题考查的知识点是基于比较的排序算法效率。)

20.已知下列各种初始状态(长度为n)元素，试问当利用直接插入法进行排序时，至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)? (1)关键字自小到大有序(key 1 ＜key 2 ＜…＜key n )； (2)关键字自大到小逆序(key 1 ＞key 2 ＞…＞key n )； (3)奇数关键字顺序有序，偶数关键字顺序有序(key 1 ＜key 3 ＜…，key 2 ＜key 4 ＜…)； (4)前半部分元素按关键字顺序有序，后半部分元素按关键字顺序逆序(key 1 ＜key 2 ＜…＜key m ，key m+1 ＞ key m+2 ＜…＜key n ，m为中间位置)。

__________________________________________________________________________________________ 正确答案：(正确答案：本题主要考查直接插入法的算法思想及性能分析。 根据题目所给出的条件，最好情况下的比较次数即为最少比较次数。 (1)在关键字自小到大有序的情况下，插入第i个(2≤i≤n)元素的比较次数为1，因此，总的比较次数为1+1+1+…+1=n一1。 (2)在关键字自大到小有序的情况下，插入第i个(2≤i≤n)元素的比较次数为i，因此，总的比较次数为2+3+4+…+n=[n(n+1)／2]一1=(n一1)(n+2)／2。 (3)在奇数关键字顺序有序和偶数关键字顺序有序的情况下，比较次数最少的情况是所有记录关键字均按升序排列，这时，总的比较次数为n一1。 (4)在前半部分元素按关键字有序，后半部分按关键字逆序的情况下，后半部分元素的关键字均大于前半部分元素的关键字时比较次数最少，此时前半部分的比较次数为m—1，后半部分的比较次数为(n一m—1)(n一m+2)／2，因止匕，总的比较次数为m一1+(n一m一1)(n一m+2)／2=(n一2)(n+8)／8(假设n为偶数，m=n／2)。)

21.对于n个元素组成的线性表进行快速排序时，所需进行的比较次数与这n个元素的初始排序有关。问： (1)当n=7时，在最好情况下需进行多少次比较?请说明理由。 (2)当n=7时，给出一个最好情况的初始排序的实例。 (3)当n=7时，在最坏情况下需进行多少次比较?请说明理由。 (4)当n=7时，给出一个最坏情况的初始排序的实例。

__________________________________________________________________________________________ 正确答案：(正确答案：(1)在最好情况下，假设每次划分能得到两个长度相等的子文件，文件的长度n=2k一1，那么第一遍划分得到两个长度均为[*91]的子文件，第二遍划分得到4个长度均为[*]的子文件，以此类推，总共进行k=log 2 (n+1)遍划分，各子文件的长度均为1，排序完毕。当n=7时，后=3，在最好情况下，第一遍需比较6次，第二遍分别对两个子文件(长度均为3，k=2)进行排序，各需2次，共10次即可。 (2)在最好情况下快速排序的原始序列实例：4，1，3，2，6，5，7。 (3)在最坏情况下，若每次用来划分的记录的关键字具有最大值(或最小值)，那么只能得到左(或右) 子文件，其长度比原长度少1。因此，若原文件中的记录按关键字递减次序排列，而要求排序后按递增次序排列时，快速排序的效率与冒泡排序相同，其时间复杂度为O(n )。所以当n=7时，最坏情况下的比较次数为21次。 (4)在最坏情况下快速排序的初始序列实例：7，6，5，4，3，2，1，要求按递增排序。 提示：此题考查的知识点是快速排序的思想。它的基本思想是：通过一趟排序将要排序的数据分割成的两部分，其中一部分的所有数据都比

2

h-1

通过逐步递推，可以得到：C(n)=(3n

／2)一2。显然，当n＞3时，2n一3＞(3n／2)一2。事实上(3n／2)一2是解决这一问题的比较次数的下

另一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。)

22.关于堆的一些问题： (1)堆的存储表示是顺序的，还是链接的? (2)设有一个最小堆，即堆中任意结点的关键字均大于它的左孩子和右孩子的关键字。其具有最大值的元素可能在什么地方? (3)对n个元素进行初始建堆的过程中，最多做多少次数据比较(不用大O表示法)?

__________________________________________________________________________________________ 正确答案：(正确答案：(1)堆的存储是顺序的。 (2)最大值元素一定是叶子结点，在最下两层上。 (3)在建含有n个元素、深度为h的堆时，其比较次数不超过4n，推导如下： 由于第i层上的结点数至多是2 ，以它为根的二叉树的深度为h一i+1，则调用[*92]次筛选算法时总共进行的关键字比较次数不超过下式之值： n

i-1

提示：此题考查的知识点是堆的基本定义及效率。堆定义为n个关键字序列K 1 ，K 2 ，…，K

当且仅当该序列满足如下性质(简称为堆性质)： (1)k i ≤K 2i 且k i ≤K 2i+1 或 (2)k i ≥K 2i 且k i ≥

K 2i+1 (1≤i≤n)。k i 相当于二叉树的非叶结点，K 2i 则是左孩子，k 2i+1 是右孩子。)

23.若有N个元素已构成一个小根堆，那么如果增加一个元素为K n+1 ，请用文字简要说明如何在log 2 n的时间内将其重新调整为一个堆。

__________________________________________________________________________________________ 正确答案：(正确答案：K 1 ～K n 是堆，在K n+1 加入后，将K 1 ..K n+1 调成堆。设c=n+1， ≤K c ，则调整完成。否则K f 与K c 交换之后，c=f， 根结点，调整结束)

24.冒泡排序方法是把大的元素向上移(气泡的上浮)，也可以把小的元素向下移(气泡的下沉)。请给出上浮和下沉过程交替的冒泡排序算法。

__________________________________________________________________________________________ 正确答案：(正确答案：void BubbleSort2(int a[]，int n){ ／／相邻两趟向相反方向起泡的冒泡排序算法 int change=1；low=0；high=n—1； ／／冒泡的上下界 while(low＜high&&change){ change=0； ／／交换标志 for(i=low；i＜high：i++) ／／从上向下起泡 if(a[i]＞a[i+1]){a[i]←→a[i+1]；change=1；} ／／有交换，修改标志change high一一； ／／修改上界 for(i=high；i＞low；i一一) ／／从下向上起泡 if(a[i]＜a[i+1]{a[i]←→a[i—1]；change=1；} low++； ／／修改下界 } } 提示：此题考查的知识点是双向冒泡算法。题目中“向上移”理解为向序列的右端，而“向下移”按向序列的左端来处理。) 25.有一种简单的排序算法，叫做计数排序(Count sorting)。这种排序算法对一个待排序的表(用数组表示)进行排序，并将排序结果存放到另一个新的表中。必须注意的是，表中所有待排序的关键字互不柜同，计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键字比该记录的关键字小。假设针对某一个记录，统计出的计数值为c，那么，这个记录在新的有序表中的合适的存放位置即为c。 设计实现计数排序的算法。对于有n个记录的表，关键字的比较次数是多少?与简单选择排序相比较，这种方法是否更好?为什么?

__________________________________________________________________________________________ 正确答案：(正确答案：typedef struct{ int key： datatype info }flecType； void countSort(RecType a[]，b[]，int n){ ／／计数排序算法，将a中记录排序放入b中 int i，j，cnt； for(i=0；i 2次。 简单选择排序算法比本算法好。简单选择排序的比较次数是n(n一1)／2，且只用一个交换记录的空间；而这种方法的比较次数是n，且需要另一数组空间。 提示：此题考查的知识点是计数排序思想。因题目要求“针对表中的每个记录，扫描待排序的表一趟”，所以比较次数是n次。若“对任意两个记录之间应该只进行一次比较”，则可把以上算法中的比较语句改为： for(i=0；i)

26.某个待排序的序列是一个可变长度的字符串序列，这些字符串一个接一个地存储于唯一的字符数组中。请改写快速排序算法，对这个字符串序列进行排序。

__________________________________________________________________________________________ 正确答案：(正确答案：int Partition(RecType R[]，int n，int h){ ／／一趟快速排序算法，枢轴记录到位，并返回其所在位置 int i=n，j=h，R[0]=R[i]，x=R[i]．key； while(i＜j){ while(i＜j&&R[j]．key

2

2

若K f

继续比较，直到K f ≤K c ，或f=0，即为

＞=x)j-一； if(i＜j)R[i]=R[j]； while(i＜j&&R[i]．key＜=x)i++； if(i＜j)R[j]=R[i]； }／／while R[i]=R[0]； return； } 提示：此题考查的知识点是快速排序的思想。)

27.设有一个数组中存放了一个无序的关键字序列K 1 ，K 2 ，…，K n 。现要求将K n 放在将元素排序后的正确位置上，试编写实现该功能的算法，要求比较关键字的次数不超过n。

__________________________________________________________________________________________ 正确答案：(正确答案：int Partition(RecType K[]，int m，int n){ ／／交换记录子序列K[1．．n]中的记录，使枢轴记录到位，并返回其所在位置 ／／此时，在它之前(后)的记录均不大(小)于它 int i=m，j=n，K[0]=K[j]，x=K[j]．key； while(i =x)j一一； if(in为枢轴的一趟快速排序。以最后一个关键字为枢轴先从前向后再从后向前快速排序。)