数据结构（山东联盟-青岛大学）章节测试课后答案2024春

第六章测试

1.树最合适用来表示（   ）。
A:元素之间具有分支层次关系的数据 B:元素之间无联系的数据 C:无序数据元素 D:有序数据元素
答案:A
2.一棵有n个结点的树的所有结点的度数之和为（   ）。
A:2n B:n-1 C:n+1 D:n 3.设树中某结点不是根结点，则离它最近的祖先结点是（      ）。
A:该结点本身      B:父结点的父结点 C:根结点 D:父结点 4.在二叉树中某一结点的深度为3,高度为4,该树的髙度至少为（          ）。
A:8 B:7 C:5 D:6 5.设一棵高度为h的满二叉树有n个结点，其中有m个叶结点，则（          ）。
A:h+m=2n B:m=h-1 C:n=h+m D:n=2^h-1 6.具有33个结点的完全二叉树，有（    ）个度为1的结点。
A:0 B:16 C:12 D:1 7.一颗有124个叶子结点的完全二叉树最多有（       ）个结点。
A:248 B:247 C:250 D:249 8.一颗有129个叶结点的完全二叉树最少有（   ）个结点。
A:254 B:257 C:258 D:255 9.如果二叉树T2是由一棵树T1转换而来的二叉树，那么T1中结点的先根序列对应T2的（     ）序列。
A:先序遍历           B:层次遍历 C:中序遍历           D:后序遍历           10.如果二叉树T2是由一棵树T1转换而来的二叉树，那么T1中结点的后根序列对应T2的（   ）序列。
A:中序遍历           B:后序遍历           C:先序遍历           D:层次遍历 11.一个深度为k且只有k个结点的二叉树，按照完全二叉树顺序存储的方式存放于一个一维数组A[n]中，那么n应至少是（）。
A:2^k-1 B:2^k C:2k+1 D:2k 12.二叉树的叶子结点在前序、中序和后序遍历过程中的相对顺序（  ）。
A:无法确定 B:发生改变 C:其余选项都不对 D:不发生改变 13.设n、m为一棵二叉树上的两个结点，在中序遍历序列中，n在m前的条件是（）。
A:n是m的祖先 B:n在m左方 C:n在m右方 D:n是m的子孙 14.在一棵二叉树中有两个结点n和m。在该二叉树的前序遍历序列中n在m之前，而在其后序遍历序列中n在m之后，则n和m的关系是（）。
A:n是m的左兄弟 B:n是m的右兄弟 C:n是m的子孙 D:n是m的祖先 15.前序序列与中序序列正好相反的非空二叉树是（）。
A:满二叉树 B:右单支树 C:左单支树 D:完全二叉树 16.在中序线索二叉树中，指针 t 所指结点的左子树为空的充要条件是（ ） 。
A:t->lchild== NULL B:t->ltag==1 C:t->ltag==1 且 t->lchild==NULL D:其余选项都不对 17.设森林F对应的二叉树为A，它有m个结点。A的根为p，p的右子树中结点个数为n，则森林F中第一棵树的结点个数是（）。
A:n+1 B:m-n C:无法确定 D:m-n-1 18.设F是一个森林，B是由F转换得到的二叉树，F中有n个非叶结点，则B中右指针域为空的结点有（）个。
A:n B:n-1 C:n+2 D:n+1 19.用n个权重构造出来的Huffman 树共有（ ）个结点。
A:2n B:n+1 C:2n+1 D:2n-1 20.设T是Huffman树，具有5个叶结点，树T的高度最高可以是（）。
A:5 B:4 C:3 D:6