17信息学奥林匹克竞赛

第17届全国信息学奥林匹克竞赛省预赛试题。

(需要两个小时来提高群C++语言)

●●●所有试题的答案都要求写在答题卡上，无效●●

a、单项选择题(* * 10题，每题1.5分，* * 15分。每个问题有且只有一个正确选项。)

1.在二进制中，10101+()= 1100110。

a . 1011 B . 1101 c . 1010d . 1111

2.字符“A”的ASCII码是十六进制的41，字符“Z”的ASCII码是十六进制的()。

A.66b.5a.c.50d .要看具体电脑。

3.右图是一棵二叉树，其前序遍历是()。

A.ABDEFC B.DBEFAC C.DFEBCA D.ABCDEF

4.寄存器是()的重要组成部分。

A.硬盘b .缓存c .内存d .中央处理器(CPU)

5.广度优先搜索需要的数据结构是()。

A.链表b .队列c .栈d .哈希表

6.用高级语言编写程序时，“空间复杂度”中的空间一般指()。

A.程序运行时理论上占用的内存空间。

B.程序运行时理论上占用的数组空间

C.程序运行时理论上占用的硬盘空间

D.程序源文件占用的理论硬盘空间

7.利用快速排序的分治思想，可以实现一个求第k个大数的程序。假设不考虑极端最坏的情况，理论上可以实现的最低算法时间复杂度是()。

A.O(N2)B . O(n log n)C . O(n)d . O(1)

8.为了解决web应用中的不兼容问题，保证信息的畅通，()制定了一系列标准，涉及HTML、XML、CSS等。，建议开发者遵照执行。

A.微软b .美国计算机协会(ACM) C .联合国教科文组织d .万维网联盟(W3C)

9.体育课铃响了，学生们一个接一个地奔向操场，按照老师的要求从高到低站成一排。当每个同学按顺序来到操场，从排尾走到头，找到第一个比自己高的同学，站在他身后。这种排队方法类似于()算法。

A.快速排序b .插入排序c .冒泡排序d .归并排序

10.1956()被授予肖克利、约翰·巴丁和布拉顿。

A.诺贝尔物理学奖b .约翰？冯？诺伊曼奖

C.图灵奖d .加特纳奖(唐纳德e .克努特奖)

二、不定选择题(* * 10题，每题1.5分，* * * 15分。每题正确答案数不少于1。选多选少都不计分)。

1.如果根节点的深度是1，恰好有2011个叶节点的二叉树的深度可能是()。

a . 10 b . 11 c . 12d . 2011

2.在布尔逻辑中，逻辑或的本质是()。

A.转换定律:PVQ = QVP

B.有约束力的法律:PV(QVR)=(PVQ)VR

C.幂等定律:PVP = P

D.有界定律:PV1 = 1(1代表逻辑真)。

3.如果一个正整数有100个十六进制位，那么它可能有()个二进制位。

A.399 B.400 C.401 D.404

4.汇编语言()。

是一种独立于特定硬件的编程语言。

B.写复杂程序时，相比高级语言，代码量大，不容易调试。

直接访问寄存器、存储单元和I/O端口。

d随着高级语言的诞生，已经完全被淘汰，不再使用。

5.现有的文言文应该用二进制霍夫曼编码压缩。为简单起见，假设这篇文言文仅由四个汉字组成，即直、胡、者、也，分别出现700、600、300、400次。那么，“也”字的编码长度可能是()。

A.1

6.生物识别是一种利用人体的生物特征进行身份认证的技术。目前，指纹识别、虹膜识别、人脸识别等技术已经广泛应用于政府、银行、安防等领域。下列属于生物识别技术及其应用的是()。

A.手指静脉验证b .步态验证C. ATM密码验证d .语音验证

7.对于序列“7，5，1，9，3，6，8，4”，移除()将在不改变顺序的情况下减少3个反向对。

a7 b . 5 c . 3d . 6

8.计算机中的数值信息分为整数和实数(浮点数)。由于()的使用，实数可以表示很大或很小的数。

A.顺序码b .补码c .反码d .尾数较长

9.用Dijkstra算法计算S点到右边其他点的最短路径长度时，到B点的距离d[B]初始赋为8，算法实现过程中会有()。

A.3 B. 7 C.6 D.5

10.为计算机网络中的数据交换而建立的一套规则、标准或约定称为网络协议。在下列英文缩写中，()是网络协议。

A.HTTP B.TCP/IP

三。解题(***2题，每空5分，* * * 10分)

1.平面图可以是绘制在平面上的简单无向图，它的边只能在顶点相交。有四个顶点的平面至少有六条边，如右图所示。那么，一个有五个顶点的平面至少有一条边。

2.定义一个字符串操作，其中一个元素可以一次移动到任意位置。例如，对于字符串“BCA”，您可以将A移动到B之前，并更改字符串“ABC”。把字符串“DACHEBGIF”改成“ABCDEFGHI”至少需要_ _ _ _ _ _次。

四个。阅读程序写作成绩(***4题，每题8分，32分***)

# include & ltiostream & gt

# include & ltcstring & gt

使用命名空间std

const int SIZE = 100；

int main()

{

int n，I，sum，x，a[SIZE]；

CIN & gt；& gtn；

memset(a，0，sizeof(a))；

for(I = 1；我& lt= n；i++){

CIN & gt；& gtx；

a[x]++；

}

I = 0；

sum = 0；

while(sum & lt；(n/2+1)){

i++；

sum+= a[I]；

}

cout & lt& lt我& lt& ltendl

返回0；

}

输入:

4 5 6 6 4 3 3 2 3 2 1

输出:

# include & ltiostream & gt

使用命名空间std

int n；

void f2(int x，int y)；

void f1(int x，int y)

{

if(x & lt；n)

f2(y，x+y)；

}

void f2(int x，int y)

{

cout & lt& ltx & lt& lt' ';

f1(y，x+y)；

}

int main()

{

CIN & gt；& gtn；

f1(0，1)；

返回0；

}

输入:30

输出:_ _ _ _ _ _ _ _ _ _

# include & ltiostream & gt

使用命名空间std

const int V = 100；

int n，m，ans，e[V][V]；

布尔拜访了[V]；

void dfs(int x，int len)

{

int I；

visited[x]= true；

if(len & gt；ans)

ans = len

for(I = 1；我& lt= n；i++)

如果((！已访问[I])& amp；& amp(e[x][i]！=-1) )

dfs(i，len+e[x][I])；

visited[x]= false；

}

int main()

{

int i，j，a，b，c；

CIN & gt；& gtn & gt& gtm；

for(I = 1；我& lt= n；i++)

for(j = 1；j & lt= m；j++)

e[I][j]=-1；

for(I = 1；我& lt= m；i++)

{

CIN & gt；& gta & gt& gtb & gt& gtc；

e[a][b]= c；

e[b][a]= c；

}

for(I = 1；我& lt= n；i++)

visited[I]= false；

ans = 0；

for(I = 1；我& lt= n；i++)

dfs(i，0)；

cout & lt& ltans & lt& ltendl

返回0；

}

输入:

4 6

1 2 10

2 3 20

3 4 30

4 1 40

1 3 50

2 4 60

输出:_ _ _ _ _ _ _ _ _

# include & ltiostream & gt

# include & ltcstring & gt

# include & lt字符串& gt

使用命名空间std

const int SIZE = 10000；

const int长度= 10；

int n，m，a[大小][长度]；

int h(int u，int v)

{

int ans，I；

ans = 0；

for(I = 1；我& lt= n；i++)

如果(a[u][i]！=a[v][i])

ans++；

返回ans

}

int main()

{

int sum，I，j；

CIN & gt；& gtn；

memset(a，0，sizeof(a))；

m = 1；

while(1)

{

I = 1；

而((i & lt= n)& amp；& amp(a[m][i]==1))

i++；

如果(i & gtn)

打破；

m++；

a[m][I]= 1；

for(j = I+1；j & lt= n；j++)

a[m][j]= a[m-1][j]；

}

sum = 0；

for(I = 1；我& lt= m；i++)

for(j = 1；j & lt= m；j++)

sum+=h(i，j)；

cout & lt& ltsum & lt& ltendl

返回0；

}

输入:7

产出:_ _ _ _ _ _ _ _

动词（verb的缩写）完善方案(1题2分，2题3分，* * * 28分)。

1.(大整数根)输入一个正整数n(1≤n≤10100)，尝试用二分法计算其平方根的整数部分。

# include & ltiostream & gt

# include & lt字符串& gt

使用命名空间std

const int SIZE = 200

结构庞大{

int len，num[SIZE]；

};

//其中len表示大整数的位数；Num[1]表示一位，num[2]表示十位，依此类推。

hugeint次(hugeint a，hugeint b)

//计算大整数A和b的乘积。

{

int i，j；

hugeint ans

memset(ans.num，0，sizeof(ans . num))；

for(I = 1；我& lt= a.leni++)

for(j = 1；j & lt= b.lenj++)

① +=a号[i]*b号[j]；

for(I = 1；我& lt= a . len+b . len；i++){

ans . num[I+1]+= ans . num[I]/10；

② ;

}

if(ans . num[a . len+b . len]& gt；0)

ans . len = a . len+b . len；

其他

ans . len = a . len+b . len-1；

返回ans

}

hugeint add(hugeint a，hugeint b)

//计算大整数A和b的和。

{

int I；

hugeint ans

memset(ans.num，0，sizeof(ans . num))；

if(a . len & gt；文学硕士)

ans . len = a . len；

其他

ans . len = b . len；

for(I = 1；我& lt= ans.leni++){

ans . num[I]+=③；

ans . num[I+1]+= ans . num[I]/10；

ans . num[I]% = 10；

}

if(ans . num[ans . len+1]& gt；0)

ans . len++；

返回ans

}

hugeint平均值(hugeint a，hugeint b)

//计算大整数A和b的平均值的整数部分。

{

int I；

hugeint ans

ans=add(a，b)；

for(I = ans . len；我& gt=2;我- ){

ans . num[I-1]+=(④)* 10；

ans . num[I]/= 2；

}

ans . num[1]/= 2；

if(ans . num[ans . len]= 0)

ans . len-；

返回ans

}

胡根特加二号

//计算大整数a加2后的结果。

{

int I；

hugeint ans

ans = a；

ans . num[1]+= 2；

I = 1；

而((i & lt= ans . len)& amp；& amp(ans . num[I]& gt；=10) ){

ans . num[I+1]+= ans . num[I]/10；

ans . num[I]% = 10；

i++；

}

if(ans . num[ans . len+1]& gt；0)

⑤ ;

返回ans

}

布尔结束(休伊特a，休伊特b)

//如果整数是一个& gtb返回真，否则返回假。

{

int I；

如果(⑥)

返回false

if(a . len & gt；文学硕士)

返回true

for(I = a . len；我& gt=1;我- ){

if(a . num[I]& lt；编号[i])

返回false

if(a . num[I]& gt；编号[i])

返回true

}

返回false

}

int main()

{

字符串s；

int I；

hugeint目标，左，中，右；

CIN & gt；& gts；

memset(target.num，0，sizeof(target . num))；

target.len=s.length()。

for(I = 1；我& lt= target.leni++)

target . num[I]= s[target . len-I]-⑦；

memset(left.num，0，sizeof(left.num))。

left . len = 1；

left . num[1]= 1；

右=目标；

做{

中间=平均(左，右)；

if(over( ⑧))

右=中；

其他

左=中；

}while(！over(plustwo(左)，右))；

for(I = left . len；我& gt=1;我-)

cout & lt& ltleft . num[I]；

返回0；

}

2.(笛卡儿树)对于给定的两两正整数序列，笛卡儿树是这样的二叉树:首先，它是一个最小堆，即除了根节点之外的每个节点的权重都大于父节点的权重；其次，它的中间序列遍历恰好是一个给定的序列。比如序列7，2，12，1，10，5，15，3，下图就是对应的笛卡尔树。输入序列的小数位数n (1 ≤ n

# include & ltiostream & gt

使用命名空间std

const int SIZE = 100+5；

const int INFINITY = 1000000；

int n，a[SIZE]，maxDeep，num

void solve(int left，int right，int deep)

{

int i，j，min

if(deep & gt；maxDeep){

maxDeep = deep

num = 1；

}

else if(deep==maxDeep)

① ;

min=无穷大；

for(I =左；我& lt=对；i++)

if(min & gt；一个[我]{

min = a[I]；

② ;

}

if(left & lt；j)

③ ;

if(j & lt；右)

④ ;

}

int main()

{

int I；

CIN & gt；& gtn；

for(I = 1；我& lt= n；i++)

CIN & gt；& gta[I]；

max deep = 0；

求解(1，n，1)；

cout & lt& ltmaxDeep & lt& lt' & lt& ltnum & lt& ltendl

返回0；

}

NOIP2011年改进组(C++语言)参考答案及评分标准

1.选择题:(65438+每题0.5分)

1.B 2。B 3。A 4。D 5。B

6.一个7。C 8。D 9。B 10。A

二、不定选择题(* * 10题，每题1.5分，* * * 15分。每个问题的正确答案数大于或等于1。选多选少都不计分)。

1.CD 2。ABCD 3。AB 4。公元前5年。公元前

6.ABD 7。CD 8。一个9。BCD 10。美国广播公司

三、解题:(***2题，每空5分，* * * 10分)

1.9

2.4

四、阅读程序写结果(***4题，每题8分，32分作***)

1.3

2.1 2 5 13 34

3.150

4.57344

五、完善程序(65438号+0，每空2分，2号，每空3分，* * * 28分)。

(注意:在下面的过程中可能有一些等价的填空方法。各省可以请自己的专家在电脑上审核，不一定要报科委审核。)

① ans.num[i + j - 1]

②ans num[I]= ans num[I]mod 10

③甲号[i] +乙号[i]

④ ans.num[i]% 2(或ans.num[i] & 1)

⑤ ans.len++(或ans.len = ans.len+1)

⑥a . len & lt；贝伦

7英尺0英寸(或48英寸)

⑧次(中、中)、目标

① num++(或num = num+1)

② j = i

③求解(左，j - 1，深+ 1)

④求解(j + 1，右，深+ 1)