1、信息學奧賽基礎知識講義 基礎部分一、進制：2進制數(shù)與8進制、10進制、16進制數(shù)的換算 換算1：將N進制數(shù)換算成10進制數(shù)（N可以為2,8,16或其它自然數(shù)） 換算2：將10進制數(shù)換算成N進制數(shù)（N可以為2,8,16或其它自然數(shù)）1.下列無符號數(shù)中，最小的數(shù)是（） A.（11011001）2 B.（75）10 C.（37）8 D.（2A）16 7、小張用十六進制，八進制和十進制寫下了如下一個等式：52-19=33式中三個數(shù)是各不相同進位制的數(shù)，試問52,19,33，分別為_。（A）8，10， 16 （B）10, 16, 8 (c) 8, 16, 10 (D) 10, 8, 16二、數(shù)據(jù)的存儲和

2、編碼所有的數(shù)據(jù)都是以二進制存儲在計算機的存儲器中的，數(shù)據(jù)的傳送、存儲、加工、處理或指令都是以二進制形式進行的。 對于數(shù)值:弄清原碼、反碼、補碼以及定點數(shù)和浮點數(shù)。負數(shù)在計算機中以補碼形式存放，小數(shù)在計算機中是以浮點數(shù)形式存放。0的原碼表示法有兩種，+0和0 8位定點整數(shù)的補碼表示范圍為-128_+127 14、計算機中的數(shù)有浮點數(shù)與定點數(shù)兩種，其中用浮點數(shù)表示的數(shù)，通常由（ ）這兩部分組成。 A.指數(shù)與基數(shù) B. 尾數(shù)與小數(shù) C. 階碼與尾數(shù) D.整數(shù)與小數(shù)8、如果用一個字節(jié)表示一個整數(shù)，最高位用作符號位，其他位表示數(shù)值，例如00000001表示+1，10000001表示-1（1） 試問這樣表

3、示法的整數(shù)a的范圍應是A、-127=a=127 B、-128=a=128C、-128=a127 D、-128a=0）個數(shù)據(jù)元素的有限序列3、特征：（1）數(shù)據(jù)表中的元素具有相同的特性（相同的數(shù)據(jù)類型）3、 （2）元素之間具備線性關系（有順序，并且是一對一的關系）相關名詞：表頭、表尾eg:線性表是： A、有限序列，可以為空；B、有限序列，不能為空 C、無限序列，可以為空 D、無限序列，不能為空三、常用的兩種線性表模型隊列：特點：只能在表的一端進行插入，在表的另一端進行刪除的線性表相關名詞：隊首、隊尾堆棧：特點：只能在表的一端進行插入和刪除操作應用：求解數(shù)學表達式、實現(xiàn)遞歸算法相關名詞：棧頂、棧底e

4、g:設棧S的初始狀態(tài)為空，現(xiàn)有個元素組成的序列（1，2，3，4，5），對該序列在S棧上依次進行如下操作（從序列中的1開始，出棧后不再進棧）：進棧，進棧，進棧，出棧，進棧，出棧，進棧，請問出棧的元素序列是:四、線性表的存儲：（順序存儲和鏈表存儲） 順序存儲：是按數(shù)據(jù)元素在存儲器中的相對位置來表示數(shù)據(jù)元素間的邏輯關系 程序描述：用一維數(shù)組來描述順序存儲結(jié)構(gòu),二維數(shù)組的每一個元素為一個線性表 鏈表存儲：用一組任意的存儲單元來存儲數(shù)據(jù)元素，元素之間的關系通過指針來 表現(xiàn)。 程序描述：用指針eg：找同學 兩種存儲結(jié)構(gòu)的特點對比順序表鏈表一個表必須用一組連續(xù)的內(nèi)存地址存儲內(nèi)存地址可以是連續(xù)的也可以是不連續(xù)

5、的插入和刪除元素難度大插入和刪除元素簡單（不需移動元素，只需修改頭尾指針即可）存取數(shù)據(jù)快（只要確定了起始位置，線性表中任一數(shù)據(jù)元素可隨機存取）存取數(shù)據(jù)慢17.線性表若采用鏈表存貯結(jié)構(gòu),要求內(nèi)存中可用存貯單元地址（） A.必須連續(xù) B.部分地址必須連續(xù) C.一定不連續(xù) D.連續(xù)不連續(xù)均可 18.下列敘述中,正確的是（） A.線性表的線性存貯結(jié)構(gòu)優(yōu)于鏈表存貯結(jié)構(gòu) B.隊列的操作方式是先進后出 C.棧的操作方式是先進先出 D.二維數(shù)組是指它的每個數(shù)據(jù)元素為一個線性表的線性表 14、線性表有兩種存儲結(jié)構(gòu)：一是順序表，二是鏈表。試問：（1）有一個線性表，在處理過過程中表的長度會根據(jù)需要動態(tài)發(fā)生變化，在這

6、種情況下應選用哪種存儲結(jié)構(gòu)（2）有一個線性表，很少進行插入和刪除操作，但要求以最快的速度存取線性表中的元素，應采用哪種存儲結(jié)構(gòu)15.已知數(shù)組A中，每個元素AI,J在存貯時要占3個字節(jié)，設I從1變化到8，J從1變化到10，分配內(nèi)存時是從地址SA開始連續(xù)按行存貯分配的。試問：A5,8的起始地址為（） A.SA+144 B.SA+180 C.SA+222 D.SA+225(4*10+8)*31.在下面各世界頂級的獎項中，為計算機科學與技術(shù)領域做出杰出貢獻的科學家設立的獎項是（ ）。A. 沃爾夫獎 B. 諾貝爾獎 C. 菲爾茲獎 D. 圖靈獎2. 在下列各軟件中，不屬于 NOIP 競賽（復賽）推薦使用

7、的語言環(huán)境有（ ）。A. gcc/g+ B. Turbo PascalC. RHIDE D. free pascal3. 以下斷電之后仍能保存數(shù)據(jù)的有（ ）。A. 寄存器 B. ROM C. RAM D. 高速緩存4Linux 是一種( )。A. 繪圖軟件 B. 程序設計語言 C. 操作系統(tǒng) D. 網(wǎng)絡瀏覽器5. CPU 是( )的簡稱。A. 硬盤 B. 中央處理器 C. 高級程序語言 D. 核心寄存器6. 在計算機中，防火墻的作用是（ ）。A. 防止火災蔓延 B.防止網(wǎng)絡攻擊C. 防止計算機死機 D. 防止使用者誤刪除數(shù)據(jù)7. 在下列關于計算機語言的說法中，不正確的是（ ）。A. Pasca

8、l和C都是編譯執(zhí)行的高級語言B. 高級語言程序比匯編語言程序更容易從一種計算機移植到另一種計算機上C. C+是歷史上的第一個支持面向?qū)ο蟮挠嬎銠C語言D. 與匯編語言相比，高級語言程序更容易閱讀8. 在下列關于計算機算法的說法中，不正確的是（ ）。A. 一個正確的算法至少要有一個輸入B. 算法的改進，在很大程度上推動了計算機科學與技術(shù)的進步C. 判斷一個算法的好壞的主要標準是算法的時間復雜性與空間復雜性D. 目前仍然存在許多涉及到國計民生的重大課題，還沒有找到能夠在計算機上實施的有效算法9. 在下列各種排序算法中，不是以“比較”作為主要操作的算法是（ ）。A. 選擇排序 B. 冒泡排序 C. 插

9、入排序 D. 基數(shù)排序10在編程時（使用任一種高級語言，不一定是 Pascal），如果需要從磁盤文件中輸入一個很大的二 維數(shù)組（例如 1000*1000 的 double 型數(shù)組），按行讀（即外層循環(huán)是關于行的）與按列讀（即外層 循環(huán)是關于列的）相比，在輸入效率上（ ）。A. 沒有區(qū)別 B. 按行讀的方式要高一些C. 按列讀的方式要高一些 D. 取決于數(shù)組的存儲方式。11在 Pascal 語言中，表達式 (21 xor 2)的值是（ ）A. 441 B. 42 C.23 D.2412在 Pascal 語言中，判斷 a 不等于 0 且 b 不等于 0 的正確的條件表達式是（ ）A. not a=

10、0 or not b=0 B. not(a=0)and(b=0) C. not(a=0 and b=0) D. (a0)and (b0)13某個車站呈狹長形，寬度只能容下一臺車，并且只有一個出入口。已知某時刻該車站狀態(tài)為空，從 這一時刻開始的出入記錄為：“進，出，進，進，進，出，出，進，進，進，出,出”。假設車輛入站的 順序為 1，2，3，則車輛出站的順序為（ ）。A. 1, 2, 3, 4, 5 B. 1, 2, 4, 5, 7C. 1, 4, 3, 7, 6 D. 1, 4, 3, 7, 214高度為 n 的均衡的二叉樹是指：如果去掉葉結(jié)點及相應的樹枝，它應該是高度為 n-1 的滿二叉樹。

11、 在這里，樹高等于葉結(jié)點的最大深度，根結(jié)點的深度為 0，如果某個均衡的二叉樹共有 2381 個結(jié)點， 則該樹的樹高為（ ）。A. 10 B. 11 C. 12 D. 1315. 與十進制數(shù) 1770 對應的八進制數(shù)是（ ）。A. 3350 B. 3351 C. 3352 D. 354016將 5 個數(shù)的序列排序，不論原先的順序如何，最少都可以通過（ ）次比較，完成從小到大的排序。A. 6 B. 7 C. 8 D. 917. 設A=B=D=true，C=false，以下邏輯運算表達式值為真的有（ ）。A. ( AB)(CD) B. (ABD)C)C. A(BCD) D. (ABC) D18. (

12、2010)16 + (32)8的結(jié)果是（ ）。A. (8234)10 B. (202B)16C. (20056)8 D. (100000000110)219. 設棧S的初始狀態(tài)為空，元素a, b, c, d, e 依次入棧，以下出棧序列不可能出現(xiàn)的有（ ）。A. a, b, c, e, d B. b, c, a, e, dC. a, e, c, b, d D. d, c, e, b, a20. 已知 6 個結(jié)點的二叉樹的先根遍歷是 1 2 3 4 5 6（數(shù)字為結(jié)點的編號，以下同），后根遍歷是3 2 5 6 4 1，則該二叉樹的可能的中根遍歷是（ ）A. 3 2 1 4 6 5 B. 3 2

13、1 5 4 6C. 2 1 3 5 4 6 D. 2 3 1 4 6 5練習二1. 在字符串“ababacbabcbdecced”中出現(xiàn)次數(shù)最多的字母出現(xiàn)了（ ）次。A. 6 B. 5 C. 4 D. 3 E. 22. 設全集 I = a, b, c, d, e, f, g, h，集合 A = a, b, c, d, e, f，B = c, d, e，C = a, d，那 么集合 A B C 為（ ）。A. c, e B. d, e C. e D. c, d, e E. d, f3. 和十進制數(shù) 23 的值相等的二進制數(shù)是（ ）。A. 10110 B. 11011 C. 11011 D. 10

14、111 E. 100114. 完全二叉樹的結(jié)點個數(shù)為 11，則它的葉結(jié)點個數(shù)為（ ）。A. 4 B.3 C.5 D. 2 E. 65. 平面上有五個點 A(5, 3), B(3, 5), C(2, 1), D(3, 3), E(5, 1)。以這五點作為完全圖 G 的頂點， 每兩點之間的直線距離是圖 G 中對應邊的權(quán)值。以下哪條邊不是圖 G 的最小生成樹中 的邊（ ）。A. AD B. BD C. CD D. DE E. EA6. Intel 的首顆 16 位處理器是（ ）。A. 8088 B. 80386 C. 80486 D. 8086 E. Pentium7. 處理器 A 每秒處理的指令數(shù)

15、是處理器 B 的 2 倍。某一特定程序 P 分別編譯為處理器 A 和處理器 B 的指令，編譯結(jié)果處理器 A 的指令數(shù)是處理器 B 的 4 倍。已知程序 P 在處 理器 A 上執(zhí)行需要 1 個小時，那么在輸入相同的情況下，程序 P 在處理器 B 上執(zhí)行需 要（ ）小時。A. 4 B. 2 C. 1 D. 1 / 2 E. 1 / 48. 以下哪個不是計算機的輸出設備（ ）。A. 音箱 B. 顯示器 C. 打印機 D. 掃描儀 E. 繪圖儀9. 下列活動中不屬于信息學奧賽的系列活動的是（ ）。A. NOIP B. NOI C. IOI D. 冬令營 E. 程序員等級考試10. 以下斷電之后仍能保存

16、數(shù)據(jù)的是（ ）。A. 硬盤 B. 寄存器 C. 顯存 D. 內(nèi)存 E. 高速緩存11. 以下哪個軟件不是即時通信軟件（ ）。A. 網(wǎng)易泡泡 B. MSN Messenger C. Google Talk D. 3DS Max E. QQ12. 下列關于高級語言的說法錯誤的是（ ）。A. Fortran 是歷史上的第一個面向科學計算的高級語言B. Pascal 和 C 都是編譯執(zhí)行的高級語言C. C+是歷史上的第一個支持面向?qū)ο蟮恼Z言D. 編譯器將高級語言程序轉(zhuǎn)變?yōu)槟繕舜aE. 高級語言程序比匯編語言程序更容易從一種計算機移植到另一種計算機上13. 下列設備不具有計算功能的是（ ）。A. 筆記本

17、電腦 B. 掌上電腦 C. 智能手機D. 電子計算器 E. 液晶顯示器14. 常見的郵件傳輸服務器使用（ ）協(xié)議接收郵件。A. HTTP B. SMTP C. TCP D. FTP E. POP315. 下列瀏覽器中，由微軟公司開發(fā)的瀏覽器是（ ）。A. Internet Explore B. Netscape C. Opera D. Firefox E. Mozilla16. 一位藝術(shù)史學家有 20000 幅真彩色圖像，每幅圖像約占 3M 空間。如果將這些圖像以位 圖形式保存在 CD 光盤上（一張 CD 光盤的容量按 600M 計算），大約需要（ ）張 CD 光盤。A. 1 B. 10 C.

18、 100 D. 1000 E. 1000017. 設 A = true，B = false，C = false，D = true，以下邏輯運算表達式值為真的是（ ）。A. (AB)(CD) B. (AB)C)D C. A(BC) D)D. (A(BC)D E. (AB)(CD)18. (3725)8 + (B)16 的運算結(jié)果是（ ）。A. (3736)8 B. (2016)10 C. (1111110000)2 D. (3006)10 E. (7B0)1619. 二叉樹 T 的寬度優(yōu)先遍歷序列為 A B C D E F G H I，已知 A 是 C 的父結(jié)點，D 是 G 的父結(jié)點，F(xiàn) 是 I

19、 的父結(jié)點，樹中所有結(jié)點的最大深度為 3（根結(jié)點深度設為 0），可知 F的父結(jié)點是（ ）。A. 無法確定 B. B C. C D. D E. E20. 設棧 S 的初始狀態(tài)為空，元素 a, b, c, d, e, f, g 依次入棧，以下出棧序列不可能出現(xiàn)的是（ ）。A. a, b, c, e, d, f, g B. b, c, a, f, e, g, d C. a, e, d, c, b, f, gD. d, c, f, e, b, a, g E. g, e, f, d, c, b, a練習三1. 美籍匈牙利數(shù)學家馮諾依曼對計算機科學發(fā)展所做出的貢獻是（ ）。A. 提出理想計算機的數(shù)學模型，

20、B. 成為計算機科學的理論基礎。C. 是世界上第一個編寫計算機程序的人。D. 提出存儲程序工作原理，E. 并設計出第一臺具有存儲程序功能的計算機EDVAC。F. 采用集成電路作為計算機的主要功能部件。G. 指H. 出計算機性能將以每兩年翻一番的速度向前發(fā)展。2. 下列哪個不3. 是CPU（中央處理單元）（ ）。A. Intel Itanium B. DDR SDRAM C. AMD Athlon64D. AMD Opteron E. IBM Power 54. 下列網(wǎng)絡上常用的名5. 字縮寫對應的中文解釋錯誤的是（ ）。A. WWW（World Wide Web）：萬B. 維網(wǎng)。C. URL（

21、Uniform Resource Locator）：統(tǒng)一資源定位器。D. HTTP（Hypertext Transfer Protocol）：超文本傳輸協(xié)議。E. FTP（File Transfer Protocol）：快速傳輸協(xié)議。F. TCP（Transfer Control Protocol）：傳輸控制協(xié)議。6. 下面哪個部件對于個人桌面電腦的正常運行不7. 是必需的（ ）。A. CPU B. 圖形卡（顯卡） C. 光驅(qū) D. 主板 E. 內(nèi)存8. 下列哪個軟件屬于操作系統(tǒng)軟件（ ）。A. Microsoft Word B. 金山詞霸 C. Foxmail D. WinRAR E. Re

22、d Hat Linux9. 下列哪個不10. 是計算機的存儲設備11. （ ）。A. 文件管理器 B. 內(nèi)存 C. 高速緩存 D. 硬盤 E. U盤12. 下列說法中錯誤的是（ ）。A. CPU的基本功能就是執(zhí)行指B. 令。C. CPU訪問內(nèi)存的速度快于訪問高速緩存的速度。D. CPU的主頻是指E. CPU在1秒內(nèi)完成的指F. 令周期數(shù)。G. 在一臺計算機內(nèi)部，H. 一個內(nèi)存地址編碼對應唯一的一個內(nèi)存單元。I. 數(shù)據(jù)總線的寬度決定了一次傳遞數(shù)據(jù)量的大小，J. 是影響計算機性能的因素之一。13. 彩色顯示器所顯示的五彩斑斕的色彩，14. 是由紅色、藍色和（ ）色混合而15. 成的。A. 紫 B.

23、 白 C. 黑 D. 綠 E. 橙16. 用靜電吸附墨粉后轉(zhuǎn)移到紙張上，17. 是哪種輸出設備18. 的工作方式（ ）。A. 針式打印機 B. 噴墨打印機 C. 激光打印機 D. 筆式繪圖儀 E. 噴墨繪圖儀19. 一臺計算機如果要利用電話線上網(wǎng)，20. 就必須配置能夠?qū)?shù)字信號和模擬信號進行相互轉(zhuǎn)換的設備，21. 這種設備22. 是（ ）。A. 調(diào)制解調(diào)器 B. 路由器 C. 網(wǎng)卡 D. 網(wǎng)關 E. 網(wǎng)橋23. 下列哪個不24. 是數(shù)據(jù)庫軟件的名25. 稱（ ）。A. MySQL B. SQL Server C. Oracle D. 金山影霸 E. Foxpro26. 下列哪個程序設計語言不

24、27. 支持面向?qū)ο蟪绦蛟O計方法（ ）。A. C+ B. Object Pascal C. C D. Smalltalk E. Java28. 由3個a，29. 1個b和2個c構(gòu)成的所有字符串中，30. 包含子串“abc”的共有（ ）個。A. 20 B. 8 C. 16 D. 12 E. 2431. 某個車站呈狹長形，32. 寬度只能容下一臺車，33. 并且只有一個出入口。已知某時刻該車站狀態(tài)為空，34. 從這一時刻開始的出入記錄為：“進，35. 出，36. 進，37. 進，38. 出，39. 進，40. 進，41. 進，42. 出，43. 出，44. 進，45. 出”。假設車輛入站的順序為1，46. 2，47. 3，48. ，49. 則車輛出站的順序為（ ）。A. 1, 2, 3, 4, 5 B. 1, 2, 4, 5, 7 C. 1, 3, 5, 4, 6 D. 1, 3, 5, 6, 7 E. 1, 3, 6,