《全國青少年信息學奧林匹克聯賽初賽試題》由會員分享，可在線閱讀，更多相關《全國青少年信息學奧林匹克聯賽初賽試題（9頁珍藏版）》請在裝配圖網上搜索。

1、第十五屆全國青少年信息學奧林匹克聯賽初賽試題 （ 普及組 C++語言 二小時完成 ） ● ● 全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效 ●● 一． 單項選擇題 （共20題，每題1.5分，共計30分。每題有且僅有一個正確答案。） 1、 關于圖靈機下面的說法哪個是正確的： A) 圖靈機是世界上最早的電子計算機。 B) 由于大量使用磁帶操作，圖靈機運行速度很慢。 C) 圖靈機是英國人圖靈發(fā)明的，在二戰(zhàn)中為破譯德軍的密碼發(fā)揮了重要作用。 D) 圖靈機只是一個理論上的計算模型。 2、關于計算機內存下面的說法哪個是

2、正確的： A) 隨機存儲器（RAM）的意思是當程序運行時，每次具體分配給程序的內存位置是隨機而不確定的。 B) 1MB內存通常是指1024*1024字節(jié)大小的內存。 C) 計算機內存嚴格說來包括主存（memory）、高速緩存（cache）和寄存器（register）三個部分。 D) 一般內存中的數據即使在斷電的情況下也能保留2個小時以上。 3、關于BIOS下面說法哪個是正確的： A) BIOS是計算機基本輸入輸出系統(tǒng)軟件的簡稱。 B) BIOS里包含了鍵盤、鼠標、聲卡、顯卡、打印機等常用輸入輸出設備的驅動程序。 C) BIOS一般由操作系統(tǒng)廠商來開發(fā)完成。 D) BIOS

3、能提供各種文件拷貝、復制、刪除以及目錄維護等文件管理功能。 4、關于CPU下面哪個說法是正確的： A) CPU全稱為中央處理器（或中央處理單元）。 B) CPU可以直接運行匯編語言。 C) 同樣主頻下，32位的CPU比16位的CPU運行速度快一倍。 D) CPU最早是由Intel公司發(fā)明的。 5、關于ASCII，下面哪個說法是正確的： A) ASCII碼就是鍵盤上所有鍵的唯一編碼。 B) 一個ASCII碼使用一個字節(jié)的內存空間就能夠存放。 C) 最新擴展的ASCII編碼方案包含了漢字和其他歐洲語言的編碼。 D) ASCII碼是英國人主持制定并推廣使用的。 6、

4、下列軟件中不是計算機操作系統(tǒng)的是： A) Windows B) Linux C) OS/2 D) WPS 7、關于互聯網，下面的說法哪一個是正確的： A) 新一代互聯網使用的IPv6標準是IPv5標準的升級與補充。 B) 互聯網的入網主機如果有了域名就不再需要IP地址。 C) 互聯網的基礎協(xié)議為TCP/IP協(xié)議。 D) 互聯網上所有可下載的軟件及數據資源都是可以合法免費使用的。 8、關于HTML下面哪種說法是正確的： A） HTML實現了文本、圖形、聲音乃至視頻信息的統(tǒng)一編碼。 B） HTML全稱為超文本標記語言。 C） 網上廣泛使用的 Fl

5、ash動畫都是由HTML編寫的。 D） HTML也是一種高級程序設計語言。 9、關于程序設計語言，下面哪個說法是正確的： A) 加了注釋的程序一般會比同樣的沒有加注釋的程序運行速度慢。 B) 高級語言開發(fā)的程序不能使用在低層次的硬件系統(tǒng)如：自控機床或低端手機上。 C) 高級語言相對于低級語言更容易實現跨平臺的移植。 D) 以上說法都不對。 10、已知大寫字母A的ASCII編碼為65（10進制），則大寫字母J的10進制ASCII編碼為： A) 71 B) 72 C) 73 D) 以上都不是 11、十進制小數125.125對應的8進制數是 A)

6、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

7、 C) n-1 D) n+1 15、快速排序最壞情況下的算法時間復雜度為： A) O(log2n) B) O(n) C) O(nlog2n) D) O(n2) 16. 有一個由4000個整數構成的順序表，假定表中的元素已經按升序排列，采用二分查找定位一個元素。則最多需要幾次比較就能確定是否存在所查找的元素： A) 11次 B) 12次 C) 13次 D) 14次 17、排序算法是穩(wěn)定的意思是關鍵碼相同的記錄排序前后相對位置不發(fā)生改變，下列哪種排序算法是不穩(wěn)定的： A) 冒泡排序 B) 插入排

8、序 C) 歸并排序 D) 快速排序 18、已知n個頂點的有向圖，若該圖是強連通的（從所有頂點都存在路徑到達其他頂點），則該圖中最少有多少條有向邊？ A) n B) n+1 C) n-1 D) n*(n-1) 19、全國信息學奧林匹克的官方網站為參與信息學競賽的老師同學們提供相關的信息和資源，請問全國信息學奧林匹克官方網站的網址是： A) B) http://www.noi.org/ C) D) 20、在參加NOI系列競賽過程中，下面哪一種行為是 不 被嚴格禁止的： A) 攜帶書寫工具，手表和不具有通訊功能

9、的電子詞典進入賽場。 B) 在聯機測試中通過手工計算出可能的答案并在程序里直接輸出答案來獲取分數。 C) 通過互聯網搜索取得解題思路。 D) 在提交的程序中啟動多個進程以提高程序的執(zhí)行效率。 二．問題求解（共2題，每空5分，共計10分） 1．小陳現有2個任務A，B要完成，每個任務分別有若干步驟如下：A=a1->a2->a3，B=b1->b2->b3->b4->b5。在任何時候，小陳只能專心做某個任務的一個步驟。但是如果愿意，他可以在做完手中任務的當前步驟后，切換至另一個任務，從上次此任務第一個未做的步驟繼續(xù)。每個任務的步驟順序不能打亂，例如……a2->b2->a3->b3……

10、是合法的，而……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上做并行執(zhí)行。每臺PC執(zhí)行其中的某幾個語句，并可隨時通過電纜與其他PC通訊，交換一些中間結果。假設

11、每臺PC每單位時間可以執(zhí)行一個語句，且通訊花費的時間不計。則這段程序最快可以在 單位時間內執(zhí)行完畢。注意：任意中間結果只有在某臺PC上已經得到，才可以被其他PC引用。例如若語句4和6被分別分配到兩臺PC上執(zhí)行，則因為語句6需要引用語句4的計算結果，語句6必須在語句4之后執(zhí)行。 三．閱讀程序寫結果（共4題，每題8分，共計32分） 1． #include using namespace std; int a,b; int work(int a,int b){ if (a%b) return work(b,a%b); ret

12、urn b; } int main(){ cin >> a >> b; cout << work(a,b) << endl; return 0; } 輸入：20 12 輸出：_______ 2． #include 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++)

13、{ 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 using namespace std; const int c=2009; int main() { int n,p,s,i,j,t;

14、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 using namespace std; const int maxn=50; void getnext(char str[]) { int l=strlen(str),i,j,k,temp; k=l-

15、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;jstr[j+1]) { temp=str[j]; str[j]=str[j+1]; str[j+1]=temp; } return ; } int main()

16、{ 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．（最大連續(xù)子段和）給出一個數列（元素個數不多于100），數列元素均為負整數、正整數、0。請找出數列中的一個連續(xù)子數列，使得這個子數列中包含的所有元素之和最大，在和最大的前提下還要求該子數列包含的元素個數最多，并輸出這

17、個最大和以及該連續(xù)子數列中元素的個數。例如數列為4，-5，3，2，4時，輸出9和3；數列為1 2 3 -5 0 7 8時，輸出16和7。 #include 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]

18、>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個國王互相不攻擊，有多少種不同的放置方

19、法。假設國王放置在第(x,y)格，國王的攻擊的區(qū)域是:(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 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++;

20、 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=0&&j

21、+) if (i>=0&&i=0&&j> n >> m >> k; ans=0; memset(hash,0,sizeof(hash)); ⑤ ; cout << ans << endl; return 0; }