# 109學年度 復旦程式設計班 入班考考題 A卷
>尊重自己愛護復旦。
>復旦過去的光榮將來的燦爛。
>全靠師生共同努力共同發展。
>同學今天在考試的時候不要忘記自己，不要忘記復旦。
:::info
此份試題著作權為復旦程式設計班所有。
:::
:::warning
**答案網址** https://hackmd.io/@ThunderCold/HkKn3SX8D
**試題勘誤 (2020年9月8日更新)**
入班試題A卷第17題，此題經幹部群討論決議送分。
程式碼第五行`endl`的部分應使用`std::endl`才可使程式碼正常編譯並執行。原先公布之解答為A，因為我們原先考這題的想法是要問學員是否對`std::`的用法有所了解，卻忽略了程式碼的正確與否，因此經幹部群討論後決定送分，造成不便敬請見諒。
有任何疑問，歡迎與我們聯絡！
9th所有幹部群敬上
:::
## 測驗說明
* 這是109學年度復旦程式設計班入班考考題(A卷)，題目為電子檔格式，共有**20**題基礎題、**5**題進階題。
* 測驗時間為2020年9月7日12:00至12:45。作答開始與結束請聽從監試人員的指示。
* **基礎題**每題5分，共100分。均為四選一的選擇題，答錯不倒扣。
* **進階題**為篩選進階班成員用，原則上不計入初階班篩選標準，若進階題答題表現優異，則有機會進入進階班。均為填充題，答錯不倒扣。(錄取進階班學員分數必須達到初階班門檻之前提)
## 注意事項
* 請攜帶有清晰照片之身分證明文件(如:學生證、身分證、健保卡)以供查驗。
* 請自備深色墨水之原子筆及修正液(帶)，現場並無提供。
* 根據學校規定，電腦教室禁止飲食。
* 考試禁止攜帶任何形式之參考資料。
* 考試期間請將手機及電子設備關機。
* 遲到10分鐘者禁止入場(特殊情況並檢附證明者例外)，並不得提前交卷。
* 試題及所附之程式碼與虛擬碼如有錯誤，以考試時試題勘誤為準。
* 請確認開啟之題目卷別與通知郵件中分配卷別相符，並在答案卷上圈選正確之題目卷別。如答案卷圈選之題目卷別與姓名不相符，該卷以0分計算。
* 可利用答案卷背面進行計算，切勿在作答區計算。
* 相關考試規定以《桃園市復旦高級中學學生考試規則》與《桃園市復旦高級中學考試規則補充規定》為準，如有違規事項，將直接取消考試與錄取資格。
* 考試期間，電腦僅用以檢視題目，禁止有其他用途 (如:開啟編譯器或編輯器)，違者將直接取消考試與錄取資格。
## 作答方式
* **基礎題**請依照題意從四個選項中選出**一個**正確或最佳的答案，並用深色墨水原子筆將答案書寫在答案卷上相應的作答區。
* **進階題**請依照題意用深色墨水原子筆將答案書寫在答案卷上相應的作答區。
* 請務必將答案書寫工整，若作答過於潦草、書寫至相應的作答區外、或其他致使閱卷者未能理解，後果由考生自行負責。
## 第一大題 基礎題 (單選題)
1. 對於以下虛擬碼，試問輸出為何?
```cpp
int main(){
int a = 32, b = 24, tmp;
while (b != 0)
{
tmp = a % b;
a = b;
b = tmp;
}
cout << a << endl;
}
```
(A) 8
(B) 16
(C\) 24
(D) 32
2. 對於以下虛擬碼，試問輸出為何?
```cpp
int main(){
int sum = 0;
for (int i = 0; i < 100; i++)
sum += (i % 3);
cout << sum << endl;
}
```
(A) 98
(B) 99
(C\) 100
(D) 101
3. 對於以下程式碼，試問發生什麼錯誤?
```cpp
#include<iostream>
with namespace std;
int main(){
cout << "hello, world" << endl;
}
```
(A) 語意錯誤
(B) 邏輯錯誤
(C\) 語法錯誤
(D) 沒有錯誤
4. 對於以下概念，下列何者正確?
(A) `int`型態的數字限制範圍大於`double`
(B) `int`是32位元有號整數
(C\) `float`的精度大於`double`
(D) `bool`是8位元有號整數
5. 對於以下程式碼，下列敘述何者正確?
```cpp
#include<iostream>
using namespace std;
int main(){
for (int i = 1; i < 10; i++)
{
for (int j = 1; j < 10; j++)
{
cout << i << "*" << j << "=" << i*j << "\n";
}
cout << endl;
}
return 0;
}
```
(A) 該程式可輸出10\*10的乘法表
(B) 程式碼中的`i++`等同於`i+=2`
(C\) 第八行末的輸出`"\n"`可將輸出向右切齊
(D) 此程式碼會有 90 行輸出
6. 旦旦監獄某次段考全校平均太低，為了調整分數老師們協議將每個人的分數加7分後乘以三再減五最後除以2 (不考慮分數大於 100 的狀況)，為了讓分數換更快速，某位老師寫了以下程式，請問程式碼中空白處應填入何者才可出目標分數?
```cpp
#include<iostream>
using namespace std;
int main(){
int iscore, fscore;
cin >> iscore;
/*空白處*/
cout << fscore << endl;
}
```
(A) `fscore = (iscore + 7) * (3 - 5 / 2);`
(B) `fscore = (iscore + 7) * 3 - 5 / 2;`
(C\) `fscore = [(iscore + 7) * 3 - 5] / 2;`
(D) `fscore = ((iscore + 7) * 3 - 5) / 2;`
7. 對於以下虛擬碼，試問輸入`40`時，輸出為何?
```cpp
int main(){
int n;
cin >> n;
if (n > 40)
{
cout << "復旦復旦復旦旦" << endl;
}
else if (n < 40 && n >= 30)
{
cout << "巴拉巴拉小魔仙" << endl;
}
else if (n <= 30 && n >= 20)
{
cout << "復旦程式設計班" << endl;
}
else
{
cout << "你是我的小蘋果" << endl;
}
}
```
(A) 復旦復旦復旦旦
(B) 巴拉巴拉小魔仙
(C\) 復旦程式設計班
(D) 你是我的小蘋果
8. 承上題，試問輸入`30`時，輸出為何?
(A) 復旦復旦復旦旦
(B) 巴拉巴拉小魔仙
(C\) 復旦程式設計班
(D) 你是我的小蘋果
9. 對於以下虛擬碼，試問輸出為何?
```cpp
int a = 10, b = 5;
do
{
if (a >= 10)
{
a--;
}
a += 2;
b--;
}while (b >= 0);
cout << a << endl;
```
(A) 10
(B) 14
(C\) 15
(D) 16
10. 對於以下程式碼，試問輸出為何?
```cpp
#include<iostream>
using namespace std;
int main(){
bool t = true, f = false;
cout << (!t || f && t || t && t) << endl;
}
```
(A) 1
(B) 0
(C\) 無法輸出
(D) 以上皆非
11. 若執行時遇到以下錯誤訊息，試問可能犯了什麼錯誤?
`[Error] expected ';' before '}' token`
(A) 沒加`}`
(B) 沒加`;`
(C\) 沒有宣告
(D) 沒有寫任何程式碼
12. 試問下列何者敘述與其他選項不等價?
(A) `i++`
(B) `i+=1`
(C\) `i+1=i`
(D) `i=i+1`
13. 對於以下虛擬碼，試問輸出為何?
```cpp
int ans = 0;
for (int i = 0; i < 87; i++)
{
((ans + i) % 2 ? ans++ : ans = 0);
}
cout << ans;
```
(A) 43
(B) 0
(C\) 86
(D) 87
14. 對於以下虛擬碼，試問輸出為何?
```cpp
int ans = 0;
for (int i = 0; i < 10; i++)
{
for (int j = 10 - i; j > 0; j--)
{
ans += i*j;
}
}
cout << ans << endl;
```
(A) 2025
(B) 495
(C\) 720
(D) 以上皆非
15. 對於以下虛擬碼，試問輸出為何?
```cpp
int a = 1, b = 1;
for (int i = 0; i < 10; i++)
{
int tmp = a + b;
a = b;
b = tmp;
}
cout << a << " " << b << endl;
```
(A) 1 1
(B) 55 89
(C\) 144 232
(D) 89 144
16. 試問下列敘述何者正確?
(A) iostream 是輸入/輸出流的意思
(B) iostream 是特別為iOS作業系統而做的資料庫
(C\) iostream 裡面沒有string類別
(D) iostream 不屬於C++標準程式庫的一部分
17. 試問以下程式碼是否可正常編譯並執行?
```cpp
#include<iostream>
int main(){
int a, b;
std::cin >> a >> b ;
std::cout << a << " " << b << endl;
}
```
(A) 當然可以阿 還用想嗎
(B) 怎麼可能 沒有`using namespace std;`阿
(C\) 不可能 第四行太多空白了
(D) 哈哈一定不行 因為`" "`內只能有一個字元
18. 試問下列敘述何者正確?
(A) `'\n'` 是字串結束字元
(B) `'\t'` 是跳格字元
(C\) `'\a'` 是歸位字元
(D) `'\b'` 是換行字元
19. 對於以下虛擬碼，試問輸出為何?
```cpp
cout << !5 << endl;
```
(A) 0
(B) 1
(C\) 5
(D) !5
20. 對於以下程式碼，試問輸出為何?
```cpp
#include<iostream>
using namespace std;
int main(){
int a = 9, b = 5, sum = 0;
double c = 7.9;
sum += a / 6 + b + c;
cout << sum << endl;
}
```
(A) 13.9
(B) 14
(C\) 13
(D) 14.4
## 第二大題 進階題 (填充題)
### 第一子題 (1~3題)
* 合併排序 (Merge sort)，是建立在合併操作上的一種有效的排序演算法，效率為O(nlog n) (大 O 符號)。
* 1945年由約翰·馮·紐曼首次提出。該演算法是採用分治法 (Divide and Conquer)的一個非常典型的應用，且各層分治遞迴可以同時進行。
* 採用分治法:
1. 分割:遞迴地把當前序列平均分割成兩半。
2. 整合:在保持元素順序的同時將上一步得到的子序列整合到一起(合併操作)。
* 合併操作:
1. 申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合併後的序列
2. 設定兩個指標，最初位置分別為兩個已經排序序列的起始位置
3. 比較兩個指標所指向的元素，選擇相對小的元素放入到合併空間，並移動指標到下一位置
4. 重複步驟3直到某一指標到達序列尾
5. 將另一序列剩下的所有元素直接複製到合併序列尾
```cpp
//Output: 0 1 2 3 4 5 6 7 8 9
#include <iostream>
using namespace std;
int tmp[10];
void merge_sort(int arr[], unsigned start, unsigned size)
{
if (size <= 1) return;
int m = size / 2;
merge_sort(arr, start, m);
merge_sort(arr, /*...(1-1)...*/, /*...(1-2)...*/);
for (unsigned i = 0; i != size; i++)
tmp[i] = arr[start + i];
int *it = arr + start;
int *l = tmp, *r = tmp + m;
while (l != tmp + m && r != tmp + size)
{
if (/*...(2)...*/)
*it++ = *l++;
else
*it++ = *r++;
}
while (l != tmp + m)
/*...(3-1)...*/;
while (r != tmp + size)
/*...(3-2)...*/;
}
int main() {
int v[] = {1, 5, 4, 2, 0, 3, 9, 7, 6, 8};
merge_sort(v, 0, 10);
for (int i = 0; i != 10; i++)
cout << v[i] << ' ';
return 0;
}
```
試問，`...(1-1)...`、`...(1-2)...`、`...(2)...`、`...(3-1)...` 和 `...(3-2)...` 應填入什麼? (不同小題分開計分)
### 第二子題 (4~5題)
二分搜尋演算法，是一種在有序陣列中搜尋某一特定元素的搜尋方法。
搜尋過程從陣列的中間元素開始，如果中間元素正好是要搜尋的元素，則搜尋過
程結束；
如果某一特定元素大於或者小於中間元素，則在陣列大於或小於中間元素的那一
半中搜尋，
而且跟開始一樣從中間元素開始比較。這種搜尋演算法每一次比較都使搜尋範圍
縮小一半。
```cpp
#include<iostream>
using namespace std;
int main(){
int arr[10] = {1, 3, 5, 6, 8, 10, 11, 14, 15, 20};
int l = 0, r = sizeof(arr) / sizeof(int) - 1;
int key = 1; //欲尋找 key 是否在 arr 裡面
int mid;
bool find = false;
while(/*...(4)...*/)
{
mid = /*...(5)...*/;
if (arr[mid] == key)
{
find = true;
break;
}
else if (arr[mid] > key)
{
r = mid - 1;
}
else
{
l = mid + 1;
}
}
if (find)
cout << "find" << key << "in position " << mid + 1 << endl;
else
cout << "not found" << endl;
return 0;
}
```
試問，`...(4)...` 和 `...(5)...` 應填入什麼? (分開計分)
:::success
試題結束。待考試結束，監試人員清點考卷數量後方可離場。
祝各位電神考試順利 :poop:
:::
###### tags: `FDCS`
Sign in with Wallet
Connect another wallet