A．指向最左孩子B．指向最右孩子C．空D．非空
（7）对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用（）遍历实现编号。
A．先序B.中序C.后序D.从根开始按层次遍历
（8）若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用（）遍历方法最合适。
A．前序B．中序C．后序D．按层次 （9）在下列存储形式中，（）不是树的存储形式
A．双亲表示法B．孩子链表表示法C．孩子兄弟表示法D．顺序存储表示法
（10）一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（）。 A．所有的结点均无左孩子B．所有的结点均无右孩子 C．只有一个叶子结点D．是任意一棵二叉树
（11）某二叉树的前序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。 A．空或只有一个结点B．任一结点无左子树 C．高度等于其结点数D．任一结点无右子树
（12）若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则X的前驱为（）。 A．X的双亲B．X的右子树中最左的结点
C．X的左子树中最右结点D．X的左子树中最右叶结点 （13）引入二叉线索树的目的是（）。
A．加快查找结点的前驱或后继的速度B．为了能在二叉树中方便的进行插入与删除 C．为了能方便的找到双亲D．使二叉树的遍历结果唯一 （14）线索二叉树是一种（）结构。
A．逻辑B．逻辑和存储C．物理D．线性
（15）设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有（）个。
A．n-1B．nC．n+1D．n+2 2．应用题
（1）试找出满足下列条件的二叉树
①先序序列与后序序列相同②中序序列与后序序列相同 ③先序序列与中序序列相同④中序序列与层次遍历序列相同 先序遍历二叉树的顺序是“根—左子树—右子树”，中序遍历“左子树—根—右子树”，后序遍历顺序是：“左子树—右子树―根＂，根据以上原则，本题解答如下：
（１）若先序序列与后序序列相同，则或为空树，或为只有根结点的二叉树
（２）若中序序列与后序序列相同，则或为空树，或为任一结点至多只有左子树的二叉树． （３）若先序序列与中序序列相同，则或为空树，或为任一结点至多只有右子树的二叉树．
（４）若中序序列与层次遍历序列相同，则或为空树，或为任一结点至多只有右子树的二叉树 （2）设一棵二叉树的先序序列：ABDFCEGH，中序序列：BFDAGEHC ①画出这棵二叉树。
②画出这棵二叉树的后序线索树。
③将这棵二叉树转换成对应的树（或森林）。
AC(1)(2)
（3）假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为，，，，，，。 HBD，E①试为这8个字母设计赫夫曼编码。
②试设计另一种由二进制表示的等长编码方案。 FG③对于上述实例，比较两种方案的优缺点。 解：方案1；哈夫曼编码 (先将概率放大100倍，以方便构造哈夫曼树。
w={7,19,2,6,32,3,21,10}，按哈夫曼规则：【[（2,3），6],(7,10)】,……19,21,32
（100） 01 （40）（60） 192132（28） 0101 （17） （11） 19 2132 0 1 7106（5） 0101 23 7 106 方案比较： 0 1 23 字母对应出现字母对应出现方案1的WPL＝2+++4+++5+=++= 编号 编码 频率 编号 编码 频率 方案2的WPL＝3+++++++=3 1 1100 1 000 结论：哈夫曼编码优于等长二进制编码 2 00 2 001 （4）已知下列字符A、B、C、D、E、F、G的权值分别为3、12、7、4、2、8，11，试填写出其对应哈夫曼3 11110 3 010 树HT的存储结构的初态和终态。 4 1110 4 011 初态: 5 10 5 100 终态 weight parent lchild rchild 6 101 3．算法设计题 1 3 0 0 0 以二叉链表作为二叉树的存储结构，编写2 12 0 0 0 7 weightparentlchild3 0 0 0 rchild 以下算法： （1）统计二叉树的叶结点个数。 3 0 8 00 4 41 0 0 intLeafNodeCount(BiTreeT) 12 1200 5 22 0 0 0 { 7 0 1000 6 83 0 0 if(T==NULL) 4 4 0 9 00 7 11 0 0 return0;c;}1 5 2 0 8 00 8 0 0 C1 C8 C6 8 0 1000 9 0 0 列C.树D．图 7 11 1100 10 0 0 0 8 5 0 9 51 11 0 0 （9）用邻接表表示图进行深度优12 13 （10）A．先次遍历 9 10 11 12 13 9 0 15 0 20 27 47 110 120 13 13 0 40 30 9 2 11 8 6 7 10 12 先遍历时，通常借助（）来实现算法。
A．栈B.队列C.树D．图 深度优先遍历类似于二叉树的（）。 序遍历B．中序遍历C．后序遍历D．层
（11）广度优先遍历类似于二叉树的（）。
A．先序遍历B．中序遍历C．后序遍历D．层次遍历 （12）图的BFS生成树的树高比DFS生成树的树高（）。 A．小B．相等C．小或相等D．大或相等
（13）已知图的邻接矩阵如图所示，则从顶点0出发按深度优先遍历的结果是（）。
?0?1??1??1?1??0??111110011000010010011101?01??00??10?10??01?10??0011000A．0243156
B．0136542 C．0134256 D．0361542
图邻接矩阵
（14）已知图的邻接表如图所示，则从顶点0出发按广度优先遍历的结果是（），按深度优先遍历的结果是（）。
A．0132B．0231 C．0321（15）下面（）方法可以判断出一个有向图是否有环。 D．0123
A．深度优先遍历B．拓扑排序C．求最短路径D．求关键路径 2．应用题
（1）已知如图所示的有向图，请给出： ①每个顶点的入度和出度； ②邻接矩阵； ③邻接表； ④逆邻接表。
图邻接表
图有向图
（2）已知如图所示的无向网，请给出： ①邻接矩阵； ②邻接表； ③最小生成树 a b c d e f g h → b 4 → c 3 → a 4 → c 5 → a 3 → b 5 → b 5 → c 5 → b 9 → d 7 → d 6 → e 3 → d 5 → f 2 → c 5 → d 4
5 5 7 3 2 6 6
→ d → d → e → f → g → h → g → e → h → f ^ ^ ^ ^
9 ^ 5 ^
图无向网
6 → g 5 → h 4^ （3）已知图的邻接矩阵如所示。试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。
（4）有向网如图所示，试用迪杰斯特拉算法求出从顶点a到其他各顶点间的最短路径，完成表。
图有向网
图邻接矩阵
D 终点 b 15 (a,b) c 2 (a,c) d 12 (a,d) e 15 (a,b) 15 (a,b) 15 (a,b) 15 (a,b) 15 (a,b) i=1 i=2 i=3 i=4 i=5 i=6 12 (a,d) 10 (a,c,e 11 (a,c,f,d) 10 (a,c,e) 11 (a,c,f,d) ∞ ) f ∞ ) g ∞ ∞ 16 (a,c,f,g) S 终点集 {a,c} {a,c,f} {a,c,f,e} 16 (a,c,f,g) 14 (a,c,f,d,g) 6 (a,c,f {a,c,f,e,d} {a,c,f,e,d,g} {a,c,f,e,d,g,b} （5）试对图所示的AOE-网：
①求这个工程最早可能在什么时间结束；
②求每个活动的最早开始时间和最迟开始时间； ③确定哪些活动是关键活动
图网 和最迟允许开始时间Vl。然后再计算各个【解答】按拓扑有序的顺序计算各个顶点的最早可能开始时间Ve活动的最早可能开始时间e和最迟允许开始时间l，根据l-e=0来确定关键活动，从而确定关键路径。
1 2 19 19 <1,3> 0 5 0 5 10 0 <3,2> 19 17 8 29 0 2 3 15 15 <2,4> 19 17 14 29 37 <2,5> 15 27 8 5 38 38 <3,5> 19 38 0 6 43 43 <4,6> 28 3<5,6> 3Ve Vl 0 0 <1,2> e l 7 0 1l-e 7 此工程最早完成时间为43。关键路径为<1,3><3,2><2,5><5,6> 3．算法设计题
（1）分别以邻接矩阵和邻接表作为存储结构，实现以下图的基本操作： ①增添一个新顶点v，InsertVex(G,v)；
②删除顶点v及其相关的边，DeleteVex(G,v); ③增加一条边
[j].adj=1; ++; }
returnOK; }dj=0; ;
returnOK;
}StatusDelete_Arc(MGraph&G,charv,charw)dj) {
相关推荐：
loading