CSP-J 初賽模擬試卷

CSP-J初賽模擬試卷（C++語言）

一、單項選擇題1.以下與電子郵件無關(guān)的網(wǎng)絡(luò)協(xié)議是（）A.SMTPB.POP3C.MIMED.FTP(正確答案)2.二進制數(shù)11110110和00001111進行邏輯異或運算的結(jié)果是（）A.11111001(正確答案)B.00000110C.11111111D.000010013.布爾型變量占用（）個比特位。A.1B.2C.4D.8(正確答案)4.以下程序段執(zhí)行完畢后,i和s的值分別是（）

inti,s=0;

for(i=1;i<=5;i=i+2)s=s+i;A.5和9B.7和9(正確答案)C.5和7D.9和75.已知有序表(13,18,24,35,47,50,62,83,90,115,134),當(dāng)折半登找值為90的元素時,查找成功的比較次數(shù)為（）A.5B.2(正確答案)C.3D.46.數(shù)組不具有的特點是（）A.插入、刪除不需要移動元素(正確答案)B.可隨機訪問任一元素C.是一塊連續(xù)的內(nèi)存空間D.所需空間與線性長度成正比7.用冒泡排序的方法對一個長度為n的數(shù)據(jù)進行排序,平均時間復(fù)雜度為（）A.O(N·N)(正確答案)B.O(NlogN)C.O(N)D.O(NsqrtN)8.由4個節(jié)點構(gòu)成的形態(tài)不同的二叉樹有（）種。A.16B.14(正確答案)C.20D.109.以下4個數(shù)中最大的素數(shù)是（）.A.91B.89(正確答案)C.119D.9310.45和30的最小公倍數(shù)是（）A.30B.45C.90(正確答案)D.18011.深度為k的二叉樹上,最多含有（）個節(jié)點。A.2k-1B.2kC.2^k-1(正確答案)D.2^(k-1)12.字符串”abcab”本質(zhì)不同的子串個數(shù)為（）.A.12B.13(正確答案)C.14D.1513.十進制小數(shù)11.375對應(yīng)的二進制數(shù)是（）.A.1011.011(正確答案)B.1011.01C.1101.101D.1101.01114.一棵6節(jié)點二叉樹的中序遍歷為ABDGECF,先序遍歷為DBACEGF,后序遍歷（）。A.DGBEFACB.ABGEFCD(正確答案)C.GBEACFDD.ABCDEFG15.當(dāng)價格不變時,集成電路上可容納的元器件的數(shù)目,約每隔18~24個月就會增

加一倍,性能也將提升一倍。提出該規(guī)律的是（）A.圖靈B.諾貝爾C.摩爾(正確答案)D.馮·諾依曼二、閱讀程序（程序輸入不超過數(shù)組或字符串定義的范圍；判斷題正確的填√，錯誤的填×；除特殊說明外，判斷題每題1.5分，選擇題4分，共計40分）

（一）

16.若輸入123,則輸出321。（）A.正確B.錯誤(正確答案)17.若輸入12345678901223,將輸出2123456789012123456789010。（）A.正確B.錯誤(正確答案)18.該程序中，頭文件#include<iostream>可以改成#include<cstdio>。（）A.正確B.錯誤(正確答案)19.若輸入10,20,30(逗號隔開),符合程序的輸入要求。（）A.正確B.錯誤(正確答案)20.若輸入102030,輸出（）。A.201020B.201010C.201030D.2010-10(正確答案)21.若將第9行的c=b-a改成c=b,則輸入369,輸出（）。A.636B.639C.633(正確答案)D.363（二）

22.上述代碼中,若將第13行修改為INF=1<<40,則輸出結(jié)果一定不變。（）A.正確B.錯誤(正確答案)23.上述代碼中,將第20行修改為break或continue這兩種情況后,有相同的輸入,在這兩種情況下,輸出結(jié)果也一定相同。（）A.正確(正確答案)B.錯誤24.上述代碼中,將第20行修改為break后,有相同的輸入,變量c的值和未修改前一定相同。（）A.正確(正確答案)B.錯誤25.上述代碼中,將第20行修改為break后,有相同的輸入,輸出結(jié)果也一定相同。（）A.正確B.錯誤(正確答案)26.輸入為:8輸出為（）A.17B.19回車overC.19(正確答案)D.23\nover27.上述代碼中,將第6行的i<n修改為（）后功能不變,效率更高。A.i*i<=n(正確答案)B.i<n/2C.i<n/3D.i<n/4(三)

28.上述代碼實現(xiàn)了對一個長度為mxn的二維數(shù)組尋找每一行上的最小值進行求和。（）A.正確B.錯誤(正確答案)29.上述代碼如果刪除第4行,其他地方的b數(shù)組都改成a數(shù)組,那么結(jié)果不變。（）A.正確(正確答案)B.錯誤30.若輸入數(shù)據(jù)為:

44

12345678910111213141516

則輸出的結(jié)果為（）。A.28B.16C.136D.46(正確答案)31.上述代碼的時間復(fù)雜度為（）A.O(min(m,n))B.O(m*n+m*n+m+n)C.O(m*n)(正確答案)D.O(m*n+m*n)32.我們將上述算法稱為（）A.深度搜索B.廣度搜索C.動態(tài)規(guī)劃(正確答案)D.貪心33.上述代碼若刪除第4行,其他地方的b數(shù)組都改成a數(shù)組,輸入數(shù)據(jù)為,

33

123456789

則輸出的結(jié)果為（）A.20B.12C.11D.21(正確答案)三、完善程序（單選題，每小題3分，共計30分）

(一)請完善下面的程序,將1~9個數(shù)字分別填入3×3的九宮格中,第一行的三個數(shù)字組成一個三位數(shù)。要使第二行的三位數(shù)是第一行的2倍,第三行的三位數(shù)是第一行的3倍，且每個格子里的數(shù)字都不能重復(fù),現(xiàn)在要求輸出所有的填充方案,以每種方案中的第一行組成的三位數(shù)升序輸出。

輸出格式:

每一種方案輸出共三行,每行中每兩個數(shù)沒有空格,每種方案輸出后輸出一人空行。

最后一行一個數(shù)字,表示方案的總數(shù).

34.①處應(yīng)填（）A.s==n+1;(正確答案)B.s==n;C.s<n;D.s>=n;35.②處應(yīng)填（）A.t3*2==t2&&t3*3==t1B.t1*2==t2&&t2*3==t3C.t1*3==t2&&t1x2==t3D.t1*2==t2&&t1*3==t3(正確答案)36.③處應(yīng)填（）A.a[c]=i;B.a[s]=i;(正確答案)C.a[i]=s;b[c]=i;D.b[s]=1;37.④處應(yīng)填（）A.f(i+1);B.f(s+1);(正確答案)C.f(c+1);D.f(c+i+1);38.⑤處應(yīng)填（）A.a[s]=0;B.f(s-1);C.a[s]=i;D.b[i]=0;(正確答案)(二)(拓撲排序)輸入一張n節(jié)點m條邊的有向圖,用求該圖的一個拓撲排序的方式判斷該圖是否存在有向環(huán),若有拓撲排序輸出拓撲排序,并輸出”不存在有向環(huán)”,否則直接輸出”存在有向環(huán)”。

輸入:

第一行兩個正整數(shù)n,m表示節(jié)點數(shù)和邊數(shù)。

接下來m行,每行2個正整數(shù)x,y表示節(jié)點x->y之間有一邊。

輸出:

一個拓撲序:按拓撲序輸出點的編號。若拓撲序不唯一,輸出任意一個均可,并輸出“不存在有向環(huán)”。若無拓撲序,直接輸出“不存在有向環(huán)”

39.①處應(yīng)填（）.A.!cnt[i](正確答案)B.cnt[i]C.cnt[i]=0D.cnt[i]==140.②處應(yīng)填（）A.q.push(v);B.q.pop;C.cnt[u]--;D.cnt[v]--;(正確答案)41.③處應(yīng)填（）A.q