哈工大计算机考研真题权威解析

typedef struct {
    int data[100];
    int front, rear, count;
} CircularQueue;
void initQueue(CircularQueue q) {
    q->front = q->rear = q->count = 0;
}
int isEmpty(CircularQueue q) {
    return q->count == 0;
}
int isFull(CircularQueue q) {
    return q->count == 100;
}
void enqueue(CircularQueue q, int x) {
    if (!isFull(q)) {
        q->data[q->rear] = x;
        q->rear = (q->rear + 1) % 100;
        q->count++;
    }
}
int dequeue(CircularQueue q) {
    if (!isEmpty(q)) {
        int val = q->data[q->front];
        q->front = (q->front + 1) % 100;
        q->count--;
        return val;
    }
    return -1;
}

年真题第5题（15分）

〈要求〉给定一棵二叉搜索树（BST），设计算法找出第k小的节点值，要求时间复杂度O(h+k)，h为树高。

〈解题思路〉采用中序遍历+剪枝策略：利用BST左子树值小于根节点的特性，递归统计左子树节点数，当左子树节点数+1等于k时返回根节点，否则根据大小关系递归进入左右子树。

〈优化要点〉避免完整中序遍历，通过维护全局计数器实现提前终止，空间复杂度O(h)（递归栈深度）。

〈典型错误〉部分考生直接中序遍历存数组再取第k个，虽正确但未满足复杂度要求；另有考生忽略BST性质而暴力遍历整树。

年真题第3题（12分）

〈要求〉分析以下进程同步问题：三个进程P1、P2、P3共享一个缓冲区，P1写入数据，P2和P3分别读取并处理。要求：①写入期间禁止读取；②两读进程可并发；③避免死锁与饥饿。

〈标准解法〉使用信号量机制：

• mutex = 1（互斥写/读）
• readCount = 0（读者计数）
• readMutex = 1（保护readCount）
• writeMutex = 1（写者信号量）

〈PV操作关键代码〉

// 写进程P1
wait(writeMutex);
// 写操作
signal(writeMutex);
// 读者P2/P3
wait(readMutex);
readCount++;
if (readCount == 1) wait(writeMutex);
signal(readMutex);
// 读操作
wait(readMutex);
readCount--;
if (readCount == 0) signal(writeMutex);
signal(readMutex);

〈易错点提醒〉读者优先策略可能导致写进程饥饿，哈工大真题常考查写者优先方案，需额外引入writeBlock信号量。

年真题第2题（10分）

〈要求〉描述TCP三次握手过程中各标志位变化，并说明为何第二次握手需同时置SYN和ACK。

〈标准答案〉

1. 客户端发送SYN=1, seq=x，进入SYN_SENT状态
2. 服务器回复SYN=1, ACK=1, ack=x+1, seq=y，进入SYN_RCVD状态
3. 客户端确认ACK=1, ack=y+1，进入ESTABLISHED

〈深度解析〉第二次握手的SYN用于确认服务器接收能力，ACK用于确认客户端首包已到达。若仅置SYN未置ACK，则服务器无法确认客户端是否收到自己的SYN+ACK，可能导致连接建立失败。哈工大命题强调协议设计的“对称性原则”。

〈延伸考点〉常见陷阱题：为何不采用两次握手？→ 可能导致旧连接请求延迟到达引发数据错乱；为何不采用四次握手？→ 增加延迟且无必要。