计算机类考研专业课-计算机考研专业课｜科学备考·深度突破·高效提分

✅ 示例1：操作系统综合题（清华912，2023）

题干：某系统有3个进程P1、P2、P3，共享一个缓冲区（容量为1）。P1生产数据放入缓冲区，P2和P3从缓冲区取数据处理。要求：P2和P3不能同时读取缓冲区；当缓冲区为空时，P2/P3需等待；当缓冲区满时，P1需等待。请用PV操作实现同步与互斥，并说明信号量初值。

常见错误答案：

var mutex, empty, full: semaphore;
begin
  mutex:=0; empty:=1; full:=0;
  cobegin
    process P1:
      begin
        P(empty); P(mutex);
        // 生产并放入
        V(mutex); V(full);
      end;
    process P2:
      begin
        P(full); P(mutex);
        // 取出并处理
        V(mutex); V(empty);
      end;
    process P3:
      begin
        P(full); P(mutex);
        // 取出并处理
        V(mutex); V(empty);
      end;
  coend;
end;

错误分析：mutex初值应为1（互斥锁初始可用），但P2/P3共享缓冲区，当P2在临界区时，P3也需等待，但上述代码中P3的P(full)可能先于P(mutex)执行，导致死锁。

高分答案结构：

// 1. 分析资源与约束
- 共享资源：缓冲区（互斥访问）
- 同步关系：P1生产→P2/P3消费（full信号量）
- 互斥关系：P2/P3不能同时读取（mutex信号量）
// 2. 信号量设计
var mutex, empty, full: semaphore;
mutex := 1;   // 缓冲区互斥锁
empty := 1;   // 缓冲区空位数（初始1个）
full := 0;    // 缓冲区数据数（初始0）
// 3. PV操作（关键：先同步后互斥）
cobegin
  process P1:
    begin
      P(empty);     // 等空位（同步）
      P(mutex);     // 申请互斥（互斥）
      // 生产数据放入缓冲区
      V(mutex);     // 释放互斥
      V(full);      // 增加数据（同步）
    end;
  process P2:
    begin
      P(full);      // 等数据（同步）
      P(mutex);     // 申请互斥（互斥）
      // 取出并处理数据
      V(mutex);     // 释放互斥
      V(empty);     // 增加空位（同步）
    end;
  process P3:
    begin
      P(full);      // 等数据（同步）
      P(mutex);     // 申请互斥（互斥）
      // 取出并处理数据
      V(mutex);     // 释放互斥
      V(empty);     // 增加空位（同步）
    end;
coend;

高分点：

• 明确写出信号量语义，避免歧义；
• 强调“先同步后互斥”原则（P(full)/P(empty)在P(mutex)前），防止死锁；
• 对称处理P2/P3，体现结构化思维。

✅ 示例2：数据结构算法题（浙大408，2022）

题干：给定一个单链表，设计算法判断其是否为回文链表。要求：时间复杂度O(n)，空间复杂度O(1)（不考虑递归栈），且不修改链表原始结构（除临时指针外）。

高分解法（快慢指针+链表反转）：

// 步骤1：用快慢指针找到中点（slow走1步，fast走2步）
// 步骤2：反转后半部分链表（从slow.next开始）
// 步骤3：从头和中点开始比较，直到中点
// 步骤4：恢复链表（可选，本题要求不修改结构，故省略）
bool isPalindrome(ListNode head) {
  if (!head || !head->next) return true;
  // 1. 找中点
  ListNode slow = head;
  ListNode fast = head;
  while (fast->next && fast->next->next) {
    slow = slow->next;
    fast = fast->next->next;
  }
  // 2. 反转后半部分
  ListNode prev = NULL;
  ListNode curr = slow->next; // 注意：从slow.next开始
  while (curr) {
    ListNode nextTemp = curr->next;
    curr->next = prev;
    prev = curr;
    curr = nextTemp;
  }
  // 3. 比较两部分
  ListNode p1 = head;
  ListNode p2 = prev;
  bool result = true;
  while (p2) { // 只需遍历后半部分
    if (p1->val != p2->val) {
      result = false;
      break;
    }
    p1 = p1->next;
    p2 = p2->next;
  }
  // （可选）4. 恢复链表：再次反转prev
  // ...（略）
  return result;
}

高分点：

• 明确说明“不修改原始结构”如何实现——通过仅反转后半部分，且题目允许临时修改（因后续可恢复）；
• 空间复杂度O(1)：仅用3个指针，无额外数组；
• 时间复杂度O(n)：3次线性遍历（找中点、反转、比较）；
• 边界处理：空链表、单节点直接返回true。

✅ 示例3：网络协议分析题（上交806，2023）

题干：在TCP连接中，发送方cwnd=4，rwnd=8，RTT=100ms。若发送方连续发送4个MSS后收到ACK（确认号=5），且cwnd更新为8。请分析：(1) 当前处于慢启动还是拥塞避免阶段？(2) 下一个RTT内最多可发送多少数据？

高分分析：

1. 阶段判断：cwnd从4→8，翻倍增长 → 慢启动阶段（拥塞避免时cwnd每次+1 MSS）；
2. 下一轮发送量：cwnd=8，但受rwnd=8限制，实际可发min(cwnd, rwnd)=8 MSS；
3. 关键陷阱：题目说“收到ACK（确认号=5）”，意味着前4个MSS（1-4）被确认，但cwnd=8表明发送方已收到1个RTT的ACK，进入下一个RTT周期；
4. 严谨表述：“由于处于慢启动阶段，每收到一个ACK，cwnd增加1 MSS。本次收到1个ACK（确认号=5），但cwnd从4→8说明实际收到4个ACK（可能批量ACK），符合慢启动指数增长特征。”