一、判断题

1、在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上一定相邻。

2、串可以采用顺序存储，但不能采用链式存储。

3、广义表是由零或多个原子或子表组成的有限序列，所以广义表可能为空表。

4、强连通分量是有向图中的极大强连通子图。

5、一个事件的最早开始时间与以该事件为尾的弧的活动最早开始时间相同。

6、用折半查找法对一个顺序表进行查找，这个顺序表必须是按关键字值有序排列的。

7、平衡二叉排序树上，任何一个结点的左、右子树的高度之差的绝对值不大于1。

8、任意一棵二叉树的叶子结点在其先序、中序、后序序列中的相对位置肯定不发生变化。

9、若一个叶子结点是某二叉树先序遍历序列中的最后一个结点，则它必是该二叉树中序遍历序列中的最后一个结点。

10、在拓扑排序序列中任意两个相继排列的顶点Vi和Vj，在有向无环图中都存在从Vi到Vj的路径。

二、单项选择题

11、对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度和在给定值为x的结点后插入一个新结点的时间复杂度分别为______。

    ……此处隐藏25293个字…… nbsp;应用邻接矩阵存储结构通过验证顶点数和边数的关系来判断是否一棵树的代码实现如下所示。

    这段代码的思路如下：

    ①首先判断无向图的边数是否等于顶点数减一，如果不等于则不是一棵树，直接返回false。

    ②接着定义一个bool类型的数组 visited，用于记录每个顶点是否被访问过，初始化为false。

    ③从第一个顶点开始深度优先遍历(dfs函数)，遍历时将当前顶点设为已访问，然后遍历与该顶点相邻的未访问过的顶点。

    ④如果遍历结束后仍有未访问过的顶点，则说明无法从第一个顶点遍历到所有顶点，直接返回false。

    ⑤最后返回true，说明该无向图是一棵树。

    总的来说，该代码采用深度优先遍历的方式遍历无向图，并通过判断边数是否为顶点数减一，以及是否存在环，来判断该无向图是否为一棵树。