電子工程 111 年電子計算機原理考古題

假設下列的數字都是二進位的正數。（註：C 是有小數點的數字） A=(1011)2，B=(1111)2，C=(1011.1011)2 求A×B+C的結果並列出計算過程，結果用十進位表示。（20分）

在作業系統中，當一個行程（Process）執行時，它會改變狀態（State）， 常見的狀態有5 種：新建（new）、就緒（ready）、執行（running）、等待 （waiting）、結束（terminated）。請繪製行程狀態轉換圖（State Transition Diagram）表示這些狀態以及改變狀態的事件，並說明這些狀態與改變狀 態的事件。（20 分）

某個網際網路協定第四版（IPv4, Internet Protocol Version 4）的位址以二 進位表示如下： 10100011 00011001 00010001 00011110，回答下列問題並列出計算推導 過程。 它的十進位位址表示為何？（5 分） 它的位址用封包側錄軟體上看到的十六進位表示為何？（5 分） 一個IPv4 位址由網路編號（Network ID）和主機編號（Host ID）所組 成，若它的子網路遮罩（Subnet Mask）為255.255.255.0，則表示網路 編號的長度有幾個位元？（5 分） 承上題，它的子網路廣播位址（Subnet Broadcast Address）的十進位表 示為何？（5 分）

底下的C 語言程式的函式size 採用遞迴（recursive）呼叫的方式來算 出二元樹裡總共有幾個節點。struct node 是節點的定義，主程式main 傳給函式size 的參數是指向根節點（root node）的指標。 /*二元樹的節點有三個欄位：data 欄位，分別指向左、右兒子節點的 指標欄位*/ struct node { int data; struct node* left; struct node* right; }; int size (struct node* ptr) { if (ptr == NULL) return ___(a)____; else return _______(b)________; } 為了讓函式size 能夠運作正常，請寫出程式片段(a)和(b)。（a 和b 各5 分） 如果二元樹裡的節點總共有n 個，(c)請算出函式size 總共會被呼叫幾 次？（包含主程式main 呼叫函式size 那一次），(d)請敘述被呼叫次數 是如何計算出來的。（c 和d 各5 分）

有一棵二元搜尋樹（binary search tree）如下，其中圓圈內的數字代表節 點（node）的資料，請對下列問題先敘述作法後，再寫答案： 將此棵樹的節點資料用後序走訪（post-order traversal）的順序寫出。 （5 分） 畫出將資料15, 17 依序插入原本這棵樹後的二元搜尋樹。（5 分） 畫出原本這棵樹的每個節點（node）之左、右兒子（children）節點都 對調（swap）的二元樹。（5 分） 將上題所得到的二元樹裡的節點資料用中序走訪（in-order traversal） 的順序寫出。（5 分） 25 7 32 2 19 26 56