2018q3 第 3 週測驗題

目的: 檢驗學員對 C 語言 pointer, union, bit-fields, 實作 linked list 的認知

測驗 `1`

考慮以下程式碼:













#include <stdio.h>
#include <stdint.h>
struct test {
    unsigned int x : 5;
    unsigned int y : 5;
    unsigned int z;
};
int main() {
    struct test t;
    printf("Offset of z in struct test is %ld\n",
           (uintptr_t) &t.z - (uintptr_t) &t);
    return 0;
}

在 GNU/Linux x86_64 環境中執行，得到以下輸出:

Offset of z in struct test is 4

倘若將第 10 和第 11 換為以下:


    printf("Address of t.x is %p", &t.x);

會發生什麼事？

作答區

(a) 印出類似 0x7ffd144e8ad4 的輸出，也就是 t 結構物件的位址;
(b) 印出類似 0x7ffd144e8ad4 的輸出，和 t 結構物件差距 4 bytes;
(c) 可以印出數值，但這與編譯器實作有關，不能解讀;
(d) 編譯失敗，不能這樣宣告結構體的成員;
(e) 編譯失敗，不能將指標指向沒有對齊 1 byte 的結構體成員;

參考資料: Portable Bit Fields in packetC

延伸問題: 解釋原因，並且找出 C99/C11 規格書對應的描述

測驗 `2`

考慮以下程式碼，在 little-endian 硬體上，會返回 1，反之，在 big-endian 硬體上會返回 0:

int main() {
    union { int a; char b;
    } c = { .a = K1 };
    return c.b == K2;
}

補完上述程式碼。

作答區

K1 = ?

(a) 0
(b) 1
(c) -1
(d) 254

K2 = ?

(a) 0
(b) 1
(c) 254

延伸問題: 解釋運作原理，並找出類似的程式碼

測驗 `3`

以下程式碼計算 parity bit:

#include <stdint.h>
int parity(uint32_t x)
    x ^= x >> 1;
    x ^= x >> 2;
    x = (x & 0x11111111U) * 0x11111111U;
    return (x >> P) & 1;
}

補完程式碼

作答區

P = ?

(a) 32
(b) 31
(c) 30
(d) 29
(e) 28
(f) 27
(g) 26
(h) 25
(i) 24

延伸問題: 解釋原理，並且提出更快的實作機制 (提示: 透過 SIMD)

測驗 `4`

考慮以下程式碼:

#include <stdlib.h>
#include <string.h>

typedef struct rec {
    char *value;
    struct rec *next;
} record;

void insert_sorted(record **r, const char *value)
{
    record *newrec = NULL;
    while (*r && strcmp(value, (*r)->value) > 0)
        r = &((F1)->next);
    newrec = malloc(sizeof(record));
    newrec->value = F2(value);
    newrec->next = F3;
    F4 = newrec;                                                                                                                                             
}

函式 insert_sorted 的作用是在 r 所指向已依據數值排序的 linked list 中，安插給定的字串，考慮到 string literal 的生命週期，應該在新建立的節點中，複製給定的字串。

請補完上述程式碼。

作答區

F1 = ?

(a) r
(b) **r
(c) *r
(d) r->next
(e) *r->next

F2 = ?

(a) 無
(b) strdup
(c) strcpy
(d) strlen
(e) strcmp

F3 = ?

(a) r
(b) **r
(c) *r
(d) r->next
(e) *r->next

F4 = ?

(a) **r
(b) *r
(c) r
(d) r->next
(e) *r->next

延伸問題: 解釋運作原理，並新增刪除和搜尋節點的程式，附上完整的測試計畫

2018q3 第 3 週測驗題

測驗 1

測驗 2

測驗 3

測驗 4

測驗 `1`

測驗 `2`

測驗 `3`

測驗 `4`