歷年noip初賽普及組試題

歷年noip普及組初賽試題匯編蕪湖縣實(shí)驗(yàn)學(xué)校NOIP初賽復(fù)習(xí)資料第十五屆全國青少年信息學(xué)奧林匹克聯(lián)賽初賽試題(2009)(普及組C++語言二小時(shí)完成)??全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效??一．單項(xiàng)選擇題(共20題，每題1.5分，共計(jì)30分。每題有且僅有一個(gè)正確答案。)關(guān)于圖靈機(jī)下面的說法哪個(gè)是正確的：圖靈機(jī)是世界上最早的電子計(jì)算機(jī)。由于大量使用磁帶操作，圖靈機(jī)運(yùn)行速度很慢。圖靈機(jī)是英國人圖靈發(fā)明的，在二戰(zhàn)中為破譯德軍的密碼發(fā)揮了重要作用。圖靈機(jī)只是一個(gè)理論上的計(jì)算模型。2、關(guān)于計(jì)算機(jī)內(nèi)存下面的說法哪個(gè)是正確的：A)隨機(jī)存儲(chǔ)器(RAM)的意思是當(dāng)程序運(yùn)行時(shí)，每次具體分配給程序的內(nèi)存位置是隨機(jī)而不確定的。1MB內(nèi)存通常是指1024*1024字節(jié)大小的內(nèi)存。C)計(jì)算機(jī)內(nèi)存嚴(yán)格說來包括主存(memory)、高速緩存(cache)和寄存器(register)三個(gè)部分。一般內(nèi)存中的數(shù)據(jù)即使在斷電的情況下也能保留2個(gè)小時(shí)以上。3、關(guān)于BIOS下面說法哪個(gè)是正確的：BIOS是計(jì)算機(jī)基本輸入輸出系統(tǒng)軟件的簡稱。BIOS里包含了鍵盤、鼠標(biāo)、聲卡、顯卡、打印機(jī)等常用輸入輸出設(shè)備的驅(qū)動(dòng)程序。BIOS一般由操作系統(tǒng)廠商來開發(fā)完成。BIOS能提供各種文件拷貝、復(fù)制、刪除以及目錄維護(hù)等文件管理功能。4、關(guān)于CPU下面哪個(gè)說法是正確的：CPU全稱為中央處理器(或中央處理單元)。CPU可以直接運(yùn)行匯編語言。C)同樣主頻下，32位的CPU比16位的CPU運(yùn)行速度快一倍。D)CPU最早是由Intel公司發(fā)明的。5、關(guān)于ASCII，下面哪個(gè)說法是正確的：ASCII碼就是鍵盤上所有鍵的唯一編碼。一個(gè)ASCII碼使用一個(gè)字節(jié)的內(nèi)存空間就能夠存放。C)最新擴(kuò)展的ASCII編碼方案包含了漢字和其他歐洲語言的編碼。D)ASCII碼是英國人主持制定并推廣使用的。6、下列軟件中不是計(jì)算機(jī)操作系統(tǒng)的是：A)WindowsB)LinuxC)OS/2D)WPS7、關(guān)于互聯(lián)網(wǎng)，下面的說法哪一個(gè)是正確的：A)新一代互聯(lián)網(wǎng)使用的IPv6標(biāo)準(zhǔn)是IPv5標(biāo)準(zhǔn)的升級與補(bǔ)充。B)互聯(lián)網(wǎng)的入網(wǎng)主機(jī)如果有了域名就不再需要IP地址。C)互聯(lián)網(wǎng)的基礎(chǔ)協(xié)議為TCP/IP協(xié)議。D)互聯(lián)網(wǎng)上所有可下載的軟件及數(shù)據(jù)資源都是可以合法免費(fèi)使用的。8、關(guān)于HTML下面哪種說法是正確的：HTML實(shí)現(xiàn)了文本、圖形、聲音乃至視頻信息的統(tǒng)一編碼。HTML全稱為超文本標(biāo)記語言。C)網(wǎng)上廣泛使用的Flash動(dòng)畫都是由HTML編寫的。D)HTML也是一種高級程序設(shè)計(jì)語言。9、關(guān)于程序設(shè)計(jì)語言，下面哪個(gè)說法是正確的：加了注釋的程序一般會(huì)比同樣的沒有加注釋的程序運(yùn)行速度慢。高級語言開發(fā)的程序不能使用在低層次的硬件系統(tǒng)如：自控機(jī)床或低端手機(jī)上。高級語言相對于低級語言更容易實(shí)現(xiàn)跨平臺(tái)的移植。以上說法都不對。10、已知大寫字母A的ASCII編碼為65(10進(jìn)制)，則大寫字母J的10進(jìn)制ASCII編碼為：A)71B)72C)73D)以上都不是11、十進(jìn)制小數(shù)125.125對應(yīng)的8進(jìn)制數(shù)是A)100.1B)175.175C)175.1D)100.17512、有六個(gè)元素FEDCBA從左至右依次順序進(jìn)棧，在進(jìn)棧過程中會(huì)有元素被彈出棧。問下列哪一個(gè)不可能是合法的出棧序列？A)EDCFABB)DECABFC)CDFEBAD)BCDAEF13、表達(dá)式a*(b+c)-d的后綴表達(dá)式是：A)abcd*+-B)abc+*d-C)abc*+d-D)-+*abcd14、一個(gè)包含n個(gè)分支結(jié)點(diǎn)(非葉結(jié)點(diǎn))的非空二叉樹，它的葉結(jié)點(diǎn)數(shù)目最多為：A)2n+1B)2n-1C)n-1D)n+115、快速排序最壞情況下的算法時(shí)間復(fù)雜度為：A)O(log2n) B)O(n)C)O(nlog2n)D)O(n2)16.有一個(gè)由4000個(gè)整數(shù)構(gòu)成的順序表，假定表中的元素已經(jīng)按升序排列，采用二分查找定位一個(gè)元素。則最多需要幾次比較就能確定是否存在所查找的元素：A)11次B)12次C)13次D)14次17、排序算法是穩(wěn)定的意思是關(guān)鍵碼相同的記錄排序前后相對位置不發(fā)生改變，下列哪種排序算法是不穩(wěn)定的：A)冒泡排序 B)插入排序 C)歸并排序 D)快速排序18、已知9個(gè)頂點(diǎn)的有向圖，若該圖是強(qiáng)連通的(從所有頂點(diǎn)都存在路徑到達(dá)其他頂點(diǎn))，則該圖中最少有多少條有向邊？A)nB)n+1C)n-1D)n*(n-1)19、全國信息學(xué)奧林匹克的官方網(wǎng)站為參與信息學(xué)競賽的老師同學(xué)們提供相關(guān)的信息和資源，請問全國信息學(xué)奧林匹克官方網(wǎng)站的網(wǎng)址是：A)/ B)/C)/ D)/20、在參加NOI系列競賽過程中，下面哪一種行為是不被嚴(yán)格禁止的：攜帶書寫工具，手表和不具有通訊功能的電子詞典進(jìn)入賽場。在聯(lián)機(jī)測試中通過手工計(jì)算出可能的答案并在程序里直接輸出答案來獲取分?jǐn)?shù)。通過互聯(lián)網(wǎng)搜索取得解題思路。在提交的程序中啟動(dòng)多個(gè)進(jìn)程以提高程序的執(zhí)行效率。二．問題求解（共2題，每空5分，共計(jì)10分）1.小陳現(xiàn)有2個(gè)任務(wù)A,B要完成，每個(gè)任務(wù)分別有若干步驟如下：A=a1->a2->a3,B=b1->b2->b3->b4->b5。在任何時(shí)候，小陳只能專心做某個(gè)任務(wù)的一個(gè)步驟。但是如果愿意，他可以在做完手中任務(wù)的當(dāng)前步驟后，切換至另一個(gè)任務(wù)，從上次此任務(wù)第一個(gè)未做的步驟繼續(xù)。每個(gè)任務(wù)的步驟順序不能打亂，例如……a2->b2->a3->b3……是合法的，而……a2->b3->a3->b2……是不合法的。小陳從B任務(wù)的b1步驟開始做，當(dāng)恰做完某個(gè)任務(wù)的某個(gè)步驟后，就停工回家吃飯了。當(dāng)他回來時(shí)，只記得自己已經(jīng)完成了整個(gè)任務(wù)A，其他的都忘了。試計(jì)算小陳飯前已做的可能的任務(wù)步驟序列共有種。2．有如下的一段程序：a=1;b=a;d=-a;e=a+d;c=2*d;f=b+e-d;g=a*f+c;現(xiàn)在要把這段程序分配到若干臺(tái)（數(shù)量充足）用電纜連接的PC上做并行執(zhí)行。每臺(tái)PC執(zhí)行其中的某幾個(gè)語句，并可隨時(shí)通過電纜與其他PC通訊，交換一些中間結(jié)果。假設(shè)每臺(tái)PC每單位時(shí)間可以執(zhí)行一個(gè)語句，且通訊花費(fèi)的時(shí)間不計(jì)。則這段程序最快可以在單位時(shí)間內(nèi)執(zhí)行完畢。注意：任意中間結(jié)果只有在某臺(tái)PC上已經(jīng)得到，才可以被其他PC引用。例如若語句4和6被分別分配到兩臺(tái)PC上執(zhí)行，則因?yàn)檎Z句6需要引用語句4的計(jì)算結(jié)果,語句6必須在語句4之后執(zhí)行。三．閱讀程序?qū)懡Y(jié)果（共4題,每題8分,共計(jì)32分）1．#include<iostream>usingnamespacestd;inta,b;intwork(inta,intb){if(a%b)returnwork(b,a%b);returnb;intmain(){cin>>a>>b;cout<<work(a,b)<<endl;return0;)輸入：2012輸出： #include<iostream>usingnamespacestd;intmain(){inta[3],b[3];inti,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;return0;輸入：235輸出： #include<iostream>usingnamespacestd;constintc=2009;intmain(){intn,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;return0;}輸入：112輸出： #include<iostream>usingnamespacestd;constintmaxn=50;voidgetnext(charstr[]){intl=strlen(str),i,j,k,temp;k=l-2;while(k>=0&&str[k]>str[k+1])k--;i=k+1;while(i<l&&str[i]>str[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<i;j++)if(str[j]>str[j+1]){temp=str[j];str[j]=str[j+1];str[j+1]=temp;}return;}intmain(){chara[maxn];intn;cin>>a>>n;while(n>0){getnext(a);n--;}cout<<a<<endl;return0;}輸入：NOIP3輸出： 四．完善程序(前8空，每空3分，后2空，每空2分，共28分)1．（最大連續(xù)子段和）給出一個(gè)數(shù)列（元素個(gè)數(shù)不多于100），數(shù)列元素均為負(fù)整數(shù)、正整數(shù)、0。請找出數(shù)列中的一個(gè)連續(xù)子數(shù)列，使得這個(gè)子數(shù)列中包含的所有元素之和最大，在和最大的前提下還要求該子數(shù)列包含的元素個(gè)數(shù)最多，并輸出這個(gè)最大和以及該連續(xù)子數(shù)列中元素的個(gè)數(shù)。例如數(shù)列為4，-5，3，2，4時(shí)，輸出9和3；數(shù)列為123-5078時(shí)，輸出16和7。#include<iostream>usingnamespacestd;inta[101];intn,i,ans,len,tmp,beg;intmain(){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;}elseif(?&&i-beg>len)len=i-beg;TOC\o"1-5"\h\zif(tmp+a[i]③ ){beg二 ④ ；tmp=0;}else ? ；}cout<<ans<<""<<len<<endl;return0;}2.(國王放置)在n*m的棋盤上放置k個(gè)國王，要求k個(gè)國王互相不攻擊，有多少種不同的放置方法。假設(shè)國王放置在第(x,y)格，國王的攻擊的區(qū)域是：(x-1,y-1),(xT,y),(xT,y+1),(x,yT),(x,y+1),(x+1,yT),(x+1,y),(x+1,y+1)。讀入三個(gè)數(shù)n,m,k，輸出答案。題目利用回溯法求解。棋盤行標(biāo)號(hào)為0~n-1,列標(biāo)號(hào)為0~m-1。#include<iostream>usingnamespacestd;intn,m,k,ans;inthash[5][5];voidwork(intx,inty,inttot){inti,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<n)for(j=y-1;j<=y+1;j++)if(j>=0&&j<m) ② ③ ;for(i=x-1;i<=x+1;i++)if(i>=0&&i<n)for(j=y-1;j<=y+1;j++)if(j>=0&&j<m)④ ；y++;if(y==m){x++;y=0;}if(x==n)return;}while(1);}intmain(){cin>>n>>m>>k;ans=0;memset(hash,0,sizeof(hash)); ? ;cout<<ans<<endl;return0;}第十四屆全國青少年信息學(xué)奧林匹克聯(lián)賽初賽試題2008(普及組C++語言二小時(shí)完成)??全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效??一、單項(xiàng)選擇題(共20題，每題1.5分，共計(jì)30分。每題有且僅有一個(gè)正確答案.)。1．微型計(jì)算機(jī)中，控制器的基本功能是()。A.控制機(jī)器各個(gè)部件協(xié)調(diào)工作B.實(shí)現(xiàn)算術(shù)運(yùn)算和邏輯運(yùn)算C.獲取外部信息 D.存放程序和數(shù)據(jù)2.設(shè)人十口6,B二false,C二true,D二false,以下邏輯運(yùn)算表達(dá)式值為真的是()。A.(AAB)V(CADV「A) B.((「AAB)VC)A「DC.(BVCVD)ADAA D.AA(DV「C)AB3.在下列關(guān)于圖靈獎(jiǎng)的說法中,不正確的是()。圖靈獎(jiǎng)是美國計(jì)算機(jī)協(xié)會(huì)于1966年設(shè)立的,專門獎(jiǎng)勵(lì)那些對計(jì)算機(jī)事業(yè)作出重要貢獻(xiàn)的個(gè)人圖靈獎(jiǎng)有“計(jì)算機(jī)界諾貝爾獎(jiǎng)”之稱迄今為止,還沒有華裔計(jì)算機(jī)科學(xué)家獲此殊榮D.圖靈獎(jiǎng)的名稱取自計(jì)算機(jī)科學(xué)的先驅(qū)、英國科學(xué)家阿蘭?圖靈4．計(jì)算機(jī)在工作過程中,若突然停電,( )中的信息不會(huì)丟失。A.ROM和RAMB.CPUC.ROMD.RAM.完全二叉樹共有2*N-1個(gè)結(jié)點(diǎn)，則它的葉節(jié)點(diǎn)數(shù)是()。A.N-1 B.N C.2*ND.2N-1.在以下各項(xiàng)中,()不是操作系統(tǒng)軟件。A.SolarisB.Linux C.WindowsVista D.Sybase.設(shè)棧S的初始狀態(tài)為空，元素a,b,c,d,e,f依次入棧S,出棧的序列為b,d,f,e,c,a,則棧S的容量至少應(yīng)該是()。A.6 B.5 C.4 D.3.與十進(jìn)制數(shù)28.5625相等的四進(jìn)制數(shù)是()。A.123.21B.131.22C.130.22D.130.21.設(shè)字符串5="01丫1^江”，S的非空子串的數(shù)目是()。A.28B.29C.16 D.17.Web2.0是近年來互聯(lián)網(wǎng)的熱門概念之一，其核心思想是互動(dòng)與分享。下列網(wǎng)站中，()是典型的川0匕2.0應(yīng)用。A.Sina B.Flickr C.Yahoo D.Google．遞歸過程或函數(shù)調(diào)用時(shí)，處理參數(shù)和返回地址，通常使用一種稱為()的數(shù)據(jù)結(jié)構(gòu)。A.隊(duì)列 B.多維數(shù)組 C.線性表 D.棧. (2008)10+(5B)16的結(jié)果是()。A.(833)16B.(2089)10 C.(4163)8 D.(100001100011)213.二叉樹「已知其先根遍歷是1243576(數(shù)字為結(jié)點(diǎn)的編號(hào)，以下同)，中根遍歷是2415736，則該二叉樹的后根遍歷是()。A.425763 1 B. 42 75631C.742563 1 D. 42 7653114．將數(shù)組｛8,23, 4, 16,77, -5, 53, 100｝中的元素按從大到小的順序排列，每次可以交換任意兩個(gè)元素，最少需要交換()次。TOC\o"1-5"\h\zA.4 B.5 C.6 D.7．對有序數(shù)組｛5,13,19,21,37,56,64,75,88，92，100｝進(jìn)行二分查找，成功查找元素19的查找長度(比較次數(shù))是( )。A.1 B.2 C.3 D.4.面向?qū)ο蟪绦蛟O(shè)計(jì)(Object-OrientedProgramming)是一種程序設(shè)計(jì)的方法論，它將對象作為程序的基本單元，將數(shù)據(jù)和程序封裝在對象中，以提高軟件的重用性、靈活性和擴(kuò)展性。下面關(guān)于面向?qū)ο蟪绦蛟O(shè)計(jì)的說法中，不正確的是()。A.面向?qū)ο蟪绦蛟O(shè)計(jì)通常采用自頂向下設(shè)計(jì)方法進(jìn)行設(shè)計(jì)。B.面向?qū)ο蟪绦蛟O(shè)計(jì)方法具有繼承性(inheritance)、封裝性(encapsulation)、多態(tài)性(polymorphism)等幾大特點(diǎn)。C.支持面向?qū)ο筇匦缘恼Z言稱為面向?qū)ο蟮木幊陶Z言，目前較為流行的有C++、JAVA、C#等。D.面向?qū)ο蟮某绦蛟O(shè)計(jì)的雛形來自于Simula語言，后來在SmallTalk語言的完善和標(biāo)準(zhǔn)化的過程中得到更多的擴(kuò)展和對以前思想的重新注解。至今，SmallTalk語言仍然被視為面向?qū)ο笳Z言的基礎(chǔ)。.在32*32點(diǎn)陣的“字庫”中，漢字“北”與“京”的字模占用字節(jié)數(shù)之和是( )。A.512 B.256 C.384 D.128.設(shè)T是一棵有n個(gè)頂點(diǎn)的樹，下列說法不正確的是（ ）。A.T有n條邊 B.T是連通的C.T是無環(huán)的 D.T有n-1條邊.下列不屬于NOIP競賽推薦使用的語言環(huán)境的是（）。A.Dev-C++ B.VisualC++ C.freepascal D.Lazarus.在C++程序中，表達(dá)式200|10的值是（）A.20 B.1 C.220 D.202二．問題求解（共2題，每題5分，共計(jì)10分）1.書架上有4本不同的書A、B、C、D。其中A和B是紅皮的，C和D是黑皮的。把這4本書擺在書架上，滿足所有黑皮的書都排在一起的擺法有種。滿足A必須比C靠左，所有紅皮的書要擺放在一起，所有黑皮的書要擺放在一起，共有 種擺法。2．有6個(gè)城市，任何兩個(gè)城市之間都有一條道路連接，6個(gè)城市兩兩之間的距離如下表所示，則城市1到城市6的最短距離為 。城市1城市2城市3城市4城市5城市6城市102311215城市22025312城市3320365城市4153079城市51236702城市615125920三．閱讀程序?qū)懡Y(jié)果(共4題，每題8分，共計(jì)32分)#include<iostream>usingnamespacestd;intmain(){inti,a,b,c,d,f[4];for(i=0;i<4;i++)cin>>f[i];a=f[0]+f[1]+f[2]+f[3];a=a/f[0];b=f[0]+f[2]+f[3];b=b/a;(b*f[1]+a)/f[2];d=f[(b/c)%4];if(f[(a+b+c+d)%4]>f[2])cout<<a+b<<endl;elsecout<<c+d<<endl;return0;}輸入：9192939輸出： 2．#include<iostream>usingnamespacestd;voidfoo(inta,intb,intc){if(a>b)foo(c,a,b);elsecout<<a<<','<<b<<','<<c<<endl;}intmain(){inta,b,c;cin>>a>>b>>c;foo(a,b,c);return0;}輸入:312輸出: 3．#include<iostream>usingnamespacestd;voidfunc(intary[],intn)inti=0,j,x;j=n-1;while(i<j){while(i<j&&ary[i]>0)i++;while(i<j&&ary[j]<0)j--;if(i<j){x=ary[i];ary[i++]=ary[j];ary[j--]=x;}}}intmain(){inta[20],i,m;m=10;for(i=0;i<m;i++){cin>>a[i];}func(a,m);for(i=0;i<m;i++)cout<<a[i]<<"";cout<<endl;return0;}輸入：54-6-116-5922-6110輸出： 4.#include<iostream>#include<cstring>usingnamespacestd;#defineMAX100voidsolve(charfirst[],intspos_f,intepos_f,charmid[],intspos_m,intepos_m){inti,root_m;if(spos_f>epos_f)return;for(i=spos_m;i<=epos_m;i++)if(first[spos_f]==mid[i]){root_m=i;break;}solve(first,spos_f+1,spos_f+(root_m-spos_m),mid,spos_m,root_m-1);solve(first,spos_f+(root_m-spos_m)+1,epos_f,mid,root_m+1,epos_m);cout<<first[spos_f];}intmain(){charfirst[MAX],mid[MAX];intlen;cin>>len;cin>>first>>mid;solve(first,0,len-1,mid,0,len-1);cout<<endl;return0;}輸入：7ABDCEGFBDAGECF輸出： 四．完善程序(前4空，每空2.5分，后6空，每空3分，共28分)1.(字符串替換)給定一個(gè)字符串S(S僅包含大小寫字母)，下面的程序?qū)中的每個(gè)字母用規(guī)定的字母替換，并輸出S經(jīng)過替換后的結(jié)果。程序的輸入是兩個(gè)字符串，第一個(gè)字符串是給定的字符串S,第二個(gè)字符串S'由26個(gè)字母組成，它是a-z的任一排列，大小寫不定，S’規(guī)定了每個(gè)字母對應(yīng)的替換字母：S'中的第一個(gè)字母是字母A和a的替換字母，即S中的A用該字母的大寫替換，S中的a用該字母的小寫替換；S'中的第二個(gè)字母是字母B和b的替換字母，即S中的B用該字母的大寫替換，S中的b用該字母的小寫替換；……以此類推。#include<iostream>#include<string.h>charchange[26],str[5000];usingnamespacestd;voidCheckChangeRule(){inti;for(i=0;i<26;i++){if(?)change[i]-='A'-'a';}}voidChangeString(){inti;for(i=0;i<strlen(str);i++){if(?)str[i]=change[str[i]-'A']-'a'+'A';else}intmain(){inti;cin>>str;cin>>change;CheckChangeRule();?cout<<str<<endl;return0;}(找第k大的數(shù))給定一個(gè)長度為1,000,000的無序正整數(shù)序列,以及另一個(gè)數(shù)n(1<=n<=1000000),然后以類似快速排序的方法找到序列中第n大的數(shù)(關(guān)于第n大的數(shù)：例如序列{1，2，3，4，5，6}中第3大的數(shù)是4)。#include<iostream>usingnamespacestd;inta[1000001],n,ans=-1;voidswap(int&a,int&b){intc;c=a;a=b;b=c;}intFindKth(intleft,intright,intn){inttmp,value,i,j;if(left==right)returnleft;tmp=rand()%(right-left)+left;swap(a[tmp],a[left]);value= ? i=left;j=right;while(i<j){while(i<j&&?)j--;if(i<j){a[i]=a[j];i++;}elsebreak;while(i<j&&?)i++;if(i<j){a[j]=a[i];j--;}elsebreak;}④if(i<n)returnFindKth(?);if(i>n)return ? returni;}intmain(){inti;intm=1000000;for(i=1;i<=m;i++)cin>>a[i];cin>>n;ans=FindKth(1,m,n);cout<<a[ans];return0;}第十三屆全國青少年信息學(xué)奧林匹克聯(lián)賽初賽試題2007

(普及組C++語言二小時(shí)完成)??全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效??一、單項(xiàng)選擇題(共20題，每題1.5分，共計(jì)30分。每題有且僅有一個(gè)正確答案.)。.在以下各項(xiàng)中，()不是CPU的組成部分。A.控制器B.運(yùn)算器C.寄存器D.主板2．在關(guān)系數(shù)據(jù)庫中，存放在數(shù)據(jù)庫中的數(shù)據(jù)的邏輯結(jié)構(gòu)以（）為主。A.二叉樹B.多叉樹C.哈希表D.二維表3．在下列各項(xiàng)中，只有（）不是計(jì)算機(jī)存儲(chǔ)容量的常用單位。A.ByteB.KBC.UBD.TB4．ASCII碼的含義是（）。A.二一十進(jìn)制轉(zhuǎn)換碼B.美國信息交換標(biāo)準(zhǔn)代碼C.數(shù)字的二進(jìn)制編碼D.計(jì)算機(jī)可處理字符的唯一編碼.一個(gè)完整的計(jì)算機(jī)系統(tǒng)應(yīng)包括（）。A.系統(tǒng)硬件和系統(tǒng)軟件B.硬件系統(tǒng)和軟件系統(tǒng)C.主機(jī)和外部設(shè)備D.主機(jī)、鍵盤、顯示器和輔助存儲(chǔ)器.IT的含義是（）。A.通信技術(shù)B.信息技術(shù)C.網(wǎng)絡(luò)技術(shù)D.信息學(xué)7．LAN的含義是（）。A.因特網(wǎng)B.局域網(wǎng)C.廣域網(wǎng)D.城域網(wǎng)8.冗余數(shù)據(jù)是指可以由其他數(shù)據(jù)導(dǎo)出的數(shù)據(jù)，例如，數(shù)據(jù)庫中已存放了學(xué)生的數(shù)學(xué)、語文和英語的三科成績，如果還存放三科成績的總分，則總分就可以看作冗余數(shù)據(jù)。冗余數(shù)據(jù)往往會(huì)造成數(shù)據(jù)的不一致，例如，上面4個(gè)數(shù)據(jù)如果都是輸入的，由于操作錯(cuò)誤使總分不等于三科成績之和，就會(huì)產(chǎn)生矛盾。下面關(guān)于冗余數(shù)據(jù)的說法中，正確的是（）。.應(yīng)該在數(shù)據(jù)庫中消除一切冗余數(shù)據(jù).用高級語言編寫的數(shù)據(jù)處理系統(tǒng)，通常比用關(guān)系數(shù)據(jù)庫編寫的系統(tǒng)更容易消除冗余數(shù)據(jù)C.為了提高查詢效率，在數(shù)據(jù)庫中可以適當(dāng)保留一些冗余數(shù)據(jù)，但更新時(shí)要做相容性檢驗(yàn)D.做相容性檢驗(yàn)會(huì)降低效率，可以不理睬數(shù)據(jù)庫中的冗余數(shù)據(jù).在下列各軟件中，不屬于NOIP競賽（復(fù)賽）推薦使用的語言環(huán)境有（）。A.gccB.g++C.TurboCD.freepascal以下斷電之后仍能保存數(shù)據(jù)的有（）。A.硬盤B.高速緩存C.顯存D.RAM在下列關(guān)于計(jì)算機(jī)語言的說法中，正確的有（）。高級語言比匯編語言更高級，是因?yàn)樗某绦虻倪\(yùn)行效率更高B.隨著Pascal、C等高級語言的出現(xiàn)，機(jī)器語言和匯編語言已經(jīng)退出了歷史舞臺(tái)高級語言程序比匯編語言程序更容易從一種計(jì)算機(jī)移植到另一種計(jì)算機(jī)上C是一種面向?qū)ο蟮母呒売?jì)算機(jī)語言近20年來，許多計(jì)算機(jī)專家都大力推崇遞歸算法，認(rèn)為它是解決較復(fù)雜問題的強(qiáng)有力的工具。在下列關(guān)于遞歸算法的說法中，正確的是（）。A.在1977年前后形成標(biāo)準(zhǔn)的計(jì)算機(jī)高級語言“FORTRAN77”禁止在程序使用遞歸，原因之一是該方法可能會(huì)占用更多的內(nèi)存空間和非遞歸算法相比，解決同一個(gè)問題，遞歸算法一般運(yùn)行得更快一些對于較復(fù)雜的問題，用遞歸方式編程一般比非遞歸方式更難一些D.對于已經(jīng)定義好的標(biāo)準(zhǔn)數(shù)學(xué)函數(shù)sin(x),應(yīng)用程序中的語句“y=sin(sin(x))；”就是一種遞歸調(diào)用.一個(gè)無法靠自身的控制終止的循環(huán)稱為“死循環(huán)”，例如，在C++語言程序中，語句“while(1)printf(“*")；”就是一個(gè)死循環(huán)，運(yùn)行時(shí)它將無休止地打印*號(hào)。下面關(guān)于死循環(huán)的說法中，只有()是正確的。A.不存在一種算法，對任何一個(gè)程序及相應(yīng)的輸入數(shù)據(jù)，都可以判斷是否會(huì)出現(xiàn)死循環(huán)，因而，任何編譯系統(tǒng)都不做死循環(huán)檢驗(yàn)B.有些編譯系統(tǒng)可以檢測出死循環(huán)C.死循環(huán)屬于語法錯(cuò)誤，既然編譯系統(tǒng)能檢查各種語法錯(cuò)誤，當(dāng)然也應(yīng)該能檢查出死循環(huán)D.死循環(huán)與多進(jìn)程中出現(xiàn)的“死鎖”差不多，而死鎖是可以檢測的，因而，死循環(huán)也可以檢測的.在C++程序中，表達(dá)式23|2八5的值是()A.23B.1C.32D.18.在C++程序中，判斷a等于0或b等于0或c等于0的正確的條件表達(dá)式是()!((a!=0)||(b!=0)||(c!=0))!((a!=0)&&(b!=0)&&(c!=0))!(a==0&&b==0)||(c!=0)(a=0)&&(b=0)&&(c=0)地面上有標(biāo)號(hào)為A、B、C的3根細(xì)柱，在A柱上放有10個(gè)直徑相同中間有孔的圓盤，從上到下依次編號(hào)為1,2,3,……，將A柱上的部分盤子經(jīng)過B柱移入C柱，也可以在B柱上暫存。如果B柱上的操作記錄為：“進(jìn)，進(jìn)，出，進(jìn)，進(jìn)，出，出，進(jìn)，進(jìn)，出，進(jìn)，出，出”。那么，在C柱上，從下到上的盤子的編號(hào)為()。A.243657 B.241257C.243176 D.243675與十進(jìn)制數(shù)1770對應(yīng)的八進(jìn)制數(shù)是()。A.3350B.3351C.3352D.3540設(shè)A=B=true,C=D=false,以下邏輯運(yùn)算表達(dá)式值為假的有()。A.(-AAB)V(CADVA)B.-(((AAB)VC)AD)C.AA(BVCVD)VDD.(AA(DVC))AB(2070)16+(34)8的結(jié)果是()。A.(8332)10B.(208A)16C.(100000000110)2D.(20212)8已知7個(gè)結(jié)點(diǎn)的二叉樹的先根遍歷是1245637(數(shù)字為結(jié)點(diǎn)的編號(hào),以下同),中根遍歷是4265173,則該二叉樹的后根遍歷是()A.4652731B.4652137C.4231547D.4653172二．問題求解(共2題,每題5分,共計(jì)10分)1.(子集劃分)將n個(gè)數(shù){1,2,…，n}劃分成r個(gè)子集。每個(gè)數(shù)都恰好屬于一個(gè)子集，任何兩個(gè)不同的子集沒有共同的數(shù)，也沒有空集。將不同劃分方法的總數(shù)記為S(n,r)。例如，S(4,2)=7,這7種不同的劃分方法依次為{(1),(234)},{(2),(134)},{(3),(124)},{(4),(123)},{(12),(34)},{(13),(24)},{(14),(23)}。當(dāng)n=6,r=3時(shí)，S(6,3)二（提示：先固定一個(gè)數(shù)，對于其余的5個(gè)數(shù)考慮S（5,3）與S（5,2）,再分這兩種情況對原固定的數(shù)進(jìn)行分析）。2．（最短路線）某城市的街道是一個(gè)很規(guī)整的矩形網(wǎng)格（見下圖），有7條南北向的縱街，5條東西向的橫街?，F(xiàn)要從西南角的A走到東北角的B，最短的走法共有多少種？A三．閱讀程序?qū)懡Y(jié)果(共4題，每題8分，共計(jì)32分)1.#include<iostream.h>voidmain(){inti,p[5],a,b,c,x,y=20;for(i=0;i<=4;i++)cin>>p[i];a=(p[0]+p[1])+(p[2]+p[3]+p[4])/7;b=p[0]+p[1]/((p[2]+p[3])/p[4]);c=p[0]*p[1]/p[2];x=a+b-p[(p[3]+3)%4];if(x>10)y+=(b*100-a)/(p[p[4]%3]*5);elsey+=20+(b*100-c)/(p[p[4]%3]*5);cout<<x<<","<<y<<endl;}//注：本例中，給定的輸入數(shù)據(jù)可以避免分母為0或數(shù)組元素下標(biāo)越界。輸入：66553輸出： 2．#include<iostream.h>voidfun(int*a,int*b){int*k;k=a;a=b;b=k;}voidmain(){inta=3,b=6,*x=&a,*y=&b;fun(x,y);cout<<a<<","<<b<<endl;}輸出: 3．#include<iostream.h>#include<iomanip.h>#include"math.h"voidmain(){inta1[51]={0};inti,j,t,t2,n=50;for(i=2;i<=sqrt(n);i++)if(a1[i]==0){t2=n/i;for(j=2;j<=t2;j++)a1[i*j]=1;}t=0;for(i=2;i<=n;i++)if(a1[i]==0){cout<<setw(4)<<i;t++;if(t%10==0)cout<<endl;}cout<<endl;}輸出： 4.#include<iostream.h>#include"ctype.h"voidexpand(chars1[],chars2[]){inti,j,a,b,c;j=0;for(i=0;(c=s1[i])!='\0';i++)if(c=='-'){a=s1[i-1];b=s1[i+1];if(isalpha(a)&&isalpha(b)||isdigit(a)&&isdigit(b))〃函數(shù)isalpha(a)用于判斷字符a是否為字母，isdigit(b)用于判斷字符b是否為數(shù)//字，如果是，返回1，否則返回0{j--;dos2[j++]=a++;while(tolower(a)<tolower(s1[i+1]));}elses2[j++]=c;}elses2[j++]=c;s2[j]='\0';}voidmain(){chars1[100],s2[300];cin>>s1;expand(s1,s2);cout<<s2<<endl;}輸入：wer2345d-h454-82qqq輸出： 四．完善程序(前4空，每空2.5分，后6空，每空3分，共28分)1．(求字符串的逆序)下面的程序的功能是輸入若干行字符串，每輸入一行，就按逆序輸出該行，最后鍵入-1終止程序。請將程序補(bǔ)充完整。#include<iostream.h>#include<string.h>intmaxline=200,kz;intreverse(chars[]){inti,j,t;for(i=0,j=strlen(s)-1;i<j;①，②){t=s[i];s[i]=s[j];s[j]=t;}return0;}voidmain(){charline[100];cout<<"continue?-1forend."<<endl;cin>>kz;while(③){cin>>line;④;cout<<line<<endl;cout<<"continue?-1forend."<<endl;cin>>kz;}}2.(棋盤覆蓋問題)在一個(gè)2kX2k個(gè)方格組成的棋盤中恰有一個(gè)方格與其他方格不同(圖中標(biāo)記為-1的方格)，稱之為特殊方格?，F(xiàn)用L型(占3個(gè)小格)紙片覆蓋棋盤上除特殊方格的所有部分，各紙片不得重疊，于是，用到的紙片數(shù)恰好是(4k-1)/3。在下表給出的一個(gè)覆蓋方案中，k=2,相同的3個(gè)數(shù)字構(gòu)成一個(gè)紙片。下面給出的程序是用分治法設(shè)計(jì)的，將棋盤一分為四，依次處理左上角、右上角、左下角、右下角，遞歸進(jìn)行。請將程序補(bǔ)充完整。22332-1134115#include<iostream.h>#include<iomanip.h>intboard[65][65],tile;//tile為紙片編號(hào)voidchessboard(inttr,inttc,intdr,intdc,intsize)//dr,dc依次為特殊方格的行、列號(hào){intt,s;if(size==1);t=tile++;s=size/2;if(⑥)chessboard(tr,tc,dr,dc,s);else{board[tr+s-1][tc+s-1]=t;;}if(dr<tr+s&&dc>=tc+s)chessboard(tr,tc+s,dr,dc,s);else{board[tr+s-1][tc+s]=t;;}if(dr>=tr+s&&dc<tc+s)chessboard(tr+s,tc,dr,dc,s);else{board[tr+s][tc+s-1]=t;;}if(dr>=tr+s&&dc>=tc+s)chessboard(tr+s,tc+s,dr,dc,s);else{board[tr+s][tc+s]=t;;}}voidprt1(intb[][65],intn){inti,j;for(i=1;i<=n;i++){for（j=1;j<=n;j++）cout<<setw（3）<<b[i][j];cout<<endl;;}}voidmain（）{intsize,dr,dc;cout<<"inputsize（4/8/16/64）:"<<endl;cin>>size;cout<<"inputthepositionofspecialblock（x,y）:"<<endl;cin>>dr>>dc;board[dr][dc]=-1;tile++;chessboard（1,1,dr,dc,size）;prt1（board,size）;}第十二屆全國青少年信息學(xué)奧林匹克聯(lián)賽初賽試題2006（普及組C++語言二小時(shí)完成）??全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效??一、單項(xiàng)選擇題（共20題，每題1.5分，共計(jì)30分。每題有且僅有一個(gè)正確答案.）在下面各世界頂級的獎(jiǎng)項(xiàng)中，為計(jì)算機(jī)科學(xué)與技術(shù)領(lǐng)域做出杰出貢獻(xiàn)的科學(xué)家設(shè)立的獎(jiǎng)項(xiàng)是（）。A.沃爾夫獎(jiǎng)B.諾貝爾獎(jiǎng)C.菲爾茲獎(jiǎng)D.圖靈獎(jiǎng)2.在下列各軟件中，不屬于NOIP競賽（復(fù)賽）推薦使用的語言環(huán)境有（）。A.gcc/g++B.TurboPascalC.RHIDED.freepascal以下斷電之后仍能保存數(shù)據(jù)的有（）。A.寄存器B.ROMC.RAMD.高速緩存Linux是一種（）。A.繪圖軟件B.程序設(shè)計(jì)語言C.操作系統(tǒng)D.網(wǎng)絡(luò)瀏覽器CPU是（）的簡稱。A.硬盤B.中央處理器C.高級程序語言D.核心寄存器在計(jì)算機(jī)中，防火墻的作用是（）。A.防止火災(zāi)蔓延B.防止網(wǎng)絡(luò)攻擊C.防止計(jì)算機(jī)死機(jī)D.防止使用者誤刪除數(shù)據(jù)在下列關(guān)于計(jì)算機(jī)語言的說法中，不正確的是（）。Pascal和C都是編譯執(zhí)行的高級語言高級語言程序比匯編語言程序更容易從一種計(jì)算機(jī)移植到另一種計(jì)算機(jī)上C++是歷史上的第一個(gè)支持面向?qū)ο蟮挠?jì)算機(jī)語言D.與匯編語言相比，高級語言程序更容易閱讀.在下列關(guān)于計(jì)算機(jī)算法的說法中，不正確的是()。A.一個(gè)正確的算法至少要有一個(gè)輸入B.算法的改進(jìn)，在很大程度上推動(dòng)了計(jì)算機(jī)科學(xué)與技術(shù)的進(jìn)步C.判斷一個(gè)算法的好壞的主要標(biāo)準(zhǔn)是算法的時(shí)間復(fù)雜性與空間復(fù)雜性D.目前仍然存在許多涉及到國計(jì)民生的重大課題，還沒有找到能夠在計(jì)算機(jī)上實(shí)施的有效算法.在下列各種排序算法中，不是以“比較”作為主要操作的算法是()。A.選擇排序B.冒泡排序C.插入排序D.基數(shù)排序.在編程時(shí)(使用任一種高級語言，不一定是C++),如果需要從磁盤文件中輸入一個(gè)很大的二維數(shù)組(例如1000*1000的double型數(shù)組)，按行讀(即外層循環(huán)是關(guān)于行的)與按列讀(即外層循環(huán)是關(guān)于列的)相比，在輸入效率上()。A.沒有區(qū)別B.按行讀的方式要高一些C.按列讀的方式要高一些D.取決于數(shù)組的存儲(chǔ)方式。.在C++中，表達(dá)式2廠2的值是()A.441B.42C.23D.24.在C++中，判斷a不等于0且b不等于0的正確的條件表達(dá)式是()A.!a==0||!b==0B.!((a==0)&&(b==0))C.!(a==0&&b==0)D.a&&b.某個(gè)車站呈狹長形，寬度只能容下一臺(tái)車，并且只有一個(gè)出入口。已知某時(shí)刻該車站狀態(tài)為空，從這一時(shí)刻開始的出入記錄為：“進(jìn)，出，進(jìn)，進(jìn)，進(jìn)，出，出，進(jìn)，進(jìn)，進(jìn)，出，出”。假設(shè)車輛入站的順序?yàn)?，2,3,……，則車輛出站的順序?yàn)?)。A.1,2,3,4,5B.1,2,4,5,7C.1,4,3,7,6D.1,4,3,7,2.高度為n的均衡的二叉樹是指：如果去掉葉結(jié)點(diǎn)及相應(yīng)的樹枝，它應(yīng)該是高度為n-1的滿二叉樹。在這里，樹高等于葉結(jié)點(diǎn)的最大深度，根結(jié)點(diǎn)的深度為0,如果某個(gè)均衡的二叉樹共有2381個(gè)結(jié)點(diǎn)，則該樹的樹高為()。A.10B.11C.12D.13.與十進(jìn)制數(shù)1770對應(yīng)的八進(jìn)制數(shù)是()。A.3350B.3351C.3352D.3540.將5個(gè)數(shù)的序列排序，不論原先的順序如何，最少都可以通過()次比較，完成從小到大的排序。A.6B.7C.8D.9.設(shè)A=B=D=true,C=false,以下邏輯運(yùn)算表達(dá)式值為真的有()。A.(AAB)V(CAD)B.((AVBVD)AC)C.AA(BVCVD)D.(AABAC)VD.(2010)+(32)的結(jié)果是()。A.(8234) B.(202B) C.(20056) D.(100000000110)16101619.設(shè)棧S的初始狀態(tài)為空，元素a,b,c,d,e依次入棧，以下出棧序列不可能出現(xiàn)的有()。A.a,b,c,e,d B.b,c,a,e,dC.a,e,c,b,d D.d,c,e,b,a20.已知6個(gè)結(jié)點(diǎn)的二叉樹的先根遍歷是123456(數(shù)字為結(jié)點(diǎn)的編號(hào)，以下同)，后根遍歷是325641，則該二叉樹的可能的中根遍歷是()A.321465B.321546C.213546D.231465二．問題求解(共2題，每題5分，共計(jì)10分)1．(尋找假幣)現(xiàn)有80枚硬幣，其中有一枚是假幣，其重量稍輕，所有真幣的重量都相同，如果使用不帶砝碼的天平稱重，最少需要稱幾次，就可以找出假幣？你還要指出第1次的稱重方法。請寫出你的結(jié)果： 。2．(取石子游戲)現(xiàn)有5堆石子,石子數(shù)依次為3，5，7，19，50，甲乙兩人輪流從任一堆中任取(每次只能取自一堆，不能不取),取最后一顆石子的一方獲勝。甲先取，問甲有沒有獲勝策略(即無論乙怎樣取，甲只要不失誤，都能獲勝)？如果有，甲第一步應(yīng)該在哪一堆里取多少？請寫出你的結(jié)果： 。三．閱讀程序?qū)懡Y(jié)果(共4題，每題8分，共計(jì)32分)#include<iostream.h>voidmain(){inti,u[4],a,b,x,y=10;for(i=0;i<=3;i++)cin>>u[i];a=(u[0]+u[1]+u[2]+u[3])/7;b=u[0]/((u[1]-u[2])/u[3]);x=(u[0]+a+2)-u[(u[3]+3)%4];if(x>10)y+=(b*100-u[3])/(u[u[0]%3]*5);elsey+=20+(b*100-u[3])/(u[u[0]%3]*5);cout<<x<<","<<y<<endl;}//注：本例中，給定的輸入數(shù)據(jù)可以避免分母為0或下標(biāo)越界。輸入：9394輸出： #include<iostream.h>voidmain(){inti,j,m[]={2,3,5,7,13};longt;for(i=0;i<=4;i++){t=1;for(j=1;j<m[i];j++)t*=2;cout<<(t*2-1)*t<<"";}cout<<endl;}輸出: #include"iostream.h"#defineN7intfun(chars[],chara,intn){intj;j=n;while(a<s[j]&&j>0)j--;returnj;}voidmain(){chars[N+1];intk;for(k=1;k<=N;k++)s[k]='A'+2*k+1;cout<<fun(s,'M',N)<<endl;}輸出： #include<iostream.h>#include<iomanip.h>voiddigit(longn,longm){if(m>0)cout<<setw(2)<<n%10;if(m>1)digit(n/10,m/10);cout<<setw(2)<<n%10;}voidmain(){longx,x2;cout<<"Inputanumber:"<<endl;cin>>x;x2=1;while(x2<x)x2*=10;x2/=10;digit(x,x2);cout<<endl;}輸入：9734526輸出： 四．完善程序(前4空，每空2.5分，后6空，每空3分，共28分)1.(全排列)下面程序的功能是利用遞歸方法生成從1到n(n<10)的9個(gè)數(shù)的全部可能的排列(不一定按升序輸出)。例如，輸入3，則應(yīng)該輸出(每行輸出5個(gè)排列)：123132213231321312程序：#include<iostream.h>#include<iomanip.h>intn,a[10];//a[1],a[2],…,a[n]構(gòu)成n個(gè)數(shù)的一個(gè)排列l(wèi)ongcount=0;//變量count記錄不同排列的個(gè)數(shù)，這里用于控制換行voidperm(intk){intj,p,t;if(①){count++;for(p=1;p<=n;p++)cout<<setw(1)<<a[p];cout<<"";if(②)cout<<endl;return;}for(j=k;j<=n;j++){t=a[k];a[k]=a[j];a[j]=t;③;t=a[k];④;}}voidmain(){inti;cout<<"Entryn:"<<endl;cin>>n;for(i=1;i<=n;i++)a[i]=i;⑤;}2.由鍵盤輸入一個(gè)奇數(shù)P(P<100,000,000),其個(gè)位數(shù)字不是5,求一個(gè)整數(shù)S,使PXS=1111...1(在給定的條件下，解S必存在)。要求在屏幕上依次輸出以下結(jié)果:(1)S的全部數(shù)字。除最后一行外,每行輸出50位數(shù)字。(2)乘積的數(shù)字位數(shù)。例1：輸入p=13，由于13*8547=111111,則應(yīng)輸出(1)8547,(2)6例2：輸入p=147,則輸出結(jié)果應(yīng)為(1)755857898715041572184429327286470143613(2)42，即等式的右端有42個(gè)1。程序：#include<iostream.h>#include<iomanip.h>voidmain(){longp,a,b,c,t,n;while(1){cout<<"輸入p,最后一位為1或3或7或9:"<<endl;cin>>p;if((p%2!=0)&&(p%5!=0))//如果輸入的數(shù)符合要求，結(jié)束循環(huán)⑥;}a=0;n=0;while(a<p){a=a*10+1;n++;//變量a存放部分右端項(xiàng)，n為右端項(xiàng)的位數(shù)}t=0;do{b=a/p;cout<<setw(1)<<b;t++;if(⑦)cout<<endl;c=⑧;a=⑨;n++;}while(c>0);cout<<endl<<"n="<<⑩<<endl;}第十一屆全國青少年信息學(xué)奧林匹克聯(lián)賽初賽試題2005(普及組C語言二小時(shí)完成)??全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效??一.選擇一個(gè)正確答案代碼(A/B/C/D/E)，填入每題的括號(hào)內(nèi)(每題1.5分，共30分).在字符串“ababacbabcbdecced”中出現(xiàn)次數(shù)最多的字母出現(xiàn)了()次。A.6B.5C.4D.3E.2.設(shè)全集I={a,b,c,d,e,f,g,h}集合A={a,b,c,d,e,f}B={c,d,e},C={a,d},那么集合AnBn?C為()。A.{c,e}B.{d,e}C.{e}D.{c,d,e}E.{d,f}.和十進(jìn)制數(shù)23的值相等的二進(jìn)制數(shù)是()。A.10110B.11011C.11011D.10111E.10011.完全二叉樹的結(jié)點(diǎn)個(gè)數(shù)為11，則它的葉結(jié)點(diǎn)個(gè)數(shù)為()。A.4B.3C.5D.2E.65.平面上有五個(gè)點(diǎn)A(5,3),B⑶5),C(2,1),D(3,3),E(5,1)。以這五點(diǎn)作為完全圖G的頂點(diǎn)，每兩點(diǎn)之間的直線距離是圖G中對應(yīng)邊的權(quán)值。以下哪條邊不是圖G的最小生成樹中的邊()。A.ADB.BDC.CDD.DEE.EAIntel的首顆16位處理器是()。A.8088B.80386C.80486D.8086E.Pentium處理器A每秒處理的指令數(shù)是處理器B的2倍。某一特定程序P分別編譯為處理器人和處理器B的指令，編譯結(jié)果處理器A的指令數(shù)是處理器B的4倍。已知程序P在處理器A上執(zhí)行需要1個(gè)小時(shí)，那么在輸入相同的情況下，程序P在處理器B上執(zhí)行需要()小時(shí)。A.4B.2C.1D.1/2E.1/4以下哪個(gè)不是計(jì)算機(jī)的輸出設(shè)備()。A.音箱B.顯示器C.打印機(jī)D.掃描儀E.繪圖儀下列活動(dòng)中不屬于信息學(xué)奧賽的系列活動(dòng)的是()。A.NOIPB.NOIC.IOID.冬令營E.程序員等級考試以下斷電之后仍能保存數(shù)據(jù)的是()。A.硬盤B.寄存器C.顯存D.內(nèi)存E.高速緩存以下哪個(gè)軟件不是即時(shí)通信軟件()。A.網(wǎng)易泡泡B.MSNMessengerC.GoogleTalkD.3DSMaxE.QQ下列關(guān)于高級語言的說法錯(cuò)誤的是()。Fortran是歷史上的第一個(gè)面向科學(xué)計(jì)算的高級語言Pascal和C都是編譯執(zhí)行的高級語言C++是歷史上的第一個(gè)支持面向?qū)ο蟮恼Z言編譯器將高級語言程序轉(zhuǎn)變?yōu)槟繕?biāo)代碼高級語言程序比匯編語言程序更容易從一種計(jì)算機(jī)移植到另一種計(jì)算機(jī)上下列設(shè)備不具有計(jì)算功能的是()。A.筆記本電腦B.掌上電腦C.智能手機(jī)D.電子計(jì)算器E.液晶顯示器常見的郵件傳輸服務(wù)器使用()協(xié)議接收郵件。A.HTTPB.SMTPC.TCPD.FTPE.POP3下列瀏覽器中，由微軟公司開發(fā)的瀏覽器是()。A.InternetExploreB.NetscapeC.OperaD.FirefoxE.Mozilla一位藝術(shù)史學(xué)家有20000幅真彩色圖像，每幅圖像約占3M空間。如果將這些圖像以位圖形式保存在CD光盤上(一張CD光盤的容量按600M計(jì)算)，大約需要()張CD光盤。A.1B.10C.100D.1000E.10000設(shè)A=true，B=false，C=false，D=true，以下邏輯運(yùn)算表達(dá)式值為真的是()。A.(AAB)V(CAD)B.((AAB)VC)ADC.AA((BVC)AD)D.(AA(BVC))VDE.(AVB)A(CAD).(3725)8+(B)16的運(yùn)算結(jié)果是()。A.(3736)8B.(2016)10C.(1111110000)2D.(3006)10E.(7B0)16.二叉樹T的寬度優(yōu)先遍歷序列為ABCDEFGH1,已知人是C的父結(jié)點(diǎn)，D是G的父結(jié)點(diǎn)，F(xiàn)是I的父結(jié)點(diǎn)，樹中所有結(jié)點(diǎn)的最大深度為3(根結(jié)點(diǎn)深度設(shè)為0)，可知F的父結(jié)點(diǎn)是()。A.無法確定B.BC.CD.DE.E.設(shè)棧S的初始狀態(tài)為空，元素a,b,c,d,e,f,g依次入棧，以下出棧序列不可能出現(xiàn)的是()。A. a,b,c,e, d, f,gB. b, c,a,f, e,g,dC.a,e,d,c,b,f,gD. d,c,f,e, b, a,gE. g, e,f,d, c,b,a二．問題求解(請?jiān)诳崭裉幪钌洗鸢?，每?分，共10分)1. 將數(shù)組{32, 74, 25,53, 28, 43,86, 47}中的元素按從小到大的順序排列，每次可以交換任意兩個(gè)元素，最少需要交換次。2.有3個(gè)課外小組：物理組，化學(xué)組和生物組。今有張、王、李、趙、陳5名同學(xué)，已知張、王為物理組成員，張、李、趙為化學(xué)組成員，李、趙、陳為生物組成員。如果要在3個(gè)小組中分別選出3位組長，一位同學(xué)最多只能擔(dān)任一個(gè)小組的組長，共有一種選擇方案。三．閱讀程序(共4題，每題8分，共計(jì)32分)#include<stdio.h>intmain(){inta,b;TOC\o"1-5"\h\zscanf(“%d”,&a);b=(a*(a*a))+1;if (b%3 == 0) b = b / 3;if (b%5 == 0) b = b / 5;if (b%7 == 0) b = b / 7;if (b%9 == 0) b = b / 9;if (b%11 == 0) b = b / 11;if (b%13 == 0) b = b / 13;if (b%15 == 0) b = b / 15;printf(“％d \n” , (100 *a-b)/2);return0;}輸入：10輸出： #include<stdio.h>intmain(){charstr[20]=“Today-is-terrible!”;inti;for(i=6;i<=10;i++)if(str[i]=='—')str[i-1]='x'；for(i=12;i>=0;i--)if(str[i]==‘t’)str[i+1]=‘e’;printf(“%s\n”,str);return0;}輸出： #include<stdio.h>intmain(){inta,b,c,p,q,r[3];scanf(“%d%d%d”,&a,&b,&c);p=a/b/c;q=b—c+a+p;r[0]=a*p/q*q;r[1]=r[0]*(r[0]-300);if(3*q—p%3<=r[0]&&r[2]==r[2])r[1]=r[r[0]/p%2];elser[1]=q%p;printf(“％d\n”，r[0]-r[1]);return0;}輸入：10073輸出： #include<stdio.h>#include<string.h>intmain(){charstr[60];intlen,i,j,chr[26];charmmin='z';scanf("%s",str);len=strlen(str);for(i=len-1;i>=1;i--)if(str[i-1]<str[i])break;if(i==0){printf("Noresult!\n");return0;}for(j=0;j<i-1;j++)putchar(str[j]);memset(chr,0,sizeof(chr));for(j=i;j<len;j++){if(str[j]>str[i-1]&&str[j]<mmin)mmin=str[j];chr[str[j]-'a']++;}chr[mmin-'a']--;chr[str[i-1]-'a']++;putchar(mmin);for(i=0;i<26;i++)for(j=0;j<chr[i];j++)putchar(i+'a');putchar('\n');return0;}輸入：zzyzcccbbbaaa輸出： 四.完善程序(前4空，每空2分，后5空，每空4分，共28分)1．判斷質(zhì)數(shù)題目描述:給出一個(gè)正整數(shù)，判斷這個(gè)數(shù)是否是質(zhì)數(shù)。輸入:一個(gè)正整數(shù)n(1WnW10000)。輸出:如果n是質(zhì)數(shù)，輸出"YES”；否則，輸出"NO”。輸入樣例:10輸出樣例:NO程序：#include<stdio.h>intmain(){int①;scanf("%d",&n);if(n==2)puts(②);elseif(③||n%2==0)puts("NO");else{i=3;while(i*i<=n){if(④){puts("NO");return0;}i=i+2;}puts("YES");}return0;}2．木材加工題目描述:木材廠有一些原木，現(xiàn)在想把這些木頭切割成一些長度相同的小段木頭，需要得到的小段的數(shù)目是給定的。當(dāng)然，我們希望得到的小段越長越好，你的任務(wù)是計(jì)算能夠得到的小段木頭的最大長度。木頭長度的單位是cm。原木的長度都是正整數(shù)，我們要求切割得到的小段木頭的長度也是正整數(shù)。輸入:第一行是兩個(gè)正整數(shù)N和K(1WNW10000,1WKW10000),N是原木的數(shù)目，K是需要得到的小段的數(shù)目。接下來的N行，每行有一個(gè)1到10000之間的正整數(shù)，表示一根原木的長度。輸出:輸出能夠切割得到的小段的最大長度。如果連1cm長的小段都切不出來，輸出"0”。輸入樣例:37232124456輸出樣例:114程序：#include<stdio.h>intn,k,len[10000];intisok(intt){intnum=0,i;for(i=0;i<n;i++){if(num>=k)break;num=(1);}if(②)return1;elsereturn0;}intmain(){inti,left,right,mid;scanf("%d%d",&n,&k);right=0;for(i=0;i<n;i++){scanf("%d",&(len[i]));if(right<len[i])right=len[i];}right++;③;while(C￡)<right){mid=(left+right)/2;if( ⑤ )right=mid;elseleft=mid;}printf("%d\n",left);return0;}第十屆全國青少年信息學(xué)奧林匹克聯(lián)賽初賽試題2004(普及組C語言二小時(shí)完成)??全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效??一.選擇一個(gè)正確答案代碼(A/B/C/D/E)，填入每題的括號(hào)內(nèi)(每題1.5分，共30分).美籍匈牙利數(shù)學(xué)家馮?諾依曼對計(jì)算機(jī)科學(xué)發(fā)展所做出的貢獻(xiàn)是()。提出理想計(jì)算機(jī)的數(shù)學(xué)模型，成為計(jì)算機(jī)科學(xué)的理論基礎(chǔ)。是世界上第一個(gè)編寫計(jì)算機(jī)程序的人。C.提出存儲(chǔ)程序工作原理，并設(shè)計(jì)出第一臺(tái)具有存儲(chǔ)程序功能的計(jì)算機(jī)EDVAC。采用集成電路作為計(jì)算機(jī)的主要功能部件。指出計(jì)算機(jī)性能將以每兩年翻一番的速度向前發(fā)展。.下列哪個(gè)不是CPU(中央處理單元)()。A.IntelItaniumB.DDRSDRAMC.AMDAthlon64D.AMDOpteronE.IBMPower5.下列網(wǎng)絡(luò)上常用的名字縮寫對應(yīng)的中文解釋錯(cuò)誤的是()。WWW(WorldWideWeb):萬維網(wǎng)。URL(UniformResourceLocator):統(tǒng)一資源定位器。HTTP(HypertextTransferProtocol):超文本傳輸協(xié)議。FTP(FileTransferProtocol):快速傳輸協(xié)議。TCP(TransferControlProtocol):傳輸控制協(xié)議。.下面哪個(gè)部件對于個(gè)人桌面電腦的正常運(yùn)行不是必需的()。A.CPUB.圖形卡(顯卡) C.光驅(qū)D.主板E.內(nèi)存.下列哪個(gè)軟件屬于操作系統(tǒng)軟件()。A.MicrosoftWordB.金山詞霸C.FoxmailD.WinRARE.RedHatLinux

.下列哪個(gè)不是計(jì)算機(jī)的存儲(chǔ)設(shè)備（）。A.文件管理器B.內(nèi)存C.高速緩存D.硬盤E.U盤.下列說法中錯(cuò)誤的是（）。CPU的基本功能就是執(zhí)行指令。CPU訪問內(nèi)存的速度快于訪問高速緩存的速度。CPU的主頻是指CPU在1秒內(nèi)完成的指令周期數(shù)。D.在一臺(tái)計(jì)算機(jī)內(nèi)部，一個(gè)內(nèi)存地址編碼對應(yīng)唯一的一個(gè)內(nèi)存單元。E.數(shù)據(jù)總線的寬度決定了一次傳遞數(shù)據(jù)量的大小，是影響計(jì)算機(jī)性能的因素之一。.彩色顯示器所顯示的五彩斑斕的色彩，是由紅色、藍(lán)色和（）色混合而成的。A.紫B.白C.黑D.綠E.橙.用靜電吸附墨粉后轉(zhuǎn)移到紙張上，是哪種輸出設(shè)備的工作方式（）。A.針式打印機(jī)B.噴墨打印機(jī)C.激光打印機(jī)D.筆式繪圖儀E.噴墨繪圖儀.一臺(tái)計(jì)算機(jī)如果要利用電話線上網(wǎng)，就必須配置能夠?qū)?shù)字信號(hào)和模擬信號(hào)進(jìn)行相互轉(zhuǎn)換的設(shè)備，這種設(shè)備是（）。A.調(diào)制解調(diào)器 B.路由器C.網(wǎng)卡D.網(wǎng)關(guān)E.網(wǎng)橋.下列哪個(gè)不是數(shù)據(jù)庫軟件的名稱（）。A.MySQLB.SQLServerC.OracleD.金山影霸E.Foxpro.下列哪個(gè)程序設(shè)計(jì)語言不支持面向?qū)ο蟪绦蛟O(shè)計(jì)方法（）。A.C++B.ObjectPascalC.CD.SmalltalkE.Java.由3個(gè)a，1個(gè)b和2個(gè)c構(gòu)成的所有字符串中，包含子串“abc”的共有（）個(gè)。A.20B.8C.16D.12E.24.某個(gè)車站呈狹長形，寬度只能容下一臺(tái)車，并且只有一個(gè)出入口。已知某時(shí)刻該車站狀態(tài)為空，從這一時(shí)刻開始的出入記錄為：“進(jìn)，出，進(jìn)，進(jìn)，出，進(jìn)，進(jìn)，進(jìn)，出，出，進(jìn)，出”。假設(shè)車輛入站的順序?yàn)?,2,3,……，則車輛出站的順序?yàn)椋ǎ?。A.1,2,3,4,5B.1,2,4,5,7 C.1,3,5,4,6 D.1,3,5,6,7 E.1,3,6,5,7.二叉樹T，已知其前序遍歷序列為1243576，中序遍歷序列為4215736，則其后序遍歷序列為（）。A.4257631 B.4275631 C.4275361 D.4723561 E.4526371.滿二叉樹的葉結(jié)點(diǎn)個(gè)數(shù)為N，則它的結(jié)點(diǎn)總數(shù)為（）。A.NB.2*N C.2*N1 D.2*N+1E.2n1.十進(jìn)制數(shù)2004等值于八進(jìn)制數(shù)（）。A.3077B.3724C.2766D.4002E.3755.（2004）10+（32）16的結(jié)果是（）。A.（2036）10B.（2054）16C.（4006）10D.（100000000110）2E.（2036）1