兰州交通大学考研数据结构真题权威解析

算法设计是兰州交通大学考研数据结构考试的重要组成部分，主要考查考生对算法逻辑的掌握和实现能力，尤其注重代码规范性与边界条件处理。

例如：排序算法（快速排序、归并排序、堆排序）、查找算法（二分查找、哈希表）、图算法（最小生成树、最短路径）等，均要求手写伪代码或C语言实现，并分析时间复杂度。

• 排序算法：2022年考题要求实现堆排序并画出建堆过程（以[49,38,65,97,76,13,27,49]为例），重点考查堆调整过程与稳定性判断。
• 查找算法：2021年真题给出哈希表长度为11，哈希函数为H(k)=k mod 11，要求用线性探测再散列处理冲突，并画出插入{19,14,23,1,68,20,84,27,55,11}后的哈希表及平均查找长度。
• 图算法：2020年考查Prim算法构造最小生成树，并要求画出每一步加入的边；2023年考查Dijkstra算法求单源最短路径，给出带权有向图，要求写出路径及距离数组变化过程。

兰交大算法题评分标准明确：逻辑正确（50%）、代码规范（30%）、复杂度分析（20%）。建议考生平时练习时严格按“函数声明→变量说明→算法步骤→复杂度分析”四步书写。

近年来，试题更加注重实际问题的考查，要求考生将数据结构知识应用于具体问题中，体现“学以致用”的导向。

• 数据库索引应用：2022年真题以B+树为背景，要求分析其在数据库索引中的优势（如减少磁盘I/O、支持范围查询），并画出阶为3的B+树插入过程。
• 路径规划问题：2021年综合题以校园导航为场景，给出有向图表示道路连接，要求用Floyd-Warshall算法求所有顶点对之间的最短路径，并分析空间换时间的策略。
• 任务调度系统：2023年真题模拟操作系统进程调度，要求用优先队列（堆）实现最短作业优先（SJF）调度算法，并计算平均等待时间。

特别提醒：兰交大近年增设“算法优化”子题，如“如何优化快速排序的最坏情况？”（答案：三数取中法+尾递归优化）、“如何减少Dijkstra算法的时间复杂度？”（答案：使用斐波那契堆可将时间复杂度降至O(V log V + E)）。

年简答题第1题（10分）

简述顺序表与链表的主要区别，并说明在什么情况下应选择链表而非顺序表。
答案：顺序表采用静态存储（数组），便于随机访问，但插入和删除需移动大量元素；链表采用动态存储，插入删除只需修改指针，但不支持随机访问。
应选择链表的场景：频繁插入/删除（如动态维护有序序列）、无法预估存储空间大小、元素占用空间较大（避免移动开销）。

年简答题第2题（12分）

设二叉树采用二叉链表存储，写出求二叉树高度的递归算法，并分析时间复杂度。
答案：
```c
int Height(BiTree T) {
if (!T) return 0;
int lh = Height(T->lchild);
int rh = Height(T->rchild);
return (lh > rh ? lh : rh) + 1;
}
```
时间复杂度：O(n)（每个结点访问一次）；空间复杂度：O(h)（递归栈深度，最坏O(n)）。

年算法设计题（15分）

已知一个带头结点的单链表L，设计一个算法将其就地逆置（即不另开存储空间），要求时间复杂度O(n)、空间复杂度O(1)。
答案：
```c
void Reverse(LinkList &L) {
LNode p = L->next, q;
L->next = NULL; // 断开头结点
while (p) {
q = p->next; // 暂存后继
p->next = L->next;
L->next = p; // 头插法重建
p = q;
}
}
```
评分要点：①正确断开头结点（2分）；②循环中三步操作完整（6分）；③无内存泄漏（2分）；④时间空间复杂度分析（5分）。

年综合应用题（20分）

给定有向图G的邻接矩阵如下，要求：
① 画出该图；
② 给出从顶点V1出发的DFS遍历序列；
③ 给出从顶点V1出发的BFS遍历序列；
④ 判断该图是否为强连通图，并说明理由。
邻接矩阵（行→列）：
V1→V2,V3；V2→V3；V3→V4；V4→V1
答案：
① 略（4分）；
② DFS：V1→V2→V3→V4（或V1→V3→V4→V1…但需注意回溯，标准答案为V1,V2,V3,V4）；
③ BFS：V1→V2,V3→V4；
④ 是强连通图，因任意两顶点间存在双向路径（V1↔V2↔V3↔V4↔V1）。