第 1 题
目前计算机芯片（集成电路）制造的主要原料是（ ），它是一种可以在沙子中提炼出的物质。
A.硅
B.铜
C.锗
D.铝
正确答案： A
本题共 1.5 分
第 2 题
（ ）是主要用于显示网页服务器或者文件系统的 HTML 文件内容，并让用户与这些文件交互的一种软件。
A.资源管理器
B.浏览器
C.电子邮件
D.编译器
正确答案： B
本题共 1.5 分
第 3 题
目前个人电脑的( )市场占有率最靠前的厂商包括 Intel、AMD 等公司。
A.显示器
B.CPU
C.内存
D.鼠标
正确答案： B
本题共 1.5 分
第 4 题
无论是 TCP/IP 模型还是 OSI 模型，都可以视为网络的分层模型，每个网络协议都会被归入某一层中。如果用现实生活中的例子来比喻这些“层”，以下最恰当的是（ ）。
A.中国公司的经理与缅甸公司的经理交互商业文件
B.军队发布命令
C.国际会议中，每个人都与他国地位对等的人直接进行会谈
D.体育比赛中，每一级比赛的优胜者晋级上一级比赛
正确答案： A
本题共 1.5 分
第 5 题
如果不在快速排序中引入随机化，有可能导致的后果是（ ）。
A.数组访问越界
B.陷入死循环
C.排序结果错误
D.排序时间退化为平方级
正确答案： D
本题共 1.5 分
第 6 题
1946 年诞生于美国宾夕法尼亚大学的 ENIAC 属于（）计算机。
A.电子管
B.晶体管
C.集成电路
D.超大规模集成电路
正确答案： A
本题共 1.5 分
第 7 题
在程序运行过程中，如果递归调用的层数过多，会因为（ ）引发错误。
A.系统分配的栈空间溢出
B.系统分配的堆空间溢出
C.系统分配的队列空间溢出
D.系统分配的链表空间溢出
正确答案： A
本题共 1.5 分
第 8 题
8.地址总线的位数决定了 CPU 可直接寻址的内存空间大小，例如地址总线为 16 位，其最大的可寻址空间为 64KB。如果地址总线是 32 位，则理论上最大可寻址的内存空间为（ ）。
A.128KB
B.1MB
C.1GB
D.4GB
正确答案： D
本题共 1.5 分
第 9 题
以下不属于目前 3G（第三代移动通信技术）标准的是（）。
A.GSM
B.TD-SCDMA
C.CDMA2000
D.WCDMA
正确答案： A
本题共 1.5 分
第 10 题
10.仿生学的问世开辟了独特的科学技术发展道路。人们研究生物体的结构、功能和工作原理，并将这些原理移植于新兴的工程技术之中。以下关于仿生学的叙述，错误的是（ )。
A.由研究蝙蝠，发明雷达
B.由研究蜘蛛网，发明因特网
C.由研究海豚，发明声纳
D.由研究电鱼，发明伏特电池
正确答案： B
本题共 1.5 分
第 11 题
如果对于所有规模为n的输入，一个算法均恰好进行（ ）次运算，我们可以说该算法的时间复杂度为O(2^n)。
A.2^(n+1)
B.3^n
C.n*2^n
D.2^(2n)
正确答案： A
本题共 1.5 分
第 12 题
从顶点 A0 出发，对有向图（ ）进行广度优先搜索（BFS）时，一种可能的遍历顺序是A_0,A_1,A_2,A_3,A_4A0?,A1?,A2?,A3?,A4?。
正确答案： AD
本题共 1.5 分
第 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
正确答案： AD
本题共 1.5 分
第 14 题
在计算机显示器所使用的 RGB 颜色模型中，（）属于三原色之一。
A.黄色
B.蓝色
C.紫色
D.绿色
正确答案： BD
本题共 1.5 分
第 15 题
一棵二叉树一共有 19 个节点，其叶子节点可能有（ ）个。
A.1
B.9
C.10
D.11
正确答案： ABC
本题共 1.5 分
第 16 题
6.已知带权有向图 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的一条最短路径
正确答案： CD
本题共 1.5 分
第 17 题
7.逻辑异或（⊕）是一种二元运算，其真值表如下所示。
以下关于逻辑异或的性质，正确的有（ ）。
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)
正确答案： AB
本题共 1.5 分
第 18 题
8.十进制下的无限循环小数（不包括循环节内的数字均为 0 或均为 9 的平凡情况），在二进制下有可能是（ ）。
A.无限循环小数（不包括循环节内的数字均为 0 或均为 1 的平凡情况）
B.无限不循环小数
C.有限小数
D.整数
正确答案： A
本题共 1.5 分
第 19 题
以下（ ）属于互联网上的 E-mail 服务协议。
A.HTTP
B.FTP
C.POP3
D.SMTP
正确答案： CD
本题共 1.5 分
第 20 题
以下关于计算复杂度的说法中，正确的有（ ）。
A.如果一个问题不存在多项式时间的算法，那它一定是 NP 类问题
B.如果一个问题不存在多项式时间的算法，那它一定不是 P 类问题
C.如果一个问题不存在多项式空间的算法，那它一定是 NP 类问题
D.如果一个问题不存在多项式空间的算法，那它一定不是 P 类问题
正确答案： BD
本题共 1.5 分
第 21 题
1.本题中，我们约定布尔表达式只能包含 p, q, r 三个布尔变量，以及“与”（∧）、“或”（∨）、“非”（?）三种布尔运算。如果无论 p, q, r 如何取值，两个布尔表达式的值总是相同，则称它们等价。例如，(p∨q)∨r 和 p∨(q∨r)等价，p∨?p 和 q∨?q 也等价；而 p∨q 和 p∧q 不等价。那么，两两不等价的布尔表达式最多有_________个。
正确答案： 256
本题共 5 分
第 22 题
2.对于一棵二叉树，独立集是指两两互不相邻的节点构成的集合。例如，图 1 有 5 个不同的独立集（1 个双点集合、3 个单点集合、1 个空集），图 2 有 14 个不同的独立集。那么，图 3 有_________个不同的独立集。
正确答案： 5536
本题共 5 分
第 23 题
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
#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
输出：_______
正确答案： 41
本题共 8 分
第 24 题
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
#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
输出：________
正确答案： 16
本题共 8 分
第 25 题
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
#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
输出：_________
（2）
输入：2012
输出：_________ #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.正确答案： 7
2.正确答案： 2004
本题共 8 分
第 26 题
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
#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
输出：__________
正确答案： 55
本题共 8 分
第 27 题
1.（排列数）输入两个正整数 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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
#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; } ⑤; } } } } |
1.正确答案： false
2.正确答案： used[data[i]]=false
3.正确答案： j
4.正确答案： n
5.正确答案： break
本题共 15 分
第 28 题
2.（新壳栈）小 Z 设计了一种新的数据结构“新壳栈”。首先，它和传统的栈一样支持压入、弹出操作。此外，其栈顶的前 c 个元素是它的壳，支持翻转操作。其中，c > 2 是一个固定的正整数，表示壳的厚度。小 Z 还希望，每次操作，无论是压入、弹出还是翻转，都仅用与 c 无关的常数时间完成。聪明的你能帮助她编程实现“新壳栈”吗？
程序期望的实现效果如以下两表所示。其中，输入的第一行是正整数 c，之后每行输入都是一条指令。另外，如遇弹出操作时栈为空，或翻转操作时栈中元素不足 c 个，应当输出相应的错误信息。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 |
#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; } |
1.正确答案： return(k%c)+1
2.正确答案： s[n]=q[tail]
3.正确答案： q[head]
4.正确答案： q[head]
5.正确答案： q[tail]
6.正确答案： next(head)
本题共 12 分