（装订线内不要答题）

（考试时间 150 分钟）

一、单项选择题（本大题共15小题，每小题1分，共15分）

1、通常一个程序对应一个算法，说一个操作系统不是算法，是因为[ ]

A、操作系统执行结果不确定。

B、操作系统太复杂。

C、操作系统经常被扩充。

D、操作系统正常运行时不终止。

2、一个算法具有多个特性，其中算法的正确性是指：[ ]

A、计算机按算法指定的操作步骤顺序执行，能在执行有限步骤后给出结果。

B、正确的算法要求组成算法的规则和步骤的意义唯一确定，没有二义性。

C、能对有效的输入，总能在有限的时间内给出正确的输出。

D、同时指A和B两个方面。

3、某算法希望通过进栈和退栈操作得到所有可能的退栈序列。如果3次进栈操作依次将整数1、2和3进栈，只要栈非空，可以执行退栈操作；只要还有整数可进栈，也可以执行进栈操作。这样，因进栈操作和退栈操作所有可能的不同顺序，就可得到所有可能的整数1、2、3退栈序列，不同的退栈序列的个数为[ ]

A、4

B、5

C、6

D、7

4、以下函数的功能[ ]

int* f(int a[], int n, int key){

if(n == 0) return NULL;

if(a[0] == key) return a;

return f(a+1, n-1, key);

}

A、是在数组a[]的前n个元素中找值key。

B、是返回NULL(n=0)，或a(a[0]=key)。

C、不确定，因为该函数有错误。

D、是在数组a[]的前n个元素中找值等于key的元素的指针。

5、在以下序列中，可以看作是一个堆的是

A、9、6、4、2、8、1、3

B、9、8、4、2、3、6、1

C、9、8、4、2、6、3、1

D、9、4、8、1、6、3、2

6、下列排序算法都要对排序数列作多趟处理，才能完成排序要求，其中每趟处理后使数列中的有序段个数成倍减少，而有序段的元素个数成倍增加排序算法是[ ] A、shell排序B、堆排序C、快速排序D、归并排序