2025-2026学年下学期期末

2025-2026学年下学期期末试卷

说明：单选多选无法还原，仅参考题干与考查知识点；题目数据为现编，考点与原题一致 ——————— by 赤团开时

一、填空题（本大题共 2 小题，共 5 空，每空两分）

考试无注释，采用类实现，代码片段仅作参考

1. 插入排序算法实现（共3空）

标准插入排序代码片段，根据注释补全逻辑：

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;

        // 填空 (1)：使用不等号判断，查找大于/小于已知值(key)的合适插入位置
        while (________________________________________) {

            // 填空 (2)：执行元素的"向后赋值"（即将当前元素后移一位）
            ________________________________________;
            j--;
        }

        // 填空 (3)：内层循环结束后，将原空出来的关键位置赋予已知值(key)
        ________________________________________;
    }
}

解：

(1) j >= 0 && arr[j] > key (2) arr[j + 1] = arr[j] (3) arr[j + 1] = key

2. 顺序栈的 pop() 出栈操作（共2空）

顺序栈出栈核心逻辑补全：

int pop(Stack *s, int *e) {
    // 填空 (4)：进行栈的安全检查，判断当前栈是否为空
    if (________________________________________) {
        return ERROR;
    }

    *e = s->data[s->top];

    // 填空 (5)：更新栈顶指针（描述栈顶指针应当如何变化）
    ________________________________________;

    return OK;
}

解：

(4) s->top == -1（或 s->top < 0） (5) s->top--（或 s->top = s->top - 1）

二、简答题（本大题共 4 小题，每题十分）

1. 循环时间复杂度推导

算法循环控制变量 i 初始值为 0；迭代增长规则：

第1步：i += 1
第2步：i += 2
第3步：i += 3 依次累加，终止条件 i > n 时退出循环。

要求：详细写出推导过程，给出大O时间复杂度。

解：

第 $k$ 步后， $i = 1 + 2 + \cdots + k = \frac{k(k+1)}{2}$ 。终止条件为 $\frac{k(k+1)}{2} > n$ ，即 $k^2 + k - 2n > 0$ 。解得 $k \approx \sqrt{2n}$ ，故时间复杂度为 $O(\sqrt{n})$ 。

2. 快速排序(Quicksort)过程演练

原始无序序列：[28, 15, 42, 9, 67, 33, 21, 54] 要求：

基准值选取规则：floor((low + high) / 2) 向下取整对应元素
写出每一趟 Partition 划分后的完整序列或者绘制完整递归调用树展示分治流程

解：

序列下标 0~7，初始 low=0, high=7，基准下标 = floor((0+7)/2) = 3，基准值 = 9。

第一趟（基准 9）：划分后 [9, 15, 42, 28, 67, 33, 21, 54]，基准位置 0。左半为空，右半 low=1, high=7，基准下标 = floor((1+7)/2) = 4，基准值 = 67。

第二趟（基准 67）：划分后 [9, 15, 42, 28, 54, 33, 21, 67]，基准位置 7。左半 low=1, high=6，基准下标 = floor((1+6)/2) = 3，基准值 = 28。

第三趟（基准 28）：划分后 [9, 15, 21, 28, 54, 33, 42, 67]，基准位置 3。左半 low=1, high=2，右半 low=4, high=6。

左半（基准 15）：划分后不变 [9, 15, 21, ...]，基准位置 1。

右半（基准 33）：划分后 [..., 28, 33, 54, 42, 67]，基准位置 5。

继续递归直至有序。最终结果：[9, 15, 21, 28, 33, 42, 54, 67]。

3. 平衡二叉查找树(AVL 树)构建流程

输入序列（从左至右依次插入空树）：[45, 12, 58, 6, 18, 52, 70, 31, 64] 要求：

插入失衡时，标注失衡节点、旋转类型（LL/RR/LR/RL）
画出每次旋转后的局部/整体树结构
给出最终完整平衡AVL树形态

解：

插入过程（仅标注失衡与旋转）：

插入 45：根节点，平衡。
插入 12：45 的左孩子，平衡。
插入 58：45 的右孩子，平衡。
插入 6：12 的左孩子，平衡。
插入 18：12 的右孩子，平衡。
插入 52：58 的左孩子，平衡。
插入 70：58 的右孩子，平衡。
插入 31：18 的右孩子 → 45 失衡（LL 型），对 45 做右旋。
插入 64：最终调整后平衡。

最终 AVL 树形态：

          45
        /    \
      12      58
     /  \    /  \
    6   18  52  70
         \     /
         31  64

（具体旋转步骤略，以最终形态为准）

4. Dijkstra 最短路径算法分析

有向带权图邻接矩阵（∞代表无直接边）：

起点 \ 终点	A	B	C	E
A	0	10	∞	100
B	∞	0	50	∞
C	∞	∞	0	10
D	∞	∞	20	60
E	∞	∞	∞	0

源点指定为顶点A，要求：

完整求解步骤，绘制状态更新表格（记录集合S、各顶点距离动态更新）
输出A到其余所有顶点的最短路径与对应距离

解：

步骤	S	dist(B)	dist(C)	dist(D)	dist(E)
初始化	{A}	10	∞	∞	100
1. 选 B	{A,B}	10	60(via B)	∞	100
2. 选 C	{A,B,C}	10	60	∞	70(via C)
3. 选 E	{A,B,C,E}	10	60	∞	70
4. 选 D	{A,B,C,E,D}	10	60	∞	70

注：顶点 D 不可达（没有边指向 D），dist(D) = ∞。

最短路径：

A→B：距离 10
A→C：路径 A→B→C，距离 60
A→D：不可达，距离 ∞
A→E：路径 A→B→C→E，距离 70

三、代码题（本大题共 2 小题，每题十分）

1. 单链表相邻节点成对指针翻转

功能：交换第 2i-1 和 2i 个相邻节点，仅修改指针，禁止交换节点数值，返回新头指针。输入示例：1 → 2 → 3 → 4 → 5 输出示例：2 → 1 → 4 → 3 → 5

节点结构体：

struct ListNode {
    int val;
    struct ListNode *next;
};

函数框架：

struct ListNode* swapPairs(struct ListNode* head) {
    // 编写实现代码
}

解：

struct ListNode* swapPairs(struct ListNode* head) {
    struct ListNode dummy = {0, head};
    struct ListNode *prev = &dummy;
    while (prev->next && prev->next->next) {
        struct ListNode *first = prev->next;
        struct ListNode *second = first->next;
        first->next = second->next;
        second->next = first;
        prev->next = second;
        prev = first;
    }
    return dummy.next;
}

2. 二叉树任意节点间最大路径长度

功能：求二叉树内部最长路径跨度，路径不一定经过根节点。示例说明：树结构：

最长路径：4 → 2 → 1 → 3 → 6，路径长度为4。

节点结构体：

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

函数框架：

int maxPathSum(struct TreeNode* root) {
    // 编写实现代码
}

解：

int dfs(struct TreeNode* root, int *ans) {
    if (!root) return 0;
    int left = dfs(root->left, ans);
    int right = dfs(root->right, ans);
    if (left + right > *ans) *ans = left + right;
    return (left > right ? left : right) + 1;
}

int maxPathSum(struct TreeNode* root) {
    int ans = 0;
    dfs(root, &ans);
    return ans;
}