《算法案例》試題庫

《算法案例》試題庫總分：217分考試時間：分鐘學校__________班別__________姓名__________分數__________題號一總分得分一、單選類（共75分）1.在秦九韶算法中用到的一種方法是().A.消元B.遞推C.回代D.迭代2.用輾轉相除法求204與85的最大公約數時，需要做除法的次數是()。A.1B.2C.3D.43.用更相減損之術求38和33的最大公約數是().A.38B.23C.1D.24.等值算法(更相減損之術)的理論依據是().A.每次操作所得的兩數和前兩數具有相同的最小公倍數B.每次操作所得的兩數和前兩數具有相同的最大公約數C.每次操作所得的兩數和前兩數的最小公倍數不同D.每次操作所得的兩數和前兩數的最大公約數不同5.用輾轉相除法求294和84的最大公約數時，需要做除法的次數是().A.1B.2C.3D.46.用秦九韶算法計算多項式f(x)＝12＋35x?8x2＋79x3＋6x4＋5x5＋3x6,在x＝?4的值時,v3的值為().A.?845B.220C.?57D.347.用秦九韶算法計算多項式f(x)＝3x6＋4x5＋5x4＋6x3＋7x2＋8x＋1在x＝的值時，需要做乘法和加法的次數分別是()。A.6，6B.5，6C.4，5D.5，58.用秦九韶算法計算多項式f(x)＝x5＋2x4＋3x3＋4x2＋5x＋6，當x＝?2時的值等于()。A.-10B.-32C.-12D.89.567與405的最小公倍數為()。A.567×405B.81×405C.567×405÷81D.81×56710.已知一個k進制的數132與十進制的數30相等,那么k等于()。A.7或4B.-7 C.4D.以上都不對11.如果用輾轉相除法求168與72的最大公約數，要做n次除法運算,那么n的值為()。 A.2B.3C.4D.512.利用秦九韶算法求，x=2時的值時，下列說法正確的是（）。A.先求1+2×2B.先求6×2+5,第二步求2×(6×2+5)C.D.以上都不對13.4830與3289的最大公約數是(). A.13B.35C.12D.2314.225與135的最大公約數是(). A.5B.9C.15D.4515.已知,應用秦九韻算法計算x=3時的值時,v3的值為().A.27B.11C.109D.4516.用短除法計算459和357的最大公約數是（）.A.3B.9C.17D.5117.當x=2時，下面的程序段結果是()。 A.25B.22C.24D.2618.二進制數10111轉化為五進制數是()。A.41B.25C.21D.4319.三位七進制的數表示的最大的十進制的數是（）。A.322B.332C.342D.35220.以下給出的各數中不可能是八進制數的是().A.312B.10110C.82D.745721.下列各數中最小的數是().A.B.C.D.22.將389化成四進位制數的末位是().A.1B.2C.3D.023.在循環(huán)語句的一般形式中有“untilA”,其中A是()A.循環(huán)變量B.循環(huán)體C.終止條件D.終止條件為真24.計算機中常用16進制，采用數字0～9和字母A～F共16個計數符號與10進制得對應關系如下表： 例如用16進制表示D+E＝1B，則A×B=()A.6EB.7CC.5FD.B025.用“輾轉相除法”求得459和359的最大公約數是（）A.3B.9C.17D.5126.用秦九韶算法求多項式,當時的值的過程中，做的乘法和加法次數分別為()A.4，5B.5，4C.5，5D.6，527.用秦九韶算法和直接算法求當時的值,做的乘法次數分別為().A.6,20B.7,20C.7,21D.6,2128.用秦九韶算法在計算時,要用到的乘法和加法的次數分別為()A.4,3B.6,4C.4,4D.3,429.把89化成五進制數的末位數字為（）A.1B.2C.3D.430.下面程序執(zhí)行后輸出的結果是（） A.-1B.0C.1D.2題號一總分得分二、填空類（共37分）1.用秦九韶算法求多項式f(x)＝12?8x2＋6x4＋5x5＋3x6在x＝?4的值時，v1的值為_________．2.三個數72，120，168的最大公約數是_________．3.用秦九韶算法計算多項式f(x)＝3x6＋2x5＋4x4＋5x3＋7x2＋8x＋1在x＝的值時，需做乘法和加法的次數分別是_________、_________．4.用輾轉相除法求242與154的最大公約數是_________.5.用輾轉相除法可以求兩個數的最大公約數,則1248和954的最大公約數是_________。6.完成下列進位制之間的轉化. ＝_________ 7.5280和2155的最大公約數是_________8.用輾轉相除法求出153和119的最大公約數是_________.9.三個數72,120,168的最大公約數是_________10.2183和1947的最大公約數是_________11.下列各數中最小的數是_________12.將二進制數化為八進制數，結果為_________13.將二進制數化為十進制結果為_________；再將該數化為八進制數,結果為_________14.若六進數化為十進數為12710,則_________,把12710化為八進數為_________15.完成下列進位制之間的轉化. ＝_________＝_________ 16.完成下列進位制之間的轉化. ＝_________＝_________ 17.完成下列進位制之間的轉化. ＝_________ 18._________19.把求的程序補充完整 _________“n=”，n i=1 s=1 _________i<=n s=s*i i=i+1 _________ PRINTs END20.把程序框圖補充完整： （1）_________（2）_________ 21.右圖給出的是計算的值的一個流程圖，其中判斷框內應填入的條件是_________ 題號一總分得分三、簡答類（共105分）1.用輾轉相除法求840與1785的最大公約數2.用更相減損術求612與468的最大公約數3.試設計求兩個正整數m,n的最大公約數的程序.4.輸入3個數,輸出其中最大的公約數,編程序完成上述功能.5.我國《算經十書》之一《孫子算經》中有這樣一個問題：“今有物不知其數，三三數之剩二，五五數之剩三，七七數之剩二.問物幾何？答曰：二十三.”你能用程序解決這個問題嗎？6.我國古代數學家張邱建編《張邱建算經》中記有有趣的數學問題：“今有雞翁一，值錢五；雞母一，值錢三；雞雛三，值錢一凡百錢，買雞百只，問雞翁、母、雛各幾何？”你能用程序解決這個問題嗎？7.用秦九韶算法計算函數當時的函數值。8.求多項式當的值.9.已知,求r.10.用秦九韶算法計算函數在時的函數值11.將轉化為十進制的數；12.將轉化為二進制的數；13.用冒泡排序法將下列各數排成一列：8，6，3，18，21，67，54.并寫出各趟的最后結果及各趟完成交換的次數.14.用秦九韶算法寫出求在x=?時的值的過程.15.利用秦九韶算法求多項式在的值，寫出詳細步驟。16.已知n次多項式,如果在一種算法中，計算（k＝2，3，4，…，n）的值需要k?1次乘法，計算的值需要9次運算（6次乘法，3次加法），那么計算的值需要多少次運算？17.已知n次多項式,如果在一種算法中，計算（k＝2，3，4，…，n）的值需要k?1次乘法，若采取秦九韶算法：（k＝0，1，2，…，n?1），計算的值只需6次運算，那么計算的值共需要多少次運算？18.已知n次多項式,如果在一種算法中，計算（k＝2，3，4，…，n）的值需要k?1次乘法，若采取秦九韶算法，設ai=i+1，i=0，1，…，n，求（2）（寫出采取秦九韶算法的計算過程）19.計算，寫出算法的程序.20.計算1＋4＋7＋...＋301，寫出算法的程序21.我國古代數學家張邱建編《張邱建算經》中記有有趣的數學問題：“今有雞翁一，值錢五；雞母一，值錢三；雞雛三，值錢一凡百錢，買雞百只，問雞翁、母、雛各幾何？”你能用程序解決這個問題嗎？參考答案:一、單選類（共75分）1.B2.C3.C4.B5.B6.C7.A8.C9.C10.C11.A12.B13.D14.D15.D16.D17.D18.D19.C20.C21.A22.A23.C24.A25.D26.C27.D28.C29.D30.B二、填空類（共37分）1.-7 2.24 3.(1)6 (1)六 (2)6 (2)六 4.22 5.6 6.185 7.5 8.17 9.24 10.59 11. 12.4 13.(1) (2) 14.(1)4 (2) 15.(1)89 (2)324 16.(1)69 (2)1000101 17.82 18.75 19.(1)INPUT (2)WHILE (3)WEND 20.(1)i＜＝50 (2)p＝p＋i 21.i＞10 三、簡答類（共105分）1.105 2.36 3.用輾轉相除法設計程序如下： Input“m=”;m Input“n=”;n IfmMODn=nthen n=x endifr=mMODn whiler<>0 r=mMODn m=n n=r wend printm end 4.解： INPUTm,n,k r=mMODn WHILEr<>0 m=n n=r r=mMODn WEND r=kMODn WHILEr<>0 k=n n=r r=kMODn WEND PRINTn END 5.設物共m個，被3，5，7除所得的商分別為x、y、z， 則這個問題相當于求不定方程的正整數解. m應同時滿足下列三個條件： （1）mMOD3＝2 （2）mMOD5＝3； （3）mMOD7＝2. 因此，可以讓m從2開始檢驗，若3個條件中有任何一個不成立，則m遞增1，一直到m同時滿足三個條件為止. 程序： m＝2 f＝0 WHILEf＝0 IFmMOD3＝2ANDmMOD5＝3 ANDmMOD7＝2THEN PRINT“物體的個數為：”；m f＝1 ELSE m＝m＋1 ENDIF WEND END 6.設雞翁、母、雛各x、y、z只，則 由②，得z＝100?x?y，③ ③代入①，得5x＋3y＋＝100，7x＋4y＝100.④ 求方程④的解，可由程序解之. 程序： x＝1 y＝1 WHILEx＜＝14 WHILEy＜＝25 IF7*x＋4*y＝100 THEN z＝100?x?y PRINT“雞翁、母、雛的個數別為：”；x，y，z ENDIF y＝y(tǒng)＋1 WEND x＝x＋1 y＝1 WENDEND （法二）實際上，該題可以不對方程組進行化簡，通過設置多重循環(huán)的方式得以實現.由①、②可得x最大值為20，y最大值為33，z最大值為100，且z為3的倍數. 程序如下： x＝1 y＝1 z＝3 WHILEx＜＝20 WHILEy＜＝33 WHILEz＜＝100 IF5*x＋3*y＋z/3＝100AND x＋y＋z＝100THEN PRINT“雞翁、母、雛的個數分別為：”；x、y、z ENDIFz＝z＋3 WEND y＝y(tǒng)＋1 z＝3 WEND x＝x＋1 y＝1 WEND END 7.254 8.21324 9.∵ ∴ ∴或（舍去） ∴ 10.解： 即 11. 12. 13.每一趟都從頭開始，兩個兩個地比較，若前者小，則兩數位置不變；否則，調整這兩個數的位置.解： 第一趟的結果是：63818215467完成3次交換. 第二趟的結果是：36818215467完成1次交換. 第三趟交換次數為0，說明已排好次序，即36818215467. 14.先把函數整理成 按照從內向外的順序依次進行. 15. 16.（n＋3）次 17.2n 18. 19.i＝1 S＝1 WHILEi＜＝63 S＝s＋2^i i＝i＋1 WEND PRINTs END 或 i＝1 S＝1 DOS＝s＋2^i i＝i＋1 LOOPUNTILi＞63 PRINTs END 20.i＝1 S＝0 WHILEi＜＝101 S＝s＋i i＝i＋3 WEND PRINTs END 或者是: i＝1 S＝0 DOS＝s＋3 i＝i＋1 LOOPUNTILi＞101 PRINTs END 21.設雞翁、母、雛各x、y、z只， 則 由②，得z＝100?x?y，③ ③代入①，得5x＋3y＋＝100，7x＋4y＝100.④ 求方程④的解，可由程序解之. 程序： x＝1 y＝1 WHILEx＜＝14 WHILEy＜＝25 IF7*x＋4*y＝100 THEN z＝100?x?y PRINT“雞翁、母、雛的個數別為：”；x，y，z END IFy＝y(tǒng)＋1 WENDx＝x＋1 y＝1 WEND END （法二）實際上，該題可以不對方程組進行化簡，通過設置多重循環(huán)的方式得以實現.由①、②可得x最大值為20，y最大值為33，z最大值為100，且z為3的倍數. 程序如下： x＝1 y＝1 z＝3 WHILEx＜＝20 WHILEy＜＝33 WHILEz＜＝100 IF5*x＋3*y＋z/3＝100 AND x＋y＋z＝100THEN PRINT“雞翁、母、雛的個數分別為：”；x、y、z ENDIF z＝z＋3 WEND y＝y(tǒng)＋1 z＝3 WEND x＝x＋1 y＝1 WEND END 解析:一、單選類（共75分）1.遞推是在一系列數中已知第一個數，則其后的每一個數都可由前面的數求出．2.用輾轉相除法可得204÷85＝2……34，85÷34＝2……17，34÷17＝2，此時可以判斷204與85的最大公約數是17，做了3次除法得出結果．故選C．3.∵(38，33)→(5，33)→(5，28)→(5，23)→(5，18)→(5，13)→(5，8)→(5，3)→(2，3)→(2，1)→(1，1)， ∴1是所求的最大公約數．4.無解析5.294＝84×3＋42，84＝42×2＋0．因此選B．6.由遞推公式知v1＝3×(?4)＋5＝?7，v2＝(?4)×(?7)＋6＝34，v3＝(?4)×34＋79＝ ?57，故選C．7.乘法、加法的次數與最高次的指數相等．f(x)＝3x6＋4x5＋5x4＋6x3＋7x2＋8x＋1＝(3x＋4)x5＋5x4＋6x3＋7x2＋8x＋1＝((3x＋4)x＋5)x4＋6x3＋7x2＋8x＋1＝(((3x＋4)x＋5)x＋6)x3＋7x2＋8x＋1＝((((3x＋4)x＋5)x＋6)x＋7)x2＋8x＋1＝(((((3x＋4)x＋5)x＋6)x＋7)x＋8)x＋1．顯然進行了6次乘法，6次加法．故選A．8.將f(x)改寫為f(x)＝((((x＋2)x＋3)x