2015(1)年度中国石油大学数据结构试题及答案

48、在对m阶B-树中，每个非根结点的关键码数最少为（「m/2┐-1）个，最多为（m-1）个，其子树棵数最少为（「m/2┐），最多为（m）。

三、 判断题

四、运算使用题

1、在一个有n个元素的顺序表的第i个元素（1 ? i ? n）之前插入一个新元素时，需要向后移动多少个元素？ 答案：需要向后移动 n- i + 1个元素 2、 当一个栈的进栈序列为1234567时，可能的出栈序列有多少种？6457321是否是合理的出栈序列？ 答案：

1114?13?12?11?10?9?87C14???4297?187?6?5?4?3?2?1 可能的出栈序列有

种，6457321不是合理的出栈序列。 4、设有序顺序表为 { 10, 20, 30, 40, 50, 60, 70 }，采用折半搜索时，搜索成功的平均搜索长度是多少？ 答案：

ASLsucc = (1*1 + 2*2 + 3*4 ) / 7 = 17

/ 7

5、 在结点个数为n(n>1)的各棵树中，高度最小的树的高度是多少？它有多少个叶结点？多少个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？

答案：结点个数为n时，高度最小的树的高度为1，有2层；它有n-1个叶结点，1个分支结点；高度最大的树的高度为n-1,有n层；它有1个叶结点，n-1个分支结点。 6、 一棵高度为h的满k叉树有如下性质: 第h层上的结点都是叶结点, 其余各层上每个结点都有k棵非空子树, 如果按层次自顶向下, 同一层自左向右, 顺序从1开始对全部结点进行编号, 试问:

(1) 各层的结点个数是多少?

(2) 编号为i的结点的父结点(若存在)的编号是多少? (3) 编号为i的结点的第m个孩子结点(若存在)的编号是多少?

(4) 编号为i的结点有右兄弟的条件是什么? 其右兄弟结点的编号是多少?

(5) 若结点个数为 n, 则高度h是n 的什

么函数关系? 答案：

（1）各层的结点个数是k(i=0,1,2,....,h)

i

（2）编号为i的结点的父结点(若存在)的编号是└ (i+k-2)/k」

（3）编号为i的结点的第m个孩子结点(若存在)的编号是(i-1)*k+m+1

（4）当(i-1)%k<>0时有右兄弟， 右兄弟的编号为 i+1

（5）若结点个数为 n ，则高度h和n 的关系为：h=logk(n*(k-1)+1)-1 (n=0时h=-1)

9、题目：11、将下面的森林变换成二叉树（7分）。

A E G 答案： A H I B C D F 10、将算术表达式 ((a+b)+c*(d+e)+f)*(g+B J E 分） h) 转化为二叉树。（7* 答案： K F C G + + D + + a b H g f * + h I J

12、 将给定的图简化为最小的生成树，要求从顶点1出发。（7分）

8 1 5 3 答案: 3 15 2 1 12 5 5 10 4 3 15 13、某子系统在通信联络中只可能出现8种

7 6 7 5 字符，其出现的概率分别为0.05，0.29，4 2 6 0.07，0.08，0.14，0.23，0.03，0.11试设

7 6 计赫夫曼编码。 2 9 2 6 3 7 答案：

为方便起见，设各种字符的权值

w={5,29,7,8,14,23,3,11}。因为n=8，所以要构造的赫夫曼树共有m=2n-1=2*8-1=15个结点。生成的赫夫曼树为下图所示：

0 0 1 1 0 1 23 29 赫夫曼编码为：概率为的字符编码为：0 0 0.231 1 11 1 14 00 0 0 1 概率为0.11的字符编码为：010

3 5 7 8 概率为0.05的字符编码为：0110 概率为0.03的字符编码为：0111