單選題（每題 2 分，共 30 分）

1、 已知小寫字母 b 的ASCII碼為98，下列C++代碼的輸出結果是（ ）。

#include <iostream>
using namespace std;
int main() {char a = 'b' ^ 4;cout << a;return 0;
}

A. b
B. bbbb
C. f
D. 102

正確答案：C

2、 已知 a 為 int 類型變量， p 為 int * 類型變量，下列賦值語句不符合語法的是（ ）。

A. *(p + a) = *p;
B. *(p - a) = a;
C. p + a = p;
D. p = p + a;

正確答案：C

3、下列關于C++類的說法，錯誤的是( )。

A. 如需要使用基類的指針釋放派生類對象，基類的析構函數應聲明為虛析構函數。
B. 構造派生類對象時，只調用派生類的構造函數，不會調用基類的構造函數。
C. 基類和派生類分別實現了同一個虛函數，派生類對象仍能夠調用基類的該方法。
D. 如果函數形參為基類指針，調用時可以傳入派生類指針作為實參。

正確答案：B

4、下列C++代碼的輸出是（ ）。

#include <iostream>
using namespace std;
int main() {int arr[5] = {2, 4, 6, 8, 10};int * p = arr + 2;cout << p[3] << endl;return 0;
}

A. 6
B. 8
C. 編譯出錯，無法運行。
D. 不確定，可能發生運行時異常。

正確答案：D

5、假定只有一個根節點的樹的深度為1，則一棵有N個節點的完全二叉樹，則樹的深度為( )。

A. $?lo{g}_2(N)?+1$
B. $?lo{g}_2(N)?$
C. $?lo{g}_2(N)?$
D. 不能確定

正確答案：A

6、對于如下圖的二叉樹，說法正確的是（ ）。

A. 先序遍歷是 ABDEC 。
B. 中序遍歷是 BDACE 。
C. 后序遍歷是 DBCEA 。
D. 廣度優先遍歷是 ABCDE 。

正確答案：D

7、圖的存儲和遍歷算法，下面說法錯誤的是（ ）。

A. 圖的深度優先遍歷須要借助隊列來完成。
B. 圖的深度優先遍歷和廣度優先遍歷對有向圖和無向圖都適用。
C. 使用鄰接矩陣存儲一個包含 個頂點的有向圖，統計其邊數的時間復雜度為 。
D. 同一個圖分別使用出邊鄰接表和入邊鄰接表存儲，其邊結點個數相同。

正確答案：A

8、一個連通的簡單有向圖，共有28條邊，則該圖至少有( )個頂點。

A. 5
B. 6
C. 7
D. 8

正確答案：B

9、以下哪個方案不能合理解決或緩解哈希表沖突（ ）。

A. 在每個哈希表項處，使用不同的哈希函數再建立一個哈希表，管理該表項的沖突元素。
B. 在每個哈希表項處，建立二叉排序樹，管理該表項的沖突元素。
C. 使用不同的哈希函數建立額外的哈希表，用來管理所有發生沖突的元素。
D. 覆蓋發生沖突的舊元素。

正確答案：D

10、 以下關于動態規劃的說法中，錯誤的是（ ）。

A. 動態規劃方法通常能夠列出遞推公式。
B. 動態規劃方法的時間復雜度通常為狀態的個數。
C. 動態規劃方法有遞推和遞歸兩種實現形式。
D. 對很多問題，遞推實現和遞歸實現動態規劃方法的時間復雜度相當。

正確答案：B

11、下面程序的輸出為（ ）。

#include <iostream>
using namespace std;
int rec_fib[100];
int fib(int n) {if (n <= 1)return n;if (rec_fib[n] == 0)rec_fib[n] = fib(n - 1) + fib(n - 2);return rec_fib[n];
}
int main() {cout << fib(6) << endl;return 0;
}

A. 8
B. 13
C. 64
D. 結果是隨機的。

正確答案：A

12、下面程序的時間復雜度為（ ）。

int rec_fib[MAX_N];
int fib(int n) {if (n <= 1)return n;if (rec_fib[n] == 0)rec_fib[n] = fib(n - 1) + fib(n - 2);return rec_fib[n];
}

A.$O(2^n)$
B.$O({?}^n),?=\frac{\sqrt{5}?1}{2}$
C.$O(n^2)$
D.$O(n)$

正確答案：D

13、下面 search 函數的平均時間復雜度為( )。

int search(int n, int * p, int target) {int low = 0, high = n;while (low < high) {int middle = (low + high) / 2;if (target == p[middle]) {return middle;} else if (target > p[middle]) {low = middle + 1;} else {high = middle;}}return -1;
}

A.$O(nlog(n))$
B.$O(n)$
C.$O(log(n))$
D.$O(1)$

正確答案：C

14、下面程序的時間復雜度為（ ）。

int primes[MAXP], num = 0;
bool isPrime[MAXN] = {false};
void sieve() {for (int n = 2; n <= MAXN; n++) {if (!isPrime[n])primes[num++] = n;for (int i = 0; i < num && n * primes[i] <= MAXN; i++) {isPrime[n * primes[i]] = true;if (n % primes[i] == 0)break;}}
}

A.$O(n)$
B.$O(nlogn)$
C.$O(nloglogn)$
D.$O(n^2)$

正確答案：A

15、下列選項中，哪個不可能是下圖的廣度優先遍歷序列（ ）。

A. 1, 2, 4, 5, 3, 7, 6, 8, 9
B. 1, 2, 5, 4, 3, 7, 8, 6, 9
C. 1, 4, 5, 2, 7, 3, 8, 6, 9
D. 1, 5, 4, 2, 7, 3, 8, 6, 9

正確答案：B

判斷題（每題 2 分，共 20 分）

1、C++語言中，表達式 9 & 12 的結果類型為 int 、值為 8 。

正確答案：正確

2、C++語言中，指針變量指向的內存地址不一定都能夠合法訪問。

正確答案：正確

3、對n個元素的數組進行快速排序，最差情況的時間復雜度為O(nlogn)。

正確答案：錯誤

4、題 一般情況下， long long 類型占用的字節數比 float 類型多。

正確答案：正確

5、 使用 math.h 或 cmath 頭文件中的函數，表達式 pow(10, 3) 的結果的值為 1000 、類型為 int 。

正確答案：錯誤

6、二叉排序樹的中序遍歷序列一定是有序的。

正確答案：正確

7、無論哈希表采用何種方式解決沖突，只要管理的元素足夠多，都無法避免沖突。

正確答案：正確

8、在C++語言中，類的構造函數和析構函數均可以聲明為虛函數。

正確答案：錯誤

9、 動態規劃方法將原問題分解為一個或多個相似的子問題，因此必須使用遞歸實現。

正確答案：錯誤

10、如果將城市視作頂點，公路視作邊，將城際公路網絡抽象為簡單圖，可以滿足城市間的車道級導航需求。

正確答案：錯誤

編程題 (每題 25 分，共 50 分)

線圖

【問題描述】
給定由n個結點與m條邊構成的簡單無向圖G,結點依次以1,2,…,n編號。簡單無向圖意味著G中不包含重邊與自環。G的線圖L(G)通過以下方式構建：
·

• 初始時線圖L(G)為空。
• 對于無向圖G中的一條邊，在線圖L(G)中加入與之對應的一個結點。
• 對于無向圖G中兩條不同的邊$(u_1,v_1),(u_2,v_2)$,若存在G中的結點同時連接這兩條邊(即$u_1,v_1$之一與$u_2,v_2$之一相同),則在線圖L(G)中加入一條無向邊，連接$(u_1,v_1),(u_2,v_2)$在線圖中對應的結點。
  ·
  請你求出線圖L(G)中所包含的無向邊的數量。

【輸入格式】
第一行，兩個正整數n,m,分別表示無向圖G中的結點數與邊數。
接下來m行，每行兩個正整數$u_i,v_i$,表示G中連接$u_i,v_i$的一條無向邊。

【輸出格式】
輸出共一行，一個整數，表示線圖L(G)中所包含的無向邊的數量。

【樣例輸入 1】
5 4
1 2
2 3
3 1
4 5
【樣例輸出 1】
3
【樣例輸入 2】
5 10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5
【樣例輸出 2】
30
【樣例解釋1】

【數據范圍】
對于60%的測試點，保證$1\le n\le 500,1\le m\le 500$。
對于所有測試點，保證$1\le n\le 10^5,1\le m\le 10^5$。

調味平衡

【問題描述】
小A準備了n種食材用來制作料理，這些食材依次以1,2,…,n編號，第i種食材的酸度為$a_i$,甜度為$b_i$。對于每種食材，小A可以選擇將其放入料理，或者不放入料理。料理的酸度A為放入食材的酸度之和，甜度B為放入食材的甜度之和。如果料理的酸度與甜度相等，那么料理的調味是平衡的。
過于清淡的料理并不好吃，因此小A想在滿足料理調味平衡的前提下，合理選擇食材，最大化料理的酸度與甜度之和。你能幫他求出在調味平衡的前提下，料理酸度與甜度之和的最大值嗎?

【輸入格式】
第一行，一個正整數n,表示食材種類數量。

接下來n行，每行兩個正整數$a_i,b_i$,表示食材的酸度與甜度。

【輸出格式】
輸出共一行，一個整數，表示在調味平衡的前提下，料理酸度與甜度之和的最大值。
【樣例輸入 1】
3
1 2
2 4
3 2
【樣例輸出 1】
8
【樣例輸入 2】
5
1 1
2 3
6 1
8 2
5 7
【樣例輸出 2】
2
【數據范圍】
對于40%的測試點，保證$1\le n\le 10,1\le a_i,b_i\le 10$。
對于另外20%的測試點，保證$1\le n\le 50,1\le a_i,b_i\le 10$。
對于所有測試點，保證$1\le n\le 100,1\le a_i,b_i\le 500$。