NOIP202217屆NOIP（C語言）普及組初賽試題

1、第11頁 共11頁NOIP2022-17屆NOIP（C語言）普及組初賽試題17屆NOIP（C語言）普及組初賽試題 一、單項選擇題（共20題，每題1.5分，共計30分。每題有且僅有一個正確選項。）1在二進制下，1001 + （ ）= 1110。 A. 1 B. 1 C. 0 D. 1111 2字符“0”的ASCII碼為48，則字符“9”的ASCII碼為（ ）。 A. 39 B. 57 C. 120 D. 視具體的計算機而定 3一片容量為8GB的SD卡能存儲大約（ ）張大小為2MB的數(shù)碼照片。 A. 1600 B. 2000 C. 4000 D. 16000 4摩爾定律（Moores law）是由

2、英特爾創(chuàng)始人之一戈登摩爾（Gordon Moore）提出來的。根據(jù)摩爾定律，在過去幾十年以及在可預(yù)測的未來幾年，單塊集成電路的集成度大約每（ ）個月翻一番。 A. 1 B. 6 C. 18 D. 36 5無向完全圖是圖中每對頂點之間都恰有一條邊的簡單圖。已知無向完全圖G有7個頂點，則它共有（ ）條邊。 A. 7 B. 21 C. 42 D. 49 6寄存器是（ ）的重要組成部分。 A. 硬盤 B. 高速緩存 C. 內(nèi)存 D. 中央處理器（CPU）7如果根結(jié)點的深度記為1，則一棵恰有2022個葉結(jié)點的二叉樹的深度最少是（ ）。 A. 10 B. 11 C. 12 D. 13 8. 體育課的鈴聲響

3、了，同學(xué)們都陸續(xù)地奔向操場，按老師的要求從高到矮站成一排。每個同學(xué)按順序來到操場時，都從排尾走向排頭，找到第一個比自己高的同學(xué)，并站在他的后面。這種站隊的方法類似于（ ）算法 。 A. 快速排序 B. 插入排序 C. 冒泡排序 D. 歸并排序 9一個正整數(shù)在二進制下有100位，則它在十六進制下有（ ）位。 A. 7 B. 13 C. 25 D. 不能確定 10有人認(rèn)為，在個人電腦送修前，將文件放入回收站中就是已經(jīng)將其刪除了。這種想法是（ ）。 A. 正確的，將文件放入回收站意味著徹底刪除、無法恢復(fù) B. 不正確的，只有將回收站清空后，才意味著徹底刪除、無法恢復(fù) C. 不正確的，即使將回收站清空

4、，文件只是被標(biāo)記為刪除，仍可能通過恢復(fù)軟件找回 D. 不正確的，只要在硬盤上出現(xiàn)過的文件，永遠不可能被徹底刪除 11廣度優(yōu)先搜索時，需要用到的數(shù)據(jù)結(jié)構(gòu)是（ ）。 A. 鏈表 B. 隊列 C. 棧 D. 散列表 12在使用高級語言編寫程序時，一般提到的“空間復(fù)雜度”中的“空間”是指（ ）。 A. 程序運行時理論上所占的內(nèi)存空間 B. 程序運行時理論上所占的數(shù)組空間 C. 程序運行時理論上所占的硬盤空間 D. 程序文件理論上所占的硬盤空間 13在含有n個元素的雙向鏈表中查詢是否存在關(guān)鍵字為k的元素，最壞情況下運行的時間復(fù)雜度是（ ）。 A. O(1) B. O(log n) C. O(n) D.

5、O(n log n) 14生物特征識別，是利用人體本身的生物特征進行身份認(rèn)證的一種技術(shù)。目前，指紋識別、虹膜識別、人臉識別等技術(shù)已廣泛應(yīng)用于政府、銀行、安全防衛(wèi)等領(lǐng)域。以下不屬于生物特征識別技術(shù)及其應(yīng)用的是（ ）。 A. 指靜脈驗證 B. 步態(tài)驗證 C. ATM機密碼驗證 D. 聲音驗證 15現(xiàn)有一段文言文，要通過二進制哈夫曼編碼進行壓縮。簡單起見，假設(shè)這段文言文只由4個漢字“之”、“乎”、“者”、“也”組成，它們出現(xiàn)的次數(shù)分別為700、600、300、200。那么，“也”字的編碼長度是（ ）。 A. 1 B. 2 C. 3 D. 4 16關(guān)于匯編語言，下列說法錯誤的是（ ）。 A. 是一種與

6、具體硬件相關(guān)的程序設(shè)計語言 B. 在編寫復(fù)雜程序時，相對于高級語言而言代碼量較大，且不易調(diào)試 C. 可以直接訪問寄存器、內(nèi)存單元、以及I/O端口 D. 隨著高級語言的誕生，如今已完全被淘汰，不再使用 17（ ）是一種選優(yōu)搜索法，按選優(yōu)條件向前搜索，以達到目標(biāo)。當(dāng)探索到某一步時，發(fā)現(xiàn)原先選擇并不優(yōu)或達不到目標(biāo)，就退回一步重新選擇。 A. 回溯法 B. 枚舉法 C. 動態(tài)規(guī)劃 D. 貪心法 181956年（ ）授予肖克利（William Shockley）、巴?。↗ohn Bardeen）和布拉頓（Walter Brattain），以表彰他們對半導(dǎo)體的研究和晶體管效應(yīng)的發(fā)現(xiàn)。 A. 諾貝爾物理學(xué)獎

7、 B. 約翰馮諾依曼獎 C. 圖靈獎 D. 高德納獎（Donald E. Knuth Prize）19對一個有向圖而言，如果每個節(jié)點都存在到達其他任何節(jié)點的路徑，那么就稱它是強連通的。例如，右圖就是一個強連通圖。事實上，在刪掉邊（ ）后，它依然是強連通的。 A. a B. b C. c D. d 20從ENIAC到當(dāng)前最先進的計算機，馮諾依曼體系結(jié)構(gòu)始終占有重要的地位。馮諾依曼體系結(jié)構(gòu)的核心內(nèi)容是（ ）。 A. 采用開關(guān)電路 B. 采用半導(dǎo)體器件 C. 采用存儲程序和程序控制原理 D. 采用鍵盤輸入 二、問題求解（共2題，每題5分，共計10分）1每份考卷都有一個8位二進制序列號。當(dāng)且僅當(dāng)一個序

8、列號含有偶數(shù)個1時，它才是有效的。例如，00000000、00011都是有效的序列號，而11111110不是。那么，有效的序列號共有_個。 2定義字符串的基本操作為：刪除一個字符、插入一個字符和將一個字符修改成另一個字符這三種操作。將字符串A變成字符串B的最少操作步數(shù)，稱為字符串A到字符串B的編輯距離。字符串“ABCDEFG“到字符串“BADECG“的編輯距離為_。 三、閱讀程序?qū)懡Y(jié)果（共4題，每題8分，共計32分）1. _include int main int i, n, m, ans; scanf(“%d%d“, &;n, &;m); i = n; ans = 0; while (i =

9、 m) ans += i; i+; printf(“%dn“, ans); return 0; 輸入：10 20 輸出：_ 2 _include _include _define SIZE 20 int main char map = “22233344455566677778889999“; char telSIZE; int i; scanf(“%s“, tel); for (i = 0; i = 0) &;&; (teli = A) &;&; (teli = Z) printf(“%c“, mapteli - A); return 0; 輸入：CCF-NOIP-2022 輸出：_ 3 _

10、include _include _define SIZE 100 int main int n, i, sum, x, aSIZE; scanf(“%d“, &;n); memset(a, 0, sizeof(a); for (i = 1; i = n; i+) scanf(“%d“, &;x); ax+; i = 0; sum = 0; while (sum (n / 2 + 1) i+; sum += ai; printf(“%dn“, i); return 0; 輸入： 11 4 5 6 6 4 3 3 2 3 2 1 輸出：_ 4 _include int solve(int n,

11、int m) int i, sum; if (m = 1) return 1; sum = 0; for (i = 1; i n; i+) sum += solve(i, m - 1); return sum; int main int n, m; scanf(“%d %d“, &;n, &;m); printf(“%dn“, solve(n, m); return 0; 輸入：7 4 輸出：_ 四、完善程序（前11空，每空2分，后2空，每空3分，共計28分）1（子矩陣）輸入一個n1*m1的矩陣a，和n2*m2的矩陣b，問a中是否存在子矩陣和b相等。若存在，輸出所有子矩陣左上角的坐標(biāo)；若不存在

12、輸出“There is no answer”。 _include _define SIZE 50 int n1, m1, n2, m2, aSIZESIZE, bSIZESIZE; int main int i, j, k1, k2, good, haveAns; scanf(“%d %d“, &;n1, &;m1); for (i = 1; i = n1; i+) for (j = 1; j = m1; j+) scanf(“%d“, &;aij); scanf(“%d %d“, &;n2, &;m2); for (i = 1; i = n2; i+) for (j = 1; j = m2;

13、 j+) ; haveAns = 0; for (i = 1; i = n1 - n2 + 1; i+) for (j = 1; j = ; j+) ; for (k1 = 1; k1 = n2; k1+) for (k2 = 1; k2 = ; k2+) if (ai + k1 - 1j + k2 - 1 != bk1k2) good = 0; if (good = 1) printf(“%d %dn“, i, j); ; if (haveAns = 0) printf(“There is no answern“); return 0; 2（大整數(shù)開方）輸入一個正整數(shù)n（1n00），試用二分

14、法計算它的平方根的整數(shù)部分。 _include _include _define SIZE 200 typedef struct node int len, numSIZE; hugeint; /其中l(wèi)en表示大整數(shù)的位數(shù)；num1表示個位、num2表示十位，以此類推 hugeint times(hugeint a, hugeint b) /計算大整數(shù)a和b的乘積 int i, j; hugeint ans; memset(ans.num, 0, sizeof(ans.num); for (i = 1; i = a.len; i+) for (j = 1; j = b.len; j+) +=

15、a.numi * b.numj; for (i = 1; i 0) ans.len = a.len + b.len; else ans.len = a.len + b.len - 1; return ans; hugeint add(hugeint a, hugeint b) /計算大整數(shù)a和b的和 int i; hugeint ans; memset(ans.num, 0, sizeof(ans.num); if (a.len b.len) ans.len = a.len; else ans.len = b.len; for (i = 1; i 0) ans.len+; return ans

16、; hugeint average(hugeint a, hugeint b) /計算大整數(shù)a和b的平均數(shù)的整數(shù)部分 int i; hugeint ans; ans = add(a, b); for (i = ans.len; i = 2; i-) ans.numi - 1 += ( ) * 10; ans.numi /= 2; ans.num1 /= 2; if (ans.numans.len = 0) ans.len-; return ans; hugeint plustwo(hugeint a) /計算大整數(shù)a加2后的結(jié)果 int i; hugeint ans; ans = a; ans.num1 += 2; i = 1; while (i = 10) ans.numi + 1 += ans.numi / 10; ans.numi %= 10; i+; if (ans.numans.len + 1 0) ; return ans; int over(hugeint a, hugeint b) /若大整數(shù)ab則返回1，否則返回0 int i; if ( ) return 0; if (a.len b.len) return 1; for (i = a.len; i