跳到主要内容

《数据结构与算法》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)
        ________________________________________;          
    }
}

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

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

int pop(Stack *s, int *e) {
    // 填空 (4)：进行栈的安全检查，判断当前栈是否为空
    if (________________________________________) {        
        return ERROR; 
    }
    
    *e = s->data[s->top];
    
    // 填空 (5)：更新栈顶指针（描述栈顶指针应当如何变化）
    ________________________________________;              
    
    return OK;
}

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

1. 循环时间复杂度推导​

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

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

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

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

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

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

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

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

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

4. Dijkstra 最短路径算法分析​

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

起点 \ 终点ABCE
A010∞100
B∞050∞
C∞∞010
D∞∞2060
E∞∞∞0

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

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

三、代码题（本大题共 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) {
    // 编写实现代码
}

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

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

        1
       / \
      2   3
     / \   \
    4   5   6

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

节点结构体：

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

函数框架：

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