北京邮电大学测控专业数据结构习题解.ppt

考试时间及地点 3、本章介绍的内部排序方法中，哪几种是稳定的？哪几种是不稳定的？ 第9章 作业 稳定的排序方法：直接插入、起泡、归并、基数 不稳定的排序方法：希尔、快速、 简单选择、堆排序 《数据结构》考试题型 一、填空题（10分） 二、判断题（共10分） 三、单项选择题（共10分） 四、简答题（共10分） 五、简答题（15分） 六、简答题 （10分） 七、程序题（20分） 八、简答题（15分） * 北京邮电大学自动化学院 第六章 作业 一、单项选择题 1、由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法 。 （A）正确 （B）错误 24 12 37 45 53 93 2、某二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树一定是 。 （A）空或只有一个结点 （B） 完全二叉树 （C）二叉排序树 （D） 高度等于其节点数 B D 3、深度为5的二叉树至多有 个结点。 （A）16 （B）32 （C）31 （D）10 第五章 作业 4、根据使用频率为5个字符设计的赫夫曼编码不可能是 （A）111，110，10，01，00 （B）000，001，010，011，1 （C）100，11，10，1，0 （D）001，000，01，11，10 0 1 0 1 C C 二、填空题 1、树和二叉树的主要差别是（1） 树的结点个数至少为1，而二叉树的结点个数可以为 0（2）树中结点的最大度数没有限制，而二叉树结点的最大度数为2（3）树的结点无左、右之分，而二叉树的结点右左、右之分。 第五章 作业 2 4 5 3 6 7 1 8 2、深度为k的完全二叉树至少有 个结点，至多有 个结点，若按自上而下，从左到右次序给结点编号（从1开始），则编号最小的叶子结点的编号是 3、一棵二叉树的第i（i?1）层最多有 个结点；一棵有n（n0）个结点的满二叉树共有 个叶子结点和 个非叶子结点。 2k-1 2k-1 2k-2+1 2i-1 （n+1）/2 （n-1）/2 1、已知二叉树的先序、中序和后序序列分别如下，其中有一些看不清的字母用*表示，请构造出一棵符合条件的二叉树并画出该二叉树。 先序序列是：*BC**FG 中序序列是：CB*EAG* 后序序列是：*EDB*FA A B C D E F G H I 2、将右图所示的树转化为二叉树，并写出先序遍历，中序遍历和后序遍历的结果。 A B F C D G E A B C D E F G H I A B C D E F G H I A B C D E F G H I A B C D E F G H I A B C D E F G H I 加线：在兄弟之间加一连线 抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系， 旋转：以树的根结点为轴心，将整树顺时针转45° 先序：ABEFGCDHI 中序：EFGBCHIDA 后序：GFEIHDCBA 3、设给定权集w={2，3，4，7，8，9}，试构造关于w的一棵赫夫曼树，并求其加权路径长度WPL。 2 3 4 7 8 9 2 3 4 7 8 9 5 2 3 4 7 8 9 5 9 6、如何构造赫夫曼树？ 2 3 4 7 8 9 5 9 15 7 8 15 2 3 4 9 5 9 18 6、如何构造赫夫曼树？ 7 8 15 2 3 4 9 5 9 18 33 WPL=（9+7+8）*2+4*3+（2+3）*4=80 第七章 作业 一、单项选择题 1、一个有n个顶点的无向图最多有 条边。 （A）n （B）n（n-1） （C）n（n-1）/2 （D） 2n 2、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 倍。 （A）1/2 （B）1 （C）2 （D）4 3、关键路径是事件结点网络中 。 （A）从源点到汇点的最长路径 （B）最长的回路 （C）从源点到汇点的最短路径 （D）最