武汉软件工程职业学院软件技术专业大二2019数据结构二测1. 树形结构中元素之间存在一个对多个的关系。

[判断题] *对(正确答案)错2. 先根遍历树正好等同于按___遍历对应的二叉树 [单选题] *A.先根(正确答案)B.中根C.后根D.层次3. 将一棵树转成二叉树，根结点没有左子树。

[判断题] *对错(正确答案)4. 后根遍历树正好等同于按___遍历对应的二叉树。

[单选题] *A.先根B.中根(正确答案)C.后根D.层次5. 赫夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。

[判断题] *对(正确答案)错6. 赫夫曼树的结点个数不能是偶数。

[判断题] *对(正确答案)错答案解析：n个权值构成的赫夫曼树共有2n-1个节点，为奇数7. 树最适合用来表示() [单选题] *A、有序数据元素B、无序数据元素C、元素之间具有分支层次关系的数据(正确答案)D、元素之间无联系的数据8. 下面那个是完全二叉树（） *ABC(正确答案)D(正确答案)9. 以下关于树和二叉树的描述，正确的是() [单选题] *各结点的度均为2的树即为二叉树任一遍历序列可唯一确定一棵二叉树任何树都可以转换为唯一的二叉树与之对应(正确答案)树和二叉树都只能用链式存储实现10. 3个结点构成的二叉树，共有（）种 [单选题] *345(正确答案)611. 由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）。

[单选题] *24487253(正确答案)12. 若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。

[判断题] *对(正确答案)错13. 二叉树中每个结点的两棵子树的高度差等于1。

[判断题] *对错(正确答案)14. 二叉树中每个结点有两棵非空子树或有两棵空子树。

[判断题] *对错(正确答案)15. 二叉树中所有结点个数是2k-1-1，其中k是树的深度。

[判断题] *对错(正确答案)16. 二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。

[判断题] *对错(正确答案)17. 用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。

[判断题] *对(正确答案)错18. 具有12个结点的完全二叉树有5个度为2的结点。

[判断题] *对(正确答案)错19. 二叉树是非线性数据结构，所以(）。

[单选题] *A.它不能用顺序存储结构存储B.它不能用链式存储结构存储;C.顺序存储结构和链式存储结构都能存储;(正确答案)D.顺序存储结构和链式存储结构都不能使用20. 18.设T是一棵有n个顶点的树，下列说法不正确的是（）。

[单选题] *A.T有n条边(正确答案)B.T是连通的C.T是无环的D.T有n-1条边21. 14．高度为n的均衡的二叉树是指：如果去掉叶结点及相应的树枝，它应该是高度为n-1的满二叉树。

在这里，树高等于叶结点的最大深度，根结点的深度为0，如果某个均衡的二叉树共有2381个结点，则该树的树高为()。

[单选题] *A.10B.11(正确答案)C.12D.1322. 5．如果树根算第1层，那么一棵n层的二叉树最多有()个结点。

[单选题] *A.2n-1(正确答案)B.2nC.2n+1D.2n+123. 14、一个包含n个分支结点(非叶结点)的非空二叉树，它的叶结点数目最多为()。

[单选题] *A．2n+1B．2n-1C．n-1D．n+1(正确答案)24. 7．如果根结点的深度记为1，则一棵恰有2011个叶结点的二叉树的深度最少是()。

[单选题] *A．10B．11C．12(正确答案)D．1325. 9.已知一棵二叉树有10个节点，则其中至多有()个节点有2个子节点。

[单选题] *A.4(正确答案)B.5C.6D.726. 5．完全二叉树共有2*N-1个结点，则它的叶节点数是()。

[单选题] *A.N-1B.N(正确答案)C.2*ND.2*N-127. ⒗一棵具有5层的满二叉树中结点数为()。

[单选题] *A.31(正确答案)B.32C.33D.1628. ⒘如果根的高度为1,具有61个结点的完全二叉树的高度为()。

[单选题] *A.5B.6(正确答案)C.7D.829. 19．完全二叉树的顺序存储方案，是指将完全二叉树的结点从上至下、从左至右依次存放到一个顺序结构的数组中。

假定根结点存放在数组的1号位置，则第k 号结点的父结点如果存在的话，应当存放在数组的()号位置。

[单选题] *A.2kB.2k+1C.k/2下取整(正确答案)D.(k+1)/2下取整30. 20.已知6个结点的二叉树的先根遍历是123456(数字为结点的编号，以下同)，后根遍历是325641，则该二叉树的可能的中根遍历是() [单选题] *A.321465B.321546(正确答案)C.213546D.23146531. 20.已知7个结点的二叉树的先根遍历是1245637(数字为结点的编号，以下同)，中根遍历是4265173，则该二叉树的后根遍历是() [单选题] *A.4652731(正确答案)B.4652137C.4231547D.465317232. 13.二叉树T，已知其先根遍历是1243576(数字为结点的编号，以下同)，中根遍历是2415736，则该二叉树的后根遍历是()。

[单选题] *A.4257631B.4275631(正确答案)C.7425631D.427653133. 17．一棵二叉树的前序遍历序列是ABCDEFG，后序遍历序列是CBFEGDA，则根结点的左子树的结点个数可能是()。

[单选题] *A.2(正确答案)B.3C.4D.534. 6．如果一棵二叉树的中序遍历是BAC，那么它的先序遍历不可能是()。

[单选题] *A．ABCB．CBAC．ACB(正确答案)D．BAC35. 11.二叉树的（）第一个访问的节点是根节点。

[单选题] *A.先序遍历(正确答案)B.中序遍历C.后序遍历D.以上都是36. ⒗前序遍历序列与中序遍历序列相同的二叉树为()。

[单选题] *A.根结点无左子树B.根结点无右子树C.只有根结点的二叉树或非叶子结点只有左子树的二叉树D.只有根结点的二叉树或非叶子结点只有右子树的二叉树(正确答案)37. 13、表达式a*(b+c)-d的后缀表达式是： [单选题] *A.abcd*+-B.abc+*d-(正确答案)C.abc*+d-D.-+*abcd38. 9．前缀表达式“+3*2+512”的值是()。

[单选题] *A.23B.25C.37(正确答案)D.6539. 树最适合用来表示() [单选题] *A、有序数据元素B、无序数据元素C、元素之间具有分支层次关系的数据(正确答案)D、元素之间无联系的数据40. 在完全二叉树中，若一个结点是叶结点，则它没（）。

[单选题] *A、左子结点B、右子结点C、左子结点和右子结点(正确答案)D、以上说法都不对41. 有三个结点的二叉树有（）种形态。

[单选题] *345(正确答案)642. 下面那个是完全二叉树（） *ABC(正确答案) D(正确答案)43. 若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（） [单选题] *A、9B、11(正确答案)C、15D、不确定44. 在一棵二叉树上第5层的结点数最多是多少()个？ [单选题] *141516(正确答案)17答案解析：一棵二叉树，如果每个结点都是是满的，那么会满足2^(k-1)1。

所以第5层至多有2^(5-1)=16个结点！45. 深度为6的二叉树最多有（）个结点。

[单选题] *6463(正确答案)3231答案解析：见二叉树性质46. 一棵二叉树中共有70个叶子结点与80个度为1的结点，则该二叉树中的总结点数为()个？ [单选题] *218216219(正确答案)217答案解析：假设n表示二叉树的所有结点数，n0表示度为0的结点(叶子结点)，n1表示度为1的结点，n2表示度为2的结点：n=n0+n1+n2,又由二叉树性质：n2=n0-1，将n2带入得总结点数n=70+80+70-1=21947. 一棵具有5层的满二叉树中结点数为()。

[单选题] *A.31(正确答案)B.32C.33D.1648. 如果根的高度为1,具有61个结点的完全二叉树的高度为()。

[单选题] *A.5B.6(正确答案)C.7D.8答案解析：根据二叉树性质，从所给答案中取值计算。

49. 一个具有1025个结点的二叉树的高h为（）？ [单选题] *二叉树的高度的公式是什么？111011至1025之间(正确答案)10至1024之间答案解析：若该二叉树为完全二叉树，根据二叉树性质或计算某一深度的满二叉树的结点总数，向下取整log2(1025）+1≈log2(1024）+1=log2（2^10）+1=10+1=11；或深度为10的满二叉树有2^10-1=1024-1=1023,1025>1023,所以至少11层。

该二叉树有至少有11层。

层数最多时：每层一个结点，有1025层50. 已知一棵完全二叉树含有1001个结点，那么它有（）个度为2的结点。

[单选题] *250500(正确答案)501505答案解析：设二叉树中度为0的叶子结点个数为n0，度为1结点个数为n1，度为2结点个数为n2，于是n0+n1+n2=1001根据二叉树性质：n0=n2+1，代入得到，2n2+1+n1=1001由于完全二叉树的n1只能是0或者1，为满足2n2+1+n1=1001，只有n1=0时上式才能成立，因此n2=500，n0=501。

此题有时也考叶子结点数目。

51. 已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历是()。

[单选题] *A.acbedB.decabC.deabcD.cedba(正确答案)52. 二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK；中序遍历:HFIEJKG。

该二叉树根的右子树的根是： [单选题] *A.EB.FC.G(正确答案)D.H答案解析：注意审题，要求二叉树根右子树的根结点，由先序序列可知二叉树的根结点为E，所以在中序序列中E的左子树不需考虑。

53. 表达式a*(b+c)-d的后缀表达式是： [单选题] *A.abcd*+-B.abc+*d-(正确答案)C.abc*+d-D.-+*abcd54. 完全二叉树的顺序存储方案，是指将完全二叉树的结点从上至下、从左至右依次存放到一个顺序结构的数组中。

假定根结点存放在数组的1号位置，则第k号结点的父结点如果存在的话，应当存放在数组的()号位置。