CSP-JS练习题
- 格式：docx
- 大小：17.06 KB
- 文档页数：4
CSP-J/S练习题
1. T(n)表示某个算法输入规模为 n 时的运算次数。
如果 T(1)为常数，且有递归式 T(n) = 2*T(n / 2) + 2n，那么 T(n) = （ B）。
A. Θ(n)
B. Θ(n log n)
C. Θ(n2)
D. Θ(n2 log n)
2.n 是待排序的元素个数,平均时间复杂度为 O(n log n)的为(A D)
A. 快速排序
B. 插入排序
C. 冒泡排序
D. 归并排序
AD的时间复杂度为O（nlogn）,冒泡和插入为O(n2)选择排序也是O（n2）
3.属于 NP 类问题的为(A B)
A. 存在一个 P 类问题
B. 任何一个 P 类问题
C. 任何一个不属于 P 类的问题
D. 任何一个在（输入规模的）指数时间内能够解决的问题
4.TCP协议属于哪一层协议( B).
A. 应用层
B. 传输层
C. 网络层
D. 数据链路层
TCP属于传输层协议（T->transfer）
5.下列几个32位IP地址中，书写错误的是(C ).
A. 162.105.128.27
B. 192.168.0.1
C. 256.256.129.1
D. 10.0.0.1
32位IP地址四个位置都在0~255之间
6.对长度位n的有序单链表，若检索每个元素的概率相等，则顺序检索到表中任一元素的平均检索长度为(B ).
A. n/2
B. (n+1)/2
C. (n-1)/2
D. n/4
7.若有变量 int a, float x, y, 且 a=7, x=2.5, y=4.7, 则表达式
x+a%3*(int)(x+y)%2/4的值大约是(A ).
A. 2.500000
B. 2.750000
C. 3.500000
D. 0.000000
x+a%3*(int)(x+y)%2/4=2.5+1*1/4=2.5+0=2.5
8.有以下结构体说明和变量定义，如图所示，指针p、q、r分别指向一个链表中的三个续结点。
struct node {
int data;
struct node *next;
} *p,*q,*r;
现要将q和r所指结点的先后位置交换，同时要保持链表的连续，以下程序段中错误的是(D )
A. q->next = r->next; p-> next = r; r->next = q;
B. p->next = r; q->next = r->next; r->next = q;
C. q->next = r->next; r->next = q; p->next = r;
D. r->next = q; q->next = r->next; p->next = r;
D中r的next已经更新了，下一步q的next就不能指过去了
9.同时查找2n 个数中的最大值和最小值，最少比较次数为( C).
A. 3(n-2)/2
B. 4n-2
C. 3n-2
D. 2n-2
10.下列(B C D )软件属于操作系统软件。
A. Microsoft Word
B. Windows XP
C. Android
D. Mac OS X
E. Oracle
E是数据库，Word是微软的一个办公软件
11.在数据压缩编码的应用中，哈夫曼（Huffman）算法是一种采用了（A ）思想的算法。
A. 贪心
B. 分治
C. 递推
D. 回溯
哈夫曼算法用了贪心思想
12.以下属于操作系统的有（ A B C D）。
A. Windows 10
B. UNIX
C. Linux
D. Mac OS
13.某计算机的 CPU 和内存之间的地址总线宽度是 32 位（bit），这台计算机最多可以使用（ B）的内存。
A. 2GB
B. 4GB
C. 8GB
D. 16GB
14.以下属于无线通信技术的有（A B C ）。
A. 蓝牙
B. WiFi
C. GPRS
D. 以太网
GPRS是通用分组无线服务技术
15.分辨率为 1600x900、16 位色的位图，存储图像信息所需的空间为（A ）。
A. 2812.5KB
B. 4218.75KB
C. 4320KB
D. 2880KB
16.将 7 个名额分给 4 个不同的班级，允许有的班级没有名额，有（ D）种不同的分配方案。
A. 60
B. 84
C. 96
D. 120
这种问题是7个苹果放3个盘子里问题
17.下列属于解释执行的程序设计语言是 (D)
A. C
B. C++
C. Pascal
D. Python
其他三项都是编译执行。
18.在计算机显示器所使用的 RGBRGBRGB 颜色模型中，（B D）属于三原色之一。
A. 黄色
B. 蓝色 D. 绿色
C. 紫色
19.下列关于排序说法正确的是（A B C）。
A、插入排序、冒泡排序是稳定的
B、选择排序的时间复杂度为 O(n2)
C、选择排序、希尔排序、快速排序、堆排序是不稳定的
D、希尔排序、快速排序、堆排序的时间复杂度为 O(nlogn)
19.若A=False，B=True，C=True，D=False，则下列逻辑运算真的有（D）
A. (A∧B)V(C∧D)
B. ((A∧¬B)VD)∧B
C. ((¬A→¬B)∧C)VD
D. ¬A∧(¬D→¬C)→¬B
20.在整数的补码表示法中，以下说法正确的是（A ）。
A．只有负整数的编码最高位为1
B．在编码的位数确定后，所能表示的最小整数和最大整数的绝对值相同
C．整数0有正零和负零两个编码
D．两个用补码表示的数相加时，如果在最高位产生进位，则表示运算溢出。
