NOIP2018提高组C试题.pdf

《NOIP2018提高组C试题.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第二十四届全国青少年信息学奥林匹克联赛初赛提高组C++语言试题竞赛时间：2018年10月13日14:30~16:30选手注意：试题纸共有10页，答题纸共有2页，满分100分。请在答题纸上作答，写在试题纸上的一律无效。不得使用任何电子设备（如计算器、手机、电子词典等）或查阅任何书籍资料。一、单项选择题（共10题，每题2分，共计20分；每题有且仅有一个正确选项）1.下列四个不同进制的数中，与其它三项数值上不相等的是（）。A.(269)16B.(617)10C.(1151)8D.(1001101011)22.下列属于解释执行的程序设计语言是（）。A.

2、CB.C++C.PascalD.Python3.中国计算机学会于（）年创办全国青少年计算机程序设计竞赛。A.1983B.1984C.1985D.19864.设根节点深度为0，一棵深度为h的满k（k>1）叉树，即除最后一层无任何子节点外，每一层上的所有结点都有k个子结点的树，共有（）个结点。A.(kh+1-1)/(k-1)B.kh-1C.khD.(kh-1)/(k-1)5.设某算法的时间复杂度函数的递推方程是T(n)=T(n-1)+n（n为正整数）及T(0)=1，则该算法的时间复杂度为（）。A.O(logn)B.O(nlogn)C.O(n)D.O(n

3、2)CCFNOIP2018初赛提高组C++语言试题第1页，共9页6.表达式a*d-b*c的前缀形式是（）。A.ad*bc*-B.-*ad*bcC.a*d-b*cD.-**adbc7.在一条长度为1的线段上随机取两个点，则以这两个点为端点的线段的期望长度是（）。A.1/2B.1/3C.2/3D.3/58.关于Catalan数Cn=(2n)!/(n+1)!/n！，下列说法中错误的是（）。A.Cn表示有n+1个结点的不同形态的二叉树的个数。B.Cn表示含n对括号的合法括号序列的个数。C.Cn表示长度为n的入栈序列对应的合法出栈序列个数。D.Cn表示通过连

4、接顶点而将n+2边的凸多边形分成三角形的方法个数。9.假设一台抽奖机中有红、蓝两色的球，任意时刻按下抽奖按钮，都会等概率获得红球或蓝球之一。有足够多的人每人都用这台抽奖机抽奖，假如他们的策略均为：抽中蓝球则继续抽球，抽中红球则停止。最后每个人都把自己获得的所有球放到一个大箱子里，最终大箱子里的红球与蓝球的比例接近于（）。A.1:2B.2:1C.1:3D.1:110.为了统计一个非负整数的二进制形式中1的个数，代码如下：intCountBit(intx){intret=0;while(x){ret++;________;}returnret;}则空格

5、内要填入的语句是（）。A.x>>=1CCFNOIP2018初赛提高组C++语言试题第2页，共9页B.x&=x-1C.x

6、=x>>1D.x<<=1二、不定项选择题（共5题，每题2分，共计10分；每题有一个或多个正确选项，多选或少选均不得分）1.NOIP初赛中，选手可以带入考场的有（）。A.笔B.橡皮C.手机（关机）D.草稿纸2.2-3树是一种特殊的树，它满足两个条件：（1）每个内部结点有两个或三个子结点；（2）所有的叶结点到根的路径长度相同。如果一棵2-3树有10个叶结点，那么它可能有（）个非叶结点。A.5B.6C.7D.83.下列关于最短路算法的说

7、法正确的有（）。A.当图中不存在负权回路但是存在负权边时，Dijkstra算法不一定能求出源点到所有点的最短路。B.当图中不存在负权边时，调用多次Dijkstra算法能求出每对顶点间最短路径。C.图中存在负权回路时，调用一次Dijkstra算法也一定能求出源点到所有点的最短路。D.当图中不存在负权边时，调用一次Dijkstra算法不能用于每对顶点间最短路计算。4.下列说法中，是树的性质的有（）。A.无环B.任意两个结点之间有且只有一条简单路径C.有且只有一个简单环D.边的数目恰是顶点数目减15.下列关于图灵奖的说法中，正确的有（）。A.图灵奖是由电

8、气和电子工程师协会（IEEE）设立的。B.目前获得该奖项的华人学者只有姚期智教授一人。C.其名称取自计算机科学的先驱、英国科学家艾伦·麦席森·图灵。CCFNOIP2018初赛提高组C++语言试题第3页，共9页D.它是计算机界最负盛名、最崇高的一个奖项，有“计算机界的诺贝尔奖”之称。三、问题求解（共2题，每题5分，共计10分）1.甲乙丙丁四人在考虑周末要不要外出郊游。已知①如果周末下雨，并且乙不去，则甲一定不去；②如果乙去，则丁一定去；③如果丙去，则丁一定不去；④如果丁不去，而且甲不去，则丙一定不去。如果周末丙去了，则甲________（去了/没去）

9、(1分)，乙________（去了/没去）(1分)，丁________（去了/没去）(1分)，周末________（下雨/