第十八届2012初赛C++及答案 -

第十八届全国青少年信息学奥林匹克联赛初赛

提高组C++语言试题 （竞赛时间：2012年10月13日14:30~16:30）

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

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

A.硅 B.铜 C.锗 D.铝

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

A.资源管理器 B.浏览器 C.电子邮件 D.编译器

3.目前个人电脑的（ ）市场占有率最靠前的厂商包括Intel、AMD等公司。 A.显示器 B.CPU C.内存 D.鼠标

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

A.中国公司的经理与伊拉克公司的经理交互商业文件

B.军队发布命令

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

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

1 / 11

5.如果不在快速排序中引入随机化，有可能导致的后果是（ ）。 A.数组访问越界 B.陷入死循环

C.排序结果错误 D.排序时间退化为平方级

6.1946年诞生于美国宾夕法尼亚大学的ENIAC属于（ ）计算机。 A.电子管 B.晶体管 C.集成电路 D.超大规模集成电路

7.在程序运行过程中，如果递归调用的层数过多，会因为（ ）引发错误。 A.系统分配的栈空间溢出 B.系统分配的堆空间溢出 C.系统分配的队列空间溢出 D.系统分配的链表空间溢出

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

A.128KB B.1MB C.1GB D.4GB

9.以下不属于目前3G（第三代移动通信技术）标准的是（ ）。 A.GSM B.TD-SCDMA C.CDMA2000 D.WCDMA

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

A.由研究蝙蝠，发明雷达 B.由研究蜘蛛网，发明因特网 C.由研究海豚，发明声纳 D.由研究电鱼，发明伏特电池

二、不定项选择题（共10题，每题1.5分，共计15分；每题有一个或多个正确选项，多选或少选均不得分）

1.如果对于所有规模为n的输入，一个算法均恰好进行（ ）次运算，我们可以说该算法的

n

时间复杂度为O(2)。

n+1nn2nA.2 B.3 C.n*2 D.2

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)

2 / 11

D．如果v1?v2?v3?v4?v5是v1 到v5 的一条最短路径，那么v2?v3?v4是v2 到v4的一条最短路径

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

a?b a b

False False False False True True True False True 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有_________个不同的独立集。

3 / 11

四、阅读程序写结果（共4题，每题8分，其中第3题的2个小题各4分，共计32分） 1. #include using namespace std; int n,i,temp,sum,a[100]; int main() {

cin>>n;

for(i=1;i<=n;i++) cin>>a[i];

for(i=1;i<=n-1;i++) if(a[i]>a[i+1]){ temp=a[i]; a[i]=a[i+1]; a[i+1]=temp; }

for(i=n;i>=2;i--) if(a[i]

for(i=2;i<=n-1;i++) sum+=a[i];

cout<

输入： 8

40 70 50 70 20 40 10 30

2. #include using namespace std; int n,i,ans;

int gcd(int a,int b) {

if(a%b==0) return b; else

return gcd(b,a%b); }

int main() {

cin>>n; ans=0;

for(i=1;i<=n;i++) if(gcd(n,i)==i) ans++; cout<

输出：_________ 4 / 11

输入：120 输出：_________

3. #include using namespace std; const int SIZE=20; int data[SIZE]; int n,i,h,ans; void merge() {

data[h-1]=data[h-1]+data[h]; h--; ans++; }

int main() {

cin>>n; h=1;

data[h]=1; ans=0;

for(i=2;i<=n;i++) {

h++;

data[h]=1;

while(h>1&&data[h]==data[h-1])

merge();

}

cout<

（1）

输入：8 输出：_________（4分） （2）

输入：2012 输出：_________（4分）

4. #include

#include using namespace std;

int lefts[20],rights[20],father[20]; string s1,s2,s3; int n,ans;

void calc(int x,int dep) {

ans=ans+dep*(s1[x]-'A'+1);

if(lefts[x]>=0)calc(lefts[x],dep+1); if(rights[x]>=0)calc(rights[x],dep+1); }

void check(int x) {

if(lefts[x]>=0)check(lefts[x]); s3=s3+s1[x];

if(rights[x]>=0)check(rights[x]);

5 / 11

}

void dfs(int x,int th) {

if(th==n) {

s3=\check(0); if(s3==s2) {

ans=0; calc(0,1);

cout<

return; }

if(lefts[x]==-1&&rights[x]==-1) {

lefts[x]=th; father[th]=x; dfs(th,th+1); father[th]=-1; lefts[x]=-1; }

if(rights[x]==-1) {

rights[x]=th; father[th]=x; dfs(th,th+1); father[th]=-1; rights[x]=-1; }

if(father[x]>=0) dfs(father }

int main() {

cin>>s1; cin>>s2; n=s1.size() memset(lefts, memset(rights memset(father dfs(0,1); } 输入： ABCDEF BCAEDF

输出：_________

五、完善程序（第1题第2空3分，其余每空2.5分，共计28分）

6 / 11

1.（排列数）输入两个正整数n,m(1≤n≤20,1≤m≤n)，在1~n中任取m个数，按字典序从小到大输出所有这样的排列。例如 输入：3 2 输出：1 2

1 3 2 1 2 3 3 1 3 2

#include #include

Using namespace std;

Const int SIZE=25;

bool used[SIZE]; int data[SIZE]; int n,m,i,j,k; bool flag;

int main() {

cin>>n>>m;

memset(used,false,sizeof(used)); for(i=1;i<=m;i++) {

data[i]=i; used[i]=true; }

flag=true; while(flag) {

for(i=1;i<=m-1;i++)cout<

flag= ① ; for(i=m;i>=1;i--) {

② ;

for(j=data[i]+1;j<=n;j++)if(!used[j]) {

used[j]=true;

data[i]=③ ; flag=true; break; }

if(flag) {

for(k=i+1;k<=m;k++)

for(j=1;j<=④ ;j++)if(!used[j]) {

7 / 11

data[k]=j; used[j]=true; break;

}

⑤ ; } } }

}

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

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

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

#include using namespace std;

const int

NSIZE=100000,

8 / 11

CSIZE=1000;

int n,c,r,tail,head,s[NSIZE],q[CSIZE]; //数组s模拟一个栈，n为栈的元素个数

//数组q模拟一个循环队列，tail为队尾的下标，head为队头的下 bool direction,empty;

int previous(int k) {

if(direction)

return((k+c-2)%c)+1; else

return(k%c)+1; }

int next(int k) {

if(direction) ① ; else

return((k+c-2)%c)+1; }

void push() {

int element;

cin>>element;

if(next(head)==tail){ n++;

② ;

tail=next(tail); }

if(empty)

empty=false; else

head=next(head); ③=element; }

void pop() {

if(empty){

cout<<\return; }

cout<<④<

head=previous(head); if(n>0){

9 / 11

tail=previous(tail); ⑤ =s[n]; n--; } }

}

void reverse() {

int temp;

if(⑥ ==tail){ direction=!direction; temp=head; head=tail; tail=temp; } else

cout<<\}

int main() {

cin>>c; n=0; tail=1; head=1; empty=true; direction=true; do{

cin>>r; switch(r){

case 1:push();break; case 2:pop();break; case 3:reverse();break; }

}while(r!=0); return 0; }

10 / 11

11 / 11

本文来源：https://www.bwwdw.com/article/4mlr.html