第二部分  判断题

1、完全二叉树中，若一个结点没有左孩子，则它必然是叶子。             （     ）

2、不使用递归，也可以实现二叉树的前序、中序和后序遍历。             （     ）

3、先根遍历树和前序遍历与该树对应的二叉树，其结果不同。             （     ）

4、在有序的顺序表和有序的链表上，均可以使用折半查找法来提高查找速度。（     ）

5、对于n个记录的集合进行冒泡排序，所需要的平均时间是O(n) .        （     ）

6、采用分块查找方法，既能实现线性表所希望的较快的查找速度，又能适应动态变化的需要。                                                              （     ）

7、存储无向图的相邻矩阵是对称的，因此只要存储相邻矩阵的下（或上）三角部分就可以了。                                                              （     ）

8、若一个节点是某二叉树子树的中序遍历序列中的最后一个结点，则它必是该子树的前序遍历序列中的最后一个结点。                                        （     ）

9、若连通网络上各边的权值均不相同，则该图的最小生成树是唯一的。     （     ）

10、快速排序在任何情况下都比简单排序快。

11、邻接表法只能用于有向图的存储，而相邻矩阵对于有向图和无向图的存储都适用。（  ）

12、散列法存储的基本思想是由关键码的值决定数据存储地址。            （     ）

13、堆排序的所需时间与待时间的记录个数无关。                        （     ）

14、在哈夫曼编码中，当两个字符出现的频率相同时，其编码也相同，对于这种情况应该做特殊处理。                                                        （     ）

15、任何有向网络的拓扑排序结果是唯一的。                            （     ）

16、当所有的右子树的权值都相等时，用这些结点构造的二叉树的特点是只有右子树（   ）

17、对于n个记录的集合进行快速排序，所需要的平均时间是O(nlog₂n)     （     ）

18、顺序文件是利用磁带的特有性质实现的，因此顺序文件只能存放在磁带中。（     ）

19、对于处理大量数据的磁带而言，索引顺序存取方法是一种方便的文件组织方法。（    ）

20、二叉树是树的特殊情形。                                           （     ）

21、用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关。（   ）

22、有回路的图不能进行拓扑排序。                                     （     ）

23、堆排序所需的时间与待排序的记录个数无关。                          （     ）

24、由树的前序中序遍历可以推导出后序遍历。                            （     ）

25、索引顺序文件的记录，在逻辑上按关键字的顺序排列，物理上也如此。    （     ）

26、快速排序是一种稳定的排序方法。                                    （     ）

27、树和二叉树是两类不同的树形结构。                                  （     ）

28、带权的连通无向图的最小生成树是唯一的。                            （     ）

29、后序遍历森林和中序遍历与该森林相对应的二叉树，其结果不同。        （     ）

30、对于n个记录的集合进行归并排序，所需平均时间为O(nlog₂n).          （     ）

31、直接访问文件也能顺序访问，但一般效率较差。                        （     ）

32、用相邻矩阵法存储一个图所需的存储单元数目与图的边数有关。          （     ）

33、装填因子是散列法的一个重要参数，它反映散列表的装满程序。          （     ）

34、用一维数组存储二叉树时，总是以前序遍历顺序存储结点。              （     ）

35、将一棵树转换为二叉树后，根结点没有左子树。                        （     ）

36、哈夫曼树是带权路径最短的树，路径上权值较大的结点离根较近。        （     ）

37、图结构是一种线性数据结构。                                        （     ）

38、磁盘上的顺序文件中插入新的记录时，必须复制整个文件。              （     ）

39、堆排序的堆中所有非终端结点的值均小于等于或大于等于左右子树的值。  （     ）

40、由树转换成二叉树，其根结点的右子树总是空的。                     （     ）

41、前序遍历森林和前序遍历该森林对应的二叉，其结果不同。             （     ）

42、存储无向图的相邻矩阵是对称的。                                    （     ）

43、对于n个记录进行冒泡排序，所需要的平均时间是O(n).                 （     ）

44、在二叉树中插入结点，该二叉树便不再是二叉树。                      （     ）

45、当k>=1时，高度为k的二叉树至多有2^k-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、有回路的图不能进行拓扑排序。                                      （     ）

65、用直接选择排序方法分别对序列S1=（1，2，3，4，5，6，7）和序列S2=（7，5，3，2，4，1，6）进行排序，两者比较的次数不相同。                       （     ）

66、一棵哈夫曼树中不存在度为1的结点。                                （     ）

67、顺序文件适宜顺序存取，不适宜随机存取。                            （     ）

 

第三部分 填空题

1、3个顶点可以构成      棵不同形态的树。

2、如果要将序列{50，16，23，68，94，70，73}建成堆，则只需要把16与    交换。

3、利用直接选择排序算法对n个记录进行排序，最坏情况下，记录交换的次数为       。

4、设T为非空的二叉树，若T的先序序列和中序序列相同，则T的形态是          ，若T的先序序列和后序序列相同，则T的形态是           ，若T的中序序列和后序相同，则T的形态是          。

5、一个长为n的线性表，其排序时间性能最优为        。

6、如果含n个顶点的图是一个环，则它有        棵生成树。

7、对于7个元素组成的线性表{1，2，3，4，5，6，7}进行快速排序，具有最少比较和交换次数线性表初始排列为                            。

8、由二叉树的       序和           序遍历可以唯一确定一棵二叉树。

9、设G为n个顶点的无向连通图，则G至少具有      条边。

10、树形结构中节点a有4个兄弟，b是a的双亲，则b的度为   

11、设有n个结点的完全二叉树，顺序放在数组A[1..n]中，对任一结点A[i],若A[i]有双亲，是其双亲是         ；若A[i]有左孩子，则左孩子为      ；若A[i]有右孩子，则右孩子为        ；I值最大的分支节点是        。

12、不存在拓扑序列的有向图是          

13、实现动态分配和动态回收一个节点的两个标准过程是         和           。

14、三组数组A[c1..d1,c2..d2,c3..d3]共含有                    个元素。

15、散列法存储的基本思想是根据          来决定存储地址；冲突指的是       ，处理冲突的两种主要方法是              和                。

16、堆排序是一种          排序，它的一个基本问题是如何建堆；对含n个元素的序列进行排序时，其时间复杂度是              。

17、在树中，一个结点的直接孩子结点的个数称为该结点的             。

18、具有n个顶点的图的生成树中，含有          条边。

19、文件的基本操作主要是指           和             。

20、已知二叉树的前序遍历序列为ABDCEFG,中序遍历序列为DBCAFEG，则后序遍历序列为

                 。

21、在直接插入排序和选择排序中，若初始数据基本正序，则选用          ；若初始数据基本反序，则选用              。

22、具有144项的表分为         块最好；若每块的最佳长度为8，则平均查找长度为  。

23、在二叉树的第三层上至多有         个结点，深度为k的二叉树至多有    个结点。

24、在一个具有n个顶点的无向图中，要连通全部顶点至少需要      条边。

25、文件按其记录的类型不同分为         和             两类。

26、快速排序在最坏情况下的时间复杂度为           。

27、依次将每个记录插入到一个有序的文件中的排序方法称为            

28、装填因子是哈希表          的标志；装填因子越大，发生冲突的可能性越      ，查找时的比较次数越              。

29、文件的基本存取单位是                。

30、文件的检索方式有顺序存取、              和              三种方式。

31、若有向图G采用邻接表存储，则拓扑排序算法的时间复杂度为              

32、设有100个元素，用二分查找时，最大比较次数是          ，最小比较次数是      。

33、对于大文件的排序要研究在外设上的排序技术，称为                  。

34、堆的形状是一棵            树。

35、在文件“局部有序”或文件长度较小的情况下，最佳的内部排序方法是        

36、在内部排序中，平均比较次数最少的是       ，要求附加内存容量最大的是       

37、一棵有n个顶点的生成树，有且仅有           边

38、对于n个记录的集合进行冒泡排序，最坏情况下所需要的时间是          

39、完全二叉树的第I层上有          个结点。

40、n个顶点的强连通图至少有          条边，这样的有向图的形状是          

41、过程或函数自已调用自已称为           。

42、存放在磁盘上的键文件，也称为      ，指出索引文件中各记录的物理位置。

43、快速排序法在          情况下最容易发挥其长处，在       情况下最不利于发挥其长处。

44、执行         插入排序必须采取顺序存储方式

45、一个n*n的对称矩阵，如果以行或列为主序存入内存，则其容量为           。

46、树的根结点的层数为       ，其它任何结点层数等于其父母结点层数         。

47、对n个不同的排序码的元素进行冒泡排序，最少比较次数为        ，最多比较次数为           。

48、带权的         又称为网络。

49、设有向图有n个顶点和e条边，进行拓扑排序时，总的计算时间为         

50、采用折半查找方法进行查找时，数据文件应为        ，且限于        结构。

51、          主要用于磁盘文件，这类文件的存取是通过指定键值，然后算出所对应的记录中逻辑地址。

52、一个n*n的下三角矩阵A中的元素a_ij(I>=j,1<=I,j<=n)按行存于一个一维数组B[1..n(n+1)/2]中，对其中的任一元素a_ij，若在B中的位置为k,则k=             .

53、含有100个结点的树有       条边。

54、一棵二叉树有67个结点，这些结点的度要么是0，要么是2，这棵二叉树中度为2的结点有           个。

55、在一个无环有向图G中，若存在一条从顶点I到顶点j的弧，则在顶点的拓扑序列中，顶点I与顶点j的先后次序是              。

56、在一个无向图的邻接表中，若表结点的个数是m,则图中边的条数是          条。

57、设一个闭散表表的容量为m,用线性探测法解决冲突，要插入一个键值，若插入成功，至多要进行          次比较。

58、一棵哈夫曼树有19个结点，则其叶子结点的个数是           。

59、将两个长度分别为m和n（m>n）的排好序的表归并成一个排好序的表，至少要进行   次键值比较。

60、两个序列如下：L1={25,57,48,37,92,86,12,33},L2={25,37,33,12,48,57,86,92},用冒泡法分别对L1和L2进行排序，交换次数较少的序列是           。

61、将一棵有50个结点的完全二叉树从根结点开始，由根向下，每一层从左至右，顺序地存储在一个一维数组bt[1..50]中，这棵二叉树最下面一层上最左边一个结点存储在数组元素           中。

62、一个索引文件由                      两部分组成。