13少年信息學奧林匹克聯(lián)賽初賽試題

1、13少年信息學奧林匹克聯(lián)賽初賽試題（普及組C語言二小時完成）全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效一、單項選擇題（共20題，每題15分，共計30分。每題有且僅有一個正確答案）。1 在以下各項中，（）不是CPU的組成部分。A.控制器B.運算器 C.寄存器 D.主板2. 在關(guān)系數(shù)據(jù)庫中，存放在數(shù)據(jù)庫中的數(shù)據(jù)的邏輯結(jié)構(gòu)以（）為主。A.二叉樹 B.多叉樹C.哈希表 D.二維表3. 在下列項中，只有（）不是計算機存儲容量的常用單位。A. Byte B. KBC.UB D.TB4. ASCII碼的含義是（）.A. 二一十進制轉(zhuǎn)換碼 B.美國信息交換標準代碼C.數(shù)字的二進制編碼D.計算機可處理

2、字符的唯一編碼5. 6. IT的含義是（）°A. 通信技術(shù) B.信息技術(shù)C.網(wǎng)絡(luò)技術(shù)D.信息學7. LAN的含義是（）。A.因特網(wǎng) B.局域網(wǎng)C.廣域網(wǎng)D.城域網(wǎng)&冗余數(shù)據(jù)是指可以由其他數(shù)據(jù)導(dǎo)出的數(shù)據(jù)，例如，數(shù)據(jù)庫中已存放了學生的數(shù)學、語文 和英語的三科成績，如果還存放三科成績的總分，則總分就可以看作冗余數(shù)據(jù)。冗余數(shù)據(jù)往 往會造成數(shù)據(jù)的不一致，例如，上而4個數(shù)據(jù)如果都是輸入的，由于操作錯誤使總分不等于 三科成績之和，就會產(chǎn)生矛盾。下而關(guān)于冗余數(shù)拯的說法中，正確的是（）oA. 應(yīng)該在數(shù)據(jù)庫中消除一切冗余數(shù)據(jù)B. 用髙級語言編寫的數(shù)據(jù)處理系統(tǒng)，通常比用關(guān)系數(shù)據(jù)庫編寫的系統(tǒng)更容易消

3、除冗余數(shù) 據(jù)C. 為了提髙查詢效率，在數(shù)據(jù)庫中可以適當保留一些冗余數(shù)據(jù)，但更新時要做相容性檢 驗D. 做相容性檢驗會降低效率，可以不理睬數(shù)據(jù)庫中的冗余數(shù)據(jù)9. 在下列各軟件中，不屬于NOIP競賽（復(fù)賽）推薦使用的語言環(huán)境有（）。A. gccB. g+C. Turbo CD. free pascal10. 以下斷電之后仍能保存數(shù)據(jù)的有（）。A.硬盤B.髙速緩存C.顯存 D. RAM11. 在下列關(guān)于計算機語言的說法中，正確的有（）。A. 高級語言比匯編語言更髙級，是因為它的程序的運行效率更高B. 隨著Pascal. C等髙級語言的岀現(xiàn)，機器語言和匯編語言已經(jīng)退出了歷史舞臺C. 髙級語言程序比匯編

4、語言程序更容易從一種訃算機移植到另一種計算機上D. C是一種面向?qū)ο蟮捏{級計算機語言12. 近20年來，許多訃算機專家都大力推崇遞歸算法，認為它是解決較復(fù)雜問題的強有力的工具。在下列關(guān)于遞歸算法的說法中，正確的是（）。A. 在19力年前后形成標準的計算機髙級語言“FORTRAN77”禁止在程序使用遞歸，原 因之一是該方法可能會占用更多的內(nèi)存空間B. 和非遞歸算法相比，解決同一個問題，遞歸算法一般運行得更快一些C. 對于較復(fù)雜的問題，用遞歸方式編程一般比非遞歸方式更難一些D.對于已經(jīng)立義好的標準數(shù)學函數(shù)sin(x),應(yīng)用程序中的語句“y=sin(sin(x)就是一種 遞歸調(diào)用13. 一個無法靠自

5、身的控制終止的循環(huán)稱為“死循環(huán)S例如，在C語言程序中，語while(l) printf(?");"就是一個死循環(huán)，運行時它將無休止地打印冬號。下而關(guān)于死循環(huán)的說法中， 只有()是正確的。A. 不存在一種算法,對任何一個程序及相應(yīng)的輸入數(shù)據(jù)，都可以判斷是否會岀現(xiàn)死循環(huán), 因而，任何編譯系統(tǒng)都不做死循環(huán)檢驗B. 有些編譯系統(tǒng)可以檢測岀死循環(huán)C. 死循環(huán)屬于語法錯誤，既然編譯系統(tǒng)能檢查各種語法錯誤，當然也應(yīng)該能檢查出死循 環(huán)D. 死循環(huán)與多進程中出現(xiàn)的“死鎖”差不多，而死鎖是可以檢測的，因而，死循環(huán)也可 以檢測的14. 在C語言中，表達式23I2A5的值是()A. 23B. 1C

6、.32D.1815. 在C語言中，判斷a等于0或b等于0或c等于0的正確的條件表達式是()A. !(a!=O)ll(b!=O)ll(c!=O)B. !(a!=O)&&(b!=O)&&(c!=0)C. !(a=0&&b=O)ll(c!=O)D. (a=0)&&(b=0)&&(c=0)16. 地而上有標號為A、B、C的3根細柱，在A柱上放有10個直徑相同中間有孔的圓盤, 從上到下依次編號為1, 2, 3,，將A柱上的部分盤子經(jīng)過B柱移入C柱，也可以在 B柱上暫存。如果B柱上的操作記錄為：“進，進，出，進，進，出，出，進

7、，進，岀， 進，岀，出”。那么，在C柱上，從下到上的盤子的編號為()。將B柱看成棧結(jié)構(gòu)A. 24 3 65 7B.24 1257C. 24 3 1 76D.24367517. 與十進制數(shù)1770對應(yīng)的八進制數(shù)是()。A. 3350B. 3351C. 3352 D. 3540設(shè)A=B=true, C二"false,以下邏輯運算表達式值為假的有()。B. ?(AAB)VC)AD)D. (AA(DVC) ABB.(208A)16A. (?AAB)V(CADVA)C. AA(BVCVD)VD19. (2070)16 + (34)8 的結(jié)果是()A.(8332)10C. (1000000001

8、10)2D. (20212)820. 已知7個結(jié)點的二叉樹的先根遍歷是1 245637 (數(shù)字為結(jié)點的編號，以下同)，中根 遍歷是4 265 17 3,則該二叉樹的后根遍歷是()0A.465 27 3 1B. 465 2 1 37C. 4 2 3 1 5 4 7D.465 3 1 72二問題求解(共2題，每題5分，共計10分)1. (子集劃分)將n個數(shù)1, 2,，】劃分成r個子集。每個數(shù)都恰好屬于一個子集, 任何兩個不同的子集沒有共同的數(shù)，也沒有空集。將不同劃分方法的總數(shù)記為S(n.r)o例如, S(4,2)=7,這 7 種不同的劃分方法依次為,(234), (2),( 134), (3),(

9、124), ,(123), (,(34), (,(24), (14),(23)。當 n=6.r=3 時，S(6,3)=。(提示：先固立一個數(shù)，對于其余的5個數(shù)考慮S(5,3)與S(5,2)，再分這兩種情況對原 固定的數(shù)進行分析)。S(n, r)=rXS(n-l, r)+S (n-1, r-1)S(6, 3)=3*s(5f 3)+s(5,2)2. (最短路線)某城市的街道是一個很規(guī)整的矩形網(wǎng)格(見下圖)，有7條南北向 的縱街，5條東西向的橫街。現(xiàn)要從西南角的A走到東北角的B.最短的龍法共有多少種？A(m,n)=A(m-l.n)+A(m,n-I )=A(7,4)+A(6.5)=,易知 A(m)=A

10、(Ln)=lM12345 r711111i112123456r3136101521284141020355684515153570126210BA三閱讀程序?qū)懡Y(jié)果(共4題，每題8分，共計32分)1. #include <stdio.h>int niain()int ip5,a.b,c,x,y=2O;for(i=0;i<=4;i+)scanf(H%d &pi);a=(pO)+p 1 )+(p2+p +p4|)/7;= 13b=p0+pl/(p2+p 3yp4);=8c=pO*pl/p 2;=6x=a+b-p(p3+3)%4;= 13+7-p2=20-5= 15if(x&

11、gt;10)y+= (b* 100-a)/(pp4%3*5);=20+26=46elsey+=2O+(b* 100-c)/(pp4%3*5);printf(M%d,%dn, x,y);return 0;/*注：本例中，給左的輸入數(shù)據(jù)可以避免分母為0或數(shù)組元素下標越界。*/ 輸入：66553輸出：2. include <stdio.li>void fun(int *a,int *b)int *k;k=a;a=b;b=k;main()int a=3.b=6.*x=&a嚴y=&b:fun(x,y);printf(N%d,%d，,a,b);輸出:3. #include Mm

12、ath.hH#include "stdio.hHmain()intal51=0;int ij,t,t2,n=5O:for (i=2;i<=sqrt(n);i+)if(ali=O)t2=n/i;for(j=2;j<=t2;j+) ali*j=l;t=O;for (i=2;i<=n;i+)if(ali=O)printf(,%4d,i); t+;if(t%10=0) printf(nnH);printf(Hnu);輸出：此算法的作用”4. #include nctype.huinclude "stdio.h1'void expand(char sl,ch

13、ar s2) int i,jab,c;jifor(i=0;(c=s 1 i)!=0,;i+)if(c='-) a=sli-l); b=sli+l;if (isalpha(a)&&isalpha(b) II isdigit(a)&&isdigit(b)/#函數(shù)isalpha(a)ffl于判斷字符a是否為字母，isdigit(b)用于判斷字符b是否 為數(shù)字，如果是，返回1，否則返回0可j-;do s2|j+=a+;while(tolower(a)<tolower(s 1 i+1 );/*函數(shù)tolower(a)功能是當字符a是大寫字母，改為小寫，其余情

14、況不變/else s2j+=c; else s2j+=c;s2j=W;inain() charsl100,s2300;printf(Hi nputsl:M);gets(sl);expand(sLs2);printf(H%sn,s2);輸入：wer2345d-h454-82qqq輸岀： 四.完善程序(前4空，每空2.5分，后6空，每空3分，共28分)1.(求字符串的逆序)下而的程序的功能是輸入若干行字符串，每輸入一行，就按逆 序輸岀該行，最后鍵入CTRL+Z終止程序(程序中EOF為輸入終止的標記.相應(yīng)的按鍵為 CTRL+Z,機內(nèi)碼為J) o請將程序補充完整Cinclude Hstdio.hn#include ”string.h"int maxline=100:int getline(char sJnt lim)int c,i;for(i=0; i<lim-l && (c=getchar()!=EOF && c!='n,;+i)si= _®接收一個字符到數(shù)組s;if(c=Aii