第16届全国信息学奥林匹克竞赛省预赛试题解答。
NOIP2010(帕斯卡改进小组)
一、多项选择题
1.10十进制数相当于16十进制数A1.2是()a . 101.2b . 111.4c . 65438。
2.一个字节由()二进制组成。A.8B.16 C.32 D .以上都有可能。
3.下列逻辑表达式的值始终为真()。
A.p∨(┓p∧q)∨(┓p∧┓q)b.q∨(┓p∧q)∨(p∧┓q)
C.p∨q∨(p∧┓q)∨(┓p∧q)d.p∨┓q∨(p∧┓q)∨(┓p∧┓q)
4.4下可执行文件的默认扩展名。Linux是()。A.exeb.com.dll.d .以上都不是。
5.如果方程7*7=41在某个系统中成立，那么方程12*12=()在这个系统中也成立。
A.100 b。144 c。164d。196
6.提出计算机“存储程序”工作原理的是()。
A.克劳德？香农. b .戈登。摩尔·查尔斯？巴比克·冯？诺伊曼
7.前缀表达式“+3 * 2+5 12”的值是()。答. 23B。25 C. 37D。65
8.主存的访问速度比中央处理器(CPU)的工作速度慢很多，影响了后者的效率。根据局部性原理，CPU访问的存储单元通常倾向于在一个连续的小区域内。因此，为了提高整个系统的执行效率，在CPU中引入了()。a .寄存器b .缓存c .闪存d .外部存储器
9.完全二叉树的顺序存储方案是指将完全二叉树的节点按照从上到下、从左到右的顺序结构存储在一个数组中。假设根节点存储在数组的位置1，节点K的父节点如果存在，应该存储在数组的位置()。A.2kb.2k+1 C.K./2，轮D. (k+1)/2。
10.下列比赛中历史最悠久的是()。不透明的。APIO
二、不定选择题
1.元素R1、R2、R3、R4和R5按照R1、R2、R3、R4和R5的顺序堆叠。如果第1个是R3，那么第5个可能是()。A.R1 B.R2 C.R4 D.R5
2.Pascal语言、C语言、C++语言都属于()。a .高级语言b .自然语言c .解释语言d .编译语言
3.就地排序是指辅助空间(除了存储要排序的元素)的大小与数据大小无关的一种排序算法。下列属于原位排序的有()。a .冒泡排序b .插入排序c .基数排序d .选择排序
4.在整数的补码表示法中，下列说法正确的是()。
A.只有负整数的最高编码位是1B..编码比特数确定后，可以表示的最小整数和最大整数的绝对值是相同的。
C.整数0只有一个唯一代码。d .用补码表示的两个数相加时，如果最高有效位出现进位，说明运算溢出。
5.如果二叉树的前序遍历序列是ABCDEFG，后序遍历序列是CBFEGDA，那么根节点的左子树中的节点数可能是()。A0 b . 2 c . 4d . 6
6.在下面的HTML语句中，能正确生成NOI官方网站超链接的是()。
A.& lta URL = " h t t p://w w w w n o I . c n " >欢迎来到NOI网站
B.& lta href = " h t t p://w w w n o I . c n " >欢迎来到NOI网站
C.& lta & gth t t p://w w w w n o I . c n & lt；/a & gt；
D.& lt一个名称" h t t p://w w w n o I c n " >欢迎来到NOI网站
7.关于拓扑排序，下列说法正确的是()。
A.所有连通有向图都可以实现拓扑排序。
b对于同一个图，拓扑序的结构是唯一的。
C.在拓扑排序中，入度为0的节点总是排在入度大于0的节点之前。
D.拓扑排序结果序列中的第一个节点必须是入度大于0的点。
8.平面的法线是指垂直于该平面的直线。平面通过点(1，1，1)，(0，3，0)，(2，0，0)的法线是()。
A.通过点(1，1，1)和(2，3，3)的直线b .通过点(1，1，1)和(3，2，65438)
C.过点(0，3，0)和(-3，1，1)的直线d .过点(2，0，0)和(5，2，1)的直线
9.链表中有两个指针字段llink和rlink，分别指向节点的前任和继任者。设p指向链表中的一个节点，其左右节点非空。现在要求删除节点p，那么下列语句序列中正确的是()。
a . p-& gt；rlink-& gt；llink = p-& gt；rlink
p->；llink-& gt；rlink = p-& gt；llink删除p；
b . p-& gt；llink-& gt；rlink = p-& gt；rlink
p->；rlink-& gt；llink = p-& gt；llink删除p；
C.p->rlink-& gt；llink = p-& gt；llink
p->；rlink-& gt；llink-& gt；rlink = p-& gt；rlink删除p；
D.p->llink-& gt；rlink = p-& gt；rlink
p->；llink-& gt；rlink-& gt；link = p-& gt；llink删除p；
10.今年(2010)发生的事件有()。
A.惠普实验室的研究员Vinay Deolalikar声称已经证明了P≠NP。
B.英特尔收购了电脑安全软件公司McAfee。
C.苹果发布iPhone 4手机d .微软发布Windows 7操作系统。
第三，解决问题
1.LZW编码是一种自适应字典编码。在编码的过程中，最开始只有一个基本结构元素的编码字典。如果在编码过程中遇到新条目，该条目和新代码将被添加到字典中，并用于编码后续信息。
例如，考虑一个要编码的信息字符串:“xyx yy yy xyx”。初始字典只有三个词条，第一个是X，代码是1；第二个是y，代码是2；第三个是空格，编码为3；因此，字符串“xyx”的代码是1-2-1(其中-是代码分隔符)，它后面的一个空格是1-2-1-3。但是因为有一个空格，我们知道前面的“xyx”是一个单词，又因为这个单词不在字典里，我们可以自适应的把这个词条加入字典，编码为4，然后按照新的字典对后续的信息进行编码，以此类推。于是，最终得到代码:1-2-1-3-2-2-3-5-3-4。
我们可以看到信息被压缩了。压缩后的信息传输给接收方，接收方根据基本字典就可以完成序列的完全恢复。解码过程是编码过程的反向操作。现在已知初始字典中的三个词条如上所述，接收方接收到的编码信息为2-2-1-2-3-1-3-4-3-1-2-1-3-5-3-6。
2.无向图G有七个顶点。如果没有由奇边组成的简单环，它最多有_ _ _ _ _ _ _ _ _条边。
3.记住T是一个队列，开头是空的，现有的n个总数不超过32的正整数依次放入队列。如果不管这些数是什么，我们都能找到一种出队列的方法使得某一时刻队列T中的数之和正好是9，那么n的最小值就是_ _ _ _ _ _ _ _ _。
第四，阅读程序写出结果
1.
常数
size = 10；
定义变量
I，j，cnt，n，m:整数；
数据:数组[1..size]的整数；
开始
readln(n，m)；
对于i := 1到n do
read(data[I])；
对于i := 1到n do
开始
CNT:= 0；
对于j := 1到n do
if(data[I]& lt；data[j])或((data[j] = data[i])和(j & lt我))
然后是Inc(CNT)；
如果cnt = m
然后writeln(data[I])；
结束；
结束。
投入
5 2
96 -8 0 16 87
输出:_ _ _ _ _ _ _ _ _
2.
常数
size = 100；
定义变量
na，nb，I，j，k:整数；
a，b:数组[1..size]的整数；
开始
readln(na)；
对于i := 1到na do
读(a[I])；
readln(nb)；
for i := 1 to nb do
读作(b[I])；
I:= 1；
j:= 1；
while(我& lt= na)和(j & lt= nb) do
开始
如果a[I]& lt；= b[j]那么
开始
写(a[i]，' ')；
inc(一)；
结束
否则开始
写(b[j]，' ')；
Inc(j)；
结束；
结束；
如果我& lt=那na呢
对于k := i到na do
写(a[k]，' ')；
如果j & lt那么= nb
对于k := j到nb do
写(b[k]，' ')；
结束。
投入
五
1 3 5 7 9
四
2 6 10 14
输出:_ _ _ _ _ _ _ _ _
3.
常数
num = 5；
定义变量
n:整数；
函数r(n:整数) :整数；
定义变量
I:整数；
开始
如果n & lt= num then
开始
r:= n；
退出；
结束；
对于i :=1到num do
如果r(n-I)& lt；那么0
开始
r:= I；
退出；
结束；
r:=-1；
结束；
开始
readln(n)；
writeln(r(n))；
结束。
输入16
输出:_ _ _ _ _ _ _ _ _
4.
常数
size = 100；
定义变量
n，m，x，y，I:整数；
r: array[1..size]的整数；
映射:数组[1..尺寸，1..大小]的布尔值；
找到:布尔型；
函数成功:布尔型；
定义变量
I:整数；
开始
对于i :=1到n do
如果不是映射[r[i]][r[i mod n + 1]]
那么开始吧
成功:=假；
退出；
结束；
成功:=真；
结束；
过程交换(var a，b:整数)；
定义变量
t:整数；
开始
t:= a；
a:= b；
b:= t；
结束；
procedure perm(左、右:整数)；
定义变量
I:整数；
开始
如果找到
然后退出；
如果离开& gt正确
那么开始吧
如果成功
那么开始吧
对于i := 1到n do
writeln(r[i]，' ')；
发现:=真；
结束；
退出；
结束；
对于i:=从左到右做
开始
swap(r[left]，r[I])；
烫发(左+ 1，右)；
swap(r[left]，r[I])；
结束；
结束；
开始
readln(n，m)；
fillchar(map，sizeof(map)，false)；
对于i := 1到m do
开始
readln(x，y)；
map[x][y]:= true；
map[y][x]:= true；
结束；
对于i := 1到n do
r[I]:= I；
发现:=假；
perm(1，n)；
如果找不到
然后writeln('无解决')；
结束。
输入:
9 12
1 2
2 3
3 4
4 5
5 6
6 1
1 7
2 7
3 8
4 8
5 9
6 9
输出:_ _ _ _ _ _ _ _ _
动词 （verb的缩写）改进程序
1.(过河)一个月的一个漆黑的夜晚，一群人在河的右岸，试图通过唯一的木桥走到河的左岸。在黑暗中，过桥时，他们不得不用灯照明。不幸的是，他们只有一盏灯。另外，木桥最多能承受两个人同时通过，否则就会倒塌。每个人都独自走过独木桥。不同的人可能需要不同的时间。两个人一起过独木桥，因为只有一盏灯，所以需要的时间就是慢一点的人独自过桥的时间。现在输入n (2
比如有三个人，A，B，C，他们单独过桥的时间是1.24，那么总的最少需要时间是7。具体方法是:A和B一起过桥到河的左岸，A独自返回河的右岸带回灯光，然后A和C一起过桥到河的左岸，总时间为2+65，438+0+4。
常数
SIZE = 100；
无穷大= 10000；
左=真；
右=假；
左向右=真；
RIGHT _ TO _ LEFT = false
定义变量
n，I:整数；
时间:数组[1..Size]的整数；
位置:数组[1..大小]的布尔值；
函数max(a，b :integer):整数；
开始
如果a & gtb那么
最大:= a
其他
max:= b；
结束；
函数go(stage : boolean):整数；
定义变量
I，j，num，tmp，ans:整数；
开始
if (stage =从右向左)
那么开始吧
num:= 0；
ans:= 0；
对于i := 1到n do
如果pos[i] = Rignt，则
开始
inc(数字)；
如果时间[I]& gt；然后回答
ans:= time[I]；
结束；
如果__________，那么
开始
go:= ans；
退出；
结束；
ans :=无穷大；
对于i := 1至n–1 do
如果pos[i] = RIGHT，那么
对于j := i+1到n do
如果pos[j] = RIGHT，那么
开始
pos[I]:= LEFT；
pos[j] :=左；
tmp := max(time[i]，time[j])+_ _ _ _ _ _ _；
如果tmp & lt然后回答
ans:= tmp；
pos[i] :=右；
pos[j]:= RIGHT；
结束；
go:= ans；
结束
else if (stage =从左到右)
那么开始吧
ans :=无穷大；
对于i := 1到n do
如果_______那么
开始
pos[i] :=右；
tmp:= _ _ _ _ _ _ _ _；
如果tmp & lt然后回答
ans:= tmp；
_________;
结束；
go:= ans；
结束
else go:= 0；
结束；
开始
readln(n)；
对于i := 1到n do
开始
read(time[I])；
pos[i] :=右；
结束；
writeln(go(RIGHT _ TO _ LEFT))；
结束。
-
一、单项选择题(* * 10题，每题1.5分，* * 15分)
1 2 3 4 5 6 7 8 9 10
C A A D B D C B C B
二、不定选择题(* * 10题，每题1.5分，* * * 15分，多选或少选不计分)
1 2 3 4 5 6 7 8 9 10
ACD AD ABD AC B B D D BCD ABC
三、解题(***3题，每题5分，* * * 15分)
1 . yyxy xx yyxy xyx xx xyx 2.12 3.18
四、阅读程序写结果(***4题，每题7分，28分作***)
1.16 2.1 2 3 5 6 7 9 10 14 3.4 4.1 6 9 5 4 8 3 2 7
五、完善程序(1空2分，其余10空，每空2.5分，* * * 27分)
(注意:在下面的过程中可能有一些等价的填空方法。各省可以请自己的专家在电脑上审核，不一定要报科委审核。)
1.①数量& lt= 2(或数字
②走(从左到右)
③位置[i] =左(或左=位置[i])
④ time[i]+go(从右向左)(或go(从右向左)+time[i])
⑤位置[i] :=左侧
在这个问题中，LEFT可以替换为true，LEFT_TO_RIGHT可以替换为true，RIGHT_TO_LEFT可以替换为false。
2.① opt[k]
② home[r] := k
③ j := i+i(或j := 2 * i或j := i * 2)
④ swap(i，j)(或swap(j，I))
⑤值[i]+堆[1](或堆[1]+值[I])
⑥即时通讯