1. 某个车站呈狭长形，宽度只能容下一台车，并且只有一个出入口。已知某时刻该车站状态为空，从这一时刻开始的出入记录为：“进，出，进，进，进，出，出，进，进，进，出,出”。假设车辆入站的顺序为 1，2，3，……，则车辆出站的顺序为（ ）。

{{ select(1) }}

• 1, 2, 3, 4, 5
• 1, 2, 4, 5, 7
• 1, 4, 3, 7, 6
• 1, 4, 3, 7, 2

2. 高度为 n 的均衡的二叉树是指：如果去掉叶结点及相应的树枝，它应该是高度为 n-1的满二叉树。在这里，树高等于叶结点的最大深度，根结点的深度为 0，如果某个均衡的二 叉树共有 2381 个结点，则该树的树高为（ ）。

{{ select(2) }}

• 10
• 11
• 12
• 13

3. 设栈 S 的初始状态为空，元素 a, b, c, d, e 依次入栈，以下出栈序列不可能出现的有( ）。

{{ select(3) }}

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

4. 已知 6 个结点的二叉树的先根遍历是 1 2 3 4 5 6（数字为结点的编号，以下同），后根遍历是 3 2 5 6 4 1，则该二叉树的可能的中根遍历是（ ）

{{ select(4) }}

• 3 2 1 4 6 5
• 3 2 1 5 4 6
• 2 1 3 5 4 6
• 2 3 1 4 6 5

5．地面上有标号为 A、B、C 的 3 根细柱，在 A 柱上放有 10 个直径相同中间有孔的圆盘，从上到下依次编号为 1，2，3，……，将 A 柱上的部分盘子经过 B 柱移入 C 柱，也可以在 B 柱上暂存。如果 B柱上的操作记录为：“进，进，出，进，进，出，出，进，进，出，进，出，出”。那么，在 C 柱上，从下到上的盘子的编号为（ ）。 {{ select(5) }}

• 2 4 3 6 5 7
• 2 4 1 2 5 7
• 2 4 3 1 7 6
• 2 4 3 6 7 5

6. 已知 7 个结点的二叉树的先根遍历是 1 2 4 5 6 3 7（数字为结点的编号，以下同），中根遍历是 4 2 6 5 1 7 3，则该二叉树的后根遍历是（ ） {{ select(6) }}

• 4 6 5 2 7 3 1
• 4 6 5 2 1 3 7
• 4 2 3 1 5 4 7
• 4 6 5 3 1 7 2

7．完全二叉树共有 2*N-1 个结点，则它的叶节点数是（ ）。 {{ select(7) }}

• N-1
• N
• 2*N
• 2N-1

8．设栈 S 的初始状态为空，元素 a，b，c，d，e，f 依次入栈 S，出栈的序列为 b，d，f，e，c，a，则栈 S 的容量至少应该是（ ）。 {{ select(8) }}

• 6
• 5
• 4
• 3

9． 递归过程或函数调用时，处理参数和返回地址，通常使用一种称为（ ）的数据结构。 {{ select(9) }}

• 队列
• 多维数组
• 线性表
• 栈

10. 二叉树 T，已知其先根遍历是 1 2 4 3 5 7 6（数字为结点的编号，以下同），中根遍历是 2 4 1 5 7 3 6，则该二叉树的后根遍历是（ ）。 {{ select(10) }}

• 4 2 5 7 6 3 1
• 4 2 7 5 6 3 1
• 7 4 2 5 6 3 1
• 4 2 7 6 5 3 1

11. 设 T 是一棵有 n 个顶点的树，下列说法不正确的是（

）。 {{ select(11) }}

• T 有 n 条边
• T 是连通的
• T 是无环的
• T 有 n-1 条边

12、有六个元素 FEDCBA 从左至右依次顺序进栈，在进栈过程中会有元素被弹出栈。问下列哪一个不可能是合法的出栈序列？

{{ select(12) }}

• EDCFAB
• DECABF
• CDFEBA
• BCDAEF

13、 表达式 a*(b+c)-d 的后缀表达式是： {{ select(13) }}

• abcd*+-
• abc+*d-
• abc*+d-
• -+*abcd

14、一个包含 n 个分支结点（非叶结点）的非空二叉树，它的叶结点数目最多为： {{ select(14) }}

• 2n + 1
• 2n-1
• n-1
• n+1

15、已知 n 个顶点的有向图，若该图是强连通的（从所有顶点都存在路径到达其他顶点），则该图中最少有多少条有向边？ {{ select(15) }}

• n
• n+1
• n-1
• n*(n-1)

16. 根节点深度为0，一棵深度为h 的满k（k>1）叉树，即除最后一层无任何子节点外，每一层上的所有结点都有k 个子结点的树，共有（ ）个结点。 {{ select(16) }}

• (k^(h+1) - 1) / (k - 1)
• k^h-1
• k^h
• (k^h-1) / (k - 1)

17. 由四个没有区别的点构成的简单无向连通图的个数是（ ）。 {{ select(17) }}

• 6
• 7
• 8
• 9

18.设G是有n个结点、m条边(n ≤m)的连通图，必须删去G的( )条边，才能使得G变成一棵树。

{{ select(18) }}

• m–n+1
• m-n
• m+n+1
• n–m+1

19.表达式a * (b + c) * d的后缀形式是()。

{{ select(19) }}

• abcd*+*
• abc+*d*
• a*bc+*d
• b+c*a*d

20.向一个栈顶指针为hs的链式栈中插入一个指针s指向的结点时，应执行( )。

{{ select(20) }}

• hs->next=s;
• s->next=hs;hs=s;
• s->next=hs->next;hs->next=s;
• s->next=hs;hs=hs->next;

21. 对于入栈顺序为a, b, c, d, e, f, g的序列，下列()不可能是合法的出栈序列。

{{ select(21) }}

• a,b,c,d,e,f,g
• a,d,c,b,e,g,f
• a,d,b,c,g,f,e
• g,f,e,d,c,b,a

22. 设简单无向图 G 有 16 条边且每个顶点的度数都是 2，则图 G 有（ ）个顶点。

{{ select(22) }}

• 10
• 12
• 8
• 16

23 6 个顶点的连通图的最小生成树，其边数为( )。 {{ select(23) }}

• 6
• 5
• 7
• 4

24 链表不具备的特点是( )。 {{ select(24) }}

• 可随机访问任何一个元素
• 插入、删除操作不需要移动元素
• 无需事先估计存储空间大小
• 所需存储空间与存储元素个数成正比

25线性表若采用链表存储结构，要求内存中可用存储单元地址( )。 {{ select(25) }}

• 必须连续
• 部分地址必须连续
• 一定不连续
• 连续不连续均可