习题答案.docVIP

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个结点，其中叶子结点的个数是（ ）。A250 B500 C254 D505 E以上答案都不对参考答案：E8在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（ ）个。A4 B5 C6 D7参考答案：C10具有10个叶结点的二叉树中有（ ）个度为2的结点。A8 B9 C10 D11参考答案：B53由3个结点可以构造出（ ）种不同的二叉树。A2 B3 C4 D5参考答案：D47引入二叉线索树的目的是（ ）。A加快查找结点的前驱或后继的速度 B为了能在二叉树中方便的进行插入与删除C为了能方便的找到双亲 D使二叉树的遍历结果唯一19将如下由三棵树组成的森林转换为二叉树。NPGHJMOLIKEDFBAC参考答案：HGDACJIBFEMPONKOL反过来，将一个二叉树转化成森林或树？（注意：转化成森林的结果和转化成树的结果不一样）21设某二叉树的前序遍历序列为ABCDEFGGI，中序遍历序列为BCAEDGHFI，试画出该二叉树。参考答案：AIDBECHFG27设二叉树T的存储结构如下： 1 2 3 4 5 6 7 8 9 10Lchild 0 0 2 3 7 5 8 0 10 1DataJ H F D B A C E G IRchild 0 0 0 9 4 0 0 0 0 0其中Lchild、Rchild分别为结点的左、右孩子指针域，Data为结点的数据域，若根指针T的值为6，试：(1)画出二叉树的逻辑结构；(2)写出按前序、中序、后序遍历该二叉树所得到的结点序列；(3)画出二叉树的后序线索树。参考答案：前序序列：ABCEDFHGIJ中序序列：ECBHFDJIGA后序序列：ECHFJIGDBA31假定用于通讯的电文仅有8个字母C1，C2，C8组成，各个字母在电文中出现的频率分别为5，25，3，6，10，11，36，4，试为这8个字母设计哈夫曼编码树。参考答案：各字母编码如下：c1:0110 c2:10 c3:0010 c4:0111 c5:000 c6:010 c7:11 c8:0011注意虽然哈夫曼树的带权路径长度是唯一的，但形态不唯一。33设T是一棵二叉树，除叶子结点外，其它结点的度皆为2，若T中有6个叶结点，试问：(1)树T的最大深度和最小可能深度分别是多少？(2)树T中共有多少非叶结点？(3)若叶结点的权值分别为1、2、3、4、5、6，请构造一棵哈曼夫树，并计算该哈曼夫树的带权路径长度wpl。参考答案：(1)最大深度6，最小深度4；(2)非叶结点数5；(3)哈夫曼树见下图，其带权路径长度wpl=51。34一棵深度为的满叉树有如下性质：第层上的结点都是叶子结点，其余各层上每个结点都有棵非空子树。若按层次顺序从开始对全部结点编号，问：(1)第层上有多少个结点？(2)编号为的结点的第个孩子结点（若存在）的编号是多少？(3)编号为的结点的双亲结点（若存在）的编号是多少？参考答案：(1)个(2)（）(3)（） 】2给出算法将二叉树表示的表达式二叉树按中缀表达式输出，并加上相应的括号。参考答案：本题是将符号算术表达式用二叉树表示的逆问题，即将二叉树表示的表达式还原成原表达式。二叉树的中序遍历序列与原算术表达式基本相同，差别仅在于二叉树表示中消除了括号。将中序序列加上括号就恢复原貌。当根结点运算符优先级高于左子树（或右子树）根结点运算符时，就需要加括号。int Precede(char optr1, char optr2) / 比较运算符级别高低，optr1级别高于optr2时返回1，相等时返回0，低于时返回-1 switch(optr1) case+:case-:if(optr2=+|optr2=-)return(0);else return(-1); case*:case/:if(optr1=*|optr2=/)return(0);else return(1); void 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) /输出右子树表示的算术表达式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中，本算法据此建立以二叉链表表示的完全二叉树BiTree 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。图的部分习题答案5n个结点的完全有向图含有边的数目（）。An*n n（n+1） Cn2 Dn*（n-1）参考答案：D15设图如右所示，在下面的5个序列中，符合深度优先遍历的序列有（ ）个。a e b d f c a c f d e b a e d f c b a e f d c b a e f d b cA5个 B4个 C3个 D2个参考答案：D21已知有向图G=(V,E)，其中V=V1,V2,V3,V4,V5,V6,V7，E=, ,，G的拓扑序列是（ ）。AV1,V3,V4,V6,V2,V5,V7 BV1,V3,V2,V6,V4,V5,V7CV1,V3,V4,V5,V2,V6,V7 DV1,V2,V5,V3,V4,V6,V7参考答案：A24在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（ ）。AG中有弧 BG中有一条从Vi到Vj的路径CG中没有弧 DG中有一条从Vj到Vi的路径参考答案：D26关键路径是事件结点网络中（ ）。A从源点到汇点的最长路径 B从源点到汇点的最短路径C最长回路 D最短回路参考答案：A37设有无向网如下，写出其邻接矩阵，并在此基础上按普里姆算法求最小生成树。参考答案：邻接矩阵：最小生成树：38试写出对如下有向无环图进行拓扑排序可能得到的所有拓扑序列。参考答案：每次输出一个入度为的顶点。、。39设有向网如下，用弗洛伊德算法求图中各对顶点间的最短路径。参考答案：35设有网如下，试求关键路径。参考答案：关键路径：v1v2v5v7关键路径：v1v3v6v732下图是带权的有向图G的邻接表表示法，求：（1）以结点V1出发深度遍历图G所得的结点序列；（2）以结点V1出发广度遍历图G所得的结点序列；（3）从结点V1到结点V8的最短路径；（4）从结点V1到结点V8的关键路径。参考答案：（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到V8的关键路径是V1-V6-V5-V3-V8，长97。29试利用Dijkstra算法求下图中从顶点a到其他个顶点间的最短路径，写出执行算法过程中各步的状态。参考答案：顶点a到顶点b，c，d，e，f，g间的最短路径分别是15，2，11，10，6，13。34对图示的AOE网络，计算各活动弧的e(ai)和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）顶点a到顶点i的简单路径：（a-b-e-i），（a-c-g-i），（a-c-b-e-i）。 数组20设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ ）。A13 B33 C18 D40参考答案：B23将一个A1.100，1.100的三对角矩阵，按行优先存入一维数组B1298中，A中元素A66,65（即该元素下标i=66，j=