2011少年信息學奧林匹克聯賽初賽C試題資料

1、第十七屆全國青少年信息學奧林匹克聯賽初賽試題（普及組 C語言兩小時完成）一、單項選擇題（共 20題，每題1.5分，共計 30分。每題有且僅有一個正確選項。）1.在二進制下，1100100 +（） = 1110001A. 1011B.1101C.1010D. 1111 。2 .字符“ 0的ASCII碼為48，則字符“ 9” ASCII碼為（）A. 39B. 57C. 120D.視具體的計算機而定3 .一片容量為 8GB的SD卡能存儲大約（）張大小為2MB的數碼照片。A. 1600B.2000C.4000D.160004 .摩爾定律（Moore's law ）是由英特爾創(chuàng)始人之一戈登 摩爾

2、（Gordon Moore ）提出來的。根據摩爾定律，在過去幾十年以及在可預測的未來幾年，單塊集成電路的集成度大約每（）個月翻一番。A. 1B. 6C. 18D. 365.無向完全圖是圖中每對頂點之間都恰有一條邊的簡單圖。已知無向完全圖 G有7個頂點，則它共有（）條邊。A. 7B. 21C. 42D. 496 .寄存器是（）的重要組成部分。A.硬盤B.高速緩存C.內存D.中央處理器（CPU ）7 .如果根結點的深度記為1，則一棵恰有 2011個葉結點的二叉樹的深度最少是（）A. 10B. 11C. 12D. 138. 體育課的鈴聲響了，同學們都陸續(xù)地奔向操場，按老師的要求從高到矮站成一排。每個

3、同學按順序來到操場時，都從排尾走向排頭，找到第一個比自己高的同學，并站在他的后面。這種站隊的方法類似于（）算法 。A.快速排序B.插入排序C.冒泡排序D.歸并排序位。9. 一個正整數在二進制下有100位，則它在十六進制下有（）位。A. 7B. 13C. 25D.不能確定10 .有人認為，在個人電腦送修前，將文件放入回收站中就是已經將其刪除了。這種想法 是（）。A. 正確的，將文件放入回收站意味著徹底刪除、無法恢復B. 不正確的，只有將回收站清空后，才意味著徹底刪除、無法恢復C. 不正確的，即使將回收站清空，文件只是被標記為刪除，仍可能通過恢復軟件找回D. 不正確的，只要在硬盤上出現過的文件，永

4、遠不可能被徹底刪除11.廣度優(yōu)先搜索時，需要用到的數據結構是（）。A.鏈表B.隊列C.棧。D.散列表12 在使用高級語言編寫程序時，一般提到的空間復雜度”中的空間”是指（）A. 程序運行時理論上所占的內存空間B. 程序運行時理論上所占的數組空間C. 程序運行時理論上所占的硬盤空間D. 程序源文件理論上所占的硬盤空間13 在含有n個元素的雙向鏈表中查詢是否存在關鍵字為k的元素，最壞情況下運行的時間復雜度是（）。A. 0（1） B. O（log n） C. 0（n） D. O（n log n）14 生物特征識別，是利用人體本身的生物特征進行身份認證的一種技術。目前，指紋識 另虹膜識別、人臉識別等技

5、術已廣泛應用于政府、銀行、安全防衛(wèi)等領域。以下不屬于生物特征識別技術及其應用的是（）。A.指靜脈驗證B.步態(tài)驗證C. ATM 機密碼驗證D.聲音驗證15 .現有一段文言文，要通過二進制哈夫曼編碼進行壓縮。簡單起見，假設這段文言文只由4個漢字 之”、乎”、者”、也”組成，它們出現的次數分別為700、600、300、 200。那么，也”字的編碼長度是（）。A. 1B. 2C. 3D. 416 .關于匯編語言，下列說法錯誤的是（|A. 是一種與具體硬件相關的程序設計語言B. 在編寫復雜程序時，相對于高級語言而言代碼量較大，且不易調試C. 可以直接訪問寄存器、內存單元、以及I/O端口D. 隨著高級語言

6、的誕生，如今已完全被淘汰，不再使用17 .（）是一種選優(yōu)搜索法，按選優(yōu)條件向前搜索，以達到目標。當探索到某一步時，發(fā)現原先選擇并不優(yōu)或達不到目標，就退回一步重新選擇。A.回溯法B.枚舉法C.動態(tài)規(guī)劃D.貪心法18 . 1956 年()授予肖克利(William Shockley )、巴丁( John Bardeen )和 布拉頓(WalterBrattain ),以表彰他們對半導體的研究和晶體管效應的發(fā)現。A諾貝爾物理學獎B. 約翰馮諾依曼獎C. 圖靈獎D. 高德納獎(Donald E. Knuth Prize )19 .對一個有向圖而言，如果每個節(jié)點都存在到達其他任何節(jié)點的路徑，那么就稱它是

7、強連通的。例如，右圖就是一個強連通圖。事實上，在刪掉邊()后，它依然是強連通的。A. a B. b C. cD. d20 .從ENIAC到當前最先進 的計算機，馮 諾依曼體系結構始終占有重要的地位。馮諾依曼體系結構的核心內容是()。A.采用開關電路B.采用半導體器件C.采用存儲程序和程序控制原理D.采用鍵盤輸入二、問題求解(共 2題，每題5分，共計10分)1.每份考卷都有一個8位二進制序列號。當且僅當一個序列號含有偶數個1時，它才是有 效的。例如，00000000、01010011 都是有效的序列號，而11111110不是。那么，有效的序列號共有個。2 .定義字符串的基本操作為：刪除一個字符、

8、插入一個字符和將一個字符修改成另一個字符這三種操作。將字符串A變成字符串 B的最少操作步數，稱為字符串A到字符串B的編輯距離。字符串"ABCDEFG"到字符串"BADECG"的編輯距離為 。三、 閱讀程序寫結果(共4題，每題8分，共計32分)1.#in clude<stdio.h>int mai n() int i, n, m, ans;scan f("%d%d", &n, & m);i = n;ans = 0;while (i <= m) ans += i; i+;printf("%dn&

9、quot;, ans);return 0;輸入：10 20輸出：2.#i nclude <stdio.h>#in clude <stri ng.h>#defi ne SIZE 20int mai n() char map = "22233344455566677778889999"char telSIZE;int i;scan f("%s", tel);for (i = 0; i < strlen(tel); i+)if (teli >= '0') && (teli <= '

10、;9') prin tf("%c", teli);else if (teli >= 'A') && (teli <= 'Z')prin tf("%c", mapteli - 'A');return 0;輸入：CCF-NOIP-2011輸出：3.#i nclude <stdio.h>#in clude <stri ng.h>#define SIZE 100int mai n()int n, i, sum, x, aSIZE;scanf("%

11、d", &n);memset(a, 0, sizeof(a);for (i = 1; i <= n; i+) | sca nf("%d", &x);ax+;i = 0; sum = 0;while (sum < (n / 2 + 1)|i+; sum += ai;prin tf("%dn", i);return 0;輸入：114 5 6 6 4 3 3 2 3 2 1輸出：4.#i nclude <stdio.h>int solve(i nt n, int m) int i, sum;if (m = 1)

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

13、“ There is noan swer。#i nclude <stdio.h>#defi ne SIZE 50int n1, m1, n2, m2, aSIZESIZE, bSIZESIZE;int mai n()int i, j, k1, k2, good, haveA ns;scan f("%d %d", &n1, & m1);for (i = 1; i <= n1; i+)for (j = 1; j <= m1; j+)scanf("%d", &aij);scan f("%d %d&quo

14、t;, &n2, & m2);for (i = 1; i <= n2; i+)for (j = 1; j <= m2; j+)haveA ns = 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) prin tf("%d %dn", i

15、, j);if (haveA ns = 0)prin tf("There is no an swer n"); retur n 0;2 .(大整數開方)輸入一個正整數n (1 w n<10100 )，試用二分法計算它的平方根的整數部分。#i nclude <stdio.h>#in clude <stri ng.h>#defi ne SIZE 200typedef struct node "|int len, numSIZE; hugeint; /其中l(wèi)en表示大整數的位數；num1表示個位、num2表示十位，以此類推hugeint t

16、imes(hugeint a, hugeint b)計算大整數 a 和 b 的乘積int i, j;huge int ans;memset(a ns.num, 0, sizeof(a ns.nu m);for (i = 1; i <= a.len; i+)for (j = 1; j <= ben; j+) += a.nu mi * b.nu mj;for (i = 1; i <= a.len + b.len; i+) ans.nu mi + 1 += ans.nu mi / 10;if (ans.nu maen + b.len > 0) ans.len = a.len

17、+ b.le n;else ans.len = a.len + b.len - 1;return ans;hugeint add(hugeint a, hugeint b)計算大整數a 和 b 的和int i; huge int ans;memset(a ns.num, 0, sizeof(a ns.nu m);if (a.len > b.len) ans.len = a.len;else ans.len = b.len;for (i = 1; i <= ans.len; i+) ans.numi +=;ans.nu mi + 1 += ans.nu mi / 10;ans.nu

18、mi %= 10;if (ans.nu ma ns.len + 1 > 0)ans.len+;return ans;hugeint average(hugeint a, hugeint b)/計算大整數 a和b的平均數的整數部分int i;huge int ans;ans = add(a, b);for (i = ans.len; i >= 2; i-) ans.numi - 1 += ( _ );ans.nu mi /= 2;ans.nu m1 /= 2;if (ans.nu ma ns.len = 0) ans.len-;retur n ans;hugeint plustwo(

19、hugeint a)/計算大整數 a 加int i;huge int ans;ans = a;ans.nu m1 += 2;i = 1;while (i <= ans.len) && (ans.numi >= 10) ans.nu mi + 1 += ans.nu mi / 10;ans.nu mi %= 10;i+;if (ans.nu ma ns.len + 1 > 0)retur n ans;int over(huge int a, huge int b)若大整數 a>bint i;if () return 0;if (a.len > b.len)retur n 1;for (i = aen; i >= 1;