Linux 核心设计: 第 1 周测验题 linked list

2018q1 第 4 週測驗題

测验 1

FuncA 的作用是

• (e) 建立新節點，內容是 value，並安插在結尾

FuncB 的作用是

• (d) 建立新節點，內容是 value，並安插在開頭

FuncC 的作用是

• (e) 找到節點內容為 value2 的節點，並在之後插入新節點，內容為 value1

在 main 函数调用 display 函数之前，链表分布为: 48 -> 51 -> 63 -> 72 -> 86

在程式輸出中，訊息 Traversal in forward direction 後依序印出哪幾個數字呢？

• (d) 48
• (c) 51
• (a) 63
• (e) 72
• (b) 86

在程式輸出中，訊息 Traversal in reverse direction 後依序印出哪幾個數字呢？

• (b) 86
• (e) 72
• (a) 63
• (c) 51
• (d) 48

测验 2

FuncX 的作用是 (涵蓋程式執行行為的正確描述最多者)

• (f) 判斷是否為 circular linked list，若為 circular 則回傳 0，其他非零值，過程中計算走訪的節點總數

K1 » 後面接的輸出為何

• (b) Yes

K2 » 後面接的輸出為何

• (a) No

K3 » 後面接的輸出為何

• (a) No

K4 » 後面接的輸出為何

• (a) No

K5 » 後面接的輸出為何

• (f) 0

count » 後面接的輸出為何

• (f) 0

2020q1 第 1 週測驗題

测验 1

• 本题使用的是单向 linked list

1
2
3
4

typedef struct __list {
    int data;
    struct __list *next;
} list;

• 一开始的 if 语句用于判断 start 是否为 NULL 或是否只有一个节点，如果是则直接返回无需排序

• 接下来使用 mergesort 来对 linked list 进行从小到大排序，并且每次左侧链表只划分一个节点，剩余节点全部划为右侧链表

1
2
3

    list *left = start;
    list *right = left->next;
    left->next = NULL; // LL0;

• 再来就是归并操作，将 left 和 right 进行归并，如果 merge 为 NULL，则将对应的节点赋值给它和 start，否则需要迭代 left 或 right 以及 merge 以完成归并操作

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

    for (list *merge = NULL; left || right; ) {
        if (!right || (left && left->data < right->data)) {
            if (!merge) {
                start = merge = left; // LL1;
            } else {
                merge->next = left; // LL2;
                merge = merge->next;
            }
            left = left->next; // LL3;
        } else {
            if (!merge) {
                start = merge = right; // LL4;
            } else {
                merge->next = right; // LL5;
                merge = merge->next;
            }
            right = right->next; // LL6;
        }
    }