《北京邮电大学测控专业数据结构习题解》由会员分享，可在线阅读，更多相关《北京邮电大学测控专业数据结构习题解（37页珍藏版）》请在金锄头文库上搜索。
1、第六章 作业,一、单项选择题 1、由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法 。（A）正确 （B）错误,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,
2、C,C,二、填空题 1、树和二叉树的主要差别是（1） 树的结点个数至少为1，而二叉树的结点个数可以为 0（2）树中结点的最大度数没有限制，而二叉树结点的最大度数为2（3）树的结点无左、右之分，而二叉树的结点右左、右之分。,第五章 作业,2、深度为k的完全二叉树至少有 个结点，至多有个结点，若按自上而下，从左到右次序给结点编号（从1开始），则编号最小的叶子结点的编号是,3、一棵二叉树的第i（i1）层最多有 个结点；一棵有n（n0）个结点的满二叉树共有 个叶子结点和 个非叶子结点。,2k-1,2k-1,2k-2+1,2i-1,（n+1）/2,（n-1）/2,1、已知二叉树的先序、中序和后序序列分别
3、如下，其中有一些看不清的字母用*表示，请构造出一棵符合条件的二叉树并画出该二叉树。 先序序列是：*BC*FG 中序序列是：CB*EAG* 后序序列是：*EDB*FA,2、将右图所示的树转化为二叉树，并写出先序遍历，中序遍历和后序遍历的结果。,加线：在兄弟之间加一连线,抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系，,旋转：以树的根结点为轴心，将整树顺时针转45,先序：ABEFGCDHI,中序：EFGBCHIDA,后序：GFEIHDCBA,3、设给定权集w=2，3，4，7，8，9，试构造关于w的一棵赫夫曼树，并求其加权路径长度WPL。,6、如何构造赫夫曼树？,6、如何构造赫夫曼树？
4、,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）最短的回路,C,B,A,4、下面不正确的说法是 。 A、关键活动不按期完成就会影响整个工程的完成时间 B、任何一个关键活动提前完成，将使整个工程提前完成 C、所有关键活动都提前
5、，则整个工程提前完成 D、某些关键活动若提前完成，将使整个工程提前完成。,第七章 作业,B,二、填空题 1、一个图的 表示法是惟一的，而 表示法是不惟一的。,第七章 作业,2、在有n个顶点的有向图中，每个顶点的度最大可 达 。,邻接矩阵,邻接表,2（n-1）,1、设有向图G如下图所示，试给出： （1）该图的邻接矩阵； （2）该图的邻接表； （3）从V1出发的“深度优先”遍历序列； （4）从V1出发的“广度优先”遍历序列。,第七章 作业,答案:见前面课件内容,2、对下图的AOE网，求出： （1）每个事件的最早发生时间和最迟发生时间； （2）每个活动的最早开始时间和最迟开始时间； （3）画出关键活
6、动组成的图。对哪些活动提速，可使整个工期提前。,第7章作业,答案:见前面课件内容,3、某带权图的邻接矩阵表示为： 试完成下列要求：,第7章 思考题（不要求做）,（1）写出在该图上从顶点1出发进行深度优先遍历的顶点序列。 （2）画出该图的带权邻接表； （3）画出按普里姆算法构造最小生成树的示意图。,第3答案：,第7章 思考题,深度优先遍历的顶点序列：1，2，3，8，7，4，5，6,第8章 作业,一、单项选择题 1、采用顺序查找法查找长度为n的线性表时，每个元素的平均查找长度为 。（A）n （B）n/2 （C）（n+1）/2 （D） （n-1）/2,2、在一个长度为12的有序表，按折半查找法对该表
7、进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为 。（A）35/12 （B）37/12 （C）39/12 （D）43/12,3、查找效率最高的二叉排序树是 。（A）所有结点的左子树都为空的二叉排序树（B）所有结点的右子树都为空的二叉排序树（C）平衡二叉树 （D）没有左子树的二叉排序树,C,B,C,4、以下说法错误的是 。 A、散列法存储的基本思想是由关键码值决定数据的存储地址 B、散列表的结点中只包含数据元素自身的信息，不包含任何指针 C、装填因子是散列法的一个重要参数，它反映了散列表的装填程度 D、散列表的查找效率主要取决于散列表造表时选取的散列函数和处理冲突的方法,第8章 作
8、业,5、散列表的平均查找长度 。 A、与处理冲突方法有关与表长无关 B、与处理冲突方法无关与表的长度有关 C、与处理冲突方法有关且与表的长度有关 D、与处理冲突方法无关且与表的长度无关,B,A,二、填空题 1、设线性表（a1，a2，a500）元素的值由小到大排列，对一个给定的k值用折半法查找线性表，在查找不成功的情况下至多需比较 次。,第8章 作业,2、一个无序序列可以通过构造一棵 树而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。,3、在散列存储中，装填因子的值越大，则 的值越小，则,9,二叉排序,存取元素时发生冲突的可能性就越大；,存取元素时发生冲突的可能性就越小 。,1、输
9、入一个正整数序列40，28，6，72，100，3，54，1，80，91，38，建立一棵二叉排序树，然后删除结点72，分别画出该二叉树及删除结点72后的二叉树。,第8章 作业,第8章 作业,2、设有一组关键字19，01，23，14，55，20，84，27，68，11，10，77采用散列函数H（key）=key%13，采用开放地址法的线性探测再散列方法解决冲突，试在018的散列地址空间中对该关键字序列构造散列表。,19,01,23,14,55,20,84,27,68,11,10,77,一、单项选择题 1、排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排
10、序序列的正确位置上的方法，称为 （A）希尔排序 （B）冒泡排序 （C）插入排序 （D）选择排序,第9章 作业,2、在文件“局部有序”或文件长度较小的情况下，最佳内排序方法是 （ A）直接插入排序 （B）冒泡排序 （ C）直接选择排序 （ D）归并排序,直接插入排序,插入排序,4、在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是 （ A）希尔排序 （B）冒泡排序 （ C）插入排序 （ D）选择排序,第9章 作业,3、对给出的一组关键字14，5，19，20，11，19。若按关键字非递减排序，第一趟排序结果为14，5，19，20，11，19，问采用的排序算法是 （A）简单选择排序 （B
11、）快速排序 （C）希尔排序 （D）二路归并排序,选择排序,希尔排序,二、填空题 1、在对一组记录54，38，96，23，15，72，60，45，83进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较 次。,第9章 作业,2、每次直接或通过基准元素间接比较两个元素，若出现逆序排列时就交换它们的位置，此种排序方法叫做 排序； 每次使两个相邻的有序表合并成一个有序表的排序方法叫做排序。,3、 排序方法采用的是二分法的思想， 排序方法其数据的组织采用完全二叉树结构。,3,快速,归并,快速,堆,初始关键字： 47 33 61 82 72 11 25 57,第9章 作业,1、已知序
12、列47，33，61，82，72，11，25，57，请分别给出采用快速排序、2路归并排序和堆排序法对该序列作升序排序时的每一躺的结果。,一趟结果： 25 33 11 47 72 82 61 57,二趟结果： 11 25 33 47 57 61 72 82,三趟结果： 11 25 33 47 57 61 72 82,最后结果： 11 25 33 47 57 61 72 82,快速排序结果,三趟归并后： 11 25 33 47 57 61 72 82,2路归并排序结果,堆排序结果,初始关键字： 47 33 61 82 72 11 25 57,堆排序结果,堆排序结果,希尔排序结果,第9章 作业,2、已知序列49，38，65，97，76，13，27，48，55，4，请分别给出采用希尔排序（增量序列为5、3、1）、起泡排序和简单选择排序法对该序列作升序排序时的每一躺的结果。,初始： 49， 38， 65， 97， 76， 13， 27，48，55， 4,第1趟：13， 27 ，48， 55， 4， 49， 38，65，97，76,第1趟：13， 27 ，48， 55， 4， 49， 38，65，97，76,第2趟：13， 04 ，48， 38， 27， 49，55，65，97，76,
