NOIP2011第十七屆初賽C++普及組試題與答案(Word精排版)

1、第十七屆全國青少年信息學(xué)奧林匹克聯(lián)賽初賽試題（ 普及組 c+ 語言 兩小時完成 ） 全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效 一、單項選擇題（共 20 題，每題 1.5 分，共計 30 分。每題有且僅有一個正確選項。）1、在二進制下，1101001 + （ ） = 1110110。a、1011b、1101c、1010d、11112、字符“0”的 ascii 碼為 48，則字符“9”的 ascii 碼為（ ）。a、39b、57c、120d、視具體的計算機而定3、一片容量為 8gb 的 sd 卡能存儲大約（ ）張大小為 2mb 的數(shù)碼照片。a、1600b、2000c、4000d、160

2、004、摩爾定律（moores law）是由英特爾創(chuàng)始人之一戈登摩爾（gordon moore）提出來的。根據(jù)摩爾定律，在過去幾十年以及在可預(yù)測的未來幾年，單塊集成電路的集成度大約每（ ）個月翻一番。a、1b、6c、18d、365、無向完全圖是圖中每對頂點之間都恰有一條邊的簡單圖。已知無向完全圖 g 有 7 個頂點，則它共有（ ）條邊。a、7b、21c、42d、496、寄存器是（ ）的重要組成部分。a、硬盤b、高速緩存c、內(nèi)存d、中央處理器（cpu）7、如果根結(jié)點的深度記為 1，則一棵恰有 2011 個葉結(jié)點的二叉樹的深度最少是（ ）。a、10b、11c、12d、138、體育課的鈴聲響了，同學(xué)

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

4、不正確的，只要在硬盤上出現(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、o(n log n)14、生物特征識別，是利用人體本身的生物特征進行身份認證的一種技術(shù)。目前

5、，指紋識別、虹膜識別、人臉識別等技術(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、1b、2c、3d、416、關(guān)于匯編語言，下列說法錯誤的是（ ）。a、是一種與具體硬件相關(guān)的程序設(shè)計語言b、在編寫復(fù)雜程序時，相對于高級語言而言代碼量較大，且不易調(diào)試c、可以直接訪問寄存器、內(nèi)存單

6、元、以及 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、貪心法18、1956 年（ ）授予肖克利（william shockley）、巴丁（john bardeen）和布拉頓（walter brattain），以表彰他們對半導(dǎo)體的研究和晶體管效應(yīng)的發(fā)現(xiàn)。a、諾貝爾物理學(xué)獎b、約翰馮諾依曼獎c、圖靈獎d、高德納獎（donald e. knuth prize）19、對一個有向圖而言，如果每個節(jié)點都存在到達其他任何節(jié)點

7、的路徑，那么就稱它是強連通的。例如，右圖就是一個強連通圖。事實上，在刪掉邊（ ）后，它依然是強連通的。a、ab、bc、cd、d20、從 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)一個序列號含有偶數(shù)個 1 時，它才是有效的。例如，00000000、01010011 都是有效的序列號，而 11111110 不是。那么，有效的序列號共有_個。2、定義字符

8、串的基本操作為：刪除一個字符、插入一個字符和將一個字符修改成另一個字符這三種操作。將字符串 a 變成字符串 b 的最少操作步數(shù)，稱為字符串 a 到字符串 b 的編輯距離。字符串a(chǎn)bcdefg到字符串badecg的編輯距離為_。三、閱讀程序?qū)懡Y(jié)果（共 4 題，每題 8 分，共計 32 分）1、#include using namespace std;int main() int i, n, m, ans; cin n m; i = n; ans = 0; while(i = m) ans += i; i+; cout ans endl; return 0;輸入：10 20輸出：_2、#inclu

9、de #include using namespace std;int main() string map = 22233344455566677778889999; string tel; int i; cin tel; for(i = 0; i = 0) & (teli = 9) cout = a) & (teli = z) cout mapteli - a; cout endl; return 0;輸入：ccf-noip-2011輸出：_3、#include #include using namespace std;const int size = 100;int main() int

10、n, i, sum, x, asize; cin n; memset(a, 0, sizeof(a); for(i = 1; i x; ax+; i = 0; sum = 0; while(sum (n / 2 + 1) i+; sum += ai; cout i endl; return 0;輸入：114 5 6 6 4 3 3 2 3 2 1輸出：_4、#include using namespace std;int solve(int n, int m) int i, sum; if (m = 1) return 1; sum = 0; for (i = 1; i nm; coutsol

11、ve(n, m)endl; return 0;輸入：7 4輸出：_四、完善程序（前 11 空，每空 2 分，后 2 空，每空 3 分，共計 28 分）1、（子矩陣）輸入一個n1*m1的矩陣a，和n2*m2的矩陣b，問a中是否存在子矩陣和b相等。若存在，輸出所有子矩陣左上角的坐標(biāo)；若不存在輸出“there is no answer”。#include using namespace std;const int size = 50;int n1, m1, n2, m2, asizesize, bsizesize;int main() int i, j, k1, k2; bool good, hav

12、eans; cin n1 m1; for(i = 1; i = n1; i+) for(j = 1; j aij; cin n2 m2; for(i = 1; i = n2; i+) for(j = 1; j = m2; j+) _; haveans = false; 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 = false; if(good)

13、 cout i j endl; _; if(!haveans) cout there is no answer endl; return 0;2、（大整數(shù)開方）輸入一個正整數(shù)n（1n10100），試用二分法計算它的平方根的整數(shù)部分。#include #include using namespace std;const int size = 200;struct hugeint int len, numsize;/其中 len 表示大整數(shù)的位數(shù)；num1表示個位、num2表示十位，以此類推hugeint times(hugeint a, hugeint b)/計算大整數(shù) a 和 b 的乘積 in

14、t 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+) _ += 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

15、, 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;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(an

16、s.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;bool over(hugeint a, hugeint b)/若大整數(shù) ab 則返回 true，否則返回 false in

17、t i; if(_) return false; if(a.len b.len) return true; for(i = a.len; i = 1; i-) if(a.numi b.numi) return true; return false;int main() string s; int i; hugeint target, left, middle, right; cin s; memset(target.num, 0, sizeof(target.num); target.len = s.length(); for(i = 1; i = 1; i-) cout left.numi; cout bij （或scanf(%d, &bij或scanf(%d, bi +