第六套中小学信息学奥赛CSP-J考前冲刺题
1、IPv4中,以下P地址不合法的是
A、255.255.255.255
B、0.1.1.1
C、1.1.1.0
D、1.0.0.0
答案：B
考点分析：主要考查网络相关知识，合法的IPv4地址第一个八位二进制必须是从1开始，到255，答案B
2、已知A,B,C是3个二进制数,符号^表示逻辑与运算,符号V表示逻辑或运算
若A=1100 1101 0011
B=1100 0111 0110
C=0011 0110 1010
则表达式(AVB)^(AVC)的值为
A、1100 1110 0001
B、00110010 1111
C、110011110011
D、1100 0111 0001
答案：C
考点分析：主要考查逻辑运算，逻辑或运算是有只要有一个1结果就为1，与运算是只要有一个0结果就为0，所以计算后可知答案为C
3、Linux 下可执行文件的默认扩展名为
A、exe
B、chm
C、dll
D、都不是
答案：D
考点分析：主要考查操作系统相关知识，Linux下可执行文件的默认扩展名为没有。在Linux系统中，可执行文件的扩展名并不像Windows系统那样具有特定的规定，而是通过文件的权限属性来确定是否可以执行。在Linux系统中，可执行文件的权限属性中包含了可执行的权限，即通过设置文件的执行权限之后，可以直接通过命令来执行该文件，而不需要指定扩展名；答案D
4、八进制数 7042 转化为十六进制数是
A、3521
B、F22
C、E22
D、111000100010
答案：C
考点分析：主要考查进制转换，7042对应的二进制就是D选项，转化为十六进制，4个为一组从右边开始，得出结果为E22，答案C
5、以下排序算法中,不需要进行关键字比较操作的算法是
A、基数排序
B、冒泡排序
C、堆排序
D、直接插入排序
答案：A
考点分析：主要考查排序算法，基数排序是一种非比较排序算法，它的原理是：将待排序的数组按照个位数进行排序，然后按照十位数进行排序，再按照百位数进行排序，依次类推，直到最高位排序完成。基数排序可以使用桶排序或计数排序来进行每一位的排序。答案A
6、一个袋子中有3个蓝球,2个红球,2个黄球,则从中抽出三个球颜色各不相同的概率是多少
A、10/21
B、13/33
C、12/35
D、3/7
答案：C
考点分析：主要考查排列组合相关知识，三个球颜色各不相同，那就是每种颜色一个，取法有：C(3,1)*C(2,1)*C(2,1)=3*2*2=12，总共7个球取3个的取法有：C(7,3)=7*6*5/3/2=35，答案C
7、定义乚数：素数或者是回文数满足两者中任意一个条件的数。大于等于10并且小于等于120的“L数"共有多少个?(注:回文数指从左到右读与从右到左读是相同的,如“121'，“1331”;两个条件都成立也是L数,如“131”)
A、34
B、35
C、36
D、37
答案：B
考点分析：主要考查逻辑思维推理能力，10-120之间的素数和回文数，小朋友可以列举一下不难得出答案，这里要注意的一点就是11和101这两个数既是素数又是回文数，只统计一次即可，答案B
8、定义一颗有根树的深度:根结点的深度为0,其余结点的深度等于该结点的父亲结点的深度加1。以下数字中哪一个可以作为一颗深度为9的完全二叉树的总节点数
A、511
B、510
C、1023
D、1026
答案：C
考点分析：主要考查二叉树相关知识，根据题目根的
深度为0，根是1个节点；
深度为1，最多就有2个叶子节点和一个根节点，总共节点为3；
深度为2，最多就是4个叶子节点和3个分支节点，总共节点为7
所以可以得到深度为n的总节点个数为2^(n+1)-1个节点，将9带入得到2^(9+1)-1=1024-1=1023，答案C
9、共9个互不相同的数,它们的最大公约数是2021的一个大于1的因子(6有2、3、6这三个大于1的因子,因子可以包含自身),且这9个数的和小于等于2021,则这9个数的和是多少?
A、1849
B、1935
C、2021
D、1927
答案：B
考点分析：主要考查数学思维和逻辑推理能力，2021=43*47，所以9个数的最大公约数要么是43，要么是47，如果取43为最大公约数，对应9个互不相同的数就是43的1到9倍，求和结果为1935；如果是47，9个互不相同的数，答案不在四个选项；答案B
10、以下哪位科学家被称为“博弈论之父”,“现代计算机之父"
A、图灵
B、冯诺依曼
C、塔扬
D、比尔盖茨
答案：B
考点分析：主要考查名人名言，冯·诺依曼最著名的贡献之一是提出了现代计算机结构的基本原理，被称为“冯·诺依曼体系结构”。 冯·诺依曼还在游戏理论、量子力学、数值分析等领域做出了重要的贡献。他是一位非常全面的学者，跨越了数学、物理学、计算机科学等多个学科领域，对科学和技术的发展做出了巨大的影响。答案B
11、设栈S和队列Q初始状态为空，元素a1,a2,a3…a6依次通过栈S,一个元素出栈后就进入队列Q，若出队的顺序分别是 a2,a4,a3,a6,a5,a1，则栈S的容量至少是
A、2
B、3
C、4
D、5
答案：B
考点分析：主要考查栈和队列相关知识，栈是先进后出，队列是先进先出，
- 出队顺序为2的时候，栈里面有1和2，
- 出4的时候，栈里面有1、3和4，
- 出3的时候，栈里有1和3，
- 出6的时候，栈里有1，5和6
- 出5的时候，栈里有1和5
- 出1的时候，栈里有1，所以总共栈的容量至少要有3个，答案B
12、对有序数组{5,13,19,21,37,56,64,75,88,92,100}进行二分查找,等概率的情况下查找成功的平均查找长度(平均比较次数)是
A、35/11
B、34/11
C、3
D、32/11
答案：C
考点分析：主要考查二分查找，二分查找也叫对半查找或者折中查找，就是从序列的中间进行查找：
- 56查找1次
- 19和88查找2次
- 13、37、75和100查找3次
- 5、21、64和92查找4次
- 总共查找的次数为：1+2*2+4*3+4*4=33次，总共元素有11个，所以平均查找长度为33/11=3，答案C
13、一个n个顶点的强连通图最少有几条边
A、n
B、n+1
C、n-1
D、n*(n-1)
答案：A
考点分析：主要考查图相关知识，强连通图是指图中的任意两个顶点之间都存在一条有向路径。而最小的强连通图是一个环，每个顶点都与相邻的顶点有一条边相连。一个n个顶点的环有n条边，因此一个n个顶点的强连通图至少有n条边，答案A
14、在1和2015之间(包括1和2015 在内)不能被4、5、6三个数任意一个数整除的数有几个
A、1035
B、1105
C、1075
D、2000
答案：C
考点分析：主要考查小朋友们的逻辑思维推理能力，1到2015不能倍4、5和6三个数任意一个数整除可以表示为：
- 总的2015个数减去4的倍数个数，5的倍数个数，6的倍数个数
- 加上被重复减了的4和5的公倍数，5和6的公倍数，4和6的公倍数
- 再减去被重复加了的4、5和6的公倍数
- 2015-2015/4-2015/5-2015/6+2015/20+2015/30+2015/12-2015/60=2015-503-403-335+100+67+167-33=1075，答案C
15、关于Catalan数Cn,下列说法中错误的是
A、Cn表示有n+1个结点的不同形态的二叉树的个数
B、Cn表示含n对括号的合法括号序列的个数
C、Cn表示长度为n的人栈序列对应的合法出栈序列个数
D、Cn 表示通过连接顶点而将n+2边的凸多边形分成三角形的方法个数
答案：A
考点分析：主要考查卡塔兰数相关知识，Catalan数表示的是在给定长度的组合中，能够形成的合法括号序列的数量，Catalan数在数学和计算机科学中有着广泛的应用，包括组合计数问题、卡塔兰数的结构、图论、动态规划等领域。在程序设计中，Catalan数经常用于解决括号匹配问题和求解二叉树的问题。括号匹配问题中，Catalan数表示的是合法的括号序列的数量；二叉树问题中，Catalan数表示的是n个节点的二叉树的数量，答案A，应该是n个节点不是n+1个
