noip2013提高組c++試題

1、CCFNOIP2013初賽提高組C語(yǔ)言試題第1頁(yè)，共12頁(yè)第十九屆全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽初賽提高組C語(yǔ)言試題競(jìng)賽時(shí)間：2013年10月13日14:30~16:30選手注意：?試題紙共有12頁(yè)，答題紙共有2頁(yè)，滿分100分。請(qǐng)?jiān)诖痤}紙上作答，寫在試題紙上的一律無(wú)效。?不得使用任何電子設(shè)備（如計(jì)算器、手機(jī)、電子詞典等）或查閱任何書(shū)籍資料。一、單項(xiàng)選擇題（共15題，每題1.5分，共計(jì)22.5分；每題有且僅有一個(gè)正確選項(xiàng)）1.一個(gè)32位整

2、型變量占用（）個(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é)中的熵引入信

3、息通信領(lǐng)域，標(biāo)志著信息論研究的開(kāi)端。A.馮諾伊曼（JohnvonNeumann）B.圖靈（AlanTuring）C.歐拉（LeonhardEuler）D.克勞德香農(nóng)（ClaudeShannon）5.已知一棵二叉樹(shù)有2013個(gè)節(jié)點(diǎn)，則其中至多有（）個(gè)節(jié)點(diǎn)有2個(gè)子節(jié)點(diǎn)。A.1006B.1007C.1023D.10246.在一個(gè)無(wú)向圖中，如果任意兩點(diǎn)之間都存在路徑相連，則稱其為連通圖。右圖是一個(gè)有5個(gè)頂點(diǎn)、8條邊的連通圖。若要使它不再是連通圖

4、，至少要?jiǎng)h去其中的（）條邊。CCFNOIP2013初賽提高組C語(yǔ)言試題第3頁(yè)，共12頁(yè)14.對(duì)一個(gè)n個(gè)頂點(diǎn)、m條邊的帶權(quán)有向簡(jiǎn)單圖用Dijkstra算法計(jì)算單源最短路時(shí)，如果不使用堆或其它優(yōu)先隊(duì)列進(jìn)行優(yōu)化，則其時(shí)間復(fù)雜度為（）。A.O(mnn3)B.O(n2)C.O((mn)logn)D.O((mn2)logn)15.T(n)表示某個(gè)算法輸入規(guī)模為n時(shí)的運(yùn)算次數(shù)。如果T(1)為常數(shù)，且有遞歸式T(n)=2T(n2)2n，那么T(n)=（

5、）。A.Θ(n)B.Θ(nlogn)C.Θ(n2)D.Θ(n2logn)二、不定項(xiàng)選擇題（共5題，每題1.5分，共計(jì)7.5分；每題有一個(gè)或多個(gè)正確選項(xiàng)，多選或少選均不得分）1.下列程序中，正確計(jì)算12…100這100個(gè)自然數(shù)之和sum（初始值為0）的是（）。A.f(i=1i100)sum=iiC.i=1dosum=iiwhile(i100)2.（）的平均時(shí)間復(fù)雜度為O(nlogn)，其中n是待排序的元素個(gè)數(shù)。A.快速排序B.插入排序C.