该方法是一种局部贪心算法，它在每一步只考虑了从当前顶点出发到下一个顶点的局部最短距离（边权最小），而没有考虑到这个局部选择可能会导致后续的路径代价剧增。因此，局部最优的选择无法保证全局最优，上述方法无法正确求解最短路径问题。

假设存在一个带权有向图（无向图同理），包含初始顶点 SS，目标顶点 TT，以及两个中间顶点 AA 和 BB。各边的权值如下：

• S→AS→A 的权值为 1

• S→BS→B 的权值为 5

• A→TA→T 的权值为 100

• B→TB→T 的权值为 1

按照题目中的方法执行过程如下：

1. 初始状态：最短路径集合 P={S}P={S}，当前顶点 u=Su=S。

2. 第一次选择：从 SS 出发，寻找离 SS 最近且不在 PP 中的顶点。

   SS 到 AA 的距离是 1；SS 到 BB 的距离是 5；因为 1<51<5，算法会选择顶点 AA；将 AA 加入路径，当前顶点更新为 u=Au=A；此时路径为 S→AS→A。

3. 第二次选择：从 AA 出发，寻找离 AA 最近且不在 PP 中的顶点。

   目前不在 PP 中的相关顶点只有 TT（BB也还在，但边 A→TA→T 和 A→BA→B 没有直接连接，假设只考虑有直接连接的）；AA 到 TT 的距离是 100；算法选择顶点 TT；将 TT 加入路径，当前顶点更新为 u=Tu=T。

4. 结束：当前顶点 u=Tu=T 已经是目标顶点，算法结束。

算法求得的路径为： S→A→TS→A→T，总距离为 1+100=1011+100=101。

真正的最短路径为： S→B→TS→B→T，总距离为 5+1=65+1=6。

(1) 算法的基本设计思想

由于单链表只能从头到尾单向遍历，无法从尾部回溯，为了实现尽可能高效（即尽可能只遍历一次链表）的查找，可以采用双指针（快慢指针）的思想。

基本思路是：定义两个指针 p（快指针）和 q（慢指针），初始时均指向链表的第一个实际数据结点（即 list->link）。首先让快指针 p 沿着链表向前移动 kk 步。如果在此过程中 p 变为 NULL，说明链表长度不足 kk，查找失败。如果 p 成功移动了 kk 步，则让 p 和 q 同步向后移动。由于 p 和 q 之间的距离始终保持为 kk，当快指针 p 走到链表末尾（即 p == NULL）时，慢指针 q 正好指向倒数第 kk 个结点。该算法时间复杂度为 O(n)O(n)，空间复杂度为 O(1)O(1)。

(2) 算法的详细实现步骤

#include <stdio.h>

// 单链表结点结构定义
typedef struct Node {
    int data;
    struct Node *link;
} Node;

/**
 * 查找带头结点单链表中倒数第k个位置的结点
 * @param list 头指针
 * @param k 倒数位置（正整数）
 * @return 查找成功返回1并输出data，否则返回0
 */
int findKthFromEnd(Node *list, int k) {
    // 1. 边界条件判断：空表或k不合法
    if (list == NULL || list->link == NULL || k <= 0) {
        return 0;
    }

    // 2. 初始化快慢指针，均指向第一个实际数据结点
    Node *p = list->link; // 快指针
    Node *q = list->link; // 慢指针

    // 3. 快指针先向前移动 k 步
    for (int i = 0; i < k; i++) {
        if (p == NULL) {
            return 0; // 链表长度不足 k，查找失败
        }
        p = p->link;
    }

    // 4. 快慢指针同步向后移动
    while (p != NULL) {
        p = p->link;
        q = q->link;
    }

    // 5. 此时 q 正好指向倒数第 k 个结点
    printf("%d\n", q->data); // 输出结点的data域的值
    return 1;                // 查找成功
}

1. 边界检查：若头指针 list 为空，或链表为空（list->link == NULL），或 k≤0k≤0，直接返回 0。

2. 初始化：声明两个结点指针 p 和 q，均指向链表的第一个数据结点：p = list->link; q = list->link;。

3. 快指针先行：让快指针 p 向后移动 kk 个位置。在循环移动过程中，若 p 提前变为 NULL，说明链表长度小于 kk，查找失败，返回 0。

4. 同步移动：若 p 成功走了 kk 步，则开启循环，让 p 和 q 同时向后移动（p = p->link; q = q->link;），直到 p == NULL 为止。

5. 输出结果：此时慢指针 q 指向的结点即为倒数第 kk 个结点。输出 q->data 的值，并返回 1。

在中断方式下，CPU用于该外设I/O的时间占整个CPU时间的百分比是 2.5%。

在DMA方式下，CPU用于该外设I/O的时间占整个CPU时间的百分比是 0.1%。

• C5：取 R0 的值并暂存，同时计算有效地址

  • 需要将 R0 的值送入 ALU 的输入端 A（R0out, Ain）。

  • 同时，为了后续访问主存，需要将 R1 的值（即主存地址）送入 MAR（R1out, MARin）。

  • 注意：这里将两个不冲突的操作合并在一个时钟周期内完成，以提高效率。

• C6：从主存读取数据

  • 根据 MAR 中的地址，从主存读取数据到 MDR（MemR, MDRinE）。由于是读操作，需要给存储器发读命令，所以是 MemR。

• C7：执行加法运算

  • 将 MDR 中的数据（即 ((R1))）送入 ALU 的输入端（MDRout, ADD，假设 ALU 的另一输入端已由 Ain 锁存了 R0 的值），进行加法运算，并将结果暂存到 AC（ACin）。

• C8：将结果写回主存

  • 将 AC 中的结果送入 MDR（ACout, MDRin）。

  • 同时，需要将之前保存在 MAR 中的地址（R1 的值）重新送入 MAR（R1out, MARin），因为 MAR 是地址锁存器，通常需要保持地址直到写操作完成。

  • 注：有些设计会在 C5 后就保持 MAR 不变，但标准的数据通路通常需要显式给出地址输入。题目为了简化，这里可以合并写。

• C9：写入主存

  • 将 MDR 中的数据写入主存对应地址（MemW, MDRoutE）。此时需要给存储器发写命令 MemW。

semaphore mutex = 1; // 用于缓冲区的互斥访问
semaphore empty = N; // 缓冲区中空闲单元的数量
semaphore odd = 0;   // 缓冲区中奇数的数量
semaphore even = 0;  // 缓冲区中偶数的数量

// 进程 P1 (生产者)
void P1() {
    while (true) {
        int num = produce(); // 生成一个正整数
        P(empty);            // 申请一个空闲单元，若缓冲区满则阻塞
        P(mutex);            // 申请缓冲区的互斥访问权
        
        put(num);            // 将数据放入缓冲区
        
        V(mutex);            // 释放缓冲区的互斥访问权
        if (num % 2 != 0) {
            V(odd);          // 如果是奇数，增加奇数资源数量，唤醒可能等待的 P2
        } else {
            V(even);         // 如果是偶数，增加偶数资源数量，唤醒可能等待的 P3
        }
    }
}

// 进程 P2 (奇数消费者)
void P2() {
    while (true) {
        P(odd);              // 申请一个奇数资源，若没有奇数则阻塞
        P(mutex);            // 申请缓冲区的互斥访问权
        
        int num = getodd();  // 从缓冲区取出一个奇数
        
        V(mutex);            // 释放缓冲区的互斥访问权
        V(empty);            // 增加一个空闲单元，唤醒可能等待的 P1
        
        countodd(num);       // 统计奇数个数
    }
}

// 进程 P3 (偶数消费者)
void P3() {
    while (true) {
        P(even);             // 申请一个偶数资源，若没有偶数则阻塞
        P(mutex);            // 申请缓冲区的互斥访问权
        
        int num = geteven(); // 从缓冲区取出一个偶数
        
        V(mutex);            // 释放缓冲区的互斥访问权
        V(empty);            // 增加一个空闲单元，唤醒可能等待的 P1
        
        counteven(num);      // 统计偶数个数
    }
}

2362H：210 ns；1565H：100,000,220 ns；25A5H：210 ns

物理地址：254565H；理由：访问1565H时发生缺页中断。根据LRU算法，最近最少使用的页是页号2（因为刚刚访问过2362H，其页号为2），因此页号2被淘汰，其占用的物理帧254H被分配给页号1。所以页号1对应的物理地址为 254H×1000H+565H=254565H254H×1000H+565H=254565H。