電子工程 100 年計算機概要考古題

將127 個相異正整數排序後，由小到大插入至一個空的二元搜尋樹（binary search tree），請問利用此二元搜尋樹尋找127 個數值中的任一數值，其最差情況要走訪過幾個節點？

設以G 表示一非多重圖形（multigraph）、無自身邊線（self edge）之有向圖形（directed graph）結構，並以VE表示G 之頂點（vertex）數，以表示G 之邊線（edge）數。則下列選項中有關G 之敘述何者正確？

Hash table 的溢位處理方法中，將hash 到相同位址的鍵值以鏈結串列儲存的策略稱為：

若一整數陣列（array）使用C 程式語言之語法宣告為K[12] [12] [12]，且K[7] [7] [7]儲存於記憶體中之位址（address）為631976。假設記憶體中儲存一個整數（integer）資料必須使用4 個位元組（byte），且使用列為主順序（row major order）之方式儲存陣列之組成元素，則下列各選項何者正確？

在由n 個節點構成的單向串列（singly linked list）中，若已知某節點x 前一個節點的位置，則從串列中刪除節點x 所花費的時間為：

下列那一個運算式的後序表示法（postfix notation）為abc+×d-？

當圖形中出現負數成本的edge 時，應採用何種演算法才能正確求出圖形中兩個節點的最短路徑？

執行快速排序法（quick sort）的最差時間複雜度為：

下列何者屬於資料封裝（data encapsulation）的機制？

假設只有一個節點的AVL 樹的高度為0，請問高度為4 的AVL 樹最少有幾個節點？

下列作業系統中，何者採用了微核心（micro kernel）架構？

在電腦系統中，編寫好的C 程式會經過數個系統程式轉換為可執行的程式碼（binary code）後，才能被載入到記憶體中準備執行。這些系統程式的執行順序為下列何者？

在一個分頁系統（paging system）中，假設邏輯位址（logical address）為32 bits，分頁大小（page size）為4K bytes，實體記憶體（physical memory）為256M bytes。此系統使用單一層次分頁表（single-level page table）且每一分頁表項目（page table entry）佔4 bytes。假設目前有3 個程序（processes）在系統中，則該系統最多需要用多少實體記憶體來存這些程序的分頁表？

下圖是利用解碼器（decoder）實作布林函數F 的組合電路圖。下列何者是F 的布林函式？

一個4 階段管道化精簡指令集計算機（RISC）包含指令提取階段、解碼和運算元提取階段、執行階段以及寫回階段。假設在執行之初管道內並無其他指令，執行時脈為200 MHz，且當有資料危障（data hazard）的可能時，只要提供值的指令之寫回階段於前半週期完成，則若需要該值的指令之解碼和運算元提取階段於同一週期完成，也就是同一個暫存器的前寫後讀於同一個週期中發生，即可避免資料錯誤。試問正確地執行下列6 道指令直至完成最少需要多少時間？ADDR1,R2,R3SUBR4,R1,R5ANDR2,R4,R7XORR10,R2,R11ORR12,R10,R13ADDR1,R10,R13（註：各指令中第一個暫存器為目的暫存器，餘為來源暫存器。）

在邏輯電路中，令AND gate 最少可用x 個NAND gate 表示，OR gate 最少可用y 個NAND gate 表示，NOTgate 最少可用z 個NAND gate 表示，假設上述AND、OR、NAND gates 均為具有二個輸入者，則x+y+z＝？

下列關於4 位元二進位制的數值表示法，何者為正確的描述？

以下有關於磁碟陣列（redundant array of inexpensive disks, RAID）的敘述，何者錯誤？

0yz1345673 × 8decoderFx220在一電腦系統上，某程式的執行時間中，處理機有80%花在計算， 剩餘的20%時間為存取磁碟檔案資料。若將其處理機由單核心升級到四核心，每一核心的架構與時脈不變，程式也具有理想的平行度並且予以適當平行化，則該程式整體效能最高可提升為多少倍？

以下何者為組成一台電腦之基本元件？(A)輸入裝置 (B)輸出裝置 (C)記憶體 (D)資料通路（datapath）⑤控制單元

在分頁（paging）機制中，下列那一項單元或元件可做為分頁表（page table）的快取（caching）機制？

試問下列何者為通用閘（universal gate）？通用閘的意思是任何布林函數（boolean function）均可僅用此種邏輯閘即予實現：

下列何者不等於十進位數(36) ？10

在開放系統互連（Open System Interconnection, OSI）參考模型之網路架構中，下列何者是網路層（networklayer）所負責的工作？

以下有關資訊安全的敘述何者錯誤？

在電腦網路中，SNMP 之用途為：

下列那一種網路服務協定，在實際應用上，通常建構在UDP（User Datagram Protocol）網路通信協定之上？

ISO 組織將網路管理區分為五大項目，以下何者不在其中？

在Internet 架構中，那一層通訊協定負責提供不同主機上的程序（processes）之間的邏輯通道（logical channels）？

網頁代理伺服器（Proxy）之功能為：

網路中每一台主機均需有IP 位址，以下何種協定用來自動設定IP 位址以方便管理網路：

在C-like 程式語言中，陣列（array）中最小的索引值（index）為何？

已知一C 語言程式中，宣告陣列A 為int A[10][4]，且A 在記憶體的位址為0x0080（0x 代表16 進位表示法），若每個int 資料使用4 個位元組（byte），請問A[3][3]使用的記憶體位址為何？

C 或C++程式語言中，當「&」運算子（operator）置於變數（variable）前時，其代表的意義為何？

關於C++或Java 程式語言中的建構子（constructor），下列敘述何者正確？

下列以C 程式語言撰寫之程式執行後產生之輸出為何？#include <stdio.h>int main(){int a = 1, b = 2;printf("%d", (a++)+(++b));return 0;}

下列以C 程式語言撰寫之程式執行後，若使用者輸入的數值為20，則畫面上的輸出為何？#include <stdio.h>int input(int p){scanf("%d", &p);return p*2;}int main(){int num = 10;input(num);printf("%d", num);return 0;}

下列以C++程式語言撰寫之程式執行後的輸出為何？#include <iostream>using namespace std;class P{public:P() { cout << 'A'; }~ P() { cout << 'B'; }};class Q: public P{public:Q(){ cout << 'C'; }~ Q() { cout << 'D'; }};int main(){Q q;return 0;}

下列以C++程式語言撰寫之程式執行後的輸出為何？#include <iostream>using namespace std;int main(){int num = 0;int *p;int &r = num;r = 5;p = &num;*p = 10;printf("%d", r);return 0;}