2023年7月20日发(作者：)

计算机专业基础综合历年真题试卷汇编10

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

一、 单项选择题(总题数：25，分数：50.00)

1.单项选择题1-40小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。（分数：2.00）

__________________________________________________________________________________________

解析：

2.下列叙述中，不符合m阶B树定义要求的是_______。

（分数：2.00）

A.根结点最多有m棵子树

B.所有叶结点都在同一层上

C.各结点内关键字均升序或降序排列

D.叶结点之间通过指针链接 √

解析：解析：选项A、B和C都是B-树的特点，而选项D则是B+树的特点。注意区别B-树和B+树各自的特点。

3.在一棵高度为2的5阶B树中，所含关键字的个数最少是_______。

（分数：2.00）

A.5 √

B.7

C.8

D.14

解析：解析：对于5阶B树，根结点只有达到5个关键字时才能产生分裂，成为高度为2的B树，因此高度为2的5阶B树所含关键字的个数最少是5。

4.已知一棵3阶B-树，如下图所示。删除关键字78得到一棵新B-树，其最右叶结点中的关键字是_______。

（分数：2.00）

A.60

B.60，62

C.62，65

D.65 √

解析：解析：对于上图所示的3阶B-树，被删关键字78所在结点在删除前的关键字个数=1=「3／2且其左兄弟结点的关键字个数-2≥「3／2=1，，属于“兄弟够借”的情况，则需把该结点的左兄弟结点中最大的关键字上移到双亲结点中，同时把双亲结点中大于上移关键字的关键字下移到要删除关键字的结点中，这样就达到了新的平衡，如下图所示。（分数：2.00）

A.5

B.6

C.10

D.15 √

解析：解析：关键字数量不变，要求结点数量最多，那么即每个结点中含关键字的数量最少。根据4阶B树的定义，根结点最少含1个关键字，非根结点中最少含「4／2-1=1个关键字，所以每个结点中，

5.在一棵具有15个关键字的4阶B树中，含关键字的结点个数最多是()。 关键字数量最少都为1个，即每个结点都有2个分支，类似与排序二叉树，而15个结点正好可以构造一个4层的4阶B树，使得叶结点全在第四层，符合B树定义，因此选D。

6.为提高散列(HaSh)表的查找效率，可以采取的正确措施是_______。Ⅰ．增大装填(载)因子Ⅱ．设计冲突(碰撞)少的散列函数Ⅲ．处理冲突(碰撞)时避免产生聚集(堆积)现象

（分数：2.00）

A.仅Ⅰ

B.仅Ⅱ

C.仅Ⅰ、Ⅱ

D.仅Ⅱ、Ⅲ √

解析：解析：Hash表的查找效率取决于散列函数、处理冲突的方法和装填因子。显然，冲突的产生概率与装填因子(表中记录数与表长之比)的大小成正比，即装填得越满越容易发生冲突，Ⅰ错误。Ⅱ显然正确。采用合适的处理冲突的方式避免产生聚集现象，也将提高查找效率，例如用拉链法解决冲突时就不存在聚集现象，用线性探测法解决冲突时易引起聚集现象，Ⅲ正确。

7.用哈希(散列)方法处理冲突(碰撞)时可能出现堆积(聚集)现象，下列选项中，会受堆积现象直接影响的是_______。

（分数：2.00）

A.存储效率

B.散列函数

C.装填(装载)因子

D.平均查找长度 √

解析：解析：产生堆积现象，即产生了冲突，它对存储效率、散列函数和装填因子均不会有影响，而平均查找长度会因为堆积现象而增大，选D。

8.已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”。采用KMP算法进行匹配，第一次出现“失配”(s[i]≠t[j])时，i-j=5，则下次开始匹配时，i和j的值分别是_______。

（分数：2.00）

A.i=1，j=0

B.i=5，j=0

C.i=5，j=2 √

D.i=6，j=2

解析：解析：由题中“失配s[i]≠t[j]时，i=j=5”，可知题中的主串和模式串的位序都是从0开始的(要注意灵活应变)。按照next数组生成算法，对于t有：O开始)。从而最后结果应为：i=5(i保持不变)，j=2。

9.若数据元素序列11，12，13，7，8，9，23，4，5是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是_______。

（分数：2.00）

A.冒泡排序

B.插入排序 √

C.选择排序

D.二路归并排序

解析：解析：解答本题需要对各种排序算法的特点极为清楚。对于冒泡排序和选择排序，每一趟都能确定一个元素的最终位置，而题目中，前2个元素和后2个元素均不是最小或最大的2个元素并按序排列。 选项D中的2路归荆非序，第一趟排序结束都可以得到若干个有序子序列，而此时的序列中并没有两两元素有序排列。插入排序在每趟排序后能确定前面的若干元素是有序的，而此时第二趟排序后，序列的前三个元素是有序的，符合其特征。

10.对一待排序序列分别进行折半插入排序和直接插入排序，两者之间可能的不同之处是_______。

（分数：2.00）

A.排序的总趟数

依据KMP算法“当失配时，i不变，j回退到next[j]的位置并重新比较”，当失配s[i]≠t[j]时，i=j=5，由上表不难得出next[j]=next[5]=2(位序从 B.元素的移动次数

C.使用辅助空间的数量

D.元素之间的比较次数 √

解析：解析：折半插入排序与直接插入排序都是将待插入元素插入前面的有序子表，区别是：确定当前记录在前面有序子表中的位置时，直接插入排序是采用顺序查找法，而折半插入排序是采用折半查找法。排序的总趟数取决于元素个数n，两者都是n-1趟。元素的移动次数都取决于初试序列，两者相同。使用辅助空间的数量也都是O(1)。折半插入排序的比较次数与序列初态无关，为O(nlog

2 n)；而直接插入排序的比较次数与序列初态有关，为O(n)～O(n )。

11.用希尔排序方法对一个数据序列进行排序时，若第1趟排序结果为9，1，4，13，7，8，20，23，15，则该趟排序采用的增量(间隔)可能是_______。

（分数：2.00）

A.2

B.3 √

C.4

D.5

解析：解析：首先，第二个元素为1，是整个序列中的最小元素，所以可知该希尔排序为从小到大排序。然后考虑增量问题，若增量为2，第1+2个元素4明显比第1个元素9要大，A排除；若增量为3，第i、i+3、i+6个元素都为有序序列(i=1，2，3)，符合希尔排序的定义；若增量为4，第1个元素9比第1+4个元素7要大，C排除；若增量为5，第1个元素9比第1+5个元素8要大，D排除，选B。

12.希尔排序的组内排序采用的是_______。

（分数：2.00）

A.直接插入排序 √

B.折半插入排序

C.快速排序

D.归并排序

解析：解析：希尔排序的思想是：先将待排元素序列分割成若干个子序列(由相隔某个“增量”的元素组成)，分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序(增量足够小)时，再对全体元素进行一次直接插入排序。

13.对一组数据(2，12，16，88，5，10)进行排序，若前三趟排序结果如下：第一趟排序结果：2，12，16，5，10，88第二趟排序结果：2，12，5，10，16，88第三趟排序结果：2，5，10，12，16，88则采用的排序方法可能是_______。

（分数：2.00）

A.冒泡排序 √

B.希尔排序

C.归并排序

D.基数排序

解析：解析：题中所给的三趟排序过程中，每一趟排序是从前往后依次比较，使最大值“沉底”，符合冒泡排序的特点。 看第一趟可知仅有88被移到最后。 ．如果是希尔排序，则12，88，10应变为10，12，88。因此排除希尔排序。 ．如果是归并排序，则长度为2的子序列是有序的。因此可排除归并排序。 ．如果是基数排序，则16，5，10应变为10，5，16。因此排除基数排序。 提示：对于此类题，先看备选项的排序算法有什么特征，再看题目中的排序过程是否符合这一特征，从而得出答案。一般先从选项中的简单排序方法(插入排序、起泡排序、选择排序)开始判断，若简单排序方法不符合，再判断排序方法(希尔排序、快速排序、堆排序、归并排序)。

14.采用递归方式对顺序表进行快速排序。下列关于递归次数的叙述中，正确的是_______。

（分数：2.00）

A.递归次数与初始数据的排列次序无关

B.每次划分后，先处理较长的分区可以减少递归次数

C.每次划分后，先处理较短的分区可以减少递归次数

D.递归次数与每次划分后得到的分区的处理顺序无关 √

2解析：解析：快递排序的递归次数与元素的初始排列有关。如果每一次划分后分区比较平衡，则递归次数少；如果划分后分区不平衡，则递归次数多。但快速排序的递归次数与分区处理顺序无关，即先处理较长的分区或先处理较短的分区都不影响递归次数。 此外，可以形象地把快速排序的递归调用过程用一个二叉树描述，先处理较长或较短分区，可以想象为交换某一递归结点处的左右子树，这并不会影响树中的分支数。

15.为实现快速排序算法，待排序序列宜采用的存储方式是_______。

（分数：2.00）

A.顺序存储 √

B.散列存储

C.链式存储

D.索引存储

解析：解析：对绝大部分内部排序而言，只适用于顺序存储结构。快速排序在排序的过程中，既要从后向前查找，也要从前向后查找，因此宜采用顺序存储。

16.下列选项中，不可能是快速排序第2趟排序结果的是()。

（分数：2.00）

A.2，3，5，4，6，7，9

B.2，7，5，6，4，3，9

C.3，2，5，4，7，6，9 √

D.4，2，3，5，7，6，9

解析：解析：快排的阶段性排序结果的特点是，第i趟完成时，会有i个以上的数出现在它最终将要出现的位置，即它左边的数都比它小，它右边的数都比它大。题目问第二趟排序的结果，即要找不存在2个这样的数的选项。A选项中2、3、6、7、9均符合，所以A排除；B选项中，2、9均符合，所以B排除；D选项中5、9均符合，所以D选项排除；最后看C选项，只有9一个数符合，所以C不可能是快速排序第二趟的结果。

17.已知关键字序列5，8，12，19，28，20，15，22是小根堆(最小堆)，插入关键字3，调整后得到的小根堆是_______。

（分数：2.00）

A.3，5，12，8，28，20，15，22，19 √

B.3，5，12，19，20，15，22，8，28

C.3，8，12，5，20，15，22，28，19

D.3，12，5，8，28，20，15，22，19

解析：解析：根据关键字序列得到的小顶堆的二叉树形式如下图所示。小顶堆序列为3，5，12，8，28，20，15，22，19。

18.己知序列25，13，10，12，9是大根堆，在序列尾部插入新元素18，将其再调整为大根堆，调整过程中元素之间进行的比较次数是_______。

（分数：2.00）

A.1

B.2 √

C.4

D.5

解析：解析：插入18后，首先18与10比较，交换位置，再18与25比较，不交换位置。共比较了2次，调整的过程如下图所示。比较次数是_______。

（分数：2.00）

A.1

插入关键字3时，先将其放在小顶堆的末端，如图(2)所示。再将该关键字向上进行调整，得到的结果如图(3)所示。所以，调整后的19.已知小根堆为8，15，10，21，34，16，12，删除关键字8之后需重建堆，在此过程中，关键字之间的 B.2

C.3 √

D.4

解析：解析：删除8后，将12移动到堆顶，第一次是15和10比较，第二次是10和12比较并交换，第三次还需比较12和16，故比较次数为3次。关键字序列是_______。

（分数：2.00）

A.007，110，119，114，911，120，122 √

B.007，110，119，114，911，122，120

C.007，110，911，114，119，120，122

D.110，120，911，122，114，007，119

解析：解析：基数排序的第1趟排序是按照个位数字的大小来排序的，第2趟排序是按照十位数字的大小进行排序的，排序的过程如下图所示。

20.对给定的关键字序列110，119，007，911，114，120，122进行基数排序，则第2趟分配收集后得到的21.在内部排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中，每一趟排序结束都至少能够确定一个元素最终位置的方法是_______。Ⅰ．简单选择排序Ⅱ．希尔排序Ⅲ．快速排序Ⅳ．堆排序V．二路归并排序

（分数：2.00）

A.仅Ⅰ、Ⅲ、Ⅳ √

B.仅Ⅰ、Ⅲ、Ⅴ

C.仅Ⅱ、Ⅲ、Ⅳ

D.仅Ⅲ、Ⅳ、Ⅴ

解析：解析：对于Ⅰ，简单选择排序每次选择未排序列中的最小元素放入其最终位置。对于Ⅱ，希尔排序每次是对划分的子表进行排序，得到局部有序的结果，所以不能保证每一趟排序结束都能确定一个元素的最终位置。对于Ⅲ，快速排序每一趟排序结束后都将枢轴元素放到最终位置。对于Ⅳ，堆排序属于选择排序，每次都将大根堆的根结点与表尾结点交换，确定其最终位置。对于Ⅴ，二路归并排序每趟对子表进行两两归并从而得到若干个局部有序的结果，但无法确定最终位置。

22.下列排序算法中，元素的移动次数与关键字的初始排列次序无关的是_______。

（分数：2.00）

A.直捌蠡入排序

B.起泡排序

C.基数排序 √

D.快速排序

解析：解析：基数排序的元素移动次数与关键字的初始排列次序无关，而其他三种排序都是与关键字的初始排列明显相关的。

23.已知三叉树T中6个叶结点的权分别是2，3，4，5，6，7，T的带权(外部)路径长度最小是_______。

（分数：2.00）

A.27

B.46 √

C.54

D.56

解析：解析：将哈夫曼树的思想推广到三叉树的情形。为了构成严格的三叉树，需添加权为0的虚叶结点，对于严格的三叉树(n

0 -1)％(3-1)=u=1≠0，需要添加m-u-1=3-1-1个叶结点，说明7个叶结点刚好可以构成一个严格的三叉树。按照哈夫曼树的原则，权为0的叶结点应离树根最远，构造最小带权生成树的过程如下： 最小的带权路径长度为(2+3)×3+(4+5)×2+(+7)×1=46。 24.冯．诺依曼计算机中指令和数据均以二进制形式存放在存储器中，CPU区分它们的依据是_______。

（分数：2.00）

A.指令操作码的译码结果

B.指令和数据的寻址方式

C.指令周期的不同阶段 √

D.指令和数据所在的存储单元

解析：解析：虽然指令和数据都是以二进制形式存放在存储器中，但CPU可以根据指令周期的不同阶段来区分是指令还是数据，通常在取指阶段取出的是指令，在执行阶段取出的是数据。本题容易误选A，需要清楚的是，CPU只有在确定取出的是指令之后，才会将其操作码送去译码，因此，不可能依据译码的结果来区分指令和数据。

25.计算机硬件能够直接执行的是_______。Ⅰ．机器语言程序Ⅱ．汇编语言程序Ⅲ．硬件描述语言程序

（分数：2.00）

A.仅Ⅰ √

B.仅Ⅰ、Ⅱ

C.仅Ⅰ、Ⅲ

D.Ⅰ、Ⅱ、Ⅲ

解析：解析：硬件能直接执行的只能是机器语言(二进制编码)，汇编语言是为增强机器语言的可读性和记忆性的语言，经过汇编后才能被执行。

二、 综合应用题(总题数：4，分数：16.00)

26.综合应用题41-47小题。（分数：4.00）

__________________________________________________________________________________________

解析：

设包含4个数据元素的集合s={“do”，“for”，“repeat”，“while”}，各元素的查找概率依次为：p1=0．35，p2=0．15，p3=0．15，p4=0．35。将S保存在一个长度为4的顺序表中，采用折半查找法，查找成功时的平均查找长度为2．2。请回答：（分数：4.00）

(1).若采用顺序存储结构保存S，且要求平均查找长度更短，则元素应如何排列?应使用何种查找方法?查找成功时的平均查找长度是多少?（分数：2.00）

__________________________________________________________________________________________

正确答案：(正确答案：折半查找要求元素有序顺序存储，若各个元素的查找概率不同，折半查找的性能不一定优于顺序查找。采用顺序查找时，元素按其查找概率的降序排列时查找长度最小。 采用顺序存储结构，数据元素按其查找概率降序排列。采用顺序查找方法。 查找成功时的平均查找长度=0．35×1+0．35×2+0．15×3+0．15×4=2．1。 此时，显然查找长度比折半查找的更短。)

解析：

(2).若采用链式存储结构保存S，且要求平均查找长度更短，则元素应如何排列?应使用何种查找方法?查找成功时的平均查找长度是多少?（分数：2.00）

__________________________________________________________________________________________

正确答案：(正确答案：采用链式存储结构时，只能采用顺序查找，其性能和顺序表一样，类似于上题。数据元素按其查找概率降序排列，构成单链表。采用顺序查找方法。 查找成功时的平均查找长度=0．35×1+0．35×2+0．15×3+0．15×4=2．1。)

解析：

将关键字序列(7，8，30，11，18，9，14)散列存储到散列表中，散列表的存储空间是一个下标从0开始的一维数组，散列函数为：H(key)=(key×3)MOD7，处理冲突采用线性探测再散列法，要求装填(载)因子为0．7。（分数：4.00）

(1).请画出所构造的散列表。（分数：2.00）

__________________________________________________________________________________________

正确答案：(正确答案：由装载因子为0．7，数据总数为7，可得一维数组大小为7／0．7=10，数组下标为0～9．所构造的散列函数值见下表。)

解析：

采用线性探测再散列法处理冲突，所构造的散列表见下表。(2).分别计算等概率情况下查找成功和查找不成功的平均查找长度。（分数：2.00）

__________________________________________________________________________________________

正确答案：(正确答案：查找成功时，是根据每个元素查找次数来计算平均长度的，在等概率的情况下，各关键字的查找次数见下表。 故，ASL

成功 =查找次数／元素个数=(1+2+1+1+1+3+3)／7=12／7。 这里要特别防止惯性思维。查找失败时，是根据查找失败位置计算平均次数，根据散列函数MOD7，初始只可能在0～6的位置。等概率情况下，查找0～6位置查找失败的查找次数见下表。

次数／散列后的地址个数=(3+2+1+2+1+5+4)／7=18／7。)

解析：解析：考查散列表的构造和散列查找的性能分析。

设有6个有序表A、B、C、D、E、F，分别含有10、35、40、50、60和200个数据元素，各表中元素按升序排列。要求通过5次两两合并，将6个表最终合并成1个升序表，并在最坏情况下比较的总次数达到最小。请回答下列问题：（分数：4.00）

(1).给出完整的合并过程，并求出最坏情况下比较的总次数。（分数：2.00）

__________________________________________________________________________________________

正确答案：(正确答案：对于长度分别为m，n的两个有序表的合并，最坏情况下是一直比较到两个表尾元素，比较次数为m+n-1次。故，最坏情况的比较次数依赖于表长，为了缩短总的比较次数，根据哈夫曼树(最佳归并树)思想的启发，可采用如图所示的合并顺序。根据上图中的哈夫曼树，6个序列的合并过程故，ASL

不成功 =查找为： 第1次合并：表A与表B合并，生成含有45个元素的表AB； 第2次合并：表AB与表C合并，生成含有85个元素的表ABC； 第3次合并：表D与表E合并，生成含有110个元素的表DE； 第4次合并：表ABC与表DE合并，生成含有195个元素的表ABCDE； 第5次合并：表ABCDE与表F合并，生成含有395个元素的最终表。 由上述分析可知，最坏情况下的比较次数为：第1次合并，最多比较次数=10+35-1=44；第2次合并，最多比较次数=45+40-1=84；第3次合并，最多比较次数=50+60-1=109；第4次合并，最多比较次数i=85+110-1=194；第5次合并，最多比较次数=195+200-1=394。 故，比较的总次数最多为：44+84+109+194+394=825。)

解析：

(2).根据你的合并过程，描述N(N≥2)个不等长升序表的合并策略，并说明理由。（分数：2.00）

__________________________________________________________________________________________

正确答案：(正确答案：各表的合并策略是：在对多个有序表进行两两合并时，若表长不同，则最坏情况下总的比较次数依赖于表的合并次序。可以借用哈夫曼树的构造思想，依次选择最短的两个表进行合并，可以获得最坏情况下最佳的合并效率。)

解析：解析：考查二路归并和哈夫曼树以及最佳归并树。 本题同时对多个知识点进行了综合考查。对有序表进行两两合并考查了归并排序中的Merge()函数；对合并过程的设计考查了哈夫曼树和最佳归并树。外部排序属于大纲新增考点。