(完整word版)哈工大1春《数据结构》考试题B.doc

班号

学号

姓名

哈工大2006年春季学期

《数据结构－B》试题

考试时间120分钟满分80分

题号

一

二

三

四

五

六

七

八

九

十

总分

分数

填空题（共13分，每两个空为1分）

在单链表中设置头节点的作用是。

N个顶点的连通有向图，其边的条数至少为。

后序线索二叉树的左线索指向其，右线索指向其。

广义表（a，（a，b），d，e，((I,j,),k)）的长度是________,深度是________。

对于一个具有n个结点的二元树，当它为一棵________二元树时具有最小高度，当它为一棵_______时，具有最大高度。

在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为______个。

设一棵完全二叉树具有1000个结点，则此完全二叉树有个叶子结点，有个度为2的结点，有个结点只有非空左子树，有个结点只有非空右子树。设一棵深度为6的满二叉树有个内部结点和个叶子。

设要将序列（Q,H,C,Y,P,A,M,S,R,D,F,X）中的关键码按字母序的升序重新排列，则：冒泡排序一趟扫描的结果是；初始步长为4的希尔排序一趟的结果是；快速排序一趟扫描的结果是。

深度为H的完全二叉树至少有个结点；至多有个结点；H和结点总数N之间的关系是。

给出下列广义表操作的结果：（1）GetHead【((a,b),(c,d))】===;（2）GetHead【GetTail【((a,b),(c,d))】】===;（3）GetHead【GetTail【GetHead【((a,b),(c,d))】】】===;

在二分插入排序算法中，要求被查找元素必须采用存储结构。

设F是一个森林，B是由F按照自然对应关系转换而得到的二叉树，F中有N个非终结结点，则B中右子数为空的结点有个。

简答题（共10分）

请简述图的深度优先有哪些信誉好的足球投注网站算法与宽度优先有哪些信誉好的足球投注网站算法的基本思想。（4分）

什么是二叉排序树？（3分）

请简述快速分类（即快速排序）的基本思想？（3分）

试设计一个算法，判断给定的二叉树BT是否是二叉排序树。（5分）

设某一通信系统由0～9十种字符组成，其出现的概率为:?={0.20,0.11,0.06,0.03,0.12,0.06,0.19,0.01,0.13,0.09},现用Huffman方法进行编码，请画出对应的Huffman树，并计算平均码长WPL（带权路径长度），给出每个字符的编码。（请按左子树根结点的权小于或等于右子树根结点的权的次序构造设计编码，左子树的编码为0，右子树的编码位1）。（8分）

已知某带权无向图的邻接矩阵对应的三元组压缩存储如右所示，假设邻接矩阵的行列均从1开始，第i行第j列表时第i个顶点与第j个顶点之间的关系。试分别以Prim算法和Kruskal算法求该无向图的最小生成树（假设以第一个顶点为起点，试画出其构造的每一步过程）。（8分）

用两个栈S1，S2模拟一个队列时，如何用栈的操作实现队列的插入、删除、判队空操作。请简述算法的基本思想。（6分）

若已知二叉树的先根和后根的遍历结果，可否构造出这株二元树？为什么？请举例说明（9分）

一线性表存储在带头结点的双向循环链表中，L为头指针。如下算法：

（1）说明该算法的功能。（3分）（2）在空缺处填写相应的语句。（4分）

voidunknown(BNODETP*L)

{

…

p=L-next;

q=p-next;

r=q-next；

while(q!=L)

{

while(p!=L)(p-dataq-data)

p=p-prior；

q-prior-next=r；

(1)______；

q-next=p-next；

q-prior=p；

(2)______；

(3)______；

q=r；

p=q-prior；

(4)______；

}

}

请编写完整的C++程序。如果矩阵A中存在这样的一个元素A[i,j]满足条件:A[i,