数据结构 6-10章自测题及答案.pdf

数据结构6-10章自测题及答案--第1页

自测题（6-10章）

一、填空题

1、二叉树第i(i=1)层上至多有______个结点，深度为k(k=1)的二叉树至多有______个

结点。

2、对任何二叉树，若度为2的节点数为n，则叶子数n=______。

20

3、满二叉树上各层的节点数已达到了二叉树可以容纳的______，满二叉树也是______二叉

树，但反之不然。

4、具有n个结点的完全二叉树的深度为______。

5、具有n个结点的二叉树中,一共有________个指针域,其中只有________个用来指向结点

的左右孩子，其余的________个指针域为NULL。

6、二叉树有不同的链式存储结构，其中最常用的是________与________。

7、若二叉树的一个叶子是某子树的中根遍历序列中的第一个结点，则它必是该子树的后根

遍历序列中的________个结点。

8、由________转换成二叉树时，其根结点的右子树总是空的。

9、哈夫曼树是带权路径长度________的树，通常权值较大的结点离根________。

10、有m个叶子结点的哈夫曼树，其结点总数为________。

11、已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，

则该树中有________个叶子结点。

12、具有10个顶点的无向图，边的总数最多为________。

13、N个顶点的连通图的生成树含有________条边。

14、无向图的邻接矩阵是一个________矩阵，有向图的邻接矩阵不一定是________矩

阵。

15、一个具有n个顶点的完全无向图的边数为________，一个具有n个顶点的完全有向

图的弧数为________。

16、遍历图的基本方法有________优先有哪些信誉好的足球投注网站和________优先有哪些信誉好的足球投注网站两种。

17、在有向图的邻接矩阵上，由第i行可得到第________个结点的________，而由第j

列可得到第________个结点的________。

18、折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素

20，它将依次与表中元素________比较大小。

19、在各种查找方法中，平均查找长度与结点个数n无关的查找方法是________。

20、若在线性表中采用二分查找法查找元素，该线性表应该元素________，且采用

________结构。

21、对二叉排序树进行________遍历，可以得到该二叉树所有结点构成的有序序列。

二、单项选择题

1．以下说法错误的是()

①树形结构的特点是一个结点可以有多个直接前趋

②线性结构中的一个结点至多只有一个直接后继

③树形结构可以表达(组织)更复杂的数据

数据结构6-10章自测题及答案--第1页

数据结构6-10章自测题及答案--第2页

④树(及一切树形结构)是一种分支层次结构

2.深度为6的二叉树最多有()个结点

①64②63③32④31

3.设二叉树有n个结点，则其深度为()

①n-1②n③floor(logn)+1④无法确定