哈尔滨工程大学考研-数据结构-6.doc

一、选择题1已知一算术表达式的中缀形式为 A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为( )A-A+B*C/DE B. -A+B*CD/E C-+*ABC/DE D. -+A*BC/DE2在下述结论中，正确的是（ ） 只有一个结点的二叉树的度为0; 二叉树的度为2； 二叉树的左右子树可任意交换; 深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A B C D3. 设森林F对应的二叉树为B，它有m个结点，B的根为p，p的右子树结点个数为n，森林F中第一棵树的结点个数是（ ）Am-n Bm-n-1 Cn+1 D条件不足，无法确定4在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（ ）个A4 B5 C6 D7 5一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ ）A 250 B 500 C254 D505 E以上答案都不对 6. 设给定权值总数有n 个，其哈夫曼树的结点总数为( ) A不确定 B2n C2n+1 D2n-17. 一个具有1025个结点的二叉树的高h为（ ）A11 B10 C11至1025之间 D10至1024之间8深度为h的满m叉树的第k层有（ ）个结点。(1=<k=<h) Amk-1 Bmk-1 Cmh-1 Dmh-19高度为 K的二叉树最大的结点数为（ ）。A2k B2k-1 C2k -1 D2k-1-110在下列存储形式中，哪一个不是树的存储形式？（ ）A双亲表示法 B孩子链表表示法 C孩子兄弟表示法 D顺序存储表示法二、判断题1二叉树是度为2的有序树。2完全二叉树中，若一个结点没有左孩子，则它必是树叶。3一棵树中的叶子数一定等于与其对应的二叉树的叶子数。4将一棵树转成二叉树，根结点没有左子树。 5二叉树中序线索化后，不存在空指针域。三、填空题1在二叉树中，指针p所指结点为叶子结点的条件是_。2 中缀式a+b*3+4*（c-d）对应的前缀式为_ _，若a=1，b=2，c=3，d=4，则后缀式db/cc*a-b*+的运算结果为_ _。3具有256个结点的完全二叉树的深度为_。4深度为k的完全二叉树至少有_ _个结点，至多有_ _个结点。5在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是_。四、应用题1假设在树中，结点x是结点y的双亲时，用(x,y)来表示树边。已知一棵树边的集合为：(i,m),(i,n),(b,e),(e,i),(b,d),(a,b),(g,i),(g,k),(c,g),(c,f),(h,l),(c,h),(a,c)用树形表示法画出此树，并回答下列问题：（1） 哪个是根结点？（2） 哪些是叶结点？（3） 哪个是g的双亲？（4） 哪些是g的祖先？（5） 哪些是g的孩子？（6） 哪些是e的子孙？（7） 哪些是e的兄弟？哪些是f的兄弟？（8） 结点b和n的层次各是多少？（9） 树的深度是多少？（10） 以结点c为根的子树的深度是多少？（11） 树的度数是多少？2试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。3已知一棵树为m的树中有n1个度为1的结点，n2个度为2的结点，nm个度为m的结点，问该树中有多少片叶子？4试找出分别满足下面条件的所有二叉树：（1）前序序列和中序序列相同； （2）中序序列和后序序列相同；（3）前序序列和后序序列相同； （4）前序、中序、后序序列均相同。5若二叉树中各结点的值均不相同，则由二叉树的前序序列和中序序列，或由其后序序列和中序序列均能惟一地确定一棵二叉树，但由前序序列和后序序列却不一定能惟一地确定一棵二叉树。（1）已知一棵二叉树的前序序列和中序序列分别为ABDGHCEFI和GDHBAECIF，请画出此二叉树。（2）已知一棵二叉树的中序序列和后序序列分别为BDCEAFHG和DECBHGFA，请画出此二叉树。（3）已知两棵二叉树前序序列和后序序列均为AB和BA，请画出这两棵不同的二叉树。6设用于通信的报文由字符集a,b,c,d,e,f,g,h中的字母构成，这8个字母在电文中出现的概率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10（1） 为这8个字母设计哈夫曼编码。（2） 若用三位二进制数（07）对这个8个字母进行等长编码，则哈夫曼编码的平均码长是等长编码的百分之几？它使电文总长平均压缩多少？