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