###### tags: `資訊科技概論` # 一、程式設計(C++)筆試 1. 下列程式執行完,n為? ++**3**++ ``` javascript= int a=3,b=4,n; n=a/2+b/2; ``` 2. 下列程式執行完,n為? ++**3.5**++ ``` javascript= float a=3,b=4,n; n=a/2+b/2; ``` 3. 數學式 $\frac{h+1}{w^2}$,C/C++程式如何表示? ++**(h+1)/(w*w)**++ 4. n為3位數(如153),如何求a=n的百位數、b=n的十位數、c=n的個位數? ++**a=n/100;**++ ++**b=n/10%10;**++ ++**c=n%10;**++ 5. rand()會回傳介於0和32767之間的亂數,下列程式執行完,n的範圍為? ++**100<=n<=999**++ ``` javascript= int n=rand()%900+100; ``` 6. 下列程式之執行後,會輸出? ++**2 2**++ ``` javascript= int a=1,b=2; a=b; b=a; cout << a << " " << b; ``` 7. 下列程式之執行後,會輸出? ++**2 1**++ ``` javascript= int a=1,b=2; a=a+b; b=a-b; a=a-b; cout << a << " " << b; ``` 8. 下列程式要判斷n為奇數或偶數,空格內應填入? ++**n%2==1 或 n%2!=0**++ ``` javascript= if( ) cout << "n是奇數"; else cout << "n是偶數"; ``` 9. 下列程式之執行後,會輸出? ++**n是2的倍數**++ ``` javascript= int n=30; if(n%2==0) cout << "n是2的倍數"; else if(n%3==0) cout << "n是3的倍數"; else if(n%5==0) cout << "n是5的倍數"; else cout << "n不是2或3或5的倍數"; ``` 10. 下列程式之執行後,會輸出? ++**n是2的倍數。n是3的倍數。**++ ``` javascript= int n=6; if(n%2==0) cout << "n是2的倍數。"; if(n%3==0) cout << "n是3的倍數。"; if(n%5==0) cout << "n是5的倍數。"; ``` 11. 若要在if條件式判斷 $80\le score\le89$,C/C++程式如何表示? ++**score>=80 && score<=89**++ 12. 下列程式執行完,sum為? ++**10**++ ``` javascript= int sum=0; for(int i=0;i<5;i++) sum=sum+i; ``` 13. 下列程式執行完,sum為? ++**30**++ ``` javascript= int sum=0; for(int i=0;i<5;i++) sum=sum+i*i; ``` 14. 下列程式執行完,sum為? ++**18**++ ``` javascript= int sum=0; for(int i=0;i<=10;i+=3) sum+=i; ``` 15. 下列程式執行完,會印出? ++**0 2 4 6 8**++ ``` javascript= for(int i=0;i<10;i++) { cout << i << " "; i=i+1; } ``` 16. 下列程式執行完,sum為? ++**30**++ ``` javascript= int sum=0; for(int i=0;i<20;i++) if(i%5==0) sum+=i; ``` 17. 下列程式執行完,sum為? ++**36**++ ``` javascript= int sum=0; for(int i=0;i<20;i++) if(i%2==0 && i%3==0) sum+=i; ``` 18. 下列程式執行完,cnt為? ++**25**++ ``` javascript= int cnt=0; for(int i=0;i<5;i++) for(int j=0;j<5;j++) cnt++; ``` 19. 下列程式執行完,cnt為? ++**55**++ ``` javascript= int cnt=0,n=10; for(int i=0;i<n;i++) for(int j=i;j<n;j++) cnt++; ``` 20. 下列程式會印出什麼圖形? **☆** **☆☆** ++**☆☆☆**++ ``` javascript= for(int i=0;i<3;i++) { for(int j=0;j<=i;j++) { cout << "☆"; } cout << endl; } ``` 21. 下列程式執行後,會印出? ++**4 8 16 32 64 128**++ ``` javascript= int n=2; while(n < 100) { n=2*n; cout << n << " "; } ``` 22. 下列程式執行後,會印出? ++**空白**++ ``` javascript= int n=128; while(n < 100) { n=2*n; cout << n << " "; } ``` 23. 下列程式執行後,會印出? ++**4 8 16 32 64 128**++ ``` javascript= int n=2; do { n=2*n; cout << n << " "; }while(n < 100); ``` 24. 下列程式執行後,會印出? ++**256**++ ``` javascript= int n=128; do { n=2*n; cout << n << " "; }while(n < 100); ``` 25. 下列程式執行完,sum為? ++**15**++ ``` javascript= int sum=0,n=915; while(n>0) { sum+=n%10; n/=10; } ``` 26. 宣告陣列int a[5]={1},則a[4]的初值為? ++**0**++ 27. 下列程式執行完,sum為? ++**28**++ ``` javascript= int a[5]={6, 5, 9, 8, 3},sum=0; for(int i=0;i<4;i++) sum+=a[i]; ``` 28. 下列程式執行完,a的元素為? ++**{6, 1, 3, 5, 2}**++ ``` javascript= int a[5]={2, 6, 1, 3, 5},t; for(int i=0;i<4;i++) { t=a[i]; a[i]=a[i+1]; a[i+1]=t; } ``` 29. 下列程式執行完,a的元素為? ++**{2, 1, 3, 5, 6}**++ ``` javascript= int a[5]={2, 6, 1, 3, 5},t; for(int i=0;i<4;i++) { if(a[i]>a[i+1]) { t=a[i]; a[i]=a[i+1]; a[i+1]=t; } } ``` 30. 下列程式執行完,idx為? ++**7**++ ``` javascript= int a[10]={1,3,9,2,5,8,4,9,6,7},max=-1,idx=0; for(int i=0;i<10;i++) { if(a[i]>=max) { max=a[i]; idx=i; } } ``` 31. 下列遞迴函式程式執行完,cout輸出為? ++**30**++ ``` javascript= int f(int n) { if(n==1) return 5; else return n*f(n-1); } int main() { cout << f(3); return 0; } ``` 32. 下列遞迴函式程式執行完會,cout輸出為? ++**13**++ ``` javascript= int f(int n) { if (n==0 || n==1) return 1; else return f(n-1)*2 + f(n-2)*3; } int main() { cout << f(3); return 0; } ``` 33. 下列遞迴函式程式執行完會,cout輸出為? ++**5**++ ``` javascript= int f(int n, int m) { if(n>m) return 0; else if(n==m) return 1; else return f(n+1,m)+f(n,m-n); } int main() { cout << f(1,4); return 0; } ``` 34. 以下為C語言所撰寫的遞迴函式 gcd (a, b) 擬計算 a 與 b 之最大公因數。 空白應如填入? ++**gcd(b,a%b)**++ ``` javascript= int gcd(int a,int b) { if(b==0) return a; else return ________; } ``` <br> # 二、資料結構、演算法筆試 1. 將 A, B, C 依序push進堆疊(stack),再pop二個元素,再push D, E, F,再pop一個元素,最後push G。此時堆疊中剩餘的元素由上至下依序為? ++**GEDA**++ 2. 遞迴程式的呼叫與返回會用到哪種資料結構?++**堆疊**++ 3. 有一佇列(Queue),相關函式的功能為 Enqueue X: 把X加到佇列尾端 Dequeue:把佇列最前方資料取出 假設佇列剛開始不存放任何資料,執行 Enqueue 1 Enqueue 2 Enqueue 3 Dequeue Enqueue 4 後,則此佇列的內容由前到後為? ++**2 3 4**++ 4. 一棵高度為5的二元樹,最多有幾個節點? ++**31**++ 5. 讀入 14, 15, 4, 9, 7, 18, 3, 5, 16, 20, 17,然後依照讀入的順序建造一個二元搜尋樹(binary search tree)。假設樹根(root)在第一階層(first level),請問該樹有多少階層? ++**5**++ 6. 下圖的二元樹中序走訪(inorder traversal)的順序為? ++**BDCAEF**++ 後序走訪(postorder traversal)的順序為? ++**DCBFEA**++ ![](https://i.imgur.com/1X6P0dx.png =200x) 7. 若一篇文章每個字母出現的次數為,a:3,b:2,c:1,d:4,e:5,以霍夫曼編碼。 a的編碼為? ++**01**++ e的編碼為? ++**11**++ 8. 小城鎮中的電車路線圖如右![](https://i.imgur.com/TjzH6AP.png =150x) 其中 A, B, C, D表示四個站,單一箭頭的連接線表示電車從端點為起站開向有箭頭端的終站,雙箭頭的連接線表示兩端點的站之間雙向都有電車互通。若以一個二維陣列map[i][j]來記錄這個電車路線圖,map[i][j]=1表示從站 i 到站 j 有一條電車路線,否則 map[i][j]=0,則電車路線圖的陣列值為? $$ \left[ \begin{array}{cccc} 0&1&1&0\\ 1&0&0&1\\ 1&1&0&1\\ 0&0&0&0 \end{array} \right] $$ 9. 以下列相鄰陣列表示圖形,圖形共有幾個邊? ++**7**++ $$ \left[ \begin{array}{cccc} 0&1&0&0&1\\ 1&0&1&1&1\\ 0&1&0&1&0\\ 0&1&1&0&1\\ 1&1&0&1&0 \end{array} \right] $$ 10. 下圖的DFS走訪順序為? ++**0 1 5 6 4 2 3**++ BFS走訪順序為? ++**0 1 2 3 5 6 4**++ ![](https://i.imgur.com/V20DXqK.png =250x) 11. 在圖形上做廣度優先搜尋(BFS)時,何者為最適合的資料結構?++**佇列**++ 12. 下圖的最小成本擴張樹(Minimum cost spanning tree)的成本為? ++**17**++ ![](https://i.imgur.com/IXJHGTi.png =180x) 13. 氣泡排序的時間複雜度(time complexity)為?++**O(n^2^)**++ 14. 下列程式的時間複雜度(time complexity)為?++**O(log~2~n)**++ ``` javascript= int n,i=1,sum=0; cin >> n; while(i<=n) { i*=2; sum+=i; } ``` 15. 下列程式的時間複雜度(time complexity)為?++**O(n^2^)**++ ``` javascript= int n,sum=0; cin >> n; for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { sum+=i*j; } } ```