NOIP提高组C初赛试题与答案.docx
《NOIP提高组C初赛试题与答案.docx》由会员分享，可在线阅读，更多相关《NOIP提高组C初赛试题与答案.docx（15页珍藏版）》请在冰点文库上搜索。
NOIP提高组C初赛试题与答案
2020第十五届全国青青年信息学奥林匹克联赛初赛试题
（提高组C++语言二小时完成）
全数试题答案均要求写在答卷纸上，写在试卷纸上一概无效
一．单项选择题（共10题，每题分，共计15分。
每题有且仅有一个正确答案。
）
一、关于图灵机下面的说法哪个是正确的：
A）图灵机是世界上最先的电子运算机。
B）由于大量利用磁带操作，图灵机运行速度很慢。
C）图灵机只是一个理论上的计算模型。
D）图灵机是英国人图灵发明的，在二战中为破译德军的密码发挥了重要作用。
二、关于BIOS下面的说法哪个是正确的：
A）BIOS是运算机大体输入输出系统软件的简称。
B）BIOS里包括了键盘、鼠标、声卡、图形界面显器等常常利用输入输出设备的驱动程序。
C）BIOS一样由操作系统厂商来开发完成。
D）BIOS能提供各类文件拷贝、复制、删除和目录爱惜等文件治理功能。
3、已知大写字母A的ASCII编码为65（十进制），那么大写字母J的十六进制ASCII编码为：
A）48B）49C）50D）以上都不是
4、在字长为16位的系统环境下，一个16位带符号整数的二进制补码为101。
其对应的十进制整数应该是：
A）19B）-19C）18D）-18
五、一个包括n个分支结点（非叶结点）的非空满k叉树，k>=1，它的叶结点数量为：
A）nk+1B）nk-1C）（k+1）n-1D.（k-1）n+1
6.表达式a*（b+c）-d的后缀表达式是：
A）abcd*+-B）abc+*d-C）abc*+d-D）-+*abcd
7、最优前缀编码，也称Huffman编码。
这种编码组合的特点是关于较频繁利用的元素给与较短的唯一编码，以提高通信的效率。
下面编码组合哪一组不是合法的前缀编码。
A）（00，01，10，11）
B）（0，1，00，11）
C）（0，10，110，111）
D）（1，01，000，001）
八、快速排序平均情形和最坏情形下的算法时刻复杂度别离为：
A）平均情形O（nlog2n），最坏情形O（n2）
B）平均情形O（n），最坏情形O（n2）
C）平均情形O（n），最坏情形O（nlog2n）
D）平均情形O（log2n），最坏情形O（n2）
9、右图给出了一个加权无向图，从顶点V0开始用prim算法求最小生成树。
则依次加入最小生成树的顶点集合的顶点序列为：
A）V0,V1,V2,V3,V5,V4
B）V0,V1,V5,V4,V3,V3
C）V1,V2,V3,V0,V5,V4
D）V1,V2,V3,V0,V4,V5
10、全国信息学奥林匹克的官方网站为参与信息学竞赛的教师同窗们提供相关的信息和资源，请问全国信息学奥林匹克官方网站的网址是：
A）B）D）二．不定项选择题（共10题，每题分，共计15分。
每题正确答案的个数很多于1。
多项选择或少选均不得分）。
一、关于CPU下面哪些说法是正确的：
A）CPU全称为中央处置器（或中央处置单元）。
B）CPU能直接运行机械语言。
C）CPU最先是由Intel公司发明的。
D）一样主频下，32位的CPU比16位的CPU运行速度快一倍。
二、关于运算机内存下面的说法哪些是正确的：
A）随机存储器（RAM）的意思是当程序运行时，每次具体分派给程序的内存位置是随机而不确信的。
B）一样的个人运算机在同一时刻只能存/取一个特定的内存单元。
C）运算机内存严格说来包括主存（memory）、高速缓存（cache）和寄放器（register）三个部份。
D）1MB内存一样是指1024*1024字节大小的内存。
3、关于操作系统下面说法哪些是正确的：
A.多任务操作系统专用于多核心或多个CPU架构的运算机系统的治理。
B.在操作系统的治理下，一个完整的程序在运行进程中能够被部份寄放在内存中。
C.分时系统让多个用户能够共享一台主机的运算能力，为保证每一个用户都取得及时的响应通常会采历时刻片轮转调度的策略。
D.为了方便上层应用程序的开发，操作系统都是免费开源的。
4、关于运算机网络，下面的说法哪些是正确的：
A）网络协议之因此有很多层主若是由于新技术需要兼容过去老的实现方案。
B）新一代互联网利用的IPv6标准是IPv5标准的升级与补充。
C）TCP/IP是互联网的基础协议簇，包括有TCP和IP等网络与传输层的通信协议。
D）互联网上每一台入网主机通常都需要利用一个唯一的IP地址，不然就必需注册一个固定的域名来标明其地址。
五、关于HTML下面哪些说法是正确的：
A）HTML全称超文本标记语言，实现了文本、图形、声音乃至视频信息的统一编码。
B）HTML不单包括有网页内容信息的描述，同时也包括对网页格式信息的概念。
C）网页上的超链接只能指向外部的网络资源，本网站网页间的联系通过设置标签来实现。
D）点击网页上的超链接从本质上确实是依照该链接所隐含的统一资源定位符（URL）请求网络资源或网络效劳。
六、假设3个极点的无权图G的邻接矩阵用数组存储为{{0，1，1}，{1，0，1}，{0，1，0}}，假定在具体存储中极点依次为:
v1，v2，v3。
关于该图，下面的说法哪些是正确的：
A）该图是有向图。
B）该图是强连通的。
C）该图所有顶点的入度之和减所有顶点的出度之和等于1。
D）从v1开始的深度优先遍历所通过的极点序列与广度优先的极点序列是相同的。
7、在带尾指针（链表指针clist指向尾结点）的非空循环单链表中每一个结点都以next字段的指针指向下一个节点。
假定其中已经有2个以上的结点。
下面哪些说法是正确的：
A）如果p指向一个待插入的新结点，在头部插入一个元素的语句序列为：
p->next=clist->next;clist->next=p;
B）如果p指向一个待插入的新结点，在尾部插入一个元素的语句序列为：
p->next=clist；clist->next=p;
C）在头部删除一个结点的语句序列为：
p=clist->next;clist->next=clist->next->next;deletep;
D）在尾部删除一个结点的语句序列为。
p=clist;clist=clist->next;deletep;
八、散列表的地址区间为0-10,散列函数为H（K）=Kmod11。
采纳开地址法的线性探查法处置冲突，并将关键字序列26，25，72，38，8，18，59存储到散列表中，这些元素存入散列表的顺序并非确信。
假定之前散列表为空，那么元素59寄放在散列表中的可能地址有：
A）5B）7C）9D）10
九、排序算法是稳固的意思是关键码相同的记录排序前后相对位置不发生改变，以下哪些排序算法是稳固的：
A）插入排序B）基数排序C）归并排序D）冒泡排序
10、在参加NOI系列竞赛进程中，下面哪些行为是被严格禁止的：
A）携带书写工具，腕表和不具有通信功能的电子词典进入赛场。
B）在联机测试中通过手工计算出可能的答案并在程序里直接输出答案来获取分数。
C）通过互联网搜索取得解题思路。
D）在提交的程序中启动多个进程以提高程序的执行效率。
三．问题求解（共2题，每空5分，共计10分）
1．拓扑排序是指将有向无环图G中的所有极点排成一个线性序列，使得图中任意一对极点u和v，假设∈E（G），那么u在线性序列中出此刻v之前，如此的线性序列成为拓扑序列。
如下的有向无环图，对其极点做拓扑排序，那么所有可能的拓扑序列的个数为。
2．某个国家的钱币面值有1,7,72,73共计四种，假设是要用现金付清10015元的货物，假设生意两边各类钱币的数量无穷且许诺找零，那么交易进程中至少需要流通张钱币。
四．阅读程序写结果（共4题，每题8分，共计32分）
1．
#include
usingnamespacestd;
inta,b;
intwork（inta,intb）{
if（a%b）
returnwork（b,a%b）;
returnb;
}
intmain（）{
cin>>a>>b;
cout<return0;
}
输入：
123321
输出：
_________
2．
#include
usingnamespacestd;
intmain（）
{
inta[4],b[4];
inti,j,tmp;
for（i=0;i<4;i++）
cin>>b[i];
for（i=0;i<4;i++）
{
a[i]=0;
for（j=0;j<=i;j++）
{
a[i]+=b[j];
b[a[i]%4]+=a[j];
}
}
tmp=1;
for（i=0;i<4;i++）
{
a[i]%=10;
b[i]%=10;
tmp*=a[i]+b[i];
}
cout<return0;
}
输入：
2357
输出：
_______________
3．
#include
usingnamespacestd;
constintmaxn=50;
constinty=2020;
intmain（）
{
intn,c[maxn][maxn],i,j,s=0;
cin>>n;
c[0][0]=1;
for（i=1;i<=n;i++）
{
c[i][0]=1;
for（j=1;jc[i][j]=c[i-1][j-1]+c[i-1][j];
c[i][i]=1;
}
for（i=0;i<=n;i++）
s=（s+c[n][i]）%y;
cout<return0;
}
输入：
17
输出：
4．
#include
usingnamespacestd;
intmain（）
{
intn,m,i,j,p,k;
inta[100],b[100];
cin>>n>>m;
a[0]=n;
i=0;
p=0;
k=0;
do
{
for（j=0;jif（a[i]==a[j]）
{
p=1;
k=j;
break;
}
if（p）
break;
b[i]=a[i]/m;
a[i+1]=a[i]%m*10;
i++;
}while（a[i]!
=0）;
cout<for（j=1;jcout<if（p）
cout<<"（";
for（j=k;jcout<if（p）
cout<<"）";
cout<return0;
}
输入：
513
输出：
_________
五．完善程序（前5空，每空2分，后6空，每空3分，共28分）
1．（最大持续子段和）给出一个数列（元素个数不多于100），数列元素均为负整数、正整数、0。
请找出数列中的一个持续子数列，使得那个子数列中包括的所有元素之和最大，在和最大的前提下还要求该子数列包括的元素个数最多，并输出那个最大和和该持续子数列中元素的个数。
例如数列为4，-5，3，2，4时，输出9和3；数列为123-5078时，输出16和7。
#include
usingnamespacestd;
inta[101];
intn,i,ans,len,tmp,beg,end;
intmain（）{
cin>>n;
for（i=1;i<=n;i++）
cin>>a[i];
tmp=0;
ans=0;
len=0;
beg=①;
for（i=1;i<=n;i++）{
if（tmp+a[i]>ans）{
ans=tmp+a[i];
len=i-beg;
}
elseif（②&&i-beg>len）
len=i-beg;
if（tmp+a[i]③）{
beg=④;
tmp=0;
}
else
⑤;
}
cout<return0;
}
2.（寻觅等差数列）有一些长度相等的等差数列（数列中每一个数都为0~59的整数），设长度均为L，将等差数列中的所有数打乱顺序放在一路。
此刻给你这些打乱后的数，问原先，L最大可能为多大？
先读入一个数n（1<=n<=60），再读入n个数，代表打乱后的数。
输出等差数列最大可能长度L。
#include
usingnamespacestd;
inthash[60];
intn,x,ans,maxnum;
intwork（intnow）{
intfirst,second,delta,i;
intok;
while（①&&!
hash[now]）
++now;
if（now>maxnum）
return1;
first=now;
for（second=first;second<=maxnum;second++）
if（hash[second]）{
delta=②;
if（first+delta*③>maxnum）
break;
if（delta==0）
ok=（④）;
else{
ok=1;
for（i=0;iok=⑤&&（hash[first+delta*i]）;
}
if（ok）{
for（i=0;ihash[first+delta*i]--;
if（work（first））
return1;
for（i=0;ihash[first+delta*i]++;
}
}
return0;
}
intmain（）{
inti;
memset（hash,0,sizeof（hash））;
cin>>n;
maxnum=0;
for（i=0;icin>>x;
hash[x]++;
if（x>maxnum）
maxnum=x;
}
for（ans=n;ans>=1;ans--）
if（n%ans==0&&⑥）{
cout<break;
}
return0;
}
2020第十五届全国青青年信息学奥林匹克联赛初赛试题参考答案与评分标准
一、单项选择题：
（每题分）
1.C2.A3.D4.B5.D
6.B7.B8.A9.A10.C
二、不定项选择题（共10题，每题分，共计15分。
每题正确答案的个数大于或等于1。
多项选择或少选均不得分）。
1.AB2.BD3.BC4.C5.BD
6.ABD7.AC8.ABC9.ABCD10.ACD
三、问题求解：
（共2题，每空5分，共计10分）
1．432
2．35
四、阅读程序写结果（共4题，每题8分，共计32分）
1.3
2.5850
3.487（杨辉三角）
4.0.（384615）（分数变小数）
五．完善程序（前5空，每空2分，后6空，每空3分，共28分）
（说明：
以下各程序填空可能还有一些等价的写法，各省可请本省专家审定和上机验证，没必要然上报科学委员会审查）
①0
②tmp+a[i]==ans或a[i]+tmp==ans或ans==a[i]+tmp等
③<0
④i
⑤tmp+=a[i]或tmp=tmp+a[i]
①now<=maxnum或!
（now>maxnum）
②second-first
③（ans-1）
④hash[first]>=ans或hash[second]>=ans或hash[first+delta]>=ans
⑤ok
⑥work（0）或work（0）==1或work（0）>0等
升级会员 