13高初试题

第十九届全国青少年信息学奥林匹克联赛初赛
提高组Pascal语言试题
竞赛时间：2013年10月13日14：30～16：30
选手注意：
l 试题纸12页答题纸2页满分100分请答题纸作答写试题纸律效
l 电子试备（计算器手机电子词典等）查阅书籍资料
单项选择题（15题题15分计225分题仅正确选项）
1． 32位整型变量占（ ）字节
A．4 B．8 C．32 D．128
2． 二进制数1101十进制（ ）
A．325 B．4125 C．625 D．11125
3． 面事（ ）算法着异曲工妙
前座山山里座庙庙里老尚尚讲事：前座山山里座庙庙里老尚尚讲事：前座山山里座庙庙里老尚尚讲事…………………………’
A．枚举 B．递 C．贪心 D．分治
4． 1948年（ ）热力学中熵引入信息通信领域标志着信息研究开端
A．冯·诺伊曼(John von Neumann) B．图灵（Alan Turing）
C．欧拉（Leonhard Euler） D．克劳德·香农（Claude Shannon）
5． 已知棵二叉树2013节点中（ ）节点2子节点
A．1006 B．1007 C．1023 D．1024
6． 图中果意两点间存路径相连称连通图右图5顶点8条边连通图连通图少删中（ ）条边
A．2 B．3 C．4 D．5
7． 斐波契数列定义：F11F21FnFn1+Fn2（n≥3）果面函数计算斐波契数列第n项时间复杂度（ ）
function F(nlongint)longint
begin
if n<2 then
F1
else
FF(n1)+F(n2)
end
A．O(1) B．O(n) C．O(n2) D．O(Fn)
8． 二叉查找树具性质：节点值左子树节点值右子树节点值二叉查找树（ ）序序列
A．先序遍历 B．中序遍历 C．序遍历 D．宽度优先遍历
9． （261017）分存储某址区间0～10哈希表中果哈希函数h(x)（ ）会产生突中a mod b表示ab余数
A．x mod 11 B．x2 mod 11
C．2x mod 11 D．mod 11中表示取整
10． IPv4协议32位址着断分配址资源日趋枯竭正逐渐（ ）位址IPv6协议取代
A．40 B．48 C．64 D．128
11． 二分图指顶点划分成两部分部分顶点间没边相连简单图12顶点二分图（ ）条边
A．18 B．24 C．36 D．66
12． （ ）种通字符编码世界绝部分语言设定统唯二进制编码满足跨语言跨台文交换目前已收录超十万字符
A．ASCII B．Unicode C．GBK2312 D．BIG5
13． 64位非零浮点数强制转换成32位浮点数（ ）
A．原数 B．原数
C．等原数 D．原数符号相反
14． n顶点m条边带权简单图Dijkstr算法计算单源短路时果堆优先队列进行优化时间复杂度（ ）
A．O(mn+n3) B．O(n2)
C．O((m+n)log n) D．O((m+n2)log n)
15． T(n)表示某算法输入规模n时运算次数果T(1)常数递式T(n)2*T(n 2)+2nT(n) （ ）
A．Θ(n) B．Θ(n log n) C．Θ(n2) D．Θ(n2log n)
二 定项选择题（5题题15分计75分题正确选项选少选均分）
1． 列程序中正确计算12…100100然数sum（初始值0）（ ）
A．
for i1 to 100 do
sumsum+I
B．
i1
while i>100 do
begin
sumsum+I
inc(i)
end
C．
i1
repeat
sumsum+I
inc(i)
until i>100
D．
i1
repeat
sumsum+I
inc(i)
until i<100

2． （ ）均时间复杂度O(n log n)中n排序元素数
A．快速排序 B．插入排序 C．泡排序 D．排序
3． A0作起点面图进行深度优先遍历时（遍历序顶点字母标关）遍历顶点（ ）
A．A1 B．A2 C．A3 D．A4

4． （ ）属NP类问题
A．存P类问题
B．P类问题
C．属P类问题
D．（输入规模）指数时间够解决问题
5． CCF NOIP复赛考试结束（ ）提出申诉会受理
A．源程序文件名写错误
B．源程序保存指定文件夹外位置
C．输出文件文件名错误
D．提交执行文件未提交源程序
三 问题求解（2题题5分计10分题全部答5分没部分分）
1． 某系统称种防窃听方式验证户密码密码n数s1s2…sn均01该系统次机生成n数a1a2…an均01请户回答（s1a1+s2a2+…+snan）2余数果次回答总正确认掌握密码该系统认问答程泄露助破解密码——户没直接发送密码
然事愿违例n4时窃听5次问答：
问答编号
系统生成n数
掌握密码户回答
a1
a2
a3
a4
1
1
1
0
0
1
2
0
0
1
1
0
3
0
1
1
0
0
4
1
1
1
0
0
5
1
0
0
0
0
破解出密码s1 s2 s3 s4
2． 现青蛙初始时n号荷叶某时刻k号荷叶时时刻等概率机跳12…k号荷尔蒙叶直跳1号荷叶止n2时均跳2次n3时均跳25次n5时均跳次

四 阅读程序写结果（4题题8分计32分）
1． var
niinteger
strstring
isPlalindromeBoolean
begin
readln(str)
nLength(str)
isPlalindrometrue

for i1 to (n idv 2) do
begin
if (str[i]<>str[ni+1]) then
isPlalindromefalse
end
if (isPlalindrome) then
writeln(Yes’)
else
writeln(No’)
end

输入：adceecba
输出：
2． var
abuvInuminteger
begin
readln(abuv)
num0
for ia to b do
begin
if (I mod u0)or(I mod v0) then
inc(num)
end
writeln(num)
end

输入：1 1000 10 15
输出：
3． const SIZE100
var
nansIjinteger
heightnumarray[1SIZE] of integer
begin
read(n)
for i1 to n do
begin
read(height[i])
num[i]1
for j1 to i1 do
begin
if ((height[j]num[i])) then
num[i]num[j]+1
end
end
ans0
for i1 to n do
begin
if (num[i]>ans) then
ansans+num[i]
end
writeln(ans)
end

输入：
8
3 2 5 11 12 7 4 10
输出：
4． const SIZE100
var
nmpcountansxyIjinteger
aarray[1SIZE1SIZE] of integer

procedure colour(xyinteger)
begin
inc(count)
a[x][y]1
if (x>1)and(a[x1][y]0) then
colour(x1y)
if (y>1)and(a[x][y1]0) then
colour(xy1)
if (x colour(x+1y)
if (y colour(xy+1)
end

begin
fillchar(asizeof(a)0)
readln(nmp)
for i1 to p do
begin
read(xy)
a[x][y]1
end
ans0
for i1 to n do
for j1 to m do
if a[i][j]0 then
begin
count0
colour(ij)
if (ans anscount
end
writeln(ans)
end

输入：
6 5 9
1 4
2 3
2 4
3 2
4 1
4 3
4 5
5 4
6 4
输出：
五 完善程序（第1题15分第2题13分计28分）
1． （序列重排）全局数组变量a定义：
const int SIZE100
int a[SIZE]n
记录着长度n序列a[1]a[2]…a[n]
现需函数整数p(1≤p≤n)参数实现功：序列a前p数np数调改变p数（np数）间相位置例长度5序列12345p2时重排结果34512
种朴素算法实现需求时间复杂度O(n)空间复杂度O(n)：

procedure swap1(plongint)
var
Ijlongint
barray[1SIZE] of longint
begin
for i1 to p do
b[ （1） ]a[i] （2分）
for ip+1 to n do
b[ip]a[i]
for i1 to n do
a[i]b[i]
end

时间换空间时间复杂度O(n2)空间复杂度O(1)算法：

procedure swap2(plongint)
var
Ijtemplongint
begin
for ip+1 to n do
begin
tempa[i]
for jI downto （2） do （2分）
a[j]a[j1]
（3） temp （2分）
end
end

事实种更算法时间复杂度O(n)空间复杂度O(1)

procedure swap3(plongint)
var
start1end1start2end2Ijtemplongint
begin
start11
end1p
start2p+1
end2n
while true do
begin
istar1
jstart2
while (i begin
tempa[i]
a[i]a[j]
a[j]temp
inc(i)
inc(j)
end
if i start1i
else if （4） then （3分）
begin
start1 （5） （3分）
end1 （6） （3分）
start2j
end
else
break
end
end
2． （两元序列）试求整数序列中长仅包含两整数连续子序列子序列列长输出意例序列1 1 2 3 2 3 2 3 3 1 1 1 3 1中两段满足条件长子序列长度均7分划线划线标出

program two

const SIZE100

var
nIjcur1cur2count1count2
ans_lengthans_startans_endlongint
cur1cur2分表示前子序列中两整数
count1count2分表示cur1cur2前子序列中出现次数
aarray[1SIZE] of longint

begin
readln(n)
for i1 to n do
read(a[i])
i1
j1
ij分表示前子序列首尾保证中两整数
while (j inc(j)
cur1a[i]
cur2a[j]
count1 （1） （3分）
count21
ans_lengthji+1
while j begin
inc(j)
if a[j]cur1 then
inc(count1)
else if a[j]cur2 then
inc(count2)
else begin
if a[j1] （2） then （3分）
while count2>0 do
begin
while count2>0 do
begin
if a[i]cur1 then
dec(count1)
else
dec(count2)
inc(i)
end
cur2a[j]
count21
end
else begin
while count1>0 do
begin
if a[i]cur1 then
（3） （2分）
else
（4） （2分）
inc(i)
end
（5） （3分）
count11
end
end
if (ans_length begin
ans_lengthji+1
ans_startI
ans_endj
end
end
for ians_start to ans_end do
write(a[i]’ )
end
文档香网(httpswwwxiangdangnet)户传

《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档