学习C++从娃娃抓起!记录下CSP-J备考学习过程中的题目,记录每一个瞬间。
附上汇总贴:历年CSP-J初赛真题解析 | 汇总_热爱编程的通信人的博客-CSDN博客
第1题
以下哪一种设备属于输出设备( )
A.扫描仪
B.键盘
C.鼠标
D.打印机
【答案】:D
【解析】
A、B、C都是输入设备
第2题
下列四个不同进制的数中,与其它三项数值上不相等的是( )
A. ( 269 ) 16 (269)_{16} (269)16
B. ( 617 ) 10 (617)_{10} (617)10
C. ( 1151 ) 8 (1151)_8 (1151)8
D. ( 1001101011 ) 2 (1001101011)_2 (1001101011)2
【答案】:D
【解析】
十六进制和八进制优先转为二进制后比较,可以发现A和C相同,与D不同,故选D
第3题
1MB等于( )
A.1000字节
B.1024字节
C.1000 X 1000字节
D.1024 X 1024字节
【答案】:D
【解析】
1 M B = 2 10 K B = 2 20 B 1MB = 2^{10}KB = 2^{20}B 1MB=210KB=220B
第4题
广域网的英文缩写是( )
A.LAN
B.WAN
C.MAN
D.LNA
【答案】:B
【解析】
WAN:Wide Area Network
LAN:Local Area Network
MAN:Metro Area Network
LNA:局部网络结构 Local Network Architecture
第5题
中国计算机学会于( )年创办全国青少年计算机程序设计竞赛。
A.1983
B.1984
C.1985
D.1986
【答案】:B
【解析】
计算机常识
第6题
如果开始时计算机处于小写输入状态,现在有一只小老鼠反复按照CapsLock、字母键A、字母键S、字母键D、字母键F的顺序循环按键, 即CapsLock、A、S、D、F、CapsLock、A、S、D、F、…,屏幕上输出的第81个字符是字母( )
A.A
B.S
C.D
D.a
【答案】:A
【解析】
之前的原题,这次多了个字符F。
ASDFasdfASDFasdf,8个一循环,81%8=1,第1个字符就是A
第7题
根节点深度为0,一棵深度为h的满k(k>1)叉树,即除最后一层无任何子节点外,每一层上的所有结点都有k个子结点的树,共有( )个结点。
A. ( k h + 1 − 1 ) / ( k − 1 ) (k^{h+1}-1)/(k-1) (kh+1−1)/(k−1)
B.
k
h
−
1
k^h-1
kh−1
C.
k
h
k^h
kh
D.
(
k
h
−
1
)
/
(
k
−
1
)
(k^{h-1})/(k-1)
(kh−1)/(k−1)
【答案】:A
【解析】
等比数列求和公式: S n = a 1 ( q n − 1 ) q − 1 S_n = \frac{a_1(q^n-1)}{q-1} Sn=q−1a1(qn−1),这里公比为k, S n = 1 ∗ ( k h + 1 − 1 ) k − 1 S_n = \frac{1*(k^{h+1}-1)}{k-1} Sn=k−11∗(kh+1−1)
第8题
以下排序算法中,不需要进行关键字比较操作的算法是( )。
A.基数排序
B.冒泡排序
C.堆排序
D.直接插入排序
【答案】:A
【解析】
B、C、D一定需要进行比较的。基数排序是桶排序,直接放到下标中,自动做了比较。
第9题
给定一个含N个不相同数字的数组,在最坏情况下,找出其中最大或最小的数,至少需要N-1次比较操作。则最坏情况下,在该数组中同时找最大与最小的数至少需要( )次比较操作。( ⌈ ⌉ \lceil \rceil ⌈⌉表示向上取整, ⌊ ⌋ \lfloor \rfloor ⌊⌋表示向下取整)
A. ⌈ 3 N / 2 ⌉ − 2 \lceil 3N/2\rceil-2 ⌈3N/2⌉−2
B. ⌊ 3 N / 2 ⌋ − 2 \lfloor 3N/2 \rfloor-2 ⌊3N/2⌋−2
C.2N-2
D.2N-4
【答案】:A
【解析】
n为奇数时, a 1 , a 2 , … , a n − 1 , a n a_1,a_2,\dots,a_{n-1},a_n a1,a2,…,an−1,an。
第1步:使MAX初值为 a 1 a_1 a1
第2步:每一组组内比较,求出较大者(比较(n-1)/2次)
第3步:将每一组的较大者与MAX比较,求出最大值(比较(n-1)/2次)
同理求最小值,得到组内较大值和较小值可以只要(n-1)/2次,后面求最大值和最小值分别需要(n-1)/2次,所以共需3*(n-1)/2, 即3n/2-3/2= 3 n + 1 2 − 2 \frac{3n+1}{2}-2 23n+1−2
n为偶数时, a 1 , a 2 , … , a n − 1 , a n a_1,a_2,\dots,a_{n-1},a_n a1,a2,…,an−1,an。
第1步:使MAX初始为 a 1 a_1 a1和 a 2 a_2 a2的较大值,MIN则是较小值(需1次比较)
第2步:每一组组内比较,同时求出较大者和较小者(比较(n-2)/2次)
第3步:将每一组的较大者与MAX、MIN比较,求出最大值(比较2*(n-2)/2次)
共需3*(n-2)/2+1=3n/2-2= 3 n 2 − 2 \frac{3n}{2}-2 23n−2
综上,结果为 ⌈ 3 n 2 ⌉ − 2 \lceil \frac{3n}{2}\rceil-2 ⌈23n⌉−2
第10题
下面的故事与( )算法有着异曲同工之妙。
从前有座山,山里有座庙,庙里有个老和尚在给小和尚讲故事:“从前有座山,山里有座庙,庙里有个老和尚在给小和尚讲故事:‘从前有座山,山里有座庙,庙里有个老和尚给小和尚讲故事…’“
A.枚举
B.递归
C.贪心
D.分治
【答案】:B
【解析】
2013年原题,递归
第11题
由四个没有区别的点构成的简单无向连通图的个数是( )。
A.6
B.7
C.8
D.9
【答案】:A
【解析】
4个无区别的点,所以某个图的各个顶点的度数相同,则为同一个图形,如2332和2323。
6条边1种:3333
5条边1种:2332
4条边2种:2222、2231
3跳变2种:1221、1311
第12题
设含有10个元素的集合的全部子集数为S,其中由7个元素组成的子集数为T,则T/S的值为( )。
A.5 / 32
B.15 / 128
C.1 / 8
D.21 / 128
【答案】:B
【解析】
T = 10个中挑7个的组成数 = C 10 3 C_{10}^{3} C103=120
S = 2 10 2^{10} 210
T/S = 15/128
第13题
10000以内,与10000互质的正整数有( )个。
A.2000
B.4000
C.6000
D.8000
【答案】:B
【解析】
10000以内因数含2的数有5000个,因数含5的数有2000个,因数含10的数有1000个
10000-5000-2000+1000=4000
第14题
为了统计一个非负整数的二进制形式中1的个数,代码如下:
int CountBit(int x)
{
int ret = 0;
while (x)
{
ret++;
____;
}
return ret;
}
则空格内要填入的语句是( )。
A.x>>=1
B.x&=x-1
C.x|=x>>1
D.x<<=1
【答案】:B
【解析】
假设x为5,A选项结果为3,B选项结果为2,C选项死循环,D选项结果为3
第15题
下图中所使用的数据结构是( )。
A.哈希表
B.栈
C.队列
D.二叉树
【答案】:栈
【解析】
2013年原题
标签:10,真题,初赛,比较,3n,答案,解析,CSP,有座 From: https://blog.csdn.net/guolianggsta/article/details/140090923