1、算 法 與 程 序 設(shè) 計(jì)算法的程序?qū)崿F(xiàn)浙江考試標(biāo)準(zhǔn)考試內(nèi)容考核要求考試屬性1.枚舉算法及程序?qū)崿F(xiàn)c加試2.解析算法及程序?qū)崿F(xiàn)c3.排序算法及程序?qū)崿F(xiàn)(1)冒泡排序(2)選擇排序c4.查找算法及程序?qū)崿F(xiàn)(1)順序查找(2)對(duì)分查找c5.遞歸算法a6.VB訪問(wèn)Access數(shù)據(jù)庫(kù)(1)通過(guò)ADO對(duì)象連接數(shù)據(jù)庫(kù)(2)通過(guò)Recordset對(duì)象獲取數(shù)據(jù)表中的數(shù)據(jù)a一、枚舉算法1枚舉算法的基本思想根據(jù)問(wèn)題的本身性質(zhì)，_出該問(wèn)題_可能的情況，并根據(jù)題目的條件逐一分析、判斷是否滿足條件，若滿足，則它是問(wèn)題的一個(gè)解，從而挑選出符合條件的_。2枚舉算法解題的基本思路(1)確定枚舉對(duì)象、枚舉范圍和判斷條件。(2)

2、一一列舉可能的解，驗(yàn)證是否是問(wèn)題的解。3枚舉算法程序?qū)崿F(xiàn)的三要素。(1)枚舉解時(shí)，既不能遺漏任何一個(gè)真正解，又不能有重復(fù)，用循環(huán)語(yǔ)句實(shí)現(xiàn)。(2)條件判斷時(shí)，利用問(wèn)題提供的約束條件篩選、判斷解的正確性，用分支語(yǔ)句實(shí)現(xiàn)。(3)求解形式一般以輸出解的內(nèi)容或進(jìn)行與解有關(guān)的其他計(jì)算。二、解析算法1解析算法的基本思想用解析的方法找出表示問(wèn)題的前提條件與所求結(jié)果之間關(guān)系的_，并通過(guò)表達(dá)式的計(jì)算來(lái)實(shí)現(xiàn)問(wèn)題的求解。2解析算法解題的基本思路(1)建立正確的數(shù)學(xué)模型，即得出正確的數(shù)學(xué)表達(dá)式。(2)保證計(jì)算過(guò)程描述的正確性。用正確合理的VB變量、表達(dá)式來(lái)表示已經(jīng)得出的數(shù)學(xué)表達(dá)式。3解析算法程序?qū)崿F(xiàn)的步驟(1)運(yùn)用解析

3、算法分析問(wèn)題，尋找問(wèn)題中各要素之間的關(guān)系，用_表示它們的關(guān)系。(2)寫(xiě)出解決問(wèn)題的解析步驟，編寫(xiě)程序?qū)崿F(xiàn)，通過(guò)運(yùn)行程序求得問(wèn)題的正確解。三、冒泡排序1冒泡排序基本思想是在待排序的數(shù)據(jù)中，先找到最小(大)的數(shù)據(jù)將它放到最前面，再?gòu)牡诙€(gè)數(shù)據(jù)開(kāi)始，找到第二小(大)的數(shù)據(jù)將它放到第二個(gè)位置，以此類推，直到只剩下最后一個(gè)數(shù)據(jù)為止。2冒泡排序的實(shí)現(xiàn)要素(1)將數(shù)據(jù)存放在數(shù)組中，確定數(shù)組的名稱、元素個(gè)數(shù)。(2)比較與交換_進(jìn)行，在冒泡排序中，第i遍排序比較ni次，最多交換ni次。(3)強(qiáng)調(diào)_元素的比較和交換。3冒泡排序的程序?qū)崿F(xiàn)(1)從后向前實(shí)現(xiàn)冒泡排序從后向前實(shí)現(xiàn)冒泡排序的程序結(jié)構(gòu)：(2)從前向后實(shí)現(xiàn)冒

4、泡排序從前向后實(shí)現(xiàn)冒泡排序的程序結(jié)構(gòu)：【自我校對(duì)】一一列舉所有所有解數(shù)學(xué)表達(dá)式數(shù)學(xué)表達(dá)式同時(shí)相鄰四、選擇排序1選擇排序基本思想是在所有的記錄中選出最小(大)的數(shù)據(jù)，把它與第一個(gè)數(shù)據(jù)交換，然后在其余的記錄中再選出最小(大)的數(shù)據(jù)與第二個(gè)數(shù)據(jù)交換，依次類推，直至所有數(shù)據(jù)排序完成。2選擇排序的實(shí)現(xiàn)要素(1)將數(shù)據(jù)存放在數(shù)組中，確定數(shù)組的名稱、元素個(gè)數(shù)。(2)強(qiáng)調(diào)_。在第i遍排序中，比較ni次，最多交換1次。(3)變量k僅用于記錄需要尋找的最值(最大值或最小值)位置，比較的是d(j)與d(k)，交換的是_。3選擇排序的程序?qū)崿F(xiàn)(1)從前向后實(shí)現(xiàn)選擇排序從前向后實(shí)現(xiàn)選擇排序的程序結(jié)構(gòu)(升序排序)：(2)

5、從后向前實(shí)現(xiàn)選擇排序從后向前實(shí)現(xiàn)選擇排序的程序結(jié)構(gòu)(升序排序)：【答案】先比較，再交換d(k)和d(i)五查找算法_的基本思想是從第一個(gè)數(shù)據(jù)開(kāi)始，按數(shù)據(jù)的順序逐個(gè)將數(shù)據(jù)與給定的值進(jìn)行比較，若某個(gè)數(shù)據(jù)和給定值相等，則查找成功，找到所查數(shù)據(jù)的位置；反之，查找不成功。_的基本思想是在有序的數(shù)據(jù)列中，首先將要查找的數(shù)據(jù)與有序數(shù)組內(nèi)處于中間位置的數(shù)據(jù)進(jìn)行比較，如果兩者相等，則查找成功；否則根據(jù)數(shù)組元素的有序性，就可確定該數(shù)據(jù)應(yīng)該在數(shù)組的前半部分還是后半部分繼續(xù)進(jìn)行查找；在新確定的范圍內(nèi)，繼續(xù)按上述方法進(jìn)行查找，直到找到要查找的數(shù)據(jù)，使查找成功，或直到子表不存在，查找不成功。【答案】順序查找對(duì)分查找六、遞

6、歸算法函數(shù)或過(guò)程調(diào)用它本身，稱為_(kāi)。_的基本思想是把規(guī)模較大的、較難解決的問(wèn)題變成規(guī)模較小的、容易解決的同一問(wèn)題，規(guī)模較小的問(wèn)題又變成規(guī)模更小的問(wèn)題，當(dāng)問(wèn)題小到一定程度時(shí)，可以直接得出它的解，從而得到原來(lái)問(wèn)題的解。即采用“大事化小，小事化了”的基本思想。遞歸算法必須具備的條件：每一步驟解決問(wèn)題的方法要一致。有邊界條件。【答案】遞歸遞歸算法七、VB訪問(wèn)數(shù)據(jù)庫(kù)1通過(guò)ADO連接數(shù)據(jù)庫(kù)ADO是微軟公司提供的一種應(yīng)用程序訪問(wèn)數(shù)據(jù)庫(kù)的編程接口。該接口包含了多個(gè)對(duì)象，其中Connection對(duì)象用于與數(shù)據(jù)庫(kù)建立連接，在建立連接后，可通過(guò)Recordset對(duì)象獲取數(shù)據(jù)表中的數(shù)據(jù)。在用Connection建立與

7、數(shù)據(jù)庫(kù)的連接時(shí)，需要設(shè)置ConnectionString屬性的值(即連接字符串)，以指定連接數(shù)據(jù)庫(kù)所用的驅(qū)動(dòng)程序、數(shù)據(jù)源名稱、用戶名和密碼等。Connection對(duì)象具有Open、Close等方法，其中_方法用于打開(kāi)到數(shù)據(jù)源的連接，_方法用于關(guān)閉連接。2通過(guò)Recordset對(duì)象獲取數(shù)據(jù)庫(kù)中的數(shù)據(jù)，步驟如下：(右邊是對(duì)應(yīng)的代碼)：說(shuō)明：myrecord是定義的Recordset對(duì)象的名字。mytable是數(shù)據(jù)庫(kù)中某張表的名稱。EOF屬性：若當(dāng)前記錄的位置在最后的記錄之后，則返回True，否則返回False。MoveNext方法：指針移到下一條記錄。這段代碼應(yīng)該在連接數(shù)據(jù)庫(kù)后，關(guān)閉數(shù)據(jù)庫(kù)前。【答

8、案】OpenClose1(2012年6月浙江會(huì)考)計(jì)算三角形面積的算法如下：輸入三角形三邊長(zhǎng)a，b，c計(jì)算半周長(zhǎng)p(abc)/2計(jì)算三角形面積sSqr(p*(pa)*(pb)*(pc)輸出面積s上述算法屬于()A排序算法B解析算法C枚舉算法D查找算法B本題主要考查各種算法的基本思想。本題中算法的基本思想是通過(guò)數(shù)學(xué)表達(dá)式的計(jì)算來(lái)解決問(wèn)題，符合解析算法的基本思想。2(2014年3月浙江學(xué)考)運(yùn)行下列VB程序，在文本框Text1中輸入28，界面如圖所示。Private Sub Command1_Click( )Dim s As SingleDim v As SingleDim t As Single

9、s0vl0t Val ( Text 1.Text )ssv*tLabel1 .Caption Str(s)End Sub單擊“計(jì)算”按鈕Command1后，標(biāo)簽Label1中顯示的內(nèi)容是(1)_。該程序采用了(2)_(填：解析/排序/查找)算法。【解析】本題主要考查各種算法的基本思想特點(diǎn)及程序閱讀能力。s的值通過(guò)ssv*t計(jì)算得到，s的初值是0，將v10，t28(從文本框中輸入)代入，得到s280，符合解析算法的基本思想。【答案】(1)280(2)解析一、冒泡排序與選擇排序?qū)Ρ让芭菖判蚺c選擇排序冒泡排序選擇排序思想方法邊比較邊交換先選出最大值或最小值，再交換核心代碼For i1 To n1Fo

10、r i1 To n1For jn To i1 Step 1If a(j)<a(j1) Thentempa(j1)a(j1) a(j)a (j) tempEnd IfNext jNext ikiFor ji1 To nIf a(j) <a(k) ThenkjNext jIf k<>i Thentemp a(i)a(i) a(k)a (k)tempEnd IfNext i相同點(diǎn)n個(gè)數(shù)都需要n1遍排序，其中變量i控制排序的遍數(shù)比較的次數(shù)一樣多，都是(n1)(n2)321次最好的情況下，交換的次數(shù)一樣，都是0次不同點(diǎn)邊比較邊交換，最壞的情況下交換的次數(shù)是(n1)(n2)321次

11、先選擇再交換，最壞的情況下交換的次數(shù)是n1次如何區(qū)分因?yàn)槭窍噜弮蓴?shù)比較，因此代碼中有類似“a(j)和a(j1)”比較的條件表達(dá)式因?yàn)槭窍冗x出最大值或最小值，再交換，因此代碼中有尋找最大值或最小值的代碼，并且用變量(如k)來(lái)記錄該值所在的位置。如果ki則交換二、枚舉算法與順序查找枚舉算法順序查找思想方法一一列舉所有可能解并驗(yàn)證數(shù)據(jù)源從頭到尾逐個(gè)比較核心代碼For(列舉所有可能的解)If 可能解是正確解then 輸出該解nextFor(從數(shù)組的第一個(gè)元素到最后一個(gè)元素)If 當(dāng)前元素關(guān)鍵詞then 輸出該位置next區(qū)分方法For語(yǔ)句用于列舉所有可能的解，即解的范圍For 語(yǔ)句用于訪問(wèn)整個(gè)查找源的

12、數(shù)據(jù)，一般是從開(kāi)始位置到結(jié)束位置If語(yǔ)句是驗(yàn)證當(dāng)前列舉的可能解是否是正確解If語(yǔ)句用于判斷當(dāng)前訪問(wèn)的元素是不是等于關(guān)鍵詞正確解可能有多個(gè)，因此找到一個(gè)正確解后，循環(huán)繼續(xù)，直到所有可能的解都被檢驗(yàn)過(guò)一旦某個(gè)位置的數(shù)據(jù)等于關(guān)鍵詞，則記錄該位置，并且查找任務(wù)結(jié)束，通常用語(yǔ)句exit for退出循環(huán)不管是枚舉算法還是順序查找，都可以寫(xiě)成For循環(huán)語(yǔ)句，區(qū)分的方法是要分析問(wèn)題的本質(zhì)：for語(yǔ)句是為了一一列舉所有可能的解還是從頭到尾逐個(gè)訪問(wèn)數(shù)據(jù)源中的數(shù)據(jù)；if語(yǔ)句是檢驗(yàn)可能解還是比較關(guān)鍵詞。三、對(duì)分查找對(duì)分查找的基本思想：查找的數(shù)據(jù)源a(1)到a(n)是有序的(如從小到大排序)，查找的關(guān)鍵詞是key，則第

13、一次查找的范圍是1，n，如果中間位置為m，則mfix(1n)/2)。如果keya(m)，則查找成功；如果key<a(m)，則下一次查找的范圍變?yōu)?，m1；如果keya(m)，則下一次查找的范圍變?yōu)閙1，n。在新確定的范圍內(nèi)，繼續(xù)按上述方法進(jìn)行查找，直到找到要查找的數(shù)據(jù)，則查找成功；或直到子表不存在，則查找不成功。說(shuō)明：對(duì)分查找的前提是被查找的數(shù)據(jù)必須是有序的。對(duì)分查找每次訪問(wèn)的是當(dāng)前查找范圍里中間位置上的數(shù)據(jù)，并根據(jù)該數(shù)據(jù)與關(guān)鍵詞的大小關(guān)系，將下一次的查找范圍縮小一半。規(guī)模為n個(gè)數(shù)的數(shù)據(jù)源，使用對(duì)分查找時(shí)，最多經(jīng)過(guò)Int(log2n)1次查找。17位學(xué)生的身高(單位：cm)從高到低依次為

14、：178,177,175,172,170,165,162。用對(duì)分查找法找到178的過(guò)程中，依次被訪問(wèn)到的數(shù)據(jù)是()A178B172,175,178C172,177,178D172,175,177,178C本題主要考查對(duì)對(duì)分查找算法基本思想的理解。將7個(gè)數(shù)據(jù)從1到7進(jìn)行編號(hào)。第一次訪問(wèn)到的數(shù)據(jù)是第4個(gè)，即172(中間位置mFix(17)/2)4)，178172，因此下一次查找的范圍是前半部分，即第1個(gè)到第3個(gè)。因此第二次訪問(wèn)的數(shù)據(jù)應(yīng)該是第2個(gè)，即177(中間位置mFix(13)/2)2)，178177，因此下一次查找的范圍是前半部分，即第1個(gè)，因此第三次訪問(wèn)的數(shù)據(jù)是第1個(gè)，即178。2某校通過(guò)政

15、府招投標(biāo)中心采購(gòu)一套多媒體教學(xué)設(shè)備，有5家單位參加競(jìng)標(biāo)，競(jìng)標(biāo)價(jià)分別為19萬(wàn)、15萬(wàn)、21萬(wàn)、13萬(wàn)、12萬(wàn)元人民幣。若采用選擇排序算法對(duì)標(biāo)價(jià)從大到小排序，需要進(jìn)行數(shù)據(jù)互換的次數(shù)是()A1B2C3D4B原始數(shù)據(jù)19、15、21、13、12，第一遍排序19與21互換，得到21,15,19,13,12；第二遍排序15與19互換，得到21,19,15,13,12；第三遍排序與第四遍排序都不需要數(shù)據(jù)互換。因此總共是2次數(shù)據(jù)互換。3實(shí)現(xiàn)某排序算法的部分VB程序如下：For i1 To 6kiFor ji1 To 7If a(j)<a(k) Then kjNext jIf i<>k The

16、nta(i)：a(i)a(k)a(k)tEnd IfNext i在排序過(guò)程中，經(jīng)過(guò)某一遍排序“加工”后，數(shù)組元素a(1)到a(7)的數(shù)據(jù)依次為“10,41,75,12,63,11,85”。則下一遍排序“加工”后數(shù)組元素a(1)到a(7)的數(shù)據(jù)依次是()A10,11,41,75,12,63,85B10,11,75,12,63,41,85C10,11,12,75,63,41,85D10,11,12,41,63,75,85B本題主要考查選擇排序算法的代碼特點(diǎn)。選擇排序的基本操作是先找出最小數(shù)或最大數(shù)所在的位置，記錄在一個(gè)變量中，再根據(jù)需要進(jìn)行數(shù)據(jù)交換，因此代碼中會(huì)出現(xiàn)“kj”以及“If ik”的代碼

17、，根據(jù)代碼特點(diǎn)，可確定本題的排序算法是選擇排序。一旦確定是選擇排序，接著就可以用選擇排序的思想方法來(lái)對(duì)數(shù)據(jù)進(jìn)行排序。根據(jù)第一遍排序結(jié)果可得知排序的結(jié)果是數(shù)據(jù)從小到大排，選擇排序的基本思想是從所有的記錄中選出最小(從小到大排)的數(shù)據(jù)，把它與第一個(gè)數(shù)據(jù)交換，然后在其余的記錄中再選出最小的數(shù)據(jù)與第二個(gè)數(shù)據(jù)交換。以此類推，直至所有數(shù)據(jù)排序完成。因此“10,41,75,12,63,11,85”的下一遍選擇排序的結(jié)果應(yīng)該是：“10,11,75,12,63,41,85”。4有如下對(duì)a(1)到a(6)進(jìn)行升序排序的程序片段：For i1 To 5kiFor ji1 To 6_Next jIf k<>

18、;i Then ta(i)：a(i)a(k)：a(k)tNext i劃線部分應(yīng)填()AIf a(j)<a(k)Then kjBIf a(j)<a(k)Then kiCIf a(j)>a(k)Then kjDIf a(j)>a(k)Then ki【解析】本程序段為選擇排序(按升序排序)，每趟比較找出最小值，存入a(k)中，k記錄最小值編號(hào)j。【答案】A5通過(guò)編程尋找3位的水仙花數(shù)。什么是水仙花數(shù)：水仙花數(shù)是指一個(gè)n位數(shù)(n3)，它的每個(gè)位上的數(shù)字的n次冪之和等于它本身。例如153是水仙花數(shù)，因?yàn)?35333153。解決此問(wèn)題的Visual Basic程序如下，程序界面如圖所示，在列表框List1中輸出結(jié)果。在和劃線處，填入合適的語(yǔ)句或表達(dá)式，把程序補(bǔ)充完整。Private Sub Command1_Click()Dim i As IntegerDim a，b，c As IntegerFor _ai100bi10 Mod 10ci Mod 10If_The