求noip2009普及组初试卷？
(普及组Pascal语言两小时完成)
●●●所有试题的答案都要求写在答题卡上，无效●●
1.选择题(***20题，65438+每题0.5分，* * * 30分。每个问题有且只有一个正确答案。)
1，下列关于图灵机的说法哪一项是正确的:
a)图灵机是世界上最早的电子计算机。
b)由于大量使用磁带，图灵机运行速度非常慢。
c)图灵机由英国人图灵发明，在二战中为破译德国密码发挥了重要作用。
d)图灵机只是一个理论计算模型。
2.下列关于计算机内存的陈述中，哪一项是正确的:
a)随机存取内存(RAM)是指程序运行时，每次分配给程序的内存位置是随机的，不确定的。
B) 1MB内存通常指大小为1024*1024字节的内存。
c)严格来说，计算机内存包括三部分:主存、缓存和寄存器。
d)即使在断电的情况下，通用存储器中的数据也可保存2小时以上。
3.下列关于BIOS的陈述中哪一项是正确的:
A) BIOS是计算机基本输入输出系统软件的缩写。
B) BIOS包含键盘、鼠标、声卡、显卡、打印机和其他常见输入和输出设备的驱动程序。
C) BIOS一般由操作系统厂商开发。
D) BIOS可以提供文件复制、拷贝、删除、目录维护等各种文件管理功能。
4.下列关于CPU的陈述中哪一项是正确的:
A) CPU称为中央处理器(CPU)。
B) CPU可以直接运行汇编语言。
c)在相同主频下，32位CPU的运行速度是16位CPU的两倍。
D) CPU最早是英特尔公司发明的。
5.关于ASCII，下列哪个陈述是正确的:
A) ASCII码是键盘上所有按键的唯一代码。
b)一个ASCII码可以存储在一个字节的存储空间中。
c)最新的扩展ASCII编码方案包括汉字和其他欧洲语言的编码。
D) ASCII码是由英国人制定和推广的。
6、下列软件不是计算机操作系统:
A) Windows B) Linux C) OS/2 D) WPS
7.关于互联网，以下哪个陈述是正确的:
a)新一代互联网使用的IPv6标准是对IPv5标准的升级和补充。
b)如果互联网主机有域名，它不再需要IP地址。
c)互联网的基本协议是TCP/IP协议。
d)互联网上所有可下载的软件和数据资源都可以免费合法使用。
8.下列关于HTML的陈述中哪一项是正确的:
A) HTML实现了文本、图形、声音甚至视频信息的统一编码。
B) HTML被称为超文本标记语言。
c)网络上广泛使用的Flash动画是用HTML编写的。
D) HTML也是一种高级编程语言。
9.关于编程语言，下列哪个陈述是正确的:
a)带注释的程序通常比不带注释的程序慢。
b)用高级语言开发的程序不能用于低级硬件系统(如自动控制机床)或低端手机。
c)与低级语言相比，高级语言更容易实现跨平台移植。
d)以上陈述都不正确。
10.假设大写字母A的ASCII码是65(十进制)，大写字母J的十进制ASCII码是:
A) 71 B) 72 C) 73 D)以上都不是。
对应于11和十进制分数125.125的八进制数是
a)100.1 B)175.175 C)175.1D)100.175
12，从左到右依次有六个元素FEDCBA，有些元素在入栈过程中会被弹出栈。以下哪一项不能是合法的堆栈序列？
a)EDC fab B)deca BF C)CDF EBA D)BCD AEF
13，表达式a*(b+c)-d的后缀表达式为:
a)ABCD *+-B)ABC+* D-C)ABC *+D-D)-+* ABCD
14，一棵非空二叉树，有n个分支节点(非叶节点)，最大叶节点数为:
a)2n+1 B)2n-1 C)n-1D)n+1
15，快速排序最坏情况的算法复杂度是:
a)O(log2n)B)O(n)C)O(nlog2n)D)O(N2)
16.有一个由4000个整数组成的顺序表。假设表中的元素已经按升序排列，二分搜索法用于定位元素。最多需要几次比较来确定所寻找的元素是否存在:
A) 11次B) 12次C) 13次D) 14次。
17.排序算法是稳定的，这意味着具有相同键码的记录在排序前后的相对位置不会改变。以下哪种排序算法不稳定？
a)冒泡排序b)插入排序c)合并排序d)快速排序
18.给定一个有n个顶点的有向图，如果这个图是强连通的(所有顶点到其他顶点都有路)，那么这个图有多少条有向边？
a)n B)n+1 C)n-1D)n *(n-1)
19.美国国家信息学奥林匹克竞赛官方网站为参加信息学奥林匹克竞赛的教师和学生提供相关信息和资源。全国信息学奥林匹克官方网站网址是多少？
A) / D) /
20.在参加NOI系列赛的过程中，下列哪种行为没有被严格禁止:
a)携带无通讯功能的书写工具、手表、电子词典进入赛场。
b)在线测试中，手工计算可能答案并在程序中直接输出答案得到分数。
c)通过互联网搜索获得解决问题的思路。
d)在提交的程序中启动多个进程，提高程序的执行效率。
2.解题(***2题，每空5分，* * * 10分)
1.陈骁有两个任务A和B，每个任务有如下几个步骤:A = A 1-& gt；a2->；a3，B = B 1->；B2->；B3->；B4->；b5 .在任何时候，陈骁只能专注于任务的一个步骤。但如果他愿意，他可以在完成手头任务的当前步骤后切换到另一个任务，并从上一个任务的第一步继续。每个任务的步骤顺序不能被打乱，例如...a2->；B2->；a3->；B3……...是合法的，而且...a2->；B3->；a3->；B2……...是违法的。陈骁从任务B的步骤b1开始，当他刚刚完成某个任务的某个步骤时，他停止工作，回家吃晚饭。回来后只记得自己完成了整个任务A，其他的都忘了。试着计算陈骁在饭前完成的任务步骤的可能顺序。
2.有一个程序如下:
1.a:= 1；
2.b:= a；
3.d:=-a；
4.e:= a+d；
5.c:= 2 * d；
6.f:= b+ e-d；
7.g:= a * f+c；
现在需要把这个程序分发给几台(足够)用电缆连接的pc机并行执行。每台PC机执行这些语句中的一部分，可以随时通过电缆与其他pc机通信，交换一些中间结果。假设每台PC在单位时间内可以执行一条语句，花费在通信上的时间不计在内。这个程序最快可以在单位时间内完成。注意:任何中间结果只有在一台电脑上获得后，才能被其他电脑引用。例如，如果语句4和6被分配到两台PC上执行，那么语句6必须在语句4之后执行，因为它需要引用语句4的计算结果。
三个。阅读程序写作成绩(***4题，每题8分，32分***)
1.
定义变量
a，b:整数；
函数功(a，b:整数):整数；
开始
如果一个mod b & lt& gt那么0
work := work(b，a mod b)
其他
工作:= b；
结束；
开始
读(a，b)；
writeln(工作(a，b))；
结束。
输入:20 12
产出:_ _ _ _ _ _ _ _
2.
定义变量
a，b:数组[0..2]的整数；
I，j，tmp:整数；
开始
对于i := 0到2 do
读作(b[I])；
对于i := 0到2 do
开始
a[I]:= 0；
对于j := 0到i do
开始
inc(a[i]，b[j])；
inc(b[a[i] mod 3]，a[j])；
结束；
结束；
tmp:= 1；
对于i := 0到2 do
开始
a[I]:= a[I]mod 10；
b[I]:= b[I]mod 10；
tmp:= tmp *(a[I]+b[I])；
结束；
writeln(tmp)；
结束。
输入:2 3 5
产出:_ _ _ _ _ _ _ _
3.
const c = 2009
定义变量
n，p，s，I，j，t:整数；
开始
读(n，p)；
s:= 0；t:= 1；
对于i := 1到n do
开始
t:= t * p mod c；
for j := 1 to i do
s:=(s+t)mod c；
结束；
书写内容；
结束。
输入:11 2
输出:
4.
定义变量
答:字符串；
n:整数；
过程get next(var str:string)；
定义变量
l，I，j，k:整数；
临时:字符；
开始
l :=长度(str)；
k:= l-1；
while(k & gt；=1)和(str[k]>str[k+1]) do
dec(k)；
I:= k+1；
while(我& lt=l)和(str[I]& gt；str[k]) do
inc(一)；
temp:= str[k]；
str[k]:= str[I-1]；
str[I-1]:= temp；
for i := l downto k + 1 do
对于j := k + 1到i - 1 do
if str[j]>str[j+1]然后
开始
temp:= str[j]；
str[j]:= str[j+1]；
str[j+1]:= temp；
结束；
结束；
开始
改为(a)；
读作(n)；
而n & gt0 do
开始
get next(a)；
十二月(日)；
结束；
写(一)；
结束。
输入:NOIP 3
输出:
4.完善程序(前8个空格3分，后2个空格2分，* * * 28分)。
1.(最大连续子段和)给出一个数列(元素个数不超过100)，数列的元素都是负整数、正整数和0。请在序列中找到一个连续的子序列，使这个子序列中包含的所有元素之和最大。在最大和的前提下，还要求这个子序列包含最大数量的元素，并输出这个最大和以及这个连续子序列中的元素数量。比如顺序为4，-5，3，2，4时，输出9，3；当序列为1 2 3 -5 0 7 8时，输出为16和7。
定义变量
答:数组[1..100]的整数；
n，I，ans，len，tmp，beg:整数；
开始
读作(n)；
对于i := 1到n do
读(a[I])；
tmp:= 0；
ans:= 0；
len:= 0；
求:=①；
对于i := 1到n do
开始
如果tmp+a[I]& gt；然后回答
开始
ans:= tmp+a[I]；
len:= I-beg；
结束
else if ( ②)和(I-beg & gt；然后
len:= I-beg；
如果tmp + a[i] ③那么
开始
求:=④；
tmp:= 0；
结束
其他
⑤ ;
结束；
writeln(ans，' '，len)；
结束。
2.(国王摆放)在一个n*m的棋盘上摆放k个国王，要求他们不要互相攻击，有多少种不同的方式？假设把国王放在(x，y)格子里，国王的攻击区域是:(x-1，y-1)，(x-1，y)，(x-1，y+1)。读入n，m，k m，k三个数，输出答案。用回溯法解决了这个问题。棋盘行数为0~n-1，列数为0~m-1。
定义变量
n，m，k，ans:整数；
哈希:数组[0..4, 0..4]的整数；
程序工作(x，y，tot:整数)；
定义变量
I，j:整数；
开始
如果tot = k，那么
开始
公司(ans)；
退出；
结束；
重复
while hash[x，y]& lt；& gt0 do
开始
Inc(y)；
如果y = m，那么
开始
Inc(x)；
y:=①；
结束；
如果x = n，那么
退出；
结束；
对于i := x - 1到x + 1 do
如果(i & gt= 0)和(i & ltn)然后
对于j := y - 1到y + 1 do
if(j & gt；= 0)和(j & ltm)那么
② ;
③ ;
对于i := x - 1到x + 1 do
如果(i & gt= 0)和(i & ltn)然后
对于j := y - 1到y + 1 do
if(j & gt；= 0)和(j & ltm)那么
④ ;
Inc(y)；
如果y = m，那么
开始
Inc(x)；
y:= 0；
结束；
如果x = n，那么
退出；
直到假；
结束；
开始
读(n，m，k)；
ans:= 0；
fillchar(hash，sizeof(hash)，0)；
⑤ ;
writeln(ans)；
结束。