习题答案-(1)分析

1、1 .已知一算术表达式的中缀形式为A+B*C-D/E ,后缀形式为 ABC*+DE/-,其前缀形式为（ ）。A. -A+B*C/DE B. -A+B*CD/E C. -+*ABC/DE D. -+A*BC/DE参考答案：D3. 一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）。A. 250 B. 500 C. 254 D. 505 E.以上答案都不对参考答案：E8.在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（）个。A. 4 B. 5 C. 6 D. 7参考答案：C10.具有10个叶结点的二叉树中有（）个度为2的结点。A. 8 B

2、. 9 C. 10 D. 11参考答案：B）种不同的二叉树。D. 553.由3个结点可以构造出（A. 2 B. 3 C. 4参考答案：D47.引入二叉线索树的目的是（）。A .加快查找结点的前驱或后继的速度B.为了能在二叉树中方便的进行插入与删除C.为了能方便的找到双亲D.使二叉树的遍历结果唯一19.将如下由三棵树组成的森林转换为二叉树。M反过来，将一个二叉树转化成森林或树？（注意：转化成森林的结果和转化成树的结果不一样）21.设某二叉树的前序遍历序列为ABCDEFGGI ,中序遍历序列为 BCAEDGHFI ,试画出该二叉树。参考答案：27.设二叉树T的存储结构如下:12345678910L

3、child00237580101DataJHFDBACEGIRchild0009400000其中Lchild、Rchild分别为结点的左、右孩子指针域，Data为结点的数据域，若根指针T的值为6,试：（1）画出二叉树的逻辑结构；（2）写出按前序、中序、后序遍历该二叉树所得 到的结点序列；（3）画出二叉树的后序线索树。参考答案：前序序歹U: ABCEDFHGIJ 中序序歹U: ECBHFDJIGA 后序序歹U: ECHFJIGDBA31 .假定用于通讯的电文仅有8个字母C1, C2,，C8组成，各个字母在电文中出现的频率分别为5, 25, 3, 6, 10, 11, 36, 4,试为这8个字母设

4、计哈夫曼编码树。参考答案：c8 cl哈夫场国网科各字母编码如下：c1:0110 c2:10 c3:0010 c4:0111 c5:000 c6:010 c7:11 c8:0011注意虽然哈夫曼树的带权路径长度是唯一的，但形态不唯一。33 .设T是一棵二叉树，除叶子结点外，其它结点的度皆为 2,若T中有6个叶结点，试问:机T的最大深度和最小可能深度分别是多少？（2）T中共有多少非叶结点？（3）若叶结点的权值分别为1、2、3、4、5、6,请构造一棵哈曼夫树，并计算该哈曼夫树的带权路径长 度 wpl。参考答案：（1）最大深度6,最小深度4;（2）非叶结点数5;（3）哈夫曼树见下图，其带权路径长度wp

5、l=51。34 . 一棵深度为H的满k叉树有如下性质：第H层上的结点都是叶子结点，其余各层上每个结点都有k棵非空子树。若按层次顺序从1开始对全部结点编号，问：（1）第1层上有多少个结点？ （2）编号为p的结点的第1个孩子结点（若存在）的编号是多少？（3）编号为p的结点的双亲结点（若存在）的编号是多少？ 参考答案：ki个(2) ( 1 +(P-D * k ) + Ip + k -2：一 k2.给出算法将二叉树表示的表达式二叉树按中缀表达式输出，并加上相应的括号。参考答案：本题是将符号算术表达式用二叉树表示的逆问题，即将二叉树表示的表达式还原成原表 达式。 二叉树的中序遍历序列与原算术表达式基本相

6、同， 差别仅在于二叉树表示中消除了括号。将中序序列加上括号就恢复原貌。当根结点运算符优先级高于左子树(或右子树) 根结 点运算符时，就需要加括号。int Precede(char optr1, char optr2)/ 比较运算符级别高低， optr1 级别高于 optr2 时返回 1，相等时返回0，低于时返回-1switch(optr1)case +:case -:if(optr2= +|optr2= - )return(0);else return(-1);case * :case /:if(optr1= *|optr2= / )return(0);else return(1); void

7、 InorderExp (BiTree bt) /输出二叉树表示的算术表达式，设二叉树的数据域是运算符或变量名 int bracket;if(bt)if(bt-lchild!=null) bracket=Precede(bt-data,bt-lchild-data)/ 比较双亲与左子女运算符优先级 if(bracket=1) printf( ( ); InorderExp(bt-lchild);/ 输出左子女表示的算术表达式if(bracket=1)printf( ) );/加上右括号 printf(bt-data);/输出根结点if(bt-rchild!=null)/输出右子树表示的算术表达

8、式bracket=Precede(bt-data,bt-rchild-data) if (bracket=1)printf( “ (” );/右子女级别低，加括号InorderExp (bt-rchild); if(bracket=1)printf( “ )” ); / 结束 Inorder Exp4 有n 个结点的完全二叉树存放在一维数组 A1.n 中，试据此建立一棵用二叉链表表示的二叉树，根由 tree 指向。 参考答案： 方法一： BiTree Creat(ElemType A,int i)/n 个结点的完全二叉树存于一维数组 A 中， 本算法据此建立以二叉链表表示的完全二叉 树BiTr

9、ee tree;if (idata=Ai;if(2*in) tree-lchild=null;else tree-lchild=Creat(A,2*i);if(2*i+1n) tree-rchild=null;else tree-rchild=Creat(A,2*i+1); return (tree); /Creat 初始调用时i=1 。图的部分习题答案5 . n个结点的完全有向图含有边的数目()。A. n*nB. n (n+1) C. n/2D. n* (n-1)参考答案：D15.设图如右所示,在下面的5个序列中，符合深度优先遍历的序列有（）个。a e b d f ca c f d e ba

10、 e d f c b a e f d c bA. 5个B. 4个C. 3个参考答案：Da e f d b cD. 2个21. 已知有向图 G=(V,E), 其中V=V 1,V2,V3,V4,V5,V6,V7,E=, , , G 的拓 扑序列是（）。A. V1,V3,V4,V6,V2,V5,V7C. V1,V3,V4,V5,V2,V6,V7参考答案：A24.在有向图G的拓扑序列中，若顶点A . G 中有弧 C. G中没有弧参考答案：D26.关键路径是事件结点网络中(A.从源点到汇点的最长路径C.最长回路参考答案：AB. V1,V3,V2,V6,V4,V5,V7D. V1,V2,V5,V3,V4,

11、V6,V7Vi在顶点Vj之前，则下列情形不可能出现的是()。B . G中有一条从 Vi到Vj的路径D. G中有一条从 Vj到Vi的路径)。B.从源点到汇点的最短路径D.最短回路37.设有无向网如下，写出其邻接矩阵,并在此基础上按普里姆算法求最小生成树。参考答案:a0closedge0closedge00b1041o ：4c203200d30co325e40co40 ；cof50co50co_g_60co6厂coh70co72 ：5closedgeclosedgea0000b10010 ；0c200200d320320e437437f536536g6356：5h73473 -0邻接矩阵：臼434

12、 g 535国55009gQO QO OO00 OO OOoo CO 5最小生成树:oO55oO7654009QO7QO3ad00oCoCoC63C2oCJHjnaOO5OO2oO60 X：54X：X：60010020。32541950co60co725closedgeclosedge0001001002002003203204374535625.6063Q630730730closedge38.试写出对如下有向无环图进行拓扑排序可能得到的所有拓扑序列。参考答案：每次输出一个入度为0的顶点。abcdcfg、abcdfcg、abcfdeg。39.设有向网如下，用弗洛伊德算法求图中各对顶点间的最短

13、路径。黑力0123005co41co028235 0832oo60D0123005co41co02co2350732760g0123_0057415029235r 不32760参考答案:D(U012300541co02co235073_2_7_J&0D巧01230057415029235073276035.设有A OE网如下，试求关键路径。口 n。参考答案:关键路径 1 : V1fV?f Vf V7关键路径 2 : Vi一 V3一 V6一 V732.下图是带权的有向图 G的邻接表表示法，求：(1)以结点V1出发深度遍历图 G所得的结点序列;(2)以结点V1出发广度遍历图G所得的结点序列;(3)

14、从结点V1到结点V8的最短路径；(4)从结点V1到结点V8的关键路径。VIV2V34V5V67V8A26343188A512A33811511820N41567246712650八411n参考答案：(1) V1,V2,V3,V8,V5,V7,V4,V6;(2) V1,V2,V4,V6,V3,V5,V7,V8;(3) V1 到V8最短路径 56,路径为 V1-V2-V5-V7-V8;(4) V1 至UV8 的关键路径是 V1-V6-V5-V3-V8,长 97。29.试利用Dijkstra算法求下图中从顶点a到其他个顶点间的最短路径，写出执行算法过程中各步的状态。2参考答案：顶点a到顶点b, c,

15、 d, e, f, g间的最短路径分别是 15, 2, 11, 10, 6, 13。34.对图示的AOE网络，计算各活动弧的 e(a)和l(ai)的函数值，各事件(顶点)的 ve (Vj) 和vl (Vj)的函数值，列出各条关键路径。7.有向图的邻接表存储如下，要求： (1)画出其邻接矩阵存储；(2)写出图的所有强连通 分量；(3)写出顶点a到顶点i的全部简单路径。参考答案：(1)略。(注：邻接矩阵下标按字母升序：abcdefghi)(2)强连通分量：(a) , (d), ( h) , (b, e, i, f, c, g)(3)顶点的顶点 i 的简单路径:(a-b-e-i) , ( a-c-g-i ) , ( a-c-b-e-i )。数组20.设有一个10阶的对称矩阵A,采用压缩存储方式，以行序为主存储，&1为第一元素,其存储地址为1,每个元素占一个地址空间，则a85的地址为()。A. 13 B. 33 C. 18 D. 40参考答案：B23.将一个 A1.100 , 1.100的三对角矩阵，按行优先存入一维数组B1 - 298中，A中元素A 66,65 (