1、第十九屆全國青少年信息學(xué)奧林匹克聯(lián)賽初賽普及組C+語言試題競賽時(shí)間：2013年10月13日14:3016:30選手注意：試題紙共有律無效。不得使用任何電子設(shè)備（如計(jì)算器、手機(jī)、電子詞典等）或查閱任何書籍資料。一、單項(xiàng)選擇題（共20題，每題分，共計(jì)30分；每題有且僅有一個(gè)正確選項(xiàng)）9頁，答題紙共有2頁，滿分100分。請?jiān)诖痤}紙上作答，寫在試題紙上的一1.一個(gè)32位整型變量占用（）個(gè)字節(jié)。A.4B.8C.32D.1282.二進(jìn)制數(shù)在十進(jìn)制下是()。A.3.25B.4.125C.D.3.卜面的故事與（）算法有著異曲問工之妙。從前有座山，山里有座廟，廟里有個(gè)老和尚在給小和尚講故事：從前有座山，山里有座

2、廟，廟里有個(gè)老和尚在給小和尚講故事：事.A.4.A.C.5.'從前有座山，山里有座廟，廟里有個(gè)老和尚給小和尚講故枚舉B.遞歸C貪心D.邏輯表達(dá)式（）的值與變量（A（A將VB）AAAB）V（AAB）（2,6,10,17分治A的真假無關(guān)。B.（AVB）D.（AVB）A.C.6.A.7.A.8.）,將不會產(chǎn)生沖突，其中xmod11B.x2mod112xmod11D.|V2|mod11在十六進(jìn)制表示法中，字母9B.10C.15D.下圖中所使用的數(shù)據(jù)結(jié)構(gòu)是（）分別存儲到某個(gè)地址區(qū)間為amodb表示A"AAAB010的哈希表中，如果哈希函數(shù)a除以b的余數(shù)。,其中/X表示/X下取整A相當(dāng)于

3、十進(jìn)制中的（）。16）哈希表B.棧C.隊(duì)列D.二叉樹在Windows資源管理器中，用鼠標(biāo)右鍵單擊一個(gè)文件時(shí)，會出現(xiàn)一個(gè)名為“復(fù)制”的操作）。選項(xiàng)，它的意思是(A.B.C.D.9.A.用剪切板中的文件替換該文件在該文件所在文件夾中，將該文件復(fù)制到剪切板，將該文件復(fù)制到剪切板，已知一棵二叉樹有104B.5C.6將該文件克隆一份并保留原文件并刪除原文件個(gè)節(jié)點(diǎn)，則其中至多有（）個(gè)節(jié)點(diǎn)有2個(gè)子節(jié)點(diǎn)。D.7h(x)10.在一個(gè)無向圖中，如果任意兩點(diǎn)之間都存在路徑相連，則稱其為連通圖。下圖是一個(gè)有個(gè)頂點(diǎn)、6條邊的連通圖。若要使它不再是連通圖，至少要?jiǎng)h去其中的（）條邊。1B.2C.3D.4二叉樹的（）第一個(gè)訪

4、問的節(jié)點(diǎn)是根節(jié)點(diǎn)。先序遍歷B.中序遍歷C.后序遍歷D.以上都是以A0作為起點(diǎn)，對下面的無向圖進(jìn)行深度優(yōu)先遍歷時(shí)，遍歷順序不可能是（A0,A1,A2,A3B.A0,A1,A3,A2C.A0,A2,A1,A3A.11.A.12.A.)D.A0,A3,A1,A2協(xié)議使用32位地址，隨著其不斷被分配，地址資源日趨枯竭。因此，它正逐漸被使IPv4用（）位地址的IPv6協(xié)議所取代。14. 40B.48C.64D.128（）的平均時(shí)間復(fù)雜度為O（nlogn），其中n是待排序的元素個(gè)數(shù)。15. A.快速排序B.插入排序C.冒泡排序D.基數(shù)排序下面是根據(jù)歐幾里得算法編寫的函數(shù)，它所計(jì)算的是a和b的（）inteu

5、clid(inta,intb)if(b=0)returna;16. elsereturneuclid（b,a%b）;A.最大公共質(zhì)因子B.最小公共質(zhì)因子C.最大公約數(shù)D.最小公倍數(shù)通常在搜索引擎中，對某個(gè)關(guān)鍵詞加上雙引號表示（）。17. 排除關(guān)鍵詞，不顯示任何包含該關(guān)鍵詞的結(jié)果將關(guān)鍵詞分解，在搜索結(jié)果中必須包含其中的一部分精確搜索，只顯示包含整個(gè)關(guān)鍵詞的結(jié)果站內(nèi)搜索，只顯示關(guān)鍵詞所指向網(wǎng)站的內(nèi)容中國的國家頂級域名是（）。18. A.B.chC.chnD.china把64位非零浮點(diǎn)數(shù)強(qiáng)制轉(zhuǎn)換成32位浮點(diǎn)數(shù)后，不可能（）。1. A.大于原數(shù)B.小于原數(shù)C.等于原數(shù)D.與原數(shù)符號相反下列程序中，正確

6、計(jì)算1,2,?,100這100個(gè)自然數(shù)之和sum（初始值為0）的是（CCFNOIP復(fù)賽全國統(tǒng)一評測時(shí)使用的系統(tǒng)軟件是（）A.NOIWindowsB.NOILinuxC.NOIMacOSD.NOIDOS二、問題求解（共2題，每題5分，共計(jì)10分；每題全部答對得5分，沒有部分分）7個(gè)同學(xué)圍坐一圈，要選2個(gè)不相鄰的作為代表，有種不同的選法。某系統(tǒng)自稱使用了一種防竊聽的方式驗(yàn)證用戶密碼。密碼是n個(gè)數(shù)s1,s2,?,sn，均為0或1。該系統(tǒng)每次隨機(jī)生成n個(gè)數(shù)a1,a2,?,an，均為0或1,請用戶回答（s1a1+s2a2+?+snan）除以2的余數(shù)。如果多次的回答總是正確，即認(rèn)為掌握密碼。該系統(tǒng)認(rèn)為，即

7、使問答的過程被泄露，也無助于破解密碼一一因?yàn)橛脩舨]有直接發(fā)送密碼。然而，事與愿違。例如，當(dāng)n=4時(shí)，有人竊聽了以下5次問答：就破解出了密碼s1=,s2=,s3=,s4=o三、閱讀程序?qū)懡Y(jié)果（共4題，每題8分，共計(jì)32分）#include<iostream>usingnamespacestd;intmain（）inta,b;cin>>a>>b;cout<<a<<"+"<<b<<"="<<a+b<<endl;輸入：35輸出：#include<i

8、ostream>usingnamespacestd;intmain()inta,b,u,i,num;cin>>a>>b>>u;num=0;for(i=a;i<=b;i+)if(i%u)=0)num+;cout<<num<<endl;return0;輸入：110015輸出：#include<iostream>usingnamespacestd;intmain()constintSIZE=100;intn,f,i,left,right,middle,aSIZE;cin>>n>>f;for(i

9、=1;i<=n;i+)cin>>ai;left=1;right=n;domiddle=(left+right)/2;if(f<=amiddle)right=middle;elseleft=middle+1;while(left<right);cout<<left<<endl;return0;輸入：121724691115171819202125輸出：#include<iostream>usingnamespacestd;intmain()constintSIZE=100;intheightSIZE,numSIZE,n,ans;c

10、in>>n;for(inti=0;i<n;i+)cin>>heighti;numi=1;for(intj=0;j<i;j+)if(heightj<heighti)&&(numj>=numi)numi=numj+1;ans=0;for(inti=0;i<n;i+)cout<<ans<<endl;)輸入：625311124輸出：四、完善程序(共2題，每題14分，共計(jì)28分)1.(序列重排)全局?jǐn)?shù)組變量a定義如下：constintSIZE=100;intaSIZE,n;它記錄著一個(gè)長度為n的序列a1,a2,

11、?,an。現(xiàn)在需要一個(gè)函數(shù)，以整數(shù)p(1<p<n)為參數(shù)，實(shí)現(xiàn)如下功能：將序列a的前p個(gè)數(shù)與后np個(gè)數(shù)對調(diào)，且不改變這p個(gè)數(shù)(或np個(gè)數(shù))之間的相對位置。例如，長度為5的序列1,2,3,4,5，當(dāng)p=2時(shí)重排結(jié)果為3,4,5,1,2。有一種樸素的算法可以實(shí)現(xiàn)這一需求，其時(shí)間復(fù)雜度為O(n)、空間復(fù)雜度為O(n):voidswap1(intp)(inti,j,bSIZE;for(i=1;i<=p;i+)b(1)=ai;(二叉查找樹)二叉查找樹具有如下性質(zhì)：每個(gè)節(jié)點(diǎn)的值都大于其左子樹上所有節(jié)點(diǎn)的值、小于其右子樹上所有節(jié)點(diǎn)的值。試判斷一棵樹是否為二叉查找樹。輸入的第一行包含一個(gè)整數(shù)

12、n,表示這棵樹有n個(gè)頂點(diǎn)，編號分別為1,2,?,n，其中編號為1的為根結(jié)點(diǎn)。之后的第i行有三個(gè)數(shù)value,left_child,right_child,分別表示該節(jié)點(diǎn)關(guān)鍵字的值、左子節(jié)點(diǎn)的編號、右子節(jié)點(diǎn)的編號；如果不存在左子節(jié)點(diǎn)或右子節(jié)點(diǎn)，貝U用0代替。輸出1表示這棵樹是二叉查找樹，輸出0則表示不是。#include<iostream>usingnamespacestd;constintSIZE=100;constintINFINITE=1000000;structnode(intleft_child,right_child,value;);nodeaSIZE;intis_bst

13、(introot,intlower_bound,intupper_bound)(intcur;if(root=0)return1;cur=aroot.value;if(cur>lower_bound)&&(1)&&(is_bst(aroot.left_child,lower_bound,cur)=1)&&(is_bst(2),，)=1)return1;return0;)intmain()(inti,n;cin>>n;for(i=1;i<=n;i+)cin>>ai.value>>ai.left_child>>ai.right_child;cout<<is_bst（5）,-INFINITE,INFINITE）<<endl;return0;第十九屆全國青少年信息學(xué)奧林匹克聯(lián)賽初賽普及組參考答案一、單項(xiàng)選擇題（共20題，每題分，共計(jì)30分）12345678910AABCDBBCAC11121314151617181920AADACCADAB1. 二、問題求解（共2題，每題5分，共計(jì)10分；每題全部答對得5分，沒有部分分）1