1、计算机专业基础综合历年真题试卷汇编 4 及答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 下列叙述中，不符合 m 阶 B 树定义要求的是_。（A）根结点最多有 m 棵子树（B）所有叶结点都在同一层上（C）各结点内关键字均升序或降序排列（D）叶结点之间通过指针链接2 在一棵高度为 2 的 5 阶 B 树中，所含关键字的个数最少是_。（A）5（B） 7（C） 8（D）143 已知一棵 3 阶 B-树，如下图所示。删除关键字 78 得到一棵新 B-树，其最右叶结点中的关键字是_。（A）60（B） 60，62（C） 6
2、2，65（D）654 在一棵具有 15 个关键字的 4 阶 B 树中，含关键字的结点个数最多是()。（A）5（B） 6（C） 10（D）155 为提高散列(HaSh) 表的查找效率，可以采取的正确措施是_。增大装填(载) 因子设计冲突(碰撞) 少的散列函数处理冲突(碰撞) 时避免产生聚集(堆积) 现象（A）仅（B）仅 （C）仅 、（D）仅、6 用哈希(散列) 方法处理冲突(碰撞) 时可能出现堆积(聚集)现象，下列选项中，会受堆积现象直接影响的是_。（A）存储效率（B）散列函数（C）装填 (装载)因子（D）平均查找长度7 已知字符串 S 为“abaabaabacacaabaabcc”，模式串 t
3、 为“abaabc”。采用 KMP 算法进行匹配，第一次出现“ 失配 ”(sitj)时，i-j=5，则下次开始匹配时，i 和 j 的值分别是_。（A）i=1 ，j=0（B） i=5，j=0（C） i=5，j=2（D）i=6 ，j=28 若数据元素序列 11，12，13，7，8，9，23，4，5 是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是_。（A）冒泡排序（B）插入排序（C）选择排序（D）二路归并排序9 对一待排序序列分别进行折半插入排序和直接插入排序，两者之间可能的不同之处是_。（A）排序的总趟数（B）元素的移动次数（C）使用辅助空间的数量（D）元素之间的比较次数10
4、用希尔排序方法对一个数据序列进行排序时，若第 1 趟排序结果为9，1，4，13，7，8，20，23，15，则该趟排序采用的增量(间隔)可能是_。（A）2（B） 3（C） 4（D）511 希尔排序的组内排序采用的是_。（A）直接插入排序（B）折半插入排序（C）快速排序（D）归并排序12 对一组数据(2，12，16，88，5，10)进行排序，若前三趟排序结果如下：第一趟排序结果：2，12，16，5，10，88第二趟排序结果：2，12，5，10，16，88第三趟排序结果：2，5，10，12，16，88则采用的排序方法可能是_。（A）冒泡排序（B）希尔排序（C）归并排序（D）基数排序13 采用递归方式
5、对顺序表进行快速排序。下列关于递归次数的叙述中，正确的是_。（A）递归次数与初始数据的排列次序无关（B）每次划分后，先处理较长的分区可以减少递归次数（C）每次划分后，先处理较短的分区可以减少递归次数（D）递归次数与每次划分后得到的分区的处理顺序无关14 为实现快速排序算法，待排序序列宜采用的存储方式是_。（A）顺序存储（B）散列存储（C）链式存储（D）索引存储15 下列选项中，不可能是快速排序第 2 趟排序结果的是()。（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，916 已知关键字序列 5，8，12，19，2
6、8，20，15，22 是小根堆(最小堆)，插入关键字 3，调整后得到的小根堆是_。（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，1917 己知序列 25，13，10，12，9 是大根堆，在序列尾部插入新元素 18，将其再调整为大根堆，调整过程中元素之间进行的比较次数是_。（A）1（B） 2（C） 4（D）518 已知小根堆为 8，15，10，21，34，16，12，删除关键字 8 之后需重建堆，在此过程中，关键字之间的比较次数是_。（
7、A）1（B） 2（C） 3（D）419 对给定的关键字序列 110，119，007，911，114，120，122 进行基数排序，则第 2 趟分配收集后得到的关键字序列是_。（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，11920 在内部排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中，每一趟排序结束都至少能够确定一个元素最终位置的方法是_。简单选择排序希尔排序快速排序堆排
8、序 V二路归并排序（A）仅、（B）仅 、（C）仅 、（D）仅、21 下列排序算法中，元素的移动次数与关键字的初始排列次序无关的是_。（A）直捌蠡入排序（B）起泡排序（C）基数排序（D）快速排序22 已知三叉树 T 中 6 个叶结点的权分别是 2，3， 4，5，6，7，T 的带权(外部)路径长度最小是_。（A）27（B） 46（C） 54（D）5623 冯诺依曼计算机中指令和数据均以二进制形式存放在存储器中，CPU 区分它们的依据是_。（A）指令操作码的译码结果（B）指令和数据的寻址方式（C）指令周期的不同阶段（D）指令和数据所在的存储单元24 计算机硬件能够直接执行的是_。机器语言程序汇编语言
9、程序硬件描述语言程序（A）仅（B）仅 、（C）仅 、（D）、二、综合应用题41-47 小题，共 70 分。24 设包含 4 个数据元素的集合 s=“do”，“for” ，“repeat”，“while” ，各元素的查找概率依次为：p1=035，p2=0 15，p3=015， p4=035。将 S 保存在一个长度为 4 的顺序表中，采用折半查找法，查找成功时的平均查找长度为 22。请回答：25 若采用顺序存储结构保存 S，且要求平均查找长度更短，则元素应如何排列?应使用何种查找方法? 查找成功时的平均查找长度是多少?26 若采用链式存储结构保存 S，且要求平均查找长度更短，则元素应如何排列?应使
10、用何种查找方法? 查找成功时的平均查找长度是多少?26 将关键字序列(7，8，30，11，18，9，14)散列存储到散列表中，散列表的存储空间是一个下标从 0 开始的一维数组，散列函数为：H(key)=(key3)MOD7，处理冲突采用线性探测再散列法，要求装填(载)因子为 07。27 请画出所构造的散列表。28 分别计算等概率情况下查找成功和查找不成功的平均查找长度。28 设有 6 个有序表 A、B、C、D、E、F，分别含有 10、35、40、50、60 和 200个数据元素，各表中元素按升序排列。要求通过 5 次两两合并，将 6 个表最终合并成 1 个升序表，并在最坏情况下比较的总次数达到
11、最小。请回答下列问题：29 给出完整的合并过程，并求出最坏情况下比较的总次数。30 根据你的合并过程，描述 N(N2)个不等长升序表的合并策略，并说明理由。计算机专业基础综合历年真题试卷汇编 4 答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 【正确答案】 D【试题解析】 选项 A、B 和 C 都是 B-树的特点，而选项 D 则是 B+树的特点。注意区别 B-树和 B+树各自的特点。【知识模块】 数据结构2 【正确答案】 A【试题解析】 对于 5 阶 B 树，根结点只有达到 5 个关键字时才能产生分裂，成为高度
12、为 2 的 B 树，因此高度为 2 的 5 阶 B 树所含关键字的个数最少是 5。【知识模块】 数据结构3 【正确答案】 D【试题解析】 对于上图所示的 3 阶 B-树，被删关键字 78 所在结点在删除前的关键字个数=1= 32 =1，且其左兄弟结点的关键字个数-232 ，属于“兄弟够借”的情况，则需把该结点的左兄弟结点中最大的关键字上移到双亲结点中，同时把双亲结点中大于上移关键字的关键字下移到要删除关键字的结点中，这样就达到了新的平衡，如下图所示。【知识模块】 数据结构4 【正确答案】 D【试题解析】 关键字数量不变，要求结点数量最多，那么即每个结点中含关键字的数量最少。根据 4 阶 B 树
13、的定义，根结点最少含 1 个关键字，非根结点中最少含42 -1=1 个关键字，所以每个结点中，关键字数量最少都为 1 个，即每个结点都有 2 个分支，类似与排序二叉树，而 15 个结点正好可以构造一个 4 层的 4 阶B 树，使得叶结点全在第四层，符合 B 树定义，因此选 D。【知识模块】 数据结构5 【正确答案】 D【试题解析】 Hash 表的查找效率取决于散列函数、处理冲突的方法和装填因子。显然，冲突的产生概率与装填因子(表中记录数与表长之比)的大小成正比，即装填得越满越容易发生冲突，错误。显然正确。采用合适的处理冲突的方式避免产生聚集现象，也将提高查找效率，例如用拉链法解决冲突时就不存在
14、聚集现象，用线性探测法解决冲突时易引起聚集现象，正确。【知识模块】 数据结构6 【正确答案】 D【试题解析】 产生堆积现象，即产生了冲突，它对存储效率、散列函数和装填因子均不会有影响，而平均查找长度会因为堆积现象而增大，选 D。【知识模块】 数据结构7 【正确答案】 C【试题解析】 由题中“失配 sitj时，i=j=5” ，可知题中的主串和模式串的位序都是从 0 开始的(要注意灵活应变)。按照 next 数组生成算法，对于 t 有：依据 KMP 算法“当失配时，i 不变，j 回退到 nextj的位置并重新比较 ”，当失配 sitj时，i=j=5，由上表不难得出 nextj=next5=2(位序
15、从 O 开始)。从而最后结果应为：i=5(i 保持不变)，j=2。【知识模块】 数据结构8 【正确答案】 B【试题解析】 解答本题需要对各种排序算法的特点极为清楚。对于冒泡排序和选择排序，每一趟都能确定一个元素的最终位置，而题目中，前 2 个元素和后 2 个元素均不是最小或最大的 2 个元素并按序排列。选项 D 中的 2 路归荆非序，第一趟排序结束都可以得到若干个有序子序列，而此时的序列中并没有两两元素有序排列。插入排序在每趟排序后能确定前面的若干元素是有序的，而此时第二趟排序后，序列的前三个元素是有序的，符合其特征。【知识模块】 数据结构9 【正确答案】 D【试题解析】 折半插入排序与直接插
16、入排序都是将待插入元素插入前面的有序子表，区别是：确定当前记录在前面有序子表中的位置时，直接插入排序是采用顺序查找法，而折半插入排序是采用折半查找法。排序的总趟数取决于元素个数 n，两者都是 n-1 趟。元素的移动次数都取决于初试序列，两者相同。使用辅助空间的数量也都是 O(1)。折半插入排序的比较次数与序列初态无关，为 O(nlog2n)；而直接插入排序的比较次数与序列初态有关，为 O(n)O(n 2)。【知识模块】 数据结构10 【正确答案】 B【试题解析】 首先，第二个元素为 1，是整个序列中的最小元素，所以可知该希尔排序为从小到大排序。然后考虑增量问题，若增量为 2，第 1+2 个元素
17、 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。【知识模块】 数据结构11 【正确答案】 A【试题解析】 希尔排序的思想是：先将待排元素序列分割成若干个子序列(由相隔某个“增量”的元素组成)，分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序(增量足够小)时，再对全体元素进行一次直接插入排序。【知识模块】 数据结构12
18、【正确答案】 A【试题解析】 题中所给的三趟排序过程中，每一趟排序是从前往后依次比较，使最大值“沉底”，符合冒泡排序的特点。看第一趟可知仅有 88 被移到最后。如果是希尔排序，则 12，88，10 应变为 10，12，88。因此排除希尔排序。如果是归并排序，则长度为 2 的子序列是有序的。因此可排除归并排序。如果是基数排序，则 16，5，10 应变为 10，5，16。因此排除基数排序。提示：对于此类题，先看备选项的排序算法有什么特征，再看题目中的排序过程是否符合这一特征，从而得出答案。一般先从选项中的简单排序方法(插入排序、起泡排序、选择排序)开始判断，若简单排序方法不符合，再判断排序方法(希
19、尔排序、快速排序、堆排序、归并排序)。【知识模块】 数据结构13 【正确答案】 D【试题解析】 快递排序的递归次数与元素的初始排列有关。如果每一次划分后分区比较平衡，则递归次数少；如果划分后分区不平衡，则递归次数多。但快速排序的递归次数与分区处理顺序无关，即先处理较长的分区或先处理较短的分区都不影响递归次数。此外，可以形象地把快速排序的递归调用过程用一个二叉树描述，先处理较长或较短分区，可以想象为交换某一递归结点处的左右子树，这并不会影响树中的分支数。【知识模块】 数据结构14 【正确答案】 A【试题解析】 对绝大部分内部排序而言，只适用于顺序存储结构。快速排序在排序的过程中，既要从后向前查找
20、，也要从前向后查找，因此宜采用顺序存储。【知识模块】 数据结构15 【正确答案】 C【试题解析】 快排的阶段性排序结果的特点是，第 i 趟完成时，会有 i 个以上的数出现在它最终将要出现的位置，即它左边的数都比它小，它右边的数都比它大。题目问第二趟排序的结果，即要找不存在 2 个这样的数的选项。A 选项中2、3、6、7、9 均符合，所以 A 排除；B 选项中， 2、9 均符合，所以 B 排除；D选项中 5、9 均符合，所以 D 选项排除；最后看 C 选项，只有 9 一个数符合，所以C 不可能是快速排序第二趟的结果。【知识模块】 数据结构16 【正确答案】 A【试题解析】 根据关键字序列得到的小
21、顶堆的二叉树形式如下图所示。插入关键字 3 时，先将其放在小顶堆的末端，如图(2)所示。再将该关键字向上进行调整，得到的结果如图(3)所示。所以，调整后的小顶堆序列为3，5，12，8，28，20，15，22，19。【知识模块】 数据结构17 【正确答案】 B【试题解析】 插入 18 后，首先 18 与 10 比较，交换位置，再 18 与 25 比较，不交换位置。共比较了 2 次，调整的过程如下图所示。【知识模块】 数据结构18 【正确答案】 C【试题解析】 删除 8 后，将 12 移动到堆顶，第一次是 15 和 10 比较，第二次是 10和 12 比较并交换，第三次还需比较 12 和 16，故
22、比较次数为 3 次。【知识模块】 数据结构19 【正确答案】 A【试题解析】 基数排序的第 1 趟排序是按照个位数字的大小来排序的，第 2 趟排序是按照十位数字的大小进行排序的，排序的过程如下图所示。【知识模块】 数据结构20 【正确答案】 A【试题解析】 对于，简单选择排序每次选择未排序列中的最小元素放入其最终位置。对于，希尔排序每次是对划分的子表进行排序，得到局部有序的结果，所以不能保证每一趟排序结束都能确定一个元素的最终位置。对于，快速排序每一趟排序结束后都将枢轴元素放到最终位置。对于，堆排序属于选择排序，每次都将大根堆的根结点与表尾结点交换，确定其最终位置。对于，二路归并排序每趟对子表
23、进行两两归并从而得到若干个局部有序的结果，但无法确定最终位置。【知识模块】 数据结构21 【正确答案】 C【试题解析】 基数排序的元素移动次数与关键字的初始排列次序无关，而其他三种排序都是与关键字的初始排列明显相关的。【知识模块】 数据结构22 【正确答案】 B【试题解析】 将哈夫曼树的思想推广到三叉树的情形。为了构成严格的三叉树，需添加权为 0 的虚叶结点，对于严格的三叉树(n 0-1)(3-1)=u=10，需要添加 m-u-1=3-1-1 个叶结点，说明 7 个叶结点刚好可以构成一个严格的三叉树。按照哈夫曼树的原则，权为 0 的叶结点应离树根最远，构造最小带权生成树的过程如下：最小的带权路
24、径长度为(2+3)3+(4+5)2+(+7)1=46。【知识模块】 数据结构23 【正确答案】 C【试题解析】 虽然指令和数据都是以二进制形式存放在存储器中，但 CPU 可以根据指令周期的不同阶段来区分是指令还是数据，通常在取指阶段取出的是指令，在执行阶段取出的是数据。本题容易误选 A，需要清楚的是， CPU 只有在确定取出的是指令之后，才会将其操作码送去译码，因此，不可能依据译码的结果来区分指令和数据。【知识模块】 计算机组成原理24 【正确答案】 A【试题解析】 硬件能直接执行的只能是机器语言(二进制编码)，汇编语言是为增强机器语言的可读性和记忆性的语言，经过汇编后才能被执行。【知识模块】
25、 计算机组成原理二、综合应用题41-47 小题，共 70 分。【知识模块】 数据结构25 【正确答案】 折半查找要求元素有序顺序存储，若各个元素的查找概率不同，折半查找的性能不一定优于顺序查找。采用顺序查找时，元素按其查找概率的降序排列时查找长度最小。采用顺序存储结构，数据元素按其查找概率降序排列。采用顺序查找方法。查找成功时的平均查找长度=0351+0 352+0153+0 154=21。此时，显然查找长度比折半查找的更短。【知识模块】 数据结构26 【正确答案】 采用链式存储结构时，只能采用顺序查找，其性能和顺序表一样，类似于上题。数据元素按其查找概率降序排列，构成单链表。采用顺序查找方法
26、。查找成功时的平均查找长度=0351+0 352+0153+0 154=21。【知识模块】 数据结构【知识模块】 数据结构27 【正确答案】 由装载因子为 07，数据总数为 7，可得一维数组大小为707=10 ，数组下标为 09所构造的散列函数值见下表。采用线性探测再散列法处理冲突，所构造的散列表见下表。【知识模块】 数据结构28 【正确答案】 查找成功时，是根据每个元素查找次数来计算平均长度的，在等概率的情况下，各关键字的查找次数见下表。故，ASL 成功 =查找次数元素个数=(1+2+1+1+1+3+3)7=127。这里要特别防止惯性思维。查找失败时，是根据查找失败位置计算平均次数，根据散列
27、函数MOD7，初始只可能在 06 的位置。等概率情况下，查找 06 位置查找失败的查找次数见下表。故，ASL 不成功 =查找次数散列后的地址个数=(3+2+1+2+1+5+4)7=187。【试题解析】 考查散列表的构造和散列查找的性能分析。【知识模块】 数据结构【知识模块】 数据结构29 【正确答案】 对于长度分别为 m，n 的两个有序表的合并，最坏情况下是一直比较到两个表尾元素，比较次数为 m+n-1 次。故，最坏情况的比较次数依赖于表长，为了缩短总的比较次数，根据哈夫曼树(最佳归并树)思想的启发，可采用如图所示的合并顺序。 根据上图中的哈夫曼树，6 个序列的合并过程为：第 1 次合并：表
28、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 次合并，最多比
29、较次数 i=85+110-1=194；第 5 次合并，最多比较次数=195+200-1=394 。故，比较的总次数最多为：44+84+109+194+394=825。【知识模块】 数据结构30 【正确答案】 各表的合并策略是：在对多个有序表进行两两合并时，若表长不同，则最坏情况下总的比较次数依赖于表的合并次序。可以借用哈夫曼树的构造思想，依次选择最短的两个表进行合并，可以获得最坏情况下最佳的合并效率。【试题解析】 考查二路归并和哈夫曼树以及最佳归并树。本题同时对多个知识点进行了综合考查。对有序表进行两两合并考查了归并排序中的 Merge()函数；对合并过程的设计考查了哈夫曼树和最佳归并树。外部排序属于大纲新增考点。【知识模块】 数据结构
