发布时间 : 星期日 文章中国石油大学数据结构试题及答案更新完毕开始阅读98863db3f111f18583d05ac6
答案：需要向后移动 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）各层的结点个数是ki (i=0,1,2,....,h)
（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 B C D F H I J K 答案：
A B E
C F G D H
10、将算术表达式 ((a+b)+c*(d+e)+f)*(g+h) 转化为二叉树。（7分） 答案：
a + b c d + + * + f h g * + e 12、 将给定的图简化为最小的生成树，要求从顶点1出发。（7分）
2 8 1 5 3 15 7 7 5 3 10 12 6 9 4 2
6 答案:
6 6 2 3 1 5 3 4 7 2 7 15 5
13、某子系统在通信联络中只可能出现8种字符，其出现的概率分别为0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11试设计赫夫曼编码。 答案：
为方便起见，设各种字符的权值w={5,29,7,8,14,23,3,11}。因为n=8，所以要构造的赫夫曼树共有m=2n-1=2*8-1=15个结点。生成的赫夫曼树为下图所示：
0 1 0 29 1 0 5 1 3 0 14 7 0 1 1 1 8 0 1 0
23 11 赫夫曼编码为：概率为0.23的字符编码为：00 概率为0.11的字符编码为：010
概率为0.05的字符编码为：0110 概率为0.03的字符编码为：0111