noip2004模拟试题2个小时能做到70分

1、NOIP2004 初赛模拟试题 提高版用时：2 小时一、单项选择题（每小题只有一个正确）（1） 以下关于的叙述，正确的是A B C D E1912 年出生于法国二，参与了德国近乎完美的编译方法 Enigma 的设计战后以羽毛球作为消遣方式提出并实现了人工智能未娶（2） 蓝牙技术是一种A B C D E无线网络接入技术CPU 制作工艺3D 图形加速技术人工智能技术图像技术（3） 64 位无符号整数的范围是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） 以下排序算法不会快速排序随机化快速排序的是C D E二叉排序树二分查找的排序后遍历输出排序（7） 以下查找算法理论时间复杂度最低的是A B C D E顺序查找 散列查找 二分查找 二叉排序树树（8）入栈的顺序为 1,2,3,4 的序列，出栈顺序不可能的是A B C D E14114232313244241323（9）快

3、速排序最好情况时，时间复杂度为A B C D Enlogn nlog2n n*sqrt(n) n2n2logn（10） 下列排序方法中，不能每次都能将至少一个元素放在最终位置上的是A B C D E冒泡排序排序快速排序堆排序 计数排序二、多项选择题（每小题有 1 到 5 个正确（1）以下属于编译器的有）A B C D ETP BP FPC GPCDelphi7（2）以下关于算法，正确的有A B C算法必须有输入算法必须有输出算法必须执行有限次后结束D 算法必须能够以某种语言在计算机上实现E 算法的每一个步骤必须有确定的语言表示方法（3）下列属于冯.计算机模型的有A B C D E采用二进制表示

4、数据和指令采用”程序”工作方式计算机硬件有五大(运算器、控制器、结构化程序设计方法器、输入和输出设备)计算机只有系统（4）(12345)16+(5201314)8=A.B.C.D.E.(16C611)16 (1451537)10(1461537)10(5423021)8 (001)2（5）以下问题模型属于 NP 的有A B C D E含有负权环且每点仅经过至多一次的最短路径01 背包一般图的一般图的回路回路将地图用 4 种颜色（6）对于序列 1 8 14 23 29 44 52，用散列表，散列函数为 h(k)=kmod p，不会产生1617181920的 p 有：A B C D E（7）无向图

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) ， 下列哪些深度优先遍历结果是正确的？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）下列关于排序的说法，正确的有A排序、冒泡排序是稳定的B 选择排序的时间复杂性为 O(nlogn)C 选择排序、排序、快速排序、堆排序是不稳定的D排序、快速排序、堆排序的时间复杂性为 O(nlogn)E 快速排序是速度最快的排序（9）下列逻辑运算正确的是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） 将高级语言程序转换为可执行文件必不可少的步骤有A.B.C.D.E.调试程序解释程序编辑程序编译程序连接程序三、问题求解（1） 动态规划是竞赛中常用的解题策下出下面试题的状态转移方程：有 2 个字符串 a 和 b，请问，它们的最长公共子序列的最大长度是多少？例如，abcdefg和gacefg的最长公共子序列是acefg。（2）求 f(n) = f(n-1) + f(n-2)的通项公式，其中 f(0)=0,f(1)=1四、（1）var阅读程序，写出运行结果阅读下面一段程序

7、，写出运行结果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） 阅读下面一段程序，写出运行结果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） 阅读下面一段程序，写出运行结果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五、补完程序（1） 将下列程序补充完整问题描述将一个输入的十进制整数转换成二进制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） 将下列程序补充完整问题描述求一个序列当中的第 k 小数，并且将它输出算法描述利用快速排序的划分，每次划取一半。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