NOIP初賽復(fù)習(xí)-普和組市公開課金獎市賽課一等獎?wù)n件

1、NOIP預(yù)賽復(fù)習(xí)普及組第1頁全國青少年信息學(xué)奧林匹克聯(lián)賽預(yù)賽1、單項選擇2、問題求解3、閱讀程序?qū)懡Y(jié)果4、完善程序第2頁 計算機產(chǎn)生是20世紀最主要科學(xué)技術(shù)大事件之一。世界上第一臺計算機（ENIAC）于1946年誕生在美國賓夕法尼亞大學(xué)，到當(dāng)前為止，計算機發(fā)展大致經(jīng)歷了四代： 第一代電子管計算機，始于1946年，結(jié)構(gòu)上以CPU為中心，使用計算機語言，速度慢，存放量小，主要用于數(shù)值計算； 第二代晶體管計算機，始于1958年，結(jié)構(gòu)上以存放器為中心，使用高級語言，應(yīng)用范圍擴大到數(shù)據(jù)處理和工業(yè)控制； 第三代中小規(guī)模集成電路計算機，始于1964年，結(jié)構(gòu)上仍以存放器為中心，增加了各種外部設(shè)備，軟件得到了一

2、定發(fā)展，文字圖象處理功效加強； 第四代大規(guī)模和超大規(guī)模集成電路計算機，始于1971年，應(yīng)用更廣泛，很多關(guān)鍵部件可集成在一個或多個芯片上，從而出現(xiàn)了微型計算機。 一、 計算機產(chǎn)生與發(fā)展第3頁計算機發(fā)展歷史劃分依據(jù)元器件電子管 晶體管 集成電路 超大規(guī)模集成電路第4頁John von Neumann馮諾依曼計算機工作原理到當(dāng)前為止，幾乎全部計算機結(jié)構(gòu)都按馮諾依曼提出方案組成，所以都可稱為馮諾依曼機。馮諾依曼思想：二進制數(shù)、存放程序和程序控制、硬件由五大部件組成。計算機工作原理就是“存放程序和程序控制”，也稱馮諾依曼工作原理。第5頁計算機硬件系統(tǒng) 計算機硬件系統(tǒng)均由運算器、控制器、存放器、輸入設(shè)備和

3、輸出設(shè)備五大部分組成。他們之間邏輯關(guān)系以下列圖所表示:第6頁設(shè)備分類：區(qū)分圖中設(shè)備第7頁內(nèi)存放器分類ROM：只讀存放器，只能讀出信息，保留廠家寫入系統(tǒng)信息RAM：隨機存放器，可讀寫，存放運行中程序和數(shù)據(jù)（普通機器內(nèi)存18G）第8頁慣用外部設(shè)備外 存：磁帶，磁盤(軟、硬)，移動閃存，光盤，.輸入設(shè)備：鍵盤，鼠標，話筒，掃描儀，數(shù)碼相機、攝像機，光筆，.輸出設(shè)備：顯示器，打印機（針式、噴墨、激光），繪圖儀，音箱，.輸入/輸出設(shè)備：磁盤驅(qū)動器,光刻機,觸摸屏, .第9頁以下哪一個設(shè)備屬于輸出設(shè)備（） 。A. 掃描儀 B. 鍵盤 C. 鼠標 D. 打印機CPU、存放器、 I/O 設(shè)備是經(jīng)過（）連接起來

4、。A. 接口 B. 總線 C. 控制線 D. 系統(tǒng)文件斷電后會丟失數(shù)據(jù)存放器是（） 。A. RAM B. ROM C. 硬盤 D. 光盤以下對操作系統(tǒng)功效描述最為完整是（） 。A. 負責(zé)外設(shè)與主機之間信息交換B. 負責(zé)診療機器故障C. 控制和管理計算機系統(tǒng)各種硬件和軟件資源使用D. 將源程序編譯成目標程序以下選項中不屬于圖像格式是（） 。A. JPEG 格式 B. TXT 格式 C. GIF 格式 D. PNG 格式在 Windows 資源管理器中，用鼠標右鍵單擊一個文件時，會出現(xiàn)一個名為“復(fù)制” 操作選項，它意思是（）。A.用剪切板中文件替換該文件B.在該文件所在文件夾中，將該文件克隆一份C

5、.將該文件復(fù)制到剪切板，并保留原文件D.將該文件復(fù)制到剪切板，并刪除原文件計算機假如缺乏（），將無法正常開啟。A內(nèi)存 B鼠標 C U 盤 D 攝像頭（）不屬于操作系統(tǒng)。AWindows BDOS CPhotoshop DNOI LinuxdbacbCAC第10頁當(dāng)前計算機芯片（集成電路）制造主要原料是（），它是一個能夠在沙子中提煉出物質(zhì)。A硅 B銅 C鍺 D鋁當(dāng)前個人電腦（）市場擁有率最靠前廠商包含 Intel、AMD 等企業(yè)。A顯示器 BCPU C內(nèi)存 D鼠標1946 年誕生于美國賓夕法尼亞大學(xué) ENIAC 屬于（）計算機。A電子管 B晶體管 C集成電路 D超大規(guī)模集成電路矢量圖（Vecto

6、r Image）圖形文件所占貯存空間比較小，而且不論怎樣放大、縮小或旋轉(zhuǎn)等都不會失真，是因為它（）。A統(tǒng)計了大量像素塊色彩值來表示圖像B用點、直線或者多邊形等基于數(shù)學(xué)方程幾何圖元來表示圖像C每個像素點顏色信息均用矢量表示D把文件保留在互聯(lián)網(wǎng)，采取在線瀏覽方式查看圖像地址總線位數(shù)決定了 CPU 可直接尋址內(nèi)存空間大小，比如地址總線為 16 位，其最大可尋址空間為 64KB。假如地址總線是 32 位，則理論上最大可尋址內(nèi)存空間為（ ）。A128KB B1MB C1GB D4GB藍牙和 Wi-Fi 都是（）設(shè)備。A無線廣域網(wǎng) B無線城域網(wǎng) C無線局域網(wǎng) D無線路由器ABABDC第11頁一片容量為 8

7、GB SD 卡能存放大約（）張大小為 2MB 數(shù)碼照片。A. 1600B. C. 4000D. 1 6000摩爾定律（Moores law）是由英特爾創(chuàng)始人之一戈登摩爾（Gordon Moore）提出來。依據(jù)摩爾定律，在過去幾十年以及在可預(yù)測未來幾年，單塊集成電路集成度大約每（ ）個月翻一番。A. 1B. 6C. 18 D. 36存放器是（ ）主要組成部分。A. 硬盤 B. 高速緩存C.內(nèi)存D.中央處理器有些人認為，在個人電腦送修前，將文件放入回收站中就是已經(jīng)將其刪除了。這種想法是（ ）。A. 正確，將文件放入回收站意味著徹底刪除、無法恢復(fù)B. 不正確，只有將回收站清空后，才意味著徹底刪除、無

8、法恢復(fù)C. 不正確，即使將回收站清空，文件只是被標識為刪除，仍可能經(jīng)過恢復(fù)軟件找回D. 不正確，只要在硬盤上出現(xiàn)過文件，永遠不可能被徹底刪除從 ENIAC 到 當(dāng) 前最先進 計算機 ，馮諾依曼體系結(jié)構(gòu)一直占有 主要 地位。馮 諾依曼體系結(jié) 構(gòu)關(guān)鍵內(nèi)容是 （ ） 。A. 采取開關(guān)電路B. 采取半導(dǎo)體器件C. 采取存放程序和程序控制原理D. 采取鍵盤輸入Linux下可執(zhí)行文件默認擴展名為（ ）。A. exe B. com C. dll D. 以上都不是提出“存放程序”計算機工作原理是（ ）。A. 克勞德香農(nóng) B. 戈登摩爾 C. 查爾斯巴比奇 D. 馮諾依曼CCDCCDD第12頁主存放器存取速度比

9、中央處理器（CPU）工作速度慢得多，從而使得后者效率受到影響。而依據(jù)局部性原理，CPU所訪問存放單元通常都趨于聚集在一個較小連續(xù)區(qū)域中。于是，為了提升系統(tǒng)整體執(zhí)行效率，在CPU中引入了（ ）。A. 存放器 B. 高速緩存 C. 閃存 D. 外存在程序運行過程中，假如遞歸調(diào)用層數(shù)過多，會因為（）引發(fā)錯誤。A系統(tǒng)分配?？臻g溢出 B系統(tǒng)分配堆空間溢出C系統(tǒng)分配隊列空間溢出 D系統(tǒng)分配鏈表空間溢出仿生學(xué)問世開辟了獨特科學(xué)技術(shù)發(fā)展道路。人們碩士物體結(jié)構(gòu)、功效和工作原理，并將這些原理移植于新興工程技術(shù)中。以下關(guān)于仿生學(xué)敘述，錯誤是（）A由研究蝙蝠，創(chuàng)造雷達 B由研究蜘蛛網(wǎng)，創(chuàng)造因特網(wǎng)C由研究海豚，創(chuàng)造聲納

10、 D由研究電魚，創(chuàng)造伏特電池在使用高級語言編寫程序時，普通提到“空間復(fù)雜度”中“空間”是指（ ）。A. 程序運行時理論上所占內(nèi)存空間B. 程序運行時理論上所占數(shù)組空間C. 程序運行時理論上所占硬盤空間D. 程序源文件理論上所占硬盤空間以下哪個是面向?qū)ο蟾呒壵Z言（） 。A. 匯編語言 B. C+ C. Fortran D. BasicBABAx第13頁 用要求符號和規(guī)則來表示數(shù)方法十 進 制 數(shù):基數(shù)為10，有十個數(shù)碼 0 9，運算規(guī)則逢十進一二 進 制 數(shù):基數(shù)為2，有兩個數(shù)碼 0 和 1，運算規(guī)則逢二進一十六進制數(shù): 數(shù)碼 0 9, AF八 進 制 數(shù): 數(shù)碼 0 7信息在計算機中存放 數(shù)制

11、第14頁位權(quán)處于不一樣位上數(shù)字所代表值不一樣，一個數(shù)字在某個固定位置上所代表值是固定，這個固定位上值稱為位權(quán)或權(quán)值。 位權(quán)與基數(shù)關(guān)系是：各進位制中位權(quán)值恰巧是基數(shù)若干次冪。所以，任何一個數(shù)制表示數(shù)都能夠?qū)懗砂次粰?quán)展開多項式之和。比如，以下數(shù)制位權(quán)展開式：(56789)10 =5104+6103+7102+8101+9100(1011.11)2 =123+022+121+120+12-1+12-2(FDE.5)16 =15162+13161+14160+516-1 任意進制數(shù)（用R表示）從小數(shù)點以左，每一位對應(yīng)權(quán)值分別為 R0、R1 、R2、R3、R4、；以小數(shù)點以右，每一位對應(yīng)權(quán)值分別為 R1

12、、R2 、R3、。 第15頁十進制轉(zhuǎn)換成非十進制將十進制數(shù)轉(zhuǎn)換為其它進制數(shù)時，整數(shù)部分和小數(shù)部分需分別轉(zhuǎn)換，然后合并。 整數(shù)轉(zhuǎn)換：用“除R取余”法。注：R表示轉(zhuǎn)換結(jié)果為R進制數(shù)（如將十進制數(shù)轉(zhuǎn)換為二進制數(shù)R就為2，轉(zhuǎn)換為八進制數(shù)R就為8，轉(zhuǎn)換為十六進制數(shù)R就為16）。 小數(shù)轉(zhuǎn)換：用“乘R取整”法。注意：這種方法可能產(chǎn)生取不完情況，也就是說一個十進制數(shù)可能無法準確地轉(zhuǎn)換成R進制數(shù)，這就是“存放誤差”，可依據(jù)要求保留若干位。 第16頁【例】 將(91.453)10轉(zhuǎn)換成二進制數(shù)（取4位小數(shù)）。得 (91.453)10 = (1011011.0111)2 第17頁字節(jié)(Byte)：8位(bit)二進

13、制數(shù) 1KB（千字節(jié)）=1024 Byte 1MB（兆）=1024 KB 1GB=1024 MB 1TB =1024 GB 信息量單位第18頁數(shù)值（經(jīng)過運算轉(zhuǎn)換） (109)10 (1101101)2ASCII碼 （American Standard Code for Information Interchange） A （65）10 B（66）10 a （97） 10 c （99）10UNICODE編碼 敏 (25935) 10 (654F) 16 其它信息 專用程序轉(zhuǎn)換例：第19頁補碼正數(shù)補碼與原碼相同，負數(shù)補碼就是它反碼在末位加“1”。（+64）10補碼 01000000 （-64）10

14、補碼 11000000 總之，正數(shù)原碼、反碼、補碼都相同，就是它原碼；負數(shù)原碼符號位取1，其余不變；負數(shù)反碼符號位取1，其余部分求反；負數(shù)補碼就是它反碼在末位加“1”。【例】 二進制數(shù) 原碼 反碼 補碼+1011010 01011010 01011010 01011010-1011010 11011010 10100101 10100110第20頁二進制數(shù) 00100100 和 00010101 和是（）。A. 00101000 B. 001010100 C. 01000101 D. 00111001二進制數(shù) 11.01 在十進制下是（）。A.3.25B.4.125C.6.25D.11.125

15、在十六進制表示法中，字母 A 相當(dāng)于十進制中（）。A.9B.10C.15D.16在二進制下，1100100 + （ ） = 1110001。A. 1011B. 1101C. 1010D. 1111字符“0” ASCII 碼為 48，則字符“9” ASCII 碼為（ ）。A. 39 B. 57C. 120D. 視詳細計算機而定一個正整數(shù)在二進制下有 100 位，則它在十六進制下有（ ）位。A. 7B. 13C. 25D. 不能確定2E+03表示（ ）。A. 2.03 B. 5 C. 8 D. 一個字節(jié)（byte）由（ ）個二進制位組成。A. 8 B. 16 C. 32 D. 以上都有可能DABA

16、B CDA第21頁設(shè)X、Y、Z分別代表三進制下一位數(shù)字，若等式XY + ZX = XYX在三進制下成立，那么一樣在三進制下，等式XY * ZX = （ ）也成立。A. YXZ B. ZXY C. XYZ D. XZY一個字長為8位整數(shù)補碼是11111001，則它原碼是（ ）。A. 00000111 B. 01111001 C. 11111001 D. 100001111TB 代表字節(jié)數(shù)量是（）。A. 2 10 次方 B. 2 20 次方C. 2 30 次方 D. 2 40 次方以下各無符號十進制整數(shù)中，能用八位二進制表示數(shù)中最大是（） 。A. 296 B. 133 C. 256 D. 199一

17、個 32 位整型變量占用（）個字節(jié)。A.4B.8C.32D.128十六進制數(shù) 9A 在（）進制下是 232。A四 B八 C十D十二BDDdaB第22頁二、計算機網(wǎng)絡(luò)第23頁10月10日計算機網(wǎng)絡(luò)拓撲結(jié)構(gòu)總線型拓撲結(jié)構(gòu)前一頁后一頁第24頁10月10日計算機網(wǎng)絡(luò)拓撲結(jié)構(gòu)環(huán)型拓撲結(jié)構(gòu)前一頁后一頁第25頁10月10日計算機網(wǎng)絡(luò)拓撲結(jié)構(gòu)星型拓撲結(jié)構(gòu)前一頁后一頁第26頁10月10日計算機網(wǎng)絡(luò)拓撲結(jié)構(gòu)樹型拓撲結(jié)構(gòu)前一頁后一頁第27頁10月10日計算機網(wǎng)絡(luò)拓撲結(jié)構(gòu)網(wǎng)狀型拓撲結(jié)構(gòu)網(wǎng)狀型拓撲結(jié)構(gòu)主要用于互聯(lián)網(wǎng)前一頁后一頁第28頁10月10日計算機網(wǎng)絡(luò)拓撲結(jié)構(gòu)無線型拓撲結(jié)構(gòu)網(wǎng)狀型拓撲結(jié)構(gòu)主要用于互聯(lián)網(wǎng)前一頁后一頁第

18、29頁IP 地 址 組 成IP地址是32位二進制數(shù)，分成4組，每組8位二進制數(shù)，每組之間用圓點隔開，通慣用十進制來表示；000000000000000000000000000000001111111111111111111111111111111155IP地址范圍是：55；寬帶上網(wǎng)不是固定IP，而是連網(wǎng)時由ISP(Internet服務(wù)提供商 )隨機給；每個網(wǎng)絡(luò)上計算機IP不會相同。第30頁Internet域名系統(tǒng)域名由幾個英文單詞組成，中間用點（.）連接，中間不能有空格。域名地址與IP地址實際上是同一個東西。域名系統(tǒng)是為了方便解釋機器IP地址而設(shè)置。 如校IP是：8 域名是：第31頁域名組成域

19、名系統(tǒng)采取層次結(jié)構(gòu)，按地理域或機構(gòu)域進行分層。域名中，從右到左依次為最高域名段、次高域名段等，最左一個字段為主機名 機構(gòu)域：com 商業(yè)機構(gòu)edu 教育機構(gòu)gov 政府機構(gòu) net 網(wǎng)絡(luò)組織地理域：cn 中國 jp 日本hk 香港M第32頁OSI開放系統(tǒng)互聯(lián)參考模型應(yīng)用層Application表示層Presentation會話層session傳輸層transport物理層Physical數(shù)據(jù)鏈路層Data Link網(wǎng)絡(luò)層Network7654321處理網(wǎng)絡(luò)應(yīng)用數(shù)據(jù)表示主機間通信進程間連接尋址和最短路徑介質(zhì)訪問（接入）二進制傳輸?shù)?3頁常見網(wǎng)絡(luò)協(xié)議TCP（Transmission Control

20、 Protocol 傳輸控制協(xié)議）遠程登錄協(xié)議Telnet、文件傳輸協(xié)議FTP、超文本傳輸協(xié)議HTTP、域名服務(wù)DNS、簡單郵件傳輸協(xié)議SMTP、郵局協(xié)議POP3等第34頁以下哪一個是屬于電子郵件收發(fā)協(xié)議（）。A. SMTP B. UDP C. P2P D. FTP以下幾個 32 位 IP 地址中，書寫錯誤是（） 。A. 7 B. C. 256.256.129.1 D. IPv4 協(xié)議使用 32 位地址，伴隨其不停被分配，地址資源日趨枯竭。所以，它正逐步被 使用（）位地址 IPv6 協(xié)議所取代。A.40B.48C.64D.128通常在搜索引擎中，對某個關(guān)鍵詞加上雙引號表示（）。A.排除關(guān)鍵詞，

21、不顯示任何包含該關(guān)鍵詞結(jié)果B.將關(guān)鍵詞分解，在搜索結(jié)果中必須包含其中一部分C.準確搜索，只顯示包含整個關(guān)鍵詞結(jié)果D.站內(nèi)搜索，只顯示關(guān)鍵詞所指向網(wǎng)站內(nèi)容中國國家頂級域名是（）。A.cnB.chC.chnD.china（）是主要用于顯示網(wǎng)頁服務(wù)器或者文件系統(tǒng) HTML 文件內(nèi)容，并讓用戶與這些文件交互一個軟件。A資源管理器 B瀏覽器 C電子郵件 D編譯器acDCAB第35頁（）是當(dāng)前互聯(lián)網(wǎng)上慣用 E-mail 服務(wù)協(xié)議。AHTTP BFTP CPOP3 DTelnet在以下HTML語句中，能夠正確產(chǎn)生一個指向NOI官方網(wǎng)站超鏈接是（ ）。A. 歡迎訪問NOI網(wǎng)站B. 歡迎訪問NOI網(wǎng)站C. D.

22、 歡迎訪問NOI網(wǎng)站關(guān)于HTML下面哪種說法是正確：A.HTML實現(xiàn)了文本、圖形、聲音乃至視頻信息統(tǒng)一編碼。B.HTML全稱為超文本標識語言。C.網(wǎng)上廣泛使用 Flash動畫都是由HTML編寫。D.HTML也是一個高級程序設(shè)計語言。CBB第36頁三、算法基礎(chǔ)第37頁前綴表示式“+ 3 * 2 + 5 12”值是（ ）。A. 23 B. 25 C. 37 D. 65全國青少年信息學(xué)奧林匹克系列活動主辦單位是（ ）。A. 教育部 B. 科技部 C. 共青團中央 D. 中國計算機學(xué)會以下邏輯表示式值恒為真是（ ）。A. P(PQ)(PQ) B. Q(PQ)(PQ)C. PQ(PQ)(PQ) D. P

23、Q(PQ)(PQ)假如樹根算第1層，那么一棵n層二叉樹最多有（ ）個結(jié)點。A. 2n-1 B. 2n C. 2n+1 D. 2n+1假如根結(jié)點深度記為 1，則一棵恰有 個葉結(jié)點二叉樹深度最少是（ ）。 A. 10B. 11C. 12D. 13體育課鈴聲響了，同學(xué)們都陸續(xù)地奔向操場，按老師要求從高到矮站成一排。每個同學(xué)按次序來到操場時，都從排尾走向排頭，找到第一個比自己高同學(xué)，并站在他后面。這種站隊方法類似于（ ）算法 。A. 快速排序B. 插入排序C. 冒泡排序D. 歸并排序CDAACB第38頁無向完全圖是圖中每對頂點之間都恰有一條邊簡單圖。已知無向完全圖 G 有 7 個頂點，則它共有（ ）條

24、邊。A. 7B. 21C. 42D. 49原字符串中任意一段連續(xù)字符所組成新字符串稱為子串。則字符“AAABBBCCC”共有（）個不一樣非空子串。A3 B12 C36 D45（）就是把一個復(fù)雜問題分成兩個或更多相同類似子問題，再把子問題分解成更小子問題直到最終子問題能夠簡單地直接求解。而原問題解就是子問題解并。A動態(tài)規(guī)劃 B貪心 C分治 D搜索使用冒泡排序?qū)π蛄羞M行升序排列，每執(zhí)行一次交換操作系統(tǒng)將會降低 1 個逆序?qū)Γ孕蛄?5，4，3，2，1 需要執(zhí)行（）次操作，才能完成冒泡排序。A0 B5 C10 D15（）是一個先進先出線性表。A棧 B隊列 C哈希表（散列表） D二叉樹BCCCB第3

25、9頁把 64 位非零浮點數(shù)強制轉(zhuǎn)換成 32 位浮點數(shù)后，不可能（）。A.大于原數(shù)B.小于原數(shù)C.等于原數(shù)D.與原數(shù)符號相反CCF NOIP 復(fù)賽全國統(tǒng)一評測時使用系統(tǒng)軟件是（）。A.NOI WindowsB.NOI LinuxC.NOI Mac OSD.NOI DOS在一個無向圖中，假如任意兩點之間都存在路徑相連，則稱其為連通圖。下列圖是一個有4 個頂點、6 條邊連通圖。若要使它不再是連通圖，最少要刪去其中（）條邊。A.1B.2C.3D.4下列圖中所使用數(shù)據(jù)結(jié)構(gòu)是（）。 A.哈希表B.棧C.隊列D.二叉樹邏輯表示式（）值與變量 A 真假無關(guān)。A.(A B) AB.(A B) BC.(A B)

26、(A B)D.(A B) A BDBCBC第40頁下面故事與（）算法有著異曲同工之妙。從前有座山，山里有座廟，廟里有個老和尚在給小和尚講故事：從前有座山，山 里有座廟，廟里有個老和尚在給小和尚講故事：從前有座山，山里有座廟，廟里有個 老和尚給小和尚講故事.A.枚舉B.遞歸C.貪心D.分治鏈表不含有特點是（） 。A. 無須事先預(yù)計存放空間 B. 可隨機訪問任一元素C. 插入刪除不需要移動元素 D. 所需空間與線性表長度成正比bb第41頁四、問題求解把 M 個一樣球放到 N 個一樣袋子里，允許有袋子空著不放，問共有多少種不一樣放置方法？ （用 K 表示） 。比如： M = 7， N = 3 時， K = 8；在這里認為（ 5,1,1）和（ 1,5,1）是同一個放置方法。問： M = 8， N = 5 時， K = _。如圖所表示，圖中每條邊上數(shù)字表示該邊長度，則從 A到 E最短距離是_。1811第42頁7 個同學(xué)圍坐一圈，要選 2 個不相鄰作為代表，有_種不一樣選法。某系統(tǒng)自稱使