※ [本文转录自 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