NOIP2021提高组C++试题.docx

《NOIP2021提高组C++试题.docx》由会员分享，可在线阅读，更多相关《NOIP2021提高组C++试题.docx（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、NOIP2021提高组C+试题第二十一届全国青少年信息学奥林匹克联赛初赛提高组C+语言试题竞赛时间：2021年10月11日14:3016:30选手注意：试题纸共有9页，答题纸共有2页，满分100分。请在答题纸上作答，写在试题纸上的一律无效。不得使用任何电子设备如计算器、手机、电子词典等或查阅任何书籍资料。一、单项选择题共15题，每题1.5分，共计22.5分；每题有且仅有一个正确选项1.在计算机内部用来传送、存贮、加工处理的数据或指令都是以形式进行的。A.二进制码B.八进制码C.十进制码D.智能拼音码2.下列讲法正确的是。A.CPU的主要任务是执行数据运算和程序控制B.存储器具有记忆能力，其中信

2、息任何时候都不会丢失C.两个显示器屏幕尺寸一样，则它们的分辨率必定一样D.个人用户只能使用Wifi的方式连接到Internet3.与二进制小数0.1相等的十六进制数是。A.0.8B.0.4C.0.2D.0.14.下面有四个数据组，每个组各有三个数据，其中第一个数据为八进制数，第二个数据为十进制数，第三个数据为十六进制数。这四个数据组中三个数据一样的是。A.1208250B.14410068C.300200C8D.176210103F25.线性表若采用链表存储构造，要求内存中可用存储单元地址。A.必须连续B.部分地址必须连续C.一定不连续D.连续不连续均可6.今有一空栈S，对下列待进栈的数据元素

3、序列a,b,c,d,e,f依次进行进栈，进栈，出栈，进栈，进栈，出栈的操作，则此操作完成后，栈S的栈顶元素为。A.fB.cC.aD.b7.前序遍历序列与后序遍历序列一样的二叉树为。A.非叶子结点只要左子树的二叉树B.只要根结点的二叉树C.根结点无右子树的二叉树D.非叶子结点只要右子树的二叉树8.假如根的高度为1，具有61个结点的完全二叉树的高度为。A.5B.6C.7D.89.6个顶点的连通图的最小生成树，其边数为。A.6B.5C.7D.410.设某算法的计算时间表示为递推关系式T(n)=T(n-1)+nn为正整数及T(0)=1，则该算法的时间复杂度为。A.O(logn)B.O(nlogn)C.

4、O(n)D.O(n2)11.具有n个顶点，e条边的图采用邻接表存储构造，进行深度优先遍历和广度优先遍历运算的时间复杂度均为。A.(n2)B.(e2)C.(ne)D.(n+e)12.在数据压缩编码的应用中，哈夫曼Huffman算法是一种采用了思想的算法。A.贪心B.分治C.递推D.回溯13.双向链表中有两个指针域，llink和rlink，分别指回前驱及后继，设p指向链表中的一个结点，q指向一待插入结点，现要求在p前插入q，则正确的插入为。A.p-llink=q;q-rlink=p;p-llink-rlink=q;q-llink=p-llink;B.q-llink=p-llink;p-llink-

5、rlink=q;q-rlink=p;p-llink=q-rlink;C.q-rlink=p;p-rlink=q;p-llink-rlink=q;q-rlink=p;D.p-llink-rlink=q;q-rlink=p;q-llink=p-llink;p-llink=q;14.对图G中各个结点分别指定一种颜色，使相邻结点颜色不同，则称为图G的一个正常着色。正常着色图G所必需的最少颜色数，称为G的色数。那么下列图的色数是。A.3B.4C.5D.615.在NOI系列赛事中参赛选手必须使用由承办单位统一提供的设备。下列物品中不允许选手自带的是。A.鼠标B.笔C.身份证D.准考证二、不定项选择题共5题

6、，每题1.5分，共计7.5分；每题有一个或多个正确选项，多项选择或少选均不得分1.下面属于操作系统的有。A.WindowsXPB.UNIXC.LinuxD.MacOS2.下列属于视频文件格式的有。A.AVIB.MPEGC.WMVD.JPEG3.下列选项不是正确的IP地址的有。A.202.300.12.4B.192.168.0.3C.100:128:35:91D.111-103-35-214.下列有关树的叙述中，叙述正确的有。A.在含有n个结点的树中，边数只能是(n-1)条B.在哈夫曼树中，叶结点的个数比非叶结点个数多1C.完全二叉树一定是满二叉树D.在二叉树的前序序列中，若结点u在结点v之前，

7、则u一定是v的祖先5.下面图中一定能够进行黑白染色的有。黑白染色：为各个结点分别指定黑白两种颜色之一，使相邻结点颜色不同。A.二分图B.完全图C.树D.连通图三、问题求解共2题，每题5分，共计10分；每题全部答对得5分，没有部分分1.在1和2021之间包括1和2021在内不能被4、5、6三个数任意一个数整除的数有个。2.结点数为5的不同形态的二叉树一共有种。结点数为2的二叉树一共有2种：一种是根结点和左儿子，另一种是根结点和右儿子。四、浏览程序写结果共4题，每题8分，共计32分1.#includeusingnamespacestd;structpointintx;inty;intmain()s

8、tructEXinta;intb;pointc;e;e.a=1;e.b=2;e.c.x=e.a+e.b;e.c.y=e.a*e.b;coutusingnamespacestd;voidfun(char*a,char*b)a=b;(*a)+;intmain()charc1,c2,*p1,*p2;c1=A;c2=a;p1=&c1;p2=&c2;fun(p1,p2);cout#includeusingnamespacestd;intmain()intlen,maxlen;strings,ss;maxlen=0;docinss;len=ss.length();if(ss0=#)break;if(len

9、maxlen)s=ss;maxlen=len;while(true);coutusingnamespacestd;intfun(intn,intfromPos,inttoPos)intt,tot;if(n=0)return0;for(t=1;tn;coutusingnamespacestd;constintMAXN=1000;intn,i,ans,sum;intxMAXN;intlmaxMAXN;/lmaxi为仅含xi及xi左侧整数的连续子序列的序列和中，最大的序列和intrmaxMAXN;/rmaxi为仅含xi及xi右侧整数的连续子序列的序列和中，最大的序列和intmain()cinn;fo

10、r(i=0;ixi;lmax0=x0;for(i=1;ifor(i=n-2;i=0;i-)if(rmaxi+1elsefor(i=n-2;i=0;i-)if(rmaxians=x0+x2;for(i=1;iif(sumans)ans=sum;coutusingnamespacestd;constintMAXV=100;intn,i,j,v;intwMAXVMAXV;/邻接矩阵，记录边长/其中wij为连接结点i和结点j的无向边长度，若无边则为-1intdistMAXV;intusedMAXV;/记录结点能否已扩展0：未扩展；1：已扩展intmain()cinn;for(i=0;iwij;dist0=0;for(i=1;iif(usedi!=1&disti!=-1&(v=-1if(v=-1)break;for(i=0;idisti=distv+wvi;for(i=0;in;i+)coutdistiendl;return0;