第十七届全国青少年信息学奥林匹克联赛提高组初赛试题Word文档下载推荐.docx
《第十七届全国青少年信息学奥林匹克联赛提高组初赛试题Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《第十七届全国青少年信息学奥林匹克联赛提高组初赛试题Word文档下载推荐.docx（16页珍藏版）》请在冰点文库上搜索。
A10B11C12D20112在布尔逻辑中，逻辑“或”的性质有（）。
A交换律：
PVQ=QVPB结合律：
PV（QVR）=（PVQ）VRC幂等律：
PVP=PD有界律：
PV1=1（1表示逻辑真）3一个正整数在十六进制下有100位，则它在二进制下可能有（）位。
A399B400C401D4044汇编语言（）。
A是一种与具体硬件无关的程序设计语言B在编写复杂程序时，相对于高级语言而言代码量大，且不易调试C可以直接访问寄存器、内存单元、I/O端口D随着高级语言的诞生，如今已被完全淘汰，不再使用5现有一段文言文，要通过二进制哈夫曼编码进行压缩。
简单起见，假设这段文言文只由4个汉字“之”、“乎”、“者”、“也”组成，它们出现的次数分别为700、600、300、400。
那么，“也”字的编码长度可能是（）。
A1B2C3D46生物特征识别，是利用人体本身的生物特征进行身份认证的一种技术。
目前，指纹识别、虹膜识别、人脸识别等技术已广泛应用于政府、银行、安全防卫等领域。
以下属于生物特征识别技术及其应用的是（）。
A指静脉验证B步态验证CATM机密码验证D声音验证7对于序列“7、5、1、9、3、6、8、4”，在不改变顺序的情况下，去掉（）会使逆序对的个数减少3。
A7B5C3D68计算机中的数值信息分为整数和实数（浮点数）。
实数之所以能够表示很大或者很小的数，是由于使用了（）。
A阶码B补码C反码D较长的尾数9对右图使用Dijkstra算法计算S点到其余各点的最短路径长度时，到B点的距离dB初始时赋为8，在算法的执行过程中还会出现的值有（）。
A3B7C6D510为计算机网络中进行数据交换而建立的规则、标准或约定的集合称为网络协议。
下列英文缩写中，（）是网络协议AHTTPBTCP/IPCFTPDWWW三问题求解（共2题，每空5分，共计10分）1平面图可以在画在平面上，且它的边仅在顶点上才能相交的简单无向图。
4个顶点的平面图至少有6条边，如右图所示。
那么，5个顶点的平面图至少有条边。
2定义一种字符串操作，一次可以将其中一个元素移到任意位置。
举例说明，对于字符串“BCA”可以将A移到B之前，变字符串“ABC”。
如果要将字符串“DACHEBGIF”变成“ABCDEFGHI”最少需要_次操作。
四阅读程序写结果（共4题，每题8分，共计32分）1#include#include#defineSIZE100;
intmain（）intn,i,sum,x,aSIZE;
scanf（“%d”,&
n）;
memset（a,0,sizeof（a）;
for（i=1;
i=n;
i+）scanf（“%d”,&
x）;
ax+;
i=0;
sum=0;
while（sum（n/2+1）i+;
sum+=ai;
Printf（“%dn”,i）;
return0;
输入：
1145664332321输出：
2#includeintn;
voidf2（intx,inty）;
voidf1（intx,inty）if（xn）f2（y,x+y）;
voidf2（intx,inty）Printf（“%d”,x）;
f1（y,x+y）;
intmain（）Scanf（“%d”,&
f1（0,1）;
30输出：
_3#include#defineV100intn,m,ans,eVV;
boolvisitedV;
voiddfs（intx,intlen）inti;
visitedx=true;
if（lenans）ans=len;
i+）if（visitedi=0）&
（exi!
=-1）dfs（i,len+exi）;
visitedx=false;
intmain（）inti,j,a,b,c;
scanf（“%d%d”,&
n,&
m）;
i+）for（j=1;
j=m;
j+）eij=-1;
i=m;
i+）Scanf（“%d%d%d”,&
a,&
b,&
c）;
eab=c;
eba=c;
i+）visitedi=false;
ans=0;
i+）dfs（i,0）;
printf（“%dn”,ans）;
46121023203430414013502460输出：
_4#include#include#defineSIZE10000;
#defineLENGTH10;
intn,m,aSIZELENGTH;
inth（intu,intv）intans,i;
i+）if（aui!
=avi）ans+;
returnans;
intmain（）intsum,i,j;
m=1;
while
（1）i=1;
while（in）break;
m+;
ami=1;
for（j=i+1;
j=n;
j+）amj=am-1j;
j+）sum+=h（i,j）;
printf（“%dn”,sum）;
7输出：
_五完善程序（第1题，每空2分，第2题，每空3分，共28分）1.（大整数开方）输入一个正整数n（1n10100），试用二分法计算它的平方根的整数部分。
#include#include#defineSIZE200;
Typedefstructnodeintlen,numSIZE;
/其中len表示大整数的位数；
num1表示个位，num2表示十位，以此类推hugeinttimes（hugeinta,hugeintb）/计算大整数a和b的乘积inti,j;
hugeintans;
memset（ans.num,0,sizeof（ans.num）;
i=a.len;
j=b.len;
j+）+=a.numi*b.numj;
i0）ans.len=a.len+b.len;
elseans.len=a.len+b.len-1;
hugeintadd（hugeinta,hugeintb）/计算大整数a和b的和inti;
if（a.lenb.len）ans.len=a.len;
elseans.len=b.len;
i0）ans.len+;
hugeintaverage（hugeinta,hugeintb）/计算大整数a和b的平均数的整数部分inti;
ans=add（a,b）;
for（i=ans.len;
i=2;
i-）ans.numi-1+=（）*10;
ans.numi/=2;
ans.num1/=2;
if（ans.numans.len=0）ans.len-;
hugeintplustwo（hugeinta）/计算大整数a加2之后的结果inti;
ans=a;
ans.num1+=2;
i=1;
while（i=10）ans.numi+1+=ans.numi/10;
ans.numi%=10;
i+;
if（ans.numans.len+10）;
boolover（hugeinta,hugeintb）/若大整数ab则返回true，否则返回falseinti;
if（）returnfalse;
if（a.lenb.len）returntrue;
for（i=a.len;
i-）if（a.numib.numi）returntrue;
returnfalse;
intmain（）strings;
inti;
hugeinttarget,left,middle,right;
scanf（“%s”,s）;
memset（target.num,0,sizeof（target.num）;
target.len=s.length（）;
i-）printf（“%d”,left.numi）;
2.（笛卡尔树）对于一个给定的两两不等的正整数序列，笛卡尔树是这样的一棵二叉树：
首先，它是一个最小堆，即除了根结点，每个节点的权值都大雨父节点的权值；
其次，它的中序遍历恰好就是给定的序列。
例如，对于序列7、2、12、1、10、5、15、3，下图就是一棵对应的笛卡尔树。
现输入序列的规模n（1n100）和序列的n个元素，试求其对应的笛卡尔树的深度d（根节点深度为1），以及有多少个叶子节点的深度为d。
#include#defineSIZE105;
#defineINFINITY1000000intn,aSIZE,maxDeep,num;
voidsolve（intleft,intright,intdeep）inti,j,min;
if（deepmaxDeep）maxDeep=deep;
num=1;
elseif（deep=maxDeep）;
min=INFINITY;
for（i=left;
iai）min=ai;
if（leftj）;
if（jright）;
intmain（）inti;
scanf（“%d”，&
i+）scanf（“%d”，&
ai）;
maxDeep=0;
solve（1,n,1）;
printf（“%d%dn”,maxDeep,num）;
升级会员 