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

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

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

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

4、n M. Turingv答案：答案：A (塞奇塞奇布林布林 、拉里拉里佩奇佩奇 )7v微機(jī)系統(tǒng)（硬件系統(tǒng)、軟件系統(tǒng)）微機(jī)系統(tǒng)（硬件系統(tǒng)、軟件系統(tǒng)）v病毒、殺毒軟件、防火墻等病毒、殺毒軟件、防火墻等v信息的存儲(chǔ)（多媒體存儲(chǔ)容量的計(jì)算）信息的存儲(chǔ)（多媒體存儲(chǔ)容量的計(jì)算）v電子郵件相關(guān)電子郵件相關(guān)v網(wǎng)絡(luò)知識(shí)網(wǎng)絡(luò)知識(shí)vLINUX 系統(tǒng)系統(tǒng)8v2-1. 我們平時(shí)所說的內(nèi)存條是指（我們平時(shí)所說的內(nèi)存條是指（ ）。）。 vA. 寄存器寄存器 B. ROM C. RAM D. 高速緩存高速緩存v答案：答案：C9v2-2、通常所說的、通常所說的32位計(jì)算機(jī)是指（位計(jì)算機(jī)是指（ ）vA、是由、是由32個(gè)運(yùn)算器組成

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

6、B.supervisor C.administrator D.managerv答案：答案：A12v2-5、下列說法中不正確的是（、下列說法中不正確的是（ ）vA、在同一臺(tái)、在同一臺(tái)PC機(jī)上可以安裝多個(gè)操作系統(tǒng)機(jī)上可以安裝多個(gè)操作系統(tǒng)vB、在同一臺(tái)、在同一臺(tái)PC機(jī)上可以安裝多個(gè)網(wǎng)卡機(jī)上可以安裝多個(gè)網(wǎng)卡vC、在、在PC機(jī)的一個(gè)網(wǎng)卡上可以同時(shí)綁定多個(gè)機(jī)的一個(gè)網(wǎng)卡上可以同時(shí)綁定多個(gè)IP地址地址vD、一個(gè)、一個(gè)IP地址可以同時(shí)綁定到多個(gè)網(wǎng)卡上地址可以同時(shí)綁定到多個(gè)網(wǎng)卡上vE、同一個(gè)局域網(wǎng)上不同的、同一個(gè)局域網(wǎng)上不同的PC機(jī)不能使用同一個(gè)機(jī)不能使用同一個(gè)IP地址地址v答案：答案：D13v2-6在編程時(shí)（使

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

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

9、內(nèi)存單元中，則元素連續(xù)的內(nèi)存單元中，則元素A5，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個(gè)元素個(gè)元素,第第5列前面有列前面有0.4五個(gè)元素，共有五個(gè)元素，共有5*6+5=35v3、地址、地址： （5*6+5）*5+1000=117516v2-9、. 在計(jì)算機(jī)中，防火墻的作用是（在計(jì)算機(jī)中，防火墻的作用是（ ）。）。 vA、防止火災(zāi)蔓延防止火災(zāi)蔓延 B、防止網(wǎng)絡(luò)攻擊防止網(wǎng)絡(luò)攻擊 vC、 防止計(jì)算機(jī)死機(jī)防

10、止計(jì)算機(jī)死機(jī) D、防止使用者誤刪除數(shù)據(jù)防止使用者誤刪除數(shù)據(jù) v答案選答案選B17noip初賽（初賽（10月中下旬）月中下旬）noip復(fù)賽（復(fù)賽（11月中下旬）月中下旬）省隊(duì)選拔賽（由各省自行組織）省隊(duì)選拔賽（由各省自行組織）noi決賽（次年暑假）決賽（次年暑假）全國(guó)冬令營(yíng)（次年年底）全國(guó)冬令營(yíng)（次年年底）國(guó)家隊(duì)選拔賽國(guó)家隊(duì)選拔賽ctsc（次次年（次次年5月）月）國(guó)際比賽國(guó)際比賽ioi（次次年（次次年910月）月）18v3-1、 在下列各軟件中，不屬于在下列各軟件中，不屬于NOIP競(jìng)賽（復(fù)賽）推薦使用的語(yǔ)言環(huán)境有（競(jìng)賽（復(fù)賽）推薦使用的語(yǔ)言環(huán)境有（ ）。）。 vA. gcc/g+ B. Turb

11、o Pascal vC. RHIDE 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+ 194、程序語(yǔ)言及算法基礎(chǔ)、程序語(yǔ)言及算法基礎(chǔ)v了解算法的五大特征：了解算法的五大特征： 有窮性、確定性、可行性、有窮性、確定性、可行性、0或多個(gè)輸入、有一個(gè)或多個(gè)輸出或多個(gè)輸入、有一個(gè)或多個(gè)輸出v要求掌握的排序有：要求掌握的排序有： 冒泡法、插入排序、合

12、并排序、快速排序冒泡法、插入排序、合并排序、快速排序v理解每種排序的算法思想理解每種排序的算法思想v了解每種排序的時(shí)間復(fù)雜度及其穩(wěn)定性了解每種排序的時(shí)間復(fù)雜度及其穩(wěn)定性20v4-1、在下列關(guān)于計(jì)算機(jī)語(yǔ)言的說法中，不正確的是（在下列關(guān)于計(jì)算機(jī)語(yǔ)言的說法中，不正確的是（ ）。）。 vA. Pascal和和C都是編譯執(zhí)行的高級(jí)語(yǔ)言都是編譯執(zhí)行的高級(jí)語(yǔ)言 vB. 高級(jí)語(yǔ)言程序比匯編語(yǔ)言程序更容易從一種計(jì)算機(jī)移植到另一種計(jì)算機(jī)上高級(jí)語(yǔ)言程序比匯編語(yǔ)言程序更容易從一種計(jì)算機(jī)移植到另一種計(jì)算機(jī)上 vC. C+是歷史上的第一個(gè)支持面向?qū)ο蟮挠?jì)算機(jī)語(yǔ)言是歷史上的第一個(gè)支持面向?qū)ο蟮挠?jì)算機(jī)語(yǔ)言 vD. 與匯編語(yǔ)言

13、相比，高級(jí)語(yǔ)言程序更容易閱讀與匯編語(yǔ)言相比，高級(jí)語(yǔ)言程序更容易閱讀v答案選答案選C21v4-2、 在下列關(guān)于計(jì)算機(jī)算法的說法中，不正確的是（在下列關(guān)于計(jì)算機(jī)算法的說法中，不正確的是（ ）。）。 vA. 一個(gè)正確的算法至少要有一個(gè)輸入一個(gè)正確的算法至少要有一個(gè)輸入 vB. 算法的改進(jìn)，在很大程度上推動(dòng)了計(jì)算機(jī)科學(xué)與技術(shù)的進(jìn)步算法的改進(jìn)，在很大程度上推動(dòng)了計(jì)算機(jī)科學(xué)與技術(shù)的進(jìn)步 vC. 判斷一個(gè)算法的好壞的主要標(biāo)準(zhǔn)是算法的時(shí)間復(fù)雜性與空間復(fù)雜性判斷一個(gè)算法的好壞的主要標(biāo)準(zhǔn)是算法的時(shí)間復(fù)雜性與空間復(fù)雜性 vD. 目前仍然存在許多涉及到國(guó)計(jì)民生的重大課題，還沒有找到能夠在計(jì)算機(jī)上實(shí)施的有目前仍然存在許

14、多涉及到國(guó)計(jì)民生的重大課題，還沒有找到能夠在計(jì)算機(jī)上實(shí)施的有效算法效算法v答案選答案選A22v4-3、 在下列各種排序算法中，不是以在下列各種排序算法中，不是以“比較比較”作為主要操作的算法是（作為主要操作的算法是（ ）。）。 A. 選擇排序選擇排序 B. 冒泡排序冒泡排序 C. 插入排序插入排序 D. 基數(shù)排序基數(shù)排序 v1、基數(shù)排序是基于、基數(shù)排序是基于“分配分配”和和“收集收集”的排序的排序v2、技巧：用排除法做，前、技巧：用排除法做，前3者都是通過比較來排序的。者都是通過比較來排序的。23v4-4、某數(shù)列有、某數(shù)列有1000個(gè)各不相同的單元個(gè)各不相同的單元,由低到高按序排列由低到高按序

15、排列,現(xiàn)要對(duì)該數(shù)列進(jìn)行二分法檢索現(xiàn)要對(duì)該數(shù)列進(jìn)行二分法檢索,在最壞的情況下在最壞的情況下,需要檢索需要檢索( )個(gè)單元。個(gè)單元。vA.1000 B.10 C.100 D.500v分析：二分法的檢索次數(shù)為分析：二分法的檢索次數(shù)為log21000+1v答案：答案：B24v4-5、在在Pascal語(yǔ)言中，判斷語(yǔ)言中，判斷a不等于不等于0且且b不等于不等于0的正確的條件表達(dá)式是（的正確的條件表達(dá)式是（ ）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答案選答案選D25v4-6、將將5

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

17、的關(guān)鍵字類型是字符串）。符串）。vA.da,ax,eb,de,bb ff 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答案：答案：A28v4-8、遞歸算法的執(zhí)行過程，一般來說，可先后分成遞推和、遞歸算法的執(zhí)行過程，一般來說，可先后分成遞推和( )兩個(gè)階段。兩個(gè)階段。A.回溯回溯B.回歸回歸C.返回返回D.合成合成 v答案：答案：B 29v位邏輯運(yùn)算：位邏輯運(yùn)算： （與）（與） 、（或）、（或）、Xor(異或異或)、（非）（非）v位移運(yùn)算位移運(yùn)算: shl（左移位）左移位）

18、 、 shr（右移位）右移位）301、（與）、（與）、（或）、（或）、（非）（非） 運(yùn)算：對(duì)應(yīng)位都為運(yùn)算：對(duì)應(yīng)位都為1 1時(shí)為時(shí)為1 1，否則為，否則為0 0。如下：。如下： 110111 110111 001101 001101 - 000101000101運(yùn)算：對(duì)應(yīng)位只要有一個(gè)運(yùn)算：對(duì)應(yīng)位只要有一個(gè)1 1就為就為1 1。如下：。如下： 110111 110111 001101 001101 - 111111111111運(yùn)算：對(duì)每個(gè)上的值按位求反：運(yùn)算：對(duì)每個(gè)上的值按位求反：1變?yōu)樽優(yōu)?；0變?yōu)樽優(yōu)?312、Xor(異或)v1、Xor(異或異或)：對(duì)應(yīng)位相同為：對(duì)應(yīng)位相同為“0”，不同為，不

19、同為“1”v 10101v 00111v -v 10010323 3、shlshl（左移）、左移）、shrshr（右移）右移）Shl nShl n（左移位）左移位）: :所有位向左移動(dòng)所有位向左移動(dòng)n位位(00001)2 shl 1 =(00010)2(00101)2 shl 2 =(10100)2 小結(jié)：小結(jié)：二進(jìn)制每左移一位相當(dāng)于乘以一個(gè)二進(jìn)制每左移一位相當(dāng)于乘以一個(gè)2Shr nShr n（右移位）右移位）所有位向右移動(dòng)所有位向右移動(dòng)n位位(00010)2 shr 1 =(00001)2(00100)2 shr 2 =(00001)2 小結(jié)：小結(jié)：二進(jìn)制每右移一位相當(dāng)于二進(jìn)制每右移一位相當(dāng)

20、于除除以一個(gè)以一個(gè)233v5-1、已知、已知A=35H，則則A 0505H H A A 3030H H的結(jié)果是（的結(jié)果是（ ） A A、30H B30H B、05H C05H C、35H D35H D、53H E53H E、00H00H分析：分析：1 1、運(yùn)算優(yōu)于運(yùn)算優(yōu)于運(yùn)算運(yùn)算2 2、化為二進(jìn)制后再做運(yùn)算化為二進(jìn)制后再做運(yùn)算34v5-2、在在Pascal語(yǔ)言中，表達(dá)式語(yǔ)言中，表達(dá)式 (21 xor 2)的值是（的值是（ ） A. 441 B. 42 C.23 D.24 分析：分析： 10101 (21) 00010 (2) - 10111 (23)356、進(jìn)制數(shù)的運(yùn)算、進(jìn)制數(shù)的運(yùn)算v十進(jìn)制（

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

22、位二進(jìn)制數(shù)v如（215）8=（010001101）237v例例1：將：將(1011010.10)2轉(zhuǎn)換成八進(jìn)制和十六進(jìn)制數(shù)轉(zhuǎn)換成八進(jìn)制和十六進(jìn)制數(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、將十六進(jìn)制數(shù)、將十六進(jìn)制數(shù)F7.28變?yōu)槎M(jìn)制數(shù)變?yōu)槎M(jìn)制數(shù)vF 7 . 2 8 (F7.28)16=(11110111.00101)21111 0111.0010 1000 v例例3、將八進(jìn)制數(shù)、將八進(jìn)制數(shù)25.63轉(zhuǎn)換為二進(jìn)制數(shù)轉(zhuǎn)換為二進(jìn)制

23、數(shù)v2 5 6 3 (25.63)8(10101.110011)2 10 101. 110 011 38v6-1 與十進(jìn)制數(shù)與十進(jìn)制數(shù)1770 對(duì)應(yīng)的八進(jìn)制數(shù)是（對(duì)應(yīng)的八進(jìn)制數(shù)是（ ）。）。 vA. 3350 B. 3351 C. 3352 D. 3540v技巧：只需口算最低位的數(shù)字即可技巧：只需口算最低位的數(shù)字即可39v6-2、 (2010)16 + (32)8的結(jié)果是（的結(jié)果是（ ）。）。 vA. (8234)10 B. (202B)16 vC. (20056)8 D. (1)240一、線性結(jié)構(gòu)：串、棧、隊(duì)一、線性結(jié)構(gòu)：串、棧、隊(duì)二、非線性結(jié)構(gòu)：樹、圖二、非線性結(jié)構(gòu)：樹、圖41v棧特點(diǎn)：先

24、進(jìn)后出（棧特點(diǎn)：先進(jìn)后出（FILO、LIFO）v隊(duì)特點(diǎn)：先進(jìn)先出（隊(duì)特點(diǎn)：先進(jìn)先出（FIFO、LILO）v注意：有些題中還規(guī)定了?；蜿?duì)的空間注意：有些題中還規(guī)定了?；蜿?duì)的空間42v樹：普通二叉樹、滿二叉樹、完全二叉樹樹：普通二叉樹、滿二叉樹、完全二叉樹v二叉樹的特點(diǎn)：二叉樹的特點(diǎn)：v1 1、第、第i i層的結(jié)點(diǎn)最多為層的結(jié)點(diǎn)最多為2 2i-1i-1（i=1i=1）個(gè)結(jié)點(diǎn)，深度為個(gè)結(jié)點(diǎn)，深度為K K（K=1K=1）的二叉樹最多有的二叉樹最多有2 2k k-1-1個(gè)結(jié)點(diǎn)。個(gè)結(jié)點(diǎn)。v2 2、在二叉樹中，如果其葉子結(jié)點(diǎn)數(shù)為、在二叉樹中，如果其葉子結(jié)點(diǎn)數(shù)為n0n0，則其度為則其度為2 2的結(jié)點(diǎn)數(shù)為的結(jié)點(diǎn)

25、數(shù)為n2=n0-1n2=n0-1。v完全二叉樹的特點(diǎn)：完全二叉樹的特點(diǎn)：v1 1、樹葉只可能在層次最大的兩層上出現(xiàn)。、樹葉只可能在層次最大的兩層上出現(xiàn)。v2 2、對(duì)任一結(jié)點(diǎn)，左子樹的深度或者比右子樹的深度多、對(duì)任一結(jié)點(diǎn)，左子樹的深度或者比右子樹的深度多1 1，或者與右子樹深度相等。，或者與右子樹深度相等。v3 3、具有、具有n n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為個(gè)結(jié)點(diǎn)的完全二叉樹的深度為K=logK=log2 2n +1n +143v前序遍歷（前序遍歷（DLR）v根根左子樹左子樹右子樹右子樹v中序遍歷（中序遍歷（LDR）v左子樹左子樹根根右子樹右子樹v后序遍歷（后序遍歷（LRD）v左子樹左子樹右子樹

26、右子樹根根v已知前序遍歷（或后序遍歷）和中序遍歷，就能唯一確定其他一種遍歷已知前序遍歷（或后序遍歷）和中序遍歷，就能唯一確定其他一種遍歷v已知前序遍歷和后序遍歷，不能唯一確定中序遍歷已知前序遍歷和后序遍歷，不能唯一確定中序遍歷44v圖的遍歷：從圖中某一頂點(diǎn)出發(fā)訪問圖中其余的頂點(diǎn)，使每個(gè)頂點(diǎn)都被訪問且僅訪問一次。圖的遍歷：從圖中某一頂點(diǎn)出發(fā)訪問圖中其余的頂點(diǎn)，使每個(gè)頂點(diǎn)都被訪問且僅訪問一次。v深度優(yōu)先搜索（深度優(yōu)先搜索（DFS）v廣度優(yōu)先搜索（廣度優(yōu)先搜索（BFS）45v7-1、某個(gè)車站呈狹長(zhǎng)形，寬度只能容下一臺(tái)車，并且只有一個(gè)出入口。已知某時(shí)刻該車、某個(gè)車站呈狹長(zhǎng)形，寬度只能容下一臺(tái)車，并且只

27、有一個(gè)出入口。已知某時(shí)刻該車站狀態(tài)為空，從這一時(shí)刻開始的出入記錄為：站狀態(tài)為空，從這一時(shí)刻開始的出入記錄為：“進(jìn)，出，進(jìn)，進(jìn)，進(jìn)，出，出，進(jìn)，進(jìn)，進(jìn)，出，進(jìn)，進(jìn)，進(jìn)，出，出，進(jìn)，進(jìn)，進(jìn)，出進(jìn)，出,出出”。假設(shè)車輛入站的順序?yàn)?。假設(shè)車輛入站的順序?yàn)?，2，3，則車輛出站的順序?yàn)椋?，則車輛出站的順序?yàn)椋?）。）。 vA. 1, 2, 3, 4, 5 vB. 1, 2, 4, 5, 7 vC. 1, 4, 3, 7, 6 vD. 1, 4, 3, 7, 2 46v7-2、下列敘述中，正確的是（）、下列敘述中，正確的是（）A.線性表的線性存貯結(jié)構(gòu)優(yōu)于鏈表存貯結(jié)構(gòu)線性表的線性存貯結(jié)構(gòu)優(yōu)于鏈表存貯結(jié)構(gòu)B.

28、隊(duì)列的操作方式是先進(jìn)后出隊(duì)列的操作方式是先進(jìn)后出C.棧的操作方式是先進(jìn)先出棧的操作方式是先進(jìn)先出D. 二維數(shù)組是指它的每個(gè)數(shù)據(jù)元素為一個(gè)線性表的線性表二維數(shù)組是指它的每個(gè)數(shù)據(jù)元素為一個(gè)線性表的線性表 47v7-3、一棵二叉樹的中序遍歷序列為：、一棵二叉樹的中序遍歷序列為：DGBAECHF，后序遍歷序列為：，后序遍歷序列為：GDBEHFCA，則，則前序遍歷的序列是前序遍歷的序列是( )。A. ABCDFGHEB. ABDGCEFHC. ACBGDHEFD. ACEFHBGDv答案：答案：B487-4、在有、在有N個(gè)葉子節(jié)點(diǎn)的哈夫曼樹中，其節(jié)點(diǎn)總數(shù)為（）個(gè)葉子節(jié)點(diǎn)的哈夫曼樹中，其節(jié)點(diǎn)總數(shù)為（） A

29、.不確定不確定 B. 2N-1 C. 2N+1 D. 2N1、在哈夫曼樹（也叫最優(yōu)樹）中，只有兩種類型的結(jié)點(diǎn)：度為、在哈夫曼樹（也叫最優(yōu)樹）中，只有兩種類型的結(jié)點(diǎn)：度為0或或N，即最優(yōu)二叉樹中只有度為，即最優(yōu)二叉樹中只有度為0或或2的結(jié)點(diǎn)，最優(yōu)三叉樹中只有度為的結(jié)點(diǎn)，最優(yōu)三叉樹中只有度為0或或3的結(jié)點(diǎn)的結(jié)點(diǎn)2、在二叉樹中，葉子總比度為、在二叉樹中，葉子總比度為2的結(jié)點(diǎn)大的結(jié)點(diǎn)大1，即，即N=N2+1，又因?yàn)闆]有度為，又因?yàn)闆]有度為1的結(jié)點(diǎn)，所以總結(jié)的結(jié)點(diǎn)，所以總結(jié)點(diǎn)數(shù)為點(diǎn)數(shù)為N+N2=N+N-1=2N-1497-5、高度為、高度為n的均衡的二叉樹是指：如果去掉葉結(jié)點(diǎn)及相應(yīng)的樹枝，它應(yīng)該是高度為

30、的均衡的二叉樹是指：如果去掉葉結(jié)點(diǎn)及相應(yīng)的樹枝，它應(yīng)該是高度為n-1的滿的滿二叉樹。在這里，樹高等于葉結(jié)點(diǎn)的最大深度，根結(jié)點(diǎn)的深度為二叉樹。在這里，樹高等于葉結(jié)點(diǎn)的最大深度，根結(jié)點(diǎn)的深度為0，如果某個(gè)均衡的二叉樹，如果某個(gè)均衡的二叉樹共有共有2381個(gè)結(jié)點(diǎn)，則該樹的樹高為（個(gè)結(jié)點(diǎn)，則該樹的樹高為（ ）。）。 vA. 10 B. 11 C. 12 D. 13 50注：此題規(guī)定根結(jié)點(diǎn)的深度為注：此題規(guī)定根結(jié)點(diǎn)的深度為0v1、滿二叉樹指的是：對(duì)于第、滿二叉樹指的是：對(duì)于第i層，節(jié)點(diǎn)數(shù)必定是層，節(jié)點(diǎn)數(shù)必定是2i。v2、有、有i層的滿二叉樹的節(jié)點(diǎn)總數(shù)為層的滿二叉樹的節(jié)點(diǎn)總數(shù)為2(i+1)-1v3、假定均

31、衡樹的層數(shù)為、假定均衡樹的層數(shù)為x，那么該均衡樹對(duì)應(yīng)的滿二叉樹（比均衡樹小，那么該均衡樹對(duì)應(yīng)的滿二叉樹（比均衡樹小1層）節(jié)點(diǎn)數(shù)為層）節(jié)點(diǎn)數(shù)為2x-1,則必定有：則必定有：v2x-12381=3)個(gè)頂點(diǎn)的無向圖是連通的，這個(gè)圖至少要有（個(gè)頂點(diǎn)的無向圖是連通的，這個(gè)圖至少要有（ ）條邊）條邊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答案：答案：A55v7-10、下列有關(guān)樹的敘述中、下列有關(guān)樹的敘述中,敘述正確的是敘述正確的是( )vA、在含有、在含有n個(gè)結(jié)點(diǎn)的樹中，邊數(shù)只能是個(gè)結(jié)點(diǎn)的樹中，邊數(shù)只能是n-

32、1條條vB、在哈夫曼樹中，外部結(jié)點(diǎn)的個(gè)數(shù)比內(nèi)部結(jié)點(diǎn)個(gè)數(shù)多、在哈夫曼樹中，外部結(jié)點(diǎn)的個(gè)數(shù)比內(nèi)部結(jié)點(diǎn)個(gè)數(shù)多1vC、完全二叉樹一定是平衡二叉樹、完全二叉樹一定是平衡二叉樹vD、在二叉樹的前序遍序列中，若結(jié)點(diǎn)、在二叉樹的前序遍序列中，若結(jié)點(diǎn)U在結(jié)點(diǎn)在結(jié)點(diǎn)V之前，則之前，則U一定是一定是V的祖先的祖先vE、在查找樹中插入一個(gè)新結(jié)點(diǎn)，總是插入到葉結(jié)點(diǎn)下面、在查找樹中插入一個(gè)新結(jié)點(diǎn)，總是插入到葉結(jié)點(diǎn)下面v分析：分析：v1、前序遍歷是根、前序遍歷是根左左右，顯然右，顯然D是錯(cuò)誤的是錯(cuò)誤的v2、插入結(jié)點(diǎn)可以插在一個(gè)只有一個(gè)兒子的結(jié)點(diǎn)下方、插入結(jié)點(diǎn)可以插在一個(gè)只有一個(gè)兒子的結(jié)點(diǎn)下方56v7-11、以下數(shù)據(jù)結(jié)構(gòu)中哪

33、些不是線性結(jié)構(gòu)、以下數(shù)據(jù)結(jié)構(gòu)中哪些不是線性結(jié)構(gòu)?A、有向圖、有向圖 B、棧、棧 C、二叉樹、二叉樹vD、B樹樹 E、隊(duì)列、隊(duì)列57v排列排列v組合組合v數(shù)理邏輯數(shù)理邏輯58v8-1、 設(shè)設(shè)A=B=D=true，C=false，以下邏輯運(yùn)算表達(dá)式值為，以下邏輯運(yùn)算表達(dá)式值為真真(假假)的有（的有（ ）。）。 vA. (AB)(CD) B. (ABD)C) vC. A(BCD) D. (ABC)D 59總結(jié)v1、進(jìn)制轉(zhuǎn)換是必考的（二、八、十六進(jìn)制）、進(jìn)制轉(zhuǎn)換是必考的（二、八、十六進(jìn)制）v2、堆棧是必考的、堆棧是必考的,可關(guān)注隊(duì)列的操作可關(guān)注隊(duì)列的操作v3、二叉樹性質(zhì)、遍歷必考的、二叉樹性質(zhì)、遍歷必

34、考的v4、微機(jī)原理必考的（、微機(jī)原理必考的（CPU、ROM等）等）v5、排序算法的分析，概率較大、排序算法的分析，概率較大v6、新動(dòng)向：和信息學(xué)奧賽的知識(shí)、新動(dòng)向：和信息學(xué)奧賽的知識(shí)v7、信息安全，概率較大、信息安全，概率較大v8、網(wǎng)絡(luò)有關(guān)知識(shí)，今年估計(jì)會(huì)出現(xiàn)、網(wǎng)絡(luò)有關(guān)知識(shí)，今年估計(jì)會(huì)出現(xiàn)60v1、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)結(jié)構(gòu)(樹、圖樹、圖)v2、算法設(shè)計(jì)（構(gòu)造類算法）、算法設(shè)計(jì)（構(gòu)造類算法）v3、數(shù)學(xué)知識(shí)（初中不多，高中較多）、數(shù)學(xué)知識(shí)（初中不多，高中較多）61v1（尋找假幣） 現(xiàn)有80枚硬幣，其中有一枚是假幣，其重量稍輕，所有真幣的重量都相同，如果使用不帶砝碼的天平稱重，最少需要稱幾次，就可以找出假

35、幣？你還要指出第1次的稱重方法。請(qǐng)寫出你的結(jié)果：_。 62v1、該題的原型是用、該題的原型是用“二分法二分法”編程求解。二分法至少需要編程求解。二分法至少需要log(80）次，大約是）次，大約是7。v2、二分法的優(yōu)越在于每次判斷時(shí)可以排除一半。進(jìn)一步思考是否分成的部分越多，每次、二分法的優(yōu)越在于每次判斷時(shí)可以排除一半。進(jìn)一步思考是否分成的部分越多，每次判斷可以排除的數(shù)量越多？判斷可以排除的數(shù)量越多？v3、平均分成、平均分成3份來判斷，每次可以排除份來判斷，每次可以排除2/3數(shù)量。（思考分成更多份是否效果更好？）數(shù)量。（思考分成更多份是否效果更好？）63v1、平均分成、平均分成3份，如果不能被份

36、，如果不能被3整除，那么盡量讓兩份相同并且相同的兩分應(yīng)該比其他一整除，那么盡量讓兩份相同并且相同的兩分應(yīng)該比其他一份大份大1（每次判斷可以排除更多的數(shù)量）（每次判斷可以排除更多的數(shù)量）v2、每次稱相同的兩份。直到最后相同的兩分是、每次稱相同的兩份。直到最后相同的兩分是1。64實(shí)例27，27，269，9，91，1，13，3，39，9，81，1，13，3，21，165v2（取石子游戲）（取石子游戲） 現(xiàn)有現(xiàn)有5堆石子堆石子,石子數(shù)依次為石子數(shù)依次為3，5，7，19，50，甲乙兩人輪流從任一堆，甲乙兩人輪流從任一堆中任?。看沃荒苋∽砸欢眩荒懿蝗。┲腥稳。看沃荒苋∽砸欢?，不能不?。? 取最后一顆

37、石子的一方獲勝。甲先取，問甲有沒取最后一顆石子的一方獲勝。甲先取，問甲有沒有獲勝策略（即無論乙怎樣取，甲只要不失誤，都能獲勝）？如果有，甲第一步應(yīng)該在哪有獲勝策略（即無論乙怎樣取，甲只要不失誤，都能獲勝）？如果有，甲第一步應(yīng)該在哪一堆里取多少？請(qǐng)寫出你的結(jié)果：一堆里取多少？請(qǐng)寫出你的結(jié)果： v_。 66題2：xor操作v1、異或結(jié)果非、異或結(jié)果非0，必勝，否則必輸。，必勝，否則必輸。v2、根據(jù)下面列式，只要讓、根據(jù)下面列式，只要讓50對(duì)應(yīng)的最高位對(duì)應(yīng)的最高位1去掉，去掉，xor結(jié)果就是結(jié)果就是0，而這個(gè)最高位的，而這個(gè)最高位的1對(duì)應(yīng)是對(duì)應(yīng)是32。v000011（3）v000101（5）v000

38、111（7）v010011（19）v110010（50）67v3、10名劃船運(yùn)動(dòng)員中，名劃船運(yùn)動(dòng)員中，3人只會(huì)劃左舷，人只會(huì)劃左舷，2人只會(huì)劃右舷，人只會(huì)劃右舷，5人左右舷都會(huì)劃，從中選人左右舷都會(huì)劃，從中選6人，人，平均分在左、右舷，共有多少種不同的選法？平均分在左、右舷，共有多少種不同的選法？68題3：組合問題組合問題v采用窮舉劃左舷的所有情況進(jìn)行分析采用窮舉劃左舷的所有情況進(jìn)行分析v1 1、會(huì)劃左舷的全劃左舷。左舷一共只有、會(huì)劃左舷的全劃左舷。左舷一共只有1 1種，右舷為種，右舷為7 7選選3 3，方法共有：，方法共有：vC C（3 3，3 3）* *C C（7 7，3 3）=35=35

39、v2 2、派一個(gè)全能的劃左舷、派一個(gè)全能的劃左舷, ,共有方法共有方法: :vC(5C(5，1)1)* *C(3C(3，2)2)* *C(6C(6，3)=53)=5* *3 3* *20=30020=300v3 3、派二個(gè)全能的劃左舷、派二個(gè)全能的劃左舷, ,共有方法共有方法: :vC(5C(5，2)2)* *C(3C(3，1)1)* *C(5C(5，3)=103)=10* *3 3* *10=30010=300v4 4、派三個(gè)全能的劃左舷、派三個(gè)全能的劃左舷, ,共有方法共有方法: :vC(5C(5，3)3)* *C(3C(3，3)3)* *C(4C(4，3)=103)=10* *1 1*

40、*4=404=40v因此，方法數(shù)共有：因此，方法數(shù)共有：35+300+300+40=67569v4 4、設(shè)樹、設(shè)樹T T有有1717條邊，條邊，1212片樹葉，片樹葉，4 4個(gè)個(gè)4 4度內(nèi)部結(jié)點(diǎn)，度內(nèi)部結(jié)點(diǎn)，1 1個(gè)個(gè)3 3度內(nèi)部結(jié)點(diǎn)。求度內(nèi)部結(jié)點(diǎn)。求T T的樹根的度數(shù)。的樹根的度數(shù)。 注意：本題中度數(shù)定義均為圖的度數(shù)定義。注意：本題中度數(shù)定義均為圖的度數(shù)定義。70題題4：數(shù)據(jù)結(jié)構(gòu)題：數(shù)據(jù)結(jié)構(gòu)題v圖中結(jié)點(diǎn)的度指的是什么？如何計(jì)算？圖中結(jié)點(diǎn)的度指的是什么？如何計(jì)算？v是指結(jié)點(diǎn)的出度和入度。度是指結(jié)點(diǎn)的出度和入度。度=出度出度+入度入度v已知已知17條邊，可知結(jié)點(diǎn)為條邊，可知結(jié)點(diǎn)為18個(gè)。個(gè)。v設(shè)

41、根的度為設(shè)根的度為X，則所有結(jié)點(diǎn)的度之和為：則所有結(jié)點(diǎn)的度之和為：x+4*4+3*1+12v度與邊有關(guān)系嗎？度與邊有關(guān)系嗎？v顯然，總度數(shù)應(yīng)是邊的兩倍，顯然，總度數(shù)應(yīng)是邊的兩倍， 即即 x+4*4+3*1+12=17*2 =x=371v5、光明中學(xué)開設(shè)數(shù)學(xué)、英語(yǔ)和信息學(xué)三個(gè)興趣學(xué)習(xí)小組，其中數(shù)學(xué)小組、光明中學(xué)開設(shè)數(shù)學(xué)、英語(yǔ)和信息學(xué)三個(gè)興趣學(xué)習(xí)小組，其中數(shù)學(xué)小組30人，英語(yǔ)小組人，英語(yǔ)小組15人，信息學(xué)小組人，信息學(xué)小組18人，參加三個(gè)小組總?cè)藬?shù)為人，參加三個(gè)小組總?cè)藬?shù)為50人，其中有人，其中有3人同時(shí)參加人同時(shí)參加3個(gè)小組，那個(gè)小組，那么同時(shí)只參加兩個(gè)小組的同學(xué)有多少人么同時(shí)只參加兩個(gè)小組的同

42、學(xué)有多少人 ?723XYZ數(shù)學(xué)英語(yǔ)信息學(xué)301518總?cè)藬?shù)：總?cè)藬?shù)：50題題5：集合問題：集合問題分析：分析：1、將題目轉(zhuǎn)化為左圖所示、將題目轉(zhuǎn)化為左圖所示2、x+y+z即為只參加兩個(gè)小組的同學(xué)即為只參加兩個(gè)小組的同學(xué)3、30+15+18-2*3-（X+Y+Z）=50=x+y+z=773v6、十位數(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ù)，則這個(gè)十位

43、數(shù)是數(shù)，則這個(gè)十位數(shù)是_。74分析v第一步：第一步：j為為0；(十位數(shù)十位數(shù)abcdefghij是是10的倍數(shù)的倍數(shù))v第二步：第二步：e為為5；(五位數(shù)五位數(shù)abcde是是5的倍數(shù)，但的倍數(shù)，但e可能為可能為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；75v第六步：合以上第四、五步，第六步：合以上第四、五步，defgh可為可為25816、25896、45632、45672、65432、65472、85216、85296；v第七步：合四位數(shù)第七步：合四位數(shù)abcd是是