一、单选题
1、目前计算机芯片（集成电路）制造的主要原料是（ ），它是一种可以在沙子中提炼出的物质。（2012年提高组初赛）
A 硅
B 铜
C 锗
D 铝
2、（ ）是主要用于显示网页服务器或者文件系统的 HTML 文件内容，并让用户与这些文件交互的一种软件。
A 资源管理器
B 浏览器
C 电子邮件
D 编译器
3、目前个人电脑的（ ）市场占有率最靠前的厂商包括Intel、AMD等公司。
A、
显示器
B、 CPU
C、
内存
D、
鼠标
4、无论是TCP/IP模型还是OSI模型，都可以视为网络的分层模型，每个网络协议都会被归入某一层中。如果用现实生活中的例子来比喻这些“层”，以下最恰当的是（ ）。
A 中国公司的经理与伊拉克公司的经理交互商业文件
B 军队发布命令
C 国际会议中，每个人都与他国地位对等的人直接进行会谈
D 体育比赛中，每一级比赛的优胜者晋级上一级比赛
5、如果不在快速排序中引入随机化，有可能导致的后果是（ ）。
A 数组访问越界
B 陷入死循环
C 排序结果错误
D 排序时间退化为平方级
6、1946年诞生于美国宾夕法尼亚大学的ENIAC属于（ ）计算机。
A、 电子管
B、
晶体管
C、
集成电路
D、
超大规模集成电路
7、在程序运行过程中，如果递归调用的层数过多，会因为（ ）引发错误。
A 系统分配的栈空间溢出
B 系统分配的堆空间溢出
C 系统分配的队列空间溢出
D 系统分配的链表空间溢出
8、地址总线的位数决定了 CPU 可直接寻址的内存空间大小，例如地址总线为 16 位，其最大的可寻址空间为 64KB。如果地址总线是 32 位，则理论上最大可寻址的内存空间为（ ）。
A 128KB
B 1MB
C 1GB
D 4GB
9、以下不属于目前 3G（第三代移动通信技术）标准的是（ ）。
A GSM
B TD-SCDMA
C CDMA2000
D WCDMA
10、仿生学的问世开辟了独特的科学技术发展道路。人们研究生物体的结构、功能和工作原理，并将这些原理移植于新兴的工程技术之中。以下关于仿生学的叙述，错误的是（ ）。（2012年提高组初赛）
A 由研究蝙蝠，发明雷达
B 由研究蜘蛛网，发明因特网
C 由研究海豚，发明声纳
D 由研究电鱼，发明伏特电池
二、多选题
11、如果对于所有规模为 n 的输入，一个算法均恰好进行（ ）次运算，我们可以说该算法的时间复杂度为 O(2n)。
A 2n+1
B 3n
C n*2n
D 22n
12、从顶点 A0出发，对有向图（ ）进行广度优先搜索（BFS）时，一种可能的遍历顺序是 A0, A1, A2, A3, A4。
A 
B 
C 
D 
13、如果一个栈初始时为空，且当前栈中的元素从栈底到栈顶依次为a, b, c（如右图所示），另有元素 d 已经出栈，则可能的入栈顺序有（ ）。
A a, b, c, d
B、 b, a, c, d
C、
a, c, b, d
D、
d, a, b, c
14、在计算机显示器所使用的 RGB 颜色模型中，（ ）属于三原色之一。
A 黄色
B 蓝色
C 紫色
D 绿色
15、一棵二叉树一共有 19 个节点，其叶子节点可能有（ ）个。
A 1
B 9
C 10
D 11
16、已知带权有向图 G 上的所有权值均为正整数，记顶点 u 到顶点 v 的最短路径的权值为d(u, v)。若 v1, v2, v3, v4, v5是图 G 上的顶点，且它们之间两两都存在路径可达，则以下说法正确的有（ ）。
A v1 到 v2的最短路径可能包含一个环
B d(v1, v2) = d(v2, v1)
C d(v1, v3) ≤ d(v1, v2) + d(v2, v3)
D 如果 v1→v2→v3→v4→v5是 v1 到 v5的一条最短路径，那么 v2→v3→v4是 v2 到 v4的一条最短路径
17、逻辑异或（⊕）是一种二元运算，其真值表如下所示。
以下关于逻辑异或的性质，正确的有（ ）。
A 交换律：a ⊕ b = b ⊕ a
B 结合律：(a ⊕ b) ⊕ c = a ⊕ (b ⊕ c)
C 关于逻辑与的分配律：a ⊕ (b ∧ c) = (a ⊕ b) ∧ (a ⊕ c)
D 关于逻辑或的分配律：a ⊕ (b ∨ c) = (a ⊕ b) ∨ (a ⊕ c)
18、十进制下的无限循环小数（不包括循环节内的数字均为 0 或均为 9 的平凡情况），在二进制下有可能是（ ）。
A 无限循环小数（不包括循环节内的数字均为 0 或均为 1 的平凡情况）
B 无限不循环小数
C 有限小数
D 整数
19、以下（ ）属于互联网上的 E-mail 服务协议。
A HTTP
B FTP
C POP3
D SMTP
20、以下关于计算复杂度的说法中，正确的有（ ）。
A 如果一个问题不存在多项式时间的算法，那它一定是 NP 类问题
B 如果一个问题不存在多项式时间的算法，那它一定不是 P 类问题
C 如果一个问题不存在多项式空间的算法，那它一定是 NP 类问题
D 如果一个问题不存在多项式空间的算法，那它一定不是 P 类问题
三、简答题
21、本题中，我们约定布尔表达式只能包含 p, q, r 三个布尔变量，以及“与”（∧）、“或”（∨）、“非”（¬）三种布尔运算。如果无论 p, q, r 如何取值，两个布尔表达式的值总是相同，则称它们等价。例如，(p∨q)∨r 和 p∨(q∨r)等价，p∨¬p 和 q∨¬q 也等价；而 p∨q 和 p∧q 不等价。那么，两两不等价的布尔表达式最多有 个。
参考答案：两两不等价的布尔表达式最多有8个。
22、对于一棵二叉树，独立集是指两两互不相邻的节点构成的集合。例如，图1有5个不同的独立集（1个双点集合、3个单点集合、1个空集），图2有14个不同的独立集。那么，图3有 个不同的独立集。
参考答案：对于图3，独立集的个数无法直接通过观察得出，需要通过具体的计算或者编程实现。
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
输出：
参考答案：输入为8，数组元素为40 70 50 70 20 40 10 30。输出为270。
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
输出：
参考答案：输入120时，输出为4。
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;
}
（1） 输入：8
输出： （4 分）
（2） 输入：2012
输出： （4 分
参考答案：对于输入8，输出应为2；对于输入2012，输出应为1。
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
输出：
参考答案：输出为2。
四、实操题
27、（排列数）输入两个正整数 n, m (1 ≤ n ≤ 20, 1 ≤ m ≤ n)，在 1~n 中任取 m 个数，按字典序从小到大输出所有这样的排列。例如
输入：3 2
输出：
1 2
1 3
2 1
2 3
3 1
3 2
#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;
}
⑤ ;
}
}
}
}
参考答案：① false② if (!used[data[i]-1])③ j④ m⑤ used[data[i]-1] = false
28、（新壳栈）小 Z 设计了一种新的数据结构“新壳栈”。首先，它和传统的栈一样支持压入、弹出操作。此外，其栈顶的前 c 个元素是它的壳，支持翻转操作。其中，c > 2 是一个固定的正整数，表示壳的厚度。小 Z 还希望，每次操作，无论是压入、弹出还是翻转，都仅用与 c 无关的常数时间完成。聪明的你能帮助她编程实现“新壳栈”吗？
程序期望的实现效果如以下两表所示。其中，输入的第一行是正整数 c，之后每行输入都是一条指令。另外，如遇弹出操作时栈为空，或翻转操作时栈中元素不足 c 个，应当输出相应的错误信息。
#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;
}
参考答案：```cpp#include
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
