※ [本文轉錄自 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