2009全國青少年信息學(xué)奧林匹克聯(lián)賽初賽試題

1、2009第十五屆全國青少年信息學(xué)奧林匹克聯(lián)賽初賽試題(提高組C語言 二小時完成) 全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效一.單項選擇題 (共10題，每題1.5分，共計15分。每題有且僅有一個正確答案。)1、關(guān)于圖靈機下面的說法哪個是正確的：A)圖靈機是世界上最早的電子計算機。B)由于大量使用磁帶操作，圖靈機運行速度很慢。C)圖靈機只是一個理論上的計算模型。D)圖靈機是英國人圖靈發(fā)明的，在二戰(zhàn)中為破譯德軍的密碼發(fā)揮了重要作用?！痉治觥窟x擇CA最早的計算機是ENIACB圖靈機是計算機模型，沒有運行速度，更談不上磁帶操作D圖靈機是英國人阿蘭圖靈提出的理論，阿蘭圖靈本人在二戰(zhàn)中破譯德軍密

2、碼系統(tǒng)發(fā)揮重要作用，而不是圖靈機發(fā)揮作用2、關(guān)于BIOS下面的說法哪個是正確的：AA) BIOS是計算機基本輸入輸出系統(tǒng)軟件的簡稱。B) BIOS里包含了鍵盤、鼠標、聲卡、圖形界面顯器等常用輸入輸出設(shè)備的驅(qū)動程序。C) BIOS 一般由操作系統(tǒng)廠商來開發(fā)完成。D) BIOS能提供各種文件拷貝、復(fù)制、刪除以及目錄維護等文件管理功能。其實bios=Basic Input Output Systems但是對于是否是軟件這一說法還存在爭議呢！B中BIOS只存一些系統(tǒng)啟動的基本信息，這些設(shè)備的驅(qū)動程序是不存的。C項中BIOS 一般是由單獨的芯片廠家生產(chǎn)的，最著名的都是臺灣的三家。D項中，固件BIOS根本

3、這些功能3、已知大寫字母A的ASCII編碼為65 (十進制)，則大寫字母J的 十六進制ASCII編碼為：A) 48 B) 49 C) 50 D)以上都不是4、在字長為16位的系統(tǒng)環(huán)境下，一個16位帶符號整數(shù)的二進制補碼為 1111111111101101。其對應(yīng)的 十進制整數(shù)應(yīng)該是：A) 19 B) - 19 C) 18 D) -181111111111101101的原碼為1000000000010011也就是-19,最高位為符號位5、一個包含n個分支結(jié)點(非葉結(jié)點)的非空滿 k叉樹，k>=1,它的葉結(jié)點數(shù)目為：DA) nk + 1 B) nk- 1 C) (k+1)n- 1 D. (k

4、- 1)n+1考多叉樹的性質(zhì)，N0=(K-1)N+1 ,考試的時帶入K=2時候，驗證二叉樹能得到結(jié)果6.表達式a*(b+c) - d的后綴表達式是：BA) abcd*+- B) abc+*d- C) abc*+d- D) - +*abcd主要是考樹的遍歷，要明白前綴、中綴和后綴表達式。構(gòu)造二叉樹，操作數(shù)做葉子節(jié)點，運算符做非葉節(jié)點。按中序遍歷就可以得到中綴表達式7、最優(yōu)前綴編碼，也稱 Huffman編碼。這種編碼組合的特點是對于較頻繁使用的元素給與較短的唯 編碼，以提高通訊的效率。下面編碼組合哪一組不是合法的前綴編碼。BA) (00, 01, 10, 11)B) (0, 1, 00, 11)C

5、) (0, 10, 110, 111)D) (1, 01, 000, 001)0是00的前綴碼，這部分是數(shù)據(jù)結(jié)構(gòu)中哈夫曼編碼處的知識8、快速排序平均情況和最壞情況下的算法時間復(fù)雜度分別為：A2A)平均情況 O(nlog2n),取壞情況O(n )B)平均情況O(n),最壞情況O(n2)C)平均情況 O(n),最壞情況O(nlog2n)D)平均情況O(log2n),最壞情況O(n2)最好的時候是nHog (2, n),最壞情況的是退化成冒泡排序，復(fù)雜度為 O (n2)9、左圖給出了一個加權(quán)無向圖， 從頂點V。開始用prim算法求最 小生成樹。則依次加入最小生成 樹的頂點集合白頂點序列為A:A) V

6、0, V1, V2, V3, V5, V4B) V0, V1, V5, V4, V3, V3C) V1, V2, V3, V0, V5, V4D) V1, V2, V3, V0, V4, V5加入的邊依次為 v0v1、v1v2、v1v3 (或v2v3)、v1v5、 v3v410、全國信息學(xué)奧林匹克的官方網(wǎng)站為參與信息學(xué)競賽的老師同學(xué)們提供相關(guān)的信息和資源，請問全國 信息學(xué)奧林匹克官方網(wǎng)站的網(wǎng)址是：CA) B) /C) D) 不定項選擇題(共10題，每題1.5分，共計15分。每題正確答案的個數(shù)不少于1。多選或少選1、關(guān)于CPU下面哪些說法是正確的：ABA） CP

7、U全稱為中央處理器（或中央處理單元）。B） CPU能直接運行機器語言。C） CPU最早是由Intel公司發(fā)明的。D）同樣主頻下，32位的CPU比16位的CPU運行速度快一倍。C項中，Intel最早發(fā)明的是微處理器，而 CPU之前就由電子管、晶體管實現(xiàn)著呢D項中，位數(shù)只能說明處理的字長，所在的系統(tǒng)硬件指令不同，速度很難說誰快2、關(guān)于計算機內(nèi)存下面的說法哪些是正確的：BDA）隨機存儲器（RAM）的意思是當(dāng)程序運行時，每次具體分配給程序的內(nèi)存位置是隨機而不確定的。B） 一般的個人計算機在同一時刻只能存/取一個特定的內(nèi)存單元。C）計算機內(nèi)存嚴格說來包括主存（memory）、高速緩存（eache和寄存器

8、（register）三個部分。D） 1MB內(nèi)存通常是指1024*1024字節(jié)大小的內(nèi)存。一般是對字節(jié)的一個單元串行操作。1MB=1024KB=1024*1024BA中RAM不是位置隨機，而是隨時訪問，所謂 隨機存取”，指的是當(dāng)存儲器中的消息被讀取或?qū)懭霑r， 所需要的時間與這段信息所在的位置無關(guān)。C中高速緩存和寄存器的物理實現(xiàn)是集成在 CPU中,這兩部分不屬于馮諾依曼體系中的五大部分的任意 一個部分。3、關(guān)于操作系統(tǒng)下面說法哪些是正確的：BCA.多任務(wù)操作系統(tǒng)專用于多核心或多個 CPU架構(gòu)的計算機系統(tǒng)的管理。B.在操作系統(tǒng)的管理下，一個完整的程序在運行過程中可以被部分存放在內(nèi)存中。C.分時系統(tǒng)讓

9、多個用戶可以共享一臺主機的運算能力，為保證每個用戶都得到及時的響應(yīng)通常會采 用時間片輪轉(zhuǎn)調(diào)度的策略。D.為了方便上層應(yīng)用程序的開發(fā)，操作系統(tǒng)都是免費開源的。A多任務(wù)系統(tǒng)可以是單個 CPU構(gòu)架的，普通的PC都是多任務(wù)的。D操作系統(tǒng)不是都免費開源4、關(guān)于計算機網(wǎng)絡(luò)，下面的說法哪些是正確的：CA）網(wǎng)絡(luò)協(xié)議之所以有很多層主要是由于新技術(shù)需要兼容過去老的實現(xiàn)方案。B）新一代互聯(lián)網(wǎng)使用的IPv6標準是IPv5標準的升級與補充。C） TCP/IP是互聯(lián)網(wǎng)的基礎(chǔ)協(xié)議簇，包含有 TCP和IP等網(wǎng)絡(luò)與傳輸層的通訊協(xié)議。D）互聯(lián)網(wǎng)上每一臺入網(wǎng)主機通常都需要使用一個唯一的IP地址，否則就必須注冊一個固定的域名來標明其

10、地址。B新的IPv6是IPv4的升級。D即使注A網(wǎng)絡(luò)協(xié)議分層不是為了兼容，而是根據(jù)網(wǎng)絡(luò)分層模型來的冊了域名也要有IP地址的5、關(guān)于HTML下面哪些說法是正確的：BDA） HTML全稱超文本標記語言，實現(xiàn)了文本、圖形、聲音乃至視頻信息的統(tǒng)一編碼。B） HTML不單包含有網(wǎng)頁內(nèi)容信息的描述，同時也包含對網(wǎng)頁格式信息的定義。C）網(wǎng)頁上的超鏈接只能指向外部的網(wǎng)絡(luò)資源，本網(wǎng)站網(wǎng)頁間的聯(lián)系通過設(shè)置標簽來實現(xiàn)。D）點擊網(wǎng)頁上的超鏈接從本質(zhì)上就是按照該鏈接所隱含的統(tǒng)一資源定位符（URL）請求網(wǎng)絡(luò)資源或網(wǎng)絡(luò)服務(wù)。A沒有都統(tǒng)一編碼C本網(wǎng)站頁面也可以用超鏈接，就是絕對路徑。也可以用相對路徑。6、若3個頂點的無權(quán)圖G

11、的鄰接矩陣用數(shù)組存儲為0 , 1, 1, 1, 0, 1, 0, 1, 0,假定在具體 存儲中頂點依次為：vi, V2, V3o關(guān)于該圖，下面的說法哪些是正確的：ABDA）該圖是有向圖。B）該圖是強連通的。C）該圖所有頂點的入度之和減所有頂點的出度之和等于1。D）從vi開始的深度優(yōu)先遍歷所經(jīng)過的頂點序列與廣度優(yōu)先的頂點序列是相同的。7、在帶尾指針（鏈表指針clist指向尾結(jié)點）的非空循環(huán)單鏈表中每個結(jié)點都以next字段的指針指向下一個節(jié)點。假定其中已經(jīng)有 2個以上的結(jié)點。下面哪些說法是正確的：A）如果p指向一個待插入的新結(jié)點，在頭部插入一個元素的語句序列為：p->next = clist

12、->next; clist->next = p;B）如果p指向一個待插入的新結(jié)點，在尾部插入一個元素的語句序列為：p->next = clist； clist->next = p;C）在頭部刪除一個結(jié)點的語句序列為：p = clist->next; clist->next = clist->next->next; free（p）;D）在尾部刪除一個結(jié)點的語句序列為。p = clist; clist = clist ->next; free（p）;8、散列表的地址區(qū)間為0-10，散列函數(shù)為H（K）=K mod 11。采用開地址法的線性探查法處

13、理沖突，并將 關(guān)鍵字序列26, 25, 72, 38, 8, 18, 59存儲到散列表中，這些元素存入散列表的順序并不確定。假定之前散列表為空，則元素 59存放在散列表中的可能地址有：A） 5 B） 7 C） 9 D） 10選才? ABC哈希函數(shù)的沖突避免計算各個的散列值26257238818594365874這樣就可能5的順序：25、597的順序：25、26、38、599的順序:25、26、38、18、59上面的順序不是唯一的。9、排序算法是穩(wěn)定的意思是關(guān)鍵碼相同的記錄排序前后相對位置不發(fā)生改變，下列哪些排序算法是穩(wěn)定的：ABCDA)插入排序B)基數(shù)排序C)歸并排序 D)冒泡排序在編程實現(xiàn)的

14、時候，只要控制好邊界都是可以達到穩(wěn)定排序的10、在參加NOI系列競賽過程中，下面哪些行為是被嚴格禁止的：ACDA)攜帶書寫工具，手表和不具有通訊功能的電子詞典進入賽場。B)在聯(lián)機測試中通過手工計算出可能的答案并在程序里直接輸出答案來獲取分數(shù)。C)通過互聯(lián)網(wǎng)搜索取得解題思路。D)在提交的程序中啟動多個進程以提高程序的執(zhí)行效率。3 .問題求解(共2題，每空5分，共計10分)1 .拓撲排序是指將有向無環(huán)圖 G中的所有頂點排成一個線性序列，使得圖中任意一對頂點u和v,若<u, v> CE(G),則u在線性序列中出現(xiàn)在v之前，這樣的線性序列成為拓撲序列。如下的有向無環(huán) 圖，對其頂點作拓撲排序

15、，則所有可能的拓撲序列的個數(shù)為432。用排列組合即可，先確定12346的順序，然后將7插入內(nèi)部有兩個位置可選，然后將 5插入時候，可以 有6個位置選擇。最后，放89的時候，考慮兩種情況，89在一起，有8個位置選；89不在一起，8個 位置選2個。C(2,1) C(6,1) C(8,1)+C(8,2)=2 6 潦+28)=4322 .某個國家的錢幣面值有1,7, 72, 73共計四種，如果要用現(xiàn)金付清10015元的貨物，假設(shè)買賣雙方 各種錢幣的數(shù)量無限且允許找零，那么交易過程中至少需要流通小5_張錢幣。10015化成7進制數(shù)是41125,正常是4W+1=29張7A3面額的，1張7A2面額，2張7面

16、額的，5張1面額的。因為可以無限且找零，并要求最少流通數(shù)量。這樣就把7進制上大于等于4的數(shù)a,用找零7-a的方法代替，這樣就能達到最少。這里 29、1、2、5中只有5是大于4的，所以用一張大額的，并 7-5 找零的方法計算。這樣，總數(shù) 29+1+2+(1+7-5)=35張。4 .閱讀程序?qū)懡Y(jié)果(共4題，每題8分，共計32分)1. #include <stdio.h>int a,b;int work(int a,int b)if (a%b)return work(b,a%b); return b;int main()scanf("%d%d”,&a,&b);p

17、rintf("%dn",work(a,b);return 0;輸入：123 321輸出：2. #include <stdio.h>int main()int a4,b4;int i,j,tmp;for (i=0;i<4;i+)scanf("%d”,&bi);for (i=0;i<4;i+)ai=0;for (j=0;j<=i;j+)ai+=bj;bai%4+=aj;tmp=1;for (i=0;i<4;i+)ai%=10;bi%=10;tmp*=ai+bi;printf("%dn",tmp);retu

18、rn 0;輸入：2 3 5 7輸出：3. #include<stdio.h>#define maxn 50const int y=2009;int main()int n,cmaxnmaxn,i,j,s=0;scanf("%d",&n);c二1；for(i=1;i<=n;i+)ci0=1；for(j=1;j<i;j+)cij=ci-1j-1+ci-1j；cii=1；for(i=0;i<=n;i+)s=(s+cni)%y;printf("%dn",s);return 0;輸入：17輸出：4. #include <

19、stdio.h>int main()int n,m,i,j,p,k;int a100,b100;scanf("%d%d",&n,&m);a0=n;i=0;p=0；k=0;dofor (j=0;j<i;j+) if (ai=aj) p=1；k=j； break;if (P)break;bi=ai/m； ai+1=ai%m*10;i+；while (ai!=0);printf("%d.",b0);for (j=1； j<k； j+) printf("%d",bj);if (P)printf("(

20、");for (j=k;j<i;j+) printf("%d",bj);if (p)printf(")");printf("n");return 0;輸入：5 13輸出：五.完善程序(前5空，每空2分，后6空，每空3分，共28分)1.(最大連續(xù)子段和)給出一個數(shù)列(元素個數(shù)不多于100),數(shù)列元素均為負整數(shù)、正整數(shù)、00 請找出數(shù)列中的一個連續(xù)子數(shù)列，使得這個子數(shù)列中包含的所有元素之和最大，在和最大的前提下還要 求該子數(shù)列包含的元素個數(shù)最多，并輸出這個最大和以及該連續(xù)子數(shù)列中元素的個數(shù)。例如數(shù)列為4,-5, 3, 2,

21、 4時，輸出9和3;數(shù)列為1 2 3 -5 0 7 8時，輸出16和7。#include <stdio.h>int a101;int n,i,ans,len,tmp,beg,end;int main()scanf("%d",&n);for (i=1;i<=n;i+)scanf("%d”,&ai);tmp=0;ans=0;len=0;beg= ;for (i=1;i<=n;i+)if (tmp+ai>ans) ans=tmp+ai; len=i-beg;else if ( &&i-beg>len)

22、len=i-beg;if (tmp+ai )beg= ;tmp=0;else printf("%d %dn",ans,len); return 0;2.(尋找等差數(shù)列)有一些長度相等的等差數(shù)列(數(shù)列中每個數(shù)都為 059的整數(shù))，設(shè)長度均為L, 將等差數(shù)列中的所有數(shù)打亂順序放在一起?，F(xiàn)在給你這些打亂后的數(shù)，問原先，L最大可能為多大？先讀入一個數(shù)n (1<=n<=60),再讀入n個數(shù)，代表打亂后的數(shù)。輸出等差數(shù)列最大可能長度 L。#include <stdio.h>int hash60;int n, x, ans, maxnum; int work(int