1、NOIP初賽練習(xí)之一(選擇題)一單項選擇題1、操作系統(tǒng)是系統(tǒng)軟件的核心，是有效利用計算機(jī)的硬件、軟件、數(shù)據(jù)等各種資源的好管家，它還向用戶提供一套容易學(xué)習(xí)使用的操作命令。常用的操作系統(tǒng)有：MS-DOS、PC-DOS、WINDOWS、UNIX、LINUX、OS/2等。WORD、WPS是字處理軟件，F(xiàn)OXBASE是數(shù)據(jù)庫管理軟件。 2、字長表示一個存儲單元由多少位二進(jìn)制數(shù)組成，八位機(jī)一個字長就是一個字節(jié)，十六位機(jī)一個字長可以表示兩個字節(jié)。字長位的多少，表明可訪問存儲器的地址多少。 3、操作系統(tǒng)一般存放在系統(tǒng)盤，計算機(jī)啟動引導(dǎo)系統(tǒng)后，系統(tǒng)中的常用命令就駐留在內(nèi)存中，方便用戶使用計算機(jī)。所以啟動計算機(jī)引

2、導(dǎo)系統(tǒng)就是把操作系統(tǒng)從系統(tǒng)盤中調(diào)入內(nèi)存儲器。 4、我們要清楚，快存實質(zhì)是高速緩存，主存即內(nèi)存，輔存也就是外存。在這三種存儲器中，以高速緩存最快，故此，通常常用的程序都是存放在高速緩存區(qū)里。而主存的速度當(dāng)然是比輔存要快了。 5、一般，對計算機(jī)工作有較大影響的有塵土、溫度、濕度。 6、計算機(jī)的指令系統(tǒng)是由操作碼與操作數(shù)組成。 7、通用寄存器的位數(shù)跟機(jī)器有關(guān)，取決于計算機(jī)的字長。 8、計算機(jī)能實現(xiàn)的全部指令的集合合稱為指令系統(tǒng)。執(zhí)行各條指令所規(guī)定的操作是由指揮工作的控制器和執(zhí)行運算的部件共同完成。而控制器與運算器合起來稱為CPU。 9、RAM(random access memory)隨時讀寫存儲器

3、，供計算機(jī)工作時隨機(jī)寫入，計算機(jī)一旦斷電后，其中的信息就會消失。 WINDOWS 9X是一種多任務(wù)的可視化的操作系統(tǒng)，它可以同時打開多個窗口，執(zhí)行多個任務(wù)，而這些操作無論是應(yīng)用程序還是文檔編輯窗口，都可以利用圖標(biāo)、菜單或工具進(jìn)行操作，即所見即所得。所以稱之為多任務(wù)圖形方式的操作系統(tǒng)。1-10參考答案：BBDCBBCABD 11、常用的操作系統(tǒng)有：MS-DOS、PC-DOS、WINDOWS、UNIX、LINUX、OS/2等。PASCAL是程序設(shè)計的語言系統(tǒng)軟件。 12、在漢字編碼中，每個漢字無論筆畫多少，它們字模所占的字節(jié)數(shù)總是相同的，一個字節(jié)可以存儲8位二進(jìn)制，24點就需要用3個字節(jié)存儲，24

4、行則需要3*24即72個字節(jié)。 13、主機(jī)與中央處理器(CPU)是兩個不同的概念。CPU由控制器與運算器組成，而主機(jī)則由CPU和內(nèi)存儲器組成，輸入、輸出設(shè)備屬于計算機(jī)的處圍設(shè)備。 14、計算機(jī)系統(tǒng)總線分為：地址總線、控制總線、和數(shù)據(jù)總線，因此計算機(jī)系統(tǒng)在總線上傳送的信號，按其類型，分別通過地址總線、控制總線和數(shù)據(jù)總線。 15、計算機(jī)內(nèi)部無論是數(shù)據(jù)還是命令，都需要轉(zhuǎn)換成二進(jìn)制代碼才能傳送、存貯、加工處理。 16、操作系統(tǒng)是為用戶提供使用和管理計算機(jī)的軟件，一旦啟動后，常用的命令駐留在內(nèi)存中，此時用戶可以運行自己的應(yīng)用軟件，一般不需要將系統(tǒng)盤插入在A驅(qū)中，但若需要調(diào)用操作系統(tǒng)中的外部命令，則需要將

5、系統(tǒng)盤插入A驅(qū)中。 17、7位二進(jìn)制可表示27個狀態(tài)，因此有128個不同的二進(jìn)制編碼，國際上按照這樣的編碼來表示控制符號、十進(jìn)制數(shù)、字符、英文字母在大小寫以及一些特殊符號等。由于一個字節(jié)長度是八位二進(jìn)制數(shù)，所以用一個字節(jié)表示ASCII碼，則最高位為0；漢字編碼是用兩個字節(jié)表示，最高位為1。 18、外部設(shè)備包括了輸入設(shè)備、輸出設(shè)備。繪圖儀是受計算機(jī)控制，將處理信息的結(jié)果以繪出圖形的方式表示出來的一種外部設(shè)備。 19、1MB=1024KB,1KB=1024B，所以512MB=512*1024*1024個字節(jié)。 20、一個字節(jié)由8位二進(jìn)制數(shù)組成，64位的奔騰處理器一次能處理64位信息相當(dāng)于8字節(jié)。

6、11-20參考答案：CADBCCBDCA21、計算機(jī)系統(tǒng)由硬件系統(tǒng)和軟件系統(tǒng)組成。 22、操作系統(tǒng)是系統(tǒng)軟件的核心，是有效利用計算機(jī)的硬件、軟件、數(shù)據(jù)等各種資源。 23、RAM(random access memory)隨時讀寫存儲器，供計算機(jī)工作時隨機(jī)寫入，計算機(jī)一旦斷電后，其中的信息就會消失。 24、在電腦中，各種各樣的數(shù)據(jù)都是以文件的形式存放的。 25、計算機(jī)系統(tǒng)是由硬件和軟件兩部分組成，有效的使用和管理計算機(jī)的各種輸入和輸出設(shè)備，應(yīng)用各種軟件，必須借助于計算機(jī)的操作系統(tǒng)。 26、計算機(jī)的工作原理跟人的大腦很相似，而且還是大腦功能的延伸，所以習(xí)慣上叫它電腦。 27、存儲容量是指存儲的信息

7、量，它用字節(jié)(BYTE)作用基本單位。 28、計算機(jī)病毒是一種程序，是人為設(shè)計的具有破壞性的程序。計算機(jī)病毒具有破壞性、傳播性、可激發(fā)性、潛伏性、隱蔽性等特點。 29、磁盤驅(qū)動器是既能輸入又能輸出的設(shè)備。顯示器是輸出設(shè)備，鍵盤與鼠標(biāo)是輸入設(shè)備。 30、在關(guān)機(jī)狀態(tài)下開機(jī)就是冷啟動。 21-30參考答案：DCCBDADCAD31、CAI，Computer Assisted Instruction，計算機(jī)輔助教學(xué)。 32、媒體是指表示和傳播信息的載體。 33、微機(jī)的性能取決于CPU的性能，CPU主頻越快，其運算速度也就越快。存儲器中的RAM中的信息會在斷電后丟失。打印機(jī)的打印字體與針數(shù)無關(guān)。顯示器分

8、辨率與屏幕尺寸無關(guān)。 34、文本型病毒感染的主要對象是.EXE和.COM文件。 35、24針打印機(jī)的分辨率單位dpi是指印點/英寸。 36、內(nèi)存中的每一個基本單位，都被賦予一個唯一的序號，稱為地址。 37、總線是用于連接計算機(jī)中各部件(CPU、內(nèi)存、外設(shè)接口)的一組公共信號線。顯示器、磁盤驅(qū)動器、鍵盤都屬于外設(shè)，故此，通過總線與CPU相連的是內(nèi)存儲器。 38、計算機(jī)運算速度是指每秒執(zhí)行指令的條數(shù)。M表示百萬，IP表示指針寄存器，S表示秒，即每秒執(zhí)行百萬條指令。 39、MIS(Management Information System)信息管理系統(tǒng) 40、多媒體計算機(jī)一般指能夠同時接受、處理、存

9、儲和展示多種不同類型信息媒體的計算機(jī)。 31-40參考答案：BAADCBBAAD41、我國1956年開始電子計算機(jī)的科研和教學(xué)工作，1958年研制成功第一臺電子計算機(jī)(103型電子管計算機(jī)) 42、存儲程序原理是由美籍匈牙利數(shù)學(xué)家馮諾依曼于1946年指出的。 43、一般地，通過電路集成化后，運算器和控制器結(jié)合在一起，并稱之為中央處理器(Central Processing Unit)，簡稱CPU。 44、存儲器分為內(nèi)部存儲器和外部存儲器兩部分。 45、第一代電腦是電子管計算機(jī)，開始于1946年，結(jié)構(gòu)上以存儲器為中心，使用機(jī)器語言，存儲量小，主要用于數(shù)值計算。 46、CPU主要由運算器、控制器和

10、寄存器組成。寄存器是CPU內(nèi)部的臨時存儲單元，可以存放數(shù)據(jù)和地址，也可以存放控制信息和CPU工作的狀態(tài)信息。 47、1MB=1024KB 48、軟件系統(tǒng)一般都含有很多個軟件，這些軟件分屬于系統(tǒng)軟件和應(yīng)用軟件兩大類。 49、1983年12月，每秒運算1億次的“銀河”巨型計算機(jī)在中國國防科技大學(xué)問世。50、RAM(random access memory)隨時讀寫存儲器，供計算機(jī)工作時隨機(jī)寫入，計算機(jī)一旦斷電后，其中的信息就會消失。 41-50參考答案：BCCCADAADC51、3.5英寸高密軟盤的容量一般是1.44MB。 52、標(biāo)準(zhǔn)指法中，9個基本健是ASDFJKL;與空格鍵。當(dāng)未擊鍵時，十個手

11、指都放在基本鍵上，左手尾指A、左手無名指S、左手中指D、左手食指F、右手食指J、右手中指K、右手無名指L、右手尾指;、兩只大拇指空格。 53、主機(jī)、鍵盤、顯示器是構(gòu)成計算機(jī)的三大硬件，操作系統(tǒng)是軟件。 54、硬盤工作時應(yīng)特別注意震動，因為高速運行時，震動會使硬盤的磁頭劃花磁盤片。 55、打印機(jī)術(shù)語中的24針是指打印頭有24根針。 56、辦公室自動化應(yīng)用了計算機(jī)的信息處理自動化的特點。 57、計算機(jī)輔助設(shè)計(Computer Assisted Design) 58、計算機(jī)病毒是一種程序，是人為設(shè)計的具有破壞性的程序。計算機(jī)病毒具有破壞性、傳播性、可激發(fā)性、潛伏性、隱蔽性等特點。 59、寫保護(hù)的作

12、用是防止意外的寫操作而破壞原存儲的信息。磁盤寫保護(hù)后只能讀而不能修改、不能寫、也不能刪 60、操作系統(tǒng)在第三代計算機(jī)開始應(yīng)用。 51-60參考答案：DACBDCADBC61.基本方法是把任意進(jìn)制數(shù)轉(zhuǎn)換成十進(jìn)制數(shù)后進(jìn)行比較。(11011001)2=1*27+1*26+1*24+1*23+1*20=(217)10、(37)8=3*81+7*80=(31)10、(A7)16=10*161+7*160=(167)10，可以看出(37)8數(shù)最小。 62.根據(jù)題意，算式結(jié)果為33，而33不可能是十進(jìn)制數(shù)，否則52、19都必須是十進(jìn)制數(shù)，與題意不合；計算機(jī)結(jié)果也不可能是十六進(jìn)制數(shù)，否則，52必須是8進(jìn)制，減

13、出十進(jìn)制19的結(jié)果不可能是十六進(jìn)制33。故選擇B，運算為(52)10-(19)16=(33)852-(16+9)=(3*8+3) 63.由m的十六進(jìn)制ASC碼值是6D，而我們知道小寫c與m相差十進(jìn)制數(shù)10，相當(dāng)于十六進(jìn)制數(shù)A，將6D-A=63(16進(jìn)制數(shù)減法)。 64.浮點數(shù)的表示同數(shù)學(xué)中的科學(xué)計數(shù)法有相似之處，由小數(shù)及10的N次冪表示，計算機(jī)中的的浮點數(shù)則將小數(shù)部分表示為尾數(shù)，將10的N次冪的N作為階碼。 65.先求得2021再化二進(jìn)制。較快的方法有兩種，1、轉(zhuǎn)成二進(jìn)制，即：3*512+7*64+4*8+5=(21+20)*29+(22+21+20)*26+22*23+22+20=210+2

14、9+28+27+26+25+22+20(3745)866. 計算機(jī)對字符的排序是按照字符的ASC碼值的大小進(jìn)行排序的，漢字的排序則是根據(jù)漢語拼音的字母的ASC碼值進(jìn)行排序。 67. GB2312-80方案是我國于1981年頒布的信息交換用漢字編碼字符集，共收錄了6763個漢字，其中一級漢字3775個是按照拼音排序，二級漢字3008個是按部首排序，另外還有682個圖文字符。 68.基本方法是把任意進(jìn)制數(shù)轉(zhuǎn)換成十進(jìn)制數(shù)后進(jìn)行比較。(11011001)2=(217)10、(37)8=(31)10、(2A)=(42)10，故(37)8最小。 69.因為正整數(shù)的范圍僅能用7位的二進(jìn)制數(shù)表示，由于最高位是

15、零，當(dāng)7位后全為1時，表示整數(shù)127，再加1，需要進(jìn)位，則符號位變?yōu)?，數(shù)據(jù)發(fā)生質(zhì)的變化，數(shù)據(jù)由正變?yōu)樨?fù)；而負(fù)數(shù)道理基本一樣。故為-127至+127。 70. 因為正數(shù)與負(fù)數(shù)都有唯一的表示格式，而零可以有兩種格式，即：00000000和10000000。 61-70參考答案：CBDCBABCAD71. 由2*4=11可知道，十進(jìn)制數(shù)時2*4=8，而等于11則這個進(jìn)位制一定比8小，而且這個進(jìn)位除以8商為1余1，則可以判定這是7進(jìn)制數(shù)。(5*16)7(5*13)10=(65)10，運用除7取余法可得122。 72. 在計算機(jī)內(nèi)數(shù)的表示中，有符號與沒有符號的表示即為一個字節(jié)表示的內(nèi)容，一個字節(jié)為8位

16、二進(jìn)制，沒有符號就是最高可以表示11111111，也就是最高可以表示255。 73.二進(jìn)制加法法則中說明了，0+0=0，0+1=1，1+0=1，1+1=10(有進(jìn)位)。 74. 帶小數(shù)的二進(jìn)制轉(zhuǎn)換成十進(jìn)制：1110111.11=26+25+24+22+21+20+2(-1)+2(-2)=64+32+16+4+2+1+0.5+0.25=119.7575. 規(guī)格代形式對尾數(shù)的限制是：1/2=|M|=0，則符號位為0，X其余各位取值照抄；若X0，則符號位為1，X其余各位取值求反，最低位加1。故此，原碼中X取值范圍是-127至+127，由于補(bǔ)碼表示時負(fù)數(shù)的最低位要加1，即最小數(shù)可比原數(shù)絕對值大1，故為

17、-128至127。 79.基本方法是把任意進(jìn)制數(shù)轉(zhuǎn)換成十進(jìn)制數(shù)后進(jìn)行比較。(1001001)2=(73)10、(110)8=(72)10、(4A)16=(74)10所以4A最大。 80.先把6A轉(zhuǎn)換成十進(jìn)制數(shù)：(6A)16=(106)10，另外，由于152中各位上最大數(shù)值為5，故不可能為2、4進(jìn)制數(shù)，所以肯定為8進(jìn)制數(shù)。 71-80參考答案：CDBBACBADB81. 由于執(zhí)行C:FORMAT A:命令時，出錯信息顯示“命令失敗或文件名錯”，這里的文件名是正確的，說明當(dāng)前中徑下無此命令。如果在執(zhí)行此命令前曾執(zhí)行過PATH c:DOS(或AUTOEXEC.BAT文件中含有此命令)，則計算機(jī)不會報

18、錯，它會自動搜索路徑，執(zhí)行C:DOS中的FORMAT.COM命令。 82.TYPE是顯示文本文件的內(nèi)容；DIR顯示磁盤的文件目錄；CD是進(jìn)入或退出子目錄(顯示當(dāng)前目錄)，只有XCOPY命令能夠在拷貝文件夾及其子文件夾的內(nèi)容，因此只有這個命令有可能在磁盤上建立子目錄。 83.只有TYPE顯示文本文件內(nèi)容的命令能夠成功執(zhí)行，其他命令都說沒有發(fā)現(xiàn)該文件。 84. 因特網(wǎng)又稱國際互聯(lián)網(wǎng)。我國于1994年正式聯(lián)入因特網(wǎng)。全國科學(xué)技術(shù)名詞審定委員會于1997年7月8日為INTERNET作出了命名，中文名詞為“因特網(wǎng)”，注釋是“指全球最大的、開放的、由眾多網(wǎng)絡(luò)相互連接而成的計算機(jī)網(wǎng)絡(luò)”。 85.在許多文件復(fù)

19、制過程中，某一個文件讀錯誤，當(dāng)鍵入“I”后，忽略錯誤，繼續(xù)復(fù)制文件，因此僅此文件無法讀取，而其他文件是正確復(fù)制且能讀取。 86.BUFFER是開辟緩沖區(qū)；FILES是數(shù)據(jù)庫系統(tǒng)中定義所需要建立的文件數(shù)；DEVICE是指裝置數(shù)；DRIVER是驅(qū)動程序命令。 87.ATTRIB的作用是查看當(dāng)前目錄下的文件屬性。 88.A中左邊是錯誤的命令，右邊是將文件內(nèi)容復(fù)制到顯示器；B才是等效的；C中兩個是無效的命令，而D前面一個命令雖然可以將A盤的內(nèi)容全部拷貝到B盤但跟磁盤拷貝命令執(zhí)行的結(jié)果還是不一樣的，因為磁盤拷貝不僅內(nèi)容相同而且位置也相同。 89 CON1表示接外設(shè)端口，其他都和保留設(shè)備名無關(guān)。 90 一

20、般的計算機(jī)網(wǎng)絡(luò)按網(wǎng)絡(luò)的涉及范圍及范圍的距離劃分為廣域網(wǎng)和局域網(wǎng)，廣域網(wǎng)即WAN，城域網(wǎng)即MAN，局域網(wǎng)即LAN，都市網(wǎng)屬于城域網(wǎng)。如果按網(wǎng)絡(luò)的層次結(jié)構(gòu)劃分有總線型、星型、環(huán)型等形式。 81-90參考答案：DCABACBDCD91 COMMAND.COM是命令處理程序模塊，為用戶提供一個行命令式的界面，負(fù)責(zé)接收、識別、解釋和執(zhí)行鍵入的命令行。 92 PROMPT是改變系統(tǒng)提示符的內(nèi)部命令。$N$G表示系統(tǒng)提示符為前面只有當(dāng)前驅(qū)動器，顯示為C；$P$G表示設(shè)置系統(tǒng)提示符為前面帶有當(dāng)前驅(qū)動器和路徑，顯示為C:。 93 DIR命令查看一個目錄下的文件時，會顯示當(dāng)前目錄下的文件總數(shù)，最小的情況下是2個，

21、也就是說當(dāng)前目錄下沒有文件，只有.和.兩個目錄標(biāo)識符。 94 在DOS提示符下可執(zhí)行的文件類型一共有3種，分別是：.COM、.EXE、.BAT。 95 DEL是刪除文件的內(nèi)部命令，當(dāng)DEL后跟一個文件的文件名則只刪除指定的文件，如果DEL后跟通配符，則刪除合符要求的多個文件。但不能刪除隱含、只讀、系統(tǒng)文件。 96 PATH是指定可執(zhí)行文件的查找路徑的內(nèi)部命令。97 DOS執(zhí)行命令的先后順序是：內(nèi)部命令COM文件EXE文件BAT文件。TIME是顯示和設(shè)置系統(tǒng)時間的內(nèi)部命令。 98 編譯程序是程序語言軟件的功能。 99 計算機(jī)網(wǎng)絡(luò)是計算機(jī)技術(shù)與通信技術(shù)相結(jié)合而形成的一種新的通信形式。把不同地理位置

22、、具有獨立功能的多臺計算機(jī)、終端及附屬設(shè)備，用通信鏈路連接起來，并配備相應(yīng)的網(wǎng)絡(luò)軟件，以實現(xiàn)資源共享為目標(biāo)而形成的通信系統(tǒng)。所以網(wǎng)絡(luò)最突出的優(yōu)點是共享資源。 100 INTERNET上可以傳輸各種多媒體的信息。 91-100參考答案：CBCBBDDABB101 DOS規(guī)定，文件名：由1-8個字符組成。必須使用DOS規(guī)定的合法字符。合法字符有：26個英文字母(大、小寫)、0-9十個數(shù)字和一些特殊字符。另外，文件名中不能有空格、*、?、( )、/ 、.等符號。 102 A：DOS是單任務(wù)操作系統(tǒng)；B：外部命令并不裝在內(nèi)存中；C：TYPE A.TXTPRN是指把文件A.TXT的內(nèi)容輸出到打印中；D：

23、沒有CONFIG.SYS系統(tǒng)一樣可以啟動。 103 軟盤寫保護(hù)后，不能寫、不能修改、不能刪除，更不能格式化，但可以讀。 104 操作系統(tǒng)對資源的管理可以分為處理機(jī)管理、存儲管理、設(shè)備管理、文件管理、作業(yè)管理五個主要部分。其中最主要的是設(shè)備管理與文件管理。 105 內(nèi)部命令：指啟動時由裝入程序從磁盤讀入內(nèi)存并常駐內(nèi)存的命令。內(nèi)部命令對應(yīng)的程序都放在COMMAND.COM中，無需讀盤可隨時使用。 106 在WINDOWS中，將一個應(yīng)用程序窗口最小化后，這個程序并沒有停止運行，只是在后臺繼續(xù)運行，但窗口被最小化了，所以我們看不見它的運行過程。 107 FTP：文件傳輸；WWW：信息瀏覽；BBS：電子

24、公告牌；E-mail：電子郵件。 108 用戶在網(wǎng)上最常用的信息查詢工具叫搜索引擎。 109 WINDOWS窗口的右上角的按鈕一共有四種：最小化、最大化、還原、關(guān)閉。其中最大化與還原不可能同時出現(xiàn)。 110 WINDOWS窗口中窗口角可以調(diào)整窗口的寬度和高度，窗口邊框只能調(diào)整寬度或高度，滾動條可以實現(xiàn)窗口內(nèi)容的滾動，菜單提供各種菜單命令給用戶使用。101-110參考答案：BCBADACBCA111 算法是指人們?yōu)榱私鉀Q問題而選取的方法和實施步驟，而程序設(shè)計只是用計算機(jī)去實現(xiàn)問題求解的一種手段。計算機(jī)語言則是程序設(shè)計的基礎(chǔ)，計算方法是在解決問題過程中所需要的數(shù)學(xué)模式等。 112 棧是一個后進(jìn)先出

25、的線性表，根據(jù)題意，可得，1、2、3進(jìn)棧，然后是3出棧，4進(jìn)棧，4出棧，最后5進(jìn)棧，此時出棧的元素次序為3、4。 113 在容量為N的循環(huán)隊列中，有可能出現(xiàn)兩種情況，一種是尾指針R比頭指針F大，則其元素個數(shù)為R-F；另一種情況是尾指針比頭指針小，則其元素個數(shù)為R-F+N。為了更好地表示隊列中元素的個數(shù)，可以用通用公式(r-f+n) MOD n來表示任意情況下的元素個數(shù)。 114 在通常情況下，數(shù)據(jù)的徘序，常用快速排序法，然而當(dāng)數(shù)據(jù)已經(jīng)有序時，再用快速排序方法，就不能體現(xiàn)少比較數(shù)據(jù)、交換數(shù)據(jù)的特點，需要將數(shù)據(jù)進(jìn)行一一比較，這樣快速排序就蛻化為冒泡排序了。 115 哈夫曼樹是一種特殊的滿二叉樹，因

26、此若有N個葉子節(jié)點，則其總節(jié)點數(shù)也是2N-1。 116 二分法查找元素其基本思想：將數(shù)據(jù)元素對半分，將待查找的數(shù)與中間位置數(shù)相比較，若大于該中間位置的數(shù)，則在數(shù)據(jù)段的后半段檢索，否則在前半段檢索。重復(fù)上述步驟，最壞的情況下需要查看10個單元。 117 數(shù)組地址計算問題，只要掌握數(shù)據(jù)是順序存儲并占用連續(xù)的存儲空間。注意問題的要求按行存儲還是按列存儲，就能計算任意單元的起始地址。如題：按行分配空間，則A5，8前4行共40個單元，第5行開始A5，1至A5，7共7個單元，即A5，8前有47個單元，其地址是SA+(47*3)=SA+141 118.線性表中的鏈接存儲的特點：是將零散的存儲空間通過指針域連

27、接起來，因此鏈接存儲單元一般至少有兩個域：數(shù)據(jù)域和指針域，通過指針將結(jié)點鏈接后生成鏈接表。所以存儲單元地址可以連續(xù)也可以不連續(xù)。 119.二維數(shù)組本身是一個M行N列的矩陣，每行、每列都可以看做一個線性表。而其中其個元素可以看成一個列向量的線性表，也可以看成一個行向量的線性表。所以二維數(shù)組每個數(shù)據(jù)元素可以看作一個線性表的線性表。 120.由于線段兩端相同，故此，增加一只不同鳥，產(chǎn)生兩條兩端不同小鳥的線段，增加兩只不同鳥，可以產(chǎn)生兩條或四條兩端不同小鳥的線段。增加N只不同小鳥，由于線段兩端是相同鳥，通過對稱排列，必定是偶數(shù)個兩端為不同小鳥的線段。 111-120參考答案：BDDDBBADDB121

28、.列車轉(zhuǎn)轍網(wǎng)絡(luò)是一個棧，數(shù)據(jù)進(jìn)入棧中可以隨時出棧，但其必須遵循后進(jìn)先出的規(guī)則。故此，A中既然4最先出棧則，1不可能第二個出棧；C中既然3、4在前面出棧，1就不可能在2前出棧；D中原因同上。 122.選擇排序的基本思想：每次從待排序的記錄中選擇出關(guān)鍵碼值最小(或最大)的記錄，順序放在已排序的記錄序列的一端，直到全部排完。 123.棧是使用最廣泛的數(shù)據(jù)結(jié)構(gòu)之一，表達(dá)式求值、遞歸過程實現(xiàn)都是棧應(yīng)用的典型例子。 124.鏈表的一個重要特點是插入、刪除運算靈活，不需移動結(jié)點，只要改變結(jié)點中指針域的值就可以了。 125.樹葉：度為0的結(jié)點；分枝結(jié)點：度不為0的結(jié)點；結(jié)點：樹中的每一個元素都叫結(jié)點。所以無論

29、是什么二叉樹，樹葉+分枝結(jié)點=結(jié)點。 126.一維數(shù)組長度固定，在定義時都必須指出其下標(biāo)的范圍。線性表是一個相當(dāng)靈活的數(shù)據(jù)結(jié)構(gòu)，它的長度可以根據(jù)需要增加或縮短。 127.選擇排序的基本思想：每次從待排序的記錄中選擇出關(guān)鍵碼值最小(或最大)的記錄，順序放在已排序的記錄序列的一端，直到全部排完。 128.冒泡排序的基本思想：對待排序的記錄的關(guān)鍵字進(jìn)行兩兩比較，發(fā)現(xiàn)兩個記錄是反序的，則進(jìn)行交換，直到無反序排序的記錄為止。最理想的情況就是原來已經(jīng)沒有反序排序的記錄，那么只需要比較n-1次就可以完成了。 129.二叉樹的性質(zhì)：對于任意一棵二叉樹，如果其端結(jié)點數(shù)為N，而其度為2的結(jié)點總數(shù)為M時，有N=M+

30、1。 130.二叉樹的先序序列順序為：根左右；中序序列順序為：左根右；要其兩個序列的結(jié)果相同，必須是缺少了左子樹，即大家都變成了根右的順序了。 121-130參考答案：BCABAADCAC131.棧是一個后進(jìn)先出的線性表，C：如果C先出棧，則必定是A、B均在棧中，而且B比A后進(jìn)棧，所以出棧必須是B比A先出。 132.幾種排序需要內(nèi)存容量的比較：插入排序：1；選擇排序：1；快速排序：以2為底n的對數(shù)；歸并排序：n。所以最大的是歸并排序。 133. 快速排序：第一趟：27,38,13,49,76,96,65,50；第二趟：13,27,38,49,76，96，65，50(對左子表排序)；第三趟：13

31、,27,38,49,50,65,76,96(對右子表排序)。 134.利用二叉樹對一組數(shù)進(jìn)行排序，先生成一棵二叉排序樹，然后進(jìn)行中序遍歷，所得的結(jié)果就是按升序排列的數(shù)據(jù)。 135.選擇排序的基本思想：每次從待排序的記錄中選擇出關(guān)鍵碼值最小(或最大)的記錄，順序放在已排序的記錄序列的一端，直到全部排完。這是一個典型的選擇排序。 136.在二叉樹中，第I層的結(jié)點總數(shù)不超過2(I-1)；而深度為K的二叉樹的結(jié)點總數(shù)不超過2k-1。故滿二叉樹的結(jié)點總數(shù)為：2k-1(k為二叉樹的深度) 137.滿二叉樹的結(jié)點總數(shù)為：2k-1(k為二叉樹的深度)。由此得：25-1=31。 138.線性表的第一個元素沒有前

32、趨元素，線性表的最后一個元素沒有后繼元素。 139.哈夫曼樹，又稱最優(yōu)樹，是一類帶權(quán)路徑最短的樹。 140.平衡二叉樹，又稱AVL樹。它或者是一棵空樹，或具有下列性質(zhì)的二叉樹：(1)左子樹和右子樹都是平衡二叉書樹；(2)左子樹和右子樹的深度之差的絕對值不超過1。由此，12個結(jié)點的平衡二叉樹的深度最多可以為5層。 131-140參考答案：CDABACCCDB141.冒泡排序：對待排序的記錄進(jìn)行逐個比較，如發(fā)現(xiàn)兩個記錄是反序的，則進(jìn)行交換，直到無反序排列的記錄為止，即當(dāng)一次比較后沒有進(jìn)行交換則排序完成。由此可得，當(dāng)?shù)谄咛伺判驎r就沒有出現(xiàn)交換了，所以只比較了70次就可以完成排序。 142.中序遍歷的

33、順序是左根右；故此要n在m前，必須n在m的左方。 143.直接插入排序的比較的次數(shù)為n-1次，交換次數(shù)為0。 144.由于已知二叉樹的前序與中序后，可畫出二叉樹，并得出后序。由于前序為STUWV，所以根必然是S，由于中序是UWTVS，故此此二叉樹沒有右子樹。左子樹前序為TUWV可得左子樹根為T，中序為UWTV可得左子樹根T有一右子根V，左子樹T的左子樹根為U，U有一右子樹W。故此后序為A。 145.具有3個結(jié)點的的二叉樹有5種。分別是：左孫、左子、根；右孫、左子根；左子、根、右子；根、右子、左孫；根、右子、右孫。 146.快速排序適用了原數(shù)列沒有序的情況，如果原數(shù)大部分成序的話，速度越慢。最慢

34、的情況就是所有數(shù)據(jù)已經(jīng)成序。 147.該數(shù)組一共有80個元素，一個元素需要3個字節(jié)，故存放該數(shù)組至少需要240個字節(jié)。 148.因為把樹轉(zhuǎn)化為二叉樹時，把所有原來同層的子樹都變成了原來的左子樹的右子樹了。故此，樹的先根遍歷序列與其對應(yīng)的二叉樹的先序遍歷序列相同。 149.在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上把數(shù)據(jù)結(jié)構(gòu)分成線性結(jié)構(gòu)和非線性結(jié)構(gòu)。 150. 因為把樹轉(zhuǎn)化為二叉樹時，把所有原來同層的子樹都變成了原來的左子樹的右子樹了。故此，有序樹的后序就是其轉(zhuǎn)化成得的二叉樹的中序。 141-150參考答案：CCCACDCABB151.通過二叉樹的先序與中序可以寫出二叉樹，并由此可以得出后序為gdbehfca。 1

35、52.選擇排序的基本思想是：每次從待排序的記錄中選擇出最小(或最大)的記錄，順序放在已排好的記錄序列的最后。 153.快速排序在被排序數(shù)據(jù)中已基本有序的情況下最不利于發(fā)揮其長處。 154. A：順序存儲插入、刪除運算效率低；B：鏈表中的最后一個結(jié)點的指針域為空。C：包含n個結(jié)點的二叉排序樹的平均檢索長度為(log2n)2為底n的對數(shù)。 151-160：DBCDACBDAB 161-170：DABAACAACD 171-180：BCBADBBAAC說明：第1題到第60題為基礎(chǔ)知識； 第61題到第80題為數(shù)與編碼； 81-110為基本操作與網(wǎng)絡(luò)； 111-180為數(shù)據(jù)結(jié)構(gòu)與算法。181-190（0

36、4高中組題）：ADECBBCDCA 191-200（03高中組題）BBDABBCECB二、多項選擇題1-10 D BDE AD AB AC E B BCD D BE11-15 ABC ABDE CEF AB BCE16-25（04高中組題）BC ACDE BCD D AC BE ADE ACD ABDE BCE26-35（03高中組題）D BDE AD AB AC E B BCD D BENOIP初賽練習(xí)之二(解答題)前言：如何做解答題解答題一般是根據(jù)要求寫出表達(dá)式或畫出圖等，涉及的知識點主要有數(shù)學(xué)方面的基本知識、數(shù)據(jù)結(jié)構(gòu)方面的如樹和圖等、邏輯推理等，難點主要在寫出遞推公式。寫出公式之前要先從

37、起始值開始進(jìn)行摸索，寫出若干個結(jié)果之后再觀察其中的規(guī)律，再寫出公式，一般是F（N）=，省略號部分可能是F（N-1）、F（N-2）等的數(shù)學(xué)表達(dá)式。最后再驗證公式的正確性，時間允許的話可從數(shù)學(xué)等方面加以證明（當(dāng)然不要寫出證明過程，除非要求你說明其正確性）。有時是圖形的變換，如正方形、三角形、圓等的旋轉(zhuǎn)，先前給出了幾個點相應(yīng)的坐標(biāo)，求旋轉(zhuǎn)若干周后的各點坐標(biāo)，這種情況一般用到求余的運算，當(dāng)以N為一個周期時往往是用對N求余（mod n）的運算；如果是正反兩種情況可以使用（-1）的若干次方的形式來轉(zhuǎn)換兩種狀態(tài)，即用某一表達(dá)式乘以-1的若干次方。有時是有關(guān)組合數(shù)學(xué)的知識，如排列或組合，確定是(分步)乘法原理

38、還是（分類）加法原理。對于排列分次序，而組合不分各元素的次序：組合：C（m, n）=n*(n-1)*.*(n-m+1)/m!排列：P (m, n)= n*(n-1)*.*(n-m+1)數(shù)據(jù)結(jié)構(gòu)方面要對堆棧的先進(jìn)后出原理、隊列的先進(jìn)先出原理、二叉樹(結(jié)點)的遍歷、圖的鄰接矩陣表示法熟悉。至于邏輯推理方面的要將各個條件（描述）一一列出，排除矛盾情況，列舉出可能的情況，寫出符合條件的結(jié)果。參考答案：1、x=n*n-n+1 2、(1) 5種，圖略 (2) 對給出的任意一個n(n0)，用F(n)表示其鋪法的總數(shù)的遞推公式為： F(1)=1 F(2)=2 F(n)=F(n-2)+F(n-1)(n3)3、(

39、1) 5種 圖略 (2) f(1)=1 f(2)=2 f(3)=4 f(n)=f(n-1)+f(n-2)+f(n-3) (n3)4、 (1) a、b、c、f (2) 751 5、(1) ABCEGDFHIJ (2) 2250 C(7,2)*C(5,2)+C(7,2)*C(6,2)+C(5,2)*C(6,2)+C(7,2)*5*6+C(5,2)*7*6+C(6,2)*7*56、（1） 11 （2） 47、（1）75-55-（700/5-20*3-35*2）=10 （2） a b d f g e cNOIP初賽練習(xí)之三（閱讀程序?qū)懗龀绦蜻\行結(jié)果）前言： 如何做閱讀程序題閱讀程序題是得分的關(guān)鍵，因為不是讓你上機(jī)去運行程序，所以要一步步地讀程序，記錄相關(guān)變量的值，最好以畫表的形式來記錄相關(guān)變量值的變化情況。因為程序的運行結(jié)果只有輸出語句才有輸出，所以只寫出輸出語句的結(jié)果。有時要找出規(guī)律才能寫出結(jié)果，特別是循環(huán)次數(shù)多的情況，另外要注意邊界值，不能多算一步也不能少算一步。這幾年的初賽題一般是四道閱讀程序題，每道題8分總分為32，因此閱讀程序題最能拉開分差。附 參考答案:1. 944 2. 1 9 36 84 126 126 84 36 9 1 13. 初中組 max=42 高中組