[理工] [DS&Algo] [核對]-交大99-資뀠…

看板Grad-ProbAsk作者crazykk (JK)時間15年前 (2010/03/16 14:38)推噓23(23推 0噓 18→)

留言41則, 22人參與討論串1/1

12.Consider the following program. void main() { printf("%4d",f(95) ); } int f(int n) if(n>100) return (n-10); return (f(f(n+11))); } (26).The output is an integer. How many digits are there? (A)1 (B)2 (C)3 (D)4 (E)5 公佈答案:(B) (我認為是D) 原因:執行f(95)的結果是91 但是"%4d" 不論是2位數或3位數甚至是5位數，都是印出4位數 14.Given a weighted graph and two vertices s and t, we want to find a longest path from s to t. Which of the following statements are WRONG aboout this problem? Select the correct answers from the following 2 questions. i. This problem has a polynomail time algorithm. ii. This prombel can be solved by transforming it into shortest path problem. iii. This problem can be solved by using Dynamic Programming. iv. For a connected weighted graph the longest path has at least 3 edges. v. For a graph with n vettices. if the longest path has n-1 edges, then it passes through each vertex exactly once. 公佈答案:i,ii,iv (我認為是i,ii,iii,iv) 原因:longest path是NP-Complete Problem可用Dynamic Programming解? 18.Please finish the following implementation of circular queue. class Queue { private: int orz,a,b; int data[3]; public: Queue() { orz=0; a=-1; b=0; } void Enqueue(int x) { if(IsFull()) { cout<<"Queue is full"<<endl; reutrn; } a=(a+1)%3; data[a]=x; if((a+1)%3==b) orz=1; } int Dequeue(void) { int x; if(IsEmpty()) { cout<<"Queue is empty"<<endl; return -1; } orz=0; x=data[ (42) ]; b%=3; return x; } int IsEmpty(void) { return (orz==0 && ((a+1)%3==b ? (43); } int IsFull(void) { return (orz==1) ? (44); } }; (42) (A)b (B)b++ (C)++b (D)b-- (E)--b 公佈答案(B) (我認為是C) 原因:從Enqueue程式中的a=(a+1)%3; data[a]=x; 可以看出他是先把a指標(即Rear)前進,之後再放data 因此在Dequeue時b指標(即Front)也要先前進，才能取出data 否則b指標所指內容可能是空的，產生擷取到錯誤的資料情形發生 20. (48)Consider the case of inserting 10,8,12,6,4,2,11,1 into an empty min heap.Please show the first visited node when using LVR to traverse theresultant tree. (A)11 (B)10 (C)8 (D)12 (E)6 公佈答案(B) (我認為是C,B也沒錯,若用Top-down方式建立,答案是B) 原因:從題組4可發現到採用Bottom-up方式建立max heap 因此這題我也採用Bottom-up方式建立min heap,如下所示 1 / \ 4 2 / \ / \ 6 10 12 11 / 8 LVR我想應該是inorder traversal 因此第一個拜訪的點應該是8 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 60.244.36.162 ※ 編輯: crazykk 來自: 60.244.36.162 (03/16 14:39) ※ 編輯: crazykk 來自: 60.244.36.162 (03/16 14:43)

→

Lukewind

03/16 14:42, , 1^F

03/16 14:42, 1^F

→

Lukewind

03/16 14:44, , 2^F

03/16 14:44, 2^F

→

Lukewind

03/16 14:46, , 3^F

03/16 14:46, 3^F