第二十一屆全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽提高組初賽試題精編版

1、最新資料推薦2015 年第二十一屆全國(guó)青少年信息學(xué)奧林匹克競(jìng)賽初賽 提高組一、選擇題（共 15 題，每題 1.5 分）1、在計(jì)算機(jī)內(nèi)部用來傳送、存貯、加工處理的數(shù)據(jù)或指令都是以（）形式進(jìn)行的。二進(jìn)制碼 B. 八進(jìn)制碼 C. 十進(jìn)制碼 D. 智能拼音碼2、下列說法正確的是（）CPU 的主要任務(wù)是執(zhí)行數(shù)據(jù)運(yùn)算和程序控制存儲(chǔ)器具有記憶能力，其中信息任何時(shí)候都不會(huì)丟失兩個(gè)顯示器屏幕尺寸相同，則它們的分辨率必定相同個(gè)人用戶只能使用 Wifi 的方式連接到 Internet3、與二進(jìn)制小數(shù)0.1 相等的十六進(jìn)制數(shù)是（）0.8 B. 0.4 C. 0.2 D. 0.14、下面有四個(gè)數(shù)據(jù)組，每個(gè)組各有三個(gè)數(shù)據(jù)

2、，其中第一個(gè)數(shù)據(jù)為八進(jìn)制數(shù)，第二個(gè)數(shù)據(jù)為十進(jìn)制數(shù)，第三個(gè) 數(shù)據(jù)為十六進(jìn)制數(shù)。這四個(gè)數(shù)據(jù)組中三個(gè)數(shù)據(jù)相同的是（）A. 120 82 50 B. 144 100 68 C. 300 200 C8 D. 1762 1010 3F25、線性表若采用鏈表存儲(chǔ)結(jié)構(gòu)，要求內(nèi)存中可用存儲(chǔ)單元地址（）A. 必須連續(xù) B. 部分地址必須連續(xù) C. 一定不連續(xù) D. 連續(xù)不連續(xù)均可6、 今有一空棧S,對(duì)下列待進(jìn)棧的數(shù)據(jù)元素序列a,b,c,d,e,f依次進(jìn)行進(jìn)棧，進(jìn)棧，出棧，進(jìn)棧，進(jìn)棧，出棧的操作，則此操作完成后，棧S的棧頂元素為（）A. f B. c C. aD. b7、前序遍歷序列與后序遍歷序列相同的二叉樹為（）

3、A. 非葉子結(jié)點(diǎn)只有左子樹的二叉樹 B. 只有根結(jié)點(diǎn)的二叉樹C. 根結(jié)點(diǎn)無右子樹的二叉樹 D. 非葉子結(jié)點(diǎn)只有右子樹的二叉樹8、如果根的高度是 1，具有 61 個(gè)結(jié)點(diǎn)的完全二叉樹的高度是（）A. 5B. 6C. 7D. 89、6 個(gè)頂點(diǎn)的連通圖的最小生成樹，其邊數(shù)為（）A. 6B. 5C. 7D. 410、 設(shè)某算法的計(jì)算時(shí)間表示為遞推關(guān)系式T（n）=T（n-1）+n （n為正整數(shù)）及T（0）=1，則該算法的時(shí)間復(fù)雜度為 （）2A. O（logn） B. O（nlogn） C. O（n）D. O（n2）11、 具有n個(gè)頂點(diǎn)，e條邊的圖采用鄰接表存儲(chǔ)結(jié)構(gòu)，進(jìn)行深度優(yōu)先遍歷和廣度優(yōu)先遍歷運(yùn)算的時(shí)間

4、復(fù)雜度均 為（）A. O（n2） B. O（e2） C. O（ne） D.O（n+e）12、 在數(shù)據(jù)壓縮編碼的應(yīng)用中，哈夫曼（Huffman ）算法是一種采用了（）思想的算法。A. 貪心 B. 分治 C. 遞推 D. 回溯13、 雙向鏈表中有兩個(gè)指針域，llink 和 rlink ，分別指向前戲及后繼，設(shè) p 指向鏈表中的一個(gè)結(jié)點(diǎn)， q 指向一 待插入結(jié)點(diǎn)，現(xiàn)要求在 p前插入q,則正確的插入為（）p-llink=q; q-rlink=p; p-llink-rlink=q;q-llink=p-llink;q-llink=p-llink; p-llink-rlink=q; q-rlink=p; p

5、-llink-q-rlink;q-rlink=p; p-rlink=q; p-llink-rlink=q;q-rlink=p;p-llink-rlink=q; q-rlink=p; q-llink=p-llink; p-link=q;14、對(duì)圖 G 中各個(gè)結(jié)點(diǎn)分別指點(diǎn)一種顏色,使相鄰結(jié)點(diǎn)顏色不同,則稱為圖G 的一個(gè)正常著色。正常著色圖G 所必需的最少顏色數(shù),稱為 G 的色數(shù)。那么下圖的色數(shù)是（） 。最新資料推薦A. 3 B. 4 C. 5 D. 615、在NOI系列賽事中參賽選手必須使用由承辦單位統(tǒng)一提供的設(shè)備。下列物品中不色誘選手自帶的是（）A.鼠標(biāo) B.筆 C.身份證 D.準(zhǔn)考證二、不定項(xiàng)

6、選擇題1、以下屬于操作系統(tǒng)的有（）A. Win dows XPB. UNIX C. Li nuxD. Mac OS2、下列屬于視頻文件格式的有（）A. AVI B. MPEG C. WMVD. JPEG3、 下列選項(xiàng)不是正確的IP地址的有（）A. 202.300.12.4B. 192.168.0.3 C. 100:128:35:91D. 111-132-35-214、下列有關(guān)樹的敘述中，敘述正確的有（）在含有n個(gè)結(jié)點(diǎn)的樹中，邊數(shù)只能是（n-1）條在哈夫曼樹中，葉結(jié)點(diǎn)的個(gè)數(shù)比非葉結(jié)點(diǎn)個(gè)數(shù)多1完全二叉樹一定是滿二叉樹在二叉樹的前序序列中，若結(jié)點(diǎn) u在結(jié)點(diǎn)v之前，則u 定是v的祖先5、以下圖中一定可

7、以進(jìn)行黑白染色的有（）。（黑白染色：為各個(gè)結(jié)點(diǎn)分別指定黑白兩種顏色之一，使用相鄰結(jié)點(diǎn)顏色不同。）A.二分圖 B.完全圖 C.樹D.連通圖三、問題求解1、 在1和2015之間（包括1和2015在內(nèi)）不能被4、5、6三個(gè)數(shù)任意一個(gè)整除的數(shù)有 個(gè)。2、 結(jié)點(diǎn)數(shù)為5的不同形態(tài)的二叉樹一共有 種。（結(jié)點(diǎn)數(shù)為2的二叉樹一共有2種：一種是根結(jié)點(diǎn)和左 兒子，另一種是根結(jié)點(diǎn)和右兒子。）四、閱讀程序?qū)懡Y(jié)果1、#include using n amespace std;struct poi ntint x;int y;；int mai n（）struct EXint a;int b; poi nt c;e;e.a=

8、1;e.b=2;e.c.x=e.a+e.b;e.c.y=e.a*e.b;coute.c.x ,e.c.yendl;return 0;輸出：最新資料推薦2、 #include using namespace std; void fun(char *a,char *b) a=b;(*a)+;int main()char c1,c2,*p1,*p2; c1=A;c2=a;p1=&c1;p2=&c2; fun(p1,p2); coutc1c2endl;return 0;3、#include #include using namespace std; int main()int len,maxlen;

9、string s,ss;maxlen=0;docinss; len=ss.length(); if (ss0= #) break;if(lenmaxlen) s=ss; maxlen=len;while(true); coutsendl;return 0; 輸入：I am a citizen ofChina#最新資料推薦輸出：4、#inelude using n amespace std;int fun (i ntn, int fromPos, int toPos)int t,tot;if (n=0)return 0;for (t=1;t=3;t+)if (t!=fromPos & t!=to

10、Pos)break;tot=0;tot+=fu n(n-1,fromPos,t);tot+;tot+=fu n(n-1,t,toPos);return tot;int mai n() int n;cinn;coutfu n(n ,1,3)e ndl;return 0;輸入：5輸出：五、完善程序1、(雙子序列最大和)給定一個(gè)長(zhǎng)度為n(3=n=1000)的整數(shù)序列，要求從中選出兩個(gè)連續(xù)子序列，使得這兩個(gè)連續(xù)子序列的序列和之和最大，最終只需輸出這個(gè)最大和。一個(gè)連續(xù)子序列的序列和為該連續(xù)子序列中所有數(shù)之和。要求：每個(gè)連續(xù)子序列長(zhǎng)度至少為1,且兩個(gè)連續(xù)子序列之間至少間隔1個(gè)數(shù)。(第五空4分，其余2. 5

11、分)#in clude using n amespace std;const int MAXN=1000;int n ,i,a ns,sum;int xMAXN;int lmaxMAXN;/lmaxi 為僅含xi及xi左側(cè)整數(shù)的連續(xù)子序列的序列和中，最大的序列和int rmaxMAXN;/rmaxi 為僅含xi及xi右側(cè)整數(shù)的連續(xù)子序列的序列和中，最大的序列和int mai n()cinn;for (i=0;i xi;lmax0=x0;for (i=1;i n ;i+)if (lmaxi-1=0)最新資料推薦Imaxi=xi;elselmaxi=lmaxi-1+xi;for (i=1;i n

12、;i+)if (lmaxi=0;i-)if (rmaxi+1=0;i-)if (rmaxirmaxi+1) ；an s=x0+x2;for (i=1;ia ns)ans=sum;couta nse ndl;return 0;2、(最短路徑問題)無向連通圖G有n個(gè)結(jié)點(diǎn)，依次編號(hào)為0, 1, 2,.,(n-1 )。用鄰接矩陣的形式給出每條邊的邊長(zhǎng)，要求輸出以結(jié)點(diǎn) 0為起點(diǎn)出發(fā)，到各結(jié)點(diǎn)的最短路徑長(zhǎng)度。使用Dijkstra算法解決該問題：利用dist數(shù)組記錄當(dāng)前各結(jié)點(diǎn)與起點(diǎn)的已找到的最短路徑長(zhǎng)度；每次從未擴(kuò)展的結(jié)點(diǎn)中選取dist值最小的結(jié)點(diǎn)v進(jìn)行擴(kuò)展，更新與 v相鄰的結(jié)點(diǎn)的dist值；不斷進(jìn)行上述操

13、作直至所有結(jié)點(diǎn)均 被擴(kuò)展，此時(shí)dist數(shù)據(jù)中記錄的值即為各結(jié)點(diǎn)與起點(diǎn)的最短路徑長(zhǎng)度。(第五空2分，其余3分)#in clude using n amespace std;const int MAXV=100;int n,i,j,v;int wMAXVMAXV;鄰接矩陣，記錄邊長(zhǎng)其中wij為連接結(jié)點(diǎn)i和結(jié)點(diǎn)j的無向邊長(zhǎng)度，若無邊則為-1int distMAXV;int usedMAXV;記錄結(jié)點(diǎn)是否已擴(kuò)展(0:未擴(kuò)展；1:已擴(kuò)展)int mai n()cinn;for (i=0;i n ;i+)for (j=0;j wij;最新資料推薦distO=O;for (i=1;i n ;i+)disti=-1;for (i=0;i n ;i+)usedi=0