《NOIP2018提高组C++试题资料》由会员分享，可在线阅读，更多相关《NOIP2018提高组C++试题资料（9页珍藏版）》请在金锄头文库上搜索。
1、 CCF NOIP2018 初赛提高组 C 语言试题 第 1 页 共 9 页 第二十四届全国青少年信息学奥林匹克联赛初赛 提高组 C 语言试题 竞赛时间 2018 年 10 月 13 日 14 30 16 30 选手选手注意 注意 试题纸共有 10 页 答题纸共有 2 页 满分 100 分 请在答题纸上作答 写 在试题纸上的一律无效 不得使用任何电子设备 如计算器 手机 电子词典等 或查阅任何书籍资 料 一 单项选择题 共一 单项选择题 共 10 题 每题题 每题 2 分 共计分 共计 20 分分 每题有且仅有一个正确选项 每题有且仅有一个正确选项 1 下列四个不同进制的数中 与其它三项数值上
2、不相等的是 A 269 16 B 617 10 C 1151 8 D 1001101011 2 2 下列属于解释执行的程序设计语言是 A C B C C Pascal D Python 3 中国计算机学会于 年创办全国青少年计算机程序设计竞赛 A 1983 B 1984 C 1985 D 1986 4 设根节点深度为 0 一棵深度为 h 的满 k k 1 叉树 即除最后一层无任何 子节点外 每一层上的所有结点都有 k 个子结点的树 共有 个结点 A k h 1 1 k 1 B k h 1 C k h D k h 1 k 1 5 设某算法的时间复杂度函数的递推方程是 T n T n 1 n n
3、为正整数 及 T 0 1 则该算法的时间复杂度为 A O log n B O n log n C O n D O n2 CCF NOIP2018 初赛提高组 C 语言试题 第 2 页 共 9 页 6 表达式 a d b c 的前缀形式是 A a d b c B a d b c C a d b c D a d b c 7 在一条长度为 1 的线段上随机取两个点 则以这两个点为端点的线段的期望 长度是 A 1 2 B 1 3 C 2 3 D 3 5 8 关于 Catalan 数 Cn 2n n 1 n 下列说法中错误的是 A Cn 表示有 n 1 个结点的不同形态的二叉树的个数 B Cn 表示含
4、n 对括号的合法括号序列的个数 C Cn 表示长度为 n 的入栈序列对应的合法出栈序列个数 D Cn 表示通过连接顶点而将 n 2 边的凸多边形分成三角形的方法个数 9 假设一台抽奖机中有红 蓝两色的球 任意时刻按下抽奖按钮 都会等概率 获得红球或蓝球之一 有足够多的人每人都用这台抽奖机抽奖 假如他们的 策略均为 抽中蓝球则继续抽球 抽中红球则停止 最后每个人都把自己获 得的所有球放到一个大箱子里 最终大箱子里的红球与蓝球的比例接近于 A 1 2 B 2 1 C 1 3 D 1 1 10 为了统计一个非负整数的二进制形式中 1 的个数 代码如下 int CountBit int x int r
5、et 0 while x ret return ret 则空格内要填入的语句是 A x 1 CCF NOIP2018 初赛提高组 C 语言试题 第 3 页 共 9 页 B x scanf d int res 0 for int i 0 i x i if i i x 1 res printf d res return 0 输入 15 输出 2 include int n d 100 bool v 100 int main scanf d for int i 0 i n i scanf d d i v i false CCF NOIP2018 初赛提高组 C 语言试题 第 5 页 共 9 页 in
6、t cnt 0 for int i 0 i n i if v i for int j i v j j d j v j true cnt printf d n cnt return 0 输入 10 7 1 4 3 2 5 9 8 0 6 输出 3 include using namespace std string s long long magic int l int r long long ans 0 for int i l i s int len s length int ans 0 for int l1 0 l1 len l1 for int r1 l1 r1 len r1 bool b
7、o true for int l2 0 l2 len l2 for int r2 l2 r2 len r2 if magic l1 r1 magic l2 r2 if bo CCF NOIP2018 初赛提高组 C 语言试题 第 6 页 共 9 页 ans 1 cout ans endl return 0 输入 abacaba 输出 4 include using namespace std const int N 110 bool isUse N int n t int a N b N bool isSmall for int i 1 i n i if a i b i return a i
8、n return isSmall for int i 1 i n i if isUse i b pos i isUse i true if getPermutation pos 1 return true isUse i false return false void getNext for int i 1 i n i isUse i false getPermutation 1 for int i 1 i n i CCF NOIP2018 初赛提高组 C 语言试题 第 7 页 共 9 页 a i b i int main scanf d d for int i 1 i n i scanf d
9、 for int i 1 i t i getNext for int i 1 i n i printf d a i if i n putchar n else putchar return 0 输入 1 6 10 1 6 4 5 3 2 输出 1 3 分 输入 2 6 200 1 5 3 4 2 6 输出 2 5 分 五 完善程序五 完善程序 共共 2 题 每题题 每题 14 分分 共计共计 28 分分 1 对于一个1到 的排列 即1到 中每一个数在 中出现了恰好一次 令 为 第 个位置之后第一个比 值更大的位置 如果不存在这样的位置 则 1 举例来说 如果 5且 为1 5 4 2 3 则 为
10、2 6 6 5 6 下列程序读入了排列 使用双向链表求解了答案 试补全程序 第二空 2 分 其余 3 分 数据范围 1 105 include using namespace std const int N 100010 int n int L N R N a N int main cin n for int i 1 i x 1 for int i 1 i n i R i 2 L i i 1 for int i 1 i n i L 3 L a i R L a i R 4 for int i 1 i n i cout 5 cout endl return 0 2 一只小猪要买 N 件物品 N 不
11、超过 1000 它要买的所有物品在两家商店里都有卖 第 i 件物品在第一家商店的价格是 a i 在第二家商店的价格是 b i 两个价格都不小于 0 且不超过 10000 如 果在第一家商店买的物品的总额不少于不少于 50000 那么在第一家店买的物品都 可以打 95 折 价格变为原来的 0 95 倍 求小猪买齐所有物品所需最少的总额 输入 第一行一个数 N 接下来 N 行 每行两个数 第 i 行的两个数分别代 表 a i b i 输出 输出一行一个数 表示最少需要的总额 保留两位小数 试补全程序 第一空 2 分 其余 3 分 include include using namespace st
12、d const int Inf 1000000000 const int threshold 50000 const int maxn 1000 int n a maxn b maxn bool put a maxn int total a total b CCF NOIP2018 初赛提高组 C 语言试题 第 9 页 共 9 页 double ans int f threshold int main scanf d total a total b 0 for int i 0 i n i scanf d d a i b i if a i b i total a a i else total b
13、 b i ans total a total b total a total b 0 for int i 0 i n i if 1 put a i true total a a i else put a i false total b b i if 2 printf 2f total a 0 95 total b return 0 f 0 0 for int i 1 i threshold i f i Inf int total b prefix 0 for int i 0 i 0 j if 3 threshold f j min f j b i j a i 5 Inf printf 2f ans return 0
