Noip初賽綜合復(fù)習(xí)(知識(shí)點(diǎn)和例題)第二版

1、1NOIP 初賽復(fù)習(xí)指南第二版知識(shí)點(diǎn)和例題By.褚家言 2017-10-132初賽考的知識(shí)點(diǎn)就是計(jì)算機(jī)基本常識(shí)、基本操作和程序設(shè)計(jì)基礎(chǔ)知識(shí)。其中選擇題考查的是知識(shí)，而問題解決類型的題目更加重視能力的考查。一般說來，選擇題只要多用心積累就可以了。問題解決題目的模式比較固定，大家應(yīng)當(dāng)做做以前的題目。寫運(yùn)行結(jié)果和程序填空也需要多做題目，并且培養(yǎng)良好的程序閱讀和分析能力，就像語文的閱讀理解一樣。近幾年來，初賽的考查范圍有了很大的變化，越來越緊跟潮流了。這就需要大家有比較廣泛的知識(shí)，包括計(jì)算機(jī)硬件、軟件、網(wǎng)絡(luò)、簡單的數(shù)據(jù)結(jié)構(gòu)（例如棧、隊(duì)列、樹和圖等）和簡單的算法（例如排序、查找和搜索等） ，程序設(shè)計(jì)語言

2、以及一些基本的數(shù)學(xué)知識(shí)和技巧。知識(shí)點(diǎn)復(fù)習(xí)：第一部分第一部分 計(jì)算機(jī)基礎(chǔ)知識(shí)計(jì)算機(jī)基礎(chǔ)知識(shí)1. 計(jì)算機(jī)的發(fā)展計(jì)算機(jī)的發(fā)展知識(shí)點(diǎn):1.計(jì)算機(jī)的發(fā)展階段(4 代,標(biāo)志及主要特點(diǎn)) 2.ENIAC,圖靈,馮.諾依曼,Ada Lovelace(第一個(gè)程序員)2. 計(jì)算機(jī)系統(tǒng)計(jì)算機(jī)系統(tǒng)1.計(jì)算機(jī)硬件計(jì)算機(jī)硬件a. 組成:運(yùn)算器,控制器,存儲(chǔ)器,IO 設(shè)備;b. CPU:字長,主頻(時(shí)鐘頻率),總線;c. 存儲(chǔ)器:內(nèi)(ROM,RAM),外存儲(chǔ)器,種類,單位,存取速度;d. 輸入輸出設(shè)備:掃描儀,數(shù)字化儀,繪圖儀,打印機(jī)(種類)2.計(jì)算機(jī)軟件計(jì)算機(jī)軟件:a. BIOS (功能);b.系統(tǒng)軟件(包括操作系統(tǒng):D

3、OS,LINUX,UNIX,WINDOWS,OS/2,MAC/OS 和語言的解釋或編譯程序);解釋程序:高級(jí)語言翻譯的一種,它將源語言(如 basic)書寫的源程序作為輸入,解釋一句后就提交計(jì)算機(jī)執(zhí)行一句,并不形成目標(biāo)程序.翻譯程序: (編譯程序)一類很重要的語言處理程序,它把高級(jí)語言(如 FORTRAN,COBOL,pascal,c 等)源程序作為輸入,進(jìn)行翻譯轉(zhuǎn)換,產(chǎn)生出機(jī)器語言的目標(biāo)程序,然后再讓計(jì)算機(jī)去執(zhí)行這個(gè)目標(biāo)程序,得到計(jì)算結(jié)果.語言:機(jī)器語言 匯編語言 高級(jí)語言(面向?qū)ο?面向過程)c.應(yīng)用軟件數(shù)據(jù)庫管理軟件:Foxpro，Access，Orale，Sybase，DB2 和 In

4、formix 等。字處理軟件: WPS, word3.計(jì)算機(jī)的主要性能指標(biāo)計(jì)算機(jī)的主要性能指標(biāo)1. 字長2. 速度3. 存儲(chǔ)系統(tǒng)容量(bit,B,KB,MB,GB,TB)3. 數(shù)據(jù)在計(jì)算機(jī)中的表示數(shù)據(jù)在計(jì)算機(jī)中的表示1.數(shù)值的表示:二進(jìn)制,八進(jìn)制,十六進(jìn)制,十進(jìn)制(包括小數(shù)部分的轉(zhuǎn)化)原碼,反碼,補(bǔ)碼的表示2.字符的表示: ASCII 碼(128 個(gè))0-48 A-65 a-97 漢字的表示: 2 個(gè)字節(jié)(Byte) :機(jī)內(nèi)碼,輸入碼,字型碼3.圖像的表示4.聲音的表示4.計(jì)算機(jī)的維護(hù)與使用安全計(jì)算機(jī)的維護(hù)與使用安全1. 計(jì)算機(jī)的維護(hù)與安全使用常識(shí)(電源,溫度,濕度,開關(guān)機(jī))2. 計(jì)算機(jī)病毒的

5、預(yù)防與消除(何謂病毒,病毒的特點(diǎn),殺毒方式及軟件)3第二部分第二部分 計(jì)算機(jī)網(wǎng)絡(luò)計(jì)算機(jī)網(wǎng)絡(luò)1.計(jì)算機(jī)網(wǎng)絡(luò)的定義計(jì)算機(jī)網(wǎng)絡(luò)的定義: 計(jì)算機(jī)網(wǎng)絡(luò)計(jì)算機(jī)網(wǎng)絡(luò)，就是把分布在不同地理區(qū)域的計(jì)算機(jī)與專門的外部設(shè)備用通信線路互連成一個(gè)規(guī)模大、功能強(qiáng)的網(wǎng)絡(luò)系統(tǒng)，從而使眾多的計(jì)算機(jī)可以方便地互相傳遞信息，共享信息資源。2.計(jì)算機(jī)網(wǎng)絡(luò)名詞計(jì)算機(jī)網(wǎng)絡(luò)名詞: ISP: 因特網(wǎng)服務(wù)提供商,能提供撥號(hào)上網(wǎng)服務(wù)、網(wǎng)上瀏覽、下載文件、收發(fā)電子郵件等服務(wù)。即為用戶提供 Internet 接人和(或)Internet 信息服務(wù)的公司和機(jī)構(gòu)。如”中國電信”等;DNS: 域名服務(wù)器;FTP: 文件傳輸協(xié)議;HTTP:超文本傳輸協(xié)議;

6、SMTP:簡單郵件系統(tǒng)傳輸協(xié)議;WWW: 萬維網(wǎng);POP3: 郵件傳輸協(xié)議ARP: 地址解析協(xié)議3.兩種網(wǎng)絡(luò)參考模型兩種網(wǎng)絡(luò)參考模型OSI 開放式系統(tǒng)互聯(lián)模型參考模型開放式系統(tǒng)互聯(lián)模型參考模型: (七層七層)由下到上:物理層、數(shù)據(jù)鏈路層、網(wǎng)絡(luò)層、傳輸層、會(huì)話層、表示層、應(yīng)用層； TCP/IP 參考模型參考模型(五層五層)由下到上:、物理層、數(shù)據(jù)鏈路層，互聯(lián)網(wǎng)層、傳輸層、應(yīng)用層4.網(wǎng)絡(luò)軟件網(wǎng)絡(luò)軟件1.計(jì)算機(jī)協(xié)議計(jì)算機(jī)協(xié)議: (TCP/IP)a. TCP : Transfer Control Protocol,傳輸控制協(xié)議傳輸控制協(xié)議b. IP: Internet Protocol,網(wǎng)際協(xié)議網(wǎng)際協(xié)

7、議c. 三類 IP 地址: IPV42.應(yīng)用軟件應(yīng)用軟件:5.網(wǎng)絡(luò)硬件網(wǎng)絡(luò)硬件(網(wǎng)卡網(wǎng)卡, MODEM,光纖光纖,雙絞線雙絞線,同軸電纜同軸電纜,無線信道無線信道)6.網(wǎng)絡(luò)分類網(wǎng)絡(luò)分類 計(jì)算機(jī)網(wǎng)絡(luò)的類型有很多，而且有不同的分類依據(jù)。計(jì)算機(jī)網(wǎng)絡(luò)的類型有很多，而且有不同的分類依據(jù)。 按拓?fù)浣Y(jié)構(gòu)按拓?fù)浣Y(jié)構(gòu):總線型、星型、環(huán)形、樹形 按地域按地域:局域網(wǎng)、城域網(wǎng)、廣域網(wǎng)和網(wǎng)間網(wǎng)7.域名的表示域名的表示 http:/第三部分第三部分 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)1.簡單數(shù)據(jù)類型簡單數(shù)據(jù)類型:a 數(shù)值數(shù)值: integer, real, longintb 字符字符: charc 布爾類型布爾類型: Booleand

8、數(shù)組數(shù)組:一維一維,二維二維e 字符串字符串: string2.線性表線性表?xiàng)?、?duì)列棧、隊(duì)列3.樹樹二叉樹、哈弗曼樹4.圖圖圖的最小生成樹、最短路徑4第四部分第四部分 基本及常用算法基本及常用算法第五部分第五部分 問題求解問題求解隊(duì)列、棧、二叉樹等數(shù)據(jù)結(jié)構(gòu)、數(shù)學(xué)問題、歸納法、數(shù)列和邏輯推理、排列組合等題型歸類：題型歸類：第一部分：選擇題（第一部分：選擇題（3030 分分=20*1.5=20*1.5）一般是比較容易得分的，不可錯(cuò)過！程序設(shè)計(jì)方面的知識(shí)多是平時(shí)計(jì)算機(jī)課堂教學(xué)或課外活動(dòng)中學(xué)到的，建議大家找全國計(jì)算機(jī)等級(jí)考試（一、二級(jí)）的題目做做，一般不超過二級(jí)的知識(shí)點(diǎn)，知識(shí)要復(fù)習(xí)的系統(tǒng)一些。新大綱和

9、最近兩年的考試不再考DOS，但有 DOS 經(jīng)驗(yàn)的選手可能會(huì)占一點(diǎn)便宜，因?yàn)橛行╊}目可以根據(jù)經(jīng)驗(yàn)判斷。另外，往更高層次發(fā)展的過程中，必要的 DOS 知識(shí)和命令還是必須的。類型類型 1 1：計(jì)算機(jī)原理：計(jì)算機(jī)原理：NOIP1999：1、微機(jī)內(nèi)的存儲(chǔ)器的地址是以( C )編址的。A. 二進(jìn)制位 B. 字長 C. 字節(jié) D. 微處理器的型號(hào)2、下列諸因素中,對(duì)微機(jī)工作影響最小的是 ( B )A. 塵土 B. 噪聲 C. 溫度 D. 濕度3、在 24*24 點(diǎn)陣的字庫中，漢字“一 ”與“編”的字模占用字節(jié)數(shù)分別是（ C ）A. 32、32 B. 32、72 C. 72、72 D. 72、32 7、計(jì)算機(jī)

10、能直接執(zhí)行的指令包括兩部分,它們是（ B ）A. 源操作數(shù)與目標(biāo)操作數(shù) B. 操作碼與操作數(shù) C. ASC碼與漢字代碼 D. 數(shù)字與字符8、在微機(jī)中，通用寄存器的位數(shù)是 （ C ）A. 8 位 B. 16 位 C. 計(jì)算機(jī)字長 D. 32 位 9、在計(jì)算機(jī),字符編碼通常采用( C )A. 原碼 B. 反碼 C. ASCII 碼 D. 補(bǔ)碼13、已知小寫字母“M”的十六進(jìn)制的 ASC碼值是 6D，則小寫字母“C”的十六進(jìn)制數(shù)的 ASC碼值是 （ D ）A. 98 B. 62 C. 99 D. 63 14、計(jì)算機(jī)中的數(shù)有浮點(diǎn)與定點(diǎn)數(shù)兩種，其中用浮點(diǎn)數(shù)表示的數(shù)，通常由（ C ）這兩部分組成。 A.

11、指數(shù)與基數(shù) B. 尾數(shù)與小數(shù) C. 階碼與尾數(shù) D. 整數(shù)與小數(shù)16、啟動(dòng)計(jì)算機(jī)引導(dǎo) DOS 是將操作系統(tǒng) ( D ) A. 從磁盤調(diào)入中央處理器 B. 從內(nèi)存儲(chǔ)器調(diào)入高速緩沖存儲(chǔ)器 C. 從軟盤調(diào)入硬盤 D. 從系統(tǒng)盤調(diào)入內(nèi)存儲(chǔ)器18、組成“教授” （JIAO SHOU）,“副教授” （FU JIAO SHOU）與“講師”(JIANG SHI)這三個(gè)詞的漢字，在GB2312-80 字符集中都是一級(jí)漢字，對(duì)這三個(gè)詞排序的結(jié)果是（ D ） A. 教授、副教授、講師 B. 副教授、教授、講師 C. 講師、副教授、教授 D. 副教授、講師、教授19、不同的計(jì)算機(jī)，其指令系統(tǒng)也不相同，這主要取決于 （

12、 C ） A. 所用的操作系統(tǒng) B. 系統(tǒng)的總體結(jié)構(gòu) C. 所用的 CPU D. 所用的程序設(shè)計(jì)語言NOIP2000：58.計(jì)算機(jī)系統(tǒng)總線上傳送的信號(hào)有（B）A.地址信號(hào)與控制信號(hào)B. 數(shù)據(jù)信號(hào)、控制信號(hào)與地址信號(hào)C.控制信號(hào)與數(shù)據(jù)信號(hào)D. 數(shù)據(jù)信號(hào)與地址信號(hào)9.計(jì)算機(jī)的運(yùn)算速度取決于給定的時(shí)間內(nèi)，它的處理器所能處理的數(shù)據(jù)量。處理器一次能處理的數(shù)據(jù)量叫字長。 已知 64 位的奔騰處理器一次能處理 64 個(gè)信息位，相當(dāng)于（A）字節(jié)。A.8 個(gè)B.1 個(gè)C.16 個(gè)D. 2 個(gè)14.不同類型的存儲(chǔ)器組成了多層次結(jié)構(gòu)的存儲(chǔ)器體系，按存取速度從快到慢的排列是（C）A.快存/輔存/主存B. 外存/主存/

13、輔存C. 快存/主存/輔存D. 主存/輔存/外存NOIP2001：1、中央處理器 CPU 能訪問的最大存儲(chǔ)器容量取決于( A )A)地址總線 B)數(shù)據(jù)總線 C)控制總線 D)內(nèi)存容量7、若我們說一個(gè)微機(jī)的 CPU 是用的 PII300，此處的 300 確切指的是( A )A)CPU 的主時(shí)鐘頻率 B)CPU 產(chǎn)品的系列號(hào)C)每秒執(zhí)行 300 百萬條指令 D)此種 CPU 允許最大內(nèi)存容量NOIP2002：1 微型計(jì)算機(jī)的問世是由于（ C ）的出現(xiàn)。A）中小規(guī)模集成電路 B）晶體管電路 C） （超）大規(guī)模集成電路 D）電子管電路2 中央處理器（CPU）能訪問的最大存儲(chǔ)器容量取決于（ A ） 。A

14、）地址總線 B）數(shù)據(jù)總線 C）控制總線 D）實(shí)際內(nèi)存容量11微型計(jì)算機(jī)中， （ C ）的存取速度最快。A）高速緩存 B）外存儲(chǔ)器 C）寄存器 D）內(nèi)存儲(chǔ)器14一個(gè)向量第一個(gè)元素的存儲(chǔ)地址是 100，每個(gè)元素的長度是 2，則地 5 個(gè)元素的地址是（ B ） 。A）110 B）108 C）100 D）109NOIP2003：1. 圖靈 (Alan Turing) 是 （ B ） 。 A） 美國人 B） 英國人 C） 德國人 D） 匈牙利人 E） 法國人2. 第一個(gè)給計(jì)算機(jī)寫程序的人是（ B ） 。 A） Alan Mathison Turing B） Ada Lovelace C） John vo

15、n Neumann D） John Mc-Carthy E） Edsger Wybe Dijkstra11. 下列分辨率的顯示器顯示出的圖像，最清晰的是（ D ） 。 A） 800*600 B） 1024*768 C） 640*480 D） 1280*1024 E） 800*100012. 下列說法中，哪個(gè)（些）是錯(cuò)誤的（ BDE ） 。 A）程序是指令的序列，它有三種結(jié)構(gòu)：順序、分支和循環(huán)。 B）數(shù)據(jù)總線決定了中央處理器 CPU 所能訪問的最大內(nèi)存空間的大小。 C）中央處理器 CPU 內(nèi)部有寄存器組，用來儲(chǔ)存數(shù)據(jù)。 D）不同廠家生產(chǎn)的 CPU 所能處理的指令集是相同的。 E）數(shù)據(jù)傳輸過程中可

16、能會(huì)出錯(cuò)，奇偶校驗(yàn)法可以檢測出數(shù)據(jù)中那一為在傳輸中出了差錯(cuò)。17. 下列哪個(gè)（些）不是個(gè)人計(jì)算機(jī)的硬件組成部分（ B ） 。 A）主板 B）虛擬內(nèi)存 C）電源 D）硬盤 E）總線NOIP2004：7.下面哪個(gè)部件對(duì)于個(gè)人桌面電腦的正常運(yùn)行不是必需的（ C ） 。A.CPU B. 圖形卡（顯卡） C. 光驅(qū) D. 主板 E. 內(nèi)存11. 美籍匈牙利數(shù)學(xué)家馮諾依曼對(duì)計(jì)算機(jī)科學(xué)發(fā)展所做出的貢獻(xiàn)包括（ BC ） 。A.提出理想計(jì)算機(jī)的數(shù)學(xué)模型，成為計(jì)算機(jī)科學(xué)的理論基礎(chǔ)。B.提出存儲(chǔ)程序工作原理，對(duì)現(xiàn)代電子計(jì)算機(jī)的發(fā)展產(chǎn)生深遠(yuǎn)影響。C.設(shè)計(jì)出第一臺(tái)具有存儲(chǔ)程序功能的計(jì)算機(jī) EDVAC。6D.采用集成電路

17、作為計(jì)算機(jī)的主要功能部件。E.指出計(jì)算機(jī)性能將以每兩年翻一番的速度向前發(fā)展。12. 下列哪個(gè)（些）是 64 位處理器（ ACDE ） 。A. Intel Itanium B. Intel Pentium III C. AMD Athlon64D. AMD Opteron E. IBM Power 515. 下列哪個(gè)（些）不是計(jì)算機(jī)的存儲(chǔ)設(shè)備（ AC ） 。A. 文件管理器 B. 內(nèi)存 C. 顯卡 D. 硬盤 E. U 盤18. 彩色顯示器所顯示的五彩斑斕的色彩，是由哪三色混合而成的（ ACD ） 。A. 紅 B. 白 C. 藍(lán) D. 綠 E. 橙NOIP2005：7. Intel 的首顆 64

18、 位處理器是（ E ） 。A. 8088 B. 8086 C. 80386 D. 80486 E. Pentium18. 以下斷電之后將不能保存數(shù)據(jù)的有（ BCDE ） 。A. 硬盤 B. 寄存器 C. 顯存 D. 內(nèi)存 E. 高速緩存20. 下列關(guān)于高級(jí)語言的說法正確的有（ BDE ） 。A. Ada 是歷史上的第一個(gè)高級(jí)語言B. Pascal 和 C 都是編譯執(zhí)行的高級(jí)語言C. C+是歷史上的第一個(gè)支持面向?qū)ο蟮恼Z言D. 編譯器將高級(jí)語言程序轉(zhuǎn)變?yōu)槟繕?biāo)代碼E. 高級(jí)語言程序比匯編語言程序更容易從一種計(jì)算機(jī)移植到另一種計(jì)算機(jī)上NOIP2006：1. 在以下各項(xiàng)中。 （ E ）不是 CPU 的

19、組成部分。A. 控制器B. 運(yùn)算器C. 寄存器D. ALU E. RAM2. BIOS（基本輸入輸出系統(tǒng)）是一組固化在計(jì)算機(jī)內(nèi)（ C ）上一個(gè) ROM 芯片上的程序。A. 控制器B. CPUC. 主板 D. 內(nèi)存條E. 硬盤18. 在下列關(guān)于計(jì)算機(jī)語言的說法中，正確的有（ AB ） 。A. Pascal 和 C 都是編譯執(zhí)行的高級(jí)語言B. 高級(jí)語言程序比匯編語言程序更容易從一種計(jì)算機(jī)移植到另一種計(jì)算機(jī)上C. C+是歷史上的第一個(gè)支持面向?qū)ο蟮挠?jì)算機(jī)語言D. 高級(jí)語言比匯編語言更高級(jí)，是因?yàn)樗某绦虻倪\(yùn)行效率更高NOIP2007：1. 在以下各項(xiàng)中。 （ D ）不是 CPU 的組成部分。 A.

20、控制器 B. 運(yùn)算器 C. 寄存器 D. 主板 E. 算術(shù)邏輯單元(ALU) 3.在下列各項(xiàng)中，只有（ D ）不是計(jì)算機(jī)存儲(chǔ)容量的常用單位。 A. Byte B. KB C. MB D. UB E. TB 4ASCII 碼的含義是（ B ） 。 A. 二十進(jìn)制轉(zhuǎn)換碼 B. 美國信息交換標(biāo)準(zhǔn)代碼 C. 數(shù)字的二進(jìn)制數(shù)碼 D. 計(jì)算機(jī)可處理字符的唯一編碼 E. 常用字符的二進(jìn)制編碼 20. 近 20 年來， 許多計(jì)算機(jī)專家都大力推崇遞歸算法，認(rèn)為它是解決較復(fù)雜問題的強(qiáng)有力的工具. 在下列關(guān)于遞歸的說法中， 正確的是（ AC ） 。 A. 在 1977 年前后形成標(biāo)準(zhǔn)的計(jì)算機(jī)高級(jí)語言FORTRAN7

21、7禁止在程序使用遞歸， 原因之一是該方法可能會(huì)占用更多的內(nèi)存空間. B. 和非遞歸算法相比， 解決同一個(gè)問題， 遞歸算法一般運(yùn)行得更快一些 C. 對(duì)于較復(fù)雜的問題， 用遞歸方式編程往往比非遞歸方式更容易一些 D. 對(duì)于已定義好的標(biāo)準(zhǔn)數(shù)學(xué)函數(shù) sin(x)， 應(yīng)用程序中的語句“y=sin(sin(x);”就是一種遞歸調(diào)用NOIP2008：71. 在以下各項(xiàng)中， （ C ）不是操作系統(tǒng)軟件。A. Solaris B. Linux C. Sybase D. Windows Vista E. Symbian11. 在下列關(guān)于圖靈獎(jiǎng)的說法中，正確的有（ ABD ） 。A. 圖靈獎(jiǎng)是美國計(jì)算機(jī)協(xié)會(huì)于 19

22、66 年設(shè)立的，專門獎(jiǎng)勵(lì)那些對(duì)計(jì)算機(jī)事業(yè)作出重要貢獻(xiàn)的個(gè)人B. 圖靈獎(jiǎng)有“計(jì)算機(jī)界諾貝爾獎(jiǎng)”之稱C. 迄今為止，還沒有華裔計(jì)算機(jī)科學(xué)家獲此殊榮D. 圖靈獎(jiǎng)的名稱取自計(jì)算機(jī)科學(xué)的先驅(qū)、英國科學(xué)家阿蘭圖靈NOIP2009：2、關(guān)于 BIOS 下面的說法哪個(gè)是正確的：AA)BIOS 是計(jì)算機(jī)基本輸入輸出系統(tǒng)軟件的簡稱。B)BIOS 里包含了鍵盤、鼠標(biāo)、聲卡、圖形界面顯器等常用輸入輸出設(shè)備的驅(qū)動(dòng)程序。C)BIOS 一般由操作系統(tǒng)廠商來開發(fā)完成。D)BIOS 能提供各種文件拷貝、復(fù)制、刪除以及目錄維護(hù)等文件管理功能。3、已知大寫字母 A 的 ASCII 編碼為 65（十進(jìn)制） ，則大寫字母 J 的 十六

23、進(jìn)制 ASCII 編碼為：DA) 48 B) 49 C) 50 D) 以上都不是類型類型 2 2：操作系統(tǒng)與應(yīng)用軟件：操作系統(tǒng)與應(yīng)用軟件：NOIP1999：10、計(jì)算機(jī)的軟件系統(tǒng)通常分為 （ A ） A. 系統(tǒng)軟件與應(yīng)用軟件 B. 高級(jí)軟件與一般軟件 C. 軍用軟件與民用軟件 D. 管理軟件與控制軟件NOIP2000：4.計(jì)算機(jī)病毒的特點(diǎn)是（C）A. 傳播性、潛伏性、易讀性與隱蔽性B. 破壞性、傳播性、潛伏性與安全性C. 傳播性、潛伏性、破壞性與隱蔽性D. 傳播性、潛伏性、破壞性與易讀性5.WINDOWS 9X 是一種（D）操作系統(tǒng)A. 單任務(wù)字符方式B. 單任務(wù)圖形方式C. 多任務(wù)字符方式D

24、. 多任務(wù)圖形方式7.計(jì)算機(jī)網(wǎng)絡(luò)是一個(gè)（D）系統(tǒng)A.管理信息系統(tǒng)B.管理數(shù)據(jù)系統(tǒng)C.編譯系統(tǒng)D. 在協(xié)議控制下的多機(jī)互連系統(tǒng)NOIP2001：4、在樹型目錄結(jié)構(gòu)中，不允許兩個(gè)文件名相同主要指的是( D )A)同一個(gè)磁盤的不同目錄下 B)不同磁盤的同一個(gè)目錄下C)不同磁盤的不同目錄下 C)同一個(gè)磁盤的同一個(gè)目錄下10、以下對(duì) Windows 的敘述中，正確的是( A )A)從軟盤上刪除的文件和文件夾，不送到回收站B)在同一個(gè)文件夾中，可以創(chuàng)建兩個(gè)同類、同名的文件C)刪除了某個(gè)應(yīng)用程序的快捷方式，將刪除該應(yīng)用程序?qū)?yīng)的文件D)不能打開兩個(gè)寫字板應(yīng)用程序NOIP2002：7 計(jì)算機(jī)病毒傳染的必要條件

25、是：（ B ） 。 A）在內(nèi)存中運(yùn)行病毒程序 B）對(duì)磁盤進(jìn)行讀寫操作C）在內(nèi)存中運(yùn)行含有病毒的可執(zhí)行的程序 D）復(fù)制文件8 在磁盤上建立子目錄有許多優(yōu)點(diǎn)，下列描述中不屬于建立子目錄優(yōu)點(diǎn)的是（ D ） 。 A）便于文件管理 B）解決根目錄中目錄項(xiàng)個(gè)數(shù)有限問題C）加快文件查找速度 D）節(jié)省磁盤使用空間12資源管理器的目錄前圖標(biāo)中增加“+”號(hào)，這個(gè)符號(hào)的意思是（ B ） 。8A）該目錄下的子目錄已經(jīng)展開 B）該目錄下還有子目錄未展開C）該目錄下沒有子目錄 D）該目錄為空目錄13在 WORD 文檔編輯中實(shí)現(xiàn)圖文混合排版時(shí)，關(guān)于文本框的下列敘述正確的是（ C ） 。A）文本框中的圖形沒有辦法和文檔中輸入

26、文字疊加在一起，只能在文檔的不同位置B）文本框中的圖形不可以襯于文檔中輸入的文字的下方C）通過文本框，可以實(shí)現(xiàn)圖形和文檔中輸入的文字的疊加，也可以實(shí)現(xiàn)文字環(huán)繞D）將圖形放入文本框后，文檔中輸入的文字不能環(huán)繞圖形NOIP2004：14. 下列哪個(gè)（些）不是數(shù)據(jù)庫軟件的名稱（ D ） 。A. MySQL B. SQL Server C. Oracle D. Outlook E. Foxpro16. 下列哪個(gè)（些）軟件屬于操作系統(tǒng)軟件（ BE ） 。A. Microsoft Word B. Windows XP C. Foxmail D. 金山影霸 E. Red Hat Linux19. 下列哪個(gè)（

27、些）程序設(shè)計(jì)語言支持面向?qū)ο蟪绦蛟O(shè)計(jì)方法（ ABDE ） 。A. C+ B. Object Pascal C. C D. Smalltalk E. JavaNOIP2006：15. 下列外設(shè)接口中可以通過無線連接的方式連接設(shè)備的是（ ABCD ） 。A. USB 2.0 高速版 B. 紅外 C. 藍(lán)牙 D. 串口 E. IEEE 802.11g 無線網(wǎng)卡類型類型 3 3：多媒體與網(wǎng)絡(luò)：多媒體與網(wǎng)絡(luò)：NOIP2000：11.下面哪些計(jì)算機(jī)網(wǎng)絡(luò)不是按覆蓋地域劃分的（A）A.局域網(wǎng)B. 都市網(wǎng)C.廣域網(wǎng)D. 星型網(wǎng)NOIP2001：12、TCP/IP 協(xié)議共有( C )層協(xié)議A)3 B)4 C)5

28、D)6 NOIP2002：9 在使用 E-mail 前，需要對(duì) Outlook 進(jìn)行設(shè)置，其中 ISP 接收電子郵件的服務(wù)器稱為（ A ）服務(wù)器。 A）POP3 B）SMTP C）DNS D）FTP10多媒體計(jì)算機(jī)是指（ D ）計(jì)算機(jī)。A）專供家庭使用的 B）裝有 CD-ROM 的NOIP2004：8.下列哪個(gè)網(wǎng)絡(luò)上常用的名字縮寫是錯(cuò)誤的（ D ） 。A.WWW（World Wide Web）B.URL（Uniform Resource Locator）C.HTTP（Hypertext Transfer Protocol）D.FTP（Fast Transfer Protocol）E.TCP（T

29、ransfer Control Protocol） 。10. 一臺(tái)計(jì)算機(jī)如果要利用電話線上網(wǎng)，就必須配置能夠?qū)?shù)字信號(hào)和模擬信號(hào)進(jìn)行相互轉(zhuǎn)換的設(shè)備，這種設(shè)備是（ A ） 。A. 調(diào)制解調(diào)器 B. 路由器 C. 網(wǎng)卡 D. 網(wǎng)關(guān) E. 網(wǎng)橋NOIP2005：8. 常見的郵件傳輸服務(wù)器使用（ B ）協(xié)議發(fā)送郵件。A. HTTP B. SMTP C. TCP D. FTP E. POP39. 不能在 Linux 上使用的網(wǎng)頁瀏覽器是（ A ） 。A. Internet Explore B. Netscape C. Opera D. Firefox E. MozillaNOIP2008：914Web2

30、.0 是近年來互聯(lián)網(wǎng)的熱門概念之一，其核心思想是互動(dòng)與分享。下列網(wǎng)站中， （ B ）是典型的Web2.0 應(yīng)用。 A. Sina B. Flickr C. Yahoo D. Google4、關(guān)于計(jì)算機(jī)網(wǎng)絡(luò)，下面的說法哪些是正確的：CA)網(wǎng)絡(luò)協(xié)議之所以有很多層主要是由于新技術(shù)需要兼容過去老的實(shí)現(xiàn)方案。B)新一代互聯(lián)網(wǎng)使用的 IPv6 標(biāo)準(zhǔn)是 IPv5 標(biāo)準(zhǔn)的升級(jí)與補(bǔ)充。C)TCP/IP 是互聯(lián)網(wǎng)的基礎(chǔ)協(xié)議簇，包含有 TCP 和 IP 等網(wǎng)絡(luò)與傳輸層的通訊協(xié)議。D)互聯(lián)網(wǎng)上每一臺(tái)入網(wǎng)主機(jī)通常都需要使用一個(gè)唯一的 IP 地址，否則就必須注冊(cè)一個(gè)固定的域名來標(biāo)明其地址。5、關(guān)于 HTML 下面哪些說法

31、是正確的：BDA)HTML 全稱超文本標(biāo)記語言，實(shí)現(xiàn)了文本、圖形、聲音乃至視頻信息的統(tǒng)一編碼。B)HTML 不單包含有網(wǎng)頁內(nèi)容信息的描述，同時(shí)也包含對(duì)網(wǎng)頁格式信息的定義。C)網(wǎng)頁上的超鏈接只能指向外部的網(wǎng)絡(luò)資源，本網(wǎng)站網(wǎng)頁間的聯(lián)系通過設(shè)置標(biāo)簽來實(shí)現(xiàn)。D)點(diǎn)擊網(wǎng)頁上的超鏈接從本質(zhì)上就是按照該鏈接所隱含的統(tǒng)一資源定位符（URL）請(qǐng)求網(wǎng)絡(luò)資源或網(wǎng)絡(luò)服務(wù)。類型類型 4 4：數(shù)據(jù)結(jié)構(gòu)與算法：數(shù)據(jù)結(jié)構(gòu)與算法：NOIP2000：12.在有 N 個(gè)葉子節(jié)點(diǎn)的哈夫曼樹中，其節(jié)點(diǎn)總數(shù)為（B）A.不確定B. 2N-1C. 2N+1D. 2N解法一解法一: 設(shè)葉子節(jié)點(diǎn)個(gè)數(shù)為 n，度為 1 的節(jié)點(diǎn)個(gè)數(shù)為 m，度為 2

32、的節(jié)點(diǎn)個(gè)數(shù)為 l.顯然易知：一顆二叉樹的節(jié)點(diǎn)數(shù) 這個(gè)樹的度加 1（因?yàn)槊總€(gè)節(jié)點(diǎn)都是前一個(gè)節(jié)點(diǎn)的度，根節(jié)點(diǎn)除外，所以要加 1） 故有 l + m + n = 2l + m + 1- n = l + 1由于哈夫曼樹沒有度為 1 的節(jié)點(diǎn)，在 m 0總節(jié)點(diǎn) n m l 2n 1解法二解法二: 第 1 次必定是 2 個(gè)葉子組成二叉樹，產(chǎn)生 1 新結(jié)點(diǎn)，接下來有 2 種情況：1.此新結(jié)點(diǎn)與原剩下的葉子再組成二叉樹又產(chǎn)生 1 新結(jié)點(diǎn)，這樣就只有第 1 次時(shí)由 2 個(gè)葉子產(chǎn)生 1 新結(jié)點(diǎn)，以后每次由 1 葉子與新結(jié)點(diǎn)產(chǎn)生新結(jié)點(diǎn)，故 n 個(gè)葉子共有 2n-1 個(gè)結(jié)點(diǎn)。2.剩下的葉子中又有 2 個(gè)葉子(比第 1

33、次產(chǎn)生的新結(jié)點(diǎn)權(quán)小)結(jié)合產(chǎn)生新結(jié)點(diǎn)，其它類似，那么必然會(huì)由 2個(gè)都是新結(jié)點(diǎn)再產(chǎn)生新結(jié)點(diǎn)，所以實(shí)際上數(shù)量與第 1 種一樣，共有 2n-1 個(gè)。具體證明用一個(gè)構(gòu)造哈夫曼樹的算法。13.已知數(shù)組中 A 中，每個(gè)元素 A（I，J）在存貯時(shí)要占 3 個(gè)字節(jié)，設(shè) I 從 1 變化到 8，J 從 1 變化到 10，分配內(nèi)存時(shí)是從地址 SA 開始連續(xù)按行存貯分配的。試問：A（5，8）的起始地址為（A）A.SA+141B. SA+180C. SA+222D. SA+22515.某數(shù)列有 1000 個(gè)各不相同的單元，由低至高按序排列；現(xiàn)要對(duì)該數(shù)列進(jìn)行二分法檢索（binary-search） ，在最壞的情況下，需檢

34、視（B）個(gè)單元。A.1000B. 10C. 100D. 500NOIP2001：13.若已知一個(gè)棧的入棧順序是 1，2，3，n，其輸出序列為 P1，P2，P3，Pn，若 P1 是 n，則 Pi 是(C) A)i B)n-1 C)n-i+1 D)不確定15.下面關(guān)于算法的錯(cuò)誤說法是( B )A)算法必須有輸出 B)算法必須在計(jì)算機(jī)上用某種語言實(shí)現(xiàn)10C)算法不一定有輸入 D)算法必須在有限步執(zhí)行后能結(jié)束17.以下哪一個(gè)不是棧的基本運(yùn)算( B)A)刪除棧頂元素 B)刪除棧底的元素 C)判斷棧是否為空 D)將棧置為空棧18.在順序表(2，5，7，10，14，15，18，23，35，41，52)中，用

35、二分法查找 12，所需的關(guān)鍵碼比較的次數(shù)為( C)A)2 B)3 C)4 D)519.一棵二叉樹的高度為 h，所有結(jié)點(diǎn)的度為 0，或?yàn)?2，則此樹最少有( B)個(gè)結(jié)點(diǎn)A)2h-1 B)2h-1 C)2h+1 D)h+120.無向圖 G=(V，E)，其中 V=a,b,c,d,e,f E=(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d) 對(duì)該圖進(jìn)行深度優(yōu)先遍歷,得到的頂點(diǎn)序列正確的是(D) A)a,b,e,c,d,fB)a,c,f,e,b,dC)a,e,b,c,f,dD)a,b,e,d,f,cNOIP2002：17按照二叉數(shù)的定義，具有 3 個(gè)結(jié)點(diǎn)的二叉樹有（ C

36、 ）種。 A）3 B）4 C）5 D）618在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的（ B ）倍。A） 1/2 B）1 C）2 D）4解析: 在有向圖的鄰接表中，從一頂點(diǎn)出發(fā)的弧鏈接在同一鏈表中，鄰接表中結(jié)點(diǎn)的個(gè)數(shù)恰為圖中弧的數(shù)目，所以頂點(diǎn)入度之和為弧數(shù)和的一倍，若為無向圖，同一條邊有兩個(gè)結(jié)點(diǎn)，分別出現(xiàn)在和它相關(guān)的兩個(gè)頂點(diǎn)的鏈表中，因此無向圖的鄰接表中結(jié)點(diǎn)個(gè)數(shù)的邊數(shù)的 2 倍19要使 1 8 號(hào)格字的訪問順序?yàn)椋?、2、6、5、7、3、1、4，則下圖中的空格中應(yīng)填入（ C ） 。12345678461-1732A）6 B）0 C）5 D）3NOIP2003：5. 一個(gè)高度為

37、h 的二叉樹最小元素?cái)?shù)目是（ B ） 。 A） 2h+1 B） h C） 2h-1 D） 2h E） 2h-16. 已知隊(duì)列（13，2，11，34，41，77，5，7，18，26，15） ，第一個(gè)進(jìn)入隊(duì)列的元素是 13，則第五個(gè)出隊(duì)列的元素是（ B ） 。 A） 5 B） 41 C） 77 D） 13 E） 1819. 已知元素（8，25，14，87，51，90，6，19，20） ，問這些元素以怎樣的順序進(jìn)入棧，才能使出棧的順序滿足：8 在 51 前面；90 在 87 的后面；20 在 14 的后面；25 在 6 的前面；19 在 90 的后面。 （ D ） 。 A）20，6，8，51，90，

38、25，14，19，87 B）51，6，19，20，14，8，87，90，25 C）19，20，90，8，6，25，51，14，87 D）6，25，51，8，20，19，90，87，14 E）25，6，8，51，87，90，19，14，2020. 假設(shè)我們用 d=(a1,a2,a5),表示無向圖 G 的 5 個(gè)頂點(diǎn)的度數(shù)，下面給出的哪（些）組 d 值合理（ BE ） 。 A）5，4，4，3，1 B）4，2，2，1，1 C）3，3，3，2，2 D）5，4，3，2，1 E）2，2，2，2，2NOIP2004：3.某個(gè)車站呈狹長形，寬度只能容下一臺(tái)車，并且只有一個(gè)出入口。已知某時(shí)刻該車站狀態(tài)為空，從這

39、一時(shí)刻開始的出入記錄為：“進(jìn)，出，進(jìn)，進(jìn)，出，進(jìn)，進(jìn)，進(jìn)，出，出，進(jìn)，出” 。假設(shè)車輛入站的順序?yàn)?，2，3，則車輛出站的順序?yàn)椋?E ） 。A. 1, 2, 3, 4, 5 B. 1, 2, 4, 5, 7 C. 1, 3, 5, 4, 6 D. 1, 3, 5, 6, 7 E. 1, 3, 6, 5, 7114.滿二叉樹的葉結(jié)點(diǎn)個(gè)數(shù)為 N，則它的結(jié)點(diǎn)總數(shù)為（ C ） 。A. N B. 2 * N C. 2 * N 1 D. 2 * N + 1 E. 2N 15.二叉樹 T，已知其前序遍歷序列為 1 2 4 3 5 7 6，中序遍歷序列為 4 2 1 5 7 3 6，則其后序遍歷序列為（ B

40、 ） 。A. 4 2 5 7 6 3 1 B. 4 2 7 5 6 3 1 C. 4 2 7 5 3 6 1 D. 4 7 2 3 5 6 1 E. 4 5 2 6 3 7 120. 某大學(xué)計(jì)算機(jī)專業(yè)的必修課及其先修課程如下表所示：課程代號(hào)C0C1C2C3C4C5C6C7課程名稱高等數(shù)學(xué)程序設(shè)計(jì)語言離散數(shù)學(xué)數(shù)據(jù)結(jié)構(gòu)編譯技術(shù)操作系統(tǒng)普通物理計(jì)算機(jī)原理先修課程C0, C1C1, C2C3C3, C7C0C6請(qǐng)你判斷下列課程安排方案哪個(gè)（些）是合理的（ BCE ） 。A. C0, C1, C2, C3, C4, C5, C6, C7 B. C0, C1, C2, C3, C4, C6, C7, C5

41、C. C0, C1, C6, C7, C2, C3, C4, C5 D. C0, C1, C6, C7, C5, C2, C3, C4E. C0, C1, C2, C3, C6, C7, C5, C4NOIP2005：4. 完全二叉樹的結(jié)點(diǎn)個(gè)數(shù)為 4 * N + 3，則它的葉結(jié)點(diǎn)個(gè)數(shù)為（ E ） 。A. 2 * N B. 2 * N - 1 C. 2 * N + 1 D. 2 * N - 2 E. 2 * N + 25. 平面上有五個(gè)點(diǎn) A(5, 3), B(3, 5), C(2, 1), D(3, 3), E(5, 1)。以這五點(diǎn)作為完全圖 G 的頂點(diǎn)，每兩點(diǎn)之間的直線距離是圖 G 中對(duì)應(yīng)邊

42、的權(quán)值。圖 G 的最小生成樹中的所有邊的權(quán)值綜合為（ D ） 。A. 8 B. 7+ 5 C. 9 D. 6+ 5 E. 4+2 2 + 513. 二叉樹 T 的寬度優(yōu)先遍歷序列為 A B C D E F G H I，已知 A 是 C 的父結(jié)點(diǎn)，D 是 G 的父結(jié)點(diǎn)，F(xiàn) 是 I 的父結(jié)點(diǎn)，樹中所有結(jié)點(diǎn)的最大深度為 3（根結(jié)點(diǎn)深度設(shè)為 0） ，可知 E的父結(jié)點(diǎn)可能是（ BC ） 。A. A B. B C. C D. D E. F14. 設(shè)棧 S 的初始狀態(tài)為空，元素 a, b, c, d, e, f, g 依次入棧，以下出棧序列不可能出現(xiàn)的有（ CE ） 。A. a, b, c, e, d, f

43、, g B. b, c, a, f, e, g, d C. a, e, c, b, d, f, gD. d, c, f, e, b, a, g E. g, e, f, d, c, b, aNOIP2006：4在編程時(shí)（使用任一種高級(jí)語言，不一定是 Pascal） ，如果需要從磁盤文件中輸入一個(gè)很大的二維數(shù)組（例如 1000*1000 的 double 型數(shù)組） ，按行讀（即外層循環(huán)是關(guān)于行的）與按列讀（即外層循 環(huán)是關(guān)于列的）相比，在輸入效率上（ E ） 。A. 沒有區(qū)別 B. 有一些區(qū)別，但機(jī)器處理速度很快，可忽略不計(jì)C. 按行讀的方式要高一些 D. 按列讀的方式要高一些 E. 取決于數(shù)組的

44、存儲(chǔ)方式。7某個(gè)車站呈狹長形，寬度只能容下一臺(tái)車，并且只有一個(gè)出入口。已知某時(shí)刻該車站狀態(tài)為空，從 這一時(shí)刻開始的出入記錄為：“進(jìn)，出，進(jìn)，進(jìn)，進(jìn)，出，出，進(jìn)，進(jìn)，進(jìn)，出,出” 。假設(shè)車輛入站的 順序?yàn)?1，2，3，則車輛出站的順序?yàn)椋?C ） 。A. 1, 2, 3, 4, 5 B. 1, 2, 4, 5, 7 C. 1, 4, 3, 7, 6D. 1, 4, 3, 7, 2 E. 1, 4, 3, 7, 58高度為 n 的均衡的二叉樹是指：如果去掉葉結(jié)點(diǎn)及相應(yīng)的樹枝，它應(yīng)該是高度為 n-1 的滿二叉樹。在這里，樹高等于葉結(jié)點(diǎn)的最大深度，根結(jié)點(diǎn)的深度為 0，如果某個(gè)均衡的二叉樹共有 2381

45、 個(gè)結(jié)點(diǎn)， 則該樹的樹高為（ B ） 。A. 10B. 11C. 12D. 13E. 210 1解析: 均衡二叉樹就是：任意兩個(gè)度不為 2 的節(jié)點(diǎn)的深度之差不大于 1例如：12 1 / 2 3 / 4 5是均衡二叉樹而 1 / 2 3 / 4 5 6 / 7就不是，2 和 7 的深度差 2.因?yàn)?211 = 2048；所以一顆滿二叉樹從深度為 0（根節(jié)點(diǎn)）到深度 10 的總節(jié)點(diǎn)數(shù)是 2047，剩下 2381-2047 = 334 個(gè)節(jié)點(diǎn)，這剩下的節(jié)點(diǎn)的深度都是 11。所以答案為 B10將 5 個(gè)數(shù)的序列排序，不論原先的順序如何，最少都可以通過（ B ）次比較，完成從小到大的排序。A. 6 B.

46、 7 C. 8 D. 9 E. 1013. 設(shè)棧 S 的初始狀態(tài)為空，元素 a, b, c, d, e 依次入棧，以下出棧序列不可能出現(xiàn)的有（ C ） 。A. a, b, c, e, d B. b, c, a, e, dC. a, e, c, b, d D. d, c, e, b, a14. 已知 6 個(gè)結(jié)點(diǎn)的二叉樹的先根遍歷是 1 2 3 4 5 6（數(shù)字為結(jié)點(diǎn)的編號(hào)，以下同） ，后根遍歷是3 2 5 6 4 1，則該二叉樹的可能的中根遍歷是（ BC ）A. 3 2 1 4 6 5 B. 3 2 1 5 4 6C. 2 3 1 5 4 6 D. 2 3 1 4 6 5NOIP2007：2.

47、在關(guān)系數(shù)據(jù)庫中, 存放在數(shù)據(jù)庫中的數(shù)據(jù)的邏輯結(jié)構(gòu)以( E )為主。 A. 二叉樹 B. 多叉樹 C. 哈希表 D. B+樹 E. 二維表 9. 歐拉圖 G 是指可以構(gòu)成一個(gè)閉回路的圖，且圖 G 的每一條邊恰好在這個(gè)閉回路上出現(xiàn)一次（即一筆畫成） 。在以下各個(gè)描述中, 不一定是歐拉圖的是：（ D ） 。 A. 圖 G 中沒有度為奇數(shù)的頂點(diǎn) B. 包括歐拉環(huán)游的圖(歐拉環(huán)游是指通過圖中每邊恰好一次的閉路徑) C. 包括歐拉閉跡的圖(歐拉跡是指通過途中每邊恰好一次的路徑) D. 存在一條回路, 通過每個(gè)頂點(diǎn)恰好一次 E. 本身為閉跡的圖 14. 已知 7 個(gè)節(jié)點(diǎn)的二叉樹的先根遍歷是 1 2 4 5

48、6 3 7(數(shù)字為結(jié)點(diǎn)的編號(hào)，以下同)， 后根遍歷是 4 6 5 2 7 3 1， 則該二叉樹的可能的中根遍歷是（ ABD ） A. 4 2 6 5 1 7 3 B. 4 2 5 6 1 3 7 C. 4 2 3 1 5 4 7 D. 4 2 5 6 1 7 3 19. 在下列關(guān)于算法復(fù)雜性的說法中， 正確的有（ BC ） 。 A. 算法的時(shí)間復(fù)雜度，是指它在某臺(tái)計(jì)算機(jī)上具體實(shí)現(xiàn)時(shí)的運(yùn)行時(shí)間 B. 算法的時(shí)間復(fù)雜度，是指對(duì)于該算法的一種或幾種主要的運(yùn)算， 運(yùn)算的次數(shù)與問題的規(guī)模之間的函數(shù)關(guān)系 C. 一個(gè)問題如果是 NPC 類的， 就意味著在解決該問題時(shí)， 不存在一個(gè)具有多項(xiàng)式時(shí)間復(fù)雜度的算法.

49、 但這13一點(diǎn)還沒有得到理論上證實(shí)，也沒有被否定 D. 一個(gè)問題如果是 NP 類的，與 C 有相同的結(jié)論 由 X2Studio.Net 收集 5將數(shù)組8, 23, 4, 16, 77, -5, 53, 100中的元素按從大到小的順序排列，每次可以交換任意兩個(gè)元素，最少需要交換（ B ）次。A. 4 B. 5 C. 6 D. 7 E. 86設(shè)棧 S 的初始狀態(tài)為空，元素 a，b，c，d，e，f 依次入棧 S，出棧的序列為 b，d，c，f，e，a，則棧 S 的容量至少應(yīng)該是（ D ） 。A. 6 B. 5 C. 4 D. 3 E. 218. 設(shè) T 是一棵有 n 個(gè)頂點(diǎn)的樹，下列說法正確的是（ A

50、BC ） 。A. T 是連通的、無環(huán)的 B. T 是連通的，有 n-1 條邊C. T 是無環(huán)的，有 n-1 條邊 D. 以上都不對(duì)NOIP2009：5、一個(gè)包含 n 個(gè)分支結(jié)點(diǎn)（非葉結(jié)點(diǎn)）的非空滿 k 叉樹，k=1，它的葉結(jié)點(diǎn)數(shù)目為：DA) nk + 1 B) nk-1 C) (k+1)n-1 D. (k-1)n+1 7、最優(yōu)前綴編碼，也稱 Huffman 編碼。這種編碼組合的特點(diǎn)是對(duì)于較頻繁使用的元素給與較短的唯一編碼，以提高通訊的效率。下面編碼組合哪一組不是合法的前綴編碼。BA)（00，01，10，11） B)（0，1，00，11） C)（0，10，110，111） D)（1，01，000

51、，001）8、快速排序平均情況和最壞情況下的算法時(shí)間復(fù)雜度分別為：AA) 平均情況 O(nlog2n)，最壞情況 O(n2)B) 平均情況 O(n)， 最壞情況 O(n2)C) 平均情況 O(n)， 最壞情況 O(nlog2n) D) 平均情況 O(log2n)， 最壞情況 O(n2)9、左圖給出了一個(gè)加權(quán)無向圖，從頂點(diǎn) V0開始用prim 算法求最小生成樹。則依次加入最小生成樹的頂點(diǎn)集合的頂點(diǎn)序列為：AA) V0, V1, V2, V3, V5, V4 B) V0, V1, V5, V4, V3, V3 C) V1, V2, V3, V0, V5, V4 D) V1, V2, V3, V0,

52、 V4, V56、若 3 個(gè)頂點(diǎn)的無權(quán)圖 G 的鄰接矩陣用數(shù)組存儲(chǔ)為0，1，1，1，0，1，0，1，0，假定在具體存儲(chǔ)中頂點(diǎn)依次為: v1，v2，v3。關(guān)于該圖，下面的說法哪些是正確的：ABDA)該圖是有向圖。B)該圖是強(qiáng)連通的。C)該圖所有頂點(diǎn)的入度之和減所有頂點(diǎn)的出度之和等于 1。D)從 v1 開始的深度優(yōu)先遍歷所經(jīng)過的頂點(diǎn)序列與廣度優(yōu)先的頂點(diǎn)序列是相同的。8、散列表的地址區(qū)間為 0-10,散列函數(shù)為 H(K)=K mod 11。采用開地址法的線性探查法處理沖突，并將關(guān)鍵字序列 26，25，72，38，8，18，59 存儲(chǔ)到散列表中，這些元素存入散列表的順序并不確定。假定之前散列表為空，則

53、元素 59 存放在散列表中的可能地址有：ABCA) 5 B) 7 C) 9 D) 10類型類型 5 5：數(shù)學(xué)與邏輯運(yùn)算：數(shù)學(xué)與邏輯運(yùn)算：14NOIP1999：17、十進(jìn)制算術(shù)表達(dá)式 ：3*512 + 7*64 + 4*8 + 5 的運(yùn)算結(jié)果，用二進(jìn)制表示為（ B ） A. 10111100101 B. 11111100101 C. 11110100101 D. 11111101101 NOIP2000：1.下列無符號(hào)數(shù)中，最小的數(shù)是（ C ）A.（11011001）2B.(75)10C.(37)8D.(2A)1610.某種計(jì)算機(jī)的內(nèi)存容量是 640K，這里的 640K 容量是指（C）個(gè)字節(jié)A.

54、640B. 640*1000C. 640*1024D. 640*1024*1024NOIP2001：3、64KB 的存儲(chǔ)器用十六進(jìn)制表示，它的最大的地址碼是( B )A)10000 B)FFFF C)1FFFF D)EFFFF9、2KB 的內(nèi)存能存儲(chǔ)( )個(gè)漢字的機(jī)內(nèi)碼 A A)1024 B)516 C)2048 D)21811、運(yùn)算式(2047)10(3FF)16+(2000)8 的結(jié)果是( A )A)(2048)10 B)(2049)10 C)(3746)8 D)(1AF7)1616.x補(bǔ)碼=10011000，其原碼為( B )A)011001111 B)11101000 C)111001

55、10 D)01100101NOIP2002：3 十進(jìn)制書 11/128 可用二進(jìn)制數(shù)碼序列表示為：（ D ） 。A）1011/1000000 B）1011/100000000 C）0.001011 D）0.00010114 算式（2047）10 （3FF）16 （2000）8 的結(jié)果是（ A ） 。 A） （2048）10 B） （2049）10 C） （3746）8 D） （1AF7）165 已知 x =（0.1011010）2 ，則 x / 2 補(bǔ) =（ C ）2 。 A）0.1011101 B）11110110 C）0.0101101 D）0.100110C）連接在網(wǎng)絡(luò)上的高級(jí) D）具有

56、處理文字、圖形、聲音、影像等信息的15已知 A = 35H，A / 05H / A / 30H 的結(jié)果是：（ C ） 。A）30H B）05H C）35H D）53HNOIP2003：3. 十進(jìn)制數(shù) 2003 等值于二進(jìn)制數(shù)（ D ） 。 A） 0100000111 B） 10000011 C） 110000111 D） 11111010011 E） 11110100114. 假設(shè) A=true,B=false,C=ture,D=ture,邏輯運(yùn)算表達(dá)式 ABCD 的值是（ A ） 。 A） ture B） false C） 0 D） 1 E） NULL8. 設(shè)全集 E=1，2，3，4，5，集

57、合 A=1，4，B=1，2，5，C=2，4，則集合（A B）C 為（ E ） 。 A） 空集 B） 1 C） 3，5 D）1，5 E） 1，3，518. 運(yùn)算試(2008)10-(3723)8 的結(jié)果是（ BCD ） 。 A）(-1715)10 B) (5)10 C) (5)16 D) (101)2 E) (3263)8NOIP2004：1.設(shè)全集 I = a, b, c, d, e, f, g，集合 A = a, b, c，B = b, d, e，C = e, f, g，那么集合 為（ A ） 。A. a, b, c, d B. a, b, d, e C. b, d, e D. b, c,

58、d, e E. d, f, g2.由 3 個(gè) a，5 個(gè) b 和 2 個(gè) c 構(gòu)成的所有字符串中，包含子串“abc”的共有（ D ）個(gè)。A. 40320 B. 39600 C. 840 D. 780 E. 6013. (2004)10 + (32)16 的結(jié)果是（ BCD ） 。A. (2036)16 B. (2054)10 C. (4006)8 D. (100000000110)2 E. (2036)10NOIP2005：1. 字符串“ababacbab”和字符串“abcba”的最長公共子串是（ B ） 。15A. abcba B. cba C. abc D. ab E. bcba2. 設(shè)全

59、集 I = a, b, c, d, e, f, g, h，集合 B A= a, b, c, d, e, f， C A= c, d, e，B A = a, d，那么集合 C B A 為（ A ） 。A. c, e B. d, e C. e D. c, d, e E. d, f3. 以下二進(jìn)制數(shù)的值與十進(jìn)制數(shù) 23.456 的值最接近的是（ D ） 。A. 10111.0101 B. 11011.1111 C. 11011.0111 D. 10111.0111 E. 10111.111111. 設(shè) A = true，B = false，C = false，D = true，以下邏輯運(yùn)算表達(dá)式值為真

60、的有（ BC ） 。A. (A B )(C D ) B. (A B ) C ) D C. A(B C ) D )D. (A(B C ) D E. (A B )(C D )NOIP2006：5在 Pascal 語言中，表達(dá)式 (21 xor 2)的值是（ C ）A. 441B. 42C.23D.24E.2511. 設(shè) A=B=D=true，C=E=false，以下邏輯運(yùn)算表達(dá)式值為真的有（ ABC ） 。A. ( AB)(CD)EB. (AB)C)DE)C. A(BCDE)D. (A(BC) DE12. (2010)16 + (32)8 的結(jié)果是（ AB ） 。A. (8234)10B. (20