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