数据结构

既然要学索性学个彻底

1．求整数 $ n $（$ n $）阶乘的算法如下，其时间复杂度是：

int fact(int n){
    if (n <= 1) 
        return 1;
    return n * fact(n - 1);
}

A. $ O(_2 n) $

B. $ O(n) $

C. $ O(n _2 n) $

D. $ O(n^2) $

解答：

此题中使用了递归算法。递归边界为 $ n $，每次递归调用时，输入的 $ n $ 减 1，因此调用次数与 $ n $ 成线性关系。每次递归仅执行一次乘法操作，因此时间复杂度为 $ O(n) $。

答案：B

2．已知操作符包括 `+`、`-`、``、`/`、`(` 和 `)`。将中缀表达式 `a+b-a((c+d)/e-f)+g` 转换为等价的后缀表达式 `ab+acd+e/f-*-g+` 时，用栈来存放暂时还不能确定运算次序的操作符，若栈初始时为空，则转换过程中同时保存在栈中的操作符的最大个数是：

A．5

B．7

C．8

D．11

解答：

使用栈来处理中缀表达式转换为后缀表达式，运算符栈用于保存暂时无法确定次序的运算符。

3．若一棵二叉树的前序遍历序列为 `a, e, b, d, c`，后序遍历序列为 `b, c, d, e, a`，则根结点的孩子结点：

A. 只有 `e`

B. 有 `e`、`b`

C. 有 `e`、`c`

D. 无法确定

解答：

前序遍历序列：a, e, b, d, c
后序遍历序列：b, c, d, e, a

根结点是 a，前序遍历根结点之后的第一个结点是 e，它是 a 的直接孩子。从后序遍历可知 e 是所有其他结点（b, c, d）的祖先，因此根结点的唯一直接孩子是 e。

答案：A

4. 平衡二叉树节点总数

题目：
若平衡二叉树的高度为 6，且所有非叶节点的平衡因子均为 1，则该平衡二叉树的节点总数为：

A. 10
B. 20
C. 32
D. 33

答案： B. 20

解释：
对于高度为 $N$ 的平衡二叉树，节点总数的递推关系为：

$ C_N = C_{N-1} + C_{N-2} + 1 $

其中 $C_2 = 2$。
根据这个关系，计算节点总数：
- $C_3 = C_2 + C_1 + 1 = 2 + 1 + 1 = 4$
- $C_4 = C_3 + C_2 + 1 = 4 + 2 + 1 = 7$
- $C_5 = C_4 + C_3 + 1 = 7 + 4 + 1 = 12$
- $C_6 = C_5 + C_4 + 1 = 12 + 7 + 1 = 20$

因此，平衡二叉树的节点总数为 20。

5. 有向图的广度优先遍历时间复杂度

题目：
对有 $n$ 个节点、$e$ 条边且使用邻接表存储的有向图进行广度优先遍历，其算法时间复杂度是：

A. O(n)
B. O(e)
C. O(n + e)
D. O(n * e)

答案： C. O(n + e)

解释：
广度优先遍历（BFS）需要使用队列实现。对于邻接表存储结构：

遍历所有节点时，每个节点都会被访问一次，时间复杂度为 $O(n)$。
在遍历每个节点的邻接点时，每条边也会被访问一次，时间复杂度为 $O(e)$。

因此，广度优先遍历的总时间复杂度为 $O(n + e)$。

6. 有向图的拓扑排序

题目：
若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图拓扑序列的结论是：

A. 存在，且唯一
B. 存在，且不唯一
C. 存在，可能不唯一
D. 无法确定是否存在

答案： C. 存在，可能不唯一

解释：
当邻接矩阵的主对角线以下的元素均为零时，说明该有向图是一个无环图（DAG）。无环图一定存在拓扑序列。但对于拓扑序列的唯一性，可能存在多个拓扑排序。

例如，考虑下列邻接矩阵：

$ \[\begin{bmatrix} 0 & 1 & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \\ \end{bmatrix}\]

该图有两个拓扑序列，因此可以得出结论：存在拓扑序列，但不一定唯一。

总结：

对于任一有向图，如果其邻接矩阵中主对角线以下的元素均为零，则存在拓扑序列（可能不唯一）。

以下是问题的详细题目、答案及解释。

7. Dijkstra 算法最短路径

题目：
对如下有向带权图，若采用迪杰斯特拉（Dijkstra）算法求从源点 $a$ 到其他各顶点的最短路径，则得到的第一条最短路径的目标顶点是 $b$，第二条最短路径的目标顶点是 $c$，后续得到的其余各最短路径的目标顶点依次是：

A. $d, e, f$
B. $e, d, f$
C. $f, d, e$
D. $f, e, d$

答案： C. $f, d, e$

解释：
采用 Dijkstra 算法进行最短路径计算的过程如下：

综上所述，后续目标顶点依次是 $f, d, e$。

8. 最小生成树的性质

题目：
下列关于最小生成树的叙述中，正确的是：

Ⅰ．最小生成树的代价唯一
Ⅱ．所有权值最小的边一定会出现在所有的最小生成树中
Ⅲ．使用普里姆（Prim）算法从不同顶点开始得到的最小生成树一定相同
Ⅳ．使用普里姆算法和克鲁斯卡尔（Kruskal）算法得到的最小生成树总不相同

A. 仅Ⅰ
B. 仅Ⅱ
C. 仅Ⅰ、Ⅲ
D. 仅Ⅱ、Ⅳ

答案： A. 仅Ⅰ

解释：

关于叙述 I：
最小生成树的代价是唯一的，因为所有边的权值不同。若存在权值相同的边，可能存在多个最小生成树，但其代价仍然相同。因此，I 正确。
关于叙述 II：
如果权值最小的边有多条且形成环状，则这些边可能不会出现在某棵最小生成树中，因此 II 错误。
关于叙述 III：
假设有 $N$ 个节点构成环，$N-1$ 条边权值相等，则从不同顶点开始普里姆算法可能得到不同的最小生成树，因此 III 错误。
关于叙述 IV：
当最小生成树唯一时（各边的权值不同），普里姆算法和克鲁斯卡尔算法得到的最小生成树是相同的，因此 IV 错误。

综上所述，正确的选项是仅 $I$，即答案 A。

9. B-树的删除操作

题目：
已知一棵3阶B-树，如下图所示。删除关键字 $78$ 得到一棵新B-树，其最右叶节点中的关键字是：

A. $60$
B. $60, 62$
C. $62, 65$
D. $65$

答案： D. $65$

解释：
在 B-树的删除操作中，若删除的关键字是叶子节点的关键字（如 $78$），且其所在节点的关键字个数为 $1$，该节点的左兄弟节点的关键字个数大于等于 $ - 1 = 1$，则可以进行“兄弟借”的操作。

具体步骤如下：

确定删除：删除关键字 $78$，此时对应的节点是叶子节点。
“兄弟借”操作：
- 从左兄弟节点中借出最大关键字（假设为 $65$），并将该关键字上移至父节点。
- 将父节点中大于 $65$ 的关键字下移到被删除节点中。
更新后状态：
- 删除后新叶节点中包含关键字 $60$ 和 $65$。
- 所以最右叶节点中的关键字是 $65$。

综上所述，答案为 D. $65$。

10. 排序方法中的确定位置

题目：
在内部排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中，每一趟排序结束都至少能够确定一个元素最终位置的方法是：

Ⅰ．简单选择排序
Ⅱ．希尔排序
Ⅲ．快速排序
Ⅳ．堆排序
Ⅴ．二路归并排序

A. 仅Ⅰ、Ⅲ、Ⅳ
B. 仅Ⅰ、Ⅲ、Ⅴ
C. 仅Ⅱ、Ⅲ、Ⅳ
D. 仅Ⅲ、Ⅳ、Ⅴ

答案： A. 仅Ⅰ、Ⅲ、Ⅳ

解释：

简单选择排序：每次选择未排序列中的最小元素放入其最终位置，因此每一趟结束时都有一个元素确定位置，符合条件。
希尔排序：对划分的子表进行排序，未必能保证每一趟结束时确定一个元素的最终位置，因此不符合条件。
快速排序：每一趟排序结束后都会将枢轴元素放到最终位置，因此符合条件。
堆排序：在构建大根堆的过程中，每一趟确定了堆顶元素（即最大元素）的最终位置，因此符合条件。
二路归并排序：虽然每趟会归并成局部有序，但未必能确定元素的最终位置，因此不符合条件。

综上所述，符合条件的排序方法是简单选择排序、快速排序和堆排序，答案为 A. 仅Ⅰ、Ⅲ、Ⅳ。

11. 折半插入排序与直接插入排序的区别

题目：
对一待排序序列分别进行折半插入排序和直接插入排序，两者之间可能的不同之处是：

A. 排序的总趟数
B. 元素的移动次数
C. 使用辅助空间的数量
D. 元素之间的比较次数

答案： D. 元素之间的比较次数

解释：

排序的总趟数：直接插入排序和折半插入排序的总趟数均为 $n-1$，因此此选项不正确。
元素的移动次数：两种排序方法在移动元素时都取决于初始序列，移动次数相同，因此此选项不正确。
使用辅助空间的数量：两者都是原地排序，使用的辅助空间都是 $O(1)$，因此此选项不正确。
元素之间的比较次数：
- 直接插入排序：使用顺序查找法，比较次数与初始序列有关，最坏情况下为 $O(n^2)$。
- 折半插入排序：使用折半查找法，比较次数与序列初态无关，为 $O(n \log n)$。

因此，两者在元素之间的比较次数上是不同的，答案为 D. 元素之间的比较次数。

以下是问题的详细题目、答案及解释。

41. 有序表合并问题

题目：
设有 6 个有序表 A、B、C、D、E、F，分别含有 10、35、40、50、60 和 200 个数据元素，各表中元素按升序排列。要求通过 5 次两两合并，将 6 个表最终合并成 1 个升序表，并在最坏情况下比较的总次数达到最小。请问答下列问题：
（1）给出完整的合并过程，并求出最坏情况下比较的总次数。
（2）根据你的合并过程，描述 N（N≥2）个不等长升序表的合并策略，并说明理由。

解答：

（1）合并过程及最坏情况下比较的总次数：

对于长度分别为 $m$ 和 $n$ 的两个有序表的合并，最坏情况下需要进行 $m+n-1$ 次比较。为了最小化比较次数，我们可以借用哈夫曼树（最佳归并树）的构造思想，优先合并最短的两个表。

合并过程：

表的元素数量：
- A: 10
- B: 35
- C: 40
- D: 50
- E: 60
- F: 200

按照最小合并原则，合并顺序为：

第一次合并：表 A 与表 B 合并，生成含有 45 个元素的表 AB。
- 比较次数：$10 + 35 - 1 = 44$
第二次合并：表 AB 与表 C 合并，生成含有 85 个元素的表 ABC。
- 比较次数：$45 + 40 - 1 = 84$
第三次合并：表 D 与表 E 合并，生成含有 110 个元素的表 DE。
- 比较次数：$50 + 60 - 1 = 109$
第四次合并：表 ABC 与表 DE 合并，生成含有 195 个元素的表 ABCDE。
- 比较次数：$85 + 110 - 1 = 194$
第五次合并：表 ABCDE 与表 F 合并，生成最终表。
- 比较次数：$195 + 200 - 1 = 394$

总比较次数计算：

总比较次数为：

$ 44 + 84 + 109 + 194 + 394 = 825 $

因此，最坏情况下的比较总次数为 825。

（2）合并策略的描述：

在对 N 个不等长的升序表进行合并时，最坏情况下的总比较次数依赖于合并的顺序。为此，我们可以采用以下策略：

策略：每次选择当前最短的两个表进行合并，直到所有表都合并为一个。可以通过使用最小堆来实现每次合并时快速找到最短的两个表。

理由：

减少比较次数：通过优先合并较短的表，能够减少后续合并中所需的比较次数。因为在每次合并时，合并的结果将生成一个新的较长的表，因此后续合并时，较短的表的数量逐渐减少，而较长的表逐渐增多，最小化了较长表的合并对总比较次数的影响。
哈夫曼树思想：与构建哈夫曼树的过程类似，选择最短的两个表进行合并，可以保证整体合并过程的最优性，使得最坏情况下的比较次数达到最低。

这种策略能够有效地减少合并过程中需要的比较次数，是处理多个不等长升序表合并的最佳实践。

42. 找出单链表共同后缀的起始位置

题目：
假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间，例如，“loading”和“being”的存储映像如下图所示。设 str1 和 str2 分别指向两个单词所在单链表的头结点，链表结点结构为：

typedef struct LinkNode {
    char data;                // 存储字符
    struct LinkNode *next;   // 指向下一个结点
} LinkNode;

请设计一个时间上尽可能高效的算法，找出由 str1 和 str2 所指向两个链表共同后缀的起始位置（如图中字符 i 所在结点的位置 p）。要求回答以下问题：

给出算法的基本设计思想。
根据设计思想，采用 C 或 C++ 或 Java 语言描述算法，关键之处给出注释。
说明你所设计算法的时间复杂度。

解答：

（1）算法的基本设计思想：

计算长度：首先分别求出 str1 和 str2 所指的两个链表的长度 m 和 n。
对齐链表：为了能够同时到达链表的尾部，需要将较长链表的指针向后移动 k 个节点（k 为两个链表长度之差），使得两个指针指向的节点到链表的尾部长度相等。
同步移动：然后同时向后遍历两个链表，比较它们所指向的节点。如果发现两个指针指向相同的节点，则该节点即为共同后缀的起始位置。

（2）算法的 C 语言代码描述：

LinkNode *Find_1st_Common(LinkNode *str1, LinkNode *str2) {
    // 计算链表的长度
    int len1 = Length(str1);
    int len2 = Length(str2);
    
    LinkNode *p = str1;
    LinkNode *q = str2;
    
    // 使指针 p 指向较长链表的前 len1 - len2 个结点
    for (; len1 > len2; len1--) {
        p = p->next; // p 向后移动
    }
    
    // 使指针 q 指向较长链表的前 len2 - len1 个结点
    for (; len2 > len1; len2--) {
        q = q->next; // q 向后移动
    }
    
    // 同步遍历两个链表，查找共同后缀起始点
    while (p != NULL && q != NULL) {
        if (p == q) { // 找到共同后缀的起始点
            return p; // 返回共同后缀的起始节点
        }
        p = p->next; // p 和 q 同步向后移动
        q = q->next;
    }
    
    return NULL; // 如果没有共同后缀，返回 NULL
}

// 辅助函数：计算链表长度
int Length(LinkNode *head) {
    int length = 0;
    LinkNode *current = head;
    while (current != NULL) {
        length++;
        current = current->next;
    }
    return length;
}

关键注释说明：

Length 函数：计算链表的长度，以便进行后续的对齐操作。
循环移动：通过两个 for 循环，调整指针 p 和 q 的起始位置，使它们到达与尾部相同的相对位置。
同步遍历：通过 while 循环同步移动指针，查找共同后缀的起始位置。

（3）时间复杂度分析：

长度计算：计算链表的长度 Length 函数需要 O(m) 和 O(n) 的时间复杂度，其中 m 和 n 分别是两个链表的长度。
指针对齐：在最坏的情况下，可能需要 O(|m - n|) 的时间来移动指针。
同步遍历：同步遍历两个链表的时间复杂度为 O(min(m, n))。

因此，整体时间复杂度为： $ O(m + n) $

这个算法在时间上是尽可能高效的，且只需要使用常量空间 O(1)。

2012年计算机统考-数据结构部分

数据结构

1．求整数 $ n \(（\) n $）阶乘的算法如下，其时间复杂度是：

A. $ O(_2 n) $

B. $ O(n) $

C. $ O(n _2 n) $

D. $ O(n^2) $

A．5

B．7

C．8

D．11

3．若一棵二叉树的前序遍历序列为 `a, e, b, d, c`，后序遍历序列为 `b, c, d, e, a`，则根结点的孩子结点：

A. 只有 `e`

B. 有 `e`、`b`

C. 有 `e`、`c`

D. 无法确定

4. 平衡二叉树节点总数

5. 有向图的广度优先遍历时间复杂度

6. 有向图的拓扑排序

7. Dijkstra 算法最短路径

8. 最小生成树的性质

9. B-树的删除操作

10. 排序方法中的确定位置

11. 折半插入排序与直接插入排序的区别

41. 有序表合并问题

解答：

合并过程：

总比较次数计算：

理由：

42. 找出单链表共同后缀的起始位置

解答：

数据结构

1．求整数 $ n \(（\) n $）阶乘的算法如下，其时间复杂度是：

A. $ O(_2 n) $

B. $ O(n) $

C. $ O(n _2 n) $

D. $ O(n^2) $

A．5

B．7

C．8

D．11

3．若一棵二叉树的前序遍历序列为 a, e, b, d, c，后序遍历序列为 b, c, d, e, a，则根结点的孩子结点：

A. 只有 e

B. 有 e、b

C. 有 e、c

D. 无法确定

4. 平衡二叉树节点总数

5. 有向图的广度优先遍历时间复杂度

6. 有向图的拓扑排序

7. Dijkstra 算法最短路径

8. 最小生成树的性质

9. B-树的删除操作

10. 排序方法中的确定位置

11. 折半插入排序与直接插入排序的区别

41. 有序表合并问题

解答：

合并过程：

总比较次数计算：

理由：

42. 找出单链表共同后缀的起始位置

解答：

3．若一棵二叉树的前序遍历序列为 `a, e, b, d, c`，后序遍历序列为 `b, c, d, e, a`，则根结点的孩子结点：

A. 只有 `e`

B. 有 `e`、`b`

C. 有 `e`、`c`