NOIP2022年初賽普及組試題知識點分析

其次十屆全國青少年信息學奧林匹克聯(lián)賽初賽C++2022年一、快單項選擇題(共20題，每題1.5分，共計30分；每題有且僅有一個正確選項)1.以下哪個是面對對象的高級語言( )。B.C++A.匯編語言 C.Fortran D.BasicB.C++【學問點】計算機語言根底常識【把握度】了解【學問分析】心，而對象是程序運行時刻的根本成分。語言中供給了類、繼承等成分，有識認性、多態(tài)性、類別性和繼承性四個主要特點。而面對對象只是一種編程思想。匯編語言：低級語言C++：面對對象高級語言Fortran：高級語言Basic：高級語言D.240次方⒉D.240次方A.2的10次方 B.2的20次方 C.2的30次方【學問點】計算機存儲進制換算【把握度】把握【學問分析】1KB=1024B=210B1MB=1024KB=220B1GB=1024MB=230B1TB=1024GB=240BD.00111001⒊二進制數(shù)00100100和00010101的和是( )。A.00101000 B.001010100 C.01000101D.00111001【學問點】二進制運算【把握度】把握D.打印機⒋以下哪一種設備屬于輸出設備( )。A.掃描儀 B.鍵盤 C.D.打印機【學問點】計算機組成原理【把握度】把握【學問分析】硬件組成：掌握器(Control):掌握，調度程序、數(shù)據(jù)、地址，協(xié)調計算機各局部工作及內存與外設的訪問等。運算器(Datapath):運算器的功能是對數(shù)據(jù)進展各種算術運算和規(guī)律運算，即對數(shù)據(jù)進展加工處理。存儲器(Memory):存儲器的功能是存儲程序、數(shù)據(jù)和各種信號、命令等信息，并在需要時供給這些信息。輸入設備(Inputsystem):外設，輸入設備的作用是將程序、原始數(shù)據(jù)、文字、字符、掌握命令或現(xiàn)場采集的數(shù)據(jù)等信息輸入到計算機。常見的輸入設備有鍵盤、鼠標器、光電輸入機、磁帶機、磁盤機、光盤機等。輸出設備(Outputsystem):輸出設備與輸入設備同樣是計算機的重要組成局部，它把外算機的中間結果CRT、打印機、激光印字機、繪圖儀及磁帶、光盤機等。⒌以下對操作系統(tǒng)功能的描述最為完整的是( )。C.掌握和治理計算機系統(tǒng)的各種硬件和軟件資源的使用A.負責外設與主機之間的信息交換 B.C.掌握和治理計算機系統(tǒng)的各種硬件和軟件資源的使用D.將沒有程序編譯成目標程序【學問點】計算機操作系統(tǒng)【把握度】了解【學問分析】需要處理如治理與配置內存、打算系統(tǒng)資源供需的優(yōu)先次序、掌握輸入設備與輸出設備、操作網(wǎng)絡與治理文件系統(tǒng)等根本領務。操作系統(tǒng)也供給一個讓用戶與系統(tǒng)交互的操作界面。⒍CPU、存儲器、I/O設備是通過( )連接起來的。B.總線A. 接口 C.掌握線 D.B.總線【學問點】計算機組成原理【把握度】了解【學問分析】總線〔Bus〕是計算機各種功能部件之間傳送信息的公共通信干線，它是由導線組成的傳輸線束，按照計算機所傳輸?shù)男畔⒎N類，計算機的總線可以劃分為數(shù)據(jù)總線、地址總線和掌握總線，分別用來傳輸數(shù)據(jù)、數(shù)據(jù)地址和掌握信號?？偩€是一種內部構造，它是cpu、內存、輸入、輸出設備傳遞信息的公用通道，主機的各個部件通過總線相連接，外部設備通過相應的接口電路再與總線相連接，從而形成了計算機硬件系統(tǒng)。在計算機系統(tǒng)中，各個部件之間傳送信息的公共通路叫總線，微型計算機是以總線構造來連接各個功能部件的。A.RAM⒎斷電后會喪失數(shù)據(jù)的存儲器是( )。A.RAMB.ROM C.硬盤 D.光盤【學問點】計算機原理【把握度】把握【學問分析】RAMROM即只讀內存，是一種只能讀出事先所存數(shù)據(jù)的固態(tài)半導體存儲器。比照手機中的RAM和ROM分別對應電腦的內存和硬盤。內存負責程序的運行以及數(shù)據(jù)交換，有了它電腦中的軟件才能運行，⒏以下哪一種是屬于電子郵件收發(fā)的協(xié)議( )。A.SMTPB.UDP C.P2P D.FTPA.SMTP【學問點】計算機網(wǎng)絡協(xié)議【把握度】了解【學問分析】SMTP:SimpleMailTransferProtocol,簡潔郵件傳輸協(xié)議UDP:UserDataProtocolTCP相對應的協(xié)議。它是面對非連接的協(xié)議，它不與對方建立連接，而是直接就把數(shù)據(jù)包發(fā)送過去！TCP〔TransmissionControlProtocol,傳輸掌握協(xié)議〕是一種面對連接的、牢靠的、基于字節(jié)流的傳輸層通信協(xié)議。Ppin”命令TCP/IP通信是否正常，其實“ping”命令的原理就是向對方主機發(fā)送UDP數(shù)據(jù)包，然后對方主機確認收到數(shù)據(jù)包，假設數(shù)據(jù)包是否到達的消息準時反響回來，那么網(wǎng)絡就是通的。P2P(PeertoPeer)對等計算機或對等網(wǎng)絡。p2p的核心：P2P的核心是數(shù)據(jù)存儲在客戶本地，通過存儲信息(名稱、地址、分塊)的查詢，讓終端之間直接數(shù)據(jù)傳遞。P2P網(wǎng)絡讓網(wǎng)絡上的數(shù)據(jù)流量分散化，同時治理點不僅沒有效勞容量的壓力，而且只存儲數(shù)據(jù)的索引與鏈接，不對數(shù)據(jù)本身負責，避開了版權與治理的麻煩。p2p網(wǎng)絡實現(xiàn)的思想：P2P網(wǎng)絡實際上是一種“無中心政府的P世界是你下載的同時，利用文件分塊的技術，把你剛擁有的局部馬上給別人共享，固然這種共享不必再經(jīng)過你的允許，并且依據(jù)你的表現(xiàn)積分，鼓舞“好”人，嘉獎奉獻，你幫了別人，別人就來幫你。由于很多P2PP2P步共享供給了根底。FTP:FileTransferProtocol,文件傳輸協(xié)議⒐以下選項中不屬于圖像格式的是( )。B.TXT格式JPEGB.TXT格式【學問點】計算機根底學問【把握度】了解【學問分析】

C.GIF格式D.PNG格式JPG,JPEG,PNGGIFTXTtextB.可隨機訪問任一元素⒑鏈表不具有的特點是( )。A.B.可隨機訪問任一元素C.插入刪除不需要移動元素 D.所需空間與線性表長度成正比【學問點】數(shù)據(jù)構造—鏈表【把握度】把握【學問分析】〔鏈表中每一個元素稱為結點O(1)的簡單度，O(n)性表和挨次表相應的時間簡單度分別是O(logn)O(1)。間，實現(xiàn)敏捷的內存動態(tài)治理。但是鏈表失去了數(shù)組隨機讀取的優(yōu)點，同時鏈表由于增加了結點的指針域，空間開銷比較大。鏈表最明顯的好處就是，常規(guī)數(shù)組排列關聯(lián)工程的方式可能不同于這些數(shù)據(jù)任意位置上的節(jié)點，但是不允許隨機存取。鏈表有很多種不同的類型：單向鏈表，雙向鏈表以及循環(huán)鏈表。鏈表可以在多種編程語言中實現(xiàn)。像LispScheme這樣的語言的內建數(shù)據(jù)類型中就包含了鏈表的存取和操作。程序語言或面對對象語言，如C,C++Java依靠易變工具來生成鏈表。D.199⒒以下各無符號十進制整數(shù)中，能用八位二進制表示的數(shù)中最大的是( )。A.296 B.133 C.256D.199【學問點】二進制轉化【把握度】把握【學問分析】無符號八位二進制能表示的十進制范圍為0~255，超過則溢出C.256.256.129.1⒓以下幾個32位IP地址中，書寫錯誤的選項是( )。A.7 B.C.256.256.129.1【學問點】IP地址【把握度】理解【學問分析】

D.“IP0-126/128-191/192-223/224-239/240-255共五類，A、B、C、D、E類，國際上做出規(guī)ABC類，DEIP地址，與局域網(wǎng)內其他客戶機通信。還可以承受DHCP自動獵取”⒔要求以下程序的功能是計算：s=1+1/2+1/3+...+1/10。#include<iostream>usingnamespacestd;intmain{intn;floats;s=1.0;for(n=10;n>1;n--)s=s+1/n;cout<<s<<endl;return0;}程序運行后輸出結果錯誤，導致錯誤結果的程序行是( )。C.s=s+1/n;A.s=1.0; B.for(nC.s=s+1/n;【學問點】C++程序閱讀【把握度】把握【學問分析】題目要求程序的功能是計算：s=1+1/2+1/3+...+1/10。

D.cout<<s<<endl;C++中整數(shù)與整數(shù)相除，結果照舊是整數(shù)，全部無法得到浮點數(shù)的答案⒕設變量x為float型且已賦值，則以下語句中能將x中的數(shù)值保存到小數(shù)點后兩位，并將第三位四舍五入的是( )。A.x=(x*100)+0.5/100.0; B.x=(x*100+0.5)/100.0;C.x=(int)(x*100+0.5)/100.0;D.x=(xC.x=(int)(x*100+0.5)/100.0;【學問點】C++保存有效數(shù)【把握度】把握【學問分析】題目要求：保存到小數(shù)點后兩位，并將第三位四舍五入(int)(x*100+0.5)/100.0;其中x*100+0.5是將小數(shù)后兩位變成整數(shù)，再將第一位小數(shù)四舍五入，int強制轉換，將小數(shù)局部全部去除，最終/100是將整數(shù)局部的最終兩位變回小數(shù)⒖有以下程序#include<iostream>usingnamespacestd;intmain{ints,a,n;s=0;a=1;cin>>n;do{s+=1;a-=2;}while(a!=n);cout<<s<<endl;return0;}假設要使程序的輸出值為2，則應當從鍵盤給n輸入的值是( )。B.-3A.-1 C.-5 D.0B.-3【學問點】C++程序閱讀【把握度】把握【學問分析】把握do{}while循環(huán)，do{}while2，逆向推出結果。2，說明do{}while執(zhí)行了兩次a1，每次do{}while24，n的值為-3⒗一棵具有5層的滿二叉樹中結點數(shù)為( )。A.31B.32 C.33 D.16A.31【學問點】二叉樹—滿二叉樹【把握度】把握【學問分析】2n-1。⒘有向圖中每個頂點的度等于該頂點的( )。C.入度和出度之和A.入度 B.C.入度和出度之和【學問點】圖論—有向圖【把握度】把握【學問分析】

D.入度和出度之差學問點：有向圖中每個頂點的度等于該頂點的入度和出度之和。有向圖的全部邊都有方向，即確定了頂點到頂點的一個指向；而無向圖的全部邊都是雙向的，即無向有向邊組成。頂點的度是指和該頂點相連的邊的條數(shù)入度(in-degree)：以某頂點為弧頭，終止于該頂點的弧〔邊〕的數(shù)目稱為該頂點的入度。出度(out-degree)：以某頂點為弧尾，起始于該頂點的弧〔邊〕的數(shù)目稱為該頂點的出度。⒙設有100個數(shù)據(jù)元素，承受折半搜尋時，最大比較次數(shù)為( )。B.7A.6 C.8 D.10B.7【學問點】算法—折半〔二分〕【把握度】把握【學問分析】n個數(shù)折半查找,最大比較次數(shù)是(int)(log2n)+1。⒚假設有如下程序段，其中s、a、b、c均已定義為整型變量，且a、c均已賦值，c>0。s=a;for(b=1;b<=c;b++) s+=1;則與上述程序段功能等價的賦值語句是( )。B.s=a+B.s=a+c【學問點】C++程序閱讀【把握度】把握【學問分析】

C.s=s+c D.s=b+cfor(b=1;b<=c;b++) s+=1;本質就是c有多大，s1C.圖靈獎⒛計算機界的最高獎是( )。A.菲爾茲獎B.C.圖靈獎【學問點】計算機史【把握度】了解【學問分析】

D.普利策獎如圖：艾倫〔阿蘭·麥席森·1966年由美國計算機協(xié)會M個獎項，有“計算機界的諾貝爾獎”之稱，每年評比出一名計算機科學家，目前獲得該獎項的華人學2022年圖靈獎得主姚期智教授?，F(xiàn)代計算機的根底是抽象的圖靈機。如圖：二、問題求解(25105分，沒有局部分)把M個同樣的球放到N(K表示)。18例如時在這里認為和是同一種放置方法問時。18【學問點】算法—遞歸函數(shù)【把握度】把握【學問分析】K=f(m,n)m個球，n00的方案數(shù)。m=0n=1時，f(m,n)=1m<n時，f(m,n)=f(m,m)m>n時，則有：1、含有0的方案數(shù)，即有至少一個袋子空著，即相當于f(m,n)=f(m,n-1)2、不含有0的方案數(shù)，即全部袋子都有球，那么先從m個球中抽取出n個出來，各個袋子分一個，考慮剩下的m-n個球放到n個袋子里的放法，即f(m,n)=f(m-n,n).而總的放法數(shù)目等于兩者的和，即f(m,n)=f(m,n-1)+f(m-n,n)，所以：f(8,5)=f(8,4)+f(3,5)=18如下圖，圖中每條邊上的數(shù)字表示該邊的長度，則從A到E的最短距離是11 ?！緦W問點】圖論—最短路徑問題【把握度】把握【學問分析】我們可以用倒推的方法，求A 到E的最短距離。用k 來表示階段。k=4，有d4(F,E)來表示F到E 的距離。f4(F)=6k=3，用d3(C,E)、d3(C,F)、d3(D,F)、d3(D,E)來表示有四條路。f3(C)=min{d3(C,E),d3(C,F)}=min{8,1+6}=7f3(D)=min{d3(D,F),d3(D,E)}=min{2+6,4}=4k=2，有f2(B)=min{d2(B,C),d2(B,D)}=min{1+7,7+4}=8；f2(G)=min{d2(G,C),d2(G,D)}=min{2+7,4+4}=8k=1，有f1(A)=min{d1(A,B),d1(A,G),d1(A,F)}=min{3+8,4+8,6+6}=11三、閱讀程序寫結果(4832分)1.#include<iostream>usingnamespacestd;intmain{inta,b,c,d,ans;cin>>a>>b>>c;d=a-b;a=d+c;ans=a*b;cout<<“Ans=“<<ans<<endl; return0;}9輸入：2349輸出：Ans=【學問點】C++編程根底【把握度】把握2.#include<iostream>usingnamespacestd;intfun(intn){if(n==1)return1;if(n==2)return2;returnfun(n-2)-fun(n-1);}intmain{intn;cin>>n;cout<<fun(n)<<endl;return0;}-11輸入：7輸出：-11【學問點】C++編程—遞歸【把握度】把握【學問分析】遇到遞歸問題時，可以自行繪制二叉樹，分解問題3.#include<iostream>#include<string>usingnamespacestd;intmain{stringst;inti,len;getline(cin,st);len=st.size;for(i=0;i<len;i++)if(st[i]>=”a”&&st[i]<=”z”)st[i]=st[i]-”a”+”A”;cout<<st<<endl;return0;}HELLO,MYNAMEISLOSTMONKEY.輸入：Hello,mynameisLostmonkey.HELLO,MYNAMEISLOSTMONKEY.輸出：【學問點】C++編程【把握度】把握【學問分析】該題目是將全部小寫字母轉化為大寫字母，是基于ASCII碼的根本操作4.#include<iostream>usingnamespacestd;constintSIZE=100;intmain{intp[SIZE];intn,tot,i,cn;tot=0;cin>>n;for(i=1;i<=n;i++)p[i]=1;for(i=2;i<=n;i++){if(p[i]==1)tot++;cn=i*2;while(cn<=n){p[cn]=0;cn+=i;}}cout<<tot<<endl;return0;}輸入：30輸出：10【學問點】C++編程【把握度】把握【學問分析】該題目是求30以內素數(shù)的個數(shù)，學生需要把握三大構造的運行模式四、完善程序(228分)1.(數(shù)字刪除)下面程序的功能是將字符串中的數(shù)字字符刪除后輸出。請?zhí)羁铡?312分)#include<iostream>usingnamespacestd;intdelnum(char*s){inti,j;j=0;for(i=0;s[i]!=”\0”;i++)if(s[i]<”0” ||s[i]>”9”){s[j]=s[i];j++ ;}return j ;}constintSIZE=30;intmain{chars[SIZE];intlen,i;cin.getline(s,sizeof(s));len=delnum(s);for(i=0;i<len;i++)cout<< s[i];cout<<endl;return0;}【學問點】C++編程—全面【把握度】把握【學問分析】題目要求：將字符串中的數(shù)字字符刪除后輸出，所以自定義函數(shù)delnum的主要功能是將數(shù)字刪除的功能，delnum(char*s)形參是指針類型，那么也就是說，真實的操作會是在原地址上if(s[i]<”0” ||s[i]>”9”)題目要求：將字符串中的數(shù)字字符刪除后輸出，這個空則是推斷字符是否為數(shù)字，沒有字符是同時小于“0”又同時大于“9”的，而其中只能填或運算符s[j]=s[i]; j++ ;s[i]s[j]后，j所指向的內存應當向后移動len=delnum(s)說明自定義函數(shù)返回了一個值，len這個變量名也多是用來形容字符長度的，所以返回值為return j ;for(i=0;i<len;i++)cout<< s[i];是以此輸出更改后的值2.(最大子矩陣和)mn列的整數(shù)矩陣，求最大的子矩陣和(子矩陣不能為空)。輸入第一行包含兩個整數(shù)mnmn個整數(shù)，描述整個矩陣。程序最終輸出最大的子矩陣和。(4316分)比方在如下這個矩陣中：4 40-2-7092-62-41-41-180-2