哈工大2006春《数据结构》考试题-B.doc

数据结构2006年春季学期考试试题（B卷） 班号： 姓名： 班号学号姓名哈工大 2006 年 春 季学期数据结构B试 题 考试时间 120 分钟 满分 80 分题号一二三四五六七八九十总分分数一、 填空题（共13分，每两个空为1分）1 在单链表中设置头节点的作用是 。2 N个顶点的连通有向图，其边的条数至少为 。3 后序线索二叉树的左线索指向其 ，右线索指向其 。4 广义表（a，（a，b），d，e，( (I,j,), k) ）的长度是_, 深度是_。5 对于一个具有n个结点的二元树，当它为一棵_二元树时具有最小高度，当它为一棵_时，具有最大高度。6 在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为_个。7 设一棵完全二叉树具有1000个结点，则此完全二叉树有 个叶子结点，有 个度为2的结点，有 个结点只有非空左子树，有 个结点只有非空右子树。设一棵深度为6的满二叉树有 个内部结点和 个叶子。8 设要将序列（Q, H, C, Y, P, A, M, S, R, D, F, X）中的关键码按字母序的升序重新排列，则：冒泡排序一趟扫描的结果是 ；初始步长为4的希尔排序一趟的结果是 ；快速排序一趟扫描的结果是 。9 深度为H 的完全二叉树至少有 个结点；至多有 个结点；H和结点总数N之间的关系是 。10. 给出下列广义表操作的结果：（1） GetHead【(a,b),(c,d)】= ; （2） GetHead【GetTail【(a,b),(c,d)】= ; （3） GetHead【GetTail【GetHead【(a,b),(c,d)】= ;11. 在二分插入排序算法中，要求被查找元素必须采用 存储结构。12. 设F是一个森林，B是由F按照自然对应关系转换而得到的二叉树，F中有N个非终结结点，则B中右子数为空的结点有 个。二、 简答题（共10分）1、 请简述图的深度优先搜索算法与宽度优先搜索算法的基本思想。（4分）2、 什么是二叉排序树？（3分）3、 请简述快速分类（即快速排序）的基本思想？（3分）三、 试设计一个算法，判断给定的二叉树BT是否是二叉排序树。（5分）四、 设某一通信系统由09十种字符组成，其出现的概率为: w=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分）void unknown (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中存在这样的一个元素Ai,j满足条件:Ai,j是第i行中值最小的元素,且又是第j列中值最大的元素，则称之为该矩阵的一个马鞍点。请编程计算出m*n的矩阵A的所有马鞍点。（6分）十、 设哈希表为Hash13，表长为m=13，现在采用一种新的散列法双散列法来解决Hash冲突。散列（Hash）函数和再散列（ReHash）函数分别为： （注： 是求余数运算（Mod） i = 1，2，m1；其中函数REV（x）表示颠倒10进制数x的各位，如REV(37) = 73，REV(9) = 9，REV(10) = 1等。若插入的关键字依次为序列2，8，31，20，19，18，53，27中的关键字（假设初始ha