國立空中大學

一個 128K bps 的通訊元件，每分鐘可以傳送多少位元組（bytes）？

全加器（full adder）能將 2 個位元以及進位輸入（carry in）相加。其輸出 有和（sum）及進位輸出（carry out）。假設所有使用到的邏輯閘之輸入至 多有兩個，則全加器至少需要用到幾個基本邏輯閘（如：AND、OR、NOT、 XOR）？

當微處理器進行數值運算時須要檢查，以確認結果的正確性，下列何者是 除法運算時須要檢查的項目？

下列何者不屬於快取記憶體錯失（Cache Miss）的型態？

獨立磁碟冗餘陣列（RAID）可分成不同等級，在使用硬碟總數相同的情況 下，於寫入資料時，理論上下列何者的速度最快？

關於 NAND Flash 的敘述，下列何者錯誤？

一個程式內含 1000 個指令，此程式在一個單核心 5-stage 管線化（pipeline） CPU 中執行，每個 stage 耗時 1 個時脈週期（clock cycle），CPU 的運作 頻率為 2 GHz。若此程式有 2%的指令會發生管線危障（hazard），且每次 危障將導致 1 個時脈週期的管線暫停。此程式在 CPU 內的執行時間為：

CPU 以循環的機器週期（machine cycle）執行程式中的每一行指令，機器 週期的步驟順序為何？

相對於自然語言，下列何者不是程式語言的特性？

針對下列不同年代計算機所使用的技術，依照其出現的時間，從遠至今排列：①積體電路 ②電晶體 ③超大型積體電路 ④真空管

有關處理器執行指令之效能敘述，下列何者錯誤？

給定一個以相鄰矩陣（adjacency matrix）表示的一無方向圖如下表，∞表示沒有邊（edge）相鄰。請畫出對應的圖形，每個邊和其對應的權值必須列出。另外請使用 Kruskal’s 演算法計算權重最小的生成樹（minimum spanning tree），並詳細列出該生成樹的形成過程。（20 分）

四、有一棵二元樹（binary tree）利用一維陣列來存放其節點，假設樹根（root） 存放在索引（index）為 1 的位置，若有一節點 i 存放在索引為 1024 的位 置，請問該節點 i 的父節點存於陣列的那個位置，其索引為何？若節點 i 有 一右子節點 j，請問節點 j 存於陣列的那個位置，其索引為何？用一維陣 列存放二元樹，最浪費陣列空間的二元樹是那一種？請畫出並詳細說明。 （15 分）

三、有一棵高度平衡二元搜尋樹（balanced binary search tree）又稱 AVL 樹 （Adelson-Velskii Landis tree）如下圖，加入 90，請詳細說明該如何調整 成一棵 AVL 樹？接著再加入 85，請詳細說明該如何調整成一棵 AVL 樹？ 接著再刪除 15，該如何調整成一棵 AVL 樹？請將最後調整後的 AVL 樹 中每個節點之平衡因子（balance factor）寫在節點旁邊。（25 分）

二、一串含有 8 個整數的資料：48, 55, 10, 88, 26, 80, 35, 40，請以第一個數值 為樞紐（pivot）進行快速排序法（quick sort），將這些資料由小排到大， 並寫出詳細的比較過程。（20 分）

一、資料結構中的二元樹（binary tree）依其走訪節點的順序可以得出不同的運算表示式。給予一中序（inorder）表示式 FBACEIGJH 和後序（postorder） 表示式 BCAFIHJGE，請說明並畫出其對應的二元樹。有一後序表示式 36 12 / 10 23 – * 50 40 – +（此運算式中的數值均為二位數），利用堆疊運算其結果為何？（請勿只寫出最後結果，需詳細寫出堆疊內每一步的變化並說明）。（20 分）