信息學(xué)奧賽：算法基礎(chǔ)綜合測試

1、信息學(xué)奧賽：算法基礎(chǔ)綜合測試一、單選題（共13分，前6題每題1.5分，后2題每題2分）1、下列關(guān)于算法的描述正確的是（）。 A. 算法中有待執(zhí)行的運算和操作必須是相當(dāng)基本的(正確答案)B. 一個算法至少有一個輸入和一個輸出C. 算法并不需要每一個步驟都確切地定義D. 一個算法可以沒有結(jié)束2、下列關(guān)于算法的描述正確的是（） A. 算法只能用自然語言來描述B. 算法只能用流程圖或偽代碼來表示C. 同一問題可以有不同的算法(正確答案)D. 同一問題的算法不同，結(jié)果必然不同3、下列排序算法中，（）不是基于比較的排序。 A. 冒泡排序B.桶排序(正確答案)C. 快速排序D. 選擇排序4、“你打開面前這扇

2、門，看到屋里面還有一扇門。你走過去，發(fā)現(xiàn)手中的鑰匙還可以打開它，你推開門，發(fā)現(xiàn)里面還有一扇門，你繼續(xù)打開它。若干次之后，你打開面前的門后，發(fā)現(xiàn)只有一間屋子，沒有門了。然后，你開始原路返回，每走回一間屋子，你數(shù)一次，走到入口的時候，你可以回答出你到底用這你把鑰匙打開了幾扇門?！边@一表述主要體現(xiàn)了( )的思想。 A. 枚舉B. 分治C. 遞歸(正確答案)D. 貪心5、關(guān)于遞歸算法，下列說法不正確的是( )。 A. 一個過程或函數(shù)在其定義中有直接或間接調(diào)用自身，稱為遞歸B. 遞歸算法的程序結(jié)構(gòu)往往更簡潔C. 遞歸可能會消耗大量的內(nèi)存空間，程序執(zhí)行慢，甚至出現(xiàn)棧溢出等問題D. 若遞歸算法執(zhí)行效果慢，可

3、以采用“時間換空間”的思路，使用遞推算法改進(jìn)(正確答案)6、下列關(guān)于高精度算法的說法中，錯誤的是( )。 A. 高精度算法是用計算機對于超大數(shù)據(jù)的一種模擬加，減，乘，除，乘方，階乘，開方等運算的算法，即高精度算法就是能處理高精度數(shù)各種運算的算法。B. 高精度算法中，參與運算的數(shù)(加數(shù)，被減數(shù)，減數(shù)，因數(shù))范圍大大超出了標(biāo)準(zhǔn)數(shù)據(jù)類型(整型，實型)能表示范圍的運算。C. 高精度數(shù)一般采用使用一個數(shù)組來表示，一般采用字符串形式讀入并采用正序的方式進(jìn)行存儲。(正確答案)D. 高精度算法的內(nèi)在實質(zhì)是模擬算法，用計算機來模擬人用筆的計算過程。7、（漢諾塔移動次數(shù)）在圣廟里，一塊黃銅板上插著三根寶石柱。神在

4、創(chuàng)造世界的時候，在其中一根柱上從下到上地穿好了由大到小的64片金片，這就是所謂的漢諾塔。不論白天黑夜，總有一個僧侶在按照下面的法則移動這些金片：一次只移動一片，不管在哪根針上，小片必須在大片上面。僧侶們預(yù)言，當(dāng)所有的金片都從神穿好的那根柱上移到另外一根柱上時，世界就將在一聲霹靂中消滅，而梵塔、廟宇和眾生也都將同歸于盡。不管傳說是否可信，我們現(xiàn)在要解決的是，假設(shè)初始柱A上從下到上地穿好了由大到小的n片金片，一次只能移動一片，且必須滿足小片在大片之上。問最少移動（ ）次后所有的金片都從初始穿好的那根柱上移到另外一根柱C上。A. 2n-1 B. 2n-1 C. 2n+1 D. 2n+1 A. 2的n

5、次方-1(正確答案)B. 2的n-1次方C. 2的n+1次方D. 2的n次方+18、下面這段高精度加法程序計算a+b的值并存儲在a中，其中缺了3個空，依次填入選項（ ）可以補全程序。甲：ai=(ai+bi)%10 乙：ai+1=ai+1+(ai+bi)/10 丙：a0=k+1void plus(int a,int b)  int i,k;  if(a0>b0) k=a0;  else k=b0;  for(i=1;i<=k;i+)             

6、60;             if(ak+1>0)            else a0=k; A. 甲乙丙B. 乙甲丙(正確答案)C. 丙乙甲D. 丙甲乙二、閱讀程序，完成各題（共75分，30小題每題2.5分）1、(1)這段程序是一個( )算法。 A. 快速排序B. 歸并排序C. 冒泡排序(正確答案)D. 選擇排序(2)若輸入n=5，再輸入1 3 5 2 4，則程序第9行將會執(zhí)行( )次比較。 A. 10(正確答案)B. 5C. 3D. 7(3)

7、若輸入n=4，以下輸入( )會使得程序第10行執(zhí)行的次數(shù)最多。 A. 1 2 3 4B. 4 3 2 1(正確答案)C. 4 2 3 1D. 1 4 3 2(4)若輸入n=3，再輸入3 1 3，則程序第10行會執(zhí)行( )次。 A. 1(正確答案)B. 2C. 3D. 4(5)若將第7行"i<n"修改為"i<=n-1"，程序( )。 A. i的取值范圍少1B. 不能正確運行排序C. 出現(xiàn)編譯錯誤D. 能夠正確運行排序(正確答案)(6)將第10行"t=aj;aj=aj+1;aj+1=t;"修改為" t=aj+1;aj

8、+1=aj;aj=t;"。程序( )。 A. 不能夠正確執(zhí)行交換B. 仍能夠正確執(zhí)行交換(正確答案)C. 出現(xiàn)編譯錯誤D. 將從大到小進(jìn)行排序(7)將第9行"aj>aj+1"修改為"aj>=aj+1"。若輸入仍為n=3，再輸入3 1 3，則程序第10行會執(zhí)行( )次。 A. 1B. 2(正確答案)C. 3D. 4(8)將第7行"i<n"修改為"i<n-1"。若輸入n=4，再輸入4 3 2 1，則程序?qū)⑤敵? )。 A. 4 3 2 1B. 2 1 3 4(正確答案)C. 3 2 1

9、 4D. 1 2 3 4(9)將第7行"i<n"修改為"i<n-1"。若輸入n=4，再輸入1 3 2 4，則程序?qū)⑤敵? )。 A. 4 3 2 1B. 2 1 3 4C. 3 2 1 4D. 1 2 3 4(正確答案)(10)在最好情況下，第10行將執(zhí)行( )次。 A. 0(正確答案)B. 1C. nD. n(n-1)/22、(11)這段程序是一個( )算法。 A. 快速排序(正確答案)B. 歸并排序C. 冒泡排序D. 選擇排序(12)該排序算法同時也體現(xiàn)了( )思想。 A. 枚舉算法B. 查找算法C. 分治算法(正確答案)D. 貪心算法(

10、13)若輸入n=5，再輸入1 3 5 2 4，則程序?qū)敵? )。 A. 1 2 3 4 5B. 5 4 3 2 1(正確答案)C. 1 5 4 3 2D. 5 1 2 3 4(14)若將第7行"i<=j"修改為"i<j"，程序( )。 A. i的取值范圍少1B. 不能正確運行排序C. 出現(xiàn)編譯錯誤D. 能夠正確運行排序(正確答案)(15)將第10行"i<=j"修改為"i<j"，程序（ ）。 A. 將從小到大進(jìn)行排序B. 不能正確運行排序(正確答案)C. 出現(xiàn)編譯錯誤D. 能夠正確運行排序

11、(16)將第11行"t=ai;ai=aj;aj=t;"修改為"ai=t;t=aj;aj=ai;"，程序（ ）。 A. 不能夠正確執(zhí)行交換(正確答案)B. 仍能夠正確執(zhí)行交換C. 出現(xiàn)編譯錯誤D. 將從小到大進(jìn)行排序(17)將第17行"return"刪除，程序( )。 A. 將從小到大進(jìn)行排序B. 不能正確運行排序C. 出現(xiàn)編譯錯誤D. 能夠正確運行排序(正確答案)(18)在最好情況下，該排序算法將執(zhí)行( )次交換。 A. 0(正確答案)B. 1C. nD. n(n-1)/2(19)在最壞情況下，該排序算法將執(zhí)行( )次交換。 A. 0

12、B. 1C. nD. n(n-1)/2(正確答案)(20)在編程實現(xiàn)該排序算法時，該思想與以下表述( )有異曲同工之妙。 A. 道生一，一生二，二生三，三生萬物B. 吃自助餐，每次都挑最貴的一種食物吃C. 小明在思考，思考的內(nèi)容是：“小明在思考，思考的內(nèi)容是：小明在思考，思考的內(nèi)容是：”(正確答案)D. 逐一排查，查到即止3、(21)這段程序是一個( )算法。 A. 順序查找B. 二分查找(正確答案)C. 散列查找D. 枚舉(22)若輸入8 2后，再輸入2 3 5 7 11 13 17 19，則程序?qū)敵? )。 A. -1B. 0C. 1(正確答案)D. 2(23)若輸入6 3后，再輸入1

13、 3 3 3 3 5，則程序?qū)敵? )。 A. 2B. 3(正確答案)C. 4D. 5(24)若輸入6 3后，再輸入1 3 5 6 4 2，則程序?qū)敵? )。 A. -1B. 0C. 1D. 2(正確答案)(25)若輸入9 3后，再輸入1 4 7 2 5 8 3 6 9，則程序?qū)敵? )。 A. -1(正確答案)B. 1C. 4D. 7(26)若將第8行"l<=r"修改為"l<r"，程序( )。 A. r的取值范圍少1B. 不能正確運行查找(正確答案)C. 出現(xiàn)編譯錯誤D. 能夠正確運行查找(27)刪去第12行"brea

14、k"。輸入6 3后，再輸入1 2 3 4 5 6，則程序?qū)? )。 A. 輸出3B. 不能正確運行查找(正確答案)C. 出現(xiàn)編譯錯誤D. 輸出-1(28)在執(zhí)行該算法前，對數(shù)組a的要求主要是( )。 A. 數(shù)組a需要從小到大有序(正確答案)B. 數(shù)組a需要從大到小有序C. 對數(shù)組a沒有任何要求D. 不需要完全有序，但需要數(shù)組a的前半部分小于中間值，后半部分大于中間值(29)該算法還可以利用( )的思想來編寫程序。 A. 排序算法B. 遞歸算法(正確答案)C. 枚舉算法D. 貪心算法(30)與該算法思想相似的問題有( )。 A. 求所有的“水仙花數(shù)”(“水仙花數(shù)”即每位數(shù)字的立方和等于

15、該數(shù)的三位數(shù)，如153=13+53+33。)B. 青蛙跳臺階(青蛙一次可跳1或2級臺階，求青蛙跳上一個n級的臺階的跳法總數(shù)。)C. 猜數(shù)字游戲(在自然數(shù)1到n中取一個數(shù)猜，每猜一次知道猜大了或猜小了。怎么猜數(shù)最快？)(正確答案)D. 錢幣支付問題(假設(shè)不同面值紙幣的各有若干張，現(xiàn)在不考慮找零錢的支付K元，求最少紙幣張數(shù)。)三、閱讀程序?qū)懡Y(jié)果（共22分，第一題6分，第二，三題每題8分）1、#include <iostream>using namespace std;int main()  int n,x,sum=0;  cin>>n;  fo

16、r(int i=1;i<=n;i+)    sum=sum+200;    cin>>x;    sum=sum-x;    cout<<sum;  return 0;輸入：6          180 30 110 50 40 60輸出： _(答案：730)2、#include<iostream>using namespace std;int main()  const int N=6;  i

17、nt cN=;  int vN=1,5,10,20,50,100;  int i,k,m=0,cc=0;  cin>>k;  for(i=0;i<N;i+) cin>>ci;  for(i=N-1;i>=0;i-)    cc=min(k/vi,ci);    k=k-ccvi;    m+=cc;    if(k>0) m=-1;  if(m!=-1) cout<<m<<endl;  else cout<<"NO"<<endl;  retur