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

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

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

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

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、 雙向鏈表中有兩個指針域，llink 和 rlink ，分別指向前戲及后繼，設(shè) p 指向鏈表中的一個結(jié)點， q 指向一 待插入結(jié)點，現(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、對圖 G 中各個結(jié)點分別指點一種顏色,使相鄰結(jié)點顏色不同,則稱為圖G 的一個正常著色。正常著色圖G 所必需的最少顏色數(shù),稱為 G 的色數(shù)。那么下圖的色數(shù)是（） 。最新資料推薦A. 3 B. 4 C. 5 D. 615、在NOI系列賽事中參賽選手必須使用由承辦單位統(tǒng)一提供的設(shè)備。下列物品中不色誘選手自帶的是（）A.鼠標 B.筆 C.身份證 D.準考證二、不定項

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

7、以進行黑白染色的有（）。（黑白染色：為各個結(jié)點分別指定黑白兩種顏色之一，使用相鄰結(jié)點顏色不同。）A.二分圖 B.完全圖 C.樹D.連通圖三、問題求解1、 在1和2015之間（包括1和2015在內(nèi)）不能被4、5、6三個數(shù)任意一個整除的數(shù)有 個。2、 結(jié)點數(shù)為5的不同形態(tài)的二叉樹一共有 種。（結(jié)點數(shù)為2的二叉樹一共有2種：一種是根結(jié)點和左 兒子，另一種是根結(jié)點和右兒子。）四、閱讀程序?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、(雙子序列最大和)給定一個長度為n(3=n=1000)的整數(shù)序列，要求從中選出兩個連續(xù)子序列，使得這兩個連續(xù)子序列的序列和之和最大，最終只需輸出這個最大和。一個連續(xù)子序列的序列和為該連續(xù)子序列中所有數(shù)之和。要求：每個連續(xù)子序列長度至少為1,且兩個連續(xù)子序列之間至少間隔1個數(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個結(jié)點，依次編號為0, 1, 2,.,(n-1 )。用鄰接矩陣的形式給出每條邊的邊長，要求輸出以結(jié)點 0為起點出發(fā)，到各結(jié)點的最短路徑長度。使用Dijkstra算法解決該問題：利用dist數(shù)組記錄當前各結(jié)點與起點的已找到的最短路徑長度；每次從未擴展的結(jié)點中選取dist值最小的結(jié)點v進行擴展，更新與 v相鄰的結(jié)點的dist值；不斷進行上述操

13、作直至所有結(jié)點均 被擴展，此時dist數(shù)據(jù)中記錄的值即為各結(jié)點與起點的最短路徑長度。(第五空2分，其余3分)#in clude using n amespace std;const int MAXV=100;int n,i,j,v;int wMAXVMAXV;鄰接矩陣，記錄邊長其中wij為連接結(jié)點i和結(jié)點j的無向邊長度，若無邊則為-1int distMAXV;int usedMAXV;記錄結(jié)點是否已擴展(0:未擴展；1:已擴展)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