数据结构与算法（仲恺农业工程学院）答案2023秋

第五章测试

1.设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为（ ）
A:6 B:7 C:8 D:5
答案:C
2.一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ ）
A:250 B:500 C:499 D:501 3.设给定权值总数有n 个，其哈夫曼树的结点总数为( )
A:2n B:2n+1 C:2n-1 D:不确定 4.一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有( )结点
A:2h-1 B:h+1 C:2h D:2h+1 5.将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度（ ）
A:5 B:6 C:4 D:7 6.对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，
同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用( )次序的遍历实现编号
A:中序 B:先序 C:后序 D:层序 7.树的后根遍历序列等同于该树对应的二叉树的( )
A:先序 B:后序 C:层序 D:中序 8.在下列存储形式中，哪一个不是树的存储形式？（ ）
A:孩子链表示法 B:孩子兄弟表示法 C:顺序存储结构 D:双亲表示法 9.已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（ ）。
A:不确定 B:FEDCBA C:CBEFDA D:CBEDFA 10.某二叉树的前序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。
A:任一结点无左子树 B:任一结点无右子树 C:空或只有一个结点 D:高度等于其结点数 11.若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则x的前驱为( )
A:X的右子树中最左结点 B:X的左子树中最右结点 C:X的左子树中最右叶结点 D:X的双亲 12.二叉树的第i层上最多含有结点数为（ ）。
A:  B:  C: D:  13.n个结点的线索二叉树上含有的线索数为（     ）
A:n+1 B:n C:2n D:n-1 14.由3 个结点可以构造出多少种不同的二叉树？（    ）
A:3 B:4 C:2 D:5 15.当一棵有n个结点的二叉树按层次从上到下，同层次从左到右将数据存放在一维数组 A[l..n]中时，数组中第i个结点的左孩子为（     ）
A:A[2i+1](2i+1=<n) B:A[i/2] C:A[2i](2i=<n)    D:无法确定 16.度为4，高度为h的树，（   ）。
A:至少有h+3个结点 B:至少有h+4个结点 C:至多有个结点 D:至少有4h个结点 17.用孩子链存储结构表示树，其优点之一是（   ）比较方便。
A:判断指定结点在第几层 B:计算机指定结点的度 C:判断两个结点是不是兄弟 D:找指定结点的双亲 18.根据使用频率为5个字符设计的哈夫曼编码不可能是（   ）。
A:000，001，010，011，1 B:001，000，01，11，10 C:111，110，10，01，00 D:100，11，10，1，0 19.一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（   ）。
A:CABDEFG B:ADBCFEG  C:DACEFBG           D:ABCDEFG 20.二叉树是度为2的有序树。（ ）
A:对 B:错 21.对于有N个结点的二叉树，其高度为。（ ）
A:对 B:错 22.二叉树的遍历只是为了在应用中找到一种线性次序。（ ）
A:对 B:错 23.一棵一般树的结点的前序遍历和后序遍历分别与它相应二叉树的结点前序遍历和后序遍历是一致的。（ ）
A:对 B:错 24.中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。（ ）
A:错 B:对 25.由一棵二叉树的前序序列和后序序列可以唯一确定它。（ ）
A:对 B:错 26.完全二叉树中，若一个结点没有左孩子，则它必是树叶。（ ）
A:错 B:对 27.将一棵树转成二叉树，根结点没有左子树。（ ）
A:错 B:对 28.一棵哈夫曼树的带权路径长度等于其中所有分支结点的权值之和。（ ）
A:对 B:错 29.当一棵具有n个叶子结点的二叉树的WPL值为最小时，称其树为Huffman树，且其二叉树的形状必是唯一的。（ ）
A:错 B:对