清大 106 年資應所 計算機概論 參考答案

1 的個數為偶數、不符合奇同位的字串必定有錯：

• 第 2 組 11011（4 個 1）
• 第 4 組 00000（0 個 1）
• 第 6 組 10001（2 個 1）

0F（00001111）：第一道指令 13B8 把位址 B8 的內容 0F 載入暫存器 3。

C3（11000011）。

一個 I/O-bound 加一個 compute-bound 較高。前者等 I/O 時 CPU 可執行後者，CPU 與 I/O 重疊運作；兩個都是 I/O-bound 時 CPU 常閒置，且可能競爭同一個 I/O 裝置。

都是行程拿不到所需資源而無限期等待，工作無法完成。

一致：P、Q、S、T 皆為真時四個命題都成立。

不一致。

三個權重皆為 1，門檻值 1.5（加權和大於門檻值時輸出 1）。

狀態 (b1, b2)，起始 (0, 0)，目標 (x, 4)。規則：R1/R2 裝滿 B1/B2、R3/R4 倒空 B1/B2、R5 B1 倒入 B2、R6 B2 倒入 B1（倒入量取來源水量與目標剩餘容量的較小者）。控制系統以廣度優先搜尋套用規則。部分狀態圖：(0,0) →R1→ (3,0) →R5→ (0,3)；(0,0) →R2→ (0,5) →R6→ (3,2) →R3→ (0,2) →R6→ (2,0) →R2→ (2,5) →R6→ (3,4)。

n 的二進位去掉最低位就是 \ensuremath{\lfloor}n/2\ensuremath{\rfloor}，因此從最高位的 J(1) = 1 開始，往低位每多看一個位元，位元為 0 時 J ← 2J − 1，為 1 時 J ← 2J + 1。時間複雜度 O(log n)。

int josephus_iter(int n) {
    int k = 0, J = 1;
    while ((n >> (k + 1)) > 0) k++;        /* k 為 n 最高位 1 的位置 */
    for (int i = k - 1; i >= 0; i--)        /* 由高位往低位處理其餘位元 */
        J = ((n >> i) & 1) ? 2 * J + 1 : 2 * J - 1;
    return J;
}

int josephus_rec(int n) {
    if (n == 1) return 1;
    if (n % 2 == 0) return 2 * josephus_rec(n / 2) - 1;   /* J(2m) = 2J(m) - 1 */
    return 2 * josephus_rec(n / 2) + 1;                   /* J(2m+1) = 2J(m) + 1 */
}

時間複雜度 O(log n)。

以串列的第一個節點為頂端，插入與刪除都在 head。

typedef struct Node {
    int data;
    struct Node *link;
} Node;

Node *top = NULL;

void push(int x) {                 /* O(1) */
    Node *p = malloc(sizeof(Node));
    p->data = x;
    p->link = top;
    top = p;
}

int pop(void) {                    /* O(1)，假設 stack 非空 */
    Node *p = top;
    int x = p->data;
    top = p->link;
    free(p);
    return x;
}

另外記錄 tail 指標，從 tail 插入、從 head 刪除。

typedef struct Node {
    int data;
    struct Node *link;
} Node;

Node *head = NULL, *tail = NULL;

void enqueue(int x) {              /* O(1) */
    Node *p = malloc(sizeof(Node));
    p->data = x;
    p->link = NULL;
    if (tail == NULL) head = tail = p;   /* 原本是空佇列 */
    else { tail->link = p; tail = p; }
}

int dequeue(void) {                /* O(1)，假設 queue 非空 */
    Node *p = head;
    int x = p->data;
    head = p->link;
    if (head == NULL) tail = NULL;       /* 刪掉最後一個節點 */
    free(p);
    return x;
}

由無限長紙帶、讀寫頭與有限狀態控制單元組成的計算模型；每步依目前狀態與讀到的符號決定寫入符號、移動方向與下一狀態，進入停止狀態即結束。Church–Turing thesis 主張凡能以演算法計算的都能由它計算。

乘以 2 等於二進位數左移一位，也就是在最低位右邊補一個 0。紙帶上的數寫在兩個 * 之間（如 101），機器從 START 開始，讀寫頭位於右端的 *。

例：101（5）變成 1010（10）。