算法与数据结构（二）

答题说明

以下共有16道单选题，请输入题号，并输出对应答案。

输入格式

一个整数，表示题目题号。

输出格式

对应输入题号的答案。

样例代码

请将16道题的答案按顺序填入s数组后提交至OJ。

#include <cstdio>
#include <cstring>

char S[15][10]={
	"AAAAA", 	// 第1~5题
	"AAAAA", 	// 第6~10题
	"AAAAA",	// 第11~15题
	"A"	// 第16题
};

int main(){
	int	a;
	scanf("%d",	&a);
	int i = a%5 == 0 ? a/5-1 : a/5;
	int j = a%5	 == 0 ? 4 : a%5-1;
	printf("%c", S[i][j]);
	return 0;
}

题目

1.（2007）第 2 题

在关系数据库中，存放在数据库中的数据的逻辑结构以（ ）为主。

A. 二叉树

B. 多叉树

C. 哈希表

D. 二维表

2.（2007）第 20 题

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

A. 4 6 5 2 7 3 1

B. 4 6 5 2 1 3 7

C. 4 2 3 1 5 4 7

D. 4 6 5 3 1 7 2

3.（2008）第 5 题

完全二叉树共有$2*N-1$个结点，则它的叶节点数是（ ）。

A. $N-1$

B. $N$

C. $2^N$

D. $2^N -1$

4.（2008）第 13 题

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

A. 4 2 5 7 6 3 1

B. 4 2 7 5 6 3 1

C. 7 4 2 5 6 3 1

D. 4 2 7 6 5 3 1

5.（2008）第 18 题

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

A. T有n条边

B. T是连通的

C. T是无环的

D. T有n-1条边

6.（2009）第 13 题

表达式a*(b+c)-d的后缀表达式是：

A. abcd*+-

B. abc+*d-

C. abc*+d-

D. -+*abcd

7.（2009）第 14 题

一个包含n个分支结点（非叶结点）的非空二叉树，它的叶结点数目最多为：

A. 2n+1

B. 2n-1

C. n-1

D. n+1

8.（2009）第 18 题

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

A. n

B. n+1

C. n-1

D. n(n-1)

9.（2010）第 5 题

如果树根算第1层，那么一棵n层的二叉树最多有（ ）个结点。

A. $2^n-1$

B. $2n$

C. $2^n+1$

D. $2^{n+1}$

10.（2010）第 9 题

前缀表达式+ 3 * 2 + 5 12的值是（ ）。

A. 23

B. 25

C. 37

D. 65

11.（2010）第 17 题

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

A. 2

B. 3

C. 4

D. 5

12.（2010）第 18 题

关于拓扑排序，下面说法正确的是（ ）。

A. 所有连通的有向图都可以实现拓扑排序

B. 对同一个图而言，拓扑排序的结果是唯一的

C. 拓扑排序中入度为0的结点总会排在入度大于0的结点的前面

D. 拓扑排序结果序列中的第一个结点一定是入度为0的点

13.（2010）第 19 题

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

A. 2k

B. 2k+1

C. k/2下取整

D. (k+1)/2下取整

14.（2011）第 5 题

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

A. 7

B. 21

C. 42

D. 49

15.（2011）第 7 题

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

A. 10

B. 11

C. 12

D. 13

16.（2011）第 19 题

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

A. a

B. b

C. c

D. d