[資工] 交大103考古 請教數題

[qoojordon (穎川琦)]

請教數題交大103年的考古 , 我把題目篩選 , 裁成兩張圖片 , 問題詳述於內文

http://ppt.cc/ywsx Algo+OS

http://ppt.cc/5gT6 數學


103 [Algo] : 以下自己都有一套說法 , 可是不太有把握 , 希望能互相討論

11a
我的答案 : false

all-pair shortedt path 演算法我只認識 Floyd-Warshall 和 Johnson  ,

前者複雜度 n^3 , 後者 VE+V^2logV , 如果是sparse matrix的話後者表現

的確實比較好 , 是否有其他更有說服力的說法 ?

-----------------------------------------------------------------

11d
我的答案 : true

想法是shortest path總值不變 , weight倍數放大的話 , 小者恆小者大者恆大

-----------------------------------------------------------------

11e
我的答案 : false

我的反例是不確定min-cut切到幾條edge , 構成min-cut的edge數量可能不同

會造成capacity改動後的異動

-----------------------------------------------------------------

103 [OS+Archi]

4.我算不出他選項裡的東西 , 差蠻遠的 , 不知道是不我理解錯誤

 我是用multilevel page table的概念去看這個記錄file的table

 一個block能存放的pointer數量為 8KB/4B=2K

 題目給的結構最大可以描述 9+2K+(2K)^2+(2K)^3 個block

 5120th logic block 不是只要查到 double indirect block pointer就可以知道了嗎?

 應該是很小的access次數 , 為啥選項給的數字都那麼cool...

-----------------------------------------------------------------

7.
我的答案: a

不過我不知道怎麼否定其他四個選項的敘述

-----------------------------------------------------------------

題組A:

這題想問: CPU搶奪是否只發生在 CS之外 ?

我自己的解法


T:0     2     4      7  8
  |-----|-----|------|--|
    P2     P1    P1   P2

T=1 , P1沒辦法搶奪P2 , 因為P2在CS ?

-----------------------------------------------------------------


題組B:

我的答案: c,d

simultaneous 應該要確保工作中的app都可以被放在記憶體內 , 所以我取 2GB/512MB = 4


concurrent 是app比較可以有機會喘息,所以我取 2GB/256MB = 8 , 應該有說法能讓

數字在往上 , 該怎麼解釋比較合理?

-----------------------------------------------------------------

103 [MATH]

1.這題題目有給函數內積定義 , 是否會用到?
  我直接取 y=x^3必過的三個點(-1,-1) (1,1) (2,8) 求回歸線可以嗎?

-----------------------------------------------------------------

4c. rank(A)<3  , 不可逆 , 無法套投影公式 ??

-----------------------------------------------------------------


8. 兩式化簡留An
   An = 2An-1 + 2An-2 + 3
   目測特徵根很醜 , 是否想法上有錯? (沒錯就只能當爆破大隊了= =...)

-----------------------------------------------------------------

9c. 這邊是想偷渡問小黃離散上 2-101: 證明(0,1) uncountable

    理解上是他先找一個 1-1函式 , 但還是有(0,1)中的數無法被這函式對到

    看不太懂它的1-1 函式是怎麼對應的 ?

-----------------------------------------------------------------


9d. 這邊我能想到的定理只有: x不是質數的話 -> 根號x內存在x的質因數
    by題意 , 兩因數很接近 , 820307開根號附近能找到因數
    因此估因數在910上下 , 然後開始爆破大隊 ? 還是有其他更好的想法 ?

-----------------------------------------------------------------

9e. 為方便敘述 , 令 a=23.3756 , b=23.3757
    無理數下意識只想到根號 ,但是a和b到小數第四位才比出勝負 ,
    代表需要做高次方再開高次根號才辦法找到落再a,b之間的數 ,
    所幸只爆破到 a^3=12772 , b^3=12773 就有解 , 取12773^(1/3)

    我覺得我自己的做法很投機 , 是否有其他比較好的想法或做法?



謝謝大家看到這邊 ~


另外徵求一起做考古題的戰友

目前我做的順序是 交大103到97->清大103到100->台大103到100->成大103

中壢地區可見面討論 , 其他地區可以一週約幾個固定時間 , 挑好討論範圍 ,

用SK互相討教 , 不然一個人被考古題虐也是挺悶的 , 意者站內信3Q

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.169.81.50
※ 文章網址: http://www.ptt.cc/bbs/Grad-ProbAsk/M.1411997276.A.449.html
推 j897495: 好快就在寫題目了XD
→ qoojordon: QQ 大四畢業那年沒寫考古題就去考根本當砲灰
推 A4P8T6X9: OS, 4 from first to 5120th
推 A4P8T6X9: MATH 1 要投影到二維，所以會用到。
→ A4P8T6X9: MATH 4C 可以套
→ A4P8T6X9: MATH 9C他的思路是假設存在一個完美的正整數對應到(0,1)
→ A4P8T6X9: 那麼我可以找到一個實數，其跟對應的每一個都不一樣。
→ A4P8T6X9: 找法就是如果第i個對應的第j個是4，那麼這個數的第j個
→ A4P8T6X9: 就設成5，否則就設成4，則這個絕對不會被對應到。
→ A4P8T6X9: algo 應該沒問題
推 FRAXIS: 就算是dense graph，Johnson也不會比較慢，不是嗎？
抱歉 , 隔了一段時間才回復 , 先謝謝樓上三位回覆 , 補充一下後續疑問


回應A4大：

[OS 4]

請問一下OS中介紹了3種 file配置在硬碟上的方式 , 都會有一個directory去

對照他的block分配 , 想請問這份directory是放置在 OS運作用的memory裡嗎?(Q4-1)

書上有提到的分配就有三種:

contiguous , linked (FAT) , index (combine的類型 Unix Inode)

http://ppt.cc/bauC  後兩者恐龍書上示意圖


index這種方法可以一次到位 , 不就可以省去很多不必要的 disk read?

例如要讀取的資料在logic block 10 , 以圖例來說 , 只需先讀19看index就知道去10

總共兩個read


link反而就要一個一個讀取才知道自己要的那區塊在哪 , 花了很多冤枉的read block


所以如果以題幹這種說法不是只要查一次index就直接跑到 5120th ?(Q4-2)


[MATH 1]

已解決 , 謝謝你

取 P2上basis = {1,x}作正交化 , x^3投影到基底分量相加


[MATH 4]

4c,

這題卡在太執著公式沒想到真正需要的是甚麼

A ~ U= 1 2 1 2
  r    0 0 1 3
       0 0 0 0    rank(A) = 2

取 1 , 3 行向量構成 3x2矩陣後套公式可得投影矩陣

-----------------------------------------------------

4d

我一直忽略最小平方解x是一個 4x1的向量 , 以下敘述以b代替題幹中的[-1 3 1]^T

所以不能直接把b投影到C(A) , 只能套normal equation爆破求解(會有兩個自由變數)

比較好奇的是 , 這個4x1解和b(3x1)投影到R(A)會有關係嗎? 我算出來看不太出關聯


-------------------------------------------------------

MATH 9C中的說法不太能接受


他是想表達 f: Z -> ri 在(0,1) 不是 1-1

假設 f(i) = ri , 對到小數ri的人是整數i


故意取一個和ri唱反調的小數 s , 然後說s沒有在f下被對到

這應該只能說 i 本來就不是對到s , 可是不能保證 s 沒被另外一個整數i'對到阿 ?




回應 FRAXIS:

你說的沒錯 , 我擔心還有神乎其技的all pair演算法
※ 編輯: qoojordon (118.169.81.50), 10/02/2014 00:06:43
※ 編輯: qoojordon (118.169.81.50), 10/02/2014 00:08:25
推 FRAXIS: 是有其他方法啊 但是應該只會出現在課本的reference裡面吧
推 JacobSyu: 1.有爭議啦...  102之後交大考題稍微有降低難度(?
→ JacobSyu: 11.a