107 中興資工所考古題詳解｜軟體考點分析

題型與配分

全卷 4 頁、100 分，不得使用計算機。112 年以前中興甲組沒有獨立的資料結構與演算法考科，軟體內容在資訊概論的 PART 1，PART 2 是作業系統、PART 3 是計算機組織。

PART 1 的結構（A 單選 8 題 24%、B 簡答 4 題 26%）與 108 年 PART 1 相同。

PART 1 單選題（A，1–8，共 24%）

• 第 1 題｜a = 7.00、b = 7.00、c = 6.00，printf("%.3f", sqrt(a+b*c)); 印出什麼
• 第 2 題｜從 key 抽出指定位數當作位址的 hashing：direct、division remainder、modulo division、digit extraction
• 第 3 題｜Turing machine 由哪三個元件組成
• 第 4 題｜把未排序部分的最小項與未排序部分的第一項交換，是哪種排序：bubble、selection、insertion、shell
• 第 5 題｜兩數相加，指數分別為 7 與 9，較小數的小數點要怎麼移
• 第 6 題｜電腦記憶體中最常用的整數表示法：sign-and-magnitude、one's complement、two's complement、unsigned integers
• 第 7 題｜把硬碟、記憶體、CPU 切成多台各有自己硬碟、記憶體、CPU 的 virtual machine，是哪種技術：Parallel computing、Multitasking、Multicore、Virtualization
• 第 8 題｜Hamming distance 至少為 7 時，最多能自我更正幾個位元；題幹英文措辭不完整

PART 1 簡答題（B，26%）

• 第 1 題（6%）｜void bf(int *i, int *j) 執行 *i = *j + 4; *j = *j - 2; 後印出，void af(int *a, int b) 執行 *a += 4; b *= 3; 後印出再呼叫 bf(a, &b)；main 中 x = 6、y = 9，呼叫 af(&x, y) 後再印 x、y，寫出全部輸出
• 第 2 題（6%）｜10 個節點的 binary tree，preorder 為 JCBADEFIGH、inorder 為 ABCEDFJGIH，畫出這棵樹
• 第 3 題（8%）｜把 (a) −12.640625、(b) −0.375 轉成 32 位元 IEEE 格式
• 第 4 題（6%）｜寫出 quick sort 的 pseudo-code

作答時要注意的地方

1. PART 1 卷面沒有標示倒扣。
2. 單選第 1 題的格式字串是 %.3f。
3. 簡答第 1 題 af 的第二個參數是傳值，bf 的兩個參數都是 pointer，main 最後印的是 x、y。
4. 簡答第 1 題共有三個 printf，輸出有三行。
5. 簡答第 4 題只要求 pseudo-code，沒有指定 partition 的寫法。

準備方向

• floating point 與整數表示：107 單選第 5、6 題與簡答第 3 題，106 單選第 1、5 題與簡答第 3 題、108 簡答第 2、3 題、113 第 2 題也有；硬體 114 問答第 3 題考 IEEE 754。
• C 語言的 pointer 與傳參：107 簡答第 1 題，106 簡答第 1、2 題、108 單選第 1–5 題、110 第 6-A 題、112 PART 2-C、113 B-1 第 1、2 題也有。
• 樹的 traversal：107 簡答第 2 題由兩種 traversal 畫樹，108 單選第 6 題、111 第 3-VI 題、113 第 6–8 題也考 traversal。
• Quick sort：107 簡答第 4 題，109 第 12 題考 3-way quicksort、111 第 1-II 題考最壞情況。
• 排序的定義與性質：107 單選第 4 題，109 第 9 題、110 第 8-B 題、114 第 1、2、7 題也有。
• hash：107 單選第 2 題，110 第 6-B 題、111 第 3-III 題、114 第 15 題考 open addressing。
• virtualization：107 單選第 7 題，硬體 115 第 12 題也考 virtual machine。