全國青少年信息學奧林匹克聯賽初賽試題（2009年NOIP普及組C++）

NOIP試題分析——少兒編程樂園

第十五屆全國青少年信息學奧林匹克聯賽初賽試題

（ 普及組 C++語言 二小時完成 ）

●● 全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效 ●●

一． 單項選擇題 （共20題，每題1.5分，共計30分。每題有且僅有一個正確答案。）

1、 關於圖靈機下面的說法哪個是正確的：

A) 圖靈機是世界上最早的電子計算機。

B) 由於大量使用磁帶操作，圖靈機運行速度很慢。

C) 圖靈機是英國人圖靈發明的，在二戰中為破譯德軍的密碼發揮了重要作用。

D) 圖靈機只是一個理論上的計算模型。

2、關於計算機內存下面的說法哪個是正確的：

A) 隨機存儲器（RAM）的意思是當程序運行時，每次具體分配給程序的內存位置是隨機而不確定的。

B) 1MB內存通常是指1024*1024字節大小的內存。

C) 計算機內存嚴格說來包括主存（memory）、高速緩存（cache）和寄存器（register）三個部分。

D) 一般內存中的數據即使在斷電的情況下也能保留2個小時以上。

3、關於BIOS下面說法哪個是正確的：

A) BIOS是計算機基本輸入輸出系統軟件的簡稱。

B) BIOS裡包含了鍵盤、鼠標、聲卡、顯卡、打印機等常用輸入輸出設備的驅動程序。

C) BIOS一般由操作系統廠商來開發完成。

D) BIOS能提供各種文件拷貝、複製、刪除以及目錄維護等文件管理功能。

4、關於CPU下面哪個說法是正確的：

A) CPU全稱為中央處理器（或中央處理單元）。

B) CPU可以直接運行彙編語言。

C) 同樣主頻下，32位的CPU比16位的CPU運行速度快一倍。

D) CPU最早是由Intel公司發明的。

5、關於ASCII，下面哪個說法是正確的：

A) ASCII碼就是鍵盤上所有鍵的唯一編碼。

B) 一個ASCII碼使用一個字節的內存空間就能夠存放。

C) 最新擴展的ASCII編碼方案包含了漢字和其他歐洲語言的編碼。

D) ASCII碼是英國人主持制定並推廣使用的。

6、下列軟件中不是計算機操作系統的是：

A) Windows B) Linux C) OS/2 D) WPS

7、關於互聯網，下面的說法哪一個是正確的：

A) 新一代互聯網使用的IPv6標準是IPv5標準的升級與補充。

B) 互聯網的入網主機如果有了域名就不再需要IP地址。

C) 互聯網的基礎協議為TCP/IP協議。

D) 互聯網上所有可下載的軟件及數據資源都是可以合法免費使用的。

8、關於HTML下面哪種說法是正確的：

A） HTML實現了文本、圖形、聲音乃至視頻信息的統一編碼。

B） HTML全稱為超文本標記語言。

C） 網上廣泛使用的 Flash動畫都是由HTML編寫的。

D） HTML也是一種高級程序設計語言。

9、關於程序設計語言，下面哪個說法是正確的：

A) 加了註釋的程序一般會比同樣的沒有加註釋的程序運行速度慢。

B) 高級語言開發的程序不能使用在低層次的硬件系統如：自控機床或低端手機上。

C) 高級語言相對於低級語言更容易實現跨平臺的移植。

D) 以上說法都不對。

10、已知大寫字母A的ASCII編碼為65（10進制），則大寫字母J的10進制ASCII編碼為：

A) 71 B) 72 C) 73 D) 以上都不是

11、十進制小數125.125對應的8進制數是

A) 100.1 B) 175.175 C) 175.1 D) 100.175

12、有六個元素FEDCBA 從左至右依次順序進棧，在進棧過程中會有元素被彈出棧。問下列哪一個不可能是合法的出棧序列？

A) EDCFAB B) DECABF C) CDFEBA D) BCDAEF

13、 表達式a*(b+c)-d的後綴表達式是：

A) abcd*+- B) abc+*d- C) abc*+d- D) -+*abcd

14、一個包含n個分支結點（非葉結點）的非空二叉樹，它的葉結點數目最多為：

A) 2n + 1 B) 2n-1 C) n-1 D) n+1

15、快速排序最壞情況下的算法時間複雜度為：

A) O(log₂n) B) O(n) C) O(nlog₂n) D) O(n²)

16. 有一個由4000個整數構成的順序表，假定表中的元素已經按升序排列，採用二分查找定位一個元素。則最多需要幾次比較就能確定是否存在所查找的元素：

A) 11次 B) 12次 C) 13次 D) 14次

17、排序算法是穩定的意思是關鍵碼相同的記錄排序前後相對位置不發生改變，下列哪種排序算法是不穩定的：

A) 冒泡排序 B) 插入排序 C) 歸併排序 D) 快速排序

18、已知n個頂點的有向圖，若該圖是強連通的（從所有頂點都存在路徑到達其他頂點），則該圖中最少有多少條有向邊？

A) n B) n+1 C) n-1 D) n*(n-1)

19、全國信息學奧林匹克的官方網站為參與信息學競賽的老師同學們提供相關的信息和資源，請問全國信息學奧林匹克官方網站的網址是：

A) http://www.noi.com/ B) http://www.noi.org/

C) http://www.noi.cn/ D) http://www.xinxixue.com/

20、在參加NOI系列競賽過程中，下面哪一種行為是 不 被嚴格禁止的：

A) 攜帶書寫工具，手錶和不具有通訊功能的電子詞典進入賽場。

B) 在聯機測試中通過手工計算出可能的答案並在程序裡直接輸出答案來獲取分數。

C) 通過互聯網搜索取得解題思路。

D) 在提交的程序中啟動多個進程以提高程序的執行效率。

二．問題求解（共2題，每空5分，共計10分）

1．小陳現有2個任務A，B要完成，每個任務分別有若干步驟如下：A=a1->a2->a3，B=b1->b2->b3->b4->b5。在任何時候，小陳只能專心做某個任務的一個步驟。但是如果願意，他可以在做完手中任務的當前步驟後，切換至另一個任務，從上次此任務第一個未做的步驟繼續。每個任務的步驟順序不能打亂，例如……a2->b2->a3->b3……是合法的，而……a2->b3->a3->b2……是不合法的。小陳從B任務的b1步驟開始做，當恰做完某個任務的某個步驟後，就停工回家吃飯了。當他回來時，只記得自己已經完成了整個任務A，其他的都忘了。試計算小陳飯前已做的可能的任務步驟序列共有 種。

2．有如下的一段程序：

1. a=1;

2. b=a;

3. d=-a;

4. e=a+d;

5. c=2*d;

6. f=b+e-d;

7. g=a*f+c;

現在要把這段程序分配到若干臺（數量充足）用電纜連接的PC上做並行執行。每臺PC執行其中的某幾個語句，並可隨時通過電纜與其他PC通訊，交換一些中間結果。假設每臺PC每單位時間可以執行一個語句，且通訊花費的時間不計。則這段程序最快可以在

單位時間內執行完畢。注意：任意中間結果只有在某臺PC上已經得到，才可以被其他PC引用。例如若語句4和6被分別分配到兩臺PC上執行，則因為語句6需要引用語句4的計算結果，語句6必須在語句4之後執行。

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

1．

#include <iostream>

using namespace std;

int a,b;

int work(int a,int b){

if (a%b)

return work(b,a%b);

return b;

}

int main(){

cin >> a >> b;

cout << work(a,b) << endl;

return 0;

}

輸入：20 12

輸出：_______

2．

#include <iostream>

using namespace std;

int main()

{

int a[3],b[3];

int i,j,tmp;

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

cin >> b[i];

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

{

a[i]=0;

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

{

a[i]+=b[j];

b[a[i]%3]+=a[j];

}

}

tmp=1;

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

{

a[i]%=10;

b[i]%=10;

tmp*=a[i]+b[i];

}

cout << tmp << endl;

return 0;

}

輸入：2 3 5

輸出：_______

3．

#include <iostream>

using namespace std;

const int c=2009;

int main()

{

int n,p,s,i,j,t;

cin >> n >> p;

s=0;t=1;

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

{

t=t*p%c;

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

s=(s+t)%c;

}

cout << s << endl;

return 0;

}

輸入：11 2

輸出：

4．

#include <iostream>

using namespace std;

const int maxn=50;

void getnext(char str[])

{

int l=strlen(str),i,j,k,temp;

k=l-2;

while(k>=0&&str[k]>str[k+1]) k--;

i=k+1;

while(istr[k]) i++;

temp=str[k];

str[k]=str[i-1];

str[i-1]=temp;

for(i=l-1;i>k;i--)

for(j=k+1;j

if(str[j]>str[j+1])

{

temp=str[j];

str[j]=str[j+1];

str[j+1]=temp;

}

return ;

}

int main()

{

char a[maxn];

int n;

cin >> a >> n;

while(n>0)

{

getnext(a);

n--;

}

cout << a << endl;

return 0;

}

輸入：NOIP 3

輸出：

四．完善程序 (前8空，每空3分，後2空，每空2分，共28分)

1．（最大連續子段和）給出一個數列（元素個數不多於100），數列元素均為負整數、正整數、0。請找出數列中的一個連續子數列，使得這個子數列中包含的所有元素之和最大，在和最大的前提下還要求該子數列包含的元素個數最多，並輸出這個最大和以及該連續子數列中元素的個數。例如數列為4，-5，3，2，4時，輸出9和3；數列為1 2 3 -5 0 7 8時，輸出16和7。

#include <iostream>

using namespace std;

int a[101];

int n,i,ans,len,tmp,beg;

int main(){

cin >> n;

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

cin >> a[i];

tmp=0;

ans=0;

len=0;

beg= ① ;

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

if (tmp+a[i]>ans){

ans=tmp+a[i];

len=i-beg;

}

else if ( ② &&i-beg>len)

len=i-beg;

if (tmp+a[i] ③ ){

beg= ④ ;

tmp=0;

}

else

⑤ ;

}

cout << ans << " " << len << endl;

return 0;

}

2. (國王放置) 在n*m的棋盤上放置k個國王，要求k個國王互相不攻擊，有多少種不同的放置方法。假設國王放置在第(x,y)格，國王的攻擊的區域是:(x-1,y-1), (x-1,y),(x-1,y+1),(x,y-1),(x,y+1),(x+1,y-1),(x+1,y),(x+1,y+1)。讀入三個數n,m,k，輸出答案。題目利用回溯法求解。棋盤行標號為0~n-1，列標號為0~m-1。

#include <iostream>

using namespace std;

int n,m,k,ans;

int hash[5][5];

void work(int x,int y,int tot){

int i,j;

if (tot==k){

ans++;

return;

}

do{

while (hash[x][y]){

y++;

if (y==m){

x++;

y= ① ;

}

if (x==n)

return;

}

for (i=x-1;i<=x+1;i++)

if (i>=0&&i

for (j=y-1;j<=y+1;j++)

if (j>=0&&j

② ;

③ ;

for (i=x-1;i<=x+1;i++)

if (i>=0&&i

for (j=y-1;j<=y+1;j++)

if (j>=0&&j

④

;

y++;

if (y==m){

x++;

y=0;

}

if (x==n)

return;

}

while (1);

}

int main(){

cin >> n >> m >> k;

ans=0;

memset(hash,0,sizeof(hash));

⑤ ;

cout << ans << endl;

return 0;

}

十五屆普及組初賽答案（C++）