一、計算機(jī)系統(tǒng) ?

1.在以下各項中，（）不是CPU的組成部分。（NOIP2007）?

?A．控制器B．運算器C．寄存器D．主板?

【答案】D。CPU由控制器、運算器和寄存器組成。 ?

2.在下列各項中，只有（）不是計算機(jī)存儲容量的常用單位。（NOIP2007） ?

?A．ByteB．KBC．UBD．TB ?

【答案】C。存儲容量：Byte=8 bit（位）、1KB=1024B、1MB=1024KB、1GB=1024MB、1TB=1024GB。 ?

3.與十進(jìn)制數(shù)1770對應(yīng)的八進(jìn)制數(shù)是（）。（NOIP2007）?

A．3350B．3351C．3352D．3540 ?

【答案】C。考查進(jìn)制轉(zhuǎn)換，掌握十進(jìn)制、二進(jìn)制、八進(jìn)制和十六進(jìn)制互換，以及多個不同進(jìn)制數(shù)的運算（轉(zhuǎn)換為同一進(jìn)制數(shù)進(jìn)行計算）。?

4.與十進(jìn)制數(shù)28.5625相等的四進(jìn)制數(shù)是（）。（NOIP2008）?

A．123.21B．131.22C．130.22D．130.21?

【答案】D。熟練掌握進(jìn)制轉(zhuǎn)換的知識。 ?

5.計算機(jī)在工作過程中，若突然停電，（）中的信息不會丟失。（NOIP2008） ?

A．ROM 和 RAMB．CPUC．ROM D．RAM ?

【答案】C。ROM（只讀存儲器）斷電后信息不丟失，RAM（隨機(jī)存儲器，內(nèi)存）斷電后信息全部丟失。 ?

6.在32*32點陣的“字庫”中，漢字“北”與“京”的字模占用字節(jié)數(shù)之和是（）。 （NOIP2008） ??

?A．512B．256 C．384D．128 ?

【答案】B。32*32點陣的字庫，每個字占字節(jié)數(shù)為32*32/8=128字節(jié)（1個字節(jié)等于8個二進(jìn)制位，1Byte=8bits，而1位對應(yīng)點陣中的1個點）。所以2個漢字共要256個字節(jié)。

7.在下面各世界頂級的獎項中，為計算機(jī)科學(xué)與技術(shù)領(lǐng)域做出杰出貢獻(xiàn)的科學(xué)家設(shè)立的獎項是（）。（NOIP2006） ?

A. 沃爾夫獎B. 諾貝爾獎C. 菲爾茲獎D. 圖靈獎 ?

【答案】D。沃爾夫獎主要是獎勵對推動人類科學(xué)與藝術(shù)文明做出杰出貢獻(xiàn)的人士；諾貝爾獎有生理或醫(yī)學(xué)獎、文學(xué)獎、物理學(xué)獎、化學(xué)獎、經(jīng)濟(jì)學(xué)獎和和平獎；菲爾茲獎－數(shù)學(xué)界的諾貝爾獎；圖靈獎－計算機(jī)界的諾貝爾獎，2000年姚期智獲得“圖靈獎”，也是迄今為止獲得此項殊榮的唯一華裔計算機(jī)科學(xué)家。?

二、網(wǎng)絡(luò)和數(shù)據(jù)庫 ?

1.在關(guān)系數(shù)據(jù)庫中，存放在數(shù)據(jù)庫中的數(shù)據(jù)的邏輯結(jié)構(gòu)以（）為主。（NOIP2007）?

A．二叉樹B．多叉樹C．哈希表D．二維表 ?

【答案】D。關(guān)系數(shù)據(jù)庫是用二維表表示邏輯結(jié)構(gòu)，類似于Excel。?

2.LAN的含義是（）。（NOIP2007）

?A．因特網(wǎng)B．局域網(wǎng)C．廣域網(wǎng)D．城域網(wǎng) ?

【答案】B。Internet（因特網(wǎng)）、LAN（局域網(wǎng)）、WAN（廣域網(wǎng)）、MAN（城域網(wǎng)） ?

3.Web2.0 是近年來互聯(lián)網(wǎng)的熱門概念之一，其核心思想是互動與分享。下列網(wǎng) 站中，（）是典型的Web 2.0應(yīng)用。（NOIP2008） ??

A．SinaB．FlickerC．YahooD．Google ?

【答案】B。Web2.0最大的特點就是任何人可以參與、發(fā)布網(wǎng)頁信息，如博客、播客（土豆、優(yōu)酷等）、維基百科等。 ?

4.常見的郵件傳輸服務(wù)器使用（ ）協(xié)議接收郵件。（NOIP2005）?

A. HTTP B. SMTP C. TCP D. FTP E. POP3 ?

【答案】E。SMTP-發(fā)送郵件協(xié)議；POP3-接收郵件協(xié)議；HTTP-超文本傳輸協(xié)議；FTP-文件傳輸協(xié)議；TCP/IP-傳輸控制協(xié)議/因特網(wǎng)互聯(lián)協(xié)議，它是Internet最基本的協(xié)議。

??5.下列網(wǎng)絡(luò)中常用的名字縮寫對應(yīng)的中文解釋錯誤的是（ ）。（NOIP2004）?

A、WWW(World Wide Web)：萬維網(wǎng) ?B、URL（Uinform Resource Locator）：統(tǒng)一資源定位器C、HTTP（Hypertext Transfer Protocol）：超文本傳輸協(xié)議 D、FTP(File Transfer Protocol)：快速傳輸協(xié)議 E、TCP （Transfer Control Protocol）：傳輸控制協(xié)議 ?

【答案】D。FTP：文件傳輸協(xié)議。URL：統(tǒng)一資源定位器（網(wǎng)址）。

?6.下列哪個不是數(shù)據(jù)庫軟件的名稱（ ）?

A、MYSQL B、SQL Sever C、Oracle D、金山影霸 ?

【答案】D。數(shù)據(jù)庫軟件常用的有：MYSQL、SQLServer、Access、Foxpro、Oracle、Sybase等。

?三、編程語言 ?

1.一個無法靠自身的控制終止的循環(huán)成為“死循環(huán)”，例如，在C語言程序中， 語句“while(1) printf(“*”);”就是一個死循環(huán)，運行時它將無休止地打印*號。下面關(guān)于死循環(huán)的說法中，只有（）是正確的。（NOIP2007）?

A．不存在一種算法，對任何一個程序及相應(yīng)的輸入數(shù)據(jù)，都可以判斷是否會出現(xiàn)死循環(huán)，因而，任何編譯系統(tǒng)都不做死循環(huán)檢查 B．有些編譯系統(tǒng)可以檢測出死循環(huán) ?C．死循環(huán)屬于語法錯誤，既然編譯系統(tǒng)能檢查各種語法錯誤，當(dāng)然也應(yīng)該能檢查出死循環(huán) ?D．死循環(huán)與多進(jìn)程中出現(xiàn)的“死鎖”差不多，而死鎖是可以檢測的，因而，死循環(huán)也可以檢測的?

【答案】A。 ?

2.在Pascal語言中，表達(dá)式 （23 or 2 xor 5）的值是（）。（NOIP2007）?

A．18B．1C．23D．32 ?

【答案】A。本題考查進(jìn)制轉(zhuǎn)換和邏輯運算（and、or、not和xor）。對于本題首先將十進(jìn)制整數(shù)轉(zhuǎn)換二進(jìn)制數(shù)，然后再按位進(jìn)行邏輯運算。?

7.(2070)16 + (34)8 的結(jié)果是（）。（NOIP2007） ?

A．（8332）10B．（208A）16 C．（100000000110）2D．(20212)8 ?

【答案】A。本題兩個數(shù)分別是十六進(jìn)制和八進(jìn)制，故先將它們轉(zhuǎn)換為二進(jìn)制，然后再進(jìn)行計算和轉(zhuǎn)換。 ?

① (2070)16=(0010,0000,0111,0000)（每位展開為4位二進(jìn)制數(shù)）

② (34)8= (11,100)2 （（每位展開為3位二進(jìn)制數(shù)） ?

③ 利用二進(jìn)制數(shù)的運算法則，得到兩者相加為（0010,0000,0001）2＝（8332） 10 ??

8.(2008)10+(5B)16的結(jié)果是（）。（NOIP2008）?

?A．（833）16B．（2089）10 C．（4163）8D．（100001100011）2?

【答案】A。 ?

9.設(shè)A=B=True，C=D=False，下面邏輯運算表達(dá)式值為假的有（）。（NOIP2007）?

A．(﹁A∧B)∨(C∧D∨A)B．﹁(((A∧B)∨C)∧D) C．A∧(B∨C∨D)∨DD．(A∧(D∨C))∧B ?

【答案】D。“﹁”表示not，“∧”表示and（與，并且），“∨”表示or（或者）。 ?

10.在下列關(guān)于計算機(jī)語言的說法中，不正確的是（）。（NOIP2006） ?

?A. Pascal和C都是編譯執(zhí)行的高級語言 ? ?B. 高級語言程序比匯編語言程序更容易從一種計算機(jī)移植到另一種計算機(jī)上 ? ?C. C++是歷史上的第一個支持面向?qū)ο蟮挠嬎銠C(jī)語言 ? D. 與匯編語言相比，高級語言程序更容易閱讀 ?

【答案】C。第一個支持面向?qū)ο蟮挠嬎銠C(jī)語言是Smalltalk。?

四、數(shù)據(jù)結(jié)構(gòu) ?

1.地面上有標(biāo)號為A、B、C的三根柱，在A柱上放有10個直徑相同中間有孔的 圓盤，從上到下依次編號為1，2，3??，將A柱上的部分盤子經(jīng)過B柱移入C柱，也可以在B柱上暫存。如果B柱上的操作記錄為“進(jìn)、進(jìn)、出、進(jìn)、進(jìn)、出、出、進(jìn)、進(jìn)、出、進(jìn)、出、出”。那么，在C柱上，從下到上的編號為（）。（NOIP2007） ? ?

A．2 4 3 6 5 7B．2 4 1 2 5 7C．2 4 3 1 7 6D．2 4 3 6 7 5?

【答案】D。棧，后進(jìn)先出。 ?

2.某個車站呈狹長形，寬度只能容下一臺車，并且只有一個出入口。已知某時刻該車站狀態(tài)為空，從 這一時刻開始的出入記錄為：“進(jìn)，出，進(jìn)，進(jìn)，進(jìn)，出，出，進(jìn)，進(jìn)，進(jìn)，出,出”。假設(shè)車輛入站的 順序為 1，2，3，??，則車輛出站的順序為（ ）。（NOIP2006） ??

A. 1, 2, 3, 4, 5 B. 1, 2, 4, 5, 7 ?C. 1, 4, 3, 7, 6 D. 1, 4, 3, 7, 2 ?

【答案】C。棧操作。 ?

3.完全二叉樹共有2*N-1個結(jié)點，則它的葉節(jié)點數(shù)是（）。（NOIP2008）?

A．N-1B．NC．2*ND．2N-1?

【答案】B。 ? ?在二叉樹中，結(jié)點的度數(shù)有0、1、2三種情況，其中度為0的結(jié)點就是葉子結(jié)點。設(shè)D0表示度為0的結(jié)點個數(shù)，D1表示度為1的結(jié)點個數(shù)，D2表示度為2的結(jié)點個數(shù)，則有二叉樹結(jié)點=D0+D1+D2。 ?在完全二叉樹中，若除去最下面一層的結(jié)點，則此時的二叉樹構(gòu)成一個滿二叉樹，其結(jié)點個數(shù)為 （奇數(shù)），而題目中的二叉樹共有2*N-1（奇數(shù)）個結(jié)點，所以可以知道完全二叉樹最下面一層的結(jié)點個數(shù)為偶數(shù)個，得知D1=0。這樣我們只要求出D2，就可以得到D0的值了。 ?接下來，我們來看二叉樹邊的個數(shù)，由于“邊數(shù)=結(jié)點數(shù)-1”（除去根結(jié)點，因為只有它的上面沒有邊），D0結(jié)點（葉節(jié)點）無發(fā)出的邊，D1結(jié)點個數(shù)為0，D2發(fā)出的邊數(shù)為D2*2，所以得到： ? 邊數(shù)=結(jié)點數(shù)-1=D2*2 → 結(jié)點數(shù)=D2*2+1 → ? D2=（結(jié)點數(shù)-1）÷2= (2*N-2)÷2=N-1 ∵ D0+D2=2*N-1 ∴ D0=2*N-1-(N-1)=N ?

4.完全二叉樹的結(jié)點個數(shù)為11，則它的葉結(jié)點個數(shù)為（ ）。（NOIP2005） ?

?A. 4 ? B.3 ? C.5 ? D. 2 ? E. 6?

【答案】E。用上題的結(jié)論。 ?

5.高度為 n 的均衡的二叉樹是指：如果去掉葉結(jié)點及相應(yīng)的樹枝，它應(yīng)該是高度為 n-1 的滿二叉樹。 在這里，樹高等于葉結(jié)點的最大深度，根結(jié)點的深度為 0，如果某個均衡的二叉樹共有 2381 個結(jié)點， 則該樹的樹高為（）。?

?A. 10 ?B. 11 C. 12 D. 13 ?

【答案】B。滿二叉樹的結(jié)點個數(shù)為 （根結(jié)點的深度為1），而這棵二叉樹共有2381個結(jié)點，可以算出上面滿二叉樹的結(jié)點個數(shù)是 =2048-1=2047，故這棵樹有11+1（最下面1層）=12。由于題目中根結(jié)點的深度是從0（一般從1）開始的，所以該樹高12-1=11。 ?

6.遞歸過程或函數(shù)調(diào)用時，處理參數(shù)和返回地址，通常使用一種稱為（）的數(shù)據(jù) 結(jié)構(gòu)。（NOIP2008） ? ?

A．隊列B．多維數(shù)組C．線性表D．棧?

【答案】D。 ?

7.設(shè)T是一棵有n個頂點的樹，下列說法不正確的是（）。（NOIP2008）?

A．T有n條邊B．T是連通的C．T是無環(huán)的D．T有n-1條邊 ?

【答案】A。n個頂點的樹，除了根結(jié)點以外，其余每個結(jié)點上方都連接一條邊，所以一共有n-1條邊。 ?

8.已知7個節(jié)點的二叉樹的先根遍歷是1 2 4 5 6 3 7（數(shù)字為節(jié)點的編號，以 下同），中根遍歷是4 2 6 5 1 7 3，則該二叉樹的后根遍歷是（）。（NOIP2007）

?A．4 6 5 2 7 3 1B．4 6 5 2 1 3 7C．4 2 3 1 5 4 7D．4 6 5 3 1 7 2?

【答案】A。先根遍歷=先序遍歷（根→左→右），中根遍歷=中序遍歷（左→根→右），后根遍歷=后序遍歷（左→右→根）。中序遍歷保證了左子樹的所有結(jié)點在它左邊，右子樹的結(jié)點在它右邊。 ?過程如下：后用先序遍歷結(jié)果，找到父結(jié)點，然后按照中序遍歷結(jié)果將其左右子樹分開；然后再從先序遍歷結(jié)果中再找到左子樹的根結(jié)點，再重復(fù)以上操作??直到所有結(jié)點歸位。 ?先序：1 2 4 5 6 3 7 中序：4 2 6 5 1 7 3?

?① 先序第1個數(shù)字是1（二叉樹根），將中序中1的左半段與右半段分開，即得到1的左子樹是4 2 6 5，右子樹是7 3，表示為（4 2 6 5）1（7 3）。

② 再看1的左子樹4 2 6 5，其對應(yīng)的先序2 4 5 6，此時先序第1個數(shù)字是2（左子樹的根），將中序以2再次劃分為左子樹4，右子樹6 5，表示為（4）2（6 5），如圖2所示。 ?圖2 ? ?圖3 ? 圖4?
③ 2的右子樹中序為6 5，先序為5 6，則2的右子樹的根是5，再看中序，得到（6）5，到這里完成結(jié)點1左子樹的結(jié)構(gòu)，如圖3所示。 ④ 同樣方法構(gòu)建1右子樹，得到（7）3，如圖4所示。 ?

⑤ 依照后序遍歷的特點（左→右→根），得到結(jié)果：4 6 5 2 7 3 1，故答案為A。?

【思考】 ?

（1）已知中序和后序，如何求先序？ ?

（2）已知二叉樹的先序、中序和后序序列分別如下，但其中有一些已模糊不清，試構(gòu)造出該二叉樹。 ?先序序列： _BC_EF__ 中序序列： BDE_AG_H 后序序列： _DC_GH_A

??9.二叉樹T，已知其先根遍歷是1 2 4 3 5 7 6（數(shù)字為節(jié)點的編號，下同）， 中根遍歷2 4 1 5 7 3 6，則該二叉樹的后根遍歷是（）。（NOIP2008） ??

A．4 2 5 7 6 3 1B．4 2 7 5 6 3 1 C．7 4 2 5 6 3 1D．4 2 7 6 5 3 1?

【答案】B。 ?

10.已知 6 個結(jié)點的二叉樹的先根遍歷是 1 2 3 4 5 6（數(shù)字為結(jié)點的編號，以下同），后根遍歷是 3 2 5 6 4 1，則該二叉樹的可能的中根遍歷是（）。（NOIP2006） ??

A. 3 2 1 4 6 5B. 3 2 1 5 4 6 ? C. 2 1 3 5 4 6D. 2 3 1 4 6 5?

【答案】B。先序遍歷和后序遍歷不能確定唯一中序遍歷，對于本題的結(jié)果可以是：2 3 1 5 4 6或者3 2 1 5 4 6。 ??

11.二叉樹T的寬度優(yōu)先遍歷序列為A B C D E F G H I，已知A是C的父結(jié)點，D 是G 的父結(jié)點，F 是I 的父結(jié)點，樹中所有結(jié)點的最大深度為3（根結(jié)點深度設(shè)為0），可知F的父結(jié)點是（ ）。（NOIP2005）?

A. 無法確定B. BC. CD. DE. E

【答案】C。 ?

12.設(shè)棧S的初始狀態(tài)為空，元素a, b, c, d, e 依次入棧，以下出棧序列不可 能出現(xiàn)的有（）。（NOIP2006） ? ??

A. a, b, c, e, dB. b, c, a, e, d ?C. a, e, c, b, dD. d, c, e, b, a ?

【答案】C。選項C中的出棧序列：a,e,c,b,d，a,e出棧，則棧中必是b,c,d（從下往上），出棧序列只能是d,c,b，而不是c,b,d。 ?

13.滿二叉樹的葉節(jié)點為N，則它的節(jié)點總數(shù)為（ ）（NOIP2004）?

A、N ?B、2N C、2N-1 D、2N+1 E、2^N-1 ?

【答案】C。滿二叉樹的結(jié)點個數(shù)為 （根結(jié)點的深度為1），其葉子節(jié)點的個數(shù)為 ，所以“結(jié)點個數(shù)”=“葉子節(jié)點”*2-1=2N-1。

?五、算法 ?

1.近20年來，許多計算機(jī)專家都大力推崇遞歸算法，認(rèn)為它是解決較復(fù)雜問題的強(qiáng)有力的工具。在下列關(guān)于遞歸算法的說法中，正確的是（）。（NOIP2007） ??

A．在1977年前后形成標(biāo)準(zhǔn)的計算機(jī)高級語言“FORTRAN77”禁止在程序使用遞歸，原因之一是該方法可能會占用更多的內(nèi)存空間 ? ?B．和非遞歸算法相比，解決同一個問題，遞歸算法一般運行得更快一些 ? C．對于較復(fù)雜的問題，用遞歸方式編程一般比非遞歸方式更難一些 ? D．對于已經(jīng)定義好的標(biāo)準(zhǔn)數(shù)學(xué)函數(shù) sin(x)，應(yīng)用程序中的語句“y=sin(sin(x));”就是一種遞歸調(diào)用。?

【答案】A。 ?

2.在下列各種排序算法中，不是以“比較”作為主要操作的算法是（）。（NOIP2006） ??

A. 選擇排序B. 冒泡排序C. 插入排序D. 基數(shù)排序 ?

【答案】D。基于“比較”的排序：冒泡、選擇、插入、快速、歸并、堆、希爾等；而“非比較”的排序：計數(shù)排序、桶排序、基數(shù)排序等。

?3.設(shè)字符串S="Olympic"，S的非空子串的數(shù)目是（）。（NOIP2008） ??

A．28B．29C．16D．17

【答案】A。串長為1的子串有7個，串長為2的子串有6個，??，串長為7的子串有1個，共7+6+5+?2+1=28。?

?4.將數(shù)組{8，23，4，16，77，-5，53，100}中的元素按從小到大的順序排列，每次可以交換任意兩個元素，最少需要交換（）次。（NOIP2008） ?

A．4B．5C．6D．7 ?

【答案】B。選擇排序，第1次是將第1個元素與右邊7個元素中最小的一個交換，第2次是將第2個元素與右邊6個元素中最小的一個交換，??。若當(dāng)前元素已是其余元素中最小的，則不需要交換。 ?

5.對有序數(shù)組{ 5，13，19，21，37，56，64，75，88，92，100}進(jìn)行二分查找，成功查找元素19的查找長度（比較次數(shù)）是（ ）。（NOIP2008） ??

A．1B．2C．3D．4 ?

【答案】B。首先與中間元素56比較，比56小，則繼續(xù)在56左側(cè)的5個元素中查找；與這5個元素的中間元素19比較，相等，則找到，所以只需要比較2次。?

6.由3個a，1個b和2個c構(gòu)成的所有字符串中，包含子串“abc”的共有（ ） 個。（NOIP2004）?

A、20B、8C、16D、12E、24 ?

【答案】D。把“abc”看成一個整體，記為d。本題轉(zhuǎn)換為2個a、1個c、1個d進(jìn)行全排列，由于有2個a，所以要除以a的全排列個數(shù)，即 ?。

（持續(xù)更新！！！）

轉(zhuǎn)載于:https://www.cnblogs.com/RainbowCrown/p/11148470.html

總結(jié)

以上是生活随笔為你收集整理的NOIP复习资料——往年习题精选的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。