noip信息學聯(lián)賽2019模擬試卷(四)解析

1、25屆ccfnoip2019普及組初賽C+試題卷第二十五屆全國青少年信息學奧林匹克聯(lián)賽初賽(普及組C+語言試題) 競賽時間：2019年10月13日14:3016:30 選手注意： 試題紙共有7頁，答題紙共有2頁，滿分100分。請在答題紙上作答，寫在試題紙 上一律無效. 不得使用任何電子設(shè)備(如計算器、手機、電子詞典等)或查閱任何書籍資料單項選擇題(共20題，每題1.5分，共計30分。每題有且僅有一個正確答案.)1. (2019) iS+(9102)15=：A： (1001100110100111) 2 B： (116643) s C： (9DA7) D： (9DA5)2 .圖靈獎是信息學的最高

2、獎項，以下獲得過圖靈獎的中國人是：A：姚期智 B：姚期輝 C：馬云 D：馬化騰3 .國際信息學奧林匹克競賽縮寫是：A：NOIB：CTSC4.2. 0E-3二A：2000B：0. 0025.計算 20196&1二A：1B：31C： IOIC： 8C： 0D： ACMD： -2000D： 20196 .使用二分算法在一個大小為n (n=4)中尋找第4大的整數(shù)所需的時間復(fù)雜度為:A： 0 (1) B： 0 (nlogn) C： 0 (logn) D： 0 (n)7 .若設(shè)函數(shù)f (x)=1 (x=l, x=2)L_3*f (sqrt (x) )+f (x/2)+l (x2)當x=19時，計算過程中共

3、調(diào)用的f (x)個數(shù)是(包括調(diào)用f (1) , f (2)： 注釋：此處運算默認下取整A： 3B:48.上題函數(shù)中f (19)=C:5D:68A： 30B:37C： 36D:399 .第7題中的函數(shù)值不可以用以下哪種方法求得:D：遞歸搜索D：顯卡A:動態(tài)規(guī)劃B：分治C：遞推10 .以下部件損壞，主機仍可正常工作的是：A：內(nèi)存條B：硬盤C：顯示屏 1L對一下數(shù)據(jù)1000, 2, 3, 5,4,1, 5000進行冒泡排序，共計需交換次數(shù)為:A： 5B： 10C： 15D： 1812 .如果將人體比作計算機，那么人體的記憶中樞相當于以下計算機部件的:A：運算器 B：中央處理器C：控制器 D：內(nèi)存13

4、 .以下示意圖中的數(shù)據(jù)結(jié)構(gòu)不屬于選項中的哪個數(shù)據(jù)結(jié)構(gòu)：A：大根堆 B：無向圖C:連通圖D：完全二義樹14 . dos、unix和windows的共同點是：A：都是硬件B：都是聯(lián)網(wǎng)系統(tǒng)軟件 C：都是應(yīng)用軟件D：都已經(jīng)過時15 .html是一種高級語言，以下操作可以查看html代碼的是：A：打開瀏覽器按FilB：運行html. exeC：無法查看D：打開瀏覽器按F1216 .以下關(guān)于計算機病毒的說法正確的是：A：防火墻可以防止感染B：通過生物傳播C： 一旦感染無法破解D：計算機一次感染終身免疫17 .c+語言“實數(shù)下取整”操作是：A： (int)xB： float(x)C： floor(x)D:c

5、eil(x)18 . 一棵n層二叉樹的最多節(jié)點數(shù)減去最少節(jié)點數(shù)等于：A:2*nB: 2n-nC: n:nD:n*log2 (n) -n19 .現(xiàn)給出以下程序：#include using namespace std;int i, x;int aU=0F 10, 2, 3, 5,14, 8, 20, 1, 7,-1;int mainO (cinx;sort(a+1, a+11);for (i=l;i=x) break;)問若將此程序的輸入輸出看做函數(shù)，則此函數(shù)的圖像不經(jīng)過點：A： (0,2) B： (2,4)C： (11,9) D： (21, 11)20 .上題程序劃線部分可替換為：A： cou

6、tupper_bound (a, a+10, x) endl;25屆ccfnoip2019普及組初賽C+試題卷B： coutupper_bound (a+l, a+11, x)endl;C： coutupper_bound (a+l, a+11, x)-aendl;D: coutlower_bound(a+l, a+11, x)-aendl;二.問題求解(共2題，每題5分，共計10分)L五位數(shù)的卡布列克運算循環(huán)節(jié)為：注釋：卡布列克運算為將一數(shù)的所有數(shù)位數(shù)字重新排列可得的數(shù)的最大值減最小值(高 位補零)，保證有循環(huán)節(jié)，本題有三個答案，寫出一個即得5分，各數(shù)字用逗號隔開:2.對于一棵勾股樹(任一直

7、角三角形三邊均有與邊長等長正方形重合，任一直角三角形 直角邊為邊長的正方形均與另一直角三角形斜邊重合，如圖)，設(shè)所有最小正方形邊長三.閱讀程序?qū)懡Y(jié)果(共4題，每題8分，共計32分)1.#includeusing namespace std;int mainO(int a, b, c;double ans;cinac;if (!cll=c) c-=l;b= (a*c)/2;ans=sqrt(pow(b, 3);printf C%Q. 2f”, ans);return 0;)輸入：1 3輸出：2.#include#includeusing namespace std;int n, aElOl, i

8、 ;int mainO (cinn;for (i=l;iaLi;sort(a+1, a+n+1);n=unique (a+l, a+n+1) aT ;coutnendl;for (i=l; i=n; i+) coutali，;coutendl;return 0;)輸入：1020 40 32 67 40 20 89 300 400 15輸出：3.#includeusing namespace std;long long o=l, minn=10000000, m;struct palong long s;long long j;string n;long long cost;)；pa p1000

9、5;int mainO (while(cinplo. splo.n)o+;for(int i=l;io;i+) (for(int g=l;go;g+)pi. cost+=abs(pLil. j-pgL j)*pg s; if (plil. cost=minn) (minn=pEi.cost;m=i; 825屆ccfnoip2019普及組初賽C+試題卷 coutpLm. ncostendl;return 0;) 輸入：7 9289 Vladivostok 5 8523 Chabarovsk 3 5184 Irkutsk 8 2213 Yalutorovsk 10 0 Moscow 輸出：4.#i

10、nclude using namespace std; int a500001, b500001, i, n, A, B, 1, r, mid; bool check(int mid) ( int ii,s=0; memcpy(b, a, sizeof(a); for (ii=l;ii=n;ii+) bii一=mid*A; for (ii=l;ii=n;ii+) ifs+=(int)ceil(double)bEii/B);return s=mid; ) int mainO ( scanf(%d%d%d &n, &A, &B); for (i=l;i=n;i+) scanf; 1=0； r=50

11、0010; while (laj825屆ccfnoip2019普及組初賽C+試題卷旦ij的有序?qū)?。逆序?qū)梢杂妹芭菖判蚝蜌w并排序求得。試完善以下冒泡排序程序 段與歸并排序程序。s=0;for (i=l;i=n;i+)for (j=l;jaj+l)(2);+s;)coutsendl;/#includeusing namespace std;long long a500001, b500001, s, n;void guibingdong long 1, long long r)(if (r-l=0) return;if (rT=l)if (araEj)(s+=(6)bk=aj;+k;+j；)el

12、sebk=ai;+k;+i；)for (;i=mid;i+) bk+=ai; for (;j=r;j+) bk+=aj;for (k=l;k=r;k+)；)int mainO(long long i;scanf (飛Id, &n);for (i=l; i=n; i+) scanf (“先Id”,;guibing(l, n);printf (%ldn”, s);return 0;)2.石子合并:在一個圓形操場的四周擺放N堆石子，現(xiàn)要將石子有次序地合并成一堆.規(guī)定 每次只能選相鄰的2堆合并成新的一堆，并將新的一堆的石子數(shù)，記為該次合并的得分。 試設(shè)計出1個算法，計算出將N堆石子合并成1堆的最小得分

13、和最大得分.#includeusing namespace std;const int Maxn=1000+10;int tMaxn, dpiMaxnMaxn, dp2MaxnMaxn;int mainO int n;cinn;for(int i=l;i=n;+i) cinti;t (1)for(int i=2;i=2*n;+i) ti+=ti-l;memset(dpi, 0, sizeof(dpi);for(int i=2*n-l;(2)for(int j= (3);j=2*n;+j) int b=2147483647;for (int k=i;kj;+k)dplij=max(dplij,

14、dplik+dplk+lj+tj-ti-1);b=min(b, );dp2i j=b; int max0=0, min0=10000000;for(int i=l;i=n;+i)maxO=max(5);min0=min(min0, dp2ij i+n-l) ; coutminOendlmaxOendl;return 0; CCF NOIP2019普及組(C+語言)參考答案與評分標準一、單項選擇題（共20題，每題1.5分，共計30分）L答案為：(任答其一即可)59994, 53955 ：74943, 62964, 71973, 83952：61974, 82962, 75933, 639542.al:+a2:+a8/或匯&丁三、閱讀程序?qū)懡Y(jié)果(共4題，每題8分，共計32分)1. 1. 002. 815 20 32 40 67 89 300 4003. Yalutorovsk 1121254. 6四、完善程序(第1題，每空2分，第2題