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

1、百度文庫7第十五屆全國青少年信息學奧林匹克聯(lián)賽初賽試題(提高組C+語言二小時完成) 全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效一.單項選擇題(共10題，每題分，共計 15分。每題有且僅有一個正確答案。)1、關(guān)于圖靈機下面的說法哪個是正確的：A)圖靈機是世界上最早的電子計算機。B)由于大量使用磁帶操作，圖靈機運行速度很慢。C)圖靈機只是一個理論上的計算模型。D)圖靈機是英國人圖靈發(fā)明的，在二戰(zhàn)中為破譯德軍的密碼發(fā)揮了重要作用。2、關(guān)于BIOS下面的說法哪個是正確的：A) BIOS是計算機基本輸入輸出系統(tǒng)軟件的簡稱。B) BIOS里包含了鍵盤、鼠標、聲卡、圖形界面顯器等常用輸入輸出設(shè)備的

2、驅(qū)動程序。,/ C) BIOS 一般由操作系統(tǒng)廠商來開發(fā)完成。D) BIOS能提供各種文件拷貝、復制、刪除以及目錄維護等文件管理功能。3、已知大寫字母 A的ASCII編碼為65 (十進制)，則大寫字母 J的 十六進制 ASCII編碼為：A) 48 B) 49 C) 50 D)以上都不是4、在字長為16位的系統(tǒng)環(huán)境下，一個16位帶符號整數(shù)的二進制補碼為101。其對應(yīng)的十進制整數(shù)應(yīng)該是:A) 19 B) -19 C) 18 D) -185、一個包含n個分支結(jié)點(非葉結(jié)點)的非空滿k叉樹，k=1 ,它的葉結(jié)點數(shù)目為：A) nk + 1 B) nk-1 C) (k+1)n -1 D. (k-1)n+1

3、6.表達式a*(b+c)-d的后綴表達式是：A) abcd*+ - B) abc+*d - C) abc*+d - D) - +*abcd7、最優(yōu)前綴編碼，也稱 Huffman編碼。這種編碼組合的特點是對于較頻繁使用的元素給與較短的唯一編 碼，以提高通訊的效率。下面編碼組合哪一組不是合法的前綴編碼。A) (00, 01, 10, 11)B) (0, 1, 00, 11)C) (0, 10, 110, 111)D) (1, 01, 000, 001)8、快速排序平均情況和最壞情況下的算法時間復雜度分別為：A)平均情況 O(nlog2n),最壞情況 O(n2)/B)平均情況 O(n),最壞情況O(

4、n2)C)平均情況O(n), 最壞情況O(nlog 2n)D)平均情況 O(log 2n), 最壞情況O(n2)/9、左圖給出了一個加權(quán)無向圖，從 頂點V。開始用prim算法求最小生成 樹。則依次加入最小生成樹的頂點 集合的頂點序列為：A) V0, V1, V2, V3, V5, V4B) V0, V1, V5, V4, V3, V3C) V1, V2, V3, V0, V5, V4D) V1, V2, V3, V0, V4, V510、全國信息學奧林匹克的官方網(wǎng)站為參與信息學競賽的老師同學們提供相關(guān)的信息和資源，請問全國信 息學奧林匹克官方網(wǎng)站的網(wǎng)址是：A）B）D）二.不定項選擇題 （共10

5、題，每題分，共計 15分。每題正確答案的個數(shù)不少于1。多選或少選均不得分）。1、關(guān)于CPU下面哪些說法是正確的：/A） CPU全稱為中央處理器（或中央處理單元）。B） CPU能直接運行機器語言。./C） CPU最早是由Intel公司發(fā)明的。D） 同樣主頻下，32位的CPU比16位的CPU運行速度快一倍。2、關(guān)于計算機內(nèi)存下面的說法哪些是正確的：A） 隨機存儲器（RAM ）的意思是當程序運行時，每次具體分配給程序的內(nèi)存位置是隨機而不確定的。B） 一般的個人計算機在同一時刻只能存/取一個特定的內(nèi)存單元。C） 計算機內(nèi)存嚴格說來包括主存（ memory）、高速緩存（cache）和寄存器（regist

6、er）三個部分。D） / 1MB內(nèi)存通常是指1024*1024字節(jié)大小的內(nèi)存。3、關(guān)于操作系統(tǒng)下面說法哪些是正確的：A.多任務(wù)操作系統(tǒng)專用于多核心或多個CPU架構(gòu)的計算機系統(tǒng)的管理。B.在操作系統(tǒng)的管理下，一個完整的程序在運行過程中可以被部分存放在內(nèi)存中。C.分時系統(tǒng)讓多個用戶可以共享一臺主機的運算能力，為保證每個用戶都得到及時的響應(yīng)通常會采 用時間片輪轉(zhuǎn)調(diào)度的策略。D.為了方便上層應(yīng)用程序的開發(fā)，操作系統(tǒng)都是免費開源的。4、關(guān)于計算機網(wǎng)絡(luò)，下面的說法哪些是正確的：A）網(wǎng)絡(luò)協(xié)議之所以有很多層主要是由于新技術(shù)需要兼容過去老的實現(xiàn)方案。B）新一代互聯(lián)網(wǎng)使用的IPv6標準是IPv5標準的升級與補充。

7、C） TCP/IP是互聯(lián)網(wǎng)的基礎(chǔ)協(xié)議簇，包含有 TCP和IP等網(wǎng)絡(luò)與傳輸層的通訊協(xié)議。D）互聯(lián)網(wǎng)上每一臺入網(wǎng)主機通常都需要使用一個唯一的IP地址，否則就必須注冊一個固定的域名來標明其地址。5、關(guān)于HTML下面哪些說法是正確的：A）、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ù)。/6、若3個頂點的無權(quán)圖 G的鄰

8、接矩陣用數(shù)組存儲為0 , 1, 1, 1 , 0, 1 , 0 , 1, 0，假定在具體存儲中頂點依次為：V1, V2, V3O關(guān)于該圖，下面的說法哪些是正確的：/A） 該圖是有向圖。/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 = clis

9、t-next; clist-next = p; 1./B） 如果p指向一個待插入的新結(jié)點，在尾部插入一個元素的語句序列為： p-next = clist ； clist-next = p;C） 在頭部刪除一個結(jié)點的語句序列為：p = clist-next; clist-next = clist-next-next; delete p;D） 在尾部刪除一個結(jié)點的語句序列為。p = clist; clist = clist -next; delete p;8、散列表的地址區(qū)間為 0-10，散列函數(shù)為H(K)=K mod 11 。采用開地址法的線性探查法處理沖突，并將關(guān) 鍵字序列26, 25, 72

10、, 38, 8, 18, 59存儲到散列表中，這些元素存入散列表的順序并不確定。假定 之前散列表為空，則元素 59存放在散列表中的可能地址有：A) 5 B) 7 C) 9 D) 109、排序算法是穩(wěn)定的意思是關(guān)鍵碼相同的記錄排序前后相對位置不發(fā)生改變，下列哪些排序算法是穩(wěn)定的：A)插入排序B)基數(shù)排序C)歸并排序D)冒泡排序10、在參加NOI系列競賽過程中，下面哪些行為是被嚴格禁止的：A)攜帶書寫工具，手表和不具有通訊功能的電子詞典進入賽場。B)在聯(lián)機測試中通過手工計算出可能的答案并在程序里直接輸出答案來獲取分數(shù)。C)通過互聯(lián)網(wǎng)搜索取得解題思路。D) 一在提交的程序中啟動多個進程以提高程序的執(zhí)

11、行效率。3 .問題求解(共 2題，每空5分，共計10分)1 .拓撲排序是指將有向無 環(huán)圖G中的所有頂點排成一個線性序列，使得圖中任意一對頂點u和v,若 CE(G),則u在線性序列中出現(xiàn)在 v之前，這樣的線性序列成為拓撲序列。如下的有向無環(huán)圖， 對其頂點做拓撲排序，則所有可能的拓撲序列的個數(shù)為 。2,某個國家的錢幣面值有 1,7, 72, 73共計四種，如果要用現(xiàn)金付清 10015元的貨物，假設(shè)買賣雙方各 種錢幣的數(shù)量無限且允許找零，那么交易過程中至少需要流通 張錢幣。4 .閱讀程序?qū)懡Y(jié)果(共 4題，每題8分，共計32分) 1.#include using namespace std; int

12、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;輸入：123 321輸出：2.#include using namespace std;int main()int a4,b4;int i,j,tmp; /for (i=0;i bi;for (i=0;i4;i+)ai=0;for (j=0;j=i;j+)ai+=bjbai%4+=aj;tmp=1;for (i=0;i4;i+)ai%=10;bi%=10;tmp*=ai+

13、bi;cout tmp endl;return 0;輸入：2 3 5 7輸出：3. #include using namespace std;const int maxn=50;const int y=2009;int main()int n,cmaxnmaxn,i,j,s=0;cin n;c00=1；for(i=1;i=n;i+)(ci0=1；for(j=1;ji;j+)cij=ci-1j-1+ci-1j;cii=1;)for(i=0;i=n;i+)s=(s+cni)%y;cout s endl;return 0;)輸入：17 輸出：4. #include using namespace s

14、td;int main()(int n,m,i,j,p,k;int a100,b100;cin n m;a0=n;i=0;p=0;k=0;do(for (j=0;ji;j+)if (ai=aj)(p=1;k=j;break;)if (p)break;bi=ai/m;ai+1=ai%m*10;i+;while (ai!=0);cout b0 .;for (j=1； jk； j+) cout bj;/if (P) cout (;/for (j=k;ji;j+)/cout bj; 二if (P)cout );cout endl;return 0;輸入：5 13 輸出：五.完善程序(前5空，每空2分，

15、后6空，每空3分，共28分)1 .(最大連續(xù)子段和)給出一個數(shù)列(元素個數(shù)不多于100),數(shù)列元素均為負整數(shù)、正整數(shù)0。請找出數(shù)列中的一個連續(xù)子數(shù)列，使得這個子數(shù)列中包含的所有元素之和最大，在和最大的前提下還要求該子數(shù)列包含的元素個數(shù)最多，并輸出這個最大和以及該連續(xù)子數(shù)列中元素的個數(shù)。例如數(shù)列為4, -5 , 3,2 , 4時，輸出9和3;數(shù)列為1 2 3 -5 0 7 8 時，輸出16和7。#include using namespace std;int a101;int n,i,ans,len,tmp,beg,end;int main() cin n; for (i=1;i ai;tmp=

16、0; /ans=0;、/len=0;/beg= ；、/for (i=1;ians) /ans=tmp+ai;/len=i-beg;、/ else if ( &i-beglen)/len=i-beg;、/if (tmp+ai)/beg= ；tmp=0;else； cout ans len endl;/return 0;y2.(尋找等差數(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。#in

17、clude Xusing namespace std; int hash60;int n, x, ans, maxnum; int work(int now) int first, second, delta, i; int ok;while (& !hashnow)+now;if (now maxnum)return 1;first = now; for (second = first; second maxnum)break; if (delta = 0) ok = ()；elseok = 1;for (i = 0; i ans; i+) ok = & (hashfirst+delta*i); if (ok)for (i = 0; i ans; i+)/hashfirst+delta*i-;if (work(first) /return 1;for (i = 0; i n;maxnum = 0;for (i = 0; i x;hashx+;if (x maxnum)/maxnum = x;for (ans = n; ans = 1; ans-)if ( n%ans=0 &)cout ans endl;break;return 0;百度文庫第十五屆全國青少年信息學奧林匹克聯(lián)賽初賽試題提高組答卷紙姓名：_v得分:單項選擇題 (共10題，