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

國際標準組織（international standard organization；ISO）定義了開放系統互連（open system interconnection；OSI）之7 層（layers）架構，試問其中有那些層有做流量控 制（flow control）？為何要做？各層的作法有何不同？（20 分）

有一導管（pipeline）處理機執行每一指令（instruction）必須分四級（stages）處理， 例如：擷取（fetch）、解碼（decode）、運算元擷取（operand fetch）、執行 （execute）四級。若各級之處理時間分別是：第一級需要80 奈秒（ns），第二級 需要50 奈秒，第三級需要90 奈秒，第四級需要40 奈秒（假設無其他延遲）。試 問：（20 分） ㈠若執行10 個指令，共需要多少時間？ ㈡若執行100 個指令，共需要多少時間？

乙太網路（Ethernet ）採用載波感測多重存取/ 碰撞偵測（carrier sense multiple access/collision detection；CSMA/CD）的存取（access）方式，請說明其原理。（20 分）

依序讀入一串數字：71, 48, 33, 11, 78, 51, 63, 18, 25, 9，試求其：（20 分） ㈠最大堆積樹（maximum heap tree）。 ㈡二元搜尋樹（binary search tree）。

試依下圖之無向性連結圖（undirected connected graph），建構一個最小成本生成樹 （minimum cost spanning tree）並標示其生成順序，每一鏈路（link）之成本標示在 其旁邊，而啟始（source）節點（node）為節點0：（20 分） ㈠採用Prim’s algorithm 且無任何限制。 ㈡採用Prim’s algorithm 但限制每一分支（branch）最多只能有兩條鏈路。

3 2 5 1 4 0 10 26 20 24 16 18 14 28 22 12 Source node