9765 83图5
4
24 .给定一组权重值，构造哈夫曼树，哈夫曼树的高度一定是唯一的，这种说法是__________的。(回答正确或不正确)
三、综合题 1．（1）已知某二叉树的后序遍历序列是debca，中序遍历序列是dbeac，试画出该二叉树。 （2）若上述二叉树的各个结点的字符分别代表不同的整数（其中没有相等的），并恰好使
该树成为一棵二叉排序树，试给出a、b、c、d、e的大小关系。
（3）给出该树的前序遍历序列。
2. (1) 说明什么是顶点活动网(AOV网)和拓扑序列 （2）设有向图G如下，写出3种拓扑序列，
（3）在图G中增加一条边，使图G仅有一条拓扑序列
a d b c
图6
6
3．（1）利用筛选过程把序列{42，82，67，102，16，32，57，52}建成堆（小根堆），画出相应的完全二叉树（不要求中间过程）。
（2）写出对上述堆对应的完全二叉树进行中序遍历得到的序列。
4．如下是一棵二叉排序树，A1,A2,…A9代表1，2，3,…9中各个不同数字， （1）给出对该树中序遍历的结果 （2） A3,A5,A7的值各为多少？
（3）请在该树中再插入一个结点9 .5作为叶结点，并使它仍然是一棵二叉排序树
A1 A2 A3 A4 A5 A9 A6 A7 A8
图7
5．设查找表为(11,12,13,14,15,16,17,18,19,20,21) ,元素的下标从0开始。
（1）画出对上述查找表进行折半查找所对应的判定树（树中结点用数值表示） （2）说明成功查找到元素15，19各需要经过多少次比较？ （3）说明查找不到元素10，15.5各需要经过多少次比较？ （4）給出中序遍历判定树的序列。
7
6．
(1) 设有查找表{17，26，14，16，15，30，18，19，28}，依次取表中数据构造一棵二叉 排序树.
(2)对上述二叉树给出后序遍历的结果 (3).对上述二叉树给出中后序遍历的结果
(4))在上述二叉树中查找元素15共要进行多少次元素的比较?
四、程序填空题
1 .以下程序是折半插入排序的算法
设待排序的记录序列存放在a[1],…a[n]中，以a[0]作为辅助工作单元，以下程序是要把a[i]插入到已经有序的序列a[1],…a[i-1]中。 void binsort (NODE a[ ],int n) { int x,i,j,s,k,m;
for （i=2；i<=__(1)___;i++） { a[0]=a[i];
x= a[i].key; s=1; j=i-1; while (s<=j) { m=__(2)___ if( x
__(4)___ }
for ( k=i-1;k>=j+1;k- -) __(5)___=a[k]; a[j+1]=a[0]; }
}
2．以下函数是二叉排序树的查找算法，若二叉树为空，则返回根结点的指针，否则，返回值是指向树结点的结构指针p（查找成功p指向查到的树结点，不成功p指向为NULL）完成程序中的空格
typedef struct Bnode { int key;
struct Bnode *left; struct Bnode *right;
8
} Bnode;
Bnode *BSearch(Bnode *bt, int k)
/* bt用于接收二叉排序树的根结点的指针，k用以接收要查找的关键字*/ { Bnode *p;
if(bt== ___(1)_____) return (bt);
p=bt;
while(p->key!= __(2)______) { if(k
else___(4)_____; if(p==NULL) break; }
return(___(5)_____); }
3．以下函数为链栈的进栈操作，x是要进栈的结点的数据域，top为栈顶指针
struct node
{ ElemType data;
struct node *next; };
struct node *top ;
void Push(ElemType x)
{
struct node *p;
p=(struct node*)malloc(___(1)_____); p->data=x; ___(2)_____; _____(3)___; }
}
4 .设有一个头指针为head的不带头结点单向链表，p、q是指向链表中结点类型的指针变量，p指向链表中结点a, （设链表中没有结点的数据域与结点a的数据域相同）,写出相关语句
(1).使该单向链表成为单向循环链表
(2)插入结点s,使它成为a结点的直接前驱 q=p; x=p->data;
while （__(1)___）q=q->next; q->next=head; q=p; p=p->next; while(p->data!=x) { q=p;
9
__(2)___ }
s->next=p; __(3)___
期末综合练习一答案
一、单项选择题
1．B 2．C 3．A 4 ．B5．D6．D7．B8．C9．A 10．B 11．B 12．C13．D 14．B15．B16．A17．A18．A19．A 20．D21．C22．D 23．D24．C25．C26．A27．B28．A29．B
二、填空题 1．多个数据项 2．图状结构 3．多对多 4．15 5．22 6．（p->next）->prior=p->prior； 7．P所指结点的直接后继 8．p->next=s; 9．p->next=head; 10．abcdefg 11．p本身
12．d=top->data; 13．rear->next=s; 14．front= =rear 15．a7,6
16．A的第一个非零元素的下标为2，3 ，元素为16 17．A共有11个非零元素，a8,5为36 18．5 19．7
20．中序遍历 21．n
22．519876432 23．5387946 24．不正确
三、综合应用题
10
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构（本）期末综合练习（2013年12月）(2)在线全文阅读。
相关推荐：