作者brilliantl (brilliant)
看板Grad-ProbAsk
标题[理工] 106台科资工概论 对答案
时间Tue Jan 16 12:37:34 2018
各位大大好
刚写了台科考古但手边没答案
在这边po上我的答案
如果有写错的拜托各位多多指教 ((跪
题目:
https://imgur.com/w84LKMj
https://imgur.com/ZxDTFi5
https://imgur.com/QDiOI2W
https://imgur.com/cWCRoLW
我的答案：
1.F T F F T
2.(a) O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(2^n) < O(n!)
(b) Theta(n^2)
不是很确定
3.(a) //-de*+ab-cdf
(b) de-ab+cd-*/f/
4.(a) worse case: O(n^2)
best case: O(nlogn)
(b) 若是要将数列由小到大排序，worse case的情况是pivot都选到最小或最大值
best case 的情况是pivot都选到中位数
不是很确定是不是这样写就好
5.假设每个resource都只有一个=>RAG画出来有circular wait的现象=>有deadlock
6.(a)log_2(16)+log_2(2048) = 4+11 = 15 bits
(b)log_2(16) = 4 bits
(c)log_2(4)+log_2(2048) = 2+11 = 13 bits
7.8 times
有查过前面的文章，应该是对的
8.(a)code sequence 1: 1+1+8 = 10 => code sequence 1 执行比较多的指令
code sequence 2: 2+1+1 = 4
(b)code sequence 1: 1x7 + 1x3 + 8x1 = 18 cycles => 一样快
code sequence 2: 2x7 + 1x4 + 1x1 = 18 cycles
(c)code sequence 1: 18/10 = 1.8
code sequence 2: 18/4 = 4.5
(d)code from compilier 1: 10^9 x( 3x7 + 1x3 + 1x1)/( 5x10^9 ) = 5 seconds
code from compilier 2: 10^9 x( 1x7 + 3x3 + 4x1)/( 5x10^9 ) = 4 seconds
=> code form compilier 2 is faster
(e)code from compilier 1: 10^9 x(3+1+1)/(5x10^6) = 1000 mips
code from compilier 2: 10^9 x(1+3+4)/(
4x10^6) =
2000 mips
=>code from compilier 2 is faster
9.如图
https://imgur.com/MjbWiXu
10.(a) 2 no-ops between 16 and 20
2 no-ops between 20 and 24
(b) 假设branch是在EX stage决定的
total cycle = 3+1+3+(5-1) = 10 ctcles
虽然台科相较台清交容易，但还是怕手残有算错
还请各位帮忙找错，感激不尽！
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 27.246.42.23
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1516077457.A.AB1.html
1F：推 bighb69738: 8.e 1600 错了 应该除4 01/16 17:03
对欸! 感谢b大
2F：推 a1596482: 想请问第九题的cache 3，是不是只有4个block？这样我算 01/16 21:39
3F：→ a1596482: 只有两个hit而已 01/16 21:39
对!我手残写成8个，感谢
※ 编辑: brilliantl (111.249.1.196), 01/17/2018 00:32:47
4F：推 MaoJ: 10. (b) 11 02/04 00:47
5F：推 Monetelliz: 可以借问一下第五题DAG怎麽画吗 01/21 00:01