臺北巿立師範學院九十二學年度碩士班研究生入學考試試題

所　　別：數學資訊教育研究所

科　　目：計算機概論（資訊教育組）

考試時間：九十分鐘

※ 注意：不必抄題，作答時請將試題題號及答案依照順序寫在答卷上。(於本試題紙上作答者，不予計分)

壹、名詞解釋 (每題2分，共10分)

1、XML（2分）

2、Call by reference（2分）

3、CGI（2分）

4、Multithread（2分）

5、ADSL（2分）

貳、問答題 （每大題10分，共90分）

一、1、比較stack、queue之特性。 (2分)

2、請以array實作stack之push, pop函數。 (4分)

3、請運用stack說明如何將中序(infix)運算式轉換為中序(postfix)運算式？以a+(b-c*d)/e-f為例 。(4分)

二、1、比較linear search及binary search之時間複雜度(average case)。 (2分)

2、進行binary search之先決條件為何？ (1分)

3、給予二整數陣列A(存放學號)、B(存放成績), 此二陣列為平行陣列(如A[1] 存放學號,B[1] 存放該學號之成績)，索引1~n。請以binary search方式撰寫函數，輸入學號進行搜尋，傳回該學號之成績。(7分)

三、1、說明binary search tree(BST)進行單一資料搜尋之時間複雜度(average case及worst case)？在何種狀況會發生worst case？ (3分)

2、給予一系列字元資料：G、A、F、M、Z、X、Q、Y、C、H、D、B，建立一BST，請以圖形表示此BST 。(3分)

3、列出上述BST中序、前序、後序追蹤之結果。 (4分)

四、What is big-O notation? (10分)

五、1、說明OSI model 中data link layer、network layer之功能。 (4分)

2、說明網路中error detection and correction之三種技術之原理：parity checks,

CRC, checksum method。 (6分)

六、1、比較SMTP、HTTP。 (3分)

2、比較TCP、 UDP。 (3分)

3、有許多應用較適於利用UDP來傳輸，其適用UDP之理由何在？(4分)

七、Describe the connection-establishment procedure of TCP. (10分)

八、Describe how DHCP allows a host to obtain an IP address automatically. (DHCP: Dynamic Host Configuration Protocol) (10分)

九、What is the purpose of MAC address, IP address, and port number? (10分)