《第十八届2012初赛C++及答案_》由会员分享，可在线阅读，更多相关《第十八届2012初赛C++及答案_（11页珍藏版）》请在金锄头文库上搜索。
1、1 / 11第十八届全国青少年信息学奥林匹克联赛初赛提高组 C+ 语言试题 （竞赛时间： 2012年 10月 13日 14:3016:30 ）一、单项选择题（共 10题，每题 1.5 分，共计 15分；每题有且仅有一个正确选项）1.目前计算机芯片（集成电路）制造的主要原料是（），它是一种可以在沙子中提炼出的 物质。A.硅 B.铜 C.锗 D.铝 2.（）是主要用于显示网页服务器或者文件系统的HTML 文件内容，并让用户与这些文件交互的一种软件。 A.资源管理器 B.浏览器 C.电子邮件 D.编译器 3.目前个人电脑的（）市场占有率最靠前的厂商包括 Intel 、AMD 等公司。 A.显示器 B
2、.CPU C.内存 D.鼠标 4.无论是 TCP/IP模型还是 OSI模型，都可以视为网络的分层模型，每个网络协议都会被归入某 一层中。如果用现实生活中的例子来比喻这些“层”，以下最恰当的是( ）。 A.中国公司的经理与伊拉克公司的经理交互商业文件B.军队发布命令C.国际会议中，每个人都与他国地位对等的人直接进行会谈D.体育比赛中，每一级比赛的优胜者晋级上一级比赛2 / 115.如果不在快速排序中引入随机化，有可能导致的后果是（）。 A.数组访问越界 B.陷入死循环 C.排序结果错误 D.排序时间退化为平方级 6.1946年诞生于美国宾夕法尼亚大学的 ENIAC 属于（）计算机。 A.电子管
3、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.仿生学的
4、问世开辟了独特的科学技术发展道路。人们研究生物体的结构、功能和工作原 理，并将这些原理移植于新兴的工程技术之中。以下关于仿生学的叙述，错误的是（）。 A.由研究蝙蝠，发明雷达 B.由研究蜘蛛网，发明因特网 C.由研究海豚，发明声纳 D.由研究电鱼，发明伏特电池二、不定项选择题（共 10题，每题 1.5 分，共计 15分；每题有一个或多个正确选项，多选或 少选均不得分） 1.如果对于所有规模为 n的输入，一个算法均恰好进行（）次运算，我们可以说该算法的时间复杂度为 O(2n) 。 A.2n+ 1B.3nC.n*2n D.22n2.从顶点 A0出发，对有向图（）进行广度优先搜索（ BFS ）时，一
5、种可能的遍历顺序是 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。若12345,v v v
6、 v v是图 G 上的顶点，且它们之间两两都存路径可达，则以下说法正确的有（）。A1v到2v的最短路径可能包含一个环B1221( ,)(,)d v vd v vC131223(,)( ,)(,)d v vd v vd v v3 / 11D如果12345vvvvv是1v到5v的一条最短路径，那么234vvv是2v到4v的一条最短路径7逻辑异或（）是一种二元运算，其真值表如下所示。a b abFalse False False False True True True False True True True Flase 以下关于逻辑异或的性质，正确的有（）。A交换律：abbaB结合律：()()a
7、bcabcC关于逻辑与的分配律：()()()abcabacD关于逻辑或的分配律：()()()abcabac8十进制下的无限循环小数（不包括循环节内的数字均为0 成均为 9 的平凡情况），在二进制下有可能是（）。A无限循环小数 ( 不包括循环节内的数字均为 0或均为 9的平凡情）B无限不循环小数 C有限小数 D整数9（）是目前互联网上常用的 E-mail 服务协议。AHTTP BFTP C POP3 D SMTP 10以下关于计算复杂度的说法中，正确的有（）。A如果一个问题不存在多项式时间的算法，那它一定是NP类问题B如果一个问题不存在多项式时间的算法，那它一定不是P类问题C如果一个问题不存在多
8、项式空间的算法，那它一定是NP类问题D如果一个问题不存在多项式空间的算法，那它一定不是P类问题三、问题求解（共 2 题，每题 5分，共计 10分）1.本题中，我们约定布尔表达式只能包含p,q,r 三个布尔变量，以及“与”（）、“或” （）、“非”（ ?）三种布尔运算。如果无论 p,q,r 如何取值，两个布尔表达式的值总是相同， 则称它们等价。例如， (pq)r 和 p(qr) 等价， p?p和 q?q也等价；而 pq 和 pq不等 价。那么，两两不等价的布尔表达式最多有 _ 个。2.对于一棵二叉树，独立集是指两两互不相邻的节点构成的集合。例如，图1有 5个不同的独立集 （1个双点集合、 3个单
9、点集合、 1个空集），图 2 有 14个不同的独立集。那么，图 3 有_ 个不同的独立集。4 / 11四、阅读程序写结果（共 4题，每题 8分，其中第 3题的 2 个小题各 4分，共计 32分） 1. #include using namespace std; int n,i,temp,sum,a100; int main() cinn; for(i=1;iai; for(i=1;iai+1) temp=ai; ai=ai+1; ai+1=temp; for(i=n;i=2;i-) if(ai using namespace std; int n,i,ans; int gcd(int a,in
10、t b) if(a%b=0) return b; else return gcd(b,a%b); int main() cinn; ans=0; for(i=1;i using namespace std; const int SIZE=20; int dataSIZE; int n,i,h,ans; void merge() datah-1=datah-1+datah; h-; ans+; int main() cinn; h=1; datah=1; ans=0; for(i=2;i1 cout #include using namespace std; int lefts20,rights
11、20,father20; string s1,s2,s3; int n,ans; void calc(int x,int dep) ans=ans+dep*(s1x-A+1); if(leftsx=0)calc(leftsx,dep+1); if(rightsx=0)calc(rightsx,dep+1); void check(int x) if(leftsx=0)check(leftsx); s3=s3+s1x; if(rightsx=0)check(rightsx); 6 / 11 void dfs(int x,int th) if(th=n) s3=“; check(0); if(s3
12、=s2) ans=0; calc(0,1); cout=0) dfs(father int main() cins1; cins2; n=s1.size() memset(lefts, memset(rights memset(father dfs(0,1); 输入： ABCDEF BCAEDF 输出：_ 五、完善程序（第 1题第 2空 3分，其余每空 2.5 分，共计 28分）7 / 111.（排列数）输入两个正整数 n,m(1 n20,1m n)，在 1n中任取 m个数，按字典序从小到大 输出所有这样的排列。例如 输入：3 2 输出：1 2 1 3 2 1 2 3 3 1 3 2 #inc
13、lude #include Using namespace std; Const int SIZE=25; bool usedSIZE; int dataSIZE; int n,m,i,j,k; bool flag; int main() cinnm; memset(used,false,sizeof(used); for(i=1;i=1;i-) ; for(j=datai+1;j2是一个固定的正整数，表 示壳的厚度。小 Z还希望，每次操作，无论是压入、弹出还是翻转，都仅用与c 无关的常数时间完 成。聪明的你能帮助她编程实现“新壳栈”吗 ? 程序期望的实现效果如以下两表所示。其中，输入的第一行
14、是正整数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 3 错误信息1 4 由于栈中元素不足 c 个，无法翻转，故 操作失败，输出错误信息2 4 1 弹出栈顶元素 4 2 1 空弹出栈顶元素 1 2 错误信息空由于栈中元素不足 c 个，无法翻转，故 操作失败，输出错误信息0 空退出表 2：输入输出样例#include using namespace std; const int NSIZE=100000, 9 / 11CSIZE=1000; int n,
