首页 > 其他分享 >历年CSP-J初赛真题解析 | 2018年CSP-J初赛选择题(1-15)

历年CSP-J初赛真题解析 | 2018年CSP-J初赛选择题(1-15)

时间:2024-07-04 10:27:49浏览次数:25  
标签:10 真题 初赛 比较 3n 答案 解析 CSP 有座

学习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

相关文章