1. 目前计算机芯片（集成电路）制造的主要原料是（ ），它是一种可以在沙子中提炼出的物质。{{ select(1) }}

• 硅
• 铜
• 锗
• 铝

2. （ ）是主要用于显示网页服务器或者文件系统的 HTML 文件内容，并让用户与这些文件交互的一种软件。{{ select(2) }}

• 资源管理器
• 浏览器
• 电子邮件
• 编译器

3. 目前个人电脑的（ ）市场占有率最靠前的厂商包括 Intel、AMD 等公司。{{ select(3) }}

• 显示器
• CPU
• 内存
• 鼠标

4. 无论是 TCP/IP 模型还是 OSI 模型，都可以视为网络的分层模型，每个网络协议都会被归入某一层中。如果用现实生活中的例子来比喻这些“层”，以下最恰当的是（ ）。{{ select(4) }}

• 中国公司的经理与老挝缅甸公司的经理交互商业文件
• 军队发布命令
• 国际会议中，每个人都与他国地位对等的人直接进行会谈
• 体育比赛中，每一级比赛的优胜者晋级上一级比赛

5. 如果不在快速排序中引入随机化，有可能导致的后果是（ ）。{{ select(5) }}

• 数组访问越界
• 陷入死循环
• 排序结果错误
• 排序时间退化为平方级

6. 1946 年诞生于美国宾夕法尼亚大学的 ENIAC 属于（）计算机。{{ select(6) }}

• 电子管
• 晶体管
• 集成电路
• 超大规模集成电路

7. 在程序运行过程中，如果递归调用的层数过多，会因为（ ）引发错误。{{ select(7) }}

• 系统分配的栈空间溢出
• 系统分配的堆空间溢出
• 系统分配的队列空间溢出
• 系统分配的链表空间溢出

8. 地址总线的位数决定了 CPU 可直接寻址的内存空间大小，例如地址总线为 $16$ 位，其最大的可寻址空间为 $64\text{KB}$。如果地址总线是 $32$ 位，则理论上最大可寻址的内存空间为（ ）。{{ select(8) }}

• $128\text{KB}$
• $1\text{MB}$
• $1\text{GB}$
• $4\text{GB}$

9. 以下不属于目前 3G（第三代移动通信技术）标准的是（）。{{ select(9) }}

• GSM
• TD-SCDMA
• CDMA2000
• WCDMA

10. 仿生学的问世开辟了独特的科学技术发展道路。人们研究生物体的结构、功能和工作原理，并将这些原理移植于新兴的工程技术之中。以下关于仿生学的叙述，错误的是（ ）。{{ select(10) }}

• 由研究蝙蝠，发明雷达
• 由研究蜘蛛网，发明因特网
• 由研究海豚，发明声纳
• 由研究电鱼，发明伏特电池

11. 如果对于所有规模为 $n$ 的输入，一个算法均恰好进行（ ）次运算，我们可以说该算法的时间复杂度为 $\Theta(2^n)$。{{ multiselect(11) }}

• $\Theta(2^{n+1})$
• $\Theta(3^n)$
• $\Theta(n\times2^n)$
• $\Theta(2^{2n})$

12. 从顶点 $A_0$ 出发，对有向图（ ）进行广度优先搜索（BFS）时，一种可能的遍历顺序是 $A_0\to A_1\to A_2\to A_3 \to A_4$。{{ multiselect(12) }}

• 
• 
• 
• 

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

{{ multiselect(13) }}

• $a,b,c,d$
• $b,a,c,d$
• $a,c,b,d$
• $d,a,b,c$

14. 在计算机显示器所使用的 RGB 颜色模型中，（ ）属于三原色之一。{{ multiselect(14) }}

• 黄色
• 蓝色
• 紫色
• 绿色

15. 一棵二叉树一共有 $19$ 个节点，其叶子节点可能有（ ）个。{{ multiselect(15) }}

• $1$
• $9$
• $10$
• $11$

16. 已知带权有向图 $G$ 上的所有权值均为正整数，记顶点 $u$ 到顶点 $v$ 的最短路径的权值为 $d(u,v)$。若 $v_1,v_2,v_3,v_4,v_5$ 是图 $G$ 上的顶点，且它们之间两两都存在路径可达，则以下说法正确的有（ ）。{{ multiselect(16) }}

• $v_1$ 到 $v_2$ 的最短路径可能包含一个环
• $d(v_1,v_2)=d(v_2,v_1)$
• $d(v_1,v_3)\le d(v_1,v_2)+d(v_2,v_3)$
• 如果 $v_1→v_2→v_3→v_4→v_5$ 是 $v_1$ 到 $v_5$ 的一条最短路径，那么 $v2→v3→v4$ 是 $v_2$ 到 $v_4$ 的一条最短路径

17. 逻辑异或（$\oplus$）是一种二元运算，其真值表如下所示。

$a$	$b$	$a \oplus b$
$\text{false}$	$\text{false}$
	$\text{true}$	$\text{true}$
$\text{true}$	$\text{false}$
	$\text{true}$	$\text{false}$

以下关于逻辑异或的性质，正确的有（ ）。{{ multiselect(17) }}

• 交换律：$a \oplus b=b \oplus a$
• 结合律：$(a\oplus b)⊕c=a⊕(b⊕c)$
• 关于逻辑与的分配律：$a⊕(b∧c)=(a⊕b)∧(a⊕c)$
• 关于逻辑或的分配律：$a⊕(b∨c)=(a⊕b)∨(a⊕c)$

18. 十进制下的无限循环小数（不包括循环节内的数字均为 $0$ 或均为 $9$ 的平凡情况），在二进制下有可能是（ ）。{{ multiselect(18) }}

• 无限循环小数（不包括循环节内的数字均为 $0$ 或均为 $1$ 的平凡情况）
• 无限不循环小数
• 有限小数
• 整数

19. 以下（ ）属于互联网上的 E-mail 服务协议。{{ multiselect(19) }}

• HTTP
• FTP
• POP3
• SMTP

20. 以下关于计算复杂度的说法中，正确的有（ ）。{{ multiselect(20) }}

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

21. 本题中，我们约定布尔表达式只能包含 $p,q,r$ 三个布尔变量，以及“与”（$∧$）、“或”（$∨$）、“非”（$¬$）三种布尔运算。如果无论 $p,q,r$ 如何取值，两个布尔表达式的值总是相同，则称它们等价。例如，$(p∧q)∨r$ 和 $p∨(q∨r)$ 等价，$p∨¬p$ 和 $q∨¬q$ 也等价；而 $p∨q$ 和 $p∧q$ 不等价。那么，两两不等价的布尔表达式最多有 {{ input(21) }} 个。
22. 对于一棵二叉树，独立集是指两两互不相邻的节点构成的集合。例如，图 1 有 $5$ 个不同的独立集（$1$ 个双点集合、$3$ 个单点集合、$1$ 个空集），图 2 有 $14$ 个不同的独立集。那么，图 3 有 {{ input(22) }} 个不同的独立集。

23. 读程序写结果

#include <iostream>
using namespace std;
int n, i, temp, sum, a[100];
int main() {
    cin >> n;
    for (i = 1; i <= n; i++)
        cin >> a[i];
    for (i = 1; i <= n - 1; i++)
        if (a[i] > a[i + 1]) {
            temp = a[i];
            a[i] = a[i + 1];
            a[i + 1] = temp;
        }
    for (i = n; i >= 2; i--)
        if (a[i] < a[i - 1]) {
            temp = a[i];
            a[i] = a[i - 1];
            a[i - 1] = temp;
        }
    sum = 0;
    for (i = 2; i <= n - 1; i++)
        sum +  = a[i];
    cout << sum / (n - 2) << endl;
    return 0;
}

输入：

8
40 70 50 70 20 40 10 30

输出： {{ input(23) }}

24. 读程序写结果

#include <iostream>
using namespace std;
int n, i, ans;
int gcd(int a, int b)
{
    if (a % b == 0) return b;
    else
        return gcd(b, a%b);
}
int main()
{
    cin>>n;
    ans = 0;
    for (i = 1; i <= n; i++)
        if (gcd(n,i) == i)
            ans++;
    cout<<ans<<endl;
}

输入：120

输出：{{ input(24) }}

25. 读程序写结果

#include <iostream>
using namespace std;
const int SIZE = 20;
int data[SIZE];
int n, i, h, ans;
void merge()
{
    data[h-1] = data[h-1] + data[h];
    h--;
    ans++;
}
int main()
{
    cin>>n;
    h = 1;
    data[h] = 1;
    ans = 0;
    for (i = 2; i <= n; i++)
    {
        h++;
        data[h] = 1;
        while (h > 1 && data[h] == data[h-1])
            merge();
    }
    cout<<ans<<endl;
}

输入：8

输出：{{ input(25) }}

输入：2012

输出：{{ input(26) }}

26. 读程序写结果

#include <iostream>
#include <string>
using namespace std;
int lefts[20], rights[20], father[20];
string s1, s2, s3;
int n, ans;
void calc(int x, int dep)
{
    ans = ans + dep*(s1[x] - 'A' + 1);
    if (lefts[x] >= 0) calc(lefts[x], dep+1);
    if (rights[x] >= 0) calc(rights[x], dep+1);
}
void check(int x)
{
    if (lefts[x] >= 0) check(lefts[x]);
    s3 = s3 + s1[x];
    if (rights[x] >= 0) check(rights[x]);
}
void dfs(int x, int th)
{
    if (th == n)
    {
        s3 = "";
        check(0);
        if (s3 == s2)
        {
            ans = 0;
            calc(0, 1);
            cout<<ans<<endl;
        }
        return;
    }
    if (lefts[x] == -1 && rights[x] == -1)
    {
        lefts[x] = th;
        father[th] = x;
        dfs(th, th+1);
        father[th] = -1;
        lefts[x] = -1;
    }
    if (rights[x] == -1)
    {
        rights[x] = th;
        father[th] = x;
        dfs(th, th+1);
        father[th] = -1;
        rights[x] = -1;
    }
    if (father[x] >= 0)
        dfs(father[x], th);
}
int main()
{
    cin>>s1;
    cin>>s2;
    n = s1.size();
    memset(lefts, -1, sizeof(lefts));
    memset(rights, -1, sizeof(rights));
    memset(father, -1, sizeof(father));
    dfs(0, 1);
}

输入：

ABCDEF
BCAEDF

输出：{{ input(27) }}

27. 完善程序

排列数：输入两个正整数 $n,m\ (1≤n≤20,1≤m≤n)$，在 $1\sim n$ 中任取 $m$ 个数，按字典序从小到大输出所有这样的排列。

#include <iostream>
#include <cstring>
using namespace std;
const int SIZE = 25;
bool used[SIZE];
int data[SIZE];
int n, m, i, j, k;
bool flag;
int main()
{
	cin >> n >> m;
	memset( used, false, sizeof(used) );
	for ( i = 1; i <= m; i++ )
	{
		data[i] = i;
		used[i] = true;
	}
	flag = true;
	while ( flag )
	{
		for ( i = 1; i <= m - 1; i++ )
			cout << data[i] << " ";
		cout << data[m] << endl;
		flag = ①;
		for ( i = m; i >= 1; i-- )
		{
			②;
			for ( j = data[i] + 1; j <= n; j++ )
				if ( !used[j] )
				{
					used[j] = true;
					data[i] = ③;
					flag	= true;
					break;
				}
			if ( flag )
			{
				for ( k = i + 1; k <= m; k++ )
					for ( j = 1; j <= ④; j++ )
						if ( !used[j] )
						{
							data[k] = j;
							used[j] = true;
							break;
						}
				⑤;
			}
		}
	}
}

①填：{{ input(28) }}

②填：{{ input(29) }}

③填：{{ input(30) }}

④填：{{ input(31) }}

⑤填：{{ input(32) }}

28. 完善程序

新壳栈：小 Z 设计了一种新的数据结构“新壳栈”。首先，它和传统的栈一样支持压入、弹出操作。此外，其栈顶的前 $c$ 个元素是它的壳，支持翻转操作。其中，$c>2$ 是一个固定的正整数，表示壳的厚度。小 Z 还希望，每次操作，无论是压入、弹出还是翻转，都仅用与 $c$ 无关的常数时间完成。聪明的你能帮助它编程实现“新壳栈”吗？

程序期望的实现效果如以下两表所示。其中，输入的第一行是正整数 $c$，之后每行输入都是一条指令。另外，如遇弹出操作时栈为空，或翻转操作时栈中元素不足 $c$ 个，应当输出相应的错误信息。

指令	含义
0	退出
1 e	在栈顶压入元素 $e$
2	弹出并输出栈顶元素
3	翻转栈顶的 $c$ 个元素

输入	输出	栈内元素	说明
3		$\{\}$	输入正整数 $c$
1 1		$\{1\}$	压入元素$1$
1 2		$\{1,2\}$	压入元素$2$
1 3		$\{1,2,3\}$	压入元素$3$
1 4		$\{1,2,3,4\}$	压入元素$4$
3		$\{1,4,3,2\}$	翻转栈顶的 $c$ 个元素
1 5		$\{1,4,3,2,5\}$	压入元素$5$
3		$\{1,4,5,2,3\}$	翻转栈顶的 $c$ 个元素
2	3	$\{1,4,5,2\}$	弹出栈顶元素$3$
	2	$\{1,4,5\}$	弹出栈顶元素$2$
	5	$\{1,4\}$	弹出栈顶元素$5$
3	错误信息		由于栈中元素不足 $c$ 无法翻转，故操作失败，输出错误信息
2	4	$\{1\}$	弹出栈顶元素$4$
	1	$\{\}$	弹出栈顶元素$1$
	错误信息		由于栈为空，无法弹出栈顶元素，故操作失败，输出错误信息
0			退出

#include < iostream > 
using namespace std; 
const int NSIZE = 100000,CSIZE = 1000;
int n, c, r, tail, head, s[NSIZE], q[CSIZE]; 
//数组 s 模拟一个栈，n 为栈的元素个数
//数组 q 模拟一个循环队列，tail 为队尾的下标，head 为队头的下标 
bool direction, empty; 
int previous(int k) {
	if (direction)
		return ((k + c - 2) % c) + 1; 
	else
		return (k % c) + 1; 
}
int next(int k) {
	if (direction)
		①; 
	else
		return ((k + c - 2) % c) + 1; 
}
void push() {
	int element; 
	cin >> element; 
	if (next(head) == tail) {
		n++; 
		②; 
		tail = next(tail); 
	}
	if (empty)
		empty = false; 
	else
		head = next(head); 
	③ = element; 
}
void pop() {
	if (empty) {
		cout << "Error: the stack is empty!" << endl; return; 
	}
	cout << 	④ << endl; 
	if (tail == head)
		empty = true; 
	else {
		head = previous(head); 
	if (n > 0) {
		tail = previous(tail); 
		⑤ = s[n]; 
		n--; 
	}
}
}
void reverse() {
	int temp; 
	if (	⑥ == tail) {
		direction =  ! direction; 
		temp = head; 
		head = tail; 
		tail = temp; 
	}
	else
		cout << "Error: less than " << c << " elements in the stack!" << endl; 
}
int main() {
	cin >> c; 
	n = 0; 
	tail = 1; 
	head = 1; 
	empty = true; 
	direction = true; 
	do {
		cin >> r; 
		switch (r) {
			case 1:push(); break; 
			case 2:pop(); break; 
			case 3:reverse(); break; 
		}
	}while (r != 0); 
	return 0; 
}

①填：{{ input(33) }}

②填：{{ input(34) }}

③填：{{ input(35) }}

④填：{{ input(36) }}

⑤填：{{ input(37) }}

⑥填：{{ input(38) }}