NOIP初賽試題分析及知識點

NOIP 初賽談學(xué)問是根底，力氣最重要NOIP3根本學(xué)問。具體來說：選擇題考察的是計算機(jī)根本常識、根本操作和程序設(shè)計中的一些基本數(shù)據(jù)構(gòu)造與根本算法；而填空題更加重視力氣〔尤其是隊列、棧、二叉樹等數(shù)據(jù)構(gòu)造、數(shù)學(xué)問題、歸納法、數(shù)列和規(guī)律推理等〕的考察；讀程序?qū)戇\行結(jié)果考察的是對程序的理解和跟蹤，重在分析推理力氣。讀程序的4條題目往往有確定的層次，試卷中給出程序的并不簡潔，語句的含義簡潔明白，但是悟性好的選手總是很快就能體會到程序的設(shè)計思路并得出正確的答案，機(jī)械仿照計算機(jī)手工逐步算出結(jié)果的同學(xué)往往做的很慢，造成時間不夠，而且簡潔失誤；完善程序更是考察程序設(shè)計力氣，尤其是在明確算法和數(shù)據(jù)構(gòu)造的條件下，如何編程。讀程序和完善程序，需要在尋常的學(xué)習(xí)中提高，常常閱讀、爭論和爭論別人的優(yōu)秀程序，提高自己的理解力和速度。各種題型的解題閱歷〔以2023、2023年試題為例〕選擇題〔30分=20*1.5〕一般是比較簡潔得分的，不行錯過！程序設(shè)計方面的學(xué)問多是尋常計算機(jī)課堂教學(xué)或課外活動中學(xué)到的，建議大家找全國計算機(jī)等級考試〔一、二級〕的題目做做，一般不超過二級的學(xué)問點，學(xué)問要復(fù)習(xí)的系統(tǒng)DOSDOS有些題目可以依據(jù)閱歷推斷。另外，往更高層次進(jìn)展的過程中，必要的DOS學(xué)問和命令還是必需的。分布：5-6個數(shù)據(jù)構(gòu)造或算法方面的根本學(xué)問〔；2023年初中組〔16：一個向量第一個元素的存儲地址是100,每個元素的長度是2,則第個元素的地址是(B)A)110B)108C)100D)1092023年初中組〔17是(D)A)希爾排序 B)起泡排序 C)插入排序 D)選擇排序2023〔1913個元素的Hash表(O~12),Hash函數(shù)是:H(key)=key%13,其中%是求余數(shù)運算。用線性探查法解決沖突,則對于序列(2、8、31、20、19、18、53、,18B)。A)5 B)9 C)4 D)02023年高中組〔17：依據(jù)二叉數(shù)的定義，具有3個結(jié)點的二叉樹有〔C〕種。A〕3 B〕4 C〕5 D〕62023年高中組〔18：在一個有向圖中，全部頂點的入度之和等于全部頂點的出度之和的〔B〕倍。A〕1/2 B〕1 C〕2 D〕42023年高中組〔19：要使1．8號格字的訪問挨次為：8、、6、5、、3、、，則以以下圖中的空格中應(yīng)填入〔C。12345678461-1732A〕6B〕0C〕5D〕32023年高中組〔20：設(shè)棧S和隊列Q初始狀態(tài)為空，元素

，e，e，e1 2 3

，e，e4 5 6SQ，e，e，e2 4

，e，3 6e，e5

，則棧S的容量至少應(yīng)當(dāng)為〔 B 。1A〕2 B〕3 C〕4 D〕52023年初中組〔19：在挨次表(2，5，7，10，14，15，18，23，35，41，52)中，用二分法查找12，所需的關(guān)鍵碼比較的次數(shù)為( C)。A)2 B)3 C)4 D)52023年初中組20：假設(shè)一個棧的入棧挨次是12，?n，其輸出序列為P3，?，Pn，P1n，則PiC)。A)i B)n-1 C)n-i+1 D)不確定2023年高中組〔17：以下哪一個不是棧的根本運算(B)。A)刪除棧頂元素 B)刪除棧底的元素 C)推斷棧是否為空 D)將棧置為空棧2023〔19h0或B)個結(jié)點。A)2h-1 B)2h-1 C)2h+1 D)h+12023年高中組〔20：無向圖G=(V，E)，其中V={a,b,c,d,e,f}E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，對該圖進(jìn)展深度優(yōu)先遍歷,得到的頂點序列正確的選項是(D)。A)a,b,e,c,d,f B)a,c,f,e,b,d C)a,e,b,c,f,d D)a,b,e,d,f,c2-3〔補(bǔ)碼、反碼等〕和進(jìn)制問題；2023年初中組〔12：(0.5)10

=( C )。16A)0.1 B)0.75 C)0.8 D)0.252023年初中組〔14：算式(2047)10

一(3FF)16

+(2023)8

的結(jié)果是( A )。A)(2048)10

B)(2049)10

C)(3746)8

D)(1AF7)162023年高中組〔：十進(jìn)制書11/128可用二進(jìn)制數(shù)碼序列表示為〔 D 。A〕1011/1000000B〕1011/100000000C〕0.001011D〕0.00010112023年高中組〔：x=〔0.1011010〕2

，則[x/2]補(bǔ)=〔 C 〕。2A〕0.1011101B〕11110110C〕0.0101101D〕0.1001102023年高中組〔15：A=35H，A/\05H\/A/\30H的結(jié)果是〔 C 。A〕30H B〕05H C〕35H D〕53H2023年初中組〔：與二進(jìn)制數(shù)101.01011等值的十六進(jìn)制數(shù)為( D )。A)A.B B)5.51 C)A.51 D)5.582023年初中組〔：2KB的內(nèi)存能存儲( A )個漢字的機(jī)內(nèi)碼A)1024 B)516 C)2048 D)2182023年高中組〔：64KB的存儲器用十六進(jìn)制表示，它的最大的地址碼是( B )A)10000 B)FFFF C)1FFFF D)EFFFFCPU、內(nèi)存、總線、字長、體系構(gòu)造、外設(shè)等；2023年初中組〔：微型計算機(jī)的問世是由于( C )的消滅。中小規(guī)模集成電路 B)晶體管電路 C)(超)大規(guī)模集成電路 D)電子管電路2023年初中組〔：以下說法中正確的選項是( B )。計算機(jī)體積越大,其功能就越強(qiáng)CPU兩個顯示器屏幕大小一樣,則它們的區(qū)分率必定一樣點陣打印機(jī)的針數(shù)越多,則能打印的漢字字體越多2023年初中組〔：CPU處理數(shù)據(jù)的根本單位是字,一個字的字長( D )。A)為8個二進(jìn)制位 B)為16個二進(jìn)制位C)為32個二進(jìn)制位 D)與芯片的型號有關(guān)2023年高中組〔：中心處理器〔CPU〕能訪問的最大存儲器容量取決于〔 A 。A〕地址總線 B〕數(shù)據(jù)總線 C〕把握總線 D〕實際內(nèi)存容量2023年高中組〔11：微型計算機(jī)中〔 C 〕的存取速度最快。A〕高速緩存 B〕外存儲器 C〕存放器 D〕內(nèi)存儲器2023年初中組〔：斷電后計算機(jī)信息照舊存在的部件為( C )。A)存放器 B)RAM存儲器 C)ROM存儲 D)運算器2023年初中〔11說一臺微機(jī)的CPU是用的PII300此處的300精準(zhǔn)指的是( A )A)CPU的主時鐘頻率 B)CPU產(chǎn)品的系列號C)每秒執(zhí)行300百萬條指令 D)此種CPU允許最大內(nèi)存容量2023年初中組〔17：以下設(shè)備哪一項不是計算機(jī)輸入設(shè)備( C )A)鼠標(biāo) B)掃描儀 C)數(shù)字化儀 D)繪圖儀2023年初中組〔18：在計算機(jī)硬件系統(tǒng)中，cache是( D )存儲器A)只讀 B)可編程只讀 C)可擦除可編程只讀 D)高速緩沖2-3個多媒體〔概念、組成、圖片文件格式和相關(guān)軟件使用學(xué)問等〕和網(wǎng)絡(luò)方面〔IP地址、域名、EMAIL、協(xié)議等〕的題目；2023多媒體計算機(jī)是指( D )計算機(jī)。專供家庭使用的 B)裝有CDROM的C)連接在網(wǎng)絡(luò)上的高級 D)具有處理文字、圖形、聲音、影像等信息的9在使用E-mailOutlookISP〔A效勞器。A〕POP3 B〕SMTP C〕DNS D〕FTP用畫筆(Paintbrush)繪制圖形并存儲在文件中,該圖形文件的文件名缺省的后綴為( B )。.jpg B).bmp C).gif D).tiffE-mail地址中用戶名和郵件所在效勞器名之間的分隔符號是( B )。A)# B)@ C)& D)$13)IPv4地址是由(B )位二進(jìn)制數(shù)碼表示的。A)16 B)32 c)24 D)8202312〕TCP/IPC)層協(xié)議。A)3 B)4C)5D)62-3個WIN98及自帶的根本工具軟件〔查找、磁盤工具〕和資源治理器方面〔文件名、通配符等〕的題目；2023在Windows98中,通過查找命令查找文件時,假設(shè)輸入F*.?,則以下文件( C )可以被查到。F.BAS B)FABC.BAS C)F.C D)EF.資源治理器的名目前圖標(biāo)中增加“+“號,這個符號的意思是( B )。該名目下的子名目已經(jīng)開放 B)該名目下還有子名目未開放C)該名目下沒有子名目 D)該名目為空名目,啟動WORD的不正確方法是( C )。OfficeWord單擊“開頭“→“程序“→WordWord雙擊桌面上的“Word快捷圖標(biāo)“在樹型名目構(gòu)造中,不允許兩個文件名一樣主要是指( D )。同一個磁盤的不同名目下 B)不同磁盤的同一個名目下C)不同磁盤的不同名目下 D)同一個磁盤的同一個名目下以下表達(dá)中,錯誤的選項是( C )。ExcelWordWord用記事本(Notepad)編輯文本時可以插入圖片用畫筆(Paintbrush)繪圖時可以輸入文字8〕在磁盤上建立子名目有很多優(yōu)點以下描述中不屬于建立子名目優(yōu)點的〔 D 。A〕便于文件治理 B〕解決根名目中名目項個數(shù)有限問題C〕加快文件查找速度 D〕節(jié)約磁盤使用空間在WORD文檔編輯中實現(xiàn)圖文混合排版時關(guān)于文本框的以下表達(dá)正確的選項是〔 C 。A〕文本框中的圖形沒有方法和文檔中輸入文字疊加在一起，只能在文檔的不同位置B〕文本框中的圖形不行以襯于文檔中輸入的文字的下方C〕通過文本框，可以實現(xiàn)圖形和文檔中輸入的文字的疊加，也可以實現(xiàn)文字圍繞D〕將圖形放入文本框后，文檔中輸入的文字不能圍繞圖形2023以下對Windows的表達(dá)中，正確的選項是( A )。A)從軟盤上刪除的文件和文件夾，不送到回收站在同一個文件夾中，可以創(chuàng)立兩個同類、同名的文件刪除了某個應(yīng)用程序的快捷方式，將刪除該應(yīng)用程序?qū)?yīng)的文件D)不能翻開兩個寫字板應(yīng)用程序其他：軟件、病毒、使用習(xí)慣、ASCII碼和漢字編碼等；2023以下哪一種程序設(shè)計語言是解釋執(zhí)行的( B )。Pascal B)GWBASIC C)C++ D)FORTRAN7〕計算機(jī)病毒傳染的必要條件是〔 B 。A〕在內(nèi)存中運行病毒程序 B〕對磁盤進(jìn)展讀寫操作C〕在內(nèi)存中運行含有病毒的可執(zhí)行的程序 D〕復(fù)制文件2023計算機(jī)軟件保護(hù)法是用來保護(hù)軟件( D )的。A)編寫權(quán) B)復(fù)制權(quán) C)使用權(quán) D)著作權(quán)下面關(guān)于算法的錯誤說法是( B )。算法必需有輸出 B)算法必需在計算機(jī)上用某種語言實現(xiàn)C)算法不愿定有輸入 D)算法必需在有限步執(zhí)行后能完畢解釋程序的功能是( C )。將高級語言程序轉(zhuǎn)換為目標(biāo)程序B)將匯編語言程序轉(zhuǎn)換為目標(biāo)程序C)解釋執(zhí)行高級語言程序 D)解釋執(zhí)行匯編語言程序13〕應(yīng)用軟件和系統(tǒng)軟件的相互關(guān)系是( B )。A)后者以前為根底 B)前者以后者為根底C)每一類都以另一類為根底D)每一類都不以另一類為根底16〕計算機(jī)病毒是( B )。通過計算機(jī)傳播的危害人體安康的一種病毒人為制造的能夠侵入計算機(jī)系統(tǒng)并給計算機(jī)帶來故障的程序或指令集合C)一種由于計算機(jī)元器件老化而產(chǎn)生的對生態(tài)環(huán)境有害的物質(zhì)D)利用計算機(jī)的海量高速運算力氣而研制出來的用于疾病預(yù)防的型病毒填空〔152-3〕這局部題目對數(shù)學(xué)要求要高一點，往往考察的是數(shù)學(xué)問題〔如代數(shù)變形、組合、概論統(tǒng)計等，數(shù)列〔一般是考遞推、遞歸、歸納法等學(xué)問〔如隊列、棧、二叉樹。建議大家多花一點時間做，盡量做對。1.數(shù)組A[30..100,20..100]以行優(yōu)先的方式存儲,每個元素占8個字節(jié),且A[40,30]的地址為20230,則A[60,90]的地址為: 。假設(shè)以列優(yōu)先存儲,則為: 。X，則：X+〔40-30〕*〔100-20+1〕+〔30-20〕*8=20230前面的行數(shù)每行的列數(shù)本行中序號每個元素的基則：X=13340，用上述的式子，不難算出：A[60，90]的地址：33340列優(yōu)先存儲，只要略微改動上述公式，結(jié)果略；考察了數(shù)據(jù)構(gòu)造中數(shù)組存儲方式。還可以考數(shù)組基類型為記錄的狀況，可以問你同樣的問題；或者問你共占用多少空間！2.〔1998年初中組〕設(shè)棧S的初始狀態(tài)為空,現(xiàn)有5個元素組成的序列{1,2,3,4,5},對該序列在S棧上依次進(jìn)展如下操作(從序列中的1開頭,出棧后不在進(jìn)棧):進(jìn)棧,進(jìn)棧,進(jìn)棧,出棧,進(jìn)棧,出棧,進(jìn)棧,問出棧的元素序列是: ,棧頂指針的值為 ，棧頂元素為: 。解答：出棧序列為{3，4}，棧頂指針值為3，棧頂元素為5。考察了數(shù)據(jù)構(gòu)造中的棧。還可以把棧和隊列結(jié)合起來考！如下題：3．如2023年高中組：設(shè)棧S和隊列Q初始狀態(tài)為空，元素e ，e ，e ，e ，e ，e1 2 3 4 5 6次通過棧S，一個元素出棧后即進(jìn)入隊列Q，假設(shè)出隊挨次為e ，e ，e ，e ，e ，e ，2 4 3 6 5 1則棧S的容量至少應(yīng)當(dāng)為 。3。4〔2023年初中組〕設(shè)循環(huán)隊列中數(shù)組的下標(biāo)范圍是1..n，其頭尾指針分別為f和r，其元素個數(shù)為： ?！瞨-f+n〕modn考察了數(shù)據(jù)構(gòu)造中的隊列。5.中綴表達(dá)式、前綴表達(dá)式、后綴表達(dá)式〔1997〕〔1)中綴表達(dá)式：A+B*C/D求它的前綴表達(dá)式和后綴表達(dá)式？〔2〕前綴表達(dá)式：+△A*B△C {注△表示一元運算符負(fù)號，即△A表示-A}求它的中綴表達(dá)式和后綴表達(dá)式？解答：畫〔二叉〕表達(dá)式樹?！?〕的結(jié)果：+A*B/CD；ABCD/*+〔〕-A〕+B〔-C；A△BC△*+考察了數(shù)據(jù)構(gòu)造中的表達(dá)式樹。6.〔1998〕U1,U2,U3...Un...KK個數(shù)a1,a2,..,ak,使得數(shù)列從某項開頭都滿足:U(n+k)=a1*U(n+k-1)＋a2*U(n+k-2)+......＋akUn A)例如數(shù)列1,1,2,3,5.....K=2,a1=1,a2=13(N>=1)滿足:U(n+2)＝U(n+1)＋Un試對數(shù)列1^3,2^3,3^3,......,N^3,??K和a1,a2,...ak,使得式AK=2，列出方程組：a1*12+a2*22=32a1*22+a2*32=42以上方程組無整數(shù)解。再設(shè)K=3，列出方程組：a1*02+a2*12+a3*22=32a1*12+a2*22+a3*32=42a1*22+a2*32+a3*42=52以上方程的整數(shù)解為：a1=1，a2=-3，a3=3，此時K=3。實質(zhì)是考數(shù)學(xué)。7.〔1998年高中組〕給出一棵二叉樹的中序遍歷:DBGEACHFI與后序遍歷:DGEBHIFCA,畫出此二叉樹。8.〔1996年高中組〕下面是一個利用完全二叉樹特性,用挨次表來存儲的一個二叉樹,結(jié)點數(shù)據(jù)為字符型(結(jié)點層次從小到大,同一層從左到右挨次存儲,#表示空結(jié)點,@表示存儲數(shù)據(jù)完畢)。結(jié)點123 456789101112131415數(shù)據(jù)ABC ##DE#####GF@請畫出對應(yīng)的二叉樹。解答：以上兩題的圖分別如下：以上兩題實質(zhì)是考數(shù)據(jù)構(gòu)造中的二叉樹。還常?？级鏄涞挠嫈?shù)！如下題：9．〔2023年初中組〕abc，二叉樹可以得到這一遍歷結(jié)果，并畫出這些二叉樹。解答：510〔1999年初中組〕例如以以下圖A盤的名目構(gòu)造：D1，Dll，…，D2均表示子名目的名字。在這里，根名目2，D13，D114，D12，D2，D111，D112，D113的1。不考慮子名目的名字，則可簡潔的圖示為如下所示的樹構(gòu)造：2231個，度43個。1的子名目有幾個？解答：一種方法是畫圖；另外，可以依據(jù)整棵樹的入度=出度〔由于任一根關(guān)聯(lián)邊連接兩個結(jié)點〕這一性質(zhì)推導(dǎo)，除根結(jié)點外的每個結(jié)點入度都是1，所以總的入度=1*x+1*2+1*1+1*3-10，分支結(jié)點的出度為度數(shù)-1，根結(jié)點的出度就是它的度，所以總的出度=0*x+〔2-1〕*2+〔3-1〕*1+〔4-1〕*3+1；算出：x=9?？疾炝擞嬎銠C(jī)中的名目構(gòu)造和樹構(gòu)造中的“度”的概念和性質(zhì)。11〔1998年高中組〕用鄰接矩陣/鄰接表表示下面的無向/有向圖〔略。考察了數(shù)據(jù)構(gòu)造中的圖的表示。12.〔1999〕Nocomachnsnn連續(xù)的奇數(shù)的和。例如：13=123=3+533=7+9+1143=13+15+17+19在這里，假設(shè)將每一個式中的最小奇數(shù)稱為X，那么當(dāng)給出n之后，請寫出X與n之間的關(guān)系表達(dá)式： 。解答：X=n*(n-1)+1考察代數(shù)和遞推力氣！13〔2023年高中組〕設(shè)有一個共有n級的樓梯，某人每步可走1級，也可走2級，也可走3n=3時，共有4種走1+1+1,1+2,2+1,3。n=1,2,3簡潔錯；二是用組合數(shù)學(xué)和歸納法進(jìn)展推導(dǎo)，一般先假設(shè)F〔n〕=a*F〔n-1〕+b*F〔n-2〕+c*F〔n-3〕+……，然后算a，b，c……直到某個系數(shù)=0就完畢，再代入式子中。F〔1〕＝1 F〔2〕＝2 F〔3〕＝4F〔N〕＝F〔N－3〕＋F〔N－2〕＋F〔N－1〕 〔N≥4〕14〔2023年初中組〕有2n的一個長方形方格，用一個×2的骨牌鋪滿方格。例如n=32×31×23試對給出的任意一個〔n>0，求出鋪法總數(shù)的遞推公式解答：F〔1〕=1 F〔2〕=2F〔n〕=F〔n-2〕+F〔n-1〔n≥3〕以上兩題，考察了歸納+加法原理+乘法原理+遞歸關(guān)系式！這是近年來的常見題。15．(2023NM:N=2,M=36法:紅紅黃黃黃紅黃紅黃黃紅黃黃紅黃黃紅紅黃黃黃紅黃紅黃黃黃黃紅紅。問題：當(dāng)N=4,M=3時有多少種不同排法?(不用列出每種排法)解答：35排列組合和概率統(tǒng)計！16〔1999年高中組〕將Ln定義為求在一個平面中用n條直線所能確定的最大區(qū)域數(shù)目。例如：當(dāng)n=1L=2,進(jìn)一步考慮，用n條折成角的直線〔角度任意1Znn=1，Z1=2〔如以以下圖所示〕n1Ln= 2Zn= 解答：此題實質(zhì)是求直線或折線將一個平面分成的最大區(qū)域數(shù)，從兩個方面考慮：nn=1,L1=2, F(1)=2n=2,L2=4, F(2)=F(1)+2n=3,L3=7, F(3)=F(2)+3n=4,L4=11, F(4)=F(3)+4??所以， F(n)=F(n-1)+n把上面的n個等式左右相加，化簡得出：+即：L〔n〕=n*(n+1)/2+1nn=1,Z1=2, F(1)=0+2n=2,Z2=7, F(2)=1*(2*2-1)+4n=3,Z3=16, F(3)=2*(2*3-1)+6n=4,Z4=29, F(4)=3*(2*4-1)+8??所以， F(n)=(n-1)*(2*n-1)+2*n即：Z〔n〕=(n-1)*(2*n-1)+2*n幾何+歸納+組合數(shù)學(xué)！17．(1998年初中組)50a，b，c三本書的書名，將讀過的書打a8人；只讀b4人；只讀c3人；2a，b4a，c2人；讀過b，c兩3人；問：讀過a的人數(shù)是 〔2〕一本書也沒有讀過的人數(shù)是 。解答〔1〕12人 〔〕30人方法：推理或集合表示如下：aa+ab+abc+ac=8+2+2+0=12一本未讀過的人：50-a-b-c-abc-ab-ac-bc=30規(guī)律推理+集合運算及變形！近兩年NOIP初賽填空題舉例：2023年高中〔1〕在書架上放有編號為1，2．n的n本書。現(xiàn)將n當(dāng)放回去時要求每本書都不能放在原來的位置上。例如：n=3時：原來位置為：1 2 3放回去時只能為：3 1 2 或2 3 1 這兩種n=5時滿足以上條件的放法共有多少種？〔不用列出每種放法〕解答：f(n)=n*f(n-1)+1(n>1,且n為偶數(shù)時取+，n為奇數(shù)時取-)-f(1)=0n=5442023年高中〔2〕0和k0k0和kn0和k0

，kkn 0和度，kk0knk和數(shù)字。0

n 〔n

=數(shù)學(xué)表達(dá)式，數(shù)學(xué)表達(dá)式僅含n 、解答：nnn=(k-1)n+1。0 k 0 k2023年初中〔1〕S,1,2,3,4,5廂可以向左行走,也可以進(jìn)入棧S3請寫出全部可能的到達(dá)出口的車廂排列總數(shù)(不必給出每種排列)。12345出口← ←12345S↓解答：92023〔2〕NM:N=2,M=36黃紅黃黃紅黃黃紅黃黃紅紅黃黃黃紅黃紅黃黃黃黃紅紅N=4,M=3解答：352023〔1〕一棵二叉樹的結(jié)點名為大寫英文字母，其中序與后序遍歷的挨次分別為：CBGEAFHDIJCGEBHFJIDA，則該二叉樹的先序遍歷的挨次為：解答：ABCEGDFHIJ2023〔2〕平面上有三條平行直線，每條直線上分別有7，5，6個點，且不同直線上三個點都不在同一條直線上。問用這些點為頂點，能組成多少個不同四邊形？解答：22502023〔1〕在a,b,c,d,e,f六件物品中，按下面的條件能選出的物品是： 。a,b(2)a,d(3)a,e,f2b,cc,dd不選，則e解答：a,b,c,f2023〔2〕平面上有三條平行直線，每條直線上分別有7，5，6個點，且不同直線上三個點都不在同一條直線上。問用這些點為頂點，能組成多少個不同三角形？解答：751。閱讀程序，寫運行結(jié)果(25分左右,3-4題)其實很簡潔,目的幾乎是送分，而且占的分?jǐn)?shù)很多，但得分率卻不見得高。很簡潔不明不白的就把分〔全〕丟了!!!這局部程序考3程序設(shè)計語言本身，如循環(huán)、遞歸、值型參和變量型參數(shù)、跟蹤變量等；歸納和數(shù)學(xué)運算力氣；是否把握了一些常用算法〔程序段〕的框架；細(xì)心、急躁等心理品質(zhì)；靈感+編程的量等；一般做這類題目的核心是找程序目的：即這個程序想干什么。迄今為止考過的題目還沒有“亂寫”的，總有一點“寫作目的”的。抓住了它，不僅得出答案變得很簡潔了，而且對自己的結(jié)果也會比較有信念。一般的解題步驟如下：從總體上通讀程序，大致把握程序的目的和算法；猜測變量的作用，跟蹤主要變量值的變化〔列表，找出規(guī)律；將程序分段，理清每一小段的作用和目的〔靈感+關(guān)鍵表達(dá)式和語句的領(lǐng)悟；看清輸入、依據(jù)輸出格式，寫出結(jié)果；帶著得到的結(jié)果回到程序進(jìn)展檢查；下面舉幾個例子。1．基此題(考語言本身，尤其是循環(huán)嵌套。1999年初中組)Programexcpl;varx,y,y1,jk,j1,g,e:Integer;a:array[1..20]of0..9;beginx:=3465;y:=264;jk:=20;forj1:=1to20doa[j1]:=0;whiley<>0dobeginy1:=ymod10;y:=ydiv10;whiley1<>0dobeging:=x;fore:=Jkdownto1dobeging:=g+a[e];a[e]:=gmod10;g:=gdiv10end;y1:=y1-1end;jk:=jk-1end;j1:=1;whilea[j1]=0doj1:=j1+1;forJk:=j1to20dowrite(a[jk]:4);writelnend.程序運行結(jié)果為： 。解答：程序不長，但是有確定的難度。高手最多半分鐘就看懂了程序的意思，但初學(xué)者往往算了很久得出了結(jié)果卻是錯的。下面我們還是先以一個初學(xué)者的身份分析一下這個程序。記住，不要一開頭就模擬電腦來一個個語句“執(zhí)行”-------你算過自己是多少Hz的CPU沒有？！i就是j，很厭煩。i和j般作為循環(huán)計數(shù)器，沒有什么意思，因此不要管它了。然后要看變量在程序的哪里消滅過，著重看它與其它變量的相互引用關(guān)系，猜測它的作用。例如上題：xg:=x不要管它，由于它很可能只是一個初始數(shù)據(jù)。y1)whiley<>0do2)y1:=ymod10;y:=ydiv10;很明顯，y每次少了最終一位數(shù)字,把這位數(shù)字給了y1。有閱歷的選手應(yīng)當(dāng)體會到了什么，不過我們連續(xù)?，F(xiàn)在我們知道了：y對程序的作用是：每次供給最終一位給y1,y14,6,2y1，它消滅在兩個地方:1)whiley1<>0do2)y1=y1-1y1jk:fore:=jkdownto1do2)jk:=jk-1jk作為循環(huán)初始值，竟然一次比一次少...其緣由有待進(jìn)一步分析。j1:1)forj1:=1to20doa[j1]:=0;2)j1:=1;3)whilea[j1]=0doj1:=j1+1;4)forJk:=j1to20dowrite(a[jk]:4);明顯，j1和其它變量沒有什么聯(lián)系。1)是初始化，2)3)4)是輸出數(shù)組a。g:消滅的位置是幾層循環(huán)之內(nèi)了，應(yīng)當(dāng)很重要！一會兒再分析！e:作為循環(huán)變量，沒有什么意思。通過變量分析，我們知道了：x,yyy1,循環(huán)y1j1g下面依據(jù)程序構(gòu)造，把程序分成幾塊，逐個爭論。最主要的程序段是兩個WHILE循環(huán)中套一個FOR〔y=0前后都很簡潔，是一些變量和數(shù)組的初始化、輸入、輸出等，下面重點剖析核心程序段。1〕x:=3465;y:=264;jk:=20;forj1:=1to20doa[j1]:=0;輸入與變量、數(shù)組的初始化，不要管它。whiley<>0dobeginy1:=ymod10;6即：y:=ydiv10;whiley1<>06即：<<g:=x;fore:=Jkdownto1dobeging:=g+a[e];a[e]:=gmod10;語句g:=x;執(zhí)行后變量狀況：g:=gdiv10g:=g+a[e];g=x+a[e];end;>>y1:=y1-1end;a[e]:=gmod10;g:=gdiv10;g:=g+a[e-1];a[e-1]:=gmod10;a[e]:=x+a[e]的個位g=(x+a[e])的前幾位g=(x+a[e])的前幾位+a[e-1];a[e-1]=a[e-1]+(x+a[e])的進(jìn)位jk:=jk-1??end;3)j1:=1;whilea[j1]=0doj1:=j1+1;forJk:=j1to20dowrite(a[jk]:4);writeln從前往后，找到<>0的位置開頭，輸出數(shù)組元素的值〔輸出結(jié)果，也不要管它。2Yy1,執(zhí)行<<運算>>y1jk1。現(xiàn)在最重要的是<<運算>>中的在干什么？a[],a[]的變化！a[e]總是取個位(gmod10)，ga[e-1](別忘了e莫非是...高精度加法？？？RIGHT！y1，y1每次都是yx*y所以答案就是3465*264=914760再看它的輸出格式，輸出的應(yīng)當(dāng)是： 9 1 4 7 6 0其實有閱歷的話，看到gg:=g+a[e];a[e]:=gmod10;個標(biāo)志句子。就可以一下子知道程序的用意了。根本方法；主要程序段可以通過列表了解變量的變化狀況；要細(xì)心、急躁；題純粹考算法思路，如下面的例子：2.programex2;vari,j,n:longint;b:array[0..31]of0..1;beginn=1999;i:=0;whilen<>0dobeginb[i]:=nmod2;i:=i+1;n:=ndiv2end.

end;forj:=i-1downto0dowrite(b[j]);輸出什么？解答：很明顯，是把十進(jìn)制整數(shù)轉(zhuǎn)換成二進(jìn)制數(shù)，所以輸出111110011113.有些題目則是考數(shù)學(xué)，或依據(jù)一些根本規(guī)章重復(fù)地做某個操作。如：programexp1(imput,output);vari,,s,max:integer;a:array[1..10]ofinteger;beginfori:=1to10do read(a[i]);max:=a[1]；s:=a[1];fori：=2to10dobeginifs<0thens：=0;s：=s+a[i];ifs>maxthenmax：=send;end.

writeln(‘max=’,max)輸入：89－124651115－289輸出：max=解答：此題主要做累加：s：=s+a[i];再依據(jù)結(jié)果打擂臺。但最關(guān)鍵的語句是：ifs<0thens：=0s<0的和值屏蔽掉〔置0。了解了這一點，題目就很簡潔了。步驟如下：s<0?s=8s>max?max=8;I=2N8+9=17Ymax=17;I=3N17-1=16Nmax=17;I=4N16+24=40Ymax=40;I=5N10+6=46Ymax=46;I=6N46+5=51Ymax=51;I=7N51+11=62Ymax=62;I=8N62+15=77Ymax=77;I=9N77-28=49Nmax=77;I=10N49+9=58Nmax=77;所以結(jié)果為：77。小結(jié)：本質(zhì)是求一個n長的整數(shù)數(shù)列的連續(xù)x長的子序列，要求子序列的和最大！留意：smax！！另外此題給的輸入數(shù)據(jù)比較簡潔，所以有很多人沒有完全懂-112-1036534-4-278-12349果是多少呢？答：9！！考子程序的調(diào)用，尤其是遞歸或帶參數(shù)〔值參與變量型參數(shù)PROGRAMEX3；CONSTN=10;VARS,I:INTEGER;FUNCTIONCO(I1:INTEGER):INTEGER;VARJ1,S1:INTEGER;BEGINS1:=N;FORJ1:=(N-1)DOWNTO(N-I1+1)DOS1:=S1*J1DIV(N-J1+1);CO:=S1END;BEGINS:=N+1;FORI:=2TONDOS:=S+CO(I);WRITELN(‘S=’,S);END.解答過程：假設(shè)有子程序，一般先讀主程序，了解主程序什么時候調(diào)用子程序？干什n-1再單獨閱讀子程序，分析變量、參數(shù)和返回值，確定它的功能。此題函數(shù)猛一看好象比較簡潔，不過是通過一個循環(huán)構(gòu)造完成累乘和累除，下面再具體分析！通過列表，觀看子程序中的變量變化狀況，以便找出規(guī)律，確定子程序的作用。此題如下：CO〔2〕=10*9/2CO〔3〕=10*9*8/2/3CO〔4〕=10*9*8*7/2/3/4??覺察,好象是組合數(shù)學(xué)的公式：CO〔i〕=10！/〔i!*(10-i)!〕即：C(m,n)=m!/(n!*(m-n)!)=m*(m-1)*??*(m-n+1)/n!〔4〕所以結(jié)果很明確：C(10,0)+C(10,1)+??+C(10,9)+C(10,10)=722總結(jié)：靈感來源于豐富的數(shù)學(xué)根底和閱歷！完善程序〔30分=2*15〕這局部題目得分率很低。沒關(guān)系，盡量做吧。實在不會把一些簡潔的填好就行了。有〕i:=i+1；i:=0；留意常常問自己程序中有沒有做下面的事：初始化(i:=0;j:=0;fori:=1tondoa[i]:=02〕一些明顯的動作：a.結(jié)果沒有儲存在需要的地方。b.累加器沒有做加法c.輸出3)關(guān)鍵動作。例如交換排序程序的“交換”操作等很明顯需要完成的操作。分析方法和寫運行結(jié)果類似，留意分析變量和程序構(gòu)造，理解變量和模塊的作用是解題的關(guān)鍵。不嫻熟是不妨用自然語言描述一下。一般的解題步驟：認(rèn)真閱讀程序的目的和算法、數(shù)據(jù)構(gòu)造的描述！！把程序中的變量和題目中數(shù)據(jù)構(gòu)造描述結(jié)合起來，記住關(guān)鍵變量的作用?。〗Y(jié)合問題的算法描述和要求及步驟，把程序劃分成幾段，每段完成指定的功能！逐步解決每段！留意不要由于個別空而影響你對整個程序的把握，不知道的，先空在那兒，把知道！留意確定要提示自己：程序中有沒有做那些最根本的事。做完后，不要忘了把程序從前往后讀兩遍，看看是否完成了題目的任務(wù)；還要檢查一n-，還是n-i+1？下面舉例賜予說明。根底題〔[程序的說明]100050之間的隨機(jī)數(shù)用一個數(shù)組存放后進(jìn)展排序，然后再將其中重復(fù)消滅的數(shù)進(jìn)展刪除，只保存一個，使得剩下的數(shù)中任何兩個都不一樣且連續(xù)存儲在原數(shù)組中。constmaxn=100;typearraytype=array[1..maxn]ofinteger;vari,j,temp,current,tail:integer;a:arraytype;beginrandomize;fori:=1tomaxndoa[i]:=random(51);fori:=1to ① doforj:=_②_tomaxndoifa[i]<a[j]thenbegintemp:=a[i];a[i]:=a[j];a[j]:=tempend;fori:=2tomaxndoif ③ thena[i]:=-a[i];tail:=0;current:=1;while ④ dobeginwhilea[current]<0docurrent:=current+1;tail:=tail+1;a[tail]:= ⑤ ;current:=current+1end;if ⑥

thenbegintail:=tail+1;a[tail]:=0end;end.

fori:=1totaildowrite(a[i]:5);writeln[解答]程序的思想已經(jīng)不能再清楚了，由于要排序〔很明顯是冒泡排序，所以：①maxn-1②i+1那么如何刪除呢？先分析一下變量的含義，currenttail再看刪的過程：好象是先做標(biāo)記〔，然后從隊首current開頭找第1個沒被做標(biāo)記〔>0〕的數(shù)，把它放到當(dāng)前隊尾tail的下一個位置。所以：③a[i]=abs(a[i-1])④(current<=maxn)and(a[current]<>0)⑤a[current]⑥(a[tail]<>0)and(a[current]=0)關(guān)鍵變量+特定的思想方法+靈感〔1995年初中組2〕336成盡可能多的不同整數(shù)。2，3，52,3,5，2+3=5〔5〕2+5=7, 3+5=8, 2+3+5=102，3，56程序要求：輸出所選的這6個數(shù)，以及能組成不同整數(shù)的個數(shù)。6A6主要程序段：A[1]:=1;t:=0;Fori:=2to6dobegin ① ;forj:=1toi-1dos:= ② ;a[i]:= ③ ;end;Fori:=1to6doBegint:= ④ ;WRITE(a[i],””);End;Writeln(”能組成不同整數(shù)的個數(shù)：”,t)ss，s不要焦急，我們爭論一下題目的例子和算法提要，覺察：選擇的6個數(shù)〔a[i]〕應(yīng)當(dāng)盡可能不重復(fù)；且a[i]>a[i-1]而a[i]還要盡可能小；假設(shè)現(xiàn)在已求出了a[1]?a[i-1]，a[i]應(yīng)當(dāng)取a[1]+a[2]+?+a[i-1]+1,這！s:=0;②累加1：s+1；那么④怎么填呢？它表示能組成的不同整數(shù)的個數(shù)，那為什么要掃描一遍數(shù)組呢？感61248163〔哦，難怪說小于33！讓我更加堅信上面做的是對的，很明顯是二進(jìn)制數(shù)的問題嗎？本質(zhì)上就是一個求一個6位的二進(jìn)制數(shù)最多能表示多少狀態(tài)？答案為：20+21+22+23+4+25=1+2+4+8+16+32。不要感動，看題目④填什么？累加：t+a[i]。簡潔的問題描述+簡潔的程序+細(xì)心地處理細(xì)節(jié)問題〔1995年高中組3〕xx：array[1..N]ofchar例如 x=(””,”2”,”0”,””,”3”,”.”,”5”,”%”) 則表示203.5x=(”-”,”1”,”.”,””,”2”,”0”,”%”) 則表示-1.2xx[1]外，其后可以包含有假設(shè)干個”.”與””，但僅以第一次消滅的為準(zhǔn)，空格不起任何作用，并以字符”%”作為完畢標(biāo)志。程序要求：將輸入的字符串復(fù)原成實數(shù)輸出〔小數(shù)點后無用的0應(yīng)除去以以下形式存放〔不需要輸出。F01。A：array[1..N]ofinteger;存放數(shù)字，不放小數(shù)點。K：表示A中有效數(shù)字的個數(shù)。J：表示小數(shù)點后的位數(shù)。例如：數(shù)203.24，復(fù)原后結(jié)果的存放是：F=0A=(2,0,3,2,4)K=5J=2又如：數(shù)-33.0740，復(fù)原后結(jié)果的存放是：F=1A=(3,3,0,7,4)K=5J=3算法提要：x:array[1..10]ofchar10；首先讀入字符串，然后處理數(shù)的符號，在復(fù)原的過程中，需要判定整數(shù)局部與小數(shù)局部，同時去除多余的空格和小數(shù)點，并商定輸入是正確的，不用作出錯檢查。只要程序段：ForI:=1to10doa[I]:=0;ForI:=1to10doread(x[I]);J:=0;f:=0;k:=0;b:=0;Ifx[1]=”-”thenbegin ① ; ② ;EndElseifx[1]:=””thenI:=2ElseI:=1;While ③

doI:=I+1;While ④ doBEGINIf(x[I]>=”0”)and(x[I]<=”9”)Thenbegink:=k+1; ⑤ ;Ifb=1then ⑥ ;endElseif(x[I]=”.”)and(b=0)thenb:=1;I:=I+1END;Ifj>0thenwhilea[k]=0dobegin ⑦ ⑧ End;解答：明顯，藍(lán)色的程序段是用來處理實數(shù)的符號的，所以依據(jù)商定①應(yīng)當(dāng)是設(shè)置負(fù)f:=1;elseii:=2；x[i]=’’〕and〔i<10〕;④也很明顯，一個大循環(huán)，推斷字符串是否掃描完畢，即：x[i]<>’%’b變量的含義：依據(jù)else子句，覺察b=1數(shù)字字符轉(zhuǎn)換成數(shù)字填到數(shù)組a中a[k]:=ord(x[i])-48；⑥填j:=j+1;(j的位數(shù))；0j:=j-1;k:=k-1;！典型算法+數(shù)據(jù)構(gòu)造〔1996年高中組1/初中組3〕四色問題：N=81，2，??，N。圖形之間的相鄰關(guān)系用下面的鄰接矩陣表示：其中：1——相鄰，0——不相鄰。12345678[程序要求]將上面圖形的每一個局部涂上紅101000011〔，黃〔2，藍(lán)〔3，綠〔〕四種顏色之一，要求210100110相鄰的局部有不同顏色。301010100輸入方式：鄰接矩陣。400101100輸出方式：區(qū)域、顏色。500010100[算法描述] 用數(shù)組R:ARRAY[1..N,1..N]OF6011110100..1S:ARRAY[1..N]OFINTEGER711000101顏色。810000010承受回溯的方法，首先給第一個圖形涂上紅色〔1他顏色，當(dāng)有沖突時回溯解決。［程 序］PROGRAMEXP2(INPUT,OUTPUT);CONSTN=8;VARI,J,K:INTEGER;R:ARRAY[1..N,1..N]OF0..1;S:ARRAY[1..N] OFINTEGER;BEGINFORI:=1TONDOBEGINFORJ:=1TONDOREAD(R[I,J]);READLNEND; ① ；I:=2;J:=1;WHILEI<=NDOBEGINWHILE(J<=4)AND(I<=N)DOBEGINK:=1;WHILE ② DOK:=K+1;IFK<ITHEN ③ ELSEBEGIN ④ ; I:=I+1;J:=1ENDEND;IFJ>4THENBEGINI:=I-1; ⑤ END;END;FORI:=1TONDOWRITELN(I,””,S[I])END.解答：鄰接矩陣+回溯法，步驟略，答案如下：①S[1]：=1；②(K<I)AND(S[K]*R[I,J])<>J③J:=J+1;④S[I]:=J;⑤J:=S[I]+1;5.子程序及參數(shù)〔1999〕[問題描述]A，BA，B〔無相同元素，現(xiàn)將AB合并為數(shù)組，同樣要求數(shù)組C也是從小到大排好序〔保存一個。NA，Bi，j，k分別表示數(shù)組A，B，C[程序清單]programexcp3;constn=8;m=2*n;typearr1=array[1..n]ofinteger;arr2=array[1..m]ofinteger;var a,b:arr1;c:arr2;i,j,k:integer;procedurecopy(x:arr1;vary:arr2;vari,j:integer);begini:=i+1;y[i]:=x[j];j:=j+1;end;beginfori:=1tondoread(a[i]);readln;fori:=1tondoread(b[i]);readln;i:=1;j:=1; ① while ② doifa[i]<b[j]thencopy(a,c,k,i)elseifb[j]<a[i]thencopy(b,c,k,j)elsebegincopy(a,c,k,i); ③ end;while ④ docopy(a,c,k,i);while ⑤ docopy(b,c,k,j);fori:=1tokdowrite(c[i]:4);writeln;end.解答：就此題而言，算法和題目本身對選手很清楚！線性表的歸并操作在NOIP屢次，不管是用數(shù)組來操作還是用鏈表操作；甚至還有一些題目是它的變形〔比方多項式的加法。此題中的copy〔關(guān)鍵是參數(shù)的書寫4答案：①k:=0②(i<=n)and(j<=n)③j:=j+1④i<=n⑤j<=n特定的算法〔1999年高中組2〕[問題描述]用生成法求出1，2，?，r(r<=8)[算法過程]用數(shù)組：a:array[1..r]ofinteger;表示排列；初始化時，a[I]:=1(I=1,2,?.f)設(shè)中間的某一個排列為a[1],a[2],?a[r]，則求出下一個排列的算法為：從后面對前找，直到找到一個挨次為止〔設(shè)下標(biāo)為j,則a[j-1]<a[j]〕[程序清單]programexp4;constr=7;

a[j]-a[ra[k]a[j-1]大的最小元素a[j-1a[Ｋ]交換a[j]，a[j+1]??a[r]由小到大排序。varn,i,s,k,j,i1,t:intger;a:array[1..r]ofinteger;procedureprint1;varik:integer;beginforik:=1tordowrite(a[ik]:8);writeln;endbeginfori:=1tordo ① ;print1;s:=1;fori:=2tordos:=s*i;s:=s-1;fori:= ② dobeginj:=r;while ③ doj:=j-1; k:=j;fori1:=j+1tordoif ④ thenk:=i1;步驟2t:=a[j-1];a[j-1]:=a[k];a[k]:=t; fori1:=jtor-1dofork:=i1+1tordoif ⑤ then begint:=a[i1];a[i1]:=a[k];a[k]:=t;end;print1;end;end.解題步驟：首先，此題給出了關(guān)鍵而具