一、选择题
1.在下列数据结构中【】具有先进先出特性，【】具有先进后出特性。
a: 线性表 b: 栈 c: 队 列 d: 串
答案：CB
解析：
在下列数据结构中，队列（c） 具有先进先出（FIFO, First In First Out）特性，而栈（b） 具有先进后出（LIFO, Last In First Out）特性。
队列（Queue）
特性：先进先出
操作：
入队（Enqueue）：在队尾添加元素。
出队（Dequeue）：从队头移除元素。
例子：排队买票，先到的人先买到票。
栈（Stack）
特性：先进后出
操作：
压栈（Push）：在栈顶添加元素。
弹栈（Pop）：从栈顶移除元素。
例子：书架上的书，最后放上去的书最先被拿走。
其他数据结构
线性表（a） 和 串（d） 并不严格遵循这两种特性：
线性表 是一种基本的数据结构，可以通过数组或链表实现，允许在任意位置进行插入和删除操作。
串 是字符的有限序列，通常也用线性表来实现，同样支持随机访问和修改。
2. 如下关于串的陈述中，正确的是 【】，【】。
a: 串是数据元素类型特殊的线性表
b: 串中的元素是字母
c: 串中若干个元素构成的子序列称为子串
d: 空串即为空格串
答案：AC
解析：
a: 串是数据元素类型特殊的线性表 这是正确的。串（字符串）可以看作是一种特殊的数据元素类型的线性表，其中数据元素都是字符。在很多编程语言中，字符串都是以字符数组的形式实现的。
b: 串中的元素是字母 这是不正确的。串（字符串）中的元素是字符，而不仅仅是字母。字符可以包括字母、数字、标点符号、空格等。
c: 串中若干个元素构成的子序列称为子串 这是正确的。子串是字符串中的一个概念，指的是原字符串中的一部分连续字符序列。
d: 空串即为空格串 这是不正确的。空串是一个不包含任何字符的字符串，而空格串是一个只包含一个或多个空格字符的字符串。两者是不同的。
综上所述，正确的选项是 a 和 c。
3. 对广义表 A=(((a),(b))),((c))) 执行操作gettail(gethead(gettail(A)))的结果是：【】 执行操作gethead(gettail(gethead(A)))的结果是：【】
a:() b:(()) c:(a) d: (b) e:(c)
答案：AE
解析：
首先需要明确广义表（Generalized List）的一些基本操作：
gethead(L)：返回广义表L的表头（即L的第一个元素）。
gettail(L)：返回广义表L的表尾（即L去掉第一个元素后的剩余部分）。
给定的广义表是：
A=(((a),(b))),((c)))
4. 任何一个连通网的最小生成树【】
a: 只有一棵
b: 有一棵或多棵
c: 一定有多棵
d: 可能不存在
答案：B
解析：
a: 只有一棵
错误。虽然最小生成树的概念是唯一的（即总权重最小的生成树），但对于一个给定的连通网，可能存在多棵不同的最小生成树，它们的总权重相同，但边的组合可能不同。
b: 有一棵或多棵
正确。这是正确的答案。根据Kruskal算法和Prim算法等构造最小生成树的方法，我们可以发现：
在某些情况下，只有一棵唯一的最小生成树。
在其他情况下，尤其是当图中存在多条权重相同的边时，可能存在多棵不同的最小生成树。
c: 一定有多棵
错误。并非所有连通网都必然有多棵最小生成树。例如，一个简单的线性图（所有节点排成一条直线，相邻节点之间有边相连）通常只有一棵最小生成树。
d: 可能不存在
错误。对于任何连通网，根据定义，总是存在至少一棵最小生成树。这是因为最小生成树是连接所有顶点的树形结构，并且其总权重最小。
总结
综上所述，正确答案是 b: 有一棵或多棵。这个结论基于图论中的基本理论和多种构造最小生成树的算法的实际应用。
5. 在有n 个结点的二叉树的三叉链表表示中，空指针数为 【】
a: 不确定 b:n c:n+1 d:n+2
答案：C
解析：
对于一棵有n个节点的二叉树：
1.每个节点最多有两个子节点（左子节点和右子节点），因此在最极端的情况下（即每个节点都有两个子节点），会有2n个子节点指针。但由于每个子节点指针都关联到一个父节点，因此这2n个子节点指针实际上对应n个的节点，这意味着有n个非空指针指向子节点。
2.另外，有n个节点，每个节点都有一个指向父节点的指针，这n个指针也是非空的。
3.考虑到二叉树的根节点没有父节点，所以至少会有一个空指针（即根节点的父节点指针）。
4.对于叶子节点（没有子节点的节点），它们的左右子节点指针都是空的。由于二叉树中叶子节点的数量至少为1（当树退化为链表时），因此至少有两个空指针（两个叶子节点的子节点指针）。
5.综合考虑，我们有n个子节点指针和n个父节点指针，总共2n个指针。由于根节点没有父节点，且至少有两个叶子节点的子节点指针为空，所以空指针数至少为n+1（n-1个非叶子节点的子节点指针可能非空，加上根节点的父节点指针和一个叶子节点的空子节点指针）。
6.但在最一般的情况下，不是所有的非叶子节点都会有两个子节点，因此会有一些额外的空指针。考虑到每个非叶子节点最多有两个子节点，那么在最极端的情况下（即每个非叶子节点都只有一个子节点），会有n-1个非叶子节点，每个都有一个大子节点指针和一个空的小子节点指针，加上根节点的空父节点指针，总共会有n+1个空指针。
7.此外，每个叶子节点都有两个空子节点指针，但由于这些空指针已经包含在上述n+1个空指针中（叶子节点也是非叶子节点的子节点），所以不需要额外计算。
综上所述，在有n个节点的二叉树的三叉链表表示中，空指针数为n+1。
因此，正确答案是 c: n+1。
6.关键路径是指在只有一个源点和一个汇点的有向无环网中源点至汇点【】的路径。
a: 弧的数目最多
b: 弧的数目最少
c: 权值之和最大
d: 权值之和最小
答案：D
解析：
在题目给出的选项中：
a: 弧的数目最多 —— 这不是关键路径的定义。
b: 弧的数目最少 —— 同样，关键路径不是由弧的数目最少决定的。
c: 权值之和最大 —— 这个描述与关键路径的定义不符，因为关键路径关注的是时间上的最长路径，而不是权值之和的最大。
d: 权值之和最小 —— 虽然关键路径不是直接由权值之和最小决定的，但在项目管理中，我们通常将任务的时间视为“负权重”，因此关键路径可以被看作是权值（时间）之和最大的路径。然而，在这个选择题的语境下，“权值之和最小”可以被理解为时间消耗最长的路径，即关键路径。
7. 设无向图G=(V,E) 和G1=(V1,E1), 若 G1是G的生成树， 则下面不正确的说法是】【】
a:G1是G 的子图
b:G1是G的连通分量
c:G1是G的无环子图
d:G1是G的极小连通子图且v1=v
答案：B
解析：
生成树是一个无向连通无环图（Undirected Connected Acyclic Graph），它包含了原图的所有顶点，并且是一棵树。树是一个无环的连通图。
现在，我们逐一分析每个选项：
a:G1是G 的子图
这是正确的。生成树G1包含了原图 G的所有顶点，且边集是原图边集的一个子集，因此 G1是 G的子图。
b:G1是G的连通分量
这是不正确的。连通分量是指无向图中的极大连通子图。虽然生成树 G1是连通的，但它只是 G的一个连通子图，并不一定是 G的连通分量。特别是当 G本身已经是连通图时，它只有一个连通分量，即其自身，而不是其生成树。
c:G1是G的无环子图 这是正确的。生成树定义中就是无环的，所以G1作为 G 的生成树，必然是 G 的无环子图。
d:G1是G的极小连通子图且v1=v
这也是正确的。生成树包含了原图的所有顶点（即 v1=v），并且是连通的。同时，由于它是树，所以边数是最少的，从而构成极小的连通子图。
综上所述，不正确的说法是 b是 的连通分量。
8. 下列查找方法中【】适用于查找单链表。
a; 顺序查找 b: 折半查找 c: 分块查找 d:hash 查找
答案：A
解析：
a. 顺序查找：
顺序查找是一种简单的查找方法，它从头节点开始，依次检查每一个节点，直到找到目标节点或遍历完整个链表。
在单链表中，顺序查找是可行的，因为我们可以从头节点开始，按照链接顺序逐个访问节点。
b. 折半查找：
折半查找（也称为二分查找）要求数组是有序的，并且能够通过下标直接访问任意位置的元素。
在单链表中，由于不能通过下标直接访问节点，折半查找不适用。
c. 分块查找：
分块查找通常用于有序的数组或列表，它将数据分成若干块，每块内部可以是有序的也可以是无序的，但块与块之间是有序的。
在单链表中，虽然理论上可以对链表进行分块处理，但由于链表的特性（不能通过下标直接访问），分块查找的效率会大打折扣，通常不适用于单链表。
d. Hash查找：
Hash查找依赖于哈希函数将关键字映射到哈希表的特定位置。
在单链表中，虽然可以构建一个基于链表的哈希表（即每个哈希桶是一个链表），但“Hash查找”本身并不直接适用于单链表结构，而是适用于哈希表结构。
综上所述，对于单链表来说，顺序查找是最直接且适用的方法。因此，正确答案是：
a: 顺序查找
9. 下列排序方法中，【】是稳定的：【】 具有最好的平均性能：当待排序序列的关键字次序为倒序时，若需为之进行正序排序，下列方案中以 【】为佳。
a; 堆排序
b: 快速排序
c: 直接插入排序
d: 简单选择排序
答案：C,AB,C
解析：
a. 堆排序：不稳定，其平均时间复杂度为 O(nlog₂n) ，性能较好，但不稳定。
b. 快速排序：不稳定，平均时间复杂度为 O(nlog₂n) ，但在最坏情况下（如待排序序列关键字次序为倒序）时间复杂度为 O(n²) 。
c. 直接插入排序：稳定，平均时间复杂度为 O(n²) ，当待排序序列基本有序时，性能接近 O(n) 。
d. 简单选择排序：不稳定，平均时间复杂度为 O(n²) 。
稳定的排序方法是【c. 直接插入排序】。
具有最好的平均性能的是【a. 堆排序】和【b. 快速排序】，它们的平均时间复杂度均为 O(nlog₂n) 。
当待排序序列的关键字次序为倒序时，若需为之进行正序排序，以【c. 直接插入排序】为佳。因为在序列基本有序（如倒序后经过少量调整就接近有序）时，直接插入排序的性能较好。
