不定项选择题1214

您的姓名：



1、若逻辑变量 A、C 为真，B、D 为假，以下逻辑运算表达式为真的有（）。【多选题】

((¬A∧B)∨C)∧¬B

(B∨C∨D)∨D∧A

(A∧B)∨(C∧D∨¬A)

A∧(D∨¬C)∧B

3、在 NOI 比赛中，对于程序设计题，选手提交的答案不得包含下列哪些内容（）。【多选题】

运行其他程序

改变文件系统的访问权限

打开或创建题目规定的输入/输出文件之外的其他文件

试图访问网络

读写文件系统的访问权限

4、以下哪些结构可以用来存储图（）。【多选题】

栈

二叉树

邻接表

邻接矩阵

5、下列各无符号十进制整数中，能用八位二进制表示的数有（）。【多选题】

256

199

296

133

6、下列程序中，正确计算 1，2，…，100 这 100 个自然数之和 sum(初始值为 0)的是（）。【多选题】

i=1; do { sum+=i, i++; } while (i>100);

i=1; while (i>100) sum+=i, i++;

i=1; do { sum+=i, i++; } while (i<=100);

for (i=1;i<=100;i++) sum+=i;

7、（）的平均时间复杂度为 O(n log n)，其中 n 是待排序的元素个数。【多选题】

归并排序

快速排序

冒泡排序

插入排序

8、以A0作为起点，对下面的无向图进行深度优先遍历时(遍历的顺序与顶点字母的下标无关)，最后一个遍历的顶点可能是（）。

【多选题】

9、（）属于 NP 类问题。【多选题】

存在一个 P 类问题

任何一在(输入规模的)指数时间内能够解决的问题

任何一个不属于 P 类的问题

任何一个 P 类问题

10、CCF NOIP 复赛考试结束后，因（）提出的申诉将不会被受理。【多选题】

源程序保存在指定文件夹以外的位置

输出文件的文件名错误

只提交了可执行文件，未提交源程序

源程序文件名大小写错误

11、如果对于所有规模为 n 的输入，一个算法均恰好进行（）次运算，我们可以说该算法的时间复杂度为O(2ⁿ)。【多选题】

2的 2n 次方

2的 n+1 次方

n * (2的 n 次方)

3的 n 次方

12、从顶点 A0出发，对有向图（）进行广度优先搜索(BFS)时，一种可能的遍历顺序是A0，A1，A2，A3，A4。

【多选题】

图 A

图 B

图 C

图 D

13、如果一个栈初始时为空，且当前栈中的元素从栈底到栈顶依次为 a，b，c(如下图所示)，另有元素 d 已经出栈，则可能的入栈顺序有（）。

【多选题】

b，a，c，d

a，c，b，d

a，b，c，d

d，a，b，c

14、在计算机显示器所使用的 RGB 颜色模型中，（）属于三原色之一。【多选题】

黄色

蓝色

绿色

紫色

15、一棵二叉树一共有 19 个节点，其叶子节点可能有（）。【多选题】

16、已知带权有向图 G 上的所有权值均为正整数，记顶点 u 到顶点 v 的最短路径的权值为 d(u,v)。若 v1，v2，v3，v4，v5 是图 G 上的顶点，且它们之间两两都存在路径可达，则以下说法正确的有（）。【多选题】

d(v1,v2)=d(v2,v1)

v1 到 v2 的最短路径可能包含一个环

如果 v1->v2->v3->v4->v5 是 v1 到 v5 的一条最短路径，那么 v2->v3->v4 是 v2 是 v4 的一条最短路径

d(v1,v3)<=d(v1,v2)+d(v2,v3)

17、逻辑异或(⊕)是一种二元运算，其真值表如下所示。

以下关于逻辑异或的性质，正确的有（）。【多选题】

交换律：a⊕b=b⊕a

结合律：(a⊕b)⊕c=a⊕(b⊕c)

关于逻辑或的分配律：a⊕(b∨c)=(a⊕b)∨(a⊕c)

关于逻辑与的分配律：a⊕(b∧c)=(a⊕b)∧(a⊕c)

18、十进制下的无限循环小数(不包括循环节内的数字均为 0 或均为 9 的平凡情况)，在二进制下有可能是（）。【多选题】

无限不循环小数

整数

无限循环小数(不包括循环节内的数字均为 0 或均为 9 的平凡情况)

有限小数

19、以下（）属于互联网上的 E-mail 服务协议。【多选题】

FTP

POP3

HTTP

SMTP

20、以下关于计算复杂度的说法中，正确的有（）。【多选题】

如果一个问题不存在多项式空间的算法，那它一定是 NP 类问题

如果一个问题不存在多项式空间的算法，那它一定不是 P 类问题

如果一个问题不存在多项式时间的算法，那它一定是 NP 类问题

如果一个问题不存在多项式时间的算法，那它一定不是 P 类问题