树、图、查找、排序习题二
2008-12-07 01:43阅读：
第二部分 判断题
1、完全二叉树中，若一个结点没有左孩子，则它必然是叶子。
（
）
2、不使用递归，也可以实现二叉树的前序、中序和后序遍历。
（
）
3、先根遍历树和前序遍历与该树对应的二叉树，其结果不同。
（
）
4、在有序的顺序表和有序的链表上，均可以使用折半查找法来提高查找速度。（
）
5、对于n个记录的集合进行冒泡排序，所需要的平均时间是O(n) .
（ ）
6、采用分块查找方法，既能实现线性表所希望的较快的查找速度，又能适应动态变化的需要。
（ ）
7、存储无向图的相邻矩阵是对称的，因此只要存储相邻矩阵的下（或上）三角部分就可以了。
（ ）
8、若一个节点是某二叉树子树的中序遍历序列中的最后一个结点，则它必是该子树的前序遍历序列中的最后一个结点。
（
）
9、若连通网络上各边的权值均不相同，则该图的最小生成树是唯一的。 （
）
10、快速排序在任何情况下都比简单排序快。
11、邻接表法只能用于有向图的存储，而相邻矩阵对于有向图和无向图的存储都适用。（ ）
12、散列法存储的基本思想是由关键码的值决定数据存储地址。
（
）
13、堆排序的所需时间与待时间的记录个数无关。
（ ）
14、在哈夫曼编码中，当两个字符出现的频率相同时，其编码也相同，对于这种情况应该做特殊处理。
（
）
15、任何有向网络的拓扑排序结果是唯一的。
（
）
16、当所有的右子树的权值都相等时，用这些结点构造的二叉树的特点是只有右子树（ ）
17、对于n个记录的集合进行快速排序，所需要的平均时间是O(nlog2n)
（ ）
18、顺序文件是利用磁带的特有性质实现的，因此顺序文件只能存放在磁带中。（
）
19、对于处理大量数据的磁带而言，索引顺序存取方法是一种方便的文件组织方法。（
）
20、二叉树是树的特殊情形。
（
）
21、用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关。（ ）
22、有回路的图不能进行拓扑排序。
（
）
23、堆排序所需的时间与待排序的记录个数无关。
（
）
24、由树的前序中序遍历可以推导出后序遍历。
（
）
25、索引顺序文件的记录，在逻辑上按关键字的顺序排列，物理上也如此。 （
）
26、快速排序是一种稳定的排序方法。
（
）
27、树和二叉树是两类不同的树形结构。
（ ）
28、带权的连通无向图的最小生成树是唯一的。
（
）
29、后序遍历森林和中序遍历与该森林相对应的二叉树，其结果不同。
（ ）
30、对于n个记录的集合进行归并排序，所需平均时间为O(nlog2n).
（
）
31、直接访问文件也能顺序访问，但一般效率较差。
（ ）
32、用相邻矩阵法存储一个图所需的存储单元数目与图的边数有关。
（
）
33、装填因子是散列法的一个重要参数，它反映散列表的装满程序。
（
）
34、用一维数组存储二叉树时，总是以前序遍历顺序存储结点。
（ ）
35、将一棵树转换为二叉树后，根结点没有左子树。
（ ）
36、哈夫曼树是带权路径最短的树，路径上权值较大的结点离根较近。
（ ）
37、图结构是一种线性数据结构。
（ ）
38、磁盘上的顺序文件中插入新的记录时，必须复制整个文件。
（ ）
39、堆排序的堆中所有非终端结点的值均小于等于或大于等于左右子树的值。 （
）
40、由树转换成二叉树，其根结点的右子树总是空的。
（
）
41、前序遍历森林和前序遍历该森林对应的二叉，其结果不同。
（
）
42、存储无向图的相邻矩阵是对称的。
（
）
43、对于n个记录进行冒泡排序，所需要的平均时间是O(n).
（
）
44、在二叉树中插入结点，该二叉树便不再是二叉树。
（
）
45、当k>=1时，高度为k的二叉树至多有2k-1个结点。
（ ）
46、散列法的平均查找长度不随表中结点数目的增加而增加。
（ ）
47、用二分查找法对一个顺序表进行查找，这个顺序表可以是按各键值排好序的，也可以没有按键值排好序的。
（
）
48、用一维数组存储二叉树时，总是以前序遍历存储节点。
（ ）
49、连通分量是无向图中的极小连通子图。
（ ）
50、如果某种排序算法是不稳定的，则该方法没有实际应用价值。
（
）
51、索引顺序文件既能顺序访问，又能随即访问。
（
）
52、在有序的顺序表和有序的链表上，均可使用折半查找来提高查找速度。 （
）
53、在n个节点的无向图中，若边数大于n-1,则该图必是连通图。
（
）
54、强连通分量是有向图中的极大强连通子图。
（
）
55、中序遍历二叉排序树的结点就可以得到排好序的结点序列。
（ ）
56、一个无向图的邻接矩阵中各元素之和与图中边的条数相等。
（ ）
57、对于n个记录的集合进行快速排序，所需要的附加空间数为O(n)
（
）
58、外部排序与外部设备特性无关。
（
）
59、在索引顺序文件中插入新的记录时，必须复制整个文件。
（ ）
60、散列表结点中包含数据元素自身的信息，不包含任何指针。
（ ）
61、n个结点的有向图，若它有n(n-1)条边，则它一定是强连通图。
（
）
62、虽然信息项的序列的顺序不一样，但依次生成的二叉排序树却是一样的。 （
）
63、对于n个记录的集合进行快速排序，在最坏的情况下所需要的时间是O（n）（
）
64、有回路的图不能进行拓扑排序。
（
