做題：https://ti.luogu.com.cn/problemset/1003

選擇題

第 1 題
微型計算機中，控制器的基本功能是（ A）。

A. 控制機器各個部件協(xié)調(diào)工作
B. 實現(xiàn)算術運算和邏輯運算
C. 獲取外部信息
D. 存放程序和數(shù)據(jù)

注：控制器直接找“控制”

第 2 題
設A=true，B=false，C=true，D=false，以下邏輯運算表達式值為真的是（ B）。

A. (A∧B)∨(C∧D∨ -A)
B. ((A∧B)∨C)∧ -D
C. (B∨C∨D)∧D∧A
D. A∧(D∨ C)∧B

注：∧為與，∨為或，補充一下￢是為邏輯非

符號提供：? ￢ ∧ ∨

第 3 題
在下列關于圖靈獎的說法中，不正確的是（ C）。

A. 圖靈獎是美國計算機協(xié)會于1966年設立的，專門獎勵那些對計算機事業(yè)作出重要貢獻的個人
B. 圖靈獎有“計算機界諾貝爾獎”之稱
C. 迄今為止，還沒有華裔計算機科學家獲此殊榮
D. 圖靈獎的名稱取自計算機科學的先驅(qū)、英國科學家阿蘭·圖靈

注：對圖靈獎的了解不深沒關系，但是一定要記住中國人是獲得過圖靈獎的！此人名叫姚期智，2000年圖靈獎！

第 4 題
計算機在工作過程中，若突然停電，（C ）中的信息不會丟失。

A. ROM和RAM
B. CPU
C. ROM
D. RAM

注：CPU必丟，下面是RAM和ROM的介紹，另外提一句

---

RAM、ROM、Cache

引：百度百科、https://blog.csdn.net/qq_30146831/article/details/107291969。

可以保存數(shù)據(jù)的還有CD、U盤、硬盤等。

第 5 題
完全二叉樹共有$2N?1$個結點，則它的葉節(jié)點數(shù)是（ B）。

A. $N?1$
B. $N$
C. $2N$
D. $2^N?1$

注：

很簡單，你可以帶入一個簡單的例子試試，例如深度為3的滿二叉樹有7個節(jié)點，有4個葉節(jié)點.并且這也是一個性質(zhì)。

第 6 題
在以下各項中，（ D）不是操作系統(tǒng)軟件。

A. Solaris
B. Linux
C. Windows Vista
D. Sybase

注：Vista和Linux肯定是，而Solaris很多人不知道，但是Sybase是一種數(shù)據(jù)庫

sybase 美國Sybase公司研制的一種關系型數(shù)據(jù)庫系統(tǒng)

第 7 題
設棧S的初始狀態(tài)為空，元素a，b，c，d，e，f依次入棧S，出棧的序列為b，d，f，e，c，a，則棧S的容量至少應該是（ C）。

A. 6
B. 5
C. 4
D. 3

注：這么幾個數(shù)，手推都行了。

第 8 題
與十進制數(shù)28.5625相等的四進制數(shù)是（ ）。

A. 123.21
B. 131.22
C. 130.22
D. 130.21

注：四進制，大同小異也。尤其注意小數(shù)位處理，二進制是乘二取整，那么四進制也就是乘四取整。

如果不知道小數(shù)位的處理方法可以百度。

分為（1）十進制轉(zhuǎn)四進制使用短除加乘四取整（2）四進制轉(zhuǎn)十進制使用逐個乘方，注意小數(shù)位的負次方。

此題為（1）方法。

如下手稿：（字丑勿噴）

第 9 題
設字符串S=“Olympic”，S的非空子串的數(shù)目是（ A）。

A. 28
B. 29
C. 16
D. 17

注：字符串本身也是子串，所以結果就是7+6+5+4+3+2+1=28

第 10 題
Web2.0是近年來互聯(lián)網(wǎng)的熱門概念之一，其核心思想是互動與分享。下列網(wǎng)站中，（ B）是典型的Web2.0應用。

A. Sina
B. Flickr
C. Yahoo
D. Google

注：我一開始把Sina想成了微博，以為也是Web2.0，結果非也。

第 11 題
遞歸過程或函數(shù)調(diào)用時，處理參數(shù)和返回地址，通常使用一種稱為（ D）的數(shù)據(jù)結構。

A. 隊列
B. 多維數(shù)組
C. 線性表
D. 棧

注：記住搭配——遞歸對棧

第 12 題
$(2008{)}_{10}+(5B{)}_{16}$的結果是（ A）。

A. $(833{)}_{16}$
?
B. $(2089{)}_{10}$
?
C. $(4163{)}_8$
?
D. $(100001100011{)}_2$

注：都轉(zhuǎn)換成10進制相加，然后再判斷就行。

轉(zhuǎn)換成十進制相加的結果是2099.

第 13 題
二叉樹T，已知其先根遍歷是1 2 4 3 5 7 6（數(shù)字為結點的編號，以下同），中根遍歷是2 4 1 5 7 3 6，則該二叉樹的后根遍歷是（ B）。

A. 4 2 5 7 6 3 1
B. 4 2 7 5 6 3 1
C. 7 4 2 5 6 3 1
D. 4 2 7 6 5 3 1

注：

資料放在這了：先序遍歷、后序遍歷、中序遍歷：https://blog.csdn.net/qq_34840129/article/details/80619761

看懂了咱們就畫樹。

首先從先序遍歷知道根是1。于是在中序遍歷的數(shù)列中按照1劃分可以找出左子樹和右子樹。

即2,4為左子樹，5,7,3,6為右子樹。

左子樹容易處理，右子樹還是按照先序遍歷找根，在中序遍歷中劃分的策略行進。

………………

結果如下

接著，后序遍歷就出來了。為4 2 7 5 6 3 1。

第 14 題
將數(shù)組{8, 23, 4, 16, 77, -5, 53, 100}中的元素按從大到小的順序排列，每次可以交換任意兩個元素，最少需要交換（ B）次。

A. 4
B. 5
C. 6
D. 7

注：很明顯的選擇排序，手算就行。

下面是從小到大的，都一樣。

第一次 77 和53交換 8 23 4 16 53 -5 77 100 第二次 53 和-5交換 8 23 4 16 -5 53 77 100 第三次 23 和-5交換 8 -5 4 16 23 53 77 100 第四次 8 與4交換 4 -5 8 16 23 53 77 100 第五次 4與-5 交換 -5 4 8 16 23 53 77 100 （每次從前面（未排好序的元素）選取最大的元素進行交換）

第 15 題
對有序數(shù)組{5, 13, 19, 21, 37, 56, 64, 75, 88，92，100}進行二分查找，成功查找元素19的查找長度（比較次數(shù)）是（ B）。

A. 1
B. 2
C. 3
D. 4

注：二分查找，寫代碼寫的多了很快就算出來了。

首先l = 0, r = 11 - 1 = 10; mid = arr[(l + r)/ 2]; 判斷大了 r = mid; // 一次 mid = arr[(l + r)/ 2]; mid=19 判斷正好; //兩次 結束

第 16 題
面向?qū)ο蟪绦蛟O計（Object-Oriented Programming）是一種程序設計的方法論，它將對象作為程序的基本單元，將數(shù)據(jù)和程序封裝在對象中，以提高軟件的重用性、靈活性和擴展性。下面關于面向?qū)ο蟪绦蛟O計的說法中，不正確的是（ A）。

A. 面向?qū)ο蟪绦蛟O計通常采用自頂向下設計方法進行設計。
B. 面向?qū)ο蟪绦蛟O計方法具有繼承性（inheritance）、封裝性（encapsulation）、多態(tài)性（polymorphism）等幾大特點。
C. 支持面向?qū)ο筇匦缘恼Z言稱為面向?qū)ο蟮木幊陶Z言，目前較為流行的有C++、JAVA、C#等。
D. 面向?qū)ο蟮某绦蛟O計的雛形來自于Simula語言，后來在SmallTalk語言的完善和標準化的過程中得到更多的擴展和對以前思想的重新注解。至今，SmallTalk語言仍然被視為面向?qū)ο笳Z言的基礎。

注：不要以為字數(shù)多就難了，A就是錯的，誰說寫個C++還要自頂向下了？！我寫完主函數(shù)再寫函數(shù)不行嗎？

第 17 題
在32*32點陣的“字庫”中，漢字“北”與“京”的字模占用字節(jié)數(shù)之和是（ B）。

A. 512
B. 256
C. 384
D. 128

注：字符編碼，《信息學奧賽一本通：初賽篇》有講到

$32\times 32\times 2=2048$
$2048÷8=256$

第 18 題
設T是一棵有n個頂點的樹，下列說法不正確的是（ A）。

A. T有n條邊
B. T是連通的
C. T是無環(huán)的
D. T有n-1條邊

注：

很明顯，就是在A和D里面選一個。那么就選D，這是定理，不管幾叉樹、什么樹。

而且樹是無環(huán)、連通的。

第 19 題
下列不屬于NOIP競賽推薦使用的語言環(huán)境的是（ B）。

A. Dev-C++
B. Visual C++
C. free pascal
D. Lazarus

注：

第 20 題
在C++程序中，表達式200|10的值是（ D）。

A. 20
B. 1
C. 220
D. 202

注：就是一個進制轉(zhuǎn)換+邏輯運算
$(200{)}_{10}=(11001000{)}_2$
$(10{)}_{10}=(1010{)}_2$
$1010|11001000=11001010$
$(11001010{)}_2=(202{)}_{10}$

問題求解

第一題

書架上有4本不同的書A、B、C、D。其中A和B是紅皮的，C和D是黑皮的。把這4本書擺在書架上，滿足所有黑皮的書都排在一起的擺法有__12__種。滿足 A必須比C靠左，所有紅皮的書要擺放在一起，所有黑皮的書要擺放在一起，共有__4__種擺法。

注：

第一空：捆綁法$P{}_3^3\times 2=12$

第二空：模擬都出來了。

ABCD、ABDC、BACD、BADC完事。

第二題

有6個城市，任何兩個城市之間都有一條道路連接，6個城市兩兩之間的距離如下表所示，則城市1到城市6的最短距離為______7______。

我的推理思路是倒著推，先看離6最近的是5，權值2。

繼續(xù)看離5最近的2，權值3。

離2最近的也就是1了，權值2。

最后，總共7。

閱讀程序?qū)懡Y果

1

#include<iostream> using namespace std; int main() {int i, a, b, c, d, f[4];for(i = 0; i < 4; i++) cin >> f[i];a = f[0] + f[1] + f[2] + f[3];a = a / f[0];b = f[0] + f[2] + f[3];b = b / a;c = (b * f[1] + a) / f[2];d = f[(b / c ) % 4];if(f[(a + b + c + d) % 4] > f[2])cout << a + b<< endl;else cout << c + d << endl;return 0; }

輸入：9 19 29 39

正確答案： 23

2

#include<iostream> using namespace std; void foo(int a, int b, int c) {if(a > b) foo(c, a, b);elsecout<<a<<','<<b<<','<<c<<endl; } int main() {int a, b, c;cin >> a >> b >> c;foo(a, b, c);return 0; }

輸入: 3 1 2

正確答案： 2,3,1

3

#include <iostream> using namespace std;void func(int ary[], int n ) {int i=0, j, x;j=n-1;while(i<j){while (i<j&&ary[i]>0) i++;while (i<j&&ary[j]<0) j--;if (i<j){x=ary[i];ary[i++]=ary[j];ary[j--]=x;}} }int main() {int a[20], i, m;m=10;for(i=0; i<m; i++){cin>>a[i];}func(a, m);for (i=0; i<m; i++)cout<<a[i]<<" ";cout<< endl;return 0; }

輸入：5 4 -6 -11 6 -59 22 -6 1 10

正確答案： 5 4 10 1 6 22 -59 -6 -11 -6

4

#include<iostream> #include<cstring> using namespace std;#define MAX 100 void solve(char first[], int spos_f, int epos_f, char mid[], int spos_m, int epos_m) {int i, root_m;if(spos_f > epos_f)return;for(i = spos_m; i <= epos_m; i++)if(first[spos_f] == mid[i]){root_m = i;break;}solve(first, spos_f + 1, spos_f + (root_m - spos_m), mid, spos_m, root_m - 1);solve(first, spos_f + (root_m - spos_m) + 1, epos_f, mid, root_m + 1, epos_m);cout << first[spos_f]; }int main() {char first[MAX], mid[MAX];int len;cin >> len;cin >> first >> mid;solve(first, 0, len - 1, mid , 0, len - 1); cout << endl;return 0; }

輸入：

7 ABDCEGF BDAGECF

正確答案： DBGEFCA

完善程序

1

第 27 題
完善程序：
（字符串替換）給定一個字符串S（S僅包含大小寫字母），下面的程序?qū)中的每個字母用規(guī)定的字母替換，并輸出S經(jīng)過替換后的結果。程序的輸入是兩個字符串，第一個字符串是給定的字符串S，第二個字符串S’由26個字母組成，它是a-z的任一排列，大小寫不定，S’規(guī)定了每個字母對應的替換字母：S’中的第一個字母是字母A和a的替換字母，即S中的A用該字母的大寫替換，S中的a用該字母的小寫替換；S’中的第二個字母是字母B和b的替換字母，即S中的B用該字母的大寫替換，S中的b用該字母的小寫替換；…… 以此類推。

#include <iostream> #include <string.h> char change[26], str[5000]; using namespace std;void CheckChangeRule() {int i;for (i = 0;i < 26;i ++){if ( [ ① ] )change[i] -= 'A' - 'a';} }void ChangeString() {int i;for (i = 0;i <strlen(str);i ++){if ( [ ② ] )str[i] = change[str[i] - 'A'] -'a' + 'A';else[ ③ ] } }int main() {int i; cin >> str ;cin >> change;CheckChangeRule();[ ④ ] cout << str << endl;return 0; }

2

完善程序：

(找第k大的數(shù)) 給定一個長度為1,000,000的無序正整數(shù)序列, 以及另一個數(shù)n (1<=n<=1000000), 然后以類似快速排序的方法找到序列中第n大的數(shù)（關于第n大的數(shù)：例如序列{1，2，3，4，5，6}中第3大的數(shù)是4）。

#include <iostream> using namespace std;int a[1000001],n,ans = -1; void swap(int &a,int &b) {int c;c = a; a = b; b = c; }int FindKth(int left, int right, int n) {int tmp,value,i,j;if (left == right) return left;tmp = rand()% (right - left) + left;swap(a[tmp],a[left]);value =[ ① ];i = left;j = right;while (i < j){while (i < j && [ ② ]) j --;if (i < j) {a[i] = a[j]; i ++;} else break;while (i < j && [ ③ ]) i ++;if (i < j) {a[j] = a[i]; j - -;} else break;}[ ④ ] if (i < n) return FindKth([ ⑤ ] );if (i > n) return [ ⑥ ] return i; }int main() {int i;int m = 1000000;for (i = 1;i <= m;i ++)cin >> a[i];cin >> n;ans = FindKth(1,m,n);cout << a[ans];return 0; }

?

總結

以上是生活随笔為你收集整理的NOIP 2008 普及组初赛试题 解题报告、题解及选择题思路，高质量的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。