第十九屆全國奧林匹克信息學(xué)聯(lián)賽初賽

CCFNOIP2013初賽提高組C語言試題第頁，共12頁第十九屆全國青少年信息學(xué)奧林匹克聯(lián)賽初賽提高組C語言試題競賽時(shí)間：2013年10月13日14:30~16:30選手注意：●試題紙共有12頁，滿分100分。請?jiān)诖痤}紙上做答，寫在試題紙上的一律無效?！癫坏檬褂萌魏坞娮釉O(shè)備（如計(jì)算器、手機(jī)、電子詞典等）或查閱任何書籍資料。單項(xiàng)選擇題（共15題，每題1.5分，共計(jì)22.5分：每題僅有一個(gè)正確選項(xiàng)）一個(gè)32位整型變量占用（）個(gè)字節(jié)。A.4B.8C.32D.1282.二進(jìn)制數(shù)11.01在十進(jìn)制下是（）。A.3.25B.4.125C.6.25D.11.1253.下面的故事與（）算法有異曲同工之妙。從前有座山，山里有座廟，廟里有個(gè)老和尚在給小和尚講故事：“從前有座山，山里有座廟，廟里有個(gè)老和尚在給小和尚講故事：‘從前有座山，山里有座廟，廟里有個(gè)老和尚在給小和尚講故事……’”A.枚舉B.遞歸C.貪心D.分治4.1948年，（）將熱力學(xué)的熵引入信息通信領(lǐng)域，標(biāo)志著信息理論的開端。A.馮·諾依曼(JohnvonNeumann)B.圖靈(AlanTuring)C.歐拉(LeohardEuler)D.克勞德·香農(nóng)(ClaudeShannon)5.已知一棵二叉樹有2013個(gè)節(jié)點(diǎn)，則其中至多有（）個(gè)節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)。A.1006B.1007C.1023D.10246.在一個(gè)無向圖中，如果任意兩點(diǎn)之間都存在路徑相連，則稱之為連通圖。右圖是一個(gè)右五個(gè)頂點(diǎn)、八條邊的連通圖。若要使它不再是連通圖，至少要?jiǎng)h去其中（）條邊。23457.斐波那契數(shù)列定義如下：F1=1,F2=1,Fn=(n-1)+f(n-2)。如果用下面的函數(shù)計(jì)算斐波那契數(shù)列的第n項(xiàng)，則其時(shí)間復(fù)雜度為（）。intF(intn){if(n<=2)return1;elsereturnF(n-1)+F(n-2)}A.O(1)B.O(n)C.O(n2)D.O(Fn)8.二叉查找樹具有如下性質(zhì)：每個(gè)節(jié)點(diǎn)的值都大于其左子樹上所有節(jié)點(diǎn)的值、小于其右子樹上所有節(jié)點(diǎn)的值。那么，二叉查找樹的（）是一個(gè)有序序列。A.先序遍歷B.中序遍歷C.后序遍歷D.寬度優(yōu)先遍歷9.將(2,6,10,17)分別存儲到某個(gè)地址區(qū)間為0~10的哈希表中，如果哈希函數(shù)h(x)=（），將不會發(fā)生沖突，其中amodb表示a除以b的余數(shù)。A.xmod11B.x2mod11C.2xmod11D.[√x]mod11，其中[√x]表示向下取整10.IPv4協(xié)議使用32位地址，隨著其不斷變化，地址資源日趨枯竭。因此，它正逐漸被使用（）位地址的IPv6協(xié)議所取代。A．40B.48C.64D.12811.二分圖是指能將頂點(diǎn)劃分成兩個(gè)部分，每一部分頂點(diǎn)間沒有邊相連的簡單無向圖。那么，12個(gè)頂點(diǎn)的二分圖至多有（）條邊。A.18B.24C.36D.6612.（）是一種通用的字符編碼，它為世界上絕大部分語言設(shè)定了統(tǒng)一并且唯一的二進(jìn)制編碼，以滿足跨語言、跨平臺的文本交換。目前它已經(jīng)收錄了超過十萬個(gè)不同字符。A.ASCIIB.UnicpdeC.GBK2312D.BIG513.把64位非零浮點(diǎn)數(shù)強(qiáng)制轉(zhuǎn)換成32位浮點(diǎn)數(shù)后，不可能（）A.大于原數(shù)B.小于原數(shù)C.等于原數(shù)D.與原數(shù)符號相反14.對于一個(gè)n個(gè)頂點(diǎn)，m條邊的帶權(quán)有向圖用Dijkstra算法計(jì)算單源最短路時(shí)，如果不使用堆或其他優(yōu)先隊(duì)列進(jìn)行優(yōu)化，則其時(shí)間復(fù)雜度位（）A.O(mn+n3)B.O(n2)C.O((m+n)㏒n)D.O((m+n2)㏒n)15.T(n)表示某個(gè)算法輸入規(guī)模位n時(shí)的運(yùn)算次數(shù)。如果T(1)位常數(shù)，且有遞歸式T(n)=2*T(n/2)+2n，那么T(n)=（）A.Θ(n)B.Θ(n㏒n)C.Θ(n2)D.Θ(n2㏒n)二、不定選項(xiàng)題（共5題，每題1.5分，共計(jì)7.5分；每題有一個(gè)或多個(gè)正確選項(xiàng)，多選或少選均不得分）1.下列程序中，正確計(jì)算1,2，……，100個(gè)自然數(shù)之和sum（初始值為0）的是（）A.for(i=1;i<=100;i++)sum+=i;B.i=1;while(i>100){sum+=I;i++;}C.i=1;do{sum+=I;i++;}while(i<=100);D.i=1;do{sum+=I;i++;}while(i>100);（）的平均時(shí)間復(fù)雜度為Θ(n㏒n)，其中n是待排序的元個(gè)數(shù)。A.快速排序B.插入排序C.冒泡排序D.歸并排序3.以A0作為起點(diǎn)，對下面的無向題進(jìn)行深度優(yōu)先遍歷時(shí)，（遍歷的順序與定點(diǎn)字母的下標(biāo)無關(guān)），最后一個(gè)遍歷到的頂點(diǎn)可能是（）。A.printf("%d\n",ans);return0;}輸入：832511127410輸出：4.#include<stdio.h>#include<stdlib.h>#include<string.h>#defineSIZE100Intn,m,p,count;inta[SIZE][SIZE];voidcolour(intx,inty){count++;a[x][y];if((x>1)&&(a[x-1][y]==0))colour(x-1,y);if((y>1)&&(a[x][y-1]==0))colour(x,y-1);if((x<n)&&(a[x+1][y]==0))colour(x+1,y);if((x<m)&&(a[x][y+1]==0))colour(x,y+1);}intmain(){inti,j,x,y,ans;memset(a,0,sizeof(a));scanf("%d%d%d",&n,&m,&p);for(i=1;i<=p;i++){scanf("%d%d",&x,&y);a[x][y]=1;}ans=0;for(i=1;i<=n;i++)for(j=1;j<=m;j++)if(a[i][j]==0){count=