十一届 pascal 初赛试题答案
作者&投稿：鄣官 （若有异议请与网页底部的电邮联系）
b d d d d e a d d e b a b d b 20(e正确的)多选的话就是 abcd
10 11
第十一届全国青少年信息学奥林匹克联赛初赛试题普及组(P)参考答案
一. 选择一个正确答案代码（A/B/C/D/E）,填入每题的括号内 (每题1.5分,多选无分, 共30 分)
题号 1 2 3 4 5 6 7 8 9 10
选择 B A D E D D B D E A
题号 11 12 13 14 15 16 17 18 19 20
选择 D C E E A C D B C E
二．问题解答 （每题5分，共10分）
1. 答： 5
2. 答： 11
三. 阅读程序，并写出程序的正确运行结果：（每题8分，共32分）
(1) 程序的运行结果是: 499
(2) 程序的运行结果是: Today-ix-terrible!
(3) 程序的运行结果是: -7452
(4) 程序的运行结果是: zzzaaabbbcccy
四.根据题意, 将程序补充完整 (前4空，每空2分，后5空，每空4分，共28分)
pascal 语言
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
1.① n, i （或者 i, n）
② 'YES'
③ n = 1 (或者 n – 1 = 0)
④ n mod i = 0
2.① num + len[i] div t
② num >= k
③ left := 0
④ left + 1
⑤ not isok(mid) （或者 isok(mid) = false）
用时：2小时
一、 单项选择题（每小题只有一个正确答案）
（1） 以下关于图灵的叙述，正确的是
A． 1912年出生于法国
B． 二战时，参与了德国近乎完美的密码编译方法Enigma的设计
C． 战后以羽毛球作为消遣方式
D． 提出并实现了人工智能
E． 终身未娶
（2） 蓝牙技术是一种
A． 无线网络接入技术
B． CPU制作工艺
C． 3D图形加速技术
D． 人工智能技术
E． 图像存储技术
（3） 64位无符号整数的范围是
A． -1063 - 1063
B． -1063 - 1063-1
C． 0 - 264
D． 0 - 264-1
E． 0 - 1064-1
（4） (1234567890ABCDEF)16+(ACACACACAC)16=
A． (123456253D587B9B)16
B． (123456253D587A9A)16
C． (123456253D587A9B)16
D． (123456253D588B9B)16
E． (1001000110100010101110010010100111101010110000111101010011011)2
（5） 22 or 33 and 44=
A． 24
B． 36
C． 44
D． 56
E． 64
（6） 以下排序算法不会退化的是
A． 快速排序
B． 随机化快速排序
C． 二叉排序树插入后遍历输出
D． 二分查找的插入排序
E． 希尔排序
（7） 以下查找算法理论时间复杂度最低的是
A． 顺序查找
B． 散列查找
C． 二分查找
D． 二叉排序树
E． 红-黑树
（8） 入栈的顺序为1,2,3,4的序列，出栈顺序不可能的是
A． 1 2 3 4
B． 4 3 2 1
C． 1 2 4 3
D． 1 3 4 2
E． 4 1 2 3
（9） 快速排序最好情况时，时间复杂度为
A． nlogn
B． nlog2n
C． n*sqrt(n)
D． n2
E． n2logn
（10） 下列排序方法中，不能每次都能将至少一个元素放在最终位置上的是
A． 冒泡排序
B． 插入排序
C． 快速排序
D． 堆排序
E． 计数排序
二、 多项选择题（每小题有1到5个正确答案）
（1） 以下属于编译器的有
A． TP
B． BP
C． FPC
D． GPC
E． Delphi7
（2） 以下关于算法，正确的有
A． 算法必须有输入
B． 算法必须有输出
C． 算法必须执行有限次后结束
D． 算法必须能够以某种语言在计算机上实现
E． 算法的每一个步骤必须有确定的语言表示方法
（3） 下列属于冯.诺依曼计算机模型的核心思想有
A． 采用二进制表示数据和指令
B． 采用”存储程序”工作方式
C． 计算机硬件有五大部件(运算器、控制器、存储器、输入和输出设备)
D． 结构化程序设计方法
E． 计算机软件只有系统软件
（4） (12345)16+(5201314)8=
A. (16C611)16
B. (1451537)10
C. (1461537)10
D. (5423021)8
E. (101100011011000010001)2
（5） 以下问题模型属于NP的有
A． 含有负权环且每点仅经过至多一次的最短路径
B． 01背包
C． 一般图的哈密尔顿回路
D． 一般图的欧拉回路
E． 将地图用4种颜色着色
（6） 对于序列1 8 14 23 29 44 52，用散列表存储，散列函数为h(k)=k mod p，不会产生冲突的p有：
A． 16
B． 17
C． 18
D． 19
E． 20
（7） 无向图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． a,c,f,e,d,b
B． a,e,f,c,d,b
C． a,b,e,c,d,f
D． a,b,e,d,f,c
E． a,b,c,d,e,f
（8） 下列关于排序的说法，正确的有
A． 插入排序、冒泡排序是稳定的
B． 选择排序的时间复杂性为O(nlogn)
C． 选择排序、希尔排序、快速排序、堆排序是不稳定的
D． 希尔排序、快速排序、堆排序的时间复杂性为O(nlogn)
E． 快速排序是速度最快的排序
（9） 下列逻辑运算正确的是
A. A•（A + B ）= A
B. A +（A•B）= A
C. A•（B + C ）= A•B + A•C
D. A +（B•C）=（A + B）•（A + C）
E. 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
T, Y, S, P, J, B : Integer;
Begin
ReadLn(S, P, Y, J);
T := 12 + J - P - Y;
B := T div 3;
Case T Mod 3 Of
1: If S + P = Y Then Inc(Y)
Else Inc(P);
2: Begin inc(P); Inc(Y); End;
End;
Writeln(B + Y, ' ', B + P, ' ', B);
End.
输入：8 7 5 4
（2） 阅读下面一段程序，写出运行结果
Var
A, B, N, i : Longint;
f : Array[1..1000000] Of Byte;
Begin
Readln(A, B, N);
f[1] := 1;
f[2] := 1;
For i := 3 To N Do
f[i] := (A * f[i-1] + B * f[i-2]) mod 7;
WriteLn(f[N]);
End.
输入：5 2 123456
（3） 阅读下面一段程序，写出运行结果
Var
i, N, M : Longint;
Function J(N : Longint):Longint;
Var
B : Array[1..1000000] Of Boolean;
P : Longint;
Function Next(P : Longint):Longint;
Begin
P := (P + 1) Mod N;
If P = 0 Then P := N;
While not B[P] Do
Begin
P := (P + 1) Mod N;
If P = 0 Then P := N;
End;
Next := P;
End;
Begin
FillChar(B,SizeOf(B),True);
P := 1;
For i := 1 To N - 1 Do
Begin
P := Next(P);
B[P] := False;
P := Next(P);
End;
J := P;
End;
Begin
ReadLn(N, M);
For i := 1 To M Do
N := J(N);
WriteLn(N);
End.
输入：7 2
输入：144455 166677
五、 补完程序
（1） 将下列程序补充完整
[问题描述]将一个输入的十进制整数转换成二进制
Var
N : Longint;
Ans : String;
Begin
ReadLn(N);
Ans := ____(1)____;
While (N > 0) Do
Begin
If (N Mod 2 = 0) Then
Ans := ____(2)____
Else
Ans := ____(3)____;
N := ____(4)____;
End;
Writeln(Ans);
End.
（2） 将下列程序补充完整
[问题描述]求一个序列当中的第k小数，并且将它输出
[算法描述]利用快速排序的划分思想，每次划取一半。
Type
ArrType = Array[1..10000] of Integer;
Var
A : Arrtype;
N, K, I : Integer;
Function Find(A:ArrType; P, R, K : Integer): Integer;
Procedure Swap(Var A, B: Integer);
Var
Tmp : Integer;
Begin
Tmp := A;
A := B;
B := Tmp;
End;
Function Partition(P, R: Integer): Integer;
Var
x, t, i, j : Integer;
Begin
x := ____(1)____;
i := P - 1;
j := R + 1;
Repeat
Repeat
Dec(j);
Until ____(2)____;
Repeat
Inc(i);
Until ____(3)____;
If ____(4)____ Then
Swap(A[i],A[j])
Else
Break;
Until False;
Partition := j;
End;
Function Select(P, R, i : Integer):Integer;
Var
q, k : integer;
Begin
If ____(5)____ Then
Select := A[P]
Else
Begin
q := Partition(P, R);
k := ____(6)____;
If (i<=k) Then
Select:= ____(7)____
Else
Select:= ____(8)____;
End;
End;
Begin
Find := Select(P, R, K);
End;
Begin
ReadLn(N, K);
For i := 1 To N Do
Read(A[i]);
Writeln(Find(A, 1, N, K));
End.
（3） 将下列程序补充完整
[问题描述]输入n个数，求一个和最大的连续子序列，而且序列的长度在L1和L2之间
[算法描述]使用堆维护。
Type
Dat=Record
W, Num:Longint;
End;
Var
M, P, N, L1, L2, I, Now, J, Len, Base, Max:Longint;
Heap:Array[1..200000] Of Dat;
Where:Array[1..200000] Of Longint;
InNum:Array[1..200000] Of Longint;
Procedure Swap(Var A, B:Dat; Which:Longint);
Var
I:Dat;
Begin
Where[A.W]:= ____(1)____;
Where[B.W]:= ____(2)____;
I:=A;
A:=B;
B:=I;
End;
Procedure Ins(N, M:Longint);
Var
I:Longint;
Begin
Inc(Len);
Heap[Len].Num:=N;
Heap[Len].W:=M;
I:=Len;
While (I Div 2>0) And (____(3)____) Do
Begin
Swap(Heap[I], Heap[I Div 2], I);
I:=I Div 2;
End;
Where[M]:=I;
End;
Procedure Del(Which:Longint);
Var
I:Longint;
Begin
Heap[Which]:=Heap[Len];
Where[Heap[Which].W]:=Which;
I:=Which;
While (I Div 2>0) And (Heap[I].Num>Heap[I Div 2].Num) Do
Begin
Swap(Heap[I], Heap[I Div 2], I);
I:=I Div 2;
End;
While ((I*2<=Len-1) And (Heap[I].Num<Heap[I*2].Num))
Or ((I*2+1<=Len-1) And (Heap[I].Num<Heap[I*2+1].Num)) Do
Begin
If Heap[I*2].Num>Heap[I*2+1].Num Then
Begin
Swap(Heap[I*2], Heap[I], I*2);
I:= ____(4)____;
End
Else
Begin
Swap(Heap[I*2+1], Heap[I], I*2+1);
I:= ____(5)____;
End;
End;
Heap[Len].Num:=0;
Heap[Len].W:=0;
Dec(Len);
End;
Begin
Len:=0;
Now:=0;
Max:=-MaxLongint;
Readln(N, L1, L2);
For I:=1 To L2 Do
Begin
Read(J);
Inc(Now, J);
InNum[I]:=Now;
If I>=L1 Then Ins(Now, I);
End;
Max:=Heap[1].Num;
For I:=L2+1 To N Do
Begin
Read(J);
Inc(Now, J);
InNum[I]:=Now;
Base:=InNum[____(6)____];
Del(____(7)____);
Ins(Now, I);
If Heap[1].Num-Base>Max Then Max:=Heap[1].Num-Base;
End;
For I:= ____(8)____ Do
Begin
Base:=InNum[I-L1+1];
Del(Where[I]);
If Heap[1].Num-Base>Max Then Max:=Heap[1].Num-Base;
End;
Writeln(Max);
End.
*****************************************************************
NOIP2004初赛模拟 - 试题分析
单项选择题
1 - 图灵与1912年出生于英国伦敦，二战时，参与了Enigma的破译工作，战后以长跑作为消遣，提出了人工智能，但是至今仍然没有人实现。他终身未娶； 答案：E
2 - 蓝牙技术是无线接入技术，答案：A
3 - 64位为64位二进制，无符号则为0到2^64-1；答案：D
4 - 基本的数制转换问题，答案：E
5 - 位操作就是对二进制数的每一位进行位操作，注意优先级，先计算and，再计算or，答案：D
6 - 随机化快速排序虽然几乎不会出现退化情况，但是仍然是存在的，仍然不能说明是稳定的。二分查找的插入排序，复杂度以插入的时间O(n)计算，故仍然是稳定的n^2，答案：D。
7 - 顺序查找为O(n)，散列查找为O(1)，后3种查找复杂度均为logn。答案：B
8 - 栈是后进先出的线性表，根据栈的性质，E是不可能的
9 - 快速排序平均情况和最好情况时间复杂度都是nlogn
10 - 插入排序最后一趟可能调整所有表中的元素，故错误。
多项选择题
1 - TP、BP等都是软件，而非编译器，答案CD
2 - 算法可以没有输入。故选BCDE
3 - 结构化程序设计是那什和B.施耐德曼提出的，而E根本就不正确，故选ABC
4 - 进制转化，答案BD
5 - 欧拉回路不是NP问题，随着四色定理的证明，四色问题也就不是NP问题。其他几个为NP问题，答案ABC
6 - 根据散列表的性质，选AE
7 - 根据深度有先遍历的深度性质，选D
8 - 注意堆排序是不稳定的，答案ABC
9 - 根据逻辑运算的性质选ABCD
10 - 程序先经过编译再经过连接最终生成exe。编译出的代码不能直接在windows下运行。
问题求解
1 - 经典题，方程：
opt[i, j] = opt[i-1, j-1] (a[i]=a[j])
max{opt[i-1, j], opt[i, j-1]} (a[i]<>a[j])
2 - 通项公式为(((1+S5)/2)^n-((1-S5)/2)^n)/S5
具体解法请参见组合数学
阅读程序
1 - 基本的阅读程序方法。输出：6 9 1
2 - 手算的办法是算不了那么多项的。由于是取模运算，于是可以找到周期循环。接着问题就好解决了。答案：5
3 - 第1问可以手算，答案是7。第2问就要进行数学上的分析。
首先，J(n)返回的是，n个人按照报数的方法，出圈人的那个编号。
程序里迷惑了你，用了O(n)的算法，其实不难写出递归式：
J(2n) = J(n) - 1
J(2n+1) = J(n) + 1
同样，可以对应到二进制上，进而可以得到结论：
J(J(J(J(J(...J(N))...))))至多运算logn次以后就收敛，也就是J(n)不再变化。
于是只要适当模拟就可以解决问题了，第2问答案255。
补充程序
1 - 基本的进制转换，显而易见第1空应该是初始化。
接着是试除的过程。因为用了字串的操作，所以就省去了逆序的过程，而直接进行字符串操作。
2 - 这是快速排序的一个推广，程序结构写的也比较清楚了。Partition部分的答案为：
(1) A[(P + R) Shr 1] //快速排序一般用这种方法避免退化，随机化效率显得略微有些不够
(2) A[j]<=x
(3) A[i]>=x
(4) i<j
Select中，就是快速排序变形的精华所在。
(5) 空很是递推的边界。很容易得到，当P=R时，才能肯定的返回A[P]。
(6) 当中的k，是元素总数的意思，于是得到q - p + 1
7与8，分别是继续划分。7为Select(P, Q, i)，8为Select(Q+1, R, i-k)。这就保证了寻找的第k大数始终正确
3 - 部分和是很重要的一种技术，这里再加上了堆的维护，就可以实现logn的查找了。由于算法比较基本，就不做详细解答了。请同学们仔细复习数据结构上的内容。
答案：
(1) Which Div 2
(2) Which
(3) Heap[I].Num>Heap[I Div 2].Num
(4) I*2
(5) I*2+1
(6) I-L2
(7) Where[I-L2+L1-1]
(8) N-L2+L1 To N-1
哪一年的？
令定君欣： 耗内存太大了,无法计算 我也运行了下,输入2005再空格就呆在那了,按CTRL+C才出来
宝安区18639653831： 第十六届全国青少年信息学奥林匹克联赛初赛 pascal 普及组 答案和试题？
令定君欣： CCF NOIP2010普及组(Pascal语言)参考答案与评分标准一、单项选择题(共20题,每题1.5分,共计30分)1 2 3 4 5 6 7 8 9 10D A A D A D B D C B11 12 13 14 15 16 17 18 19 20D B B B B A A D C D二、问题求解(共2题,每题5分,共计...
宝安区18639653831： 第十五届全国青少年信息学奥林匹克联赛初赛试题及答案 - ？
令定君欣： NOIP2009初赛普及组(C语言、PASCAL语言)参考答案与评分标准一、单项选择题:(每题1.5分)1. D 2. B 3. A 4. A 5. B6. D 7. C 8. B 9. C 10. D11. C 12. C 13. B 14. D 15. D16. B 17. D 18. A 19. C 20. B二、问题求解:(共2题,每空...
宝安区18639653831： noip2008初赛答案who有?？
令定君欣： NOIP2008年提高组(Pascal语言)参考答案与评分标准 一、单项选择题:(每题1.5分) 1. C 2. A 3. B 4. C 5. B 6. D 7. D 8. E 9. B 10. C 二、 不定项选择题 (共10题,每题1.5分,共计15分.每题正确答案的个数大于或等于1.多选或少选均不...
宝安区18639653831： NOIP2009普及组初赛三题4题 - ？
令定君欣： 原题目确实有错误,标准答案为NPOI 附:关于NOIP2009初赛普及组Pascal语言一道题目的问题与阅卷处理意见 经查,NOIP2009 初赛普及组(Pascal版本)第四大题(阅读程序写结果)第4小题题 目中存在一处数据输入格式的错误:该题提供...
宝安区18639653831： 谁能给我出PASCAL初赛的题目 - ？
令定君欣： 2006年南海区青少年信息学奥林匹克竞赛初赛试题(高中组,两小时完成)◆◆请将正确答案在答题卷上填写,在本试题卷上答题无效◆◆一、nbsp;选择填空(1—10小题为单选题,11—20小题为多选题,多选题多选、少选、错选均不能得...
宝安区18639653831： 高悬赏!noip提高初赛pascal语言历届题目详细分析 - ？
令定君欣： 6. 已知队列(13,2,11,34,41,77,5,7,18,26,15),第一个进入队列的元素是13,则第五个出队列的元素是(B). A) 5 B) 41 C) 77 D) 13 E) 18 19. 已知元素(8,25,14,87,51,90,6,19,20),问这些元素以怎样的顺序进入栈,才能使出栈的顺序满足...
宝安区18639653831： 输入一个数N 1 - 二分之一+三分之一……N分之一,PASCAL语言 求这个答案 - ？
令定君欣： double s=0; for(int i=1;i<=n;i++){if(i%2==0){i=-1*i}s=s+1/i } 因为不会PASCAL语言,此段程序用c#语言编写,提供思路 % 是取模,即求i除以2的余数
宝安区18639653831： 第十六届noip普及组的答案 pascal语言 急求 今天回答的再加100分？
令定君欣： 我初赛78分哈,初赛算是挤进了...... 一、 1-10 DAADADBDCB 11-20 DABBBAADCD 二、 1. {2-2-1-2-3-1-1-3-4-3-1-2-1-3-5-3-6} 2. 49种 三、1. 2_20_77_91(＂_＂指一个空格,下同) 2. 99_101_111_ 3. 120_112 4. (1) 1 (2)4 四、1. (1) tmp:=...
宝安区18639653831： NOIP2013 Pascal普及组初赛试题答案？
令定君欣： 一大题:AABCDBBCACAADACCADAB 一道题1.5分二大题:14种 s1=0 s2=1 s3=1 s4=1 一道题5分(第二题s1~s4需要全部答对,答错一个没分)三大题:3+5=8 6 7 4 一道题8分四大题:n-p+ia[i]ni-p+1a[i-p]cur<upper_bounda[root].right_childcurupper_bound1第三个答案和最后一个答案两分,其他的答案3分,一共28分.我的得分是51,不知你呢?
