第十六屆全國青少年信息學奧林匹克聯(lián)賽初賽試題

1、第十六屆全國青少年信息學奧林匹克聯(lián)賽初賽 試題普及組 C+ 語言兩小時完成?全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效?、單項選擇題共20 題，每題 1.5 分，共計30 分。每題有且僅有一個正確選項。以上都有可能3 以下邏輯表達式的值恒為真的是 (A. P V (?P A Q) V (?P A ?Q) B. Q C. P V QV (P A ?Q) V (?P A Q) D. P)。V (?P A Q) V (P A ?Q)V ?QV (P A ?Q) V (?P A ?Q)1 2E+03 表示()。D. 2000A. 2.03 B. 5 C. 8 2 一個字節(jié) byte 由 個二

2、進制位組成。A. 8 B. 16 C. 32 D.4 Linux 下可執(zhí)行文件的默認擴展名為 A. exe B. com C. dllD.以上都不是5如果樹根算第A. 2 n -11 層，那么一棵 n 層的二叉樹最多有B. 2C. 2n+1個結點D. 2n+16提出“存儲程序的計算機工作原理的是馮?諾依曼A. 克勞德 ?香農 B. 戈登?摩爾 C.查爾斯?巴比奇 D.XY + ZX = XYX 在三進制下成立，C+ 語言都屬于8 Pascal 語言、 C 語言和腳本語言 C. 。A. 面向對象語言 B.解釋性語言 D.A. YXZ B. ZXY C. XYZ D. XZY7設 X、Y、Z 分別

3、代表三進制下的一位數字，假設等式 那么同樣在三進制下，等式 XY * ZX = 也成立。編譯性語言9前綴表達式“ + 3 * 2 + 5 12 的值是 A. 23 B. 25 C. 37 D. 6510 主存儲器的存取速度比中央處理器ePU迎訪的工作速度慢得多/a從而使得后者的效率受到影響。而根據局部性原理，CPU所訪問的存儲單歡送常都趨于聚集在一個較小的連續(xù)區(qū)域中。于是，為了提高系統(tǒng)整體的執(zhí)行效率，在CPU中引入了。歡送訪問NOI網站/aA.存放器B.高速緩存C.閃存D.外存11 . 一個字長為8位的整數的補碼是 11111001，那么它的原碼是。A. 00000111B.01111001C

4、.11111001D.10000111A. gn) B.卸log n )C.g(log n)D.g(n )13 .一個自然數在十進制下有n位，那么它在1進制下的位數與最接近。A. 5n B. n*log210 C.10*log2nD. 10nlog 2n12 .基于比擬的排序時間復雜度的下限是，其中n表示待排序的元素個數。14 .在以下 HTML語句中，可以正確產生一個指向NOI官方網站的超鏈接的是)A. <a url=" :/ noi ">B. <a href=" :/ noi ">C. <a> :/ noi <

5、;/a>D. <a name=" :/ noi ">15 .元素 R1、R2、R3、R4、R5入棧的順序為 R1、R2、R3、R4、R5。如果第1個出棧的 是R3 ,那么第5個出棧的不可能是。A. R1B. R2C. R4D. R516 .雙向鏈表中有兩個指針域llink和rlink，分別指向該結點的前驅及后繼。設p指向 鏈表中的一個結點，它的左右結點均非空?，F(xiàn)要求刪除結點p，那么下面語句序列中錯誤的選項是()。A. p->rlink->llink = p->rlink;p->lli nk->rl ink = p->ll

6、i nk; delete p;B. p->llink->rlink = p->rlink;p->rl in k->lli nk = p->lli nk; delete p;C. p->rlink->llink = p->llink;p->rli nk->lli nk->rli nk = p->rli nk; delete p;D. p->llink->rlink = p->rlink;p->lli nk->rli nk->lli nk = p->lli nk; delete

7、p;ABCDEFG ,后序遍歷序列是 CBFEGDA，那么根結點的左17 . 一棵二叉樹的前序遍歷序列是 子樹的結點個數可能是。A. 2B. 3C. 4D. 518 關于拓撲排序，下面說法正確的選項是 。A. 所有連通的有向圖都可以實現(xiàn)拓撲排序B. 對同一個圖而言，拓撲排序的結果是唯一的C. 拓撲排序中入度為 0 的結點總會排在入度大于 0 的結點的前面D. 拓撲排序結果序列中的第一個結點一定是入度為 0 的點19 完全二叉樹的順序存儲方案，是指將完全二叉樹的結點從上至下、從左至右依次存放 到一個順序 結構的數組中。假定根結點存放在數組的 1 號位置，那么第 k 號結點的父結點如 果存在的話，

8、應當存放 在數組的 號位置。A. 2k B. 2k+1 C. k/2 下取整 D. k+1 /2 下取整A. 教育 部 B.20 全國青少年信息學奧林匹克系列活動的主辦單位是 。 共青團中央 D. 中國計算機學會、問題求解共 2 題，每題 5 分，共計 10 分1LZW 編碼是一種自適應詞典編碼。在編碼的過程中，開始時只有一部根底構造元素的編碼詞典， 如果在編碼的過程中遇到一個新的詞條， 那么該詞條及一個新的編碼會被追加到詞典 中，并用于后繼信息 的編碼。舉例說明，考慮一個待編碼的信息串： "xyx yy yy xyx" 。初始詞典只有 3 個條目， 第一個為 x ， 編碼

9、為1 ;第二個為y，編碼為2 ;第三個為空格，編碼為3 ;于是串"xyx"的編碼為 1-2-1 其中 - 為編碼分隔符 ，加上后面的一個空格就是1-2-1-3 。但由于有了 一個空格，我們就知道前面的 "xyx" 是一個單詞， 而由于該單詞沒有在詞典中，我們就可以 自適應的把這個詞條添加到詞典里，編碼為 4 ，然后按照新的詞典對后繼信息進行編碼，以 此類推。于是，最后得到編碼： 1-2-1-3-2-2-3-5-3-4?，F(xiàn)在初始詞典的 3 個條目如上述，那么信息串 "yyxy xx yyxy xyx xx xyx"的編碼是 。2隊列快照

10、是指在某一時刻隊列中的元素組成的有序序列。例如，當元素1 、2、3 入隊，元素1 出隊后， 此刻的隊列快照是 "2 3"。當元素2 、3也出隊后，隊列快照是 "" ，即為空。 現(xiàn)有3 個正整數元素依次入隊、出隊。它們的和為 8，那么共有 種可能的不同的隊列快照不同隊列的相同快照只計一次。例如，"5 1" 、"4 2 2"、"" 都是可能的隊列快照 ;而 "7" 不是可能的隊列快照，因為剩下的 2 個正整數的和不可能是1。三、閱讀程序寫結果共 4 題，每題 8 分，其中第 4

11、題1 、 2各4 分，共計 32 分1#include <iostream> using namespace std;void swap(int & a, int & b)int t;t = a;a = b;b = t;int main()int a1, a2, a3, x;cin>>a1>>a2>>a3;if (a1 > a2) swap(a1, a2);if (a2 > a3) swap(a2, a3);if (a1 > a2) swap(a1, a2);cin>>x;if (x < a2)

12、 if (x < a1)cout<<x<<' '<<a1<<' '<<a2<<' '<<a3<<endl; elsecout<<a1<<' '<<x<<' '<<a2<<' '<<a3<<endl;elseif (x < a3)cout<<a1<<' '<

13、;<a2<<' '<<x<<' '<<a3<<endl; elsecout<<a1<<' '<<a2<<' '<<a3<<' '<<x<<endl;return 0;輸入:91 2 20 77輸出：2 .#in elude <iostream>using n amespace std;int rSum(i n t j)int sum = 0;w

14、hile (j != 0) sum = sum * 10 + (j % 10);j=j/10 ；return sum;int mai n()int n, m, i;cin?n?m;for (i = n; i < m; i+) if (i = rSum(i) cout<<i<<" return 0;輸入：90 120輸出：3.#in elude <iostream>#i n elude <stri ng> using n amespace std;int mai n()stri ng s;char ml, m2;int i;getl

15、 in e(c in, s);ml =''m2 =''for (i = 0; i < sen gth(); i+)if (si > ml) m2 = ml;ml = si;else if (si > m2)m2 = si;cout< <in t(m1)vv' 'vvin t(m2)<<e n dl; return 0;輸入：Expo 2021 Sha nghai China輸出：提示：字符空格'O''A''a'ASCII 碼324865974 .#in cl

16、ude <iostream>using n amespace std;con st int NUM = 5;int r(i nt n)int i;if (n <= NUM) return n;for (i = 1; i <= NUM; i+) if (r(n - i) < 0) return i; return -1;int main()int n;cin>>n;coutvvr (n) <<endl;return 0;1輸入：7輸出： 4 分2輸入：16輸出： 4 分四、完善程序前 4空，每空2.5分，后6空，每空3分，共計28 分1 .哥

17、德巴赫猜測 哥德巴赫猜測是指，任一大于 2的偶數都可寫成兩個質數之和。迄今 為止， 仍然是一個著名的世界難題，被譽為數學王冠上的明珠。試編寫程序，驗證任一大于2且不超過n的偶數都能寫成兩個質數之和。#in elude <iostream> using n amespace std;int main()const int SIZE = 1000;int n, r, pSIZE, i, j, k, ans; bool tmp;cin>>n;r = 1;p1 = 2;for (i = 3; i <= n; i+) ；=0) for (j = 1; j <= r;

18、j+) if (i %tmp = false; break;if (tmp) r+;；ans = 0;for (i = 2; i <= n / 2; i+) tmp = false;for (j = 1; j <= r; j+)for (k = j; k <= r; k+) if (i + i =tmp = true; break;if (tmp)an s+;coutvva n s<<e n dl;return 0;假設輸入n為2021，那么輸出滿足哥德巴赫猜測。時表示驗證成功，即大于 2且不超過2021的偶數都2 ?過河問題在一個月黑風高的夜晚，有一群人在河的右

19、岸，想通過唯一的一根獨木橋走到河的左岸。在這伸手不見五指的黑夜里，過橋時必須借助燈光來照明，很不幸的是，他 們只有一盞燈。另外，獨木橋上最多承受兩個人同時經過，否那么將會坍塌。每個人單獨過橋都需要一定的時間，不同的人需要的時間可能不同。兩個人一起過橋時，由于只有一盞燈，所以需要的時間是較慢的那個人單獨過橋時所花的時間。現(xiàn)輸入n 2wn 100 和這n個人單獨過橋時需要的時間，請計算總共最少需要多少時間，他們才能全部到達河的左岸。例如，有3個人甲、乙、丙，他們單獨過橋的時間分別為1、2、4，那么總共最少需要的時間為7。具體方法是：甲、乙一起過橋到河的左岸，甲單獨回到河的右岸將燈帶回，然后甲、丙再

20、起過橋到河的左岸，總時間為2+1+4=7。#in elude <iostream> using n amespace std;const int SIZE = 100;const int INFINITY = 10000;const bool LEFT = true;const bool RIGHT = false;const bool LEFT_TO_RIGHT = true; const bool RIGHT_TO_LEFT = false;int n, hourSIZE; bool posSIZE;int max(i nt a, i nt b)if (a > b)return a;else return b;in