備戰(zhàn)選擇題問題求解

1、v初賽：初賽全部為筆試，滿分初賽：初賽全部為筆試，滿分100分。分。v試題由四部分組成：試題由四部分組成： v1、選擇題：共、選擇題：共20題，每題題，每題1.5分，共計分，共計30分。分。(普及組全為單選題普及組全為單選題;提高組提高組10個單選，個單選，10個不定個不定項選擇項選擇)v2、問題求解題：共、問題求解題：共2題，每題題，每題5分分,共計共計10分分 v3、程序閱讀理解題、程序閱讀理解題:共共4題，每題題，每題8分分,共計共計32分。分。 v4、程序完善題：共、程序完善題：共2題，每題題，每題14分，共計分，共計28分。分。v計算機基本常識：計算機基本常識： IT文化、微機原理、

2、信息安全、基本應用文化、微機原理、信息安全、基本應用v與奧賽活動有關的知識與奧賽活動有關的知識v程序語言及算法基礎程序語言及算法基礎v數(shù)據(jù)結構數(shù)據(jù)結構(串、棧、隊、樹、圖串、棧、隊、樹、圖)v離散數(shù)學：排列組合、數(shù)理邏輯離散數(shù)學：排列組合、數(shù)理邏輯v重點考查：在重點考查：在IT領域中的杰出人物及重要事項領域中的杰出人物及重要事項v范圍較廣，準備較困難范圍較廣，準備較困難v關注關注IT界發(fā)展動態(tài)界發(fā)展動態(tài)v1-1. 在下面各世界頂級的獎項中，為計算機科學與在下面各世界頂級的獎項中，為計算機科學與技術領域做出杰出貢獻的科學家設立的獎項是（技術領域做出杰出貢獻的科學家設立的獎項是（ ）。）。 v A

3、. 沃爾夫獎沃爾夫獎 B. 諾貝爾獎諾貝爾獎v C. 菲爾茲獎菲爾茲獎 D. 圖靈獎圖靈獎 v答案：答案：Dv1-2、Google 是萬維網(wǎng)上最大的搜索引擎，是萬維網(wǎng)上最大的搜索引擎，使用戶能夠訪問一個包含超過使用戶能夠訪問一個包含超過 80 億個網(wǎng)址億個網(wǎng)址的索引。的索引。Google 堅持不懈地對其搜索功能堅持不懈地對其搜索功能進行革新，始終保持著自己在搜索領域的領進行革新，始終保持著自己在搜索領域的領先地位。先地位。 Google的創(chuàng)始人是（的創(chuàng)始人是（ ）vA、Sergey Brin 、 Larry PagevB、陳天橋、陳天橋vC、Bill Gates vD、 Alan M. Tur

4、ingv答案：答案：A (塞奇塞奇布林布林 、拉里拉里佩奇佩奇 )v微機系統(tǒng)（硬件系統(tǒng)、軟件系統(tǒng)）微機系統(tǒng)（硬件系統(tǒng)、軟件系統(tǒng)）v病毒、殺毒軟件、防火墻等病毒、殺毒軟件、防火墻等v信息的存儲（多媒體存儲容量的計算）信息的存儲（多媒體存儲容量的計算）v電子郵件相關電子郵件相關v網(wǎng)絡知識網(wǎng)絡知識vLINUX 系統(tǒng)系統(tǒng)v2-1. 我們平時所說的內存條是指（我們平時所說的內存條是指（ ）。）。 vA. 寄存器寄存器 B. ROM C. RAM D. 高速緩存高速緩存v答案：答案：Cv2-2、通常所說的、通常所說的32位計算機是指（位計算機是指（ ）vA、是由、是由32個運算器組成的個運算器組成的 vB

5、、通用寄存器數(shù)目為、通用寄存器數(shù)目為32個個vC、CPU一次可處理的數(shù)據(jù)為一次可處理的數(shù)據(jù)為32位位vD、地址總線的寬度為、地址總線的寬度為32位位vE、數(shù)據(jù)總線的寬度為、數(shù)據(jù)總線的寬度為32位位v答案：答案：Cv2-3Linux是一種是一種( )。 vA.單用戶、單任務的操作系統(tǒng)單用戶、單任務的操作系統(tǒng)vB.單用戶、多任務的操作系統(tǒng)單用戶、多任務的操作系統(tǒng)vC.多用戶、單任務的操作系統(tǒng)多用戶、單任務的操作系統(tǒng)vD.多用戶、多任務的操作系統(tǒng)多用戶、多任務的操作系統(tǒng)v答案：答案：Dv2-4、Linux下的超級用戶的名字是（下的超級用戶的名字是（ ）vA. root B.supervisor C.

6、administrator D.managerv答案：答案：Av2-5、下列說法中不正確的是（、下列說法中不正確的是（ ）vA、在同一臺、在同一臺PC機上可以安裝多個操作系統(tǒng)機上可以安裝多個操作系統(tǒng)vB、在同一臺、在同一臺PC機上可以安裝多個網(wǎng)卡機上可以安裝多個網(wǎng)卡vC、在、在PC機的一個網(wǎng)卡上可以同時綁定多個機的一個網(wǎng)卡上可以同時綁定多個IP地址地址vD、一個、一個IP地址可以同時綁定到多個網(wǎng)卡上地址可以同時綁定到多個網(wǎng)卡上vE、同一個局域網(wǎng)上不同的、同一個局域網(wǎng)上不同的PC機不能使用同一個機不能使用同一個IP地址地址v答案：答案：Dv2-6在編程時（使用任一種高級語言，不一在編程時（使用任

7、一種高級語言，不一定是定是Pascal），如果需要從磁盤文件中輸入），如果需要從磁盤文件中輸入一個很大的二維數(shù)組（例如一個很大的二維數(shù)組（例如1000*1000的的double型數(shù)組），按行讀（即外層循環(huán)是關型數(shù)組），按行讀（即外層循環(huán)是關于行的）與按列讀（即外層循環(huán)是關于列的）于行的）與按列讀（即外層循環(huán)是關于列的）相比，在輸入效率上（相比，在輸入效率上（ ）。）。 vA. 沒有區(qū)別沒有區(qū)別 vB. 按行讀的方式要高一些按行讀的方式要高一些 vC. 按列讀的方式要高一些按列讀的方式要高一些 vD. 取決于數(shù)組的存儲方式。取決于數(shù)組的存儲方式。 v答案：答案：Dv2-7、如果、如果pascal

8、系統(tǒng)只允許變量使用系統(tǒng)只允許變量使用64KB的內存，現(xiàn)在讓你定義一個值為整型的一維的內存，現(xiàn)在讓你定義一個值為整型的一維數(shù)組，這個數(shù)組的下標為數(shù)組，這個數(shù)組的下標為1.max，那么，那么max最大可能的值為最大可能的值為( )vA.64 B.64000 C.32000 D.32768v64KB=64*1024Bv整型占整型占2個字節(jié)個字節(jié)v所以所以,max=64*1024/2v答案選答案選Dv2-8、數(shù)組、數(shù)組A0.5,0.6的每個元素占的每個元素占5個單元，將其個單元，將其按列優(yōu)先次序存儲在起始地址為按列優(yōu)先次序存儲在起始地址為1000的連續(xù)的內存的連續(xù)的內存單元中，則元素單元中，則元素A5

9、，5的地址為（的地址為（ ）vA.1175 B.1180 C.1205 D.1210 E.1190v分析：分析：v1、搞清楚列優(yōu)先的含義、搞清楚列優(yōu)先的含義v2、A5，5前面有前面有0,1,2,3,4共共5列，每列有列，每列有0.5共共6個元素個元素,第第5列前面有列前面有0.4五個元素，共有五個元素，共有5*6+5=35v3、地址、地址： （5*6+5）*5+1000=1175v2-9、. 在計算機中，防火墻的作用是（在計算機中，防火墻的作用是（ ）。）。 vA、防止火災蔓延防止火災蔓延 B、防止網(wǎng)絡攻擊防止網(wǎng)絡攻擊 vC、 防止計算機死機防止計算機死機 D、防止使用者誤刪除防止使用者誤刪除

10、數(shù)據(jù)數(shù)據(jù) v答案選答案選B1.noip初賽（初賽（10月中下旬）月中下旬）2.noip復賽（復賽（11月中下旬）月中下旬）3.省隊選拔賽（由各省自行組織）省隊選拔賽（由各省自行組織）4.noi決賽（次年暑假）決賽（次年暑假）5.全國冬令營（次年年底）全國冬令營（次年年底）6.國家隊選拔賽國家隊選拔賽ctsc（次次年（次次年5月）月）7.國際比賽國際比賽ioi（次次年（次次年910月）月）v3-1、 在下列各軟件中，不屬于在下列各軟件中，不屬于NOIP競賽競賽（復賽）推薦使用的語言環(huán)境有（復賽）推薦使用的語言環(huán)境有（ ）。）。 vA. gcc/g+ B. Turbo Pascal vC. RHI

11、DE D. free pascal E、Lazarusv答案選答案選B推薦的：推薦的： pascal: free pascal、 Lazarus c 及及c+、 Dev C+、 gcc/g+、 RHIDE不推薦的不推薦的: TP7(turbo pascal 7) 、TC(turbo C) 、Visual C+ 4、程序語言及算法基礎、程序語言及算法基礎v了解算法的了解算法的五大特征五大特征： 有窮性、確定性、可行性、有窮性、確定性、可行性、0或多個輸入、或多個輸入、有一個或多個輸出有一個或多個輸出v要求掌握的排序有：要求掌握的排序有： 冒泡法、插入排序、合并排序、快速排序冒泡法、插入排序、合并

12、排序、快速排序v理解每種排序的理解每種排序的算法思想算法思想v了解每種排序的了解每種排序的時間復雜度時間復雜度及其及其穩(wěn)定性穩(wěn)定性v4-1、在下列關于計算機語言的說法中，不正在下列關于計算機語言的說法中，不正確的是（確的是（ ）。）。 vA. Pascal和和C都是編譯執(zhí)行的高級語言都是編譯執(zhí)行的高級語言 vB. 高級語言程序比匯編語言程序更容易從一高級語言程序比匯編語言程序更容易從一種計算機移植到另一種計算機上種計算機移植到另一種計算機上 vC. C+是歷史上的第一個支持面向對象的計是歷史上的第一個支持面向對象的計算機語言算機語言 vD. 與匯編語言相比，高級語言程序更容易閱與匯編語言相比，

13、高級語言程序更容易閱讀讀v答案選答案選Cv4-2、 在下列關于計算機算法的說法中，不正確的在下列關于計算機算法的說法中，不正確的是（是（ ）。）。 vA. 一個正確的算法至少要有一個輸入一個正確的算法至少要有一個輸入 vB. 算法的改進，在很大程度上推動了計算機科學與算法的改進，在很大程度上推動了計算機科學與技術的進步技術的進步 vC. 判斷一個算法的好壞的主要標準是算法的時間復判斷一個算法的好壞的主要標準是算法的時間復雜性與空間復雜性雜性與空間復雜性 vD. 目前仍然存在許多涉及到國計民生的重大課題，目前仍然存在許多涉及到國計民生的重大課題，還沒有找到能夠在計算機上實施的有效算法還沒有找到能

14、夠在計算機上實施的有效算法v答案選答案選Av4-3、 在下列各種排序算法中，不是以在下列各種排序算法中，不是以“比較比較”作為主要操作的算法是（作為主要操作的算法是（ ）。）。 A. 選擇排序選擇排序 B. 冒泡排序冒泡排序 C. 插入排序插入排序 D. 基數(shù)排序基數(shù)排序 v1、基數(shù)排序是基于、基數(shù)排序是基于“分配分配”和和“收集收集”的排的排序序v2、技巧：用排除法做，前、技巧：用排除法做，前3者都是通過比較者都是通過比較來排序的。來排序的。v4-4、某數(shù)列有、某數(shù)列有1000個各不相同的單元個各不相同的單元,由低由低到高按序排列到高按序排列,現(xiàn)要對該數(shù)列進行二分法檢索現(xiàn)要對該數(shù)列進行二分法

15、檢索,在最壞的情況下在最壞的情況下,需要檢索需要檢索( )個單元。個單元。vA.1000 B.10 C.100 D.500v分析：二分法的檢索次數(shù)為分析：二分法的檢索次數(shù)為log21000+1v答案：答案：Bv4-5、在在Pascal語言中，判斷語言中，判斷a不等于不等于0且且b不等于不等于0的正確的條件表達式是（的正確的條件表達式是（ ）vA. not a=0 or not b=0 vB. not(a=0)and(b=0) vC. not(a=0 and b=0) vD. (a0)and (b0) v答案選答案選Dv4-6、將將5個數(shù)的序列排序，不論原先的順序個數(shù)的序列排序，不論原先的順序如

16、何，最少都可以通過（如何，最少都可以通過（ ）次比較，完成從）次比較，完成從小到大的排序。小到大的排序。 vA. 6 B. 7 C. 8 D. 9 分析v1、既然是追求最少比較次數(shù)，必定不會用、既然是追求最少比較次數(shù)，必定不會用n2的算法排序。的算法排序。v2、排序本質可說是循環(huán)查找各個位置上數(shù)、排序本質可說是循環(huán)查找各個位置上數(shù)v（1）用二分查找）用二分查找v（2）總次數(shù)）總次數(shù)3227v4-7、下列序列中，（、下列序列中，（ ）是執(zhí)行第一趟快速）是執(zhí)行第一趟快速排序后得到的序列（排序的關鍵字類型是字排序后得到的序列（排序的關鍵字類型是字符串）。符串）。vA.da,ax,eb,de,bb f

17、f ha,gcvB.cd,eb,ax,da ff ha,gc,bbvC.gc,ax,eb,cd,bb ff da,havD.ax,bb,cd,da ff eb,gc,hav答案：答案：Av4-8、遞歸算法的執(zhí)行過程，一般來說，可先、遞歸算法的執(zhí)行過程，一般來說，可先后分成遞推和后分成遞推和( )兩個階段。兩個階段。A.回溯回溯B.回歸回歸C.返回返回D.合成合成 v答案：答案：B v位邏輯運算：位邏輯運算： （與）（與） 、（或）、（或）、Xor(異或異或)、（非）（非）v位移運算位移運算: shl（左移位）左移位） 、 shr（右移位）右移位）1、（與）、（與）、（或）、（或）、（非）（非）

18、 運算：對應位都為運算：對應位都為1 1時為時為1 1，否則為，否則為0 0。如下：。如下： 110111 110111 001101 001101 - 000101000101運算：對應位只要有一個運算：對應位只要有一個1 1就為就為1 1。如下：。如下： 110111 110111 001101 001101 - 111111111111運算：對每個上的值按位求反：運算：對每個上的值按位求反：1變?yōu)樽優(yōu)?；0變?yōu)樽優(yōu)?2、Xor(異或)v1、Xor(異或異或)：對應位相同為：對應位相同為“0”，不同為，不同為“1”v 10101v 00111v -v 100103 3、shlshl（左移）

19、、左移）、shrshr（右移）右移）ShlShl n n（左移位）左移位）: :所有位向左移動所有位向左移動n位位(00001)2 shl 1 =(00010)2(00101)2 shl 2 =(10100)2 小結：小結：二進制每左移一位相當于乘以一個二進制每左移一位相當于乘以一個2ShrShr n n（右移位）右移位）所有位向右移動所有位向右移動n位位(00010)2 shr 1 =(00001)2(00100)2 shr 2 =(00001)2 小結：小結：二進制每右移一位相當于二進制每右移一位相當于除除以一個以一個2v5-1、已知、已知A=35H，則則A 0505H H A A 303

20、0H H的的結果是（結果是（ ） A A、30H B30H B、05H C05H C、35H D35H D、53H E53H E、00H00H分析：分析：1 1、運算優(yōu)于運算優(yōu)于運算運算2 2、化為二進制后再做運算化為二進制后再做運算v5-2、在在Pascal語言中，表達式語言中，表達式 (21 xor 2)的的值是（值是（ ） A. 441 B. 42 C.23 D.24 分析：分析： 10101 (21) 00010 (2) - 10111 (23)6、進制數(shù)的運算、進制數(shù)的運算v十進制（十進制（0-9）v二進制（二進制（0、1）、）、v八進制（八進制（0-8）v十六進制（十六進制（0-9

21、，A-F）v掌握不同進制數(shù)之間的相互轉換掌握不同進制數(shù)之間的相互轉換v注意技巧，節(jié)省時間注意技巧，節(jié)省時間v1、十進制數(shù)、十進制數(shù) N進制數(shù)進制數(shù) 方法：除N取余倒序法v2、N進制數(shù)進制數(shù) 十進制數(shù)（帶小數(shù)）十進制數(shù)（帶小數(shù)）v方法：整數(shù)部分：kNi求和法v 小數(shù)部分：小數(shù)部分*N取整v3、十六進制數(shù)與二進制數(shù)間的關系、十六進制數(shù)與二進制數(shù)間的關系v每位十六進制數(shù)相當于4位二進制數(shù)v如（215）16=（001000010101）2v4、八進制數(shù)與二進制數(shù)間的關系、八進制數(shù)與二進制數(shù)間的關系v每位八進制位相當于3位二進制數(shù)v如（215）8=（010001101）2v例例1：將：將(1011010

22、.10)2轉換成八進制和十六進轉換成八進制和十六進制數(shù)制數(shù) v001 011 010. 100 (1011010.10)2=(132.4)8v 1 3 2 . 4v0101 1010. 1000 (1011010.10)2=(5A.8)16v 5 A . 8v例例2、將十六進制數(shù)、將十六進制數(shù)F7.28變?yōu)槎M制數(shù)變?yōu)槎M制數(shù)vF 7 . 2 8 (F7.28)16=(11110111.00101)21111 0111.0010 1000 v例例3、將八進制數(shù)、將八進制數(shù)25.63轉換為二進制數(shù)轉換為二進制數(shù)v2 5 6 3 (25.63)8(10101.110011)2 10 101. 11

23、0 011 v6-1 與十進制數(shù)與十進制數(shù)1770 對應的八進制數(shù)是（對應的八進制數(shù)是（ ）。）。 vA. 3350 B. 3351 C. 3352 D. 3540v技巧：技巧：只需口算最低位的數(shù)字即可只需口算最低位的數(shù)字即可v6-2、 (2010)16 + (32)8的結果是（的結果是（ ）。）。 vA. (8234)10 B. (202B)16 vC. (20056)8 D. (100000000110)2一、線性結構：串、棧、隊一、線性結構：串、棧、隊二、非線性結構：樹、圖二、非線性結構：樹、圖v棧特點：先進后出（棧特點：先進后出（FILO、LIFO）v隊特點：先進先出（隊特點：先進先出

24、（FIFO、LILO）v注意：有些題中還規(guī)定了?；蜿牭目臻g注意：有些題中還規(guī)定了棧或隊的空間v樹：普通二叉樹、滿二叉樹、完全二叉樹樹：普通二叉樹、滿二叉樹、完全二叉樹v二叉樹的特點：二叉樹的特點：v1 1、第、第i i層的結點最多為層的結點最多為2 2i-1i-1（i=1i=1）個結點，深度為個結點，深度為K K（K=1K=1）的二叉樹最多有的二叉樹最多有2 2k k-1-1個結點。個結點。v2 2、在二叉樹中，如果其葉子結點數(shù)為、在二叉樹中，如果其葉子結點數(shù)為n0n0，則其度為則其度為2 2的結點數(shù)為的結點數(shù)為n2=n0-1n2=n0-1。v完全二叉樹的特點：完全二叉樹的特點：v1 1、樹葉

25、只可能在層次最大的兩層上出現(xiàn)。、樹葉只可能在層次最大的兩層上出現(xiàn)。v2 2、對任一結點，左子樹的深度或者比右子樹的深度、對任一結點，左子樹的深度或者比右子樹的深度多多1 1，或者與右子樹深度相等。，或者與右子樹深度相等。v3 3、具有、具有n n個結點的完全二叉樹的深度為個結點的完全二叉樹的深度為K=logK=log2 2n +1n +1v前序遍歷（前序遍歷（DLR）v根根左子樹左子樹右子樹右子樹v中序遍歷（中序遍歷（LDR）v左子樹左子樹根根右子樹右子樹v后序遍歷（后序遍歷（LRD）v左子樹左子樹右子樹右子樹根根v已知前序遍歷（或后序遍歷）和中序遍歷已知前序遍歷（或后序遍歷）和中序遍歷，就能

26、就能唯一唯一確定其他一種遍歷確定其他一種遍歷v已知前序遍歷和后序遍歷已知前序遍歷和后序遍歷，不能唯一確定中，不能唯一確定中序遍歷序遍歷v圖的遍歷：從圖中某一頂點出發(fā)訪問圖中其圖的遍歷：從圖中某一頂點出發(fā)訪問圖中其余的頂點，使每個頂點都被訪問且僅訪問一余的頂點，使每個頂點都被訪問且僅訪問一次。次。v深度優(yōu)先搜索（深度優(yōu)先搜索（DFS）v廣度優(yōu)先搜索（廣度優(yōu)先搜索（BFS）v7-1、某個車站呈狹長形，寬度只能容下一臺、某個車站呈狹長形，寬度只能容下一臺車，并且只有一個出入口。已知某時刻該車車，并且只有一個出入口。已知某時刻該車站狀態(tài)為空，從這一時刻開始的出入記錄為：站狀態(tài)為空，從這一時刻開始的出入

27、記錄為：“進，出，進，進，進，出，出，進，進，進，出，進，進，進，出，出，進，進，進，出進，出,出出”。假設車輛入站的順序為。假設車輛入站的順序為1，2，3，則車輛出站的順序為（，則車輛出站的順序為（ ）。）。 vA. 1, 2, 3, 4, 5 vB. 1, 2, 4, 5, 7 vC. 1, 4, 3, 7, 6 vD. 1, 4, 3, 7, 2 v7-2、下列敘述中，正確的是（）、下列敘述中，正確的是（）A.線性表的線性存貯結構優(yōu)于鏈表存貯結構線性表的線性存貯結構優(yōu)于鏈表存貯結構B.隊列的操作方式是先進后出隊列的操作方式是先進后出C.棧的操作方式是先進先出棧的操作方式是先進先出D. 二

28、維數(shù)組是指它的每個數(shù)據(jù)元素為一個線二維數(shù)組是指它的每個數(shù)據(jù)元素為一個線性表的線性表性表的線性表 v7-3、一棵二叉樹的中序遍歷序列為：、一棵二叉樹的中序遍歷序列為：DGBAECHF，后序遍歷序列為：，后序遍歷序列為：GDBEHFCA，則前序遍歷的序列是，則前序遍歷的序列是( )。A. ABCDFGHEB. ABDGCEFHC. ACBGDHEFD. ACEFHBGDv答案：答案：B7-4、在有、在有N個葉子節(jié)點的哈夫曼樹中，其節(jié)點個葉子節(jié)點的哈夫曼樹中，其節(jié)點總數(shù)為（）總數(shù)為（） A.不確定不確定 B. 2N-1 C. 2N+1 D. 2N1、在哈夫曼樹（也叫最優(yōu)樹）中，只有兩種類、在哈夫曼樹

29、（也叫最優(yōu)樹）中，只有兩種類型的結點：度為型的結點：度為0或或N，即最優(yōu)二叉樹中只有度，即最優(yōu)二叉樹中只有度為為0或或2的結點，最優(yōu)三叉樹中只有度為的結點，最優(yōu)三叉樹中只有度為0或或3的的結點結點2、在二叉樹中，葉子總比度為、在二叉樹中，葉子總比度為2的結點大的結點大1，即，即N=N2+1，又因為沒有度為，又因為沒有度為1的結點，所以總結的結點，所以總結點數(shù)為點數(shù)為N+N2=N+N-1=2N-17-5、高度為、高度為n的均衡的二叉樹是指：如果去掉的均衡的二叉樹是指：如果去掉葉結點及相應的樹枝，它應該是高度為葉結點及相應的樹枝，它應該是高度為n-1的的滿二叉樹。在這里，樹高等于葉結點的最大滿二叉

30、樹。在這里，樹高等于葉結點的最大深度，根結點的深度為深度，根結點的深度為0，如果某個均衡的二，如果某個均衡的二叉樹共有叉樹共有2381個結點，則該樹的樹高為（個結點，則該樹的樹高為（ ）。）。 vA. 10 B. 11 C. 12 D. 13 注：此題規(guī)定注：此題規(guī)定根結點的深度為根結點的深度為0v1、滿二叉樹指的是：對于第、滿二叉樹指的是：對于第i層，節(jié)點數(shù)必定層，節(jié)點數(shù)必定是是2i。v2、有、有i層的滿二叉樹的節(jié)點總數(shù)為層的滿二叉樹的節(jié)點總數(shù)為2(i+1)-1v3、假定均衡樹的層數(shù)為、假定均衡樹的層數(shù)為x，那么該均衡樹對，那么該均衡樹對應的滿二叉樹（比均衡樹小應的滿二叉樹（比均衡樹小1層）

31、節(jié)點數(shù)為層）節(jié)點數(shù)為2x-1,則必定有：則必定有：v2x-12381=3)個頂點的無向個頂點的無向圖是連通的，這個圖至少要有（圖是連通的，這個圖至少要有（ ）條邊）條邊vA.(n-1)*(n-2)/2+1vB.n*(n-1)/2-(n+2)vC.(n-2)*(n-1)/2vD.(n/2+1)*(n-1)v答案：答案：Av7-10、下列有關樹的敘述中、下列有關樹的敘述中,敘述正確的是敘述正確的是( )vA、在含有、在含有n個結點的樹中，邊數(shù)只能是個結點的樹中，邊數(shù)只能是n-1條條vB、在哈夫曼樹中，外部結點的個數(shù)比內部結、在哈夫曼樹中，外部結點的個數(shù)比內部結點個數(shù)多點個數(shù)多1vC、完全二叉樹一定

32、是平衡二叉樹、完全二叉樹一定是平衡二叉樹vD、在二叉樹的前序遍序列中，若結點、在二叉樹的前序遍序列中，若結點U在結點在結點V之前，則之前，則U一定是一定是V的祖先的祖先vE、在查找樹中插入一個新結點，總是插入到葉、在查找樹中插入一個新結點，總是插入到葉結點下面結點下面v分析：分析：v1、前序遍歷是根、前序遍歷是根左左右，顯然右，顯然D是錯誤的是錯誤的v2、插入結點可以插在一個只有一個兒子的結點下方、插入結點可以插在一個只有一個兒子的結點下方v7-11、以下數(shù)據(jù)結構中哪些不是線性結構、以下數(shù)據(jù)結構中哪些不是線性結構?A、有向圖、有向圖 B、棧、棧 C、二叉樹、二叉樹vD、B樹樹 E、隊列、隊列v

33、排列排列v組合組合v數(shù)理邏輯數(shù)理邏輯v8-1、 設設A=B=D=true，C=false，以下邏輯，以下邏輯運算表達式值為運算表達式值為真真(假假)的有（的有（ ）。）。 vA. (AB)(CD) B. (ABD)C) vC. A(BCD) D. (ABC)D 總結v1、進制轉換是必考的（二、八、十六進制）、進制轉換是必考的（二、八、十六進制）v2、堆棧是必考的、堆棧是必考的,可關注隊列的操作可關注隊列的操作v3、二叉樹性質、遍歷必考的、二叉樹性質、遍歷必考的v4、微機原理必考的（、微機原理必考的（CPU、ROM等）等）v5、排序算法的分析，概率較大、排序算法的分析，概率較大v6、新動向：和信

34、息學奧賽的知識、新動向：和信息學奧賽的知識v7、信息安全，概率較大、信息安全，概率較大v8、網(wǎng)絡有關知識，今年估計會出現(xiàn)、網(wǎng)絡有關知識，今年估計會出現(xiàn)v1、數(shù)據(jù)結構、數(shù)據(jù)結構(樹、圖樹、圖)v2、算法設計（構造類算法）、算法設計（構造類算法）v3、數(shù)學知識（初中不多，高中較多）、數(shù)學知識（初中不多，高中較多）v1（尋找假幣） 現(xiàn)有80枚硬幣，其中有一枚是假幣，其重量稍輕，所有真幣的重量都相同，如果使用不帶砝碼的天平稱重，最少需要稱幾次，就可以找出假幣？你還要指出第1次的稱重方法。請寫出你的結果：_。 v1、該題的原型是用、該題的原型是用“二分法二分法”編程求解。二分法編程求解。二分法至少需要至

35、少需要log(80）次，大約是）次，大約是7。v2、二分法的優(yōu)越在于每次判斷時可以排除一半。、二分法的優(yōu)越在于每次判斷時可以排除一半。進一步思考是否分成的部分越多，每次判斷可以排進一步思考是否分成的部分越多，每次判斷可以排除的數(shù)量越多？除的數(shù)量越多？v3、平均分成、平均分成3份來判斷，每次可以排除份來判斷，每次可以排除2/3數(shù)量。數(shù)量。（思考分成更多份是否效果更好？）（思考分成更多份是否效果更好？）v1、平均分成、平均分成3份，如果不能被份，如果不能被3整除，那么整除，那么盡量讓兩份相同并且相同的兩分應該比其他盡量讓兩份相同并且相同的兩分應該比其他一份大一份大1（每次判斷可以排除更多的數(shù)量）（

36、每次判斷可以排除更多的數(shù)量）v2、每次稱相同的兩份。直到最后相同的兩分、每次稱相同的兩份。直到最后相同的兩分是是1。實例27，27，269，9，91，1，13，3，39，9，81，1，13，3，21，1v2（取石子游戲）（取石子游戲） 現(xiàn)有現(xiàn)有5堆石子堆石子,石子數(shù)依次石子數(shù)依次為為3，5，7，19，50，甲乙兩人輪流從任一堆，甲乙兩人輪流從任一堆中任?。看沃荒苋∽砸欢眩荒懿蝗。┲腥稳。看沃荒苋∽砸欢?，不能不?。? 取取最后一顆石子的一方獲勝。甲先取，問甲有最后一顆石子的一方獲勝。甲先取，問甲有沒有獲勝策略（即無論乙怎樣取，甲只要不沒有獲勝策略（即無論乙怎樣取，甲只要不失誤，都能獲勝）？

37、如果有，甲第一步應該失誤，都能獲勝）？如果有，甲第一步應該在哪一堆里取多少？請寫出你的結果：在哪一堆里取多少？請寫出你的結果： v_。 題2：xor操作v1、異或結果非、異或結果非0，必勝，否則必輸。，必勝，否則必輸。v2、根據(jù)下面列式，只要讓、根據(jù)下面列式，只要讓50對應的最高位對應的最高位1去掉，去掉，xor結果就是結果就是0，而這個最高位的，而這個最高位的1對應對應是是32。v000011（3）v000101（5）v000111（7）v010011（19）v110010（50）v3、10名劃船運動員中，名劃船運動員中，3人只會劃左舷，人只會劃左舷，2人只會劃右舷，人只會劃右舷，5人左右舷

38、都會劃，從中選人左右舷都會劃，從中選6人，平均分在左、右舷，共有多少種不同的人，平均分在左、右舷，共有多少種不同的選法？選法？題3：組合問題組合問題v采用窮舉劃左舷的所有情況進行分析采用窮舉劃左舷的所有情況進行分析v1 1、會劃左舷的全劃左舷。、會劃左舷的全劃左舷。左舷一共只有左舷一共只有1 1種，種，右舷為右舷為7 7選選3 3，方法共有：，方法共有：vC C（3 3，3 3）* *C C（7 7，3 3）=35=35v2 2、派一個全能的劃左舷、派一個全能的劃左舷, ,共有方法共有方法: :vC(5C(5，1)1)* *C(3C(3，2)2)* *C(6C(6，3)=53)=5* *3 3

39、* *20=30020=300v3 3、派二個全能的劃左舷、派二個全能的劃左舷, ,共有方法共有方法: :vC(5C(5，2)2)* *C(3C(3，1)1)* *C(5C(5，3)=103)=10* *3 3* *10=30010=300v4 4、派三個全能的劃左舷、派三個全能的劃左舷, ,共有方法共有方法: :vC(5C(5，3)3)* *C(3C(3，3)3)* *C(4C(4，3)=103)=10* *1 1* *4=404=40v因此，方法數(shù)共有：因此，方法數(shù)共有：35+300+300+40=675v4 4、設樹、設樹T T有有1717條邊，條邊，1212片樹葉，片樹葉，4 4個個4

40、 4度內部度內部結點，結點，1 1個個3 3度內部結點。求度內部結點。求T T的樹根的度數(shù)。的樹根的度數(shù)。 注意：本題中度數(shù)定義均為圖的度數(shù)定義。注意：本題中度數(shù)定義均為圖的度數(shù)定義。題題4：數(shù)據(jù)結構題：數(shù)據(jù)結構題v圖中結點的度指的是什么？如何計算？圖中結點的度指的是什么？如何計算？v是指結點的出度和入度。度是指結點的出度和入度。度=出度出度+入度入度v已知已知17條邊，可知結點為條邊，可知結點為18個。個。v設根的度為設根的度為X，則所有結點的度之和為：則所有結點的度之和為：x+4*4+3*1+12v度與邊有關系嗎？度與邊有關系嗎？v顯然，總度數(shù)應是邊的兩倍，顯然，總度數(shù)應是邊的兩倍， 即即

41、 x+4*4+3*1+12=17*2 =x=3v5、光明中學開設數(shù)學、英語和信息學三個興、光明中學開設數(shù)學、英語和信息學三個興趣學習小組，其中數(shù)學小組趣學習小組，其中數(shù)學小組30人，英語小組人，英語小組15人，信息學小組人，信息學小組18人，參加三個小組總人人，參加三個小組總人數(shù)為數(shù)為50人，其中有人，其中有3人同時參加人同時參加3個小組，那個小組，那么同時只參加兩個小組的同學有多少人么同時只參加兩個小組的同學有多少人 ?3XYZ數(shù)學英語信息學301518總人數(shù)：總人數(shù)：50題題5：集合問題：集合問題分析：分析：1、將題目轉化為左、將題目轉化為左圖所示圖所示2、x+y+z即為只參即為只參加兩個

42、小組的同學加兩個小組的同學3、30+15+18-2*3-（X+Y+Z）=50=x+y+z=7v6、十位數(shù)、十位數(shù)abcdefghij，其中不同的字母表示，其中不同的字母表示不同的數(shù)字。不同的數(shù)字。a是是1的倍數(shù)，兩位數(shù)的倍數(shù)，兩位數(shù)ab是是2的的倍數(shù)，三位數(shù)倍數(shù)，三位數(shù)abc是是3的倍數(shù)，四位數(shù)的倍數(shù)，四位數(shù)abcd是是4的倍數(shù)，的倍數(shù)，,十位數(shù)十位數(shù)abcdefghij是是10的倍的倍數(shù)，則這個十位數(shù)是數(shù)，則這個十位數(shù)是_。分析v第一步第一步：j為為0；(十位數(shù)十位數(shù)abcdefghij是是10的倍數(shù)的倍數(shù))v第二步第二步：e為為5；(五位數(shù)五位數(shù)abcde是是5的倍數(shù)，但的倍數(shù)，但e可能為

43、可能為0或或5，但，但0已被已被j占用占用)v第三步第三步：a、c、g、i為奇數(shù)，為奇數(shù)，b、d、f、h為偶為偶數(shù)；數(shù)；(余下余下2、4、6、8的倍數(shù)尾數(shù)為偶數(shù)的倍數(shù)尾數(shù)為偶數(shù)) v第四步第四步：試八位數(shù)：試八位數(shù)abcdefgh是是8的倍數(shù)的倍數(shù) fgh可為可為216、296、416、432、472、496、632、672、816、832、872、896，h可為可為2或或6；v第五步第五步：試六位數(shù)：試六位數(shù)abcdef是是6的倍數(shù)的倍數(shù)def可可為為258、456、654、852；v第六步第六步：合以上第四、五步，：合以上第四、五步，defgh可為可為25816、25896、45632、45672、65432、65472、85216、85296；v第七步第七步：合四位數(shù)：合四位數(shù)abcd是是4的倍數(shù)及第三、的倍數(shù)及第三、六步結果，六步結果，defgh可為可為25816、25896、65432、65472；v第八步第八步：合兩位數(shù)：合兩位數(shù)ab是是2的倍數(shù)，三位數(shù)的