1. 今有一空栈 S，对下列待进栈的数据元素序列 a，b，c，d，e，f 依次进行进栈，进栈，出栈，进栈，进栈，出栈的操作，则此操作完成后，栈 S 的栈顶元素为（ ）。 {{ select(1) }}

• f
• c
• a
• b

2. 前序遍历序列与中序遍历序列相同的二叉树为( )。 {{ select(2) }}

• 根结点无左子树
• 根结点无右子树
• 只有根结点的二叉树或非叶子结点只有左子树的二叉树
• 只有根结点的二叉树或非叶子结点只有右子树的二叉树

3. 如果根的高度为 1,具有 61 个结点的完全二叉树的高度为( )。 {{ select(3) }}

• 5
• 6
• 7
• 8

4．如果树根算第 1 层，那么一棵 n 层的二叉树最多有（ ）个结点。 {{ select(4) }}

• $2^n-1$
• $2^n$
• $2^n+1$
• $2^{n+1}$

5．前缀表达式“+3*2+5 12”的值是（ )。 {{ select(5) }}

• 23
• 25
• 37
• 65

6．元素 R1、R2、R3、R4、R5 入栈的顺序为 R1、R2、R3、R4、R5。如果第一个出栈的是 R3，那么第五个出栈的不可能是（ ）。 {{ select(6) }}

• R1
• R2
• R4
• R5

7．双向链表中有两个指针域 llink 和 rlink，分别指向该结点的前驱和后继。设 P 指向链表中的一个结点，它的左右结点均非空。现要求删除结点 P，则下面语句序列中错误的是（ ）。 {{ select(7) }}

• P->rlink->llink = p->rlink; P->llink->rlink = p->llink; dispose(p)
• P->llink->rlink = p->rlink; P->rlink->llink = p->llink; dispose(p)
• P->rlink->llink = p->llink; P->rlink->llink->rlink= p->rlink; dispose(p)
• P->llink->rlink = p->rlink; P->llink->rlink->llink = p->llink; dispose(p)

8．一棵二叉树的前序遍历序列是 ABCDEFG，后序遍历序列是 CBFEGDA，则根结点的左子树的结点个数可能是（ ）。 {{ select(8) }}

• 2
• 3
• 4
• 5

9．关于拓扑排序，下面说法正确的是（ ）。 {{ select(9) }}

• 所有连通的有向图都可以实现拓扑排序
• 对同一个图而言，拓扑排序的结果是唯一的
• 拓扑排序中入度为 0 的结点总会排在入度大于 0 的结点前面
• 拓扑排序结果序列中的第一个结点一定是入度为 0 的点

10．完全二叉树的顺序存储方案，是指将完全二叉树的结点从上至下、从左至右依次存放到一个顺序结构的数组中。假定根结点存放在数组的 1 号位置，则第 K 号结点的父结点如果存在的话，应当存放在数组的（ ）号位置。 {{ select(10) }}

• 2k
• 2k+1
• k/2 下取整
• (k+1）/2 下取整

11．无向完全图是图中每对顶点之间都恰好有一条边的简单图。已知无向完全图 G 有 7 个顶点，则它共有（ ）条边。 {{ select(11) }}

• 7
• 21
• 42
• 49

12．如果根结点的深度记为 1，则一棵恰有 2011 个叶结点的二叉树的深度最少是（ ）。 {{ select(12) }}

• 10
• 11
• 12
• 13

13．对一个有向图而言，如果每个节点都存在到达其他任何节点的路径，那么就称它是强连通的。例如，下图就是一个强连通图。事实上，在删掉边（ ）后，它依然是强连通的。 {{ select(13) }}

• a
• b
• c
• d

14．（ ）是一种先进先出的线性表。 {{ select(14) }}

• 栈
• 队列
• 哈希表（散列表）
• 二叉树

15．如果一棵二叉树的中序遍历是 BAC，那么它的先序遍历不可能是（ ）。 {{ select(15) }}

• ABC
• CBA
• ACB
• BAC

16． 如果一个栈初始时为空，且当前栈中的元素从栈底到栈顶依次为 a，b，c，另有元素 d 已经出栈，则可能的入栈顺序是（ ）。 {{ select(16) }}

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

17. 链表不具有的特点是( )。 {{ select(17) }}

• 不必事先估计存储空间
• 可随机访问任一元素
• 插入删除不需要移动元素
• 所需空间与线性表长度成正比

18. 要求以下程序的功能是计算：s=1+1/2+1/3+...+1/10。

#include <iostream>

using namespace std;

int main(){

int n;

float s;

s = 1.0;

for(n = 10; n > 1; n--)

s = s + 1 / n;

cout << s << endl;

return 0;

}

程序运行后输出结果错误，导致错误结果的程序行是( )。 {{ select(18) }}

• s = 1.0;
• for(n = 10; n > 1; n--)
• s = s + 1 / n;
• cout << s << endl;

19. 设变量 x 为 float 型且已赋值，则以下语句中能将 x 中的数值保留到小数点后两位，并将第三位四舍五入的是( )。 {{ select(19) }}

• x = (x * 100) + 0.5 / 100.0;
• x = (x * 100 + 0.5) / 100.0;
• x = (int)(x * 100 + 0.5)/100.0;
• x = (x / 100 + 0.5) * 100.0;

20. 有以下程序

#include <iostream>

using namespace std;

int main(){

int s, a, n;

s = 0;

a = 1;

cin >> n;

do{

s += 1;

a -= 2;

}while(a != n);

cout << s << endl;

return 0;

}

若要使程序的输出值为 2，则应该从键盘给 n 输入的值是( )。 {{ select(20) }}

• -1
• -3
• -5
• 0

21. 一棵具有 5 层的满二叉树中结点数为( )。 {{ select(21) }}

• 31
• 32
• 33
• 16

22. 有向图中每个顶点的度等于该顶点的( )。 {{ select(22) }}

• 入度
• 出度
• 入度和出度之和
• 入度和出度之差

23. 已知一棵二叉树有 10 个节点，则其中至多有（ ）个节点有 2 个子节点。 {{ select(23) }}

• 4
• 5
• 6
• 7

24. 在一个无向图中，如果任意两点之间都存在路径相连，则称其为连通图。下图是一个有4 个顶点、6 条边的连通图。若要使它不再是连通图，至少要删去其中的（ ）条边。 {{ select(24) }}

• 1
• 2
• 3
• 4

25. 二叉树的（ ）第一个访问的节点是根节点。 {{ select(25) }}

• 先序遍历
• 中序遍历
• 后序遍历
• 以上都是

26. 以 A0作为起点，对下面的无向图进行深度优先遍历时，遍历顺序不可能是（ ）。 {{ select(26) }}

• A0, A1, A2, A3
• A0, A1, A3, A2
• A0, A2, A1, A3
• A0, A3, A1, A2