发布时间 : 星期日 文章中国石油大学数据结构试题及答案更新完毕开始阅读
概率为0.29的字符编码为：10
概率为0.14的字符编码为：110 概率为0.07的字符编码为：1110 概率为0.08的字符编码为：1111
14、已知一棵二叉树的前序遍历的结果是ABECDFGHIJ, 中序遍历的结果是EBCDAFHIGJ, 试画出这棵二叉树，并给出这棵二叉树的后序遍历序列。 答案：根据前序序列和中序序列能得到唯一的二叉树，所得二叉树如图：
A
E B F C G D H IJ 这棵二叉树的后序遍历序列为：EDCBIHJGFA 15、在结点个数为n(n>1)的各棵树中，高度最小的树的高度是多少？它有多少个叶结点？多少个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？
答案：结点个数为n时，高度最小的树的高度为1，有2层；它有n-1个叶结点，1个分支结点；高度最大的树的高度为n-1,有n层；它有1个叶结点，n-1个分支结点。
16、 对于一个高度为h的AVL树，其最少结点数是多少？反之，对于一个有n个结点的AVL树, 其最大高度是多少? 最小高度是多少?
答案：设高度为h(空树的高度为-1)的AVL树的最少结点为Nh，则Nh = Fh+3 -1。 Fh 是斐波那契数。又设AVL树有n个结点，则其最大高度不超过3/2*log2(n+1),
最小高度为「log2(n+1) ┐-1。
17、7-7 设有序顺序表中的元素依次为017, 094, 154, 170, 275,503, 509, 512, 553, 612, 677, 765, 897, 908。试画出对其进行折半搜索时的判定树, 并计算搜索成功的平均搜索长度和搜索不成功的平均搜索长度。 答案：折半搜索时的判定树为： 509 154 677 275
ASLSUCC=1/14（1+2*2+3*4+4*7）=45/14 ASLUNSUCC=1/15（3*1+4*14）=59/15
五、算法分析题
6、请读下列程序，该程序是在单链表中删除一个结点的算法，为空出的地方填上正确的语句。（7分）
void demo2(LinkList head,ListNode *p) {//head 是带头结点的单链表，删除P指向的结点 ListNode *q=head;
while(q&&q->next!=p ) q=q->next; if (q) Error(“*p not in head”); q->next=p->next; free(p);
017 553 503 897 094 170 512 612 765 908 }
10、判断一个带表头结点的双向循环链表L是否对称相等的算法如下所示，请在算法的 处填入正确的语句。 int symmetry(DblList DL) { int sym=1;
DblNode p=DL->rLink,q=DL->lLink; While(p!=q&&p->lLink==q)&& sym==1 ) if (p->data==q->data){ p=p->rLink; q=q->lLink; }
else sym=0; return sym;}