NOIP初賽選擇題

1、初賽選擇題1、進制轉(zhuǎn)換1）十進制轉(zhuǎn)換成二進制。2）十進制轉(zhuǎn)換成八進制、十六進制。（以二進制為跳板）3）二進制、八進制、十六進制轉(zhuǎn)換成十進制。（以二進制為跳板）4）不同進制比較大小。5）不同進制運算。6） B二進制 O八進制 D十進制 H十六進制二進制數(shù) 11.01 在十進制下是（ ）。A. 3.25 B. 4.125 C. 6.25 D. 11.125在十六進制表示法中，字母 A 相當(dāng)于十進制中的（ ）。A. 9 B. 10 C. 15 D. 16十六進制數(shù)9A在（ ）進制下是232. A. 四 B. 八 C. 十 D. 十二在二進制下，1101001 + （ ） = 1110110。A、10

2、11B、1101C、1010 D、1111一個正整數(shù)在二進制下有 100 位，則它在十六進制下有（ ）位。A、7 B、13C、25D、不能確定十進制小數(shù)125.125對應(yīng)的八進制數(shù)是A) 100.1B) 175.175C) 175.1 D) 100.175ABBBCC2、邏輯運算邏輯運算符：邏輯運算描述：1-true-真，0-false-假，非1-0，非0-1。解題：排除法，找反例。與與或或非非ABA與與B（AB）A或或B（AB）0000010110011111邏輯表達式（ ）的值與變量 A 的真假無關(guān)。A. (A B) A B. (A B) BC. (A B) (A B) D. (A B)

3、A BC3、棧和隊列棧：棧是一種特殊的線性表。其特殊性在于限定插入和刪除數(shù)據(jù)元素的操作只能在線性表的一端進行。有后進先出的特點。隊列(Queue)也是一種運算受限的線性表，它的運算限制與棧不同，是兩頭都有限制，插入只能在表的一端進行(只進不出)，而刪除只能在表的另一端進行(只出不進)，允許刪除的一端稱為隊尾(rear)，允許插入的一端稱為隊頭 (Front)。有先進先出的特點。（ ）是一種先進先出的線性表。 A. 棧 B. 隊列 C. 哈希表（散列表） D. 二叉樹如果一個棧初始時為空，且當(dāng)前棧中的元素從棧頂?shù)綏５滓来螢閍，b，c，另有元素d已經(jīng)出棧，則可能的入棧順序是（ ）。 A. a, d

4、, c, b B. b, a, c, d C. a, c, b, d D. d, a, b, c廣度優(yōu)先搜索時，需要用到的數(shù)據(jù)結(jié)構(gòu)是（ ）。A、鏈表B、隊列 C、棧D、散列表有六個元素FEDCBA 從左到右依次順序進棧，在進棧過程中會有元素被彈出棧。問下列哪一個不可能不可能是合法的出棧序列？A) EDCFABB) DECABFC) CDFEBAD) BCDAEF在程序運行過程中，如果遞歸調(diào)用的層數(shù)過多，會因為（ ）引發(fā)錯誤。 A. 系統(tǒng)分配的?？臻g溢出 B. 系統(tǒng)分配的堆空間溢出 C. 系統(tǒng)分配的隊列空間溢出 D. 系統(tǒng)分配的鏈表空間溢出 BD深度-棧BCA4、算法描述1）算法-故事2）算法執(zhí)

5、行過程的形式窮舉法、遞歸、遞推、分治、回溯。下面的故事與（ ）算法有著異曲同工之妙。從前有座山，山里有座廟，廟里有個老和尚在給小和尚講故事：從前有座山，山里有座廟，廟里有個老和尚在給小和尚講故事：從前有座山，山里有座廟，廟里有個老和尚給小和尚講故事.A. 枚舉 B. 遞歸 C. 貪心 D. 分治體育課的鈴聲響了，同學(xué)們都陸續(xù)地奔向操場，按老師的要求從高到矮站成一排。每個同學(xué)按順序來到操場時，都從排尾走向排頭，找到第一個比自己高的同學(xué)，并站在他的后面。這種站隊的方法類似于（ ）算法。A、快速排序B、插入排序C、冒泡排序D、歸并排序（ ）是一種選優(yōu)搜索法，按選優(yōu)條件向前搜索，以達到目標(biāo)。當(dāng)探索到某

6、一步時，發(fā)現(xiàn)原先選擇并不優(yōu)或達不到目標(biāo)，就退回一步重新選擇。A、回溯法B、枚舉法C、動態(tài)規(guī)劃D、貪心法BBA5、樹、二叉樹樹的相關(guān)概念：度：任一結(jié)點擁有子樹的數(shù)目，稱為結(jié)點的度；所有結(jié)點的度的最大值，稱為樹的度。層：根為第一層，最大層數(shù)為樹的深（高）度。根節(jié)點：葉子節(jié)點：度為0的結(jié)點。樹的遍歷：先（根左右）中（左根右）后（左右根）表達式中的前（中、后）綴表達式：已知一棵二叉樹有 10 個節(jié)點，則其中至多有（ ）個節(jié)點有 2 個子節(jié)點。A. 4 B. 5 C. 6 D. 7二叉樹的（ ）第一個訪問的節(jié)點是根節(jié)點。A. 先序遍歷 B. 中序遍歷 C. 后序遍歷 D. 以上都是如果一棵二叉樹的中序遍

7、歷是BAC，那么它的先序遍歷不可能是（ ）。 A. ABC B. CBA C. ACB D. BAC 如果根結(jié)點的深度記為 1，則一棵恰有 2011 個葉結(jié)點的二叉樹的深度最少是（ ）。A、10B、11C、12D、13表達式 a*(b+c)-d 的后綴表達式是A) abcd*+-B) abc+*d-C) abc*+d-D) -+*abcd 一個包含n個分支節(jié)點（非葉節(jié)點）的非空二叉樹，它的葉節(jié)點數(shù)目最多為：A) 2n + 1B) 2n - 1 C) n - 1D) n + 1AABDC6、圖 有向圖：若圖圖中的每條邊都是有方向的，則稱為有向圖。有向圖中的邊是由兩個頂點組成的有序?qū)?，有序?qū)νǔＳ?/p>

8、尖括號表示，如表示一條有向邊，其中vi是邊的始點，vj是邊的終點。和代表兩條不同的有向邊。有n個頂點的有向圖有n(n-1)條邊，則此圖稱為完全有向圖。在有 n個頂點的有向圖中，每個頂點的度最大可達 2(n-1)。無向圖：邊均是頂點的無序?qū)?，無序?qū)νǔＳ脠A括號表示。如：無序?qū)?vi，vj)和(vj，vi)表示同一條邊。舉例：V(G2)=v1，v2，v3，v4E(G2)=(vl，v2)，(v1，v3)，(v1，v4)，(v2，v3)，(v2，v4)，(v3，v4)V1V3V2V4圖的遍歷：深度遍歷：類似樹的先根遍歷。廣度遍歷：類似樹的層次遍歷。有向圖頂點的度：入度：指向該頂點的邊的個數(shù)。出度：從該

9、頂點出發(fā)的邊的個數(shù)。完全圖：若一個圖的每一對不同頂點恰有一條邊相連，則稱為完全圖。完全圖是每對頂點之間都恰連有一條邊的簡單圖。n個端點的完全圖有n個端點及n(n 1) / 2條邊。強連通圖：一個有向圖是強連通的，當(dāng)且僅當(dāng)G中有一個回路，它至少包含每個節(jié)點一次。在一個無向圖中，如果任意兩點之間都存在路徑相連，則稱其為連通圖。下圖是一個有4 個頂點、6 條邊的連通圖。若要使它不再是連通圖，至少要刪去其中的（ ）條邊。A. 1 B. 2 C. 3 D. 4以 A0 作為起點，對下面的無向圖進行深度優(yōu)先遍歷時，遍歷順序不可能是（ ）。A. A0, A1, A2, A3 B. A0, A1, A3, A

10、2 C. A0, A2, A1, A3 D. A0, A3, A1, A2無向完全圖是圖中每對頂點之間都恰有一條邊的簡單圖。已知無向完全圖 G 有 7 個頂點，則它共有（ ）條邊。A、7 B、21C、42D、49 已知n個頂點的有向圖，若該圖是強連通的（從所有頂點都存在路徑到達其他頂點），則該圖中最少有多少條有向邊？A) n B) n + 1 C) n - 1D) n* (n - 1) CA0A3A2A1BBA7、搜索排序與時間復(fù)雜度各種搜索排序算法算法時間復(fù)雜度排序法排序法 最差時間分最差時間分析析平均時間復(fù)平均時間復(fù)雜度雜度 穩(wěn)定度穩(wěn)定度 空間復(fù)雜度空間復(fù)雜度 冒泡排序O(n2)O(n2)

11、 穩(wěn)定 O(1) 快速排序O(n2)O(n*log2n) 不穩(wěn)定 O(log2n)O(n) 選擇排序O(n2)O(n2) 穩(wěn)定 O(1) 二叉樹排序O(n2)O(n*log2n) 不一頂 O(n) 插入排序 O(n2)O(n2) 穩(wěn)定 O(1) 堆排序O(n*log2n) O(n*log2n) 不穩(wěn)定 O(1) 希爾排序OO 不穩(wěn)定 O(1)（ ）的平均時間復(fù)雜度為 O(n log n)，其中 n 是待排序的元素個數(shù)。A. 快速排序 B. 插入排序 C. 冒泡排序 D. 基數(shù)排序在含有 n 個元素的雙向鏈表中查詢是否存在關(guān)鍵字為 k 的元素，最壞情況下運行的時間復(fù)雜度是（ ）。A、O(1)B、

12、O(log n)C、O(n) D、O(n log n)快速排序最壞情況下的算法復(fù)雜度為：A) O (log-2n)B) O (n) C) O (nlog2n)D) O (n2)使用冒泡排序?qū)π蛄羞M行升序排列，每執(zhí)行一次交換操作系統(tǒng)將會減少1個逆序?qū)?，因此序?5,4,3,2,1 需要執(zhí)行（ ）次操作，才能完成冒泡排序。 A. 0 B. 5 C. 10 D. 15 排序算法是穩(wěn)定的意思是關(guān)鍵碼相同的記錄排序前后相對位置不發(fā)生改變，下列哪種排序算法是不穩(wěn)定的：A) 冒泡排序B) 插入排序 C) 歸并排序D) 快速排序ACDCD8、網(wǎng)絡(luò)相關(guān)1）郵件相關(guān) SMTP（ Simple Mail Trans

13、fer Protocol簡單郵件傳輸協(xié)議，郵件的發(fā)） POP3 （ Post Office Protocol 3郵局協(xié)議的第3個版本，郵件的收）2）網(wǎng)絡(luò)相關(guān)概念WWW（ World Wide Web環(huán)球信息網(wǎng)）HTML（超文本標(biāo)記語言，標(biāo)準(zhǔn)通用標(biāo)記語言的一個應(yīng)用。）（.com為頂級域名，baidu為二級域名，以此類推）XXXXXXX用戶名標(biāo)識符郵箱服務(wù)器TCP/IP（Transmission Control Protocol/Internet Protocol的簡寫，傳輸控制協(xié)議/因特網(wǎng)互聯(lián)協(xié)議，又名網(wǎng)絡(luò)通訊協(xié)議，是Internet最基本的協(xié)議、Internet國際互聯(lián)網(wǎng)絡(luò)的基礎(chǔ)，由網(wǎng)絡(luò)層的I

14、P協(xié)議和傳輸層的TCP協(xié)議組成。）TCP/IP 定義了電子設(shè)備如何連入因特網(wǎng)，以及數(shù)據(jù)如何在它們之間傳輸?shù)臉?biāo)準(zhǔn)。協(xié)議采用了4層的層級結(jié)構(gòu)，每一層都呼叫它的下一層所提供的協(xié)議來完成自己的需求。TCP/IP 五層模型的協(xié)議 應(yīng)用層 、傳輸層、網(wǎng)絡(luò)層、數(shù)據(jù)鏈路層、物理層 IPv4：IPv4是Internet Protocol version 4:網(wǎng)際協(xié)議版本4，IPv4中規(guī)定IP地址長度為32。最多有232-1個地址。IPv6：IPv6是Internet Protocol Version 6，為IPv4下一版本。IPv6使用的128位地址。最多2128-1個地址。IPV6地址格式：優(yōu)先選用的形式是

15、X:X:X:X:X:X:X:X ，其中 X 是 8 個 16 位地址段的十六進制值。例如：CD79:BA98:7654:4210:FEDC:BA98:7654:3210類別類別ABCDE首段0XXXXXXX10XXXXXX110XXXXX1110XXXX1111XXXX3）網(wǎng)絡(luò)OSI模型 7層模型具體具體7層層數(shù)據(jù)格式數(shù)據(jù)格式功能與連接方式功能與連接方式典型設(shè)備典型設(shè)備應(yīng)用層 Application網(wǎng)絡(luò)服務(wù)與使用者應(yīng)用程序間的一個接口表示層 Presentation數(shù)據(jù)表示、數(shù)據(jù)安全、數(shù)據(jù)壓縮會話層 Session建立、管理和終止會話傳輸層 Transport數(shù)據(jù)組織成數(shù)據(jù)段Segment用一

16、個尋址機制來標(biāo)識一個特定的應(yīng)用程序（端口號）網(wǎng)絡(luò)層 Network分割和重新組合數(shù)據(jù)包Packet基于網(wǎng)絡(luò)層地址（IP地址）進行不同網(wǎng)絡(luò)系統(tǒng)間的路徑選擇路由器數(shù)據(jù)鏈路層 Data Link將比特信息封裝成數(shù)據(jù)幀F(xiàn)rame在物理層上建立、撤銷、標(biāo)識邏輯鏈接和鏈路復(fù)用 以及差錯校驗等功能。通過使用接收系統(tǒng)的硬件地址或物理地址來尋址網(wǎng)橋、交換機、網(wǎng)卡物理層Physical傳輸比特（bit）流建立、維護和取消物理連接光纖、同軸電纜、雙絞線、中繼器和集線器中國的國家頂級域名是（ ）。A. .cn B. .ch C. .chn D. .china（ ）是主要用于顯示網(wǎng)頁服務(wù)器或者文件系統(tǒng)的HTML文件的內(nèi)

17、容，并讓用戶與這些文件交互的一種軟件。 A. 資源管理器 B. 瀏覽器 C. 電子郵件 D. 編譯器 （ ）是目前互聯(lián)網(wǎng)上常用的E-mail服務(wù)協(xié)議。 A. HTTP B. FTP C. POP3 D. Telnet 關(guān)于HTML語言下面哪種說法是正確的：A) HTML實現(xiàn)了文本、圖形、聲音乃至視頻信息的統(tǒng)一編碼。B) HTML全稱為超文本標(biāo)記語言。C) 網(wǎng)上廣泛使用的Flash動畫都是由HTML編寫的。D) HTML也是一種高級程序設(shè)計語言。關(guān)于互聯(lián)網(wǎng)，下面的說法哪一個是正確的：A) 新一代互聯(lián)網(wǎng)使用的IPv6標(biāo)準(zhǔn)是IPv5標(biāo)準(zhǔn)的升級與補充。B) 互聯(lián)網(wǎng)的入網(wǎng)主機如果有了域名就不再需要IP地

18、址。C) 互聯(lián)網(wǎng)的基礎(chǔ)協(xié)議為TCP/IP協(xié)議。D) 互聯(lián)網(wǎng)上所有可下載的軟件及數(shù)據(jù)資源都是可以合法免費使用的。ABCBC無論是TCP/IP模型還是OSI模型，都可以視為網(wǎng)絡(luò)的分層模型，每個網(wǎng)絡(luò)協(xié)議都會被歸入某一層中。如果用現(xiàn)實生活中的例子來比喻這些“層”，以下最恰當(dāng)?shù)氖牵?）。 A. 中國公司的經(jīng)理與波蘭公司的經(jīng)理交互商業(yè)文件B. 軍隊發(fā)布命令C. 國際會議中，每個人都與他國地位對等的人直接進行會談D. 體育比賽中，每一級比賽的優(yōu)勝者晉級上一級比賽A9、操作系統(tǒng)相關(guān)在 Windows 資源管理器中，用鼠標(biāo)右鍵單擊一個文件時，會出現(xiàn)一個名為“復(fù)制”的操作選項，它的意思是（ ） 。A. 用剪切板中

19、的文件替換該文件B. 在該文件所在文件夾中，將該文件克隆一份C. 將該文件復(fù)制到剪切板，并保留原文件D. 將該文件復(fù)制到剪切板，并刪除原文件通常在搜索引擎中，對某個關(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)容CC關(guān)于計算機內(nèi)存，下列說法哪個是正確的：A) 隨機存儲器（RAM）的意思是當(dāng)程序運行時，每次具體分配給程序的內(nèi)存位置是隨機而不確定的。B) 1MB內(nèi)存通常是指1024*1024字節(jié)大小的內(nèi)存。C) 計算機內(nèi)存嚴(yán)格說來包括主

20、存（memory）、高速緩存（cache）和寄存器（register）三個部分。D) 一般內(nèi)存中的數(shù)據(jù)即使在斷電的情況下也能保留2個小時以上。下列軟件中不是計算機操作系統(tǒng)的是：A) WindowsB) Linux C) OS/2 D) WPS有人認(rèn)為，在個人電腦送修前，將文件放入回收站中就是已經(jīng)將其刪除了。這種想法是（ ）。A、正確的，將文件放入回收站意味著徹底刪除、無法恢復(fù)B、不正確的，只有將回收站清空后，才意味著徹底刪除、無法恢復(fù)C、不正確的，即使將回收站清空，文件只是被標(biāo)記為刪除，仍可能通過恢復(fù)軟件找回D、不正確的，只要在硬盤上出現(xiàn)過的文件，永遠不可能被徹底刪除BDC10、程序設(shè)計語言相關(guān)匯編語言：匯編語言(AssemblyLanguage)是面向機器的程序設(shè)計語言。依賴于硬件體系，且助記符量大難記。高級語言：這種語言下，其語法和結(jié)構(gòu)更類似漢字或者普通英文，且由遠離對硬件的直接操作。如pascal、c語言等。面向?qū)ο蟪绦蛟O(shè)計： Object Oriented Programming，OOP，