a、單項選擇題(* * 10題，每題1.5分，* * 15分。每個問題有且只有壹個正確答案)。
1.在下列各項中，(d)不是中央處理器的壹部分。
A.控制器b .算術單元c .寄存器d .主板e .算術邏輯單元(ALU)
2.在關系數據庫中，存儲在數據庫中的數據的邏輯結構主要是(B)。
A.二叉樹B .多分支樹c .哈希表D. B+樹e .二維表
3.下列各項中，只有(D)不是計算機存儲容量的常用單位。
A.字節
4.4的含義。ASCII碼是(b)。
A.二進制-十進制轉換碼b .美國信息交換標準碼c .數字的二進制編碼
D.能被計算機處理的字符的唯壹編碼。常用字符的二進制編碼
5.在C語言中，表達式23 | 2 ^ 5的值是(a)。
A.23 B. 1 C.18 D.32 E.24
6.在C語言中，判斷A等於0或B等於0或C等於0的正確條件表達式是(B)。
A.！((a！=0)||(b！=0)||(c！=0)) B！((a！= 0)& amp；& amp(b！= 0)& amp；& amp(c！=0))
C.！(a = = 0 & amp& ampb==0)||(c！= 0)d .(a = 0)& amp；& amp(b = 0)amp；& amp(c=0)
E.！((a=0)||(b=0)||(c=0))
7.地面上有編號為A、B、C的三根細柱，在A柱上放置10個中間有孔直徑相同的圓盤，編號為1，2，3，...從上到下。a柱上的部分光盤可通過B柱移入C柱或暫時存放在B柱上。如果B柱上的操作記錄是“進，進，出，進，進，出，進，進，出，進，進，出，進，出”。然後，在C柱上，從下到上的車牌號碼是(D)。
A.2 4 3 6 5 7 b . 2 4 1 2 5 7 c . 2 4 3 1 7 6d . 2 4 3 6 7 5 e . 2 1 4 3 7 5
8.十進制數17.5625對應的八進制數是(b)。
a . 21.5625 b . 21.44 c . 21.73d . 21.731 e .前四個答案都不正確。
9.歐拉圖G是指能形成壹個閉環的圖，圖G的每條邊在這個閉環上恰好出現壹次(即畫壹筆)。在下面的描述中，是(d)不壹定是歐拉。
圖g中沒有奇數度的頂點。
B.包含歐拉環行導航的圖(歐拉環行導航是指通過圖的每條邊恰好壹次的閉合路徑)。
C.包含歐拉閉跡的圖(歐拉跡是指通過圖的每條邊恰好壹次的路徑)。
有壹個循環恰好通過每個頂點壹次。
E.本身是閉跡的圖
10.不能被自身控制終止的循環稱為“無限循環”。例如，在C語言程序中，語句“while(1)”
printf(" * ")；”是壹個無限循環，它將在運行時無休止地打印*號。下列關於無限循環的說法中，只有(a)是正確的。
A.沒有算法可以判斷任何程序和相應的輸入數據是否會出現無限循環。因此，
任何編譯系統都不做無限循環檢查。
壹些編譯系統可以檢測無限循環。
C.無限循環是壹個語法錯誤。既然編譯系統可以檢查各種語法錯誤，那麽它也應該能夠檢查無限循環。
D.死循環類似於多個進程中的“死鎖”，死鎖是可以檢測到的，所以死循環也是可以檢測到的。
關於
E.對於死循環，只能等到它發生了再做現場處理，沒有更主動的手段。
二、不定選擇題(* * 10題，每題1.5分，* * * 15分。每個問題的正確答案數大於或等於1。選多選少都不計分)。
11.設A = B =真，C = D =假，下列邏輯運算表達式值為真(ABC)。
A.(?A∧B)∨(C∧D∨A) B？(((A∧B)∨C)∧D)
C.A∧(B∨C∨D)∨D .(A∧(D∨C))∧B
12.命題“P→Q”可以讀作P蘊涵Q，這裏P和Q是兩個獨立的命題。只有當命題P成立，命題Q不成立時，命題“P→Q”的值為假，其他情況均為真。與命題“P→Q”等價的邏輯關系是(AD)。
A.？P∨Q B. P∧Q C？(P∨Q) D？(?Q∧P)
13.(2070) 16+(34) 8的結果是(ABD)。
A.(8332)10
C.(100000000110)2d .(20214)8
14.已知有7個節點的二叉樹的第壹次根遍歷是1 2 4 5 6 3 7(編號是節點的編號，下同)，最後壹次根遍歷是4 6 5 2 7 3 1，所以二叉樹可能的中間根遍歷是(ABD)。
A.4 2 6 5 1 7 3 B. 4 2 5 6 1 3 7
C.4 2 3 1 5 4 7 D. 4 2 5 6 1 7 3
15.冗余數據是指可以從其他數據中導出的數據。例如，學生的數學、語文和英語成績已經存儲在數據庫中。如果還存儲了三科總成績，則總成績可視為冗余數據。冗余數據往往導致數據不壹致。比如以上四項數據全部輸入，由於操作失誤，總成績不等於三科成績之和，就會產生矛盾。下列關於冗余數據的說法中，正確的是(BC)。
A.應該從數據庫中刪除所有冗余數據。
B.與用高級語言編寫的數據處理系統相比，用關系數據庫編寫的系統更容易消除冗余數據。
C.為了提高查詢效率，可以在數據庫中適當保留壹些冗余數據，但更新時要進行兼容性檢查。
D.做兼容性測試會降低效率，所以可以忽略數據庫中的冗余數據。
16.在以下軟件中，推薦NOIP競賽(復賽)使用的語言環境是(ABD)。
A.gcc B. g++
C.Turbo C D. free pascal
17.以下為斷電後仍能保存數據(AB)。
A.硬盤B. rom C .視頻存儲器D. RAM
18.下列關於計算機語言的說法中，正確的是(CD)。
A.高級語言比匯編語言更高級，因為它的程序運行效率更高。
B.隨著Pascal、C等高級語言的出現，機器語言和匯編語言退出了歷史舞臺。
c高級語言程序比匯編語言程序更容易從壹臺計算機移植到另壹臺計算機。
D.c是壹種面向過程的高級計算機語言。
19.下列關於算法復雜度的說法中，正確的是(BC)。
a算法的時間復雜度是指在計算機上實現時的運行時間。
b算法的時間復雜度是指對於算法的壹個或多個主要運算，運算次數與問題規模之間的函數關系。
C.如果壹個問題是NPC，說明在求解該問題時不存在多項式時間復雜度的算法。但這壹點在理論上沒有得到證實，也沒有被否定。
D.如果壹個問題是NP級的，那麽它的結論和c壹樣。
20.近20年來，許多計算機專家大力提倡遞歸算法作為解決更復雜問題的有力工具。下列關於遞歸算法的說法中，正確的是(AC)。
A.1977左右形成的標準計算機高級語言FORTRAN77禁止程序中的遞歸，原因之壹是這種方法可能會占用更多的內存空間。
B.與非遞歸算法相比，遞歸算法解決同樣的問題壹般運行速度更快。
對於更復雜的問題，用遞歸方式編程往往比用非遞歸方式更容易。
d .對於定義的標準數學函數sin(x)，應用程序中的語句“y = sin(sin(x))；這是壹個遞歸調用。3.解題(***2題，每題5分，* * * 10分)
1.給定n個編號球，數字依次為1，2，…，n。把這N個球放進R個相同的盒子裏，這是不允許的。
如果有空盒子，不同放置方法的總數記錄為S(n，r)。比如S(4，2)=7，七種不同的放置方式如下。
{(1),(234)}, {(2),(134)}, {(3),(124)}, {(4),(123)}, {(12),(34)}, {(13),(24)},
{(14),(23)}。當n = 7，r = 4時，s (7，4) = _ _ _ _ _ _ _。
2.n個人在操場上圍成壹個圈，從1到n順時針編號，然後從第壹個人開始，每
其他每個人都要求下壹個人離開操場。顯然，第壹輪過後，偶數的人都離開了操場。依次做，直著做
操場上只剩下壹個人了。把這個人的數字記為J(N)，比如J(5)=3，J(10)=5，以此類推。規則
J(400)=______________ .
(提示:分析N=2m+r，其中0 ≤ r
四個。閱讀程序寫作成績(***4題，每題8分，32分***)
1.# include & ltstdio.h & gt
int main()
{int i，p[5]，q[5]，x，y = 20
for(I = 0；我& lt=4;i++)
scanf("%d "，& ampp[I])；
q[0]=(p[0]+p[1])+(p[2]+p[3]+p[4])/7；
q[1]= p[0]+p[1]/((p[2]+p[3])/p[4])；
q[2]= p[0]* p[1]/p[2]；
q[3]= q[0]* q[1]；
q[4]= q[1]+q[2]+q[3]；
x =(q[0]+q[4]+2)-p[(q[3]+3)% 4]；
if(x & gt；10)
y+=(q[1]* 100-q[3])/(p[p[4]% 3]* 5)；
其他
y+= 20+(q[2]* 100-q[3])/(p[p[4]% 3]* 5)；
printf("%d，%d\n "，x，y)；
返回0；
}
/*註意:在這個例子中，給定的輸入數據可以避免分母為0或者數組元素的下標越界。*/
輸入:6 6 5 5 3
輸出:_ _ _ _ _ _ _ _ _ _
2.# include & ltstdio.h & gt
void fun(int *a，int *b)
{ int * k；
k = a；a = b；b = k；
}
主( )
{int a=3，b=6，* x = & ampa，* y = & ampb；
fun(x，y)；
printf("No.1: %d，%d "，a，b)；
樂趣(& amp壹，& ampb)；
printf(" 2號:%d，%d\n "，a，b)；
}
輸出:_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
3.#包含“math.h”
#包含“stdio.h”
主()
{ int a 1[51]= { 0 }；
int i，j，t，t2，n = 50
for(I = 2；我& lt= sqrt(n)；i++)
if(a1[i]==0)
{ T2 = n/I；
for(j = 2；j & lt= t2j++)a 1[I * j]= 1；
}
t = 0；
for(I = 2；我& lt= n；i++)
if(a1[i]==0)
{printf("%4d "，I)；t++；
if(t % 10 = = 0)printf(" \ n ")；
}
printf(" \ n ")；
}
輸出:_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
________________________________________
4.#包含“stdio.h”
char ch[]={'q '，' A '，' S '，' O '，' R '，' T '，' E '，' X '，' A '，' M '，' P '，' L '，' E ' }；
int n = 12；
void shift(int k，int n)
{ char v；
int j；
v = ch[k]；j = k+k；
while(j & lt；=n)
{ if((j & lt；n)& amp；& amp(ch[j]& lt；ch[j+1]))j++；
如果(v & ltch[j])
{ ch[j/2]= ch[j]；j * = 2；}
其他
返回；
ch[j/2]= v；
}
}
無效hpsrt(無效)
{ int k；
char tmp
for(k = n/2；k & gt0;k -)移位(k，n)；/*構建壹個堆*/
printf(" no . 1:")；
for(k = 1；k & lt= n；k++)putchar(ch[k])；
putchar(' \ n ')；
for(k = n；k & gt0;k -)
{ tmp = ch[1]；ch[1]= ch[k]；ch[k]= tmp；
shift(1，k-1)；
}
}
主()
{ int k；
HP SRT()；
printf(" 2號:")；
for(k = 1；k & lt= n；k++)putchar(ch[k])；
putchar(' \ n ')；
}
輸出:_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
___________________________________________
動詞 （verb的縮寫）改進程序(前5個空格2分，後6個空格3分，* * * 28分)。
1.(格雷碼)
格雷碼是十進制數的二進制代碼。編碼順序與對應十進制數的大小不壹致。其特征在於:對於
兩個相鄰的十進制數和兩個對應的格雷碼之間只有壹個二進制位差。另外，最大數量和最小數量之間只有壹個
二進制位則不同。以壹個4位二進制數為例，編碼如下:
十進制數字格雷碼
0 0000 8 1100
1 0001 9 1101
2 0011 10 1111
3 0010 11 1110
4 0110 12 1010
5 0111 13 1011
6 0101 14 1001
7 0100 15 1000
如果把每壹個二進制位看成壹個開關，壹個數會變成另壹個相鄰的數，只需要換壹個開關。因此，
格雷碼廣泛應用於信號處理、數模轉換等領域。
以下程序的任務是輸入數字n (n
輸出m (***n位，數組gr[])對應的格雷碼。
為了完成程序，妳必須仔細分析上表中的規則，尤其是固定格雷碼某壹位的十進制數。
從0到1，或從1到0。
# include & ltstdio.h & gt
主()
{int bound=1，m，n，I，j，b，p，gr[15]；
printf("input n，m \ n ")；
scanf("%d%d "，& ampn & amp；m)；
for(I = 1；我& lt= n；i++)bound =①；
如果(m & lt0 | | m & gt=綁定)
{printf("數據錯誤！\ n ")；
② ;
}
b = 1；
for(I = 1；我& lt= n；i++)
{ p = 0；b = b * 2；
for(③；j & lt= m；j++)
如果(④)
p = 1-p；
gr[I]= p；
}
for(I = n；⑤ )
printf("%1d "，gr[I])；/*數字1出現在“%1d”中，而不是字母l */
printf(" \ n ")；
}
2.(連續郵資問題)某國發行了N種不同面額的郵票，規定每封信最多允許貼M張郵票。這裏，
在壹定的約束條件下，為了郵寄{1，2，3，…，maxvalue}連續整數集的所有郵費，並使maxvalue最大。
每枚郵票的面值如何設計？例如，當n=5，m=4時，面值設計為{1，3，11，15，32}，可以使
Maxvalue達到最大值70(換句話說，1到4張這些面額的郵票可以代表所有不超過70的郵費，但壹張都沒有。
方法表明郵費是71。但如果1到4枚其他面額的郵票能代表所有不超過K的郵資，則必須有k≤70)。
下面是用遞歸回溯法解決連續郵資問題的程序。數組x[1:n]表示n種不同的郵票面額，並指定每個元素。
素數是嚴格按下標遞增的。數組bestx [1:n]存儲最大化maxvalue的郵票面值(最優解)。
數組y[maxl]用於記錄用當前選擇的郵票面值x[1:i]可以投寄的各種郵資所需的最少郵票數量。請放了程
序言完成。
# include & ltstdio.h & gt
#定義NN 20
#定義maxint 30000
#define maxl 500 /*最高郵費*/
int n，m，bestx[NN]，x[NN]，y[maxl]，max value = 0；
無效結果()
{輸出結果:最大值和最優解:bestx[1:n](略)
}
void回溯(int i，int r)
{ int j，k，z[maxl]；
for(j = 0；j & lt= ① ;j++)
if(y[j]& lt；m)
for(k = 1；k & lt= m-y[j]；k++)
if(y[j]+k & lt；=y[ ② ])
y[③]= y[j]+k；
while(y[r]& lt；maxint)r++；
如果(i & gtn)
{ if(r-1 & gt；最大值)
{ max value =④；
for(j = 1；j & lt= n；j++)
bestx[j]= x[j]；
}
返回；
}
for(k = 0；k & ltmaxlk++)
z[k]= y[k]；
for(j =⑤；j & lt= r；j++)
{ x[I]= j；
⑥ ;
for(k = 0；k & ltmaxlk++)
y[k]= z[k]；
}
}
void main()
{ int j；
printf("input n，m:\ n ")；
scanf("%d%d "，& ampn & amp；m)；
for(j = 1；j & ltmaxlj++)
y[j]= maxint；
y[0]= 0；x[0]= 0；x[1]= 1；
回溯(2，1)；
結果()；
}