一、解釋名詞
 (1) 臨界區間(Critical Section)
 (2) 行程控制表(process control table或process control block)
 (3) Medium-term scheduler(中程排班程式)
二、何謂本文切換(Context Switch)?並請討論其與時間量(time quantum, 或稱時間片段time slice)間的關連性
三、考慮以下一組行程，其中CPU分割時間長度是以毫秒為單位：

┌──┬────┬───────────┐
│行程│到達時間│所需的CPU執行週期時間 │
├──┼────┼───────────┤
│ P1 │   0    │           8          │
├──┼────┼───────────┤
│ P2 │   5    │           2          │
├──┼────┼───────────┤
│ P3 │   3    │           4          │
├──┼────┼───────────┤
│ P4 │   1    │           3          │           
├──┼────┼───────────┤
│ P5 │   5    │           2          │
├──┼────┼───────────┤
│ P6 │   2    │           5          │
└──┴────┴───────────┘

Gantt Chart畫法請一下列方式繪製：

FCFS
      ┌───┬───┬────────┬──┐
      │Pi    │Pj    │     ......     │Pn  │
      └───┴───┴────────┴──┘
時間軸 0      5       7     ........    20    24


假設這些行程依上表所列時間到達，及所需CPU執行週期時間(若條件相同時，以process id較小者優先)，請問：

(a) 畫出這些行程以(1)先到先做(FCFS)、(2)不可搶先最短的工作先做(nonpreemptive SJF)、(3)可搶先最短的工作先做(preemptive SJF)和(4)依序循環(Round-Robin)(quantum=3)排班演算法執行的甘特圖(Gantt Chard)。【請依序寫】
(b) 在上述的每一個排班演算法中，每一個行程的回復時間(turnaround time)是多少？(最後請以表格匯整依序作答)
(c)上述的各演算法之中，每一個行程的等待時間(waiting time)是多少？(最後請以表格匯整依序作答)

四、何謂號誌(semaphores)？其優點為何？
五、[1]請說明臨界區間問題必須滿足的三個要求
    [2]依序解釋下列演算法是否為何滿足或步滿足上列的三項要求

[1 ] do {
[2 ]  waiting[i] = true;
[3 ]  key = true;
[4 ]  while(waiting[i] and key)
   key := TestAndSet(lock);
[5 ]  waiting[i] := false;
 
[6 ]    Critical Section (C.S.)
 
[7 ]  j:=(i+1)%n;
[8 ]  while (j!=i)and !(waiting[j])
   j:=(j+1)%n;
[9 ]  if (j==i)
   lock:=false;
  else
  waiting[j]:=false;

[10]   remainder section 
[11] } while (1);

1. 試分別用Prim's and Kruskal演算法畫出下圖最校展開樹(step by step)，並說明兩演算法的差異：

鄰接陣列(x代表兩點之間沒有邊)

   A  B  C  D  E  F  G
 ┌                    ┐
A│0  2  x  x  3  7  x │
B│2  0  5  x  4  x  x │
C│x  5  0  9  6  x  x │
D│x  x  9  0  x  10 12│
E│3  4  6  x  0  8  15│
F│7  x  x  10 8  0  11│
G│x  x  x  12 15 11 0 │ 
 └                    ┘

2. 請利用Dijkstra's Alogorithm找出V0到其他頂點的最短路徑Shortest Paths(請詳列你的步驟及所用到的相關資料陣列)

鄰接陣列COST = ()
    V0 V1 V2 V3 V4 V5 V6
  ┌                    ┐
V0│0  1  4  5  ∞ ∞ ∞│
V1│1  0  ∞ 2  ∞ ∞ ∞│
V2│4  ∞ 0  4  ∞ 3  ∞│
V3│5  2  4  0  5  2  ∞│
V4│∞ ∞ ∞ 5  0  ∞ 6 │
V5│∞ ∞ 3  2  ∞ 0  4 │
V6│∞ ∞ ∞ ∞ 6  4  0 │
  └                    ┘

初值
DIST = [0 1 4 5 ∞ ∞ ∞]
PRIOR = [0 0 0 0 0 0 0]
Decides = [1 0 0 0 0 0 0]

DIST[W] > DIST[1] + COST[1][W]

請解釋上述符號及公式之意義，並試算之

3. 考慮下列四個矩陣相乘，說明你的演法如何求一個最佳解，使得相乘過程中使用的乘法數目最少(需列出Dynamic Programming的關係式與簡單的想法)

 　Ａ　 ╳ 　 Ｂ　 ╳ 　Ｃ　 ╳　 Ｄ
 20╳2       2╳30    30╳12    12╳18

4. 何謂0-1Knapsack Problem

作業系統92年考古題

一. 解釋名詞

二. 行程在執行時其狀態會不斷的轉變，請畫出行程狀態圖（狀態、狀態轉換的原因皆須列出），並說明Long-term scheduler（長期排班程式）、Medium-term scheduler（中期排班程式）各指哪一部份，並說明其主要的目的。 P.95

三. 何謂號誌（semaphores）？其優點為何？ P.188考慮以下一組行程，其中CPU分割時間長度是以毫秒為單位︰

四. 考慮以下一組行程，其中CPU分割時間長度是以毫秒為單位︰

五. 請說明下列演算法是否滿足臨界區間的三項要件（依序解釋為何滿足或不滿足，請一併說明該三項要件）

六. 請舉出一個典型的同步問題，並簡略提出你的解決想法。

七. （加分題）接第五題，你是否能以test-and-set或compare-and-swap指令來實做該題

問答題：
一、試述我國古典目錄體制中「篇目」、「總序」、「小序」及序錄之意義。
二、試述「目錄」與「目錄學」的意義。
三、試述劉向《別錄》與劉歆《七略》之異同與關係，其體制對後世有何影響？
四、解釋下列中國目錄學文獻之意義：
  (1) 漢書藝文志總序云：「成帝時，以書頗散亡，使謁者陳農，求遺書於天下，詔光錄大夫劉向，校經傳、諸子、詩賦；步兵校尉任宏，校兵書，太史令伊咸，校數術，侍醫李柱國，校方技，每一書已，向輒條其篇目，撮其指意，錄而奏之，會向卒，哀帝復使向子侍中奉車都尉歆卒父業」。
  (2) 余嘉錫《目錄學發微》云：「劉歆嗣父之業，部次群書，分為六略，又敘各家之源流利弊，總為一篇，謂之輯略，以當發凡起例，班固就七略刪取其要，以為藝文志，因散輯略之文，分載各類之後，以便觀覽，後之學者，不知其然，以為七略只存其六，其實輯略之原文具在也」。

1. 試述搜尋引擎的工作原理。
2. 發展出自動摘要網頁資訊之前，有哪些搜尋網路內容的工具？
3. 常有人把台灣當成中國的一省，有特別的依據嗎？試就國際對國家的定義，說明之。
4. 除了搜尋所有網頁之外，Google還可搜尋哪些內容？舉例說明之。
5. 對Google的負面批評亦不在少數，申論之。
6. 請問ICANN認可多少通用上層網域名稱？並說明其預設用途。
7. IPv4與IPv6有何不同？在IPv4的架構下，理論上，最多可容納多少設備同時上網？計算之。
8. 有了Google之類的搜尋引擎後，圖書館還有存在的價值嗎？

一、請說明計算費氏級數(Fibonacci Term)Iterative及Recusive兩種作法的優劣
二、請利用Quick Sort演算法將下列串列排序，請將過程逐步列出
    15 22 13 27 12 10 20 25
三、請利用Divide-and-Conquer方法，說明如何解決下列問題
  (1) 大整數相乘問題(Multiplication of Large Integers)
  (2) 矩陣相乘(Strassen's Matrix Multiplication Algorithm)
四、請說明Dynamic Programming與Divide-and-Conquer的異同？
五、(1) 利用遞迴的方式說明河內塔問題的解法？
    (2) 簡單計算河內塔問題的時間複雜度？

1. 由顧客導向的服務概念說明圖書館媒體服務概念的重要性。
2. 圖書館媒體中心之服務評鑑可以透過哪些層面進行？
3. 以環境心理學的角度解釋圖書館服務環境與顧客的關係。基於讀者環境適應的角度，圖書館的規劃應該掌握哪些要領？
4. 說明CD與唱片在清潔維護時，擦拭方式有何不同？
5. 何謂Keystone Effect？如何避免？
6. 解釋圖書館中何謂機能性空間？何謂非機能性空間？
7. 何謂「動態規劃」。圖書館媒體中心如何做好動線規劃？