NOIP初賽復習-普及組

NOIP初賽復習普及組全國青少年信息學奧林匹克聯賽初賽

1、單項選擇

2、問題求解

3、閱讀程序寫結果

4、完善程序計算機的產生是20世紀最重要的科學技術大事件之一。世界上的第一臺計算機〔ENIAC〕于1946年誕生在美國賓夕法尼亞大學，到目前為止，計算機的開展大致經歷了四代：①第一代電子管計算機，始于1946年，結構上以CPU為中心，使用計算機語言，速度慢，存儲量小，主要用于數值計算；②第二代晶體管計算機，始于1958年，結構上以存儲器為中心，使用高級語言，應用范圍擴大到數據處理和工業(yè)控制；③第三代中小規(guī)模集成電路計算機，始于1964年，結構上仍以存儲器為中心，增加了多種外部設備，軟件得到了一定的開展，文字圖象處理功能加強；④

第四代大規(guī)模和超大規(guī)模集成電路計算機，始于1971年，應用更廣泛，很多核心部件可集成在一個或多個芯片上，從而出現了微型計算機。一、計算機的產生與開展計算機開展歷史的劃分依據－元器件電子管

晶體管

集成電路

超大規(guī)模集成電路JohnvonNeumann馮

諾依曼計算機的工作原理到目前為止，幾乎所有的計算機的結構都按馮·諾依曼提出的方案組成，因此都可稱為馮·諾依曼機。馮·諾依曼思想：二進制數、存儲程序和程序控制、硬件由五大部件構成。計算機的工作原理就是“存儲程序和程序控制”，也稱馮·諾依曼工作原理。計算機硬件系統計算機硬件系統均由運算器、控制器、存儲器、輸入設備和輸出設備五大局部構成。他們之間的邏輯關系如以下圖所示:設備分類：區(qū)分圖中設備內存儲器的分類ROM：只讀存儲器，只能讀出信息，保存廠家寫入的系統信息RAM：隨機存儲器，可讀寫，存放運行中的程序和數據〔一般機器內存1~8G〕常用外部設備外存：磁帶，磁盤(軟、硬)，移動閃存，光盤，...輸入設備：鍵盤，鼠標，話筒，掃描儀，數碼相機、攝像機，光筆，...輸出設備：顯示器，打印機〔針式、噴墨、激光〕，繪圖儀，音箱，...輸入/輸出設備：磁盤驅動器,光刻機,觸摸屏,...以下哪一種設備屬于輸出設備〔〕。 A.掃描儀 B.鍵盤 C.鼠標 D.打印機CPU、存儲器、I/O設備是通過〔〕連接起來的。 A.接口 B.總線 C.控制線 D.系統文件斷電后會喪失數據的存儲器是〔〕。

A.RAM B.ROM C.硬盤 D.光盤以下對操作系統功能的描述最為完整的是〔〕。

A.負責外設與主機之間的信息交換

B.負責診斷機器的故障

C.控制和管理計算機系統的各種硬件和軟件資源的使用

D.將源程序編譯成目標程序以下選項中不屬于圖像格式的是〔〕。

A.JPEG格式 B.TXT格式 C.GIF格式 D.PNG格式在Windows資源管理器中，用鼠標右鍵單擊一個文件時，會出現一個名為“復制”的操作選項，它的意思是〔〕。A. 用剪切板中的文件替換該文件B. 在該文件所在文件夾中，將該文件克隆一份C. 將該文件復制到剪切板，并保存原文件D. 將該文件復制到剪切板，并刪除原文件計算機如果缺少〔〕，將無法正常啟動。 A．內存 B．鼠標 C．U盤 D．攝像頭〔〕不屬于操作系統。 A．Windows B．DOS C．Photoshop D．NOILinuxdbacbCAC目前計算機芯片〔集成電路〕制造的主要原料是〔〕，它是一種可以在沙子中提煉出的物質。 A．硅 B．銅 C．鍺 D．鋁目前個人電腦的〔〕市場占有率最靠前的廠商包括Intel、AMD等公司。 A．顯示器 B．CPU C．內存 D．鼠標1946年誕生于美國賓夕法尼亞大學的ENIAC屬于〔〕計算機。 A．電子管 B．晶體管 C．集成電路 D．超大規(guī)模集成電路矢量圖〔VectorImage〕圖形文件所占的貯存空間比較小，并且無論如何放大、縮小或旋轉等都不會失真，是因為它〔〕。A．記錄了大量像素塊的色彩值來表示圖像B．用點、直線或者多邊形等基于數學方程的幾何圖元來表示圖像C．每個像素點的顏色信息均用矢量表示D．把文件保存在互聯網，采用在線瀏覽的方式查看圖像地址總線的位數決定了CPU可直接尋址的內存空間大小，例如地址總線為16位，其最大的可尋址空間為64KB。如果地址總線是32位，那么理論上最大可尋址的內存空間為〔〕。 A．128KB B．1MB C．1GB D．4GB藍牙和Wi-Fi都是〔〕設備。 A．無線廣域網 B．無線城域網 C．無線局域網 D．無線路由器ABABDC一片容量為8GB的SD卡能存儲大約〔〕張大小為2MB的數碼照片。 A.1600 B.2000 C.4000 D.16000摩爾定律〔Moore'slaw〕是由英特爾創(chuàng)始人之一戈登·摩爾〔GordonMoore〕提出來的。根據摩爾定律，在過去幾十年以及在可預測的未來幾年，單塊集成電路的集成度大約每〔〕個月翻一番。 A.1 B.6 C.18 D.36存放器是〔〕的重要組成局部。 A.硬盤 B.高速緩存 C.內存 D.中央處理器有人認為，在個人電腦送修前，將文件放入回收站中就是已經將其刪除了。這種想法是〔〕。A.正確的，將文件放入回收站意味著徹底刪除、無法恢復B.不正確的，只有將回收站清空后，才意味著徹底刪除、無法恢復C.不正確的，即使將回收站清空，文件只是被標記為刪除，仍可能通過恢復軟件找回D.不正確的，只要在硬盤上出現過的文件，永遠不可能被徹底刪除從ENIAC到當前最先進的計算機，馮·諾依曼體系結構始終占有重要的地位。馮·諾依曼體系結構的核心內容是〔〕。A.采用開關電路 B.采用半導體器件C.采用存儲程序和程序控制原理 D.采用鍵盤輸入Linux下可執(zhí)行文件的默認擴展名為〔〕。 A.exe B.com C.dll D.以上都不是提出“存儲程序”的計算機工作原理的是〔〕。 A.克勞德·香農 B.戈登·摩爾 C.查爾斯·巴比奇D.馮·諾依曼CCDCCDD主存儲器的存取速度比中央處理器〔CPU〕的工作速度慢得多，從而使得后者的效率受到影響。而根據局部性原理，CPU所訪問的存儲單元通常都趨于聚集在一個較小的連續(xù)區(qū)域中。于是，為了提高系統整體的執(zhí)行效率，在CPU中引入了〔〕。 A.存放器B.高速緩存C.閃存D.外存在程序運行過程中，如果遞歸調用的層數過多，會因為〔〕引發(fā)錯誤。 A．系統分配的?？臻g溢出 B．系統分配的堆空間溢出 C．系統分配的隊列空間溢出 D．系統分配的鏈表空間溢出仿生學的問世開辟了獨特的科學技術開展道路。人們研究生物體的結構、功能和工作原理，并將這些原理移植于新興的工程技術中。以下關于仿生學的表達，錯誤的選項是〔〕 A．由研究蝙蝠，創(chuàng)造雷達B．由研究蜘蛛網，創(chuàng)造因特網 C．由研究海豚，創(chuàng)造聲納D．由研究電魚，創(chuàng)造伏特電池在使用高級語言編寫程序時，一般提到的“空間復雜度”中的“空間”是指〔〕。A.程序運行時理論上所占的內存空間B.程序運行時理論上所占的數組空間C.程序運行時理論上所占的硬盤空間D.程序源文件理論上所占的硬盤空間以下哪個是面向對象的高級語言〔〕。

A.匯編語言 B.C++ C.Fortran D.BasicBABAx用規(guī)定的符號和規(guī)那么來表示數的方法十進制數:基數為10，有十個數碼0~9，運算規(guī)那么逢十進一二進制數:基數為2，有兩個數碼0和1，運算規(guī)那么逢二進一十六進制數:數碼0~9,A~F八進制數:數碼0~7信息在計算機中的存儲

數制位權處在不同位上的數字所代表的值不同，一個數字在某個固定位置上所代表的值是固定的，這個固定位上的值稱為位權或權值。位權與基數的關系是：各進位制中位權的值恰巧是基數的假設干次冪。因此，任何一種數制表示的數都可以寫成按位權展開的多項式之和。例如，以下數制的位權展開式：(56789)10=5×104+6×103+7×102+8×101+9×100(1011.11)2=1×23+0×22+1×21+1×20+1×2-1+1×2-2(FDE.5)16=15×162+13×161+14×160+5×16-1任意進制數〔用R表示〕從小數點以左，每一位對應的權值分別為R0、R1、R2、R3、R4、……；以小數點以右，每一位對應的權值分別為R－1、R－2、R－3、……。十進制轉換成非十進制將十進制數轉換為其他進制數時，整數局部和小數局部需分別轉換，然后合并。①整數轉換：用“除R取余”法。注：R表示轉換結果為R進制的數〔如將十進制數轉換為二進制數R就為2，轉換為八進制數R就為8，轉換為十六進制數R就為16〕。②小數轉換：用“乘R取整”法。注意：這種方法可能產生取不完的情況，也就是說一個十進制數可能無法精確地轉換成R進制數，這就是“存儲誤差”，可根據要求保存假設干位?！纠繉?91.453)10轉換成二進制數〔取4位小數〕。

得

(91.453)10=(1011011.0111)2字節(jié)(Byte)：8位(bit)二進制數1KB〔千字節(jié)〕=1024Byte1MB〔兆〕=1024KB1GB=1024MB1TB=1024GB

信息量的單位數值〔通過運算轉換〕(109)10→(1101101)2ASCII碼〔AmericanStandardCodeforInformationInterchange〕A→〔65〕10B→〔66〕10a→〔97〕10c→〔99〕10UNICODE編碼敏→(25935) 10→(654F)16其它信息專用程序轉換例：補碼正數的補碼與原碼相同，負數的補碼就是它的反碼在末位加“1”?！?64〕10的補碼01000000〔-64〕10的補碼11000000總之，正數的原碼、反碼、補碼都相同，就是它的原碼；負數的原碼符號位取1，其余不變；負數的反碼符號位取1，其余局部求反；負數的補碼就是它的反碼在末位加“1”。【例】二進制數原碼反碼補碼+1011010010110100101101001011010-1011010110110101010010110100110二進制數00100100和00010101的和是〔〕。

A.00101000 B.001010100 C.01000101 D.00111001二進制數11.01在十進制下是〔〕。 A. 3.25 B. 4.125 C. 6.25 D. 11.125在十六進制表示法中，字母A相當于十進制中的〔〕。A. 9 B. 10 C. 15 D. 16在二進制下，1100100+〔〕=1110001。 A.1011 B.1101 C.1010 D.1111字符“0”的ASCII碼為48，那么字符“9”的ASCII碼為〔〕。

A.39 B.57 C.120 D.視具體的計算機而定一個正整數在二進制下有100位，那么它在十六進制下有〔〕位。 A.7 B.13 C.25 D.不能確定2E+03表示〔〕。 A.2.03 B.5 C.8 D.2000一個字節(jié)〔byte〕由〔〕個二進制位組成。 A.8 B.16 C.32 D.以上都有可能DABABCDA設X、Y、Z分別代表三進制下的一位數字，假設等式XY+ZX=XYX在三進制下成立，那么同樣在三進制下，等式XY*ZX=〔〕也成立。 A.YXZ B.ZXY C.XYZ D.XZY一個字長為8位的整數的補碼是11111001，那么它的原碼是〔〕。 A.00000111B.01111001C.11111001D.100001111TB代表的字節(jié)數量是〔〕。

A.2的10次方 B.2的20次方 C.2的30次方 D.2的40次方以下各無符號十進制整數中，能用八位二進制表示的數中最大的是〔〕。

A.296 B.133 C.256 D.199一個32位整型變量占用〔〕個字節(jié)。 A. 4 B. 8 C. 32 D. 128十六進制數9A在〔〕進制下是232。 A．四 B．八 C．十 D．十二BDDdaB二、計算機網絡2024年6月1日計算機網絡拓撲結構總線型拓撲結構前一頁后一頁2024年6月1日計算機網絡拓撲結構環(huán)型拓撲結構前一頁后一頁2024年6月1日計算機網絡拓撲結構星型拓撲結構前一頁后一頁2024年6月1日計算機網絡拓撲結構樹型拓撲結構前一頁后一頁2024年6月1日計算機網絡拓撲結構網狀型拓撲結構網狀型拓撲結構主要用于互聯網前一頁后一頁2024年6月1日計算機網絡拓撲結構無線型拓撲結構網狀型拓撲結構主要用于互聯網前一頁后一頁IP地址的組成IP地址的是32位二進制數，分成4組，每組8位二進制數，每組之間用圓點隔開，通常用十進制來表示；0000000000000000000000000000000011111111111111111111111111111111IP地址范圍是：～；寬帶上網不是固定IP，而是連網時由ISP(Internet效勞提供商)隨機給的；每個網絡上的計算機的IP不會相同。Internet的域名系統域名由幾個英文單詞組成，中間用點〔.〕連接，中間不能有空格。域名地址與IP地址實際上是同一個東西。域名系統是為了方便解釋機器的IP地址而設立的。如校的IP是：域名是：域名的構成域名系統采用層次結構，按地理域或機構域進行分層。域名中，從右到左依次為最高域名段、次高域名段等，最左的一個字段為主機名機構域：com

商業(yè)機構edu

教育機構gov政府機構

net網絡組織地理域：cn

中國

jp日本hk香港MicrosoftOSI開放系統互聯參考模型應用層Application表示層Presentation會話層session傳輸層transport物理層Physical數據鏈路層DataLink網絡層Network7654321處理網絡應用數據表示主機間通信進程間的連接尋址和最短路徑介質訪問（接入）二進制傳輸常見網絡協議TCP〔TransmissionControlProtocol傳輸控制協議〕遠程登錄協議Telnet、文件傳輸協議FTP、超文本傳輸協議HTTP、域名效勞DNS、簡單郵件傳輸協議SMTP、郵局協議POP3等以下哪一種是屬于電子郵件收發(fā)的協議〔〕。

A.SMTP B.UDP C.P2P D.FTP以下幾個32位IP地址中，書寫錯誤的選項是〔〕。

A.7 B.IPv4協議使用32位地址，隨著其不斷被分配，地址資源日趨枯竭。因此，它正逐漸被使用〔〕位地址的IPv6協議所取代。 A. 40 B. 48 C. 64 D. 128通常在搜索引擎中，對某個關鍵詞加上雙引號表示〔〕。 A. 排除關鍵詞，不顯示任何包含該關鍵詞的結果 B. 將關鍵詞分解，在搜索結果中必須包含其中的一局部 C. 精確搜索，只顯示包含整個關鍵詞的結果 D. 站內搜索，只顯示關鍵詞所指向網站的內容中國的國家頂級域名是〔〕。 A. B. .ch C. .chn D. .china〔〕是主要用于顯示網頁效勞器或者文件系統的HTML文件的內容，并讓用戶與這些文件交互的一種軟件。 A．資源管理器 B．瀏覽器 C．電子郵件 D．編譯器acDCAB〔〕是目前互聯網上常用的E-mail效勞協議。

A．HTTP B．FTP C．POP3 D．Telnet在以下HTML語句中，可以正確產生一個指向NOI官方網站的超鏈接的是〔〕。 A.<aurl="://noi">歡送訪問NOI網站</a> B.<ahref="://noi">歡送訪問NOI網站</a> C.<a>://noi</a> D.<aname="://noi">歡送訪問NOI網站</a>關于HTML下面哪種說法是正確的：A.HTML實現了文本、圖形、聲音乃至視頻信息的統一編碼。B.HTML全稱為超文本標記語言。C.網上廣泛使用的Flash動畫都是由HTML編寫的。D.HTML也是一種高級程序設計語言。CBB三、算法根底前綴表達式“+3*2+512”的值是〔〕。 A.23B.25C.37D.65全國青少年信息學奧林匹克系列活動的主辦單位是〔〕。 A.教育部B.科技部C.共青團中央D.中國計算機學會以下邏輯表達式的值恒為真的是〔〕。 A.P∨(?P∧Q)∨(?P∧?Q) B.Q∨(?P∧Q)∨(P∧?Q) C.P∨Q∨(P∧?Q)∨(?P∧Q) D.P∨?Q∨(P∧?Q)∨(?P∧?Q)如果樹根算第1層，那么一棵n層的二叉樹最多有〔〕個結點。 A.2n-1 B.2n C.2n+1D.2n+1如果根結點的深度記為1，那么一棵恰有2011個葉結點的二叉樹的深度最少是〔〕。 A.10 B.11 C.12 D.13體育課的鈴聲響了，同學們都陸續(xù)地奔向操場，按老師的要求從高到矮站成一排。每個同學按順序來到操場時，都從排尾走向排頭，找到第一個比自己高的同學，并站在他的后面。這種站隊的方法類似于〔〕算法。 A.快速排序 B.插入排序 C.冒泡排序 D.歸并排序CDAACB無向完全圖是圖中每對頂點之間都恰有一條邊的簡單圖。無向完全圖G有7個頂點，那么它共有〔〕條邊。 A.7 B.21 C.42 D.49原字符串中任意一段連續(xù)的字符所組成的新字符串稱為子串。那么字符“AAABBBCCC”共有〔〕個不同的非空子串。 A．3 B．12 C．36 D．45〔〕就是把一個復雜的問題分成兩個或更多的相同類似的子問題，再把子問題分解成更小的子問題……直到最后的子問題可以簡單地直接求解。而原問題的解就是子問題解的并。 A．動態(tài)規(guī)劃 B．貪心 C．分治 D．搜索使用冒泡排序對序列進行升序排列，每執(zhí)行一次交換操作系統將會減少1個逆序對，因此序列5，4，3，2，1需要執(zhí)行〔〕次操作，才能完成冒泡排序。 A．0 B．5 C．10 D．15〔〕是一種先進先出的線性表。 A．棧 B．隊列 C．哈希表〔散列表〕 D．二叉樹BCCCB把64位非零浮點數強制轉換成32位浮點數后，不可能〔〕。 A. 大于原數 B. 小于原數 C. 等于原數 D. 與原數符號相反CCFNOIP復賽全國統一評測時使用的系統軟件是〔〕。 A. NOIWindows B. NOILinux C. NOIMacOS D. NOIDOS在一個無向圖中，如果任意兩點之間都存在路徑相連，那么稱其為連通圖。以下圖是一個有4個頂點、6條邊的連通圖。假設要使它不再是連通圖，至少要刪去其中的〔〕條邊。 A. 1 B. 2 C. 3 D. 4以下圖中所使用的數據結構是〔〕。

A. 哈希表 B. 棧 C. 隊列 D. 二叉樹邏輯表達式〔〕的值與變量A的真假無關。A. (A?B)??A B. (A?B)??BC. (A?B)?(?A?B) D. (A?B)??A?BDBCBC下面的故事與〔〕算法有著異曲同工之妙。 從前有座山，山里有座廟，廟里有個老和尚在給小和尚講故事：?從前有座山，山里有座廟，廟里有個老和尚在給小和尚講故事：‘從前有座山，山里有座廟，廟里有個老和尚給小和尚講故事....’? A. 枚舉 B. 遞歸 C. 貪心 D. 分治鏈表不具有的特點是〔〕。

A.不必事先估計存儲空間 B.可隨機訪問任一元素

C.插入刪除不需要移動元素 D.所需空間與線性表長度成正比bb四、問題求解把M個同樣的球放到N個同樣的袋子里，允許有的袋子空著不放，問共有多少種不同的放置方法？〔用K表示〕。 例如：M=7，N=3時，K=8；在這里認為〔5,1,1〕和〔1,5,1〕 是同一種放置方法。 問：M=8，N=5時，K=_________。如下圖，圖中每條邊上的數字表示該邊的長度，那么從A到E的最短距離是_________。18117個同學圍坐一圈，要選2個不相鄰的作為代表，有__________種不同的選法。某系統自稱使用了一種防竊聽的方式驗證用戶密碼。密碼是n個數s1,