noip2004模擬試題2個(gè)小時(shí)能做到70分

1、NOIP2004 初賽模擬試題 提高版用時(shí)：2 小時(shí)一、單項(xiàng)選擇題（每小題只有一個(gè)正確）（1） 以下關(guān)于的敘述，正確的是A B C D E1912 年出生于法國(guó)二，參與了德國(guó)近乎完美的編譯方法 Enigma 的設(shè)計(jì)戰(zhàn)后以羽毛球作為消遣方式提出并實(shí)現(xiàn)了人工智能未娶（2） 藍(lán)牙技術(shù)是一種A B C D E無(wú)線網(wǎng)絡(luò)接入技術(shù)CPU 制作工藝3D 圖形加速技術(shù)人工智能技術(shù)圖像技術(shù)（3） 64 位無(wú)符號(hào)整數(shù)的范圍是A B C D E-1063 -1063-1063 - 1063-1000-264264-11064-1（4）(1234567890ABCDEF)16+(ACACACACAC)16=A B C

2、D E(123456253D587B9B)16 (123456253D587A9A)16 (123456253D587A9B)16 (123456253D588B9B)16 ()20011011（5） 22 or 33 and 44=A B C D E2436445664（6） 以下排序算法不會(huì)快速排序隨機(jī)化快速排序的是C D E二叉排序樹(shù)二分查找的排序后遍歷輸出排序（7） 以下查找算法理論時(shí)間復(fù)雜度最低的是A B C D E順序查找 散列查找 二分查找 二叉排序樹(shù)樹(shù)（8）入棧的順序?yàn)?1,2,3,4 的序列，出棧順序不可能的是A B C D E14114232313244241323（9）快

3、速排序最好情況時(shí)，時(shí)間復(fù)雜度為A B C D Enlogn nlog2n n*sqrt(n) n2n2logn（10） 下列排序方法中，不能每次都能將至少一個(gè)元素放在最終位置上的是A B C D E冒泡排序排序快速排序堆排序 計(jì)數(shù)排序二、多項(xiàng)選擇題（每小題有 1 到 5 個(gè)正確（1）以下屬于編譯器的有）A B C D ETP BP FPC GPCDelphi7（2）以下關(guān)于算法，正確的有A B C算法必須有輸入算法必須有輸出算法必須執(zhí)行有限次后結(jié)束D 算法必須能夠以某種語(yǔ)言在計(jì)算機(jī)上實(shí)現(xiàn)E 算法的每一個(gè)步驟必須有確定的語(yǔ)言表示方法（3）下列屬于馮.計(jì)算機(jī)模型的有A B C D E采用二進(jìn)制表示

4、數(shù)據(jù)和指令采用”程序”工作方式計(jì)算機(jī)硬件有五大(運(yùn)算器、控制器、結(jié)構(gòu)化程序設(shè)計(jì)方法器、輸入和輸出設(shè)備)計(jì)算機(jī)只有系統(tǒng)（4）(12345)16+(5201314)8=A.B.C.D.E.(16C611)16 (1451537)10(1461537)10(5423021)8 (001)2（5）以下問(wèn)題模型屬于 NP 的有A B C D E含有負(fù)權(quán)環(huán)且每點(diǎn)僅經(jīng)過(guò)至多一次的最短路徑01 背包一般圖的一般圖的回路回路將地圖用 4 種顏色（6）對(duì)于序列 1 8 14 23 29 44 52，用散列表，散列函數(shù)為 h(k)=kmod p，不會(huì)產(chǎn)生1617181920的 p 有：A B C D E（7）無(wú)向圖

5、 G=(V,E)，V=a,b,c,d,e,f, E=(a,b),(a,c),(a,e),(b,e),(c,f),(f,d),(d,e) ， 下列哪些深度優(yōu)先遍歷結(jié)果是正確的？A B C D Ea,c,f,e,d,ba,e,f,c,d,ba,b,e,c,d,fa,b,e,d,f,ca,b,c,d,e,f（8）下列關(guān)于排序的說(shuō)法，正確的有A排序、冒泡排序是穩(wěn)定的B 選擇排序的時(shí)間復(fù)雜性為 O(nlogn)C 選擇排序、排序、快速排序、堆排序是不穩(wěn)定的D排序、快速排序、堆排序的時(shí)間復(fù)雜性為 O(nlogn)E 快速排序是速度最快的排序（9）下列邏輯運(yùn)算正確的是A.B.C.D.E.A（A + B ）=

6、 A A +（AB）= AA（B + C ）= AB + ACA +（BC）=（A + B）（A + C） A+1=A（10） 將高級(jí)語(yǔ)言程序轉(zhuǎn)換為可執(zhí)行文件必不可少的步驟有A.B.C.D.E.調(diào)試程序解釋程序編輯程序編譯程序連接程序三、問(wèn)題求解（1） 動(dòng)態(tài)規(guī)劃是競(jìng)賽中常用的解題策下出下面試題的狀態(tài)轉(zhuǎn)移方程：有 2 個(gè)字符串 a 和 b，請(qǐng)問(wèn)，它們的最長(zhǎng)公共子序列的最大長(zhǎng)度是多少？例如，abcdefg和gacefg的最長(zhǎng)公共子序列是acefg。（2）求 f(n) = f(n-1) + f(n-2)的通項(xiàng)公式，其中 f(0)=0,f(1)=1四、（1）var閱讀程序，寫(xiě)出運(yùn)行結(jié)果閱讀下面一段程序

7、，寫(xiě)出運(yùn)行結(jié)果T, Y, S, P, J, B :eger;BeginReadLn(S, P, Y, J); T := 12 + J - P - Y;B := T div 3; Case T Mod 3 Of1: If S + P = Y Then Inc(Y) Else Inc(P);2: Begin inc(P); Inc(Y); End; End;Wri End.n(B + Y, , B + P, , B);輸入：8 7 5 4（2） 閱讀下面一段程序，寫(xiě)出運(yùn)行結(jié)果VarA, B, N, i : Long;f : Array1.1000000 Of Byte;BeginReadln(A,

8、 B, N);f1 := 1;f2 := 1;For i := 3 To N Dofi := (A * fi-1 + B * fi-2)mod7;Wri End.n(fN);輸入：5 2 123456（3） 閱讀下面一段程序，寫(xiě)出運(yùn)行結(jié)果Vari, N, M : Long;Function J(N : Long):Long;VarB : Array1.1000000 Of;P : Long;Function Next(P : Long BeginP := (P + 1) Mod N; If P = 0 Then P := N;):Long;While not BP Do BeginP := (

9、P + 1) Mod N; If P = 0 Then P := N;End;Next := P; End;BeginFillChar(B,SizeOf(B),True); P := 1;For i := 1 To N - 1 Do BeginP := Next(P);BP := False;P := Next(P);End;J := P;End;BeginReadLn(N, M);For i := 1 To M Do N := J(N);Wrin(N); End.輸入：7 2輸入：144455 166677五、補(bǔ)完程序（1） 將下列程序補(bǔ)充完整問(wèn)題描述將一個(gè)輸入的十進(jìn)制整數(shù)轉(zhuǎn)換成二進(jìn)制Var

10、N : Long;Ans : String;BeginReadLn(N);Ans := _ (1); While (N 0) Do BeginIf (N Mod 2 = 0) Then Ans := _ (2)ElseAns := _ (3);N := (4);End;Wri End.n(Ans);（2） 將下列程序補(bǔ)充完整問(wèn)題描述求一個(gè)序列當(dāng)中的第 k 小數(shù)，并且將它輸出算法描述利用快速排序的劃分，每次劃取一半。TypeArrType = Array1.10000 ofeger;VarA : Arrtype; N, K, I :eger;Function Find(A:ArrType; P,

11、 Procedure Swap(Var A, B: VarR, K :eger);eger):eger;Tmp :eger;BeginTmp := A; A := B;B := Tmp;End;Function Partition(P, R: Vareger):eger;x, t, i, j :eger;Beginx := _(1);i := P - 1; j := R + 1;RepeatRepeatDec(j);Until (2)_ ; RepeatInc(i);Until (3)_ ; If (4)ThenSwap(Ai,Aj) ElseBreak; Until False; Parti

12、tion := j;End;Function Select(P, R, i : Vareger):eger;q, k :eger;BeginIf (5)Then Select := APElseBeginq := Partition(P, k := _(6) ; If (i0) And BeginSwap(HeapI, Hea I:=I Div 2;End; WhereM:=I;(_(3) Doiv 2, I);End;Procedure Del(Which:Long Var);I:Long Begin;HeapWhich:=HeapLen; WhereHeapWhich.W:=Which;

13、I:=Which;While (I Div 20) And (HeapI.NumHea Beginiv 2.Num) DoSwap(HeapI, Hea I:=I Div 2;iv 2, I);End;While (I*2=Len-1) And (HeapI.NumHeapI*2.Num)Or (I*2+1=Len-1) And (HeapI.NumHeapI*2+1.Num Then BeginSwap(HeapI*2, HeapI, I*2); I:= (4)_ ;End Else BeginSwap(HeapI*2+1, HeapI, I*2+1); I:= (5)_ ;End;End;HeapLen.Num:=0; HeapLen.W:=0; Dec(Len);DoEnd;BeginLen:=0;Now:=0;Max:=-MaxLong; Readln(N, L1, L2);For I:=1 To L2 Do BeginRead(J);Inc(Now, J); InNumI:=Now;If I=L1 Then Ins(Now, I); End;Max:=Heap1.Num;For I:=L2+1 To N DoBeginRead(J);Inc(Now, J); I