※ [本文轉錄自 future1234 信箱]
作者: future1234 (Creep)
標題: 輔大96
時間: Wed Jul 16 09:03:51 2008
1.(a) 在time-sharing system中,當process取得cpu控制使用權的時間到時(time slice=0)
則process交出cpu控制權,O.S並把cpu控制權交給下一個優先執行的process
(b) time slice太短: 造成process之間, "context switching"太頻繁,浪費系統資源
time slice太長: 造成FCFS的情形發生,容易產生starvation
2.(a) Application
Presentation
Session
Transport
Network
Data Link
Physical
(b) (i) Data Link
(ii) Network
(iii) Application
(iv) Application
(v) Presentation
3.(a)資料共2N筆,分成兩部分,使得total ages的差距為"最大"
我採selction sort做排序,採由大到小
並且只做到第N筆 ,也就是 {a[1] > a[2] >.... > a[N]} {..........}
^^^^^^^^^^^^^^^^^^^^^^^^^^ ^^^^^^^^^^^
前N筆資料 後N筆資料,沒排序,
但其中一個都比前N筆的小
假設最差的情形,selction sort 則做了 N(N-1)/2次比較交換 , 即 T(n) = O(n^2)
則此時兩筆資料的total ages差距為最大.
Algorithm如下:
Procedure SelectSort(list[],N)
begin
For i=0 to (N/2) do
begin
m=i;
For j=(i+1) to N/2 do
If list[j].key > list[m].key then m=j;
If (m!=i) then SWAP(list[m],list[i]);
end
end
(b)資料共2N筆,分成兩部分,使得total ages的差距為最小
分兩個步驟,第一個先用selection sort把2N資料都排序完, 由大到小
則,a[1] > a[2] > a[3]......> a[2N-1] > a[2N]
第二個步驟,做SWAP的動作
把a[2]跟a[N+1]做SWAP, a[3]跟a[N+2]做SWAP ,....
所以,第一個步驟花了 2N(2N-1)/2次比較交換
第二個不步驟 (N-1)次的SWAP
所以,T(n) = 2N(2N-1)/2 + (N-1) =....=O(n^2)
4.我不會...
5.(a)Linked list , 因為只要做指標的轉移 , 而array必須搬動相當的資料,在作插入的動作
(b)Array , 因為array本身就是random access的機制,存取100th資料,只要透過index(索引)
就可以直接讀取到100th的資料,但Linked list必須使用指標,從第一筆資料data->next...
到100th資料
(c)Array , 因為array本身就是random access的機制,透過index找到資料,且Linked list
必須從第一個做搜尋(sequential),直到找到資料
(d)一樣 , 因為sorting algorithm本身就適合各種資料型態的排序
6.(a)4次碰撞
148883 % 409 =7
116982 % 409 =8
176285 % 409 =6
80989 % 409 =7
143973 % 409 =5
95304 % 409 =7
186920 % 409 =7
在bucket #7 共碰撞4次 (假設bucket slot=1)
(b) bucket size = 4 (用4取餘數,ex:148883 % 4 = 3)
0 95304,186920
1 176285,80989,143973
2 116982
3 148883
7. C:Ciphertext ,P:Plaintext
C=P^e mod r
P=C^d mod r
public key(r,e)
private key(r,d)
以上為RSA加密解密的公式
此題,r=15,e=3,d=11
(a) sender做加密的動作 ,產生Ciphertext
其中P=12 , 因為 "Happy summer." ,共12個字元
^^^^^ ^^^^^^^
C=P^e mod r = 12^3 mod 15 = 3
(b) receiver做解密的動作,產生Plaintext
其中C=3 , 因為上題我們產生Ciphertext的長度為3
P=C^d mod r = 3^11 mod 15 = 12
為12個字元,即原本的"Happy summer."
8.(a) 2^6 * 2^20 / 2^2 = 2^24
共24 bits
(b) 2^10 * 2^16 = 2^26 (controllers)
9. J
/ \
C I
/ \ / \
B D G H
/ / \
A E F
10. 這題解法很多,也就是Huffman tree不只一個, 但相同的是他們總bits是相同的
102
/ \
49 53
/ \ / \
20 29 31 22
/ \ / \ E / \
12 8 9 20 14 8
A B C D F G
其中"/"為0 ,"\"為1 ,我就不畫上去了,考試你要畫上去,怕看起來太亂
所以透過Huffman encoding的結果如下
A 000
B 001
C 010
D 011
E 10
F 110
G 111
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 211.74.191.134
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.119.162.51