发布时间 : 星期三 文章数据结构（本）期末综合练习2016年6月更新完毕开始阅读
1,2,3,??，11.
（1）画出对上述查找表进行折半查找所对应的判定树（树中结点可用序号表示） （2）说明成功查找到元素33需要经过多少次比较？ (3) 在等概率条件下, 给出成功查找的平均查找长度
2．设有序表为(20, 38, 48, 60, 68, 69, 80) ,元素的序号依次为1,2,3,??，7. （1） 画出对上述查找表进行折半查找所对应的判定树（树中结点用序号表示） （2） 说明成功查找到元素20需要经过多少次比较？ (3) 说明不成功查找元素39需要经过多少次比较？ （4） 给出中序遍历该折半查找判定树的序列 3．
(1)如图1所示,若从顶点a出发，首先经过c按图的深度优先搜索法进行遍历，给出可能得到的一种顶点序列。
a
he c
d b
f
(2)设有向图如图2所示下，写出首先删除顶点1的1种拓扑序列
图1
1 2 3 4
56
图2
4．
(1) 以3，4，5，8，9，10作为叶结点的权，构造一棵哈夫曼树 (2) 给出相应权重值叶结点的哈夫曼编码。 5.
(1) 设数据集合a={7,4,9,8,6,5,3},依次取a中各数据，构造一棵二叉排序树。 (2)对该二叉树进行查找，成功查找到5要进行多少次元素间的比较？
(3) 给出对上述二叉排序树进行中序遍历的序列 6．
(1)如图3所示，若从顶点a出发，首先经过c按深度优先搜索法进行遍历，给出可能得到
第25页
的一种顶点序列。
(2)如图3所示，若从顶点a出发，按广度优先搜索法进行遍历，给出可能得到的2种顶
点序列。
a
he c
f d b 图3
（3）一组记录的关键字序列为（85,62,46,44,51,52），利用堆排序的方法建立小根堆(堆顶元素是最小元素）,给出按筛选法建立的的初始堆。
四、程序填空题
1．以下函数在a[0]到a[n-1]中，用折半查找算法查找关键字等于k的记录，查找成功返回该记录的下标，失败时返回-1，完成程序中的空格
typedef struct { int key; ?? }NODE;
int Binary_Search(NODE a[],int n, int k) {
int low,mid,high; low=0; high=n-1;
while(___(1)_____) {
mid=(low+high)/2; if(a[mid].key==k)
return __(2)______; else if(___(3)_____) low=mid+1; else __(4)______; }
___(5)_____;
}
2.以下函数在头指针为head的单向链表中插入一个新结点，结点的数据域为x，要求该 结点在链表作为第i个结点。（提示： 程序中使工作指针q指向第i-1个结点）
第26页
struct node { int data;
struct node *next; };
typedef struct node NODE
int insert(NODE *head , int x , int i) {
NODE *q,*p;
int j; q=head; j=0;
while((q!=NULL)&&(j { ___(1)_____; j++;} if(q = =NULL) return(0); p=(NODE *) ___(2)_____; ___(3)_____=x; p->next= ___(4)_____; ___(5)_____; return(1); } 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．以下函数为链队列的出队操作（链队列带有头结点），出队结点的数据域的值由 x返回，front、rear分别是链队列的队头、队尾指针 struct node { ElemType data; struct node *next; }; struct node *front，*rear; ElemType OutQueue( ) { 第27页 ElemType x; if(___(1)_____) { printf(\队列下溢错误！\\n\ exit(1); } else { struct node *p=front->next; x=p->data; front->next= ___(2)_____; if(p->next==NULL) rear=front; free(p); ___(3)_____; } } 练习三答案 一、单项选择题 1．C 2．A 3．A 4．D 5．A 6．D 7．B 812．C 13．C 14．B 15．C 16．B 17．C 1822．B 23．C 24．D 25．C 26．B 27．A 28 二、填空题 1. 6 2.图状结构 3. 逻辑 4.线性 5. 先出 6.(rear+1)%MaxSize==front为真 7.（b,a,c） 9. 18 10.O(n3) 11. 5 12.7 13 6 14.42 15. 二叉排序树 16.41 17. 10，12，11，13，14，16 18.20 19. 15 第28页 ．A 9．A 10．C 11．C 19．A 20．C 21．A 29．B 30．D ．A ．B 8.3