样稿--第二十六届全国青少年信息学奥林匹克联赛初赛模拟试题
第二十六届全国青少年信息学奥林匹克联赛初赛模拟试题
提高组C++语言试题
竞赛时间：2020 年
选手注意：
● 试卷与答卷均在网页上，请做好后在网页内提交。
● 不得使用任何电子设备（如计算器、手机、电子词典等）或查阅任何书籍资料。
一、单项选择题（共15题，每题2分，共计30分；每题有且仅有一个正确选项）
1.若有定义：int a=5；float x=3.6,y=4.5；则表达式(x/2)+((a%3)*((int)(x+y)%2))的值是（ ）。
1.800000
3.600000
4.500000
2.700000
2.下列属于视频文件格式的有（ ）。
jpg
cpp
mp4
gif
3.世界上第一台电脑是由（ ）制造的。
Αριστοτλη,Aristotélēs
Karl Alexander Müller，Johannes Georg Bednorz
JohnW.Mauchly，J.PresperEckert
Albert Einstein
4.16进制数0x1F与10进制数12进行与运算的结果为（ ）。
12
14
8
9
5.如果不在快速排序中引入随机化，有可能导致的后果是（ ）。
数组访问越界
陷入死循环
排序结果错误
排序时间退化为平方级
6.ASCII 码的含义是（ ）。
二—十进制转换码
美国信息交换标准代码
数字的二进制编码
计算机可处理字符的唯一编码
7.地面上有标号为A、B、C 的3 根细柱，在A 柱上放有10 个直径相同中间有孔的圆盘，从上到下依次编号为1，2，3，……，将A 柱上的部分盘子经过B 柱移入C 柱，也可以在B 柱上暂存。如果B 柱 上的操作记录为：“进，进，出，进，进，出，出，进，进，出，进，出，出”。那么，在C 柱上，从下 到上的盘子的编号为（ ）。
2 4 3 6 5 7
2 4 1 2 5 7
2 4 3 1 7 6
2 4 3 6 7 5
8.设A=B=true，C=D=false，以下逻辑运算表达式值为假的是（ ）。
(¬ A∧B)∨(C∧D∨A)
¬ (((A∧B)∨C)∧D)
A∧(B∨C∨D)∨D
(A∧(D∨C)) ∧B
9.在一个4*3的网格中随机放三颗棋子（不重叠），要求每行每列最多仅有一颗棋子，放置符合题意的概率为（ ）。
6/55
7/110
1/10
4/27
10.对有序数组{5, 13, 19, 21, 37, 56, 64, 75, 88, 92, 100}进行二分查找，等概率的情况下查找成功的平均查找长度（平均比较次数）是（ ）。
35/11
34/11
33/11
34/10
11.将6个球放入3个不同的盒子里，允许有的盒子空着不放，则有（ ）种放法。
62
56
50
78
12.一棵二叉树一共有 19 个节点，其叶子节点不可能有（ ）个。
1
9
10
11
13.快速排序平均情况和最坏情况下的算法时间复杂度分别为（ ）。
平均情况 O(n)， 最坏情况O(n^2)
平均情况 O(n)， 最坏情况O(n log(2)(n))
平均情况 O(n log(2)(n))，最坏情况O(n^2)
平均情况 O(log(2)(n))， 最坏情况O(n^2)
14.双向链表中有两个指针域llink和rlink，分别指向该结点的前驱及后继。设p指向链表中的一个结点，他的左右结点均为非空。现要求删除结点p，则下列语句序列中错误的是（ ）。
p->llink->rlink=p->rlink;p->rlink->llink = p->llink; delete p;
p->rlink->llink=p->rlink;p->llink->rlink=p->llink; delete p;
p->rlink->llink = p->llink;p->rlink->llink ->rlink = p->rlink; delete p;
p->llink->rlink = p->rlink;p->llink->rlink->llink = p->llink; delete p;
15.一个算法的流程可以用以下递推式来表示
则此算法在数据较小的情况下能优化到的最低时间复杂度为（ ）。
O(n^2)
O(log(2)(n))
O(n)
O(1)
二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填√，错误填×；除特殊说明外，判断题1.5分，选择题4分，共计40分）
1.
●判断题
1）该程序使用了优先队列。（ ）
选项1
选项2
2）若n=10000，该程序无法在1s内给出结果。（ ）
对
错
3）若没有第18，19，20行的初始化，该程序不能正常运行。（ ）
对
错
4）该程序内变量可能最大值为2^32-1。（ ）
对
错
●选择题
5）该程序的代码是（ ）的原理。
莫比乌斯反演
halfman编码
差分约束
树链剖分
6）该程序的时间复杂度为（ ）。
O(n^2)
O(log(2)(n))
O(n log(2)(n))
O(n)
2.
●判断题
1）该程序是解决最短路问题的一种方法。（ ）
对
错
2）该程序使用了多余的头文件。（ ）
对
错
3）若在主程序中不将a数组初始化，程序仍会正常运行。（ ）
对
错
4）该题采用了深搜剪枝的思想方法。（ ）
对
错
●选择题
5）该算法的一般复杂度为（ ）。
O(log(2)(n))
O(n)
O(n^2)
(n log(2)(n))
6）该算法的最坏复杂度为（ ）。
O(n^2)
O(n log(2)(n))
O(n+m)
O(mn)
3.
●判断题
1）本程序使用了快速排序。（ ）
对
错
2）本程序使用了n叉树（n>2）。（ ）
对
错
3）该程序运用了近似Treap树的思想。（ ）
对
错
4）该程序的时间复杂度为O(n
2
)。（ ）
对
错
●选择题
5）若n=5，且∀a[i].s=1，则ans最大为（ ）。
10
11
12
13
6）若n=5，且，则ans最大为（ ）。
10
12
14
16
三、完善程序（单选题，每小题3分，共计30分）
1.(逆序对)当i>j,a[i]<a[j]时，我们称（a[i],a[j]）为逆序对。给出一个数组a，输出其中的逆序对个数ans。
本题使用归并排序求逆序对。
1）①处应填（ ）。
A. a[i]<a[j]
B. a[i]>a[j]
C. a[i]=a[j]
D. a[i]!=a[j]
2）②处应填（ ）。
A. ans+=y2-j;
B. ans+=y2-y1+j;
C. ans+=y2-j+1;
D. ans+=j;
3）③处应填（ ）。
A. a[x1-1+k]=c[k];
B. a[x1+k]=c[k];
C. a[x1+1+k]=c[k];
D. a[y1-1+k]=c[k];
4）④处应填（ ）。
A. (x+y)/3;
B. x+y-1;
C. x+1;
D. (x+y)/2;
5）⑤处应填（ ）。
A. f(1,n);
B. f(2,n);
C. f(1,n-1);
D. /(不填)
2.（区间问题）已知一个数列，你需要进行下面两种操作：
将某区间每一个数加上 k 。
求出某区间每一个数的和。
输入格式
第一行包含两个整数 n ，m ，分别表示该数列数字的个数和操作的总个数。
第二行包含 n 个用空格分隔的整数，其中第 i 个数字表示数列第 i 项的初始值。
接下来 m 行每行包含 3 或 4 个整数，表示一个操作，具体如下：
1 x y k ：将区间 [x,y] 内每个数加上 k 。
2 x y ：输出区间 [x,y] 内每个数的和。
本程序用了线段树的方法来实现这一过程。
1）①处应填（ ）。
l==r
l>r
l<r
l<r-1
2）②处应填（ ）。
tag[p]--;
tag[p]=0;
a[p]+=tag[p];
a[p]=0;
3）③处应填（ ）。
k*(r-l+1)
k*(r-l)
k*(r-l-1)
k*(r)
4）④处应填（ ）。
push_up(p);
tag[p]+=k;
ans[p]+=k;
push_down(p,l,r);
5）⑤处应填（ ）。
memset(ans,0,sizeof ans);
build(1,n,1);
build(1,1,n);
memset(tag,0,sizeof tag);
关闭
更多问卷
复制此问卷