2012十八届noip提高组题目及答案

（提高组Pascal语言试题）

一、单项选择题（共10题，每题1.5分，共计15分；每题有且仅有一个正确选项）

1．目前计算机芯片（集成电路）制造的主要原料是（ ），它是一种可以在沙子中提炼出的物质。

A．硅

B．铜 C．锗

B．浏览器

D．铝 C．电子邮件

D．鼠标

D．编译器

2．（ ）是主要用于显示网页服务器或者文件系统的HTML文件的内容，并让用户与这些文件交互的一种软件。

A．资源管理器 A．显示器

3．目前个人电脑的（ ）市场占有率最靠前的厂商包括Intel、AMD等公司。

B．CPU

C．内存

4．无论是TCP/IP模型还是OSI模型，都可以视为网络的分层模型，每个网络协议都会被归入某一层中。如果用现实生活中的例子来比喻这些“层”，以下最恰当的是（ ）。

A． 中国公司的经理与斯洛伐克公司的经理交互商业文件 B． 军队发布命令

C． 国际会议中，每个人都与他国地位对等的人直接进行会

D． 体育比赛中，每一级比赛的优胜者晋级上一级比赛

5．如里不在快速排序中引入随机化，有可能导致的后果是（ ）。

A．数组访问越界 C．排序结果错误 A．电子管

B．陷入死循环

D．排序时间退化为平方级

D．超大规模集成电路

谈

6．1946年诞生于美国宾夕法尼亚大学的ENIAC属于（ ）计算机。

B．晶体管

C．集成电路

7．在程序运行过程中，如果递归调用的层数过多，会因为（ ）引发错误。

A．系统分配的栈空间溢出

B．系统分配的堆空间溢出

C．系统分配的队列空间溢出 D．系统分配的链表空间溢出

8．地址总线的位数决定了CPU可直接寻址的内存空间大小，例如地址总线为16位，其最大的可寻址空间为64KB。如果地址总线是32位，则理论上最大可寻址的内存空间为（ ）。

A．128KB

3G（第三代移动通信技术）标准的是（ ）。

A．GSM

B．TD-SCDMA

C．CDMA2000

D．WCDMA

于新兴

10．仿生学的问世开辟了独特的科学技术发展道路。人们研究生物体的结构、功能和工作原理，并将这些原理移植的工程技术中。以下关于仿生学的叙述，错误的是（ ）

A．由研究蝙蝠，发明雷达 C．由研究海豚，发明声纳

B．由研究蜘蛛网，发明因特网 D．由研究电鱼，发明伏特电池

n

B．1MB C．1GB D．4GB

9．以下不属于

二、不定项选择题（共10题，每题1.5分，共计15分；每题有一个或多个正确选项，多选或少选均不得分） 1．如果对于所有规模为n的输入，一个算法均恰好进行（ ）次运算，我们可以说该算法的时间复杂度为O(2A．2n1) 。

B．3

nC．n*2

n

D．22n

2． 从顶点A0 出发，对有向图（ ）进行广度优先搜索（BFS）时，一种可能的遍历顺序是A0,A1,A2,A3,A4 。

3．如果一个栈初始时为空，且当前栈中的元素从栈顶到栈底依次为a，b，c（如右图所示），另有元素d已经出栈，则可能的入栈顺序是（ ）。 A．a, b, c, d

B．b, a, c, d

C．a, c, b, d

D．d, a, b, c

4．在计算机显示器所使用的RGB颜色模型中，（ ）属于三原色之一。

A．黄色 B．蓝色 C．紫色 D．绿色 5．一棵二叉树一共有19个节点，其叶子节点可能有（ ）个。 A．1 B．9 C．10 D．11

6．已知带权有向图G上的所有权值均为正整数，记顶点u到顶点v的最短路径的权值为d(u,v) 。若v1,v2,v3,v4,v5 是图G上的顶点，且它们之间两两都存路径可达，则以下说法正确的有（ ）。

A．v1 到v2的最短路径可能包含一个环 B．d(v1,v2)d(v2,v1) C．

d(v1,v3)d(v1,v2)d(v2,v3)

v2v3v4v5是v1 到v5 的一条最短路径，那么v2v3v4是v2 到v4的一条最短路径

D．如果v17．逻辑异或（）是一种二元运算，其真值表如下所示。

a False False True True

b False True False True

ab

False True True Flase

以下关于逻辑异或的性质，正确的有（ ）。

A．交换律：abba

B．结合律：(ab)ca(bc)

C．关于逻辑与的分配律：a(bc)(ab)(ac) D．关于逻辑或的分配律：a(bc)(ab)(ac)

8．十进制下的无限循环小数（不包括循环节内的数字均为0成均为9的平凡情况），在二进制下有可能是（ ）。

A．无限循环小数(不包括循环节内的数字均为0或均为9的平凡情） B．无限不循环小数 C．有限小数 D．整数 9．（ ）是目前互联网上常用的E-mail服务协议。

A．HTTP B．FTP C．POP3 D．SMTP 10．以下关于计算复杂度的说法中，正确的有（ ）。

A．如果一个问题不存在多项式时间的算法，那它一定是NP类问题 B．如果一个问题不存在多项式时间的算法，那它一定不是P类问题 C．如果一个问题不存在多项式空间的算法，那它一定是NP类问题 D．如果一个问题不存在多项式空间的算法，那它一定不是P类问题 三、问题求解（共2题，每题5分，共计10分）

1． 本题中，我们约定布尔表达式只能包含p，q，r三个布尔变量，以及“与”（∧）、“或”（∨）、“非”（￢）三种布尔运算。如果无论p，q，r如何取值，两个布尔表达式的值总是相同，则称它们等价。例如(p∨q)∨r和p∨(q∨r)等价，p∨￢p和q∨￢q也等价；而p∨q和p∧q不等价。那么两两不等价的布尔表达式最多有 个。

2． 对于一棵二叉树，独立集是指两两互不相邻的节点构成的集合。例如，图1有5个不同的独立集（1个双点集合，3个单点集合、1个空集），图2有14个不同的独立集。那么图3有 个不同的独立集。

三、阅读程序写结果。（共4题，每题8分，共计32分） 1． var n,i,temp,sum:integer; a :array[1..100] of integer; begin readln(n); for i:=1 to n do read(a[i]); for i:=1 to n-1 do if a[i]>a[i+1] then begin temp := a[i]; a[i] := a[i+1]; a[i+1] := temp; end; for i:=n downto 2 do if a[i]40 70 50 70 20 40 10 30 输出：______________

2．var n,i,ans:integer;

function gcd(a,b :integer) : integer; begin

if a mod b=0 then gcd :=0; else gcd := gcd(b,a mod b); end; begin readln(n); ans := 0; for i:=1 to n do if gcd(n,i)=i then ans := ans + 1; writeln(ans); end.

输入：120

输出：_____________ 3． var data : array[1..20] of integer; n,i,h,ans : integer; procedure merge; begin data[h-1] := data[h-1] + data[h]; dec(h); inc(ans); end; begin readln(n); h := 1; data[h] := 1; ans := 0; for i:=2 to n do begin inc(h); data[h] := 1; while (h>1) and (data[h]=data[h-1]) do merge; end; writeln(ans); end. （1） 输入：8

输出：______________ （4分） （2）

输入：2012

输出：______________ （4分）

4． var left, right, father :array[1..20] of integer; sl, s2, s3 :string; n,ana :integer;

procedure check(x :integer); begin

if left[x]>0 then check(left[x)); s3 := s3 + sl[x];

if right[x]>0 then check(right[x]); end;

procedure calc(x,dep :integer); begin

ans:= ans + dep*(ord(sl[x])-ord('A')+1); if left[x] > 0 then calc(left[x],dep+l); if right[x]> 0 then calc(right[x),dep+l); end;

procedure dfs(x,th :integer); begin if th = n+1 then begin s3 :=''; check(1); if s2=s3 then

begin ans := 0; calc(1,1); writeln(ans); end; exit; end; if (left[x]=0) and (right[x]=0) then begin

left[x) := th; father[th] := x; dfs(th, th+1); father[th] := 0; left[x] := 0; end; if right[x] = 0 then begin

right[x] := th; father[th] := X; dfs(th, th+1); father[th] := 0; right[x] := 0; end; if (father[x] > 0) then dfs(father[x],th); end;

begin readln(s1); readln(s2); n := length(s1); fillchar(left,sizeof(left),0); fillchar(right,sizeof(right),0); fillcahr(father,sizeof(father),0); dfs(1,2); end. 输入： ABCDEF BCAEDF

输出：____________

五、完善程序（第1题第2空3分，其余每空2.5分，共计28分） 1．（排列数）输入两个正整数n,m(1n20,1mn) ，在1输入：3 2 输出：1 2

1 3 2 1 2 3 3 1

3 2

const SIZE=20; var used :array [1..SIZE] of boolean; data :array [1..SIZE] of integer; n,m,i,j,k :integer; flag :boolean; begin readln(n,m); fillchar(used,sizeof(used)，false); for i:=1 to m do begin

n 中任取m个数，按字典序从小到大输出所有这样的排列。例如

data[i] := i;

used[i] := true; end; flag := true; while flag do begin for i:=1 to m-1 do write(data[i],' '); writeln(data[m]); flag := ① ; for i := m downto 1 do begin ② ; for j := data[i]+1 to n do if used[j] = false then begin used[j] := true; data[i] := ③ ; flag := true; break; end; if flag then begin for k:= i+l to m do for j:= 1 to ④ do if used[j]=false then begin data[k] := j; used[j] := true; break; end; ⑤ ; end; end; end; end.

2．(新壳栈)小Z设计了一种新的数据结构“新壳栈”。首先，它和传统的栈一样支持压入、弹出操作。此外，其栈顶的前c个元素是它的壳，支持翻转操作。其中，c>2是一个固定的正整数，表示壳的厚度。小Z还希望，每次操作，无论是压入、弹出还是翻转，都仅用与c无关的常数时间完成。聪明的你能帮助她编程实现“新壳栈”吗?

程序期望的实现效果如以下两表所示。其中，输入的第一行是正整数c，之后每行输入都是一条指令。另外，如遇弹出操作时栈为空，或翻转操作时栈中元素不足c个，应当输出相应的错误信息。

指令 1[空格]e 2 3 0 涵义 在栈顶压入元素e 弹出（并输出）栈顶元素 翻转栈顶的前c个元素 退出 表1：指令的涵义

输入 3 1 1 1 2 1 3 1 4 3 1 5 3 2 2 2 输出 3 2 5 栈中的元素 （左为栈底，右为栈顶） 1 1 2 1 2 3 1 2 3 4 1 4 3 2 1 4 3 2 5 1 4 5 2 3 1 4 5 2 1 4 5 1 4 说明 输入正整数c 压入元素1 压入元素2 压入元素3 压入元素4 翻转栈顶的前c个元素 压入元素5 翻转栈顶的前c个元素 弹出栈顶元素3 弹出栈顶元素 2 弹出栈顶元素 5 3 2 2 2 0 错误信息 4 1 错误信息 1 4 1 空 空 空 由于栈中元素不足c个，无法翻转，故操作失败，输出错误信息 弹出栈顶元素4 弹出栈顶元素1 由于栈中元素不足c个，无法翻转，故操作失败，输出错误信息 退出 表2：输入输出样例

const

NSIZE = 100000;

CSIZE = 1000; var n,c,r,tail,head :longint; s : array[1..NSIZE] of longint; //数组s模拟一个栈，n为栈的元素个数 q :array[1..CSIZE] of longint; //数组q模拟一个循环队列，tail为队尾的下标，head为队头的下标 direction,empty :boolean;

function previous(k :longint) :longint; begin if direction then previous := ((k+c-2) mod c) + 1; else previous := (k mod c) + 1; end;

function next(k :longint) :longint; begin if direction then ① else next := ((k+c-2) mod c)+1; end;

procedure push; var element :longint; begin read(element); if next(head) = tail then begin inc(n); ② ; tail := next(tail); end; if empty then empty := false else head := next(head); ③ := element; end;

procedure pop; begin if empty then begin writeln('Error: the stack is empty!'); exit; end: writeln( ④ ); if tail = head then empty := true else begin

head := previous(head); if n > 0 then begin

tail := previous(tail); ⑤ := s[n]; dec(n); end; end; end;

procedure reverse; var

temp :longint; begin if ⑥ = tail then begin

direction := not direction; temp := head; head := tail; tail := temp; end else

writeln('Error:less than',c,' elements in the stack!'); end;

begin readln(c); n := 0; tail := 1; head := 1; empty := true; direction := true; repeat read(r); case r of 1 : push; 2 : pop; 3 : reverse; end; until r = 0; end.