1、B A C E D F N P G H J M O L I K 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 参考答案： D 3 一棵完全二叉树上有 1001 个结点，其中叶子结点的个数是 （ ）。 A 250 B 500 C 254 D 505 E以上答案都不对 参考答案： E 8在一棵三元树中度为 3 的结点数为 2 个，度为 2 的结点数为 1 个，度为 1 的结点数为 2个，则度为 0 的结点数为（ ）个 。 A 4 B 5 C
2、6 D 7 参考答案： C 10具有 10 个叶结点的二叉树中有（ ）个度为 2 的结点。 A 8 B 9 C 10 D 11 参考答案： B 53由 3 个结点可以构造出（ ）种不同的二叉树 。 A 2 B 3 C 4 D 5 参考答案： D 47 引入二叉线索树的目的是 （ ）。 A加快查找结点的前驱或后继的速度 B为了能在二叉树中方便的进行插入与删除 C为了能方便的找到双亲 D 使二叉树的遍历结果唯一 19将如下由三棵树组成的森林转换为二叉树。 参考答案： H G D A C J I B F E M P O N KO L 反过来，将一个二叉树转化成森林或树？（注意：转化成森林的结果和转化
3、成树的结果不一样） 21设某二叉树的前序遍历序列为 ABCDEFGGI，中序遍历序列为 BCAEDGHFI，试画出该二叉树。 参考答案： 27设二叉树 T 的存储结构如下 ： 1 2 3 4 5 6 7 8 9 10 Lchild 0 0 2 3 7 5 8 0 10 1 Data J H F D B A C E G I Rchild 0 0 0 9 4 0 0 0 0 0 其中 Lchild、 Rchild 分别为结点的左、右孩子指针域， Data 为结点的数据域 ，若根 指针 T的 值为 6， 试： (1)画出二叉树的逻辑结构 ； (2)写出按前序、中序、后序遍历该二叉树所得到的结点序列
4、； (3)画出二叉树的后序线索树。 参考答案： 前序序列： ABCEDFHGIJ 中序序列 ： ECBHFDJIGA 后序序列 ： ECHFJIGDBA 31 假定用于通讯的电文仅有 8 个字母 C1， C2， ， C8 组成，各个字母在电文中出现的频率分别为 5， 25， 3， 6， 10， 11， 36， 4，试为这 8 个字母设计哈夫曼编码树。 参考答案： A I D B E C H F G 各字母编码如下： c1:0110 c2:10 c3:0010 c4:0111 c5:000 c6:010 c7:11 c8:0011 注意 虽然哈夫曼树的带权路径长度是唯一的，但形态不唯一 。 33
5、设 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)第层上有多少个结点？
6、(2)编号为的结点的第个孩子结点（若存在）的编号是多少？ (3)编号为的结点的双亲结点（若存在）的编号是多少？ 参考答案： (1) 1ik 个 (2)（） (3) kkp 2（） 】 2给出算法将二叉树表示的表达式二叉树按中缀表达式输出，并加上相应的括号。 参考答案： 本题是将符号算术表达式用二叉树表示的逆问题，即将二叉树表示的表达式还原成原表达式。二叉树的中序遍历序列与原算术表达式基本相同，差别仅在于二叉树表示中消除了括号。将中序序列加上括号就恢复原貌。当根结点运算符优先级高于左子树（或右子树）根结点运算符时，就需要加括号。 int Precede(char optr1, char optr
7、2) / 比较运算符级别高低， 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)
8、 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(“ (” ); /右子女级别低，加括号 Inord
9、erExp (bt-rchild); if(bracket=1)printf(“ )” ); /结束 Inorder Exp 4有 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
10、) tree-rchild=null;else tree-rchild=Creat(A,2*i+1); return (tree); /Creat 初始调用时 i=1。 图的部分习题答案 5 n 个结点的完全有向图含有边的数目（ ）。 A n*n n（ n+1） C n 2 D n*（ n-1） 参考答案： D 15 设图如右所示， ， 在下面的 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 c A 5 个 B 4 个 C 3 个 D 2 个 参考答案： D 21 已知有
11、向图 G=(V,E) ， 其 中 V=V1,V2,V3,V4,V5,V6,V7 ，E=, ,， G 的拓扑序列是（ ）。 A V1,V3,V4,V6,V2,V5,V7 B V1,V3,V2,V6,V4,V5,V7 C V1,V3,V4,V5,V2,V6,V7 D V1,V2,V5,V3,V4,V6,V7 参考答案： A 24 在有向图 G的拓扑序列中，若顶点 Vi在顶点 Vj之前，则下列情形不可能出现的是（ ）。 A G 中有弧 B G 中有一条从 Vi 到 Vj 的路径 C G 中没有弧 D G 中有一条从 Vj 到 Vi 的路径 参考答案： D 26 关键路径是事件结点网络中（ ）。 A从
12、源点到汇点的最长路径 B从源点到汇点的最短路径 C最长回路 D最短回路 参考答案： A 37 设有无向网如下，写出其邻接矩阵，并在此基础上按普里姆算法求最小生成树。 参考答案： 邻接矩阵： 6456252363794567555553955434最小生成树： 38 试写出对如下有向无环图进行拓扑排序可能得到的所有拓扑序列。 参考答案： 每次输出一个入度为的顶点。、。 39设有向网如下，用弗洛伊德算法求图中各对顶点间的最短路径。 参考答案： 35 设有 网如下，试求关键路径。 参考答案： 关键路径： v1 v2 v5 v7 关键路径： v1 v3 v6 v7 32 下图是带权的有向图 G的邻接表
13、表示法，求： （ 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 到其他个顶点间的最短路径
14、，写出执行算法过程中各步的状态。 参考答案： 顶点 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
15、）， (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的地址为（ ）。 A 13 B 33 C 18 D 40 参考答案： B 23将一个 A1.100， 1.100的三对角矩阵，按行优先存入一维数组 B1 298中， A 中元素 A66,65（即该元素下标 i=66， j=65），在 B数组中的位置 K为（ ）。 A 198 B 195 C 197 D 196 参考答案： B 25有一个 100*90 的稀疏矩阵，非 0 元素有 10 个，设每个整型数占 2 字节，则用三元组表示该矩阵 时，所需的字节数是（ ）。 A 60 B 66 C 18000 D 33 参考答案： B 26算术表达式 a+b*(c+d/e)转为后缀表达式后为（ ） 。 A ab+cde/* B abcde/+*+ C abcde/*+ D abcde*/+ 参考答案： B
