NOIP初賽復(fù)習(xí)-普及組PPT課件.pptx

NOIP初賽復(fù)習(xí) 普及組 1 全國青少年信息學(xué)奧林匹克聯(lián)賽初賽1 單項選擇2 問題求解3 閱讀程序?qū)懡Y(jié)果4 完善程序 2 計算機的產(chǎn)生是20世紀(jì)最重要的科學(xué)技術(shù)大事件之一 世界上的第一臺計算機 ENIAC 于1946年誕生在美國賓夕法尼亞大學(xué) 到目前為止 計算機的發(fā)展大致經(jīng)歷了四代 第一代電子管計算機 始于1946年 結(jié)構(gòu)上以CPU為中心 使用計算機語言 速度慢 存儲量小 主要用于數(shù)值計算 第二代晶體管計算機 始于1958年 結(jié)構(gòu)上以存儲器為中心 使用高級語言 應(yīng)用范圍擴大到數(shù)據(jù)處理和工業(yè)控制 第三代中小規(guī)模集成電路計算機 始于1964年 結(jié)構(gòu)上仍以存儲器為中心 增加了多種外部設(shè)備 軟件得到了一定的發(fā)展 文字圖象處理功能加強 第四代大規(guī)模和超大規(guī)模集成電路計算機 始于1971年 應(yīng)用更廣泛 很多核心部件可集成在一個或多個芯片上 從而出現(xiàn)了微型計算機 一 計算機的產(chǎn)生與發(fā)展 3 計算機發(fā)展歷史的劃分依據(jù) 元器件 電子管晶體管集成電路超大規(guī)模集成電路 4 JohnvonNeumann馮 諾依曼 計算機的工作原理 到目前為止 幾乎所有的計算機的結(jié)構(gòu)都按馮 諾依曼提出的方案組成 因此都可稱為馮 諾依曼機 馮 諾依曼思想 二進制數(shù) 存儲程序和程序控制 硬件由五大部件構(gòu)成 計算機的工作原理就是 存儲程序和程序控制 也稱馮 諾依曼工作原理 5 計算機硬件系統(tǒng) 計算機硬件系統(tǒng)均由運算器 控制器 存儲器 輸入設(shè)備和輸出設(shè)備五大部分構(gòu)成 他們之間的邏輯關(guān)系如下圖所示 6 設(shè)備分類 區(qū)分圖中設(shè)備 7 內(nèi)存儲器的分類 ROM 只讀存儲器 只能讀出信息 保存廠家寫入的系統(tǒng)信息RAM 隨機存儲器 可讀寫 存放運行中的程序和數(shù)據(jù) 一般機器內(nèi)存1 8G 8 常用外部設(shè)備 外存 磁帶 磁盤 軟 硬 移動閃存 光盤 輸入設(shè)備 鍵盤 鼠標(biāo) 話筒 掃描儀 數(shù)碼相機 攝像機 光筆 輸出設(shè)備 顯示器 打印機 針式 噴墨 激光 繪圖儀 音箱 輸入 輸出設(shè)備 磁盤驅(qū)動器 光刻機 觸摸屏 9 以下哪一種設(shè)備屬于輸出設(shè)備 A 掃描儀B 鍵盤C 鼠標(biāo)D 打印機CPU 存儲器 I O設(shè)備是通過 連接起來的 A 接口B 總線C 控制線D 系統(tǒng)文件斷電后會丟失數(shù)據(jù)的存儲器是 A RAMB ROMC 硬盤D 光盤下列對操作系統(tǒng)功能的描述最為完整的是 A 負(fù)責(zé)外設(shè)與主機之間的信息交換B 負(fù)責(zé)診斷機器的故障C 控制和管理計算機系統(tǒng)的各種硬件和軟件資源的使用D 將源程序編譯成目標(biāo)程序下列選項中不屬于圖像格式的是 A JPEG格式B TXT格式C GIF格式D PNG格式在Windows資源管理器中 用鼠標(biāo)右鍵單擊一個文件時 會出現(xiàn)一個名為 復(fù)制 的操作選項 它的意思是 A 用剪切板中的文件替換該文件B 在該文件所在文件夾中 將該文件克隆一份C 將該文件復(fù)制到剪切板 并保留原文件D 將該文件復(fù)制到剪切板 并刪除原文件計算機如果缺少 將無法正常啟動 A 內(nèi)存B 鼠標(biāo)C U盤D 攝像頭 不屬于操作系統(tǒng) A WindowsB DOSC PhotoshopD NOILinux d b a c b C A C 10 目前計算機芯片 集成電路 制造的主要原料是 它是一種可以在沙子中提煉出的物質(zhì) A 硅B 銅C 鍺D 鋁目前個人電腦的 市場占有率最靠前的廠商包括Intel AMD等公司 A 顯示器B CPUC 內(nèi)存D 鼠標(biāo)1946年誕生于美國賓夕法尼亞大學(xué)的ENIAC屬于 計算機 A 電子管B 晶體管C 集成電路D 超大規(guī)模集成電路矢量圖 VectorImage 圖形文件所占的貯存空間比較小 并且無論如何放大 縮小或旋轉(zhuǎn)等都不會失真 是因為它 A 記錄了大量像素塊的色彩值來表示圖像B 用點 直線或者多邊形等基于數(shù)學(xué)方程的幾何圖元來表示圖像C 每個像素點的顏色信息均用矢量表示D 把文件保存在互聯(lián)網(wǎng) 采用在線瀏覽的方式查看圖像地址總線的位數(shù)決定了CPU可直接尋址的內(nèi)存空間大小 例如地址總線為16位 其最大的可尋址空間為64KB 如果地址總線是32位 則理論上最大可尋址的內(nèi)存空間為 A 128KBB 1MBC 1GBD 4GB藍(lán)牙和Wi Fi都是 設(shè)備 A 無線廣域網(wǎng)B 無線城域網(wǎng)C 無線局域網(wǎng)D 無線路由器 A B A B D C 11 一片容量為8GB的SD卡能存儲大約 張大小為2MB的數(shù)碼照片 A 1600B 2000C 4000D 16000摩爾定律 Moore slaw 是由英特爾創(chuàng)始人之一戈登 摩爾 GordonMoore 提出來的 根據(jù)摩爾定律 在過去幾十年以及在可預(yù)測的未來幾年 單塊集成電路的集成度大約每 個月翻一番 A 1B 6C 18D 36寄存器是 的重要組成部分 A 硬盤B 高速緩存C 內(nèi)存D 中央處理器有人認(rèn)為 在個人電腦送修前 將文件放入回收站中就是已經(jīng)將其刪除了 這種想法是 A 正確的 將文件放入回收站意味著徹底刪除 無法恢復(fù)B 不正確的 只有將回收站清空后 才意味著徹底刪除 無法恢復(fù)C 不正確的 即使將回收站清空 文件只是被標(biāo)記為刪除 仍可能通過恢復(fù)軟件找回D 不正確的 只要在硬盤上出現(xiàn)過的文件 永遠(yuǎn)不可能被徹底刪除從ENIAC到當(dāng)前最先進的計算機 馮 諾依曼體系結(jié)構(gòu)始終占有重要的地位 馮 諾依曼體系結(jié)構(gòu)的核心內(nèi)容是 A 采用開關(guān)電路B 采用半導(dǎo)體器件C 采用存儲程序和程序控制原理D 采用鍵盤輸入Linux下可執(zhí)行文件的默認(rèn)擴展名為 A exeB comC dllD 以上都不是提出 存儲程序 的計算機工作原理的是 A 克勞德 香農(nóng)B 戈登 摩爾C 查爾斯 巴比奇D 馮 諾依曼 C C D C C D D 12 主存儲器的存取速度比中央處理器 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 由研究蝙蝠 發(fā)明雷達(dá)B 由研究蜘蛛網(wǎng) 發(fā)明因特網(wǎng)C 由研究海豚 發(fā)明聲納D 由研究電魚 發(fā)明伏特電池在使用高級語言編寫程序時 一般提到的 空間復(fù)雜度 中的 空間 是指 A 程序運行時理論上所占的內(nèi)存空間B 程序運行時理論上所占的數(shù)組空間C 程序運行時理論上所占的硬盤空間D 程序源文件理論上所占的硬盤空間以下哪個是面向?qū)ο蟮母呒壵Z言 A 匯編語言B C C FortranD Basic B A B A x 13 用規(guī)定的符號和規(guī)則來表示數(shù)的方法 十進制數(shù) 基數(shù)為10 有十個數(shù)碼0 9 運算規(guī)則逢十進一 二進制數(shù) 基數(shù)為2 有兩個數(shù)碼0和1 運算規(guī)則逢二進一 十六進制數(shù) 數(shù)碼0 9 A F 八進制數(shù) 數(shù)碼0 7 信息在計算機中的存儲 數(shù)制 14 位權(quán) 處在不同位上的數(shù)字所代表的值不同 一個數(shù)字在某個固定位置上所代表的值是固定的 這個固定位上的值稱為位權(quán)或權(quán)值 位權(quán)與基數(shù)的關(guān)系是 各進位制中位權(quán)的值恰巧是基數(shù)的若干次冪 因此 任何一種數(shù)制表示的數(shù)都可以寫成按位權(quán)展開的多項式之和 例如 下列數(shù)制的位權(quán)展開式 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任意進制數(shù) 用R表示 從小數(shù)點以左 每一位對應(yīng)的權(quán)值分別為R0 R1 R2 R3 R4 以小數(shù)點以右 每一位對應(yīng)的權(quán)值分別為R 1 R 2 R 3 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 二進制數(shù)1KB 千字節(jié) 1024Byte1MB 兆 1024KB1GB 1024MB1TB 1024GB 信息量的單位 18 數(shù)值 通過運算轉(zhuǎn)換 109 10 1101101 2ASCII碼 AmericanStandardCodeforInformationInterchange A 65 10B 66 10a 97 10c 99 10UNICODE編碼敏 25935 10 654F 16其它信息專用程序轉(zhuǎn)換 例 19 補碼 正數(shù)的補碼與原碼相同 負(fù)數(shù)的補碼就是它的反碼在末位加 1 64 10的補碼01000000 64 10的補碼11000000總之 正數(shù)的原碼 反碼 補碼都相同 就是它的原碼 負(fù)數(shù)的原碼符號位取1 其余不變 負(fù)數(shù)的反碼符號位取1 其余部分求反 負(fù)數(shù)的補碼就是它的反碼在末位加 1 例 二進制數(shù)原碼反碼補碼 1011010010110100101101001011010 1011010110110101010010110100110 20 二進制數(shù)00100100和00010101的和是 A 00101000B 001010100C 01000101D 00111001二進制數(shù)11 01在十進制下是 A 3 25B 4 125C 6 25D 11 125在十六進制表示法中 字母A相當(dāng)于十進制中的 A 9B 10C 15D 16在二進制下 1100100 1110001 A 1011B 1101C 1010D 1111字符 0 的ASCII碼為48 則字符 9 的ASCII碼為 A 39B 57C 120D 視具體的計算機而定一個正整數(shù)在二進制下有100位 則它在十六進制下有 位 A 7B 13C 25D 不能確定2E 03表示 A 2 03B 5C 8D 2000一個字節(jié) byte 由 個二進制位組成 A 8B 16C 32D 以上都有可能 D A B A B C D A 21 設(shè)X Y Z分別代表三進制下的一位數(shù)字 若等式XY ZX XYX在三進制下成立 那么同樣在三進制下 等式XY ZX 也成立 A YXZB ZXYC XYZD XZY一個字長為8位的整數(shù)的補碼是11111001 則它的原碼是 A 00000111B 01111001C 11111001D 100001111TB代表的字節(jié)數(shù)量是 A 2的10次方B 2的20次方C 2的30次方D 2的40次方下列各無符號十進制整數(shù)中 能用八位二進制表示的數(shù)中最大的是 A 296B 133C 256D 199一個32位整型變量占用 個字節(jié) A 4B 8C 32D 128十六進制數(shù)9A在 進制下是232 A 四B 八C 十D 十二 B D D d a B 22 二 計算機網(wǎng)絡(luò) 23 2020年3月2日 計算機網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu) 總線型拓?fù)浣Y(jié)構(gòu) 前一頁 后一頁 24 2020年3月2日 計算機網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu) 環(huán)型拓?fù)浣Y(jié)構(gòu) 前一頁 后一頁 25 2020年3月2日 計算機網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu) 星型拓?fù)浣Y(jié)構(gòu) 前一頁 后一頁 26 2020年3月2日 計算機網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu) 樹型拓?fù)浣Y(jié)構(gòu) 前一頁 后一頁 27 2020年3月2日 計算機網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu) 網(wǎng)狀型拓?fù)浣Y(jié)構(gòu) 網(wǎng)狀型拓?fù)浣Y(jié)構(gòu)主要用于互聯(lián)網(wǎng) 前一頁 后一頁 28 2020年3月2日 計算機網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu) 無線型拓?fù)浣Y(jié)構(gòu) 網(wǎng)狀型拓?fù)浣Y(jié)構(gòu)主要用于互聯(lián)網(wǎng) 前一頁 后一頁 29 IP地址的組成 IP地址的是32位二進制數(shù) 分成4組 每組8位二進制數(shù) 每組之間用圓點隔開 通常用十進制來表示 0 0 0 0 255 255 255 255 IP地址范圍是 0 0 0 0 255 255 255 255 寬帶上網(wǎng)不是固定IP 而是連網(wǎng)時由ISP Internet服務(wù)提供商 隨機給的 每個網(wǎng)絡(luò)上的計算機的IP不會相同 30 Internet的域名系統(tǒng) 域名由幾個英文單詞組成 中間用點 連接 中間不能有空格 域名地址與IP地址實際上是同一個東西 域名系統(tǒng)是為了方便解釋機器的IP地址而設(shè)立的 如校的IP是 222 178 189 48域名是 31 域名的構(gòu)成 域名系統(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)參考模型 33 常見網(wǎng)絡(luò)協(xié)議 TCP TransmissionControlProtocol傳輸控制協(xié)議 遠(yuǎn)程登錄協(xié)議Telnet 文件傳輸協(xié)議FTP 超文本傳輸協(xié)議HTTP 域名服務(wù)DNS 簡單郵件傳輸協(xié)議SMTP 郵局協(xié)議POP3等 34 以下哪一種是屬于電子郵件收發(fā)的協(xié)議 A SMTPB UDPC P2PD FTP下列幾個32位IP地址中 書寫錯誤的是 A 162 105 128 27B 192 168 0 1C 256 256 129 1D 10 0 0 1IPv4協(xié)議使用32位地址 隨著其不斷被分配 地址資源日趨枯竭 因此 它正逐漸被使用 位地址的IPv6協(xié)議所取代 A 40B 48C 64D 128通常在搜索引擎中 對某個關(guān)鍵詞加上雙引號表示 A 排除關(guān)鍵詞 不顯示任何包含該關(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 編譯器 a c D C A B 35 是目前互聯(lián)網(wǎng)上常用的E mail服務(wù)協(xié)議 A HTTPB FTPC POP3D Telnet在下列HTML語句中 可以正確產(chǎn)生一個指向NOI官方網(wǎng)站的超鏈接的是 A 歡迎訪問NOI網(wǎng)站B 歡迎訪問NOI網(wǎng)站C D 歡迎訪問NOI網(wǎng)站關(guān)于HTML下面哪種說法是正確的 A HTML實現(xiàn)了文本 圖形 聲音乃至視頻信息的統(tǒng)一編碼 B HTML全稱為超文本標(biāo)記語言 C 網(wǎng)上廣泛使用的Flash動畫都是由HTML編寫的 D HTML也是一種高級程序設(shè)計語言 C B B 36 三 算法基礎(chǔ) 37 前綴表達(dá)式 3 2 512 的值是 A 23B 25C 37D 65全國青少年信息學(xué)奧林匹克系列活動的主辦單位是 A 教育部B 科技部C 共青團中央D 中國計算機學(xué)會以下邏輯表達(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層的二叉樹最多有 個結(jié)點 A 2n 1B 2nC 2n 1D 2n 1如果根結(jié)點的深度記為1 則一棵恰有2011個葉結(jié)點的二叉樹的深度最少是 A 10B 11C 12D 13體育課的鈴聲響了 同學(xué)們都陸續(xù)地奔向操場 按老師的要求從高到矮站成一排 每個同學(xué)按順序來到操場時 都從排尾走向排頭 找到第一個比自己高的同學(xué) 并站在他的后面 這種站隊的方法類似于 算法 A 快速排序B 插入排序C 冒泡排序D 歸并排序 C D A A C B 38 無向完全圖是圖中每對頂點之間都恰有一條邊的簡單圖 已知無向完全圖G有7個頂點 則它共有 條邊 A 7B 21C 42D 49原字符串中任意一段連續(xù)的字符所組成的新字符串稱為子串 則字符 AAABBBCCC 共有 個不同的非空子串 A 3B 12C 36D 45 就是把一個復(fù)雜的問題分成兩個或更多的相同類似的子問題 再把子問題分解成更小的子問題 直到最后的子問題可以簡單地直接求解 而原問題的解就是子問題解的并 A 動態(tài)規(guī)劃B 貪心C 分治D 搜索使用冒泡排序?qū)π蛄羞M行升序排列 每執(zhí)行一次交換操作系統(tǒng)將會減少1個逆序?qū)?因此序列5 4 3 2 1需要執(zhí)行 次操作 才能完成冒泡排序 A 0B 5C 10D 15 是一種先進先出的線性表 A 棧B 隊列C 哈希表 散列表 D 二叉樹 B C C C B 39 把64位非零浮點數(shù)強制轉(zhuǎn)換成32位浮點數(shù)后 不可能 A 大于原數(shù)B 小于原數(shù)C 等于原數(shù)D 與原數(shù)符號相反CCFNOIP復(fù)賽全國統(tǒng)一評測時使用的系統(tǒng)軟件是 A NOIWindowsB NOILinuxC NOIMacOSD NOIDOS在一個無向圖中 如果任意兩點之間都存在路徑相連 則稱其為連通圖 下圖是一個有4個頂點 6條邊的連通圖 若要使它不再是連通圖 至少要刪去其中的 條邊 A 1B 2C 3D 4下圖中所使用的數(shù)據(jù)結(jié)構(gòu)是 A 哈希表B 棧C 隊列D 二叉樹邏輯表達(dá)式 的值與變量A的真假無關(guān) A A B AB A B BC A B A B D A B A B D B C B C 40 下面的故事與 算法有著異曲同工之妙 從前有座山 山里有座廟 廟里有個老和尚在給小和尚講故事 從前有座山 山里有座廟 廟里有個老和尚在給小和尚講故事 從前有座山 山里有座廟 廟里有個老和尚給小和