⚙️ 操作系统部分真题解析

【例4】填空题第7题（2分）
题目：某系统采用请求页式存储管理，页表项含有效位、访问位、修改位。某进程访问页面顺序为：7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1。系统分配4个物理块，初始为空，采用OPT算法，缺页次数为____。
解析：OPT（最优）算法淘汰未来最久不使用的页面。
访问序列：7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1
物理块：[ ] → [7] → [7,0] → [7,0,1] → [2,0,1,7]（缺4次）
→ [2,0,1,3]（缺5）→ [2,0,4,3]（缺6）→ [2,0,4,3]（0命中）→ [2,0,4,3]（命中）→ [2,0,4,3]（命中）→ [2,0,4,3]（命中）→ [0,3,4,2]（缺7）→ [0,3,4,2]（命中）→ [0,3,1,2]（缺8）→ [0,3,1,2]（命中）→ [0,2,1,3]（缺9）→ [0,2,1,3]（命中）→ [0,1,7,3]（缺10）→ [0,1,7,3]（命中）→ [0,1,7,0]（0命中）→ [0,1,7,0]（命中）
共缺页10次。答案：10。
【关键】OPT需预知未来，考试中需逐次判断后续访问序列中最近不使用的页面。

【例5】应用题第4题（10分）
题目：某系统有3个进程P1、P2、P3，共享资源R（资源数=2）。进程对R的使用模式如下：
P1：申请1→使用→释放1
P2：申请2→使用→释放2
P3：申请1→使用→释放1
问：是否存在死锁？若存在，请给出死锁发生序列；若不存在，请说明理由。
解析：存在死锁可能。
死锁序列示例：
① P1申请1个R，成功（剩余1）；
② P2申请2个R，失败（仅剩1）→等待；
③ P3申请1个R，成功（剩余0）；
④ 此时：P1持有1，P3持有1，P2需2个；若P1释放1，P2仍需再申请1，但此时R总数为1，P2无法获得第2个；若P3释放1，同理。但若P1不释放而P3也不释放，则P2永远等待，P1与P3可继续运行——不构成死锁？
【修正】正确死锁场景：
① P1申请1（成功，R剩余1）；
② P3申请1（成功，R剩余0）；
③ P2申请2（失败，等待）；
④ P1完成使用，释放1（R=1）；
⑤ 此时若P3先获得R（再申请1，但P3已持有1，释放后可再申请，但P3未申请2个），问题在于P2需同时申请2个。若系统采用“请求即阻塞”，则P2等待期间，P1与P3可完成，无死锁。
【关键】该题存在争议，标准答案认为：不存在死锁，因为资源总数=2，最多两个进程各持1个，第三个进程无法获得足够资源，但系统可随时满足任一进程的完整请求（如释放后分配），不会形成循环等待。因此答案：不存在死锁。

【例6】综合分析题（10分）
题目：某磁盘有200个柱面（0~199），当前磁头在143号柱面，磁盘请求序列为：86,147,91,177,94,150,102,175,130。分别计算FCFS、SSTF、SCAN（向磁道号增大方向）算法的平均寻道长度。
解析：

- FCFS：143→86(57)→147(61)→91(56)→177(86)→94(83)→150(56)→102(48)→175(73)→130(45)
总寻道 = 57+61+56+86+83+56+48+73+45 = 565，平均 = 565/9 ≈ 62.78

- SSTF：143→150(7)→147(3)→130(17)→102(28)→94(8)→91(3)→86(5)→175(89)→177(2)
总寻道 = 7+3+17+28+8+3+5+89+2 = 162，平均 = 162/9 = 18

- SCAN（向高）：143→150(7)→175(25)→177(2)→199(22)→130(69)→102(28)→94(8)→91(3)→86(5)
注意：SCAN到达199后反向扫描，故顺序为143→150→175→177→199→130→102→94→91→86
总寻道 = 7+25+2+22+69+28+8+3+5 = 169，平均 = 169/9 ≈ 18.78
【易错】SCAN中“向高”指初始方向，到达边界后反向，不可漏掉反向段。

〔〕 算法设计题深度解析

【例7】算法设计题第2题（25分）
题目：给定一个整数数组（可能含负数），设计算法找出所有连续子数组中元素和最大的子数组，并返回其最大和。要求时间复杂度O(n)，空间复杂度O(1)。
解析：经典“最大子数组和”问题，采用动态规划（Kadane算法）：
思路：设dp[i]表示以第i个元素结尾的最大子数组和，则dp[i] = max(nums[i], dp[i-1] + nums[i])，最终结果为max(dp[i])。
优化：无需数组，仅用两个变量：
```c int maxSubArray(int nums[], int n) { if (n == 0) return 0; int currentSum = nums[0]; int maxSum = nums[0]; for (int i = 1; i < n; i++) { currentSum = nums[i] > currentSum + nums[i] ? nums[i] : currentSum + nums[i]; maxSum = currentSum > maxSum ? currentSum : maxSum; } return maxSum; } ```
【测试用例】
输入：[-2,1,-3,4,-1,2,1,-5,4] → 输出：6（子数组[4,-1,2,1]）
输入：[1] → 输出：1
输入：[-1] → 输出：-1
【注意】初始化必须为nums[0]，否则全负数组（如[-3,-2,-5]）会返回0而非-2。
【扩展】若要求返回子数组起止下标，需增加start、end、tempStart变量，此处略。

【例8】综合算法题（25分）
题目：设计一个支持以下操作的数据结构：
1. push(x)：压入元素x；
2. pop()：弹出栈顶元素；
3. top()：返回栈顶元素；
4. getMin()：返回栈中最小元素。
要求所有操作时间复杂度均为O(1)。
解析：用两个栈实现：

- dataStack：存储所有元素；

- minStack：栈顶始终为当前最小值。
push(x)：dataStack.push(x)；若minStack为空或x ≤ minStack.top()，则minStack.push(x)
pop()：若dataStack.top() == minStack.top()，则minStack.pop()；dataStack.pop()
getMin()：返回minStack.top()
```c class MinStack { private: stack dataStack; stack minStack; public: void push(int x) { dataStack.push(x); if (minStack.empty() || x <= minStack.top()) { minStack.push(x); } } void pop() { if (dataStack.top() == minStack.top()) { minStack.pop(); } dataStack.pop(); } int top() { return dataStack.top(); } int getMin() { return minStack.top(); } }; ```
【关键】minStack中必须允许重复最小值（如压入两个-1），否则pop()可能丢失最小值。2021年真题中，此题满分率仅32%，主要失分于未处理重复最小值情况。

〔〕 复试科目与形式（2021年版）

复试总分300分，含：

• 【专业课笔试】（100分）：C语言程序设计（参考《C语言程序设计》谭浩强）；
• 【综合面试】（150分）：含英语口语（20分）、专业能力（80分）、综合素质（50分）；
• 【上机测试】（50分）：1小时编程题（难度：简单-中等），使用Dev-C++或VS2019。

上机真题示例（2021年）：

1. 输入一个整数n，输出斐波那契数列前n项（n≤30）；
2. 输入一个字符串，统计其中数字字符出现次数；
3. 输入一个正整数，判断是否为素数（要求函数实现）。

建议：上机题难度不高，但需注意输入输出格式（如空格、换行），建议提前熟悉Dev-C++环境。

〔〕 832 vs 831科目区别详解

重庆大学2021年对专业型硕士（085404）实行双科目政策：

选择建议：

• 基础扎实者：选832，因数据结构是核心，易发挥；
• 跨考生/时间紧者：选831，内容更广但单科深度较浅；
• 注意：不同方向招生简章明确指定科目，报考时需确认。

〔〕 非计算机专业考生备考建议

年录取的非科班考生中，78%来自电子信息、自动化、数学等相近专业，22%来自文科/经管类（需补修课程）。备考建议：

1. 优先选831科目：内容覆盖更广，对算法要求略低；
2. 重点突破数据结构：因831中数据结构仍占40%，是提分关键；
3. 补学C语言：复试笔试必考，建议提前学习《C语言程序设计》基础部分；
4. 联系学长学姐：获取内部资料与复试经验，避免信息差。

真实案例：2021年一名数学专业考生，初试831科目（总分328），复试C语言92分，最终录取。其备考核心：3个月主攻数据结构+操作系统基础，重点掌握真题高频题型。