一、單項選擇題（共15題，每題1.5分，共計22.5分；每題有且僅有一個正確選項）

1.從( )年開始，NOIP競賽將不再支持Pascal語言。

A. 2020 B. 2021 C. 2022 D. 2023

2.在8位二進制補碼中，10101011表示的數(shù)是十進制下的( )。

A. 43 B. -85 C. -43 D.-84

3.分辨率為1600x900、16位色的位圖，存儲圖像信息所需的空間為( )。

A. 2812.5KB B. 4218.75KB

C. 4320KB D. 2880KB

4. 2017年10月1日是星期日，1949年10月1日是( )。

A.星期三 B.星期日

C.星期六 D.星期二

5.設G是有n個結點、m條邊(n ≤m)的連通圖，必須刪去G的( )條邊，才能使得G變成一棵樹。

A.m–n+1 B. m-n

C. m+n+1 D.n–m+1

6.若某算法的計算時間表示為遞推關系式：

T(N)=2T(N/2)+NlogN

T(1)=1

則該算法的時間復雜度為( )。

A.O(N) B.O(NlogN)

C.O(N log2N) D.O(N2)

7.表達式a * (b + c) * d的后綴形式是()。

A. abcd*+*B. abc+*d*

C. a*bc+*d D. b+c*a*d

8.由四個不同的點構成的簡單無向連通圖的個數(shù)是( )。

A. 32 B. 35 C. 38 D. 41

9.將7個名額分給4個不同的班級，允許有的班級沒有名額，有( )種不同的分配方案。

A. 60 B. 84 C. 96 D.120

10.若f[0]=0, f[1]=1, f[n+1]=(f[n]+f[n-1])/2，則隨著i的增大，f[i]將接近與( )。

A. 1/2

B. 2/3

D. 1

11.設A和B是兩個長為n的有序數(shù)組，現(xiàn)在需要將A和B合并成一個排好序的數(shù)組，請問任何以元素比較作為基本運算的歸并算法最壞情況下至少要做( )次比較。

A. n2 B. nlogn C. 2n D.2n-1

12.在n(n>=3)枚硬幣中有一枚質量不合格的硬幣（質量過輕或質量過重），如果只有一架天平可以用來稱重且稱重的硬幣數(shù)沒有限制，下面是找出這枚不合格的硬幣的算法。請把a-c三行代碼補全到算法中。

2.將A中硬幣分成X,Y,Z三個集合，使得|X|=|Y|=k, |Z|=n-2k

3. if W(X)≠W(Y)//W(X), W(Y)分別為X或Y的重量

4. then_______

5. else_______

6. __________

7. if n>2 then goto 1

8. if n=2 then任取A中1枚硬幣與拿走硬幣比較，若不等，則它不合格；若相等，則A中剩下的硬幣不合格

9. if n=1 then A中硬幣不合格

正確的填空順序是( )。

A. b,c,a B. c,b,a C. c,a,b D.a,b,c

13.在正實數(shù)構成的數(shù)字三角形排列形式如圖所示，第一行的數(shù)為a11；第二行的數(shù)從左到右依次為a21,a22;…第n行的數(shù)為an1,an2,…，ann。從a11開始，每一行的數(shù)aij只有兩條邊可以分別通向下一行的兩個數(shù)a(i+1)j和a(i+1)(j+1)。用動態(tài)規(guī)劃算法找出一條從a11向下通到an1,an2,…,ann中某個數(shù)的路徑，使得該路徑上的數(shù)之和達到最大。

令C[i,j]是從a11到aij的路徑上的數(shù)的最大和，并且C[i,0]=C[0,j]=0，則C[i,j]=( )。

A. max{C[i-1,j-1],C[i-1,j]}+aij

B. C[i-1,j-1]+c[i-1,j]

C. max{C[i-1,j-1],C[i-1,j]}+1

D. max{C[i,j-1],C[i-1,j]}+aij

14.小明要去南美洲旅游，一共乘坐三趟航班才能到達目的地，其中第1個航班準點的概率是0.9，第2個航班準點的概率為0.8，第3個航班準點的概率為0.9。如果存在第i個（i=1,2）航班晚點，第i+1個航班準點，則小明將趕不上第i+1個航班，旅行失??；除了這種情況，其他情況下旅行都能成功。請問小明此次旅行成功的概率是( )。

A. 0.5 B. 0.648 C. 0.72 D.0.74

15.歡樂噴球：兒童游樂場有個游戲叫“歡樂噴球”，正方形場地中心能不斷噴出彩色乒乓球，以場地中心為圓心還有一個圓軌道，軌道上有一列小火車在勻速運動，火車有六節(jié)車廂。假設乒乓球等概率落到正方形場地的每個地點，包括火車車廂。小朋友玩這個游戲時，只能坐在同一個火車車廂里，可以在自己的車廂里撿落在該車廂內的所有乒乓球，每個人每次游戲有三分鐘時間，則一個小朋友獨自玩一次游戲期望可以得到( )個乒乓球。假設乒乓球噴出的速度為2個/秒，每節(jié)車廂的面積是整個場地面積的1/20。

 

 

 

 

 

A. 60 B. 108 C. 18 D. 20

二、不定項選擇題（共5題，每題1.5分，共計7.5分；每題有一個或多個正確選項，多選或少選均不得分）

1.以下排序算法在最壞情況下時間復雜度最優(yōu)的有( )。

A.冒泡排序 B.快速排序

C.歸并排序 D.堆排序

2.對于入棧順序為a, b, c, d, e, f, g的序列，下列()不可能是合法的出棧序列。

A. a,b,c,d,e,f,g B. a,d,c,b,e,g,f

C. a,d,b,c,g,f,e D.g,f,e,d,c,b,a

3.下列算法中，( )是穩(wěn)定的排序算法。

A.快速排序 B.堆排序

C.希爾排序 D.插入排序

4.以下是面向對象的高級語言的是( )。

A.匯編語言 B. C++ C. FortanD. Java

5.以下和計算機領域密切相關的獎項是( )。

A.奧斯卡獎B.圖靈獎 C.諾貝爾獎D.王選獎

三、問題求解（共2題，每題5分，共計10分）

1.如圖所示，共有13個格子。對任何一個格子進行一次操作，會使得它自己以及與它上下左右相鄰的格子中的數(shù)字改變(由1變0，或由0變1)?，F(xiàn)在要使得所有的格子中的數(shù)字都變?yōu)?，至少需要3次操作。

2.如圖所示，A到B是連通的。假設刪除一條細的邊的代價是1，刪除一條粗的邊的代價是2，要讓A、B不連通，最小代價是4(2分)，最小代價的不同方案數(shù)是9(3分)。（只要有一條刪除的邊不同，就是不同的方案）

四、閱讀程序寫結果（共4題，每題8分，共計32分）

1.

#include

using namespacestd;

int g(int m, intn, int x){

int ans = 0;

int i;

if( n == 1)

return 1;

for (i=x; i <=m/n; i++)

ans += g(m –i, n-1, i);

return ans;

}

int main() {

int t, m, n;

cin >> m >> n;

cout << g(m, n, 0) << endl;

return 0;

}

輸入: 8 4

輸出:15

2.

#include

using namespacestd;

int main() {

int n, i, j, x, y, nx, ny;

int a[40][40];

for (i = 0; i< 40; i++)

for (j = 0;j< 40; j++)

a[i][j]= 0;

cin >> n;

y = 0; x = n-1;

n = 2*n-1;

for (i = 1; i <= n*n; i++){

a[y][x] =i;

ny = (y-1+n)%n;

nx = (x+1)%n;

if ((y == 0 && x == n-1) || a[ny][nx] !=0)

y= y+1;

else {y = ny; x = nx;}

}

for (j = 0; j < n; j++)

cout << a[0][j]<< “”;

cout << endl;

return 0;

}

輸入: 3

輸出:17 24 1 8 15

3.

#include

using namespacestd;

int n, s,a[100005], t[100005], i;

void mergesort(intl, int r){

if (l== r)

return;

int mid = (l+ r) / 2;

int p =l;

int i =l;

int j = mid + 1；

mergesort (l, mid);

mergesort (mid + 1, r);

while (i <= mid && j<= r){

if (a[j] < a[i]){

s += mid – i+1;

t[p] = a[j];

p++;

j++;

}

else {

t[p] = a[i];

p++;

i++;

}

}

while (i <= mid){

t[p] = a[i];

p++;

i++;

}

while (j <= r){

t[p] = a[j];

p++;

j++;

}

for (i =l; i <= r; i++ )

a[i] = t[i];

}

int main() {

cin >> n;

for (i = 1; i <= n; i++)

cin>> a[i];

mergesort (1, n);

cout << s << endl;

return 0;

}

輸入:

6

2 6 3 4 5 1

輸出:8

4.

#include

using namespacestd;

int main() {

int n, m;

cin >> n >> m;

int x = 1;

int y = 1;

int dx = 1;

int dy = 1;

int cnt = 0;

while (cnt != 2) {

cnt = 0;

x = x + dx;

y = y + dy;

if (x == 1 || x == n) {

++cnt;

dx = -dx;

}

if (y == 1 || y == m) {

++cnt;

dy = -dy;

}

}

cout << x << " " << y<< endl;

return 0;

}

輸入1: 4 3

輸出1:1 3 (2分)

輸入2: 2017 1014

輸出2:2017 1(3分)

輸入3: 987 321

輸出3:1 321(3分)

 

聲明：本文來源于網(wǎng)絡，由自主選拔在線團隊（微信公眾號：zizzsw）排版編輯，如有侵權，請聯(lián)系刪除。