計科概 2010/06/22 期末考; Closed book; 但可以帶一張手寫A4小抄(不可影印) ================================== for more Q & A, please see: http://www.csie.nctu.edu.tw/~tsaiwn/introcs/00_CS2/ 尤其是裡面有個子目錄 02_handouts/ 裡面還有許多子目錄喔! 都是可能考的題目 :-) *** 與各習題有關的都可能會考 ! 期中考考過的仍可能再考:-) Q01: C++ 呼叫函數時可以使用 call by value 或 call by reference (a)請就 Compiler 的對它們的處理方法略作說明? 包括函數內如何抓參數? (b)要如何利用C++ 的 compiler 研究這點? A:(a) 被叫用的函數一定到堆疊拿資料(透過 CPU 的 BP 加一個值) Call by value: copy 一份參數的 value 放到堆疊 call by Reference: 把參數的 address 放到堆疊, 然後被叫用的 函數內用到其對應參數都改為 *參數名, 也就是取值或稱"解參照" 就是說, 跟 call by address to pointer 完全一樣, 只是使用者寫法不同 call by Reference: 把參數的 address 放到堆疊, 然後被叫用的 函數內是用指標變數接收此參數當作所需值的 address (b)編譯時用 "-S" 可生出組語程式, 寫個有函數的簡單程式生出組語研究其內容 Q02: Compiler 如何做出 function name overloading 的功能? Compiler 如何做出 Polymorphism 的功能? 也要討論 static binding 與 dynamic binding. A: Binding 一般指變數 bind 到記憶體, 或是函數名稱 bind 到正確 function. Function name overloading : 函數名稱重複, 也就是說多個函數同名, 但是要從參數的數目或type可看出要用哪一個 function; Compiler編譯時 會把各參數的type偷加到函數名稱, 如此就不會叫錯對象, 自動 bind 到正 確函數, 因在 Run 之前就 bind好, 是為 static binding! Polymorphism 是指用 Base class 的指標(C++)或參考(Java)去操作 衍生類別的物件, 或說指定要執行某衍生類別的函數; 也就是說 Polymorphism 的function不但同名且參數也相同, 但它們是在有繼承關係之 不同的 class 內; Compiler 須翻譯出一些句子, 在 生出物件時把正確的 function之address填到某處, 然後C++翻譯 p->fun( ); 或Java翻為 p.fun( ); 這類句子時要翻譯成去執行 p 指過去後位移若干再指過去之處後再位移若干之 內含所指過去的函數; 這樣在 Run time 才 bind 到正確 function, 此即為 dynamic binding ! Q03: C++ STL 的 vector 與 Java 的 Vector 都會"自動長大", 請大略說明是怎麼做到 "自動長大" ? A: C++ STL 的 vector 其實是偷用指標指到用 new 要來的空間; 要塞入資料時若發現 size 已經等於 capacity, 則要長大: 去要一塊兩倍 capacity 的新空間, 把舊資料都 copy 過去, 把內部指標改指到新區域, 更新 capacity 和 size, 把舊區域還掉! (記得要先備份指到舊區域的指標以免沒法還!) Q04: 假設你的電腦剛開機且尚未收到任何網路封包, 若你此時下了命令 ping www.cs.nctu.edu.tw 請大略描述你電腦此時會做的所有事情 A: 目標要做出一個 ICMP echo request 封包, ICMP 封包其實是一個 IP 封包, protocol # 填寫 1 (6為 TCP, 17是UDP) (1)要先找出 www.cs.nctu.edu.tw 的 IP address a. 先查看 系統內的system32\drivers\etc\ 內的 hosts 檔案內 b. 找不到就去問 DNS server (我電腦上設定的, 用 IP 形式) 當然為了要問 DNS 須把封包送去 DSN server, 此時會做類似以下的工作以便做出適當 ether frame送往 DSN server 注意若 DNS Server 與我不在同個 subnet 則封包會先送往 Gateway (2)有了 IP 後須找出該 IP 的 MAC 或此機的 Geteway 的 MAC: a. 把該 IP 與 我設的 subnet mask 做 bitwise and b. 看看有否等於 "我的 IP 與我設的 subnet mask 做 bitwise and" 若相等表示該 IP 與我在同一個 subnet, 用 "ARP 查詢"去找出其 MAC 否則須用 "ARP 查詢"去找出我設的Geteway 的 MAC (3) 利用上述的 IP 做出內含 ICMP echo request的 IP 封包, 搭配 (2)問到的 MAC 做出 ether frame 註明是 IP (frame type 0x0800) 把這封包送出後等著接受 ICMP echo reply 封包 Q05: 很多系統有提供 tracert 或 traceroute 命令 請大略說出該程式如何做事? 要說出其原理? A: tracert 主要是要查出要到目的電腦會經過的各個路由器節點. 因為要找出所有經過的 "hop" , 所以要把封包中 TTL (Time To Live) 的值由 1 逐步增加製作 ICMP Echo Request 封包, 因為 根據規定封包經過 Router (包括Layer 3 的 switch) 時要把 TTL 減去 1, 若答案是 0 須把封包丟棄並回報, 於是 TTL 是 1 在第一個 Router 節點就會被丟棄並回報, TTL 是 2 在第二關的Router 節點就會被丟棄並回報, ... 於是就可查出所有經過的節點, 或是知道斷在何節點. Q06: HTML, DHTML, XML, CSS, 做網頁常用的... 請看我的投影片 ! A: 請看我給的投影片! Q07: Greedy? Dynamic programming ? 如何印出 1 到 52 階乘? ==> 簡易大數處理, 用 array 自己處理 如何算 C(m, n) 阿就是 m 取 n ? ==> Pascal Triangle 各種常見的 sort algorithm 及其 time complexity ? * insertion sort, selection, bubble, quick sort 各 sort 的 Big O ( ? ) ?是否 Stable sort? 穩定 ? Stable means that if two object resolve to the same value, their relative orders in the list are guaranteed to be the same as they were sorted before. ** qsort( ) in C Library is NOT stable; mergesort( ) is Stable! The qsort() function conforms to ISO/IEC 9899:1990 ** sort( ) in C++STL is NOT stable;However,stable_sort( ) is a stable sort. ** java.util.Arrays.sort( ) is a stable sort Q08: Fibonacci Rabbit problem? 注意公式的導法! 改了條件的 Fibonacci problem? 注意公式的導法! A: 請自己推導 (a)正常問題 (b)長為成兔要兩倍時間的 (c)懷孕期加倍的 ?還有, 用 recursive 算 fib(n) 若n 大一些會有何問題? 怎辦? A:==> 會算很久, 改用 Loop ==> 若很大則答案即使用 long long 也會 overflow, 可自己處理 Big number Q09: Prolog, Lisp program ** 請看看我給的程式範例, 包括 Prolog 與 Lisp 範例 Shuei(chang3) ? find GCD? moving between rooms ? Q10: XP (eXtreme Programming) ? 大略說明何謂 pair programming? 請寫出 eXtreme Programming 十二條法則中除了 pair programming外的三條法則 Q11: Hanoi tower problem? Q12: OOP 的四大 features; Object base vs. OO; OOA/OOD/OOP, CRC, UML Q13: Binary tree representation of tree? Q14: Binary search tree? Expression tree? Parsing Tree? Game Tree? Q15: RDBMS; select/project/join; SQL 參看課本第九章與我的投影片 Q16: 何謂 Heuristic Strategies 與 Heuristic function? 請用 eight-puzzle 與 Othello (黑白棋)為例說明之 A: 依據大多數人的經驗做決策稱 Heuristic Strategy, 此時通常用公式量化為一個值作為決策參考. eight-puzzle: 把每個錯的格子要走幾格才會到正確位置全部加起來, 每次選最小的(若一樣大則任選一步) Othello: 口訣是金角銀邊, 也就是四個角最好, 所以佔到角可給較高分數, 角的隔壁那格給予負的比重(weight), 以此原則給每個格子一個比重, 依此算出黑子與白子各得幾分以決定該走哪一步? 注意對我有利就是對對方不利, 所以隔一步時要考慮對對方有利的! Q17: 何謂 3D Modeling and Rendering ? (參看我的投影片) 全世界最多與電影有關的電腦動畫公司的地方? (hint:號稱南半球的好萊塢) 皮克斯工作室Pixar Animation Studios)在1986~2006間老闆是誰? Q18: 簡述 Artificial Neural Networks ? A: 模仿人類的神經網路, 原則上 除了輸入層(Input layer)通常是一些感測器, 其它每個神經元(Neuron)會有許多輸入, 有一個輸出, 每個輸入不是0就是1, 每個輸出也是 0 或 1, 把每個輸入乘上一個權重, 算出的值若大於門檻值就輸出 1 否則輸出 0; 建立模型後, 可通過訓練樣本修正除了輸入層外的各個權重(weight), 此即類神經網路的自動學習過程。 Q19: (a)請用口語化方式說明何謂 Halting problem? A: 是否有一個程式或方法, 可以判斷任一程式是否會結束? 就是說能否寫出這個可以讀入任一程式然後輸出 yes 或 no 以便 告訴我們其所讀入的程式是否會停止 (b)請證明 Halting problem 是無解的 A: 假設你已經寫出這程式, 那我們要求你的程式在認為"所讀入之程式"會停止就令 x 為 1, 否則令 x 為 0; (考慮類似 C 的語言), 接著我把你寫的這程式尾補上這句: while(x) { } 請問這新的程式是否會停止?? (i) 若你說會停, 則把此程式喂給自己, 執行到上述 while(x) { } 之前一句 x 應該是 1, 接著 while(x) { } 會陷入無窮 Loop 所以程式不會停 ==> 茅盾 (ii) 若你說會不會停, 則把此程式喂給自己, 執行到上述 while(x) { } 之前一句 x 應該是 0, 接著 while(x) { } 會立刻結束掉 那就是程式會停 ==> 茅盾 由上述兩個茅盾可知原先說有寫出之程式有問題 ! 該程式不存在!! Bare Bones Language ? Q20: P vs. NP? Turing machine ? The Enigma Cipher (奇謎密碼) ? Q21: 請只用C語言這三招 --x; ++x; while(x){ /*...*/} 以及變數宣告與函數的 return , 且可用 recursive, 寫一函數 int gcd(int m, int n) 可以求出 m 與 n 的 GCD 但為了效率, 可用 x=0; 取代 while(x) --x; A: int invert(int x) { int ans; while(ans)--ans; // ans=0; ++ans; // ans = 1; while(x) { --ans; while(x)--x; // x=0; } return ans; }//invert(x int mymod(int m, int n){ //this function will return m%n; int n2, n3, tmp, again, kk; n2=0; //while(n2)--n2; n3=0; //while(n3)--n3; tmp=0; //while(tmp)--tmp; again=0; //while(again)--again; // again = 0; ++again; // again = 1 while(again) { // Loop until again == 0 while(n){--n; ++n2; ++tmp;} // save n in tmp while(n2){ --n2; --m; kk = invert(m); while(kk) { // kk ==1 means m = 0 --kk; // kk=0; --again; // again = 0; } }//while n2 while(tmp){ --tmp; ++n; } // recover n }// again // if m !=0 then Let m = m + n 因為減過頭了 ! kk = invert(m); while(kk) { // kk==1 means m = 0; --kk; // kk = 0; n=0; //while(n) --n; // n = 0; } while(n) { --n; ++m; } // 因 m 減過頭要加回去 return m; // this is the answer of m % n } //mymod( ////// int gcd(int m, int n) { int n2, n3, tmp, ntest, r; while(tmp) --tmp; // tmp=0; while(n) {--n, ++tmp); // tmp = n; while(tmp){--tmp; ++n; ++n2; ++n3;} // recover n; n2 = n3 = n; ntest = invert(n); while(ntest) { // ntest == 1 means n == 0 return m; //if(n==0) return m; --ntest; // ntest = 0; //because it is one } //r = m%n; r = mymod(m, n); // 注意 n 不是 0 return gcd(n, r); } // gcd( Q22: function/procedure, RPC, RMI, CORBA, Web Service =================================================== * qsort( ) in C Library is NOT stable; mergesort( ) is Stable! The qsort() function conforms to ISO/IEC 9899:1990 * sort( ) in C++ STL is NOT stable (quick sort); However, stable_sort( ) is a stable sort. * java.util.Arrays.sort( ) is a stable sort. (merge sort) ============================================== ========================