信息學提高組初賽題解析多媒體概述第十屆信息學提高組初賽題解第十一屆信息學提高組初賽題解第十二屆信息學提高組初賽題解第十三屆信息學提高組初賽題解目錄目錄一、單項選擇題（每題1.5分）

1.字符串“ababacbab”和字符串“abcba”的最長公共子串是（）。

A.abcbaB.cba

C.abcD.abE.bcba

答案：1、B第十一屆信息學提高組初賽題解析2.設全集I={a,b,c,d,e,f,g,h}，

集合AUB={a,b,c,d,e,f}，

A∩C={c,d,e}，A∩~B=

{a,d}

那么集合A∩B∩C=

A.{c,e}B.{d,e}

C.{e}D.{c,d,e}

E.{d,f}答案：2、A二進制3.以下二進制數的值與十進制數23.456的值最接近的是（）。

A.10111.0101B.11011.1111C.11011.0111D.10111.0111E.10111.1111答：3、D4.完全二叉樹的結點個數為

4*N+3,則它的葉結點個數為（）。

A.2*NB.2*N–1C.2*N+1D.2*N-2E.2*N+2答案4、E完全二叉樹深度K和結點總數M關系2K-1-1<M<=2K–1葉子結點數目=度為2的結點數目加1.5.平面上有五個點A(5,3),B(3,5),C(2,1),D(3,3),E(5,1)。以這五點作為完全圖G的頂點，

每兩點之間的直線距離是圖G中對應邊的權值。圖G的最小生成樹中的所有邊的權值綜合為（）。

A.8B.7+C.9D.6+E.4+2√

2+5。答：5、D6.下列設備中沒有計算功能的是（）。

A.筆記本電腦B.掌上電腦C.智能手機D.電子計算器E.液晶顯示器7.Intel的首顆64位處理器是（）。

A.8088B.8086C.80386D.80486E.Pentium

答案：6、E7、ET6-T7Internet8.常見的郵件傳輸服務器使用（）協議發送郵件。

A.HTTPB.SMTPC.TCPD.FTPE.POP3

9.不能在Linux上使用的網頁瀏覽器是（）。A.InternetExploreB.NetscapeC.OperaD.FirefoxE.Mozilla

答案：8、B9、A10、存儲容量10.一位藝術史學家有20000幅1024*768的真彩色圖像，如果將這些圖像以位圖形式保存在CD光盤上（一張CD光盤的容量按600M計算），大約需要（）張CD光盤。A、1B.10C.100D.1000E.10000

答案：10、C二、不定項選擇題（共10題，每題1.5分多選或少選均不得分）。

11.設A=true，B=false，C=false，D=true，以下邏輯運算表達式值為真的有

A.(A∧B)∨(C∧D)B.((A∧B)∨C)∧DC.A∧((B∨C)∨D)

D.(A∧(B∨C))∨DE.(A∨B)∧(C∨D)

答案：11、CDE數制轉換12、(3725)8+(B)16的運算結果是（）A.(3736)8B.(2016)10

2

D.(3006)10E.(7E0)16

答案：12、BCEBinaryTree13.二叉樹T的寬度優先遍歷序列為ABCDEFGHI，已知A是C的父結點，D是G的

父結點，F是I的父結點，樹中所有結點的最大深度為3（根結點深度設為0），可知E

的父結點可能是（）。

A.AB.BC.CD.DE.F

。答案：13、BC

14.設棧S的初始狀態為空，元素a,b,c,d,e,f,g依次入棧，以下出棧序列不可能出現的有（）。

A.a,b,c,e,d,f,gB.b,c,a,f,e,g,dC.a,e,c,b,d,f,g

D.d,c,f,e,b,a,gE.g,e,f,d,c,b,a

答案：14、CE無線連接15.下列外設接口中可以通過無線連接的方式連接設備的是（）。

A.USB2.0高速版B.紅外C.藍牙D.串口E.IEEE802.11g無線網卡答案：15、BCECPU主頻16.處理器A每秒處理的指令數是處理器B的2倍。某一特定程序P分別編譯為處理器A和處理器B的指令，編譯結果處理器A的指令數是處理器B的4倍。已知程序P的算法時間復雜度為O(n2)，如果處理器A執行程序P時能在一小時內完成的輸入規模為n，則處理器B執行程序P時能在一小時內完成的輸入規模為（）。

A.4*nB.2*nC.nD.n/2E.n/4答案：16、B17.以下哪個(些)不是計算機的輸出設備（）。

A.鼠標B.顯示器C.鍵盤D.掃描儀E.繪圖儀

18.以下斷電之后將不能保存數據的有

A.硬盤B.寄存器C.顯存D.內存E.高速緩存答案：17、ACD18、BCDE19.下列活動中屬于信息學奧賽系列活動的是（）。A.NOIPB.NOIC.IOID.冬令營E.國家隊選拔賽

20.下列關于高級語言的說法正確的有

A.Ada是歷史上的第一個高級語言

B.Pascal和C都是編譯執行的高級語言

C.C++是歷史上的第一個支持面向對象的語言

D.編譯器將高級語言程序轉變為目標代碼

E.高級語言程序比匯編語言程序更容易從一種計算機移植到另一種計算機上。答案：19、ABCDE20、BDE三．問題求解（請在空格處填上答案，每空5分，共計10分）1.將數組{32,74,25,53,28,43,86,47}中的元素按從小到大的順序排列，每次可以交換任意兩個元素，最少需要交換次。2.取火柴游戲的規則如下一堆火柴有N根，A、B兩人輪流取出。每人每次可以取1根或2根，最先沒有火柴可取的人為敗方，另一方為勝方。如果先取者有必勝策略則記為1，先取者沒有必勝策略記為0。當N分別為100，200，300，400，500時，先取者有無必勝策略的標記順序為（回答應為一個由0和/或1組成的字符串）。Fibonacci數列算法二叉樹概念什么是多叉樹?第十一屆全國青少年信息學奧林匹克聯賽初賽試題提高組(P)參考答案一.單項選擇題（共10題，每題1.5分，共計15分。題號12３45678910選擇BADEDEEBAC二．不定項選擇題（共10題，每題1.5分。多選或少選均不得分）。題號11

12

13

14

15

16

17

18

19

20選擇CDE

BCE

BCCEBCE

B

ACD

BCDEABCDE

BDE三．問題求解（共2題，每題5分）1.答：52.答：11011三．問題求解（共2題，每題5分，共計10分）1.答：52.答：11011

四.閱讀程序（共4題，每題8分，共計32分）（1）程序的運行結果是:

-7452(2)程序的運行結果是:3223（3）程序的運行結果是:zzzaaabbbcccy（4）程序的運行結果是:31pascal語言五.完善程序(前5空每空2分，后6空每空3分，共28分)1.（1）num+len[i]divt

（2）num>=k

（3）left:=0

（4）left+1

（5）notisok(mid)（或者isok(mid)=false）