答题说明

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

输入格式

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

输出格式

对应输入题号的答案。

样例代码

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

#include <cstdio>
#include <cstring>

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

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）第 12 题

近20年来，许多计算机专家都大力推崇递归算法，认为它是解决较复杂问题的强有力的工具。在下列关于递归算法的说法中，正确的是（ ）。

A. 在1977年前后形成标准的计算机高级语言“FORTRAN77”禁止在程序使用递归，原因之一是该方法可能会占用更多的内存空间

B. 和非递归算法相比，解决同一个问题，递归算法一般运行得更快一些

C. 对于较复杂的问题，用递归方式编程一般比非递归方式更难一些

D. 对于已经定义好的标准数学函数 sin(x)，应用程序中的语句“y=sin(sin(x));”就是一种递归调用

2.（2007）第 16 题

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

A. 2 4 3 6 5 7

B. 2 4 1 2 5 7

C. 2 4 3 1 7 6

D. 2 4 3 6 7 5

3.（2008）第 7 题

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

A. 6

B. 5

C. 4

D. 3

4.（2008）第 11 题

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

A. 队列

B. 多维数组

C. 线性表

D. 栈

5.（2008）第 14 题

将数组{8, 23, 4, 16, 77, -5, 53, 100}中的元素按从大到小的顺序排列，每次可以交换任意两个元素，最少需要交换（ ）次

A. 4

B. 5

C. 6

D. 7

6.（2008）第 15 题

对有序数组{5, 13, 19, 21, 37, 56, 64, 75, 88，92，100}进行二分查找，成功查找元素19的查找长度（比较次数）是（ ）。

A. 1

B. 2

C. 3

D. 4

7.（2009）第 12 题

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

A. EDCFAB

B. DECABF

C. CDFEBA

D. BCDAEF

8.（2009）第 15 题

快速排序最坏情况下的算法时间复杂度为：

A. $O(log_2n)$

B. $O(n)$

C. $O(nlog_2n)$

D. $O(n_2)$

9.（2009）第 16 题

有一个由4000个整数构成的顺序表，假定表中的元素已经按升序排列，采用二分查找定位一个元素。则最多需要几次比较就能确定是否存在所查找的元素：

A. 11次

B. 12次

C. 13次

D. 14次

10.（2009）第 17 题

排序算法是稳定的意思是关键码相同的记录排序前后相对位置不发生改变，下列哪种排序算法是不稳定的：

A. 冒泡排序

B. 插入排序

C. 归并排序

D. 快速排序

11.（2010）第 12 题

基于比较的排序时间复杂度的下限是（ ），其中n表示待排序的元素个数。

A. $Θ(n)$

B. $Θ(n log_2n)$

C. $Θ(log n)$

D. $Θ(n_2)$

12.（2010）第 15 题

元素R1、R2、R3、R4、R5入栈的顺序为R1、R2、R3、R4、R5。如果第1个出栈的是R3，那么第5个出栈的不可能是（ ）。

A. R1

B. R2

C. R4

D. R5

13.（2010）第 16 题

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

A. p->rlink->llink = p->rlink;

p->llink->rlink = p->llink; delete p;

B. p->llink->rlink = p->rlink;

p->rlink->llink = p->llink; delete p;

C. p->rlink->llink = p->llink;

p->rlink->llink->rlink = p->rlink; delete p;

D. p->llink->rlink = p->rlink;

p->llink->rlink->llink = p->llink; delete p;

14.（2011）第 8 题

体育课的铃声响了，同学们都陆续地奔向操场，按老师的要求从高到矮站成一排。每个同学按顺序来到操场时，都从排尾走到排头，找到第一个比自己高的同学，并站在他的后面。这种站队的方法类似于（ ）算法。

A. 快速排序

B. 插入排序

C. 冒泡排序

D. 归并排序

15.（2011）第 11 题

广度优先搜索时，需要用到的数据结构是（ ）。

A. 链表

B. 队列

C. 栈

D. 散列表

16.（2011）第 13 题

在含有n个元素的双向链表中查询是否存在关键字为k的元素，平均情况下运行的时间复杂度是（ ）。

A. $O(1 )$

B. $O( log_2n )$

C. $O( n )$

D. $O( n log_2 n )$

17.（2011）第 17 题

（ ）是一种选优搜索法，按选优条件向前搜索，以达到目标。当搜索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择。

A. 回溯法

B. 枚举法

C. 动态规划

D. 贪心