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

一、选择题1．已知一算术表达式的中缀形式为A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为()A．-A+B*C/DEB.-A+B*CD/EC．-+*ABC/DED.-+A*BC/DE2．在下述结论中，正确的是（）①只有一个结点的二叉树的度为0;②二叉树的度为2；③二叉树的左右子树可任意交换;④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。A．①②③B．②③④C．②④D．①④3.设森林F对应的二叉树为B，它有m个结点，B的根为p，p的右子树结点个数为n，森林F中第一棵树的结点个数是（）A．m-nB．m-n-1C．n+1D．条件不足，无法确定4．在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（）个A．4B．5C．6D．75．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）A．250B．500C．254D．505E．以上答案都不对6.设给定权值总数有n个，其哈夫曼树的结点总数为()A．不确定B．2nC．2n+1D．2n-17.一个具有1025个结点的二叉树的高h为（）A．11B．10C．11至1025之间D．10至1024之间8．深度为h的满m叉树的第k层有（）个结点。(1=k=h)A．mk-1B．mk-1C．mh-1D．mh-19．高度为K的二叉树最大的结点数为（）。A．2kB．2k-1C．2k-1D．2k-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）若用三位二进制数（0~7）对这个8个字母进行等长编码，则哈夫曼编码的平均码长是等长编码的百分之几？它使电文总长平均压缩多少？