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

班号 学号 姓名 哈工大 2004 年 春 季学期 《数据结构－B》试 题 考试时间 120 分钟 满分 80 分 题号 一 二 三 四 五 六 七 实验报告成绩 总分 分数 填空题（共10分） 数组、栈和队列都是线性表的 存储结构，可以在数组中的 位置插入和删除元素；栈的主要特点是 ，即只能在 插入和删除元素；队列的主要特点是 ，即只能在 插入元素和 删除元素。 设有一个元素互异的、个数为n的输入序列，元素经过一个栈到达输出队列，并且元素一旦离开输入队列就不能再回到输入队列，则经过这个栈后可以得到 种不同的输出序列。 向一个长度为n的数组的第i个元素（1≤i≤n+1）之前插入一个元素时，需要向后移动 个元素。若在长度为n的数组中删除第i个元素（1≤i≤n）时，需要向前移动 个元素。 两个串相等的充分必要条件是 。 空串是 ，其长度等于 ，空格串是 ，其长度等于 。 已知二维数组A[m][n]采用行序为主方式存储，每个元素占k个存储单元，并且的一个元素的存储地址是LOC(A[0][0])，则A[i][j]的地址是 。 设单链表的结构由两个域组成，一个为data域，另一个为指针next域，则带有一个头结点的单链表head为空的条件是 ；在一个单链表中p所指向结点之后插入一个s所指结点时，应执行的两步操作依次是： 和 的操作。 用一维数组存放的一棵完全二叉树为：ABCDEFGHIJKL。那么用中序遍历的方法访问该完全二叉树的顺序为 。 简答题（共15分） 假设二叉树的存储结构采用左右孩子链表示方法，试设计递归算法，分别求出一棵给定的二叉树BT中的所有单孩子结点个数和树的高度。（只要求写出递归模型，不用给出程序代码） 有N个结点的二叉树，已知叶子结点个数为N0，写出求度为1的结点的个数N1的计算公式；如果此树是深度为K的完全二叉树，写出N为最小的公式。 请叙述图中的两种基本遍历算法：深度优先遍历算法（DFS）和广度优先遍历算法（BFS）的基本思想。 请请叙述Hash表的定义，在构造Hash函数的过程中应该注意什么，常用的Hash函数有哪些。请给出处理Hash冲突的方法。 第 1 页 （共 2 页） 试 题： 《数据结构（2004 春）－B》 班号： 姓名： 已知某字符串S共有6种字符，不妨设为a，b，c，d，e，f，各种字符分别出现7次，9次，12次，22次，23次，27次，对该字符串用｛0，1｝进行前缀编码，请回答下列问题：（10分） 该字符串的编码至少有多少位？试求出这六种字符的Huffman编码。 计算你所构造的Huffman树的带权路径长度，并画出Huffman树。 （以上两个问题，请按左子树根结点的权小于或等于右子树根结点的权的次序构造设计编码时，左子树的编码为0，右子树的编码位1）。 有一带权无向图的顶点集合为{ V1，V2，V3，V4，V5，V6，V7，V8 }。已知其邻接矩阵的三元组压缩存储示意图如右图所示（数组的脚标从1开始计数）：试回答下列问题： 请画出该无向图，并标明每个顶点的编号和每条边上的权，同时画出该图的邻接表存储示意图。 利用Prim算法或者Kruskal算法给出该图的所有可能的最小生成树。 根据你所设计的邻接表结构，分别写出从顶点V1出发，对该图进行深度优先遍历和广度优先遍历的顶点序列。（15分） 假设二叉树中所有非叶子结点都有左、右子树，则对此类二叉树： 试问：有n个叶子结点的这类二叉树，共有多少个结点？ 试证明，其中n为叶子结点的个数，表示第I个叶子结点所在的层次数（设根结点所在的层次数为1）。（10分） 设哈希表为Hash[13]，表长为m=13，现在采用一种新的散列法——双散列法来解决Hash冲突。散列（Hash）函数和再散列（ReHash）函数分别为： （注： ％是求余数运算（＝Mod）） i = 1，2