中正 111 年資管所 資料結構 參考答案

共 7 層遞迴呼叫，每層存 list 指標、n、返回位址 3 項，共 21 個單位。

總步數 $=2mn+2n+1$。

(A) -+-/abc*de*ac

(B) -/*a+bcdg

void addq(element item)
{
    rear = (rear+1) % MAX_QUEUE_SIZE;
    if (front == rear)
        queueFull();
    queue[rear] = item;
}

list_pointer invert(list_pointer lead)
{
    list_pointer middle, trail;
    middle = NULL;
    while (lead) {
        trail  = middle;         /* 暫存已反轉段的最前端 */
        middle = lead;           /* middle 前進到目前節點 */
        lead   = lead->link;     /* lead 前進到下一個節點 */
        middle->link = trail;    /* 目前節點反指回 trail */
    }
    return middle;               /* middle 停在原尾節點，即新 head */
}