HackMD
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
延伸問題: 解釋運作原理，並新增刪除和搜尋節點的程式，附上完整的測試計畫
