数据结构作业6.ppt

选择题 1.表达式x*(y-z)+u的逆波兰式（后缀表达式）表示是（　　）。 A）xyzuu-+ B）xyz-*u+ C）xyz*-u+ D）+-*xyzu 综合题 1．设有表达式：a*(b-c)/d+f/(g+h*i)，试给出此表达式的下面结果： ①二叉树表示； ②逆波兰式表示；③中缀表示； 数据结构第六次作业 B 规则：如表达式为数或者简单变量，则相应二叉树中只有一个根节点,其数据域存储此表达式信息；如表达式=（第1操作数）（运算符）（第2操作数），则相应的二叉树中以左子树表示第1操作数，右子树表示第2操作数，根节点的数据域存储运算符，操作数本身又可以为表达式。 ②逆波兰式表示(后缀即为左右根)： abc-*d/fghi*+/+ ③中缀表示(即为左根右)： a*b-c/d+f/g+h*i 3．已知下列字符A、B、C、D、E、F、G的权值分别为3、12、7、4、2、8、11，试求对应哈夫曼树。 步骤如下： (1) 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)； (2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和； (3)从森林中删除选取的两棵树，并将新树加入森林； (4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。 5.28 Build the Huffman coding tree and determine the codes for the following set of letters and weights: Letter A B C D E F G H I J K L Frequency 2 3 5 7 11 13 17 19 23 31 37 41 What is the expected length in bits of a message containing characters for this frequency distribution? 209 / \ 83 126 / \ / \ l 42 55 71 / \ / \ / \ H I 24 J 34 K / \ / \ E F 17 G / \ D 10 / \ 5 C / \ A B l 00 h 010 i 011 e 1000 f 1001 j 101 d 11000 a 1100100 b 1100101 c 110011 g 1101 k 111 其中F代表总频度或权值,n代表总个数,li代表编码长度,fi代表频度 本题中长度为?3.23445? 5.25 Show the max-heap that results from running build Heap o