NOIP2018年提高組初賽模擬考試題

./第二十三屆全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽初賽提高組PASCAL語(yǔ)言模擬試題競(jìng)賽時(shí)間：2017年10月14日14:30~16:30選手注意:●試題紙共有13頁(yè),答題紙共有2頁(yè),滿分100分。請(qǐng)?jiān)诖痤}紙上作答,寫(xiě)在試題紙上的一律無(wú)效?！癫坏檬褂萌魏坞娮釉O(shè)備〔如計(jì)算器、手機(jī)、電子詞典等或查閱任何書(shū)籍資料。單項(xiàng)選擇題〔共15題,每題1.5分,共計(jì)22.5分；每題有且僅有一個(gè)正確選項(xiàng)1．1956年〔授予肖克利〔WilliamShockley、巴丁〔JohnBardeen和布拉頓〔WalterBrattain,以表彰他們對(duì)半導(dǎo)體的研究和晶體管效應(yīng)的發(fā)現(xiàn)。A.諾貝爾物理學(xué)獎(jiǎng)B.約翰·馮·諾依曼獎(jiǎng)C.圖靈獎(jiǎng)D.高德納獎(jiǎng)〔DonaldE.KnuthPrize如果開(kāi)始時(shí)計(jì)算機(jī)處于小寫(xiě)輸入狀態(tài),現(xiàn)在有一只小老鼠反復(fù)按照CapsLock、字母鍵A、字母鍵S和字母鍵D的順序來(lái)回按鍵,即CapsLock、A、S、D、S、A、CapsLock、A、S、D、S、A、CapsLock、A、S、D、S、A、……,屏幕上輸出的第81個(gè)字符是字母〔。Ａ.AＢ.SＣ.DＤ.A二進(jìn)制數(shù)00101100和01010101異或的結(jié)果是〔。Ａ.00101000Ｂ.01111001Ｃ.01000100Ｄ.001110004.與二進(jìn)制小數(shù)0.1相等的八進(jìn)進(jìn)制數(shù)是〔。Ａ.0.8Ｂ.0.4Ｃ.0.2Ｄ.5.以比較作為基本運(yùn)算,在N個(gè)數(shù)中找最小數(shù)的最少運(yùn)算次數(shù)為〔。Ａ.NＢ.N-1Ｃ.N2Ｄ.logN6.表達(dá)式a*<b+c>-d的后綴表達(dá)形式為〔。Ａ.abcd*+-Ｂ.abc+*d-Ｃ.abc*+d-Ｄ.-+*abcd一棵二叉樹(shù)如右圖所示,若采用二叉樹(shù)鏈表存儲(chǔ)該二叉樹(shù)〔各個(gè)結(jié)點(diǎn)包括結(jié)點(diǎn)的數(shù)據(jù)、左孩子指針、右孩子指針。如果沒(méi)有左孩子或者右孩子,則對(duì)應(yīng)的為空指針。那么該鏈表中空指針的數(shù)目為〔。A.6B.7C.12Ｄ.G是一個(gè)非連通簡(jiǎn)單無(wú)向圖,共有28條邊,則該圖至少有〔個(gè)頂點(diǎn)。Ａ.10Ｂ.9Ｃ.8Ｄ.7.某計(jì)算機(jī)的CPU和內(nèi)存之間的地址總線寬度是32位〔bit,這臺(tái)計(jì)算機(jī)最多可以使用〔的內(nèi)存。A. 2GB B. 4GB C. 8GB D. 16GB10．無(wú)論是TCP/IP模型還是OSI模型,都可以視為網(wǎng)絡(luò)的分層模型,每個(gè)網(wǎng)絡(luò)協(xié)議都會(huì)被歸入某一層中。如果用現(xiàn)實(shí)生活中的例子來(lái)比喻這些"層",以下最恰當(dāng)?shù)氖恰?。A．中國(guó)公司的經(jīng)理與波蘭公司的經(jīng)理交互商業(yè)文件B．軍隊(duì)發(fā)布命令C．國(guó)際會(huì)議中,每個(gè)人都與他國(guó)地位對(duì)等的人直接進(jìn)行會(huì)談D．體育比賽中,每一級(jí)比賽的優(yōu)勝者晉級(jí)上一級(jí)比賽11.有7個(gè)一模一樣的蘋(píng)果,放到3個(gè)一樣的盤(pán)子中,一共有〔種放法。Ａ.7Ｂ.8Ｃ.21Ｄ.37Lucia和她的朋友以及朋友的朋友都在某社交網(wǎng)站上注冊(cè)了賬號(hào)。下圖是他們之間的關(guān)系圖,兩個(gè)人之間有邊相連代表這兩個(gè)人是朋友,沒(méi)有邊相連代表不是朋友。這個(gè)社交網(wǎng)站的規(guī)則是：如果某人A向他〔她的朋友B分享了某張照片,那么B就可以對(duì)該照片進(jìn)行評(píng)論；如果B評(píng)論了該照片,那么他〔她的所有朋友都可以看見(jiàn)這個(gè)評(píng)論以及被評(píng)論的照片,但是不能對(duì)該照.片進(jìn)行評(píng)論〔除非A也向他〔她分享了該照片?，F(xiàn)在Lucia已經(jīng)上傳了一張照片,但是她不想讓Jacob看見(jiàn)這張照片,那么她可以向以下朋友〔分享該照片。Ａ.Dana,Michael,EveＢ.Dana,Eve,MonicaＣ.Michael,Eve,JacobＤ.Micheal,Peter,Monica周末小明和爸爸媽媽三個(gè)人一起想動(dòng)手做三道菜。小明負(fù)責(zé)洗菜、爸爸負(fù)責(zé)切菜、媽媽負(fù)責(zé)炒菜。假設(shè)做每道菜的順序都是：先洗菜10分鐘,然后切菜10分鐘,最后炒菜10分鐘。那么做一道菜需要30分鐘。注意：兩道不同的菜的相同步驟不可以同時(shí)進(jìn)行。例如第一道菜和第二道的菜不能同時(shí)洗,也不能同時(shí)切。那么做完三道菜的最短時(shí)間需要〔分鐘。A.90B.60C.50D.4014.假設(shè)某算法的計(jì)算時(shí)間表示為遞推關(guān)系式T<n>=2T<>+T<1>=1則算法的時(shí)間復(fù)雜度為〔。A.O<n>B.O<>C.O<logn>D.O<n2>15.給定含有n個(gè)不同的數(shù)的數(shù)組L=<x1,x2,...,xn>。如果L中存在xi〔1<i<n使得x1<x2<...<xi-1<xi>xi+1>...>xn,則稱(chēng)L是單峰的,并稱(chēng)xi是L的"峰頂"?，F(xiàn)在已知L是單峰的,請(qǐng)把a(bǔ)-c三行代碼補(bǔ)全到算法中使得算法正確找到L的峰頂。Search<k+1,n>Search<1,k-1>returnL[k]Search<1,n>k←[n/2]ifL[k]>L[k-1]andL[k]>L[k+1]then__________elseifL[k]>L[k-1]andL[k]<L[k+1]then__________else__________正確的填空順序是〔。A.c,a,bB.c,b,aC.a,b,cD.b,a,c二、不定項(xiàng)選擇題〔共5題,每題1.5分,共計(jì)7.5分；每題有一個(gè)或多個(gè)正確選項(xiàng),多選或少選均不得分..以下屬于無(wú)線通信技術(shù)的有〔。A. 藍(lán)牙 B. WiFi C. GPRS D. 以太網(wǎng)可以將單個(gè)計(jì)算機(jī)接入到計(jì)算機(jī)網(wǎng)絡(luò)中的網(wǎng)絡(luò)接入通訊設(shè)備有〔。A. 網(wǎng)卡 B. 光驅(qū) C. 鼠標(biāo) D. 顯卡下列算法中運(yùn)用分治思想的有〔。A. 快速排序 B. 歸并排序 C. 冒泡排序 D. 計(jì)數(shù)排序下圖表示一個(gè)果園灌溉系統(tǒng),有A、B、C、D四個(gè)閥門(mén),每個(gè)閥門(mén)可以打開(kāi)或關(guān)上,所有管道粗細(xì)相同,以下設(shè)置閥門(mén)的方法中,可以讓果樹(shù)澆上水的有水有水果樹(shù)有〔。A. B打開(kāi),其他都關(guān)上B. AB都打開(kāi),CD都關(guān)上C. A打開(kāi),其他都關(guān)上D. D打開(kāi),其他都關(guān)上5.參加NOI比賽,以下能帶入考場(chǎng)的有〔。A. 鋼筆B. 適量的衣服 C. U盤(pán)D. 鉛筆三、問(wèn)題求解〔共2題,每題5分,共計(jì)10分；每題全部答對(duì)得5分,沒(méi)有部分分1.在1和2015之間〔包括1和2015在內(nèi)不能被4、5、6三個(gè)數(shù)任意一個(gè)數(shù)整除的數(shù)有_________個(gè)。2.結(jié)點(diǎn)數(shù)為5的不同形態(tài)的二叉樹(shù)一共有_________種。〔結(jié)點(diǎn)數(shù)為2的二叉樹(shù)一共有2種：一種是根結(jié)點(diǎn)和左兒子,另一種是根結(jié)點(diǎn)和右兒子。四、閱讀程序?qū)懡Y(jié)果〔共4題,每題8分,共計(jì)32分1．ConstSIZE=100;varn,i,sum,x:integer;a:array[1..SIZE]ofinteger;beginreadln<n>;fillchar<a,sizeof<a>,0>;fori:=1tondobeginread<x>;inc<a[x]>;end;i:=0;sum:=0;whilesum<<ndiv2+1>dobegininc<i>;sum:=sum+a[i];end;writeln<i>;end．輸入：1145664332321輸出：2．varn:integer;proceduref2<x,y:integer>;forward;proceduref1<x,y:integer>;beginifx<nthenf2<y,x+y>;end;proceduref2<x,y:integer>;beginwrite<x,’’>;f1<y,x+y>;end;beginreadln<n>;f1<0,1>;end．輸入：30輸出：_____________3．constV=100;varvisited:array[1..v]ofboolean;e:array[1..V,1..V]ofinteger;n,m,ans,i,j,a,b,c:integer;proceduredfs<x,len:integer>;varI:integer;beginvisited[x]:=true;iflen>ansthenans:=len;fori:=1tondoif<notvisited[i]>and<e[x,i]<>-1>thendfs<i,len+e[x,i]>;visited[x]:=false;end;beginreadln<n,m>;fori:=1tondoforj:=1tondoe[i][j]:=-1;fori:=1tomdobeginreadln<a,b,c>;e[a][b]:=c;e[b][a]:=c;end;fori:=1tondovisited[i]:=false;ans:=0;fori:=1tondodfs<i,0>;writeln<ans>;end.輸入：46121023203430414013502460輸出：__________4.constSIZE=10000;LENGTH=10;varsum:longint;n,m,i,j:integer;a:array[1..SIZE,1..LENGTH]ofinteger;functionh<u,v:integer>:integer;varans,i:integer;beginans:=0;fori:=1tondoifa[u][i]<>a[v][i]theninc<ans>;h:=ans;end;beginreadln<n>;filichar<a,sizeof<a>,0>;m:=1;repeati:=1;while<i<=n>and<a[m][i]=1>doinc<i>;ifi>nthenbreak;inc<m>;a[m][i]:=1;forj:=i+1tondoa[m][j]:=a[m-1][j];untilfalse;sum:=0;fori:=1tomdoforj:=1tomdosum:=sum+h<i,j>;writeln<sum>;end.輸入：7輸出：____________五、完善程序〔共2題,每題14分,共計(jì)28分1.〔雙子序列最大和給定一個(gè)長(zhǎng)度為n〔3≤n≤1000的整數(shù)序列,要求從中選出兩個(gè)連續(xù)子序列,使得這兩個(gè)連續(xù)子序列的序列和之和最大,最終只需輸出這個(gè)最大和。一個(gè)連續(xù)子序列的序列和為該連續(xù)子序列中所有數(shù)之和。要求：每個(gè)連續(xù)子序列長(zhǎng)度至少為1,且兩個(gè)連續(xù)子序列之間至少間隔1個(gè)數(shù)?！驳谖蹇?分,其余2.5分constMAXN=1000;varn,i,ans,sum:longint;x:array[1..MAXN]oflongint;lmax:array[1..MAXN]oflongint;//lmax[i]為僅含x[i]及x[i]左側(cè)整數(shù)的連續(xù)子序列的序列和中,最大的序列和rmax:array[1..MAXN]oflongint;//rmax[i]為僅含x[i]及x[i]右側(cè)整數(shù)的連續(xù)子序列的序列和中,最大的序列和beginread<n>;fori:=1tondoread<x[i]>;lmax[1]:=x[1];fori:=2tondoiflmax[i-1]<=0thenlmax[i]:=x[i]elselmax[i]:=lmax[i-1]+x[i];fori:=2tondoiflmax[i]<lmax[i-1]thenlmax[i]:=lmax[i-1];<1>fori:=n-1downto1doifrmax[i+1]<=0then<2>Else<3>fori:=n-1downto1doifrmax[i]<rmax[i+1]then<4>ans:=x[1]+x[3];fori:=2ton-1dobeginsum:=<5>ifsum>ansthenans:=sum;end;writeln<ans>;end.〔最短路徑問(wèn)題無(wú)向連通圖G有n個(gè)結(jié)點(diǎn),依次編號(hào)為1,2,3,...,n。用鄰接矩陣的形式給出每條邊的邊長(zhǎng),要求輸出以結(jié)點(diǎn)1為起點(diǎn)出發(fā),到各結(jié)點(diǎn)的最短路徑長(zhǎng)度。使用Dijkstra算法解決該問(wèn)題：利用dist數(shù)組記錄當(dāng)前各結(jié)點(diǎn)與起點(diǎn)的已找到的最短路徑長(zhǎng)度；每次從未擴(kuò)展的結(jié)點(diǎn)中選取dist值最小的結(jié)點(diǎn)v進(jìn)行擴(kuò)展,更新與v相鄰的結(jié)點(diǎn)的dist值；不斷進(jìn)行上述操作直至所有結(jié)點(diǎn)均被擴(kuò)展,此時(shí)dist數(shù)據(jù)中記錄的值即為各結(jié)點(diǎn)與起點(diǎn)的最短路徑長(zhǎng)度。〔第五空2分,其余3分constMAXV=100;varn,