1、计算机专业基础综合数据结构（集合）历年真题试卷汇编 4及答案解析(总分：70.00，做题时间：90 分钟)一、单项选择题(总题数：20，分数：40.00)1.下列二叉排序树中，满足平衡二叉树定义的是( )。【2009 年全国试题 4(2分)】（分数：2.00）A.B.C.D.2.下列叙述中，不符合 m阶 B树定义要求的是( )。【2009 年全国试题 8(2分)】（分数：2.00）A.根结点最多有 m棵子树B.所有叶结点都在同一层上C.各结点内关键字均升序或降序排列D.叶结点之间通过指针链接3.在下图所示的平衡二叉树中，插入关键字 48舌得到一棵新平衡二叉树。在新平衡二叉树中，关键字37所在结
2、点的左、右子结点中保存的关键字分别是( )。【2010 年全国试题 4(2分)】 （分数：2.00）A.13、48B.24、48C.24、53D.24、904.已知一个长度为 16的顺序表 L，其元素按关键字有序排列。若采用折半查找法查找一个 L中不存在的元素，则关键字的比较次数最多是( )。 2010 年全国试题 9(2分)】（分数：2.00）A.4B.5C.6D.75.对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是( )。【2011 年全国试题 7(2分)】（分数：2.00）A.95，22，91，24，94，71B.92，20，91，34，88，35C.21，89，77，
3、29，36，38D.12，25，71，68，33，246.为提高散列(Hash)表的查找效率，可以采取的正确措施是( )。 【2011 年全国试题 9(2分)】I增大装填(载)因子设计冲突(碰撞)少的散列函数处理冲突(碰撞)时避免产生聚集(堆积)现象（分数：2.00）A.仅 IB.仅C.仅 I、D.仅、7.若平衡二叉树的高度为 6，且所有非叶结点的平衡因子均为 1，则该平衡二叉树的结点总数为( )。【2012 年全国试题 4(2分)】（分数：2.00）A.12B.20C.32D.338.设有一棵 3阶 B树，如下图所示。删除关键字 78得到一棵新 B树，其最右叶结点所含的关键字是( )。201
4、2年全国试题 9(2分)】 （分数：2.00）A.60B.60，62C.62，65D.659.若将关键字 1，2，3，4，5，6，7 依次插入到初始为空的平衡二叉树 T中，则 T中平衡因子为 0的分支结点的个数是( )。2013 年全国试题 3(2分)】（分数：2.00）A.0B.1C.2D.310.在任意一棵非空二叉排序树 T 1 中，删除某结点 v之后形成二叉排序树 T 2 ，再将 v插入 T 2 形成二叉排序树 T 3 。下列关于 T 1 与 T 3 的叙述中，正确的是( )。【2013 年全国试题 6(2分)】 I若 v是T 1 的叶结点，则 T 1 与 T 3 不同 若 1，是 T
5、1 的叶结点，则 T 1 与 T 3 相同 若 v不是 T 1 的叶结点，则 T 1 与 T 3 不同 若 v不是 T 1 的叶结点，则 T 1 与 T 3 相同（分数：2.00）A.仅 I、B.仅 I、C.仅、D.仅、11.在一棵高度为 2的 5阶 B树中，所含关键字的个数最少是( )。2013 年全国试题 10(2分)】（分数：2.00）A.5B.7C.8D.1412.用哈希(散列)方法处理冲突(碰撞)时可能出现堆积(聚集)现象。下列选项中，会受堆积现象直接影响的是( )。【2014 年全国试题 8(2分)】（分数：2.00）A.存储效率B.散列函数C.装填(装载)因子D.平均查找长度13
6、.在一棵具有 15个关键字的 4阶 B树中，含关键字的结点数最多是( )。【2014 年全国试题 9(2分)】（分数：2.00）A.5B.6C.10D.1514.现在有一棵无重复关键字的平衡二叉树(AVL 树)，对其进行中序遍历可得到一个降序序列。下列关于该平衡二叉树的叙述中，正确的是( )。2015 年全国试题 4(2分)】（分数：2.00）A.根结点的度一定为 2B.树中最小元素一定是叶结点C.最后插入的元素一定是叶结点D.树中最大元素一定是无左子树15.下列选项中，不能构成折半查找中关键字比较序列的是( )。【2015 年全国试题 7(2分)】（分数：2.00）A.500，200，450
7、，180B.500，450，200，180C.180，500，200，450D.180，200，500，45016.若查找每个记录的概率均等，则在具有 n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度 ASL为( )。【北京航空航天大学 2000一、8(2 分)】【大连理工大学 2008一、5(2 分)】（分数：2.00）A.(n-1)2B.n2C.(n+1)2D.n17.对于顺序查找，假定查找成功与不成功的可能性相同，对每个记录的查找概率也相同，此时顺序查找的平均查找长度为( )。【华中科技大学 2006一、10(2 分)】（分数：2.00）A.05(n+1)B.025(n
8、+1)C.05(n 一 1)D.075(n+1)18.在一个有 N个元素的有序单链表中查找具有给定关键字的结点，平均情况下的时间复杂性为( )。【上海交通大学 2005四、2(2 分)】（分数：2.00）A.O(1)B.O(N)C.O(N 2 )D.O(mogN)19.将两个各有 n个元素的有序表归并成一个有序表，其最多的比较次数是：( )。【中国科学技术大学1998二、9(2 分)】（分数：2.00）A.2nB.nC.2n-120.查找 n个元素的有序表时，最有效的查找方法是( )。【中国科学技术大学 1997一、1(1 分)】【四川大学 2005】（分数：2.00）A.顺序查找B.分块查找
9、C.二分查找D.二叉排序树二、填空题(总题数：5，分数：10.00)21.在各种查找方法中，平均查找长度与结点个数，z 无关的查找方法是_。【中南大学 2005二、5(2分)】（分数：2.00）_22.动态查找表和静态查找表的重要区别在于前者包含有_和_运算，而后者不包含这两种运算。【厦门大学 2001一、3(145 分)】（分数：2.00）_23.在等概率情况下，对具有 n个元素的顺序表进行顺序查找，查找成功(即表中有关键字等于给定值 K的记录)的平均查找长度为_：查找不成功(即表中无关键字等于给定值 K的记录)的平均查找长度为_。【哈尔滨工业大学 2005一、3(1 分)】（分数：2.00
10、）_24.顺序查找 n个元素的顺序表，若查找成功，则比较关键字的次数最多为_次；当使用监视哨时，若查找失败，则比较关键字的次数为_。【华中理工大学 2000一、8(2 分)】（分数：2.00）_25.折半查找要求数据元素_，存储方式采用_。【电子科技大学 2005二、6(1 分)】（分数：2.00）_三、判断题(总题数：10，分数：20.00)26.如果数据元素保持有序，则检索时就可以采用二分检索方法。( )【兰州大学 2001一、9(1 分)】（分数：2.00）A.正确B.错误27.折半查找与二元查找树的时间性能在最坏的情况下是相同的。( )【哈尔滨工业大学 2005三、6(1 分)】（分数
11、：2.00）A.正确B.错误28.用向量和单链表表示的有序表均可使用折半查找方法来提高查找速度。( )【中科院软件所 1997一、6(1分)】（分数：2.00）A.正确B.错误29.有 n个数存放在一维数组 A1n中，在进行顺序查找时，这 n个数的排列有序或无序其平均查找长度不同。( )【北京邮电大学 1998一、6(2 分)】（分数：2.00）A.正确B.错误30.在索引顺序表中，实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块中元素个数有关。( )【上海交通大学 1998一、17(1 分)】（分数：2.00）A.正确B.错误31.适于对动态查找表进行高效率
12、查找的组织结构是分块有序表。( )【北方交通大学 2003三、2(2 分)】（分数：2.00）A.正确B.错误32.对于满足折半查找和分块查找条件的文件而言，无论它存放在何种介质上，均能进行顺序查找、折半查找和分块查找。( )【北京师范大学 2005三、4(5 分)】（分数：2.00）A.正确B.错误33.折半查找法的查找速度一定比顺序查找法快。( )【山东大学 2001一、8(1 分)】（分数：2.00）A.正确B.错误34.就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。( ) 【西安交通大学 1996二、3(3分)】（分数：2.00）A.正确B.错误35.对一棵二叉排序树按
13、前序方法遍历得出的结点序列是从小到大的序列。( )【南京航空航天大学 1995五、4(1 分)】（分数：2.00）A.正确B.错误计算机专业基础综合数据结构（集合）历年真题试卷汇编 4答案解析(总分：70.00，做题时间：90 分钟)一、单项选择题(总题数：20，分数：40.00)1.下列二叉排序树中，满足平衡二叉树定义的是( )。【2009 年全国试题 4(2分)】（分数：2.00）A.B. C.D.解析：2.下列叙述中，不符合 m阶 B树定义要求的是( )。【2009 年全国试题 8(2分)】（分数：2.00）A.根结点最多有 m棵子树B.所有叶结点都在同一层上C.各结点内关键字均升序或降
14、序排列D.叶结点之间通过指针链接 解析：解析：一棵 m阶的 B树的定义如下：或为空树，或为满足下列特性的 m叉树： (1)树中每个结点至多有 m棵子树； (2)若根结点不是叶子结点，则至少有两棵子树； (3)除根结点之外的所有非终端结点至少有m2棵子树； (4)所有的非终端结点中包含下列信息数据(n，P0，P 0 ，P 1 ，K 2 ，P 2 ，K n ，P n )，其中：K i (i=1，n)为关键字，且 K i i+1(i=1，n 一 1)，P i(i=0，n)为指向子树根结点的指针，且指针 Pi-1所指子树中所有结点的关键字均小于 Ki(i=1，n)，P n所指子树中所有结点的关键字均大
15、于 Kn，n(m21nm 一 1)为关键字的个数； (5)所有叶子结点都出现在同一层次上，并且不带信息(可以看作是外部结点或查找失败的结点，实际上这些结点不存在，指向这些结点的指针为空)。 据此，选择答案 D不符合 B树定义，D 描述的是 B+树，B+树的叶结点本身按照关键字的大小，自小而大顺序链接。3.在下图所示的平衡二叉树中，插入关键字 48舌得到一棵新平衡二叉树。在新平衡二叉树中，关键字37所在结点的左、右子结点中保存的关键字分别是( )。【2010 年全国试题 4(2分)】 （分数：2.00）A.13、48B.24、48C.24、53 D.24、90解析：解析：失去平衡的最小子树根结点
16、是 24，需做 RL型调整。4.已知一个长度为 16的顺序表 L，其元素按关键字有序排列。若采用折半查找法查找一个 L中不存在的元素，则关键字的比较次数最多是( )。 2010 年全国试题 9(2分)】（分数：2.00）A.4B.5 C.6D.7解析：解析：长度 16的顺序表的判定树的高度为 5，用折半查找法查找失败时，最多比较 5次。5.对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是( )。【2011 年全国试题 7(2分)】（分数：2.00）A.95，22，91，24，94，71 B.92，20，91，34，88，35C.21，89，77，29，36，38D.12，25，
17、71，68，33，24解析：解析：二叉排序树的查找路径走一条从根结点到子孙结点的路径。答案 A的比较轨迹是：待查关键字小于 95，沿左分支到 22，又大于 22，沿 22往右，到 91，比 91小，往左到 24，比 24大，往右找到94，这是不可能的。因为 94，这能出现在 91的左子树中。本题的详细分析和算法见五、34。6.为提高散列(Hash)表的查找效率，可以采取的正确措施是( )。 【2011 年全国试题 9(2分)】I增大装填(载)因子设计冲突(碰撞)少的散列函数处理冲突(碰撞)时避免产生聚集(堆积)现象（分数：2.00）A.仅 IB.仅 C.仅 I、D.仅、解析：解析：减小装填因子
18、可以提高散列表的查找效率；处理冲突(碰撞)时可以减少，但不能“避免”产生聚集(堆积)现象，只有选择答案是正确的。选择 B。7.若平衡二叉树的高度为 6，且所有非叶结点的平衡因子均为 1，则该平衡二叉树的结点总数为( )。【2012 年全国试题 4(2分)】（分数：2.00）A.12B.20 C.32D.33解析：解析：设以 N h 表示深度为 h的平衡二叉树中含有的最少结点数。显然，N 0 =0，N 1 =1，N 2 =2，并且 N h =N h-1 +N h-2 +1。即高为 h的平衡二叉树的左子树高为 h一 1，右子树高为 h一 2，左右子树都是含有最少结点数的平衡二叉树。这种树实际是 F
19、ibonacci树。8.设有一棵 3阶 B树，如下图所示。删除关键字 78得到一棵新 B树，其最右叶结点所含的关键字是( )。2012年全国试题 9(2分)】 （分数：2.00）A.60B.60，62C.62，65D.65 解析：解析：这里只讨论在 B树最下层非终点结点关键字的删除。 (1)若删除后仍符合 B树的定义，删除结束。 (2)若删除后会破坏 B树的定义，若左右兄弟结点的关键字数 nm2-1(m 是 B树的阶)，则可以向左右兄弟结点借用。这里举个生活中的例子。兄弟分家过日子，自己度日困难，但兄弟富裕，想借钱又碍于面子，只好和父母借。父母给了儿子钱，同时叫富裕的儿子交了抚养费。聪明的父母
20、既解决了问题，又照顾了子女的面子。本题，删除 78，破坏了 B树的定义，父母 65要了儿子 62，自己下到 78的结点处。 (3)若左右兄弟都很困难，则父母会下来和其余子女艰难度日，对父母结点同样处理，最终会导致B树的高度降低。9.若将关键字 1，2，3，4，5，6，7 依次插入到初始为空的平衡二叉树 T中，则 T中平衡因子为 0的分支结点的个数是( )。2013 年全国试题 3(2分)】（分数：2.00）A.0B.1C.2D.3 解析：解析：插入 1、2 和 3后失衡，做 RR型调整。继续输入 4和 5，失衡的最小子树的根结点是 2，做RR型调整。继续输入 6和 7，失衡的最小子树的根结点是
21、 5，做 RR型调整。最后的结果是高度为 3的满二叉树，中序遍历得到 1到 7的升序序列。10.在任意一棵非空二叉排序树 T 1 中，删除某结点 v之后形成二叉排序树 T 2 ，再将 v插入 T 2 形成二叉排序树 T 3 。下列关于 T 1 与 T 3 的叙述中，正确的是( )。【2013 年全国试题 6(2分)】 I若 v是T 1 的叶结点，则 T 1 与 T 3 不同 若 1，是 T 1 的叶结点，则 T 1 与 T 3 相同 若 v不是 T 1 的叶结点，则 T 1 与 T 3 不同 若 v不是 T 1 的叶结点，则 T 1 与 T 3 相同（分数：2.00）A.仅 I、B.仅 I、C
22、.仅、 D.仅、解析：解析：在二叉排序树上插入的结点肯定是叶子，删除叶子马上再插入不会引起二叉排序树的变化。删除分支结点会调整以保持二叉排序树的树形，再插入该结点是按叶子结点插入，形成的二叉排序树肯定与从前不同了。11.在一棵高度为 2的 5阶 B树中，所含关键字的个数最少是( )。2013 年全国试题 10(2分)】（分数：2.00）A.5 B.7C.8D.14解析：解析：根结点一个关键字，两棵子树各有两个关键字的 5阶 B树含有最少 5个关键字，所以选择答案 A。应该指出，多数教科书对 B树的叶子结点的定义是：“所有叶子结点都出现在同一层次上，并且不带信息”，B 树的高度包括叶子这一层。如
23、按这个定义，高度为 2的 5阶 B树最少一个关键字，选择答案中无此选择项。本题 B树高度未包括叶子层，下面涉及 B树高度时我们都包括叶子这一层。12.用哈希(散列)方法处理冲突(碰撞)时可能出现堆积(聚集)现象。下列选项中，会受堆积现象直接影响的是( )。【2014 年全国试题 8(2分)】（分数：2.00）A.存储效率B.散列函数C.装填(装载)因子D.平均查找长度 解析：13.在一棵具有 15个关键字的 4阶 B树中，含关键字的结点数最多是( )。【2014 年全国试题 9(2分)】（分数：2.00）A.5B.6C.10D.15 解析：解析：4 阶 B树每个结点最少 1个关键字(2 棵子树
24、)，最多 3个关键字(4 棵子树)。在关键字数确定的情况下，每个结点含有的关键字越少，所需结点数就越多。结点只含 1个关键字的 B树可以看成是满二叉树，因此本题等价于“1 5 个关键字的满二叉树的结点数”。14.现在有一棵无重复关键字的平衡二叉树(AVL 树)，对其进行中序遍历可得到一个降序序列。下列关于该平衡二叉树的叙述中，正确的是( )。2015 年全国试题 4(2分)】（分数：2.00）A.根结点的度一定为 2B.树中最小元素一定是叶结点C.最后插入的元素一定是叶结点D.树中最大元素一定是无左子树 解析：解析：题目说对无重复关键字的平衡二叉树“进行中序遍历可得到一个降序序列”，可以知道根
25、结点的值大于左子树上所有结点的值，并且小于右子树上所有结点的值。中序遍历的第一个结点是二叉树最左面的(叶子或无左子女的“根”)结点，所以应选择答案 D。我们还可以用排除法。若结点个数小于 3，则根结点的度是 1不是 2，所以 A错。中序遍历的最后一个元素是最小元素，它可以是最右面的叶子结点，也可以是没有右子女的“根”结点，所以 B错。最后插入的元素先是按叶子结点插入，但是插入后可能导致平衡二叉树失衡，经过调整最后插入的结点不再是叶子，所以 C错。15.下列选项中，不能构成折半查找中关键字比较序列的是( )。【2015 年全国试题 7(2分)】（分数：2.00）A.500，200，450，180
26、 B.500，450，200，180C.180，500，200，450D.180，200，500，450解析：解析：A 中待查关键字小于 500，大于下个待查找的是 200，接着找到 450，但比 450小，最后查找到 180。这是不可能的，因为刚才查找 200时，待查找关键字大干 200。16.若查找每个记录的概率均等，则在具有 n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度 ASL为( )。【北京航空航天大学 2000一、8(2 分)】【大连理工大学 2008一、5(2 分)】（分数：2.00）A.(n-1)2B.n2C.(n+1)2 D.n解析：17.对于顺序查找，假
27、定查找成功与不成功的可能性相同，对每个记录的查找概率也相同，此时顺序查找的平均查找长度为( )。【华中科技大学 2006一、10(2 分)】（分数：2.00）A.05(n+1)B.025(n+1)C.05(n 一 1)D.075(n+1) 解析：18.在一个有 N个元素的有序单链表中查找具有给定关键字的结点，平均情况下的时间复杂性为( )。【上海交通大学 2005四、2(2 分)】（分数：2.00）A.O(1)B.O(N) C.O(N 2 )D.O(mogN)解析：19.将两个各有 n个元素的有序表归并成一个有序表，其最多的比较次数是：( )。【中国科学技术大学1998二、9(2 分)】（分数
28、：2.00）A.2nB.nC.2n-1 解析：20.查找 n个元素的有序表时，最有效的查找方法是( )。【中国科学技术大学 1997一、1(1 分)】【四川大学 2005】（分数：2.00）A.顺序查找B.分块查找C.二分查找 D.二叉排序树解析：解析：有序表是静态查找表，采用二分查找，二又排序树是动态查找表。二、填空题(总题数：5，分数：10.00)21.在各种查找方法中，平均查找长度与结点个数，z 无关的查找方法是_。【中南大学 2005二、5(2分)】（分数：2.00）_正确答案：(正确答案：哈希查找)解析：22.动态查找表和静态查找表的重要区别在于前者包含有_和_运算，而后者不包含这两
29、种运算。【厦门大学 2001一、3(145 分)】（分数：2.00）_正确答案：(正确答案：插入，删除)解析：23.在等概率情况下，对具有 n个元素的顺序表进行顺序查找，查找成功(即表中有关键字等于给定值 K的记录)的平均查找长度为_：查找不成功(即表中无关键字等于给定值 K的记录)的平均查找长度为_。【哈尔滨工业大学 2005一、3(1 分)】（分数：2.00）_正确答案：(正确答案：(n+1)2，n+1)解析：24.顺序查找 n个元素的顺序表，若查找成功，则比较关键字的次数最多为_次；当使用监视哨时，若查找失败，则比较关键字的次数为_。【华中理工大学 2000一、8(2 分)】（分数：2.
30、00）_正确答案：(正确答案：n,n+1)解析：25.折半查找要求数据元素_，存储方式采用_。【电子科技大学 2005二、6(1 分)】（分数：2.00）_正确答案：(正确答案：有序，顺序存储)解析：三、判断题(总题数：10，分数：20.00)26.如果数据元素保持有序，则检索时就可以采用二分检索方法。( )【兰州大学 2001一、9(1 分)】（分数：2.00）A.正确B.错误 解析：解析：二分检索要求顺序存储的有序表。27.折半查找与二元查找树的时间性能在最坏的情况下是相同的。( )【哈尔滨工业大学 2005三、6(1 分)】（分数：2.00）A.正确B.错误 解析：解析：折半查找属于静态
31、查找表，其判定树(设有 n(n1)个元素)是确定的，查找长度不超过判定树的深度(与相等元素个数的完全二叉树的深度相同)。二元查找树属于动态查找表，查找长度取决于树的形状，最差情况下是单支树。28.用向量和单链表表示的有序表均可使用折半查找方法来提高查找速度。( )【中科院软件所 1997一、6(1分)】（分数：2.00）A.正确B.错误 解析：解析：单链表不能使用折半查找方法。29.有 n个数存放在一维数组 A1n中，在进行顺序查找时，这 n个数的排列有序或无序其平均查找长度不同。( )【北京邮电大学 1998一、6(2 分)】（分数：2.00）A.正确B.错误 解析：解析：在等概率查找的情况
32、下，对于查找成功，它们的平均查找长度是相同的，而对于查找失败，它们的平均查找长度是不同的。30.在索引顺序表中，实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块中元素个数有关。( )【上海交通大学 1998一、17(1 分)】（分数：2.00）A.正确 B.错误解析：31.适于对动态查找表进行高效率查找的组织结构是分块有序表。( )【北方交通大学 2003三、2(2 分)】（分数：2.00）A.正确B.错误 解析：解析：二叉排序树、平衡二叉树、B 树、键树属于动态查找表，分块有序表属于静态查找表。32.对于满足折半查找和分块查找条件的文件而言，无论它存放在何种
33、介质上，均能进行顺序查找、折半查找和分块查找。( )【北京师范大学 2005三、4(5 分)】（分数：2.00）A.正确B.错误 解析：解析：磁带存储介质就只能顺序查找。33.折半查找法的查找速度一定比顺序查找法快。( )【山东大学 2001一、8(1 分)】（分数：2.00）A.正确B.错误 解析：34.就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。( ) 【西安交通大学 1996二、3(3分)】（分数：2.00）A.正确B.错误 解析：35.对一棵二叉排序树按前序方法遍历得出的结点序列是从小到大的序列。( )【南京航空航天大学 1995五、4(1 分)】（分数：2.00）A.正确B.错误 解析：
