计算机专业基础综合数据结构(集合)历年真题试卷汇编8

计算机专业基础综合数据结构（集合）历年真题试卷汇编8

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

一、 综合题(总题数：26，分数：54.00)

1.已知长度为11的表(xal，wan，wil，zol，yo，xul，yum，wen，wim，zi，yon)，按表中元素顺序依次插入一棵初始为空的平衡二叉排序树，画出插入完成后的平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。【山东大学2001七(7分)】 （分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案： 解析：

2.用关键字1，2，3，4的四个结点(1)能构造出几种不同的二叉排序树?其中(2)最优查找树有几种?(3)AVL树有几种?(4)完全二叉树有几种?试画出这些二叉排序树。【北京工业大学1997二、3(5分)】 （分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：(1)本题的实质是给定中序序列1、2、3、4，有几种不同的二叉排序树，即该中序序列相当于多少不同的前序序列，这是树的计数问题。设中序序列中元素数为n，则二又数的数目为1／(n+1)C 2n ，这里n=4，故有14种。图示如下： 解析：

3.可以生成下图所示的二叉排序树的关键字初始序列有几种?试写出其中的任意4种。【电子科技大学2005三、2(6分)】（分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：8种(1)8，9，4，2，6 (2)8，9，4，6，2 (3)8，4，2，6，9 (4)8，4，2，9，6 (5)8，4，6，2，9 (6)8，4，6，9，2 (7)8，4，9，2，6 (8) 8，4，9，6，2) 解析：

4.设二叉排序树中关键字由1到1000的整数组成，现要查找关键字为363的结点，下述关键字序列哪一个不可能是在二叉排序树中查到的序列?说明原因。(1)51，250，501，390，320，340，382，363(2)24，877，125，342，501，623，421，363【东北大学2002一、3(4分)】 （分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：序列(2)不可能是二叉排序树中查到363的序列。查到501后，因363<501，后面应出现小于501的数，但序列中出现了623，故不可能。) 解析：

5.一棵具有m层的AVL树至少有多少个结点，最多有多少个结点? 【浙江大学1995六(8分)】 （分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：设以N m 表示深度为m的AVL树中含有的最少结点数。显然，N 0 =0，N 1 =1，N 2 =2，且N m =N m-1 +N m-2 +1(m≥2)。这个关系与斐波那契序列类似，用归纳法可以证明：当m≥0时，N m =F —1，而F m 约等于 (其中 )，则N m 约等于 m

n

ASL SUCC =(1*1+2*2+4*3+4*4)／1 1=33／1 1)

(2)最优查找树有4种，图中(10)、(11)、(12)、

(13)。(3)AVL树也有4种，图中(10)、(11)、(12)、(13)。(4)完全二叉树有1种，图中(10)。)

m+2

(即深度为m的AVL树具有的最少结点

数)。当,层的AVL树是满二叉树时，结点数为最大值2 一1。) 解析：

6.设T是一棵高度平衡树(又称平衡树)，给定关键词K，如果在T中查找K失败，且查找路径上的任一结点的平衡系数皆为零，试回答用高度平衡树插入算法在T中插入关键词为K的新结点后，树T的高度是否一定增加?并回答为什么。【吉林大学1996四、2(7分)】 （分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：树的高度一定增加。因为“查找路径上的任一结点的平衡系数皆为零”，从根结点开始查找，根结点的平衡因子为零，说明根的左右子树等高(不一定是满二叉树)。沿左(或右)子树向下查找时，查找路径上所有结点的平衡因子皆为零，说明任一结点的左右子树等高，查找失败是在叶子结点，插入也是在叶子结点，树的高度自然增加。) 解析：

7.试画出从空树开始，由字符序列(t，d，e，s，u，g，b,一j，k，r，i)构成的二叉平衡树，并为每一次的平衡处理指明旋转类型。【清华大学1994三(10分)】 （分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：解析：

8.在B一树和B+树中查找关键字时，有什么不同?【东北大学2002一、5(2分)】 （分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：在B一树中查找关键字从根结点开始，从根往下查找结点，然后在结点内查找关键字，得出查找成功与否的结论。B+树的非终端结点是索引部分，其查找从根开始，从根往下查到关键字后，要继续查到最下层结点，得到查找成功与否的结论。另外，B+树还可以在最下层从最小关键字开始，从左往右进行顺序查找，B一树则不能作顺序查找。) 解析：

9.简要叙述B树(有些教材中称为B一树)与B+树的区别。【南京航空航天大学1999六(5分)】 （分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：m阶的B+树和B一树主要区别有三：(1)有n棵子树的结点中含有n(B一树中n—1)个关键字；(2)B+树叶子结点包含了全部关键字信息，及指向含关键字记录的指针，且叶子结点本身依关键字大小自小到大顺序链接，B一树的叶子结点是失败结点，实际不存在；(3)B+树的非终端结点可以看成是索引部分，结点中只含其子树(根结点)中最大(或最小)关键字。B+树的查找既可以顺序查找，也可以随机查找，B一树只能随机查找。) 解析：

10.当B一树作为文件的索引时，一个结点除了包含关键字和指向孩子结点的指针外，还包含指向文件记录的指针。假设一个结点占用的最大空间被限定为4096字节，每个关键字和每个指针都占2字节。如果采用n阶B树作为文件的索引，则它的最大的阶数应该是多少?【北京理工大学2006十一、5(5分)】 （分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：因为每个非终端结点中包含下列信息数据(n，P 0 ，K 1 ，P 1 ，K 2 ，P 2 ，…，K n ，P n )，其中n是关键字个数，P 0 指向关键字比K 1 小的结点，(K i ，P i )(1≤i≤n)成对出现，按题意，结点中还包含指向文件记录的指针，即一个关键字要占用6字节。每个结点还包括该结点的关键字个数和小于第一个关键字的指针。故最大阶数应是(4096—4)／6=682。) 解析：

11.证明：高为h(不含叶子层)的m阶B一树上最多有m 一1个关键字。【北京交通大学2006四、2(5分)】 （分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：m阶B树的每个结点最多有m一1个关键字，第一层m—1个关键字，第二层m(m

h

) 一1)个关键字，第三层m (m一1)个关键字，……，第h层m (m一1)个关键字。将各层关键字数相加，得证。) 解析：

12.满二叉检索树符合B树定义吗?B树的插入和删除算法适用于满二叉检索树吗?为何?【东南大学1995五(6分)】 （分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：满二叉检索树可以看作是三阶B一树(2—3树)。B一树的插入和删除算法不适合满二叉检索树。满二叉检索树插入和删除结点后均破坏了“多路平衡查找树”“叶子在同一层上”(查找失败结点)的定义。) 解析：

13.含9个叶子结点的3阶B一树中至少有多少个非叶子结点?含10个叶子结点的3阶B一树中至多有多少个非叶子结点?【东南大学2005一、1(5分)】【北京轻工业学院2000八(10分)】 （分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：含9个叶子结点的3阶B一树至少有4个非叶子结点，当每个非叶子结点均含3棵子树，第三层是叶子结点时就是这种情况。当4层3阶B一树有10个叶子结点时，非叶子结点达到最大值8个：其中第一层1个，第二层2个，第三层5个。) 解析：

14.设依以下次序给出关键字：34，16，19，21，5，49，24，62，3，17，45，8，构造3阶B一树。要求从空树开始，每插入一个关键字，画出一个树形。【南开大学1997六(10分)】 （分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：解析：

15.对下面的3阶B一树，依次执行下列操作，画出各步操作的结果。【合肥工业大学1999四、3(5分)】 (1)插入90 (2)插入25 (3)插入45 (4)删除60 (5)删除80（分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：解析：

已知2棵2—3 B一树如下(省略外结点)。【吉林大学1999一、3(4分)】（分数：4.00）

) ) 2h-1

(1).对树(a)，请分别画出 先后插入 26，85两个新结点后的树形；（分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：解析：

(2).对树(b)，请分别画出 先后删除 53，37两个结点后的树形。（分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：解析：

16.阶B树中(如图所示)，插入关键字87，试画出插入调整后树的形状。【东南大学1999五(1 5分)】（分数：2.00）

) ) __________________________________________________________________________________________ 正确答案：(正确答案：解析：

17.下图是5阶B树，画出删去P后的B树，再画出删去D后的B树。【厦门大学2000七、3(20／3分)】 （分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：删除P时，亦可将双亲结点中的M与N一起并入左兄弟成为(KLMN)。解析：

18.设有关键码序列10，20，35，40，44，51，65，70，85，91，93，95。试按照最大关键码复写原则绘出相应的2阶B+树。【山东工业大学1 996二、1(6分)】 （分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：解析：

19.回答问题并填空。(1)(2分)散列表存储的基本思想是什么?(2)(4分)散列表存储中解决碰撞的基本方法有哪些?其基本思想是什么?(3)(4分)用分离的同义词子表解决碰撞和用结合的同义词表解决碰撞属于哪种基本方法?他们各有何特点?(4)(3分)用线性探查法解决碰撞时，如何处理被删除的结点?为什么?(5)(2分)散列法的平均检索长度不随( )的增加而增加，而是随( )的增大而增加。【山东工业大学1999四(15分)】 （分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：(1)哈希表存储的基本思想是用关键字的值决定数据元素的存储地址。 (2)哈希表存储中解决碰撞的基本方法： ①开放定址法。形成地址序列的公式是：H i =(H(key)+d i )％m，其中m是表长，d i 是增量。根据d i 取法不同，又分为三种：a.d i =1，2，…，m一1称为线性探测再哈希，其特点是逐个探测表空间，只要哈希表中有空闲空间，就可解决碰撞，缺点是容易造成“聚集”，即不是同义词的关键字争夺同一哈希地址。b.d i =1 ，一1 ，2 ，一2 ，…，±k (k≤m／2)称为二次探测再哈希，它减少了聚集，但不容易探测到全部表空间，只有当表长为形如4j+3(，为整数)的素数时才有可能。c.d i =伪随机数序列，称为随机探测再哈希。 ②再哈希法。H i =RH i (key)i=1，2，…，k，是不同的哈希函数，即在同义词产生碰撞时，用另一哈希函数计算哈希地址，直到解决碰撞。该方法不易产生“聚集”，但增加了计算时间。 ③链地址法。将关键字为同义词的记录存储在同一链表中，哈希表地址区间用研0一..m一1]表示，哈希表元素初始值为空指针。凡哈希地址为f(0≤i≤m一1)的记录均插在以研[i]为头指针的链表中。这种解决方法中数据元素个数不受表长限制，插入和删除操作方便，但增加了指针的空间开销。这种哈希表常称为开哈希表，“开”的含义是哈希表无边界，元素个数没限制，哈希表不会溢出，只受存储空间限制。而①中的哈希表称闭哈希表，“闭”含义是元素个数受表长限制。 ④建立公共溢出区。设H[0一m一1]为基本表，凡关键字为同义词的记录，都填入溢出区O[0..m一1]。 (3)用分离的同义词表和结合的同义词表解决碰撞均属于链地址法。链地址向量空间中的每个元素不是简单的地址，而是关键字和指针两个域，哈希地址为i(0≤i≤m—1)的第一个关键字存储在地址空间向量下标为i的“关键字”域。前者的指针域是动态指针，指向同义词的链表，具有上面 ③的优缺点；后者实际是静态链表，同义词存在同一地址向量空间(从最后向前找空闲单元)，以静态指针(下标)相连。这节省了空间，但易产生“堆积”，查找效率低。 (4)要在被删除结点的哈希地址处作标记，不能物理地删除。否则，中断了查找通路。 (5)记录、负载因子) 解析：

20.如何衡量Hash函数的优劣?简要叙述Hash表技术中的冲突概念，并指出三种解决冲突的方法。【南京航空航天大学1996九、2(6分)】 （分数：2.00）

2

2

2

2

2

) ) )