算法基础2008年考题

（装订线内不要答题）

（考试时间 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、归并排序

算法基础第1页（/共7页）

算法基础 第2页(共7页)

7、对整数序列25， 34， 58， 12， 19， 50，18作从小到大排序，经排序算法一趟处理后，序列变成50，12，34，25，58，18，19。采用的排序方法是 [ ]

A 、基数排序

B 、选择排序

C 、快速排序

D 、shell 排序

8、对有100个元素的有序线性表，用二分法检索，最大的比较次数是 [ ]

A 、100

B 、7

C 、10

D 、50

9、一棵二叉检索树，它的6个结点的关键码分别是字符A 、B 、C 、D 、E 、F 。如果该二叉检索树的前序遍历为DACBFE ，则在以下4个序列中，可能是相应的层次遍历的是 [ ]

A 、DCEBAF

B 、DAFCEB

C 、DCEAFB

D 、DAECDB

10、在平衡二叉检索树的结点X 的左子结点的右子树中插入一个新结点，使结点X 不平衡，则要让结点X 重新平衡，需采用的旋转方法是 [ ]

A 、先左旋转，再右旋转

B 、右单旋转

C 、先右旋转，再左旋转

D 、左单旋转

11

[ ] 0 1 2 3

A 、DBAC

B 、DBCA

C 、DCBA

D 、DCAB

12、如果某个问题有以下多种可能的求解方法，则一般情况下相对较快的算法是 [ ]

A 、分治法

B 、迭代法

C 、贪婪法

D 、试探法

13、在以下四种可选的算法类别中，快速排序算法是属于 [ ]

A 、分治法

B 、迭代法

C 、贪婪法

D 、试探法

14、BM 算法和KMP 算法都是有效的字符串匹配算法，其中BM 算法考虑到 [ ]

A 、正文中可能出现的字符

B 、正文和模式中所有可能出现的字符

C 、模式中出现的字符

D 、正文与模式之间字符集上的差异

15、m 阶B 树对结点的关键码个数有限制，在不是根结点的叶子结点上删除一个关键码时，发生调整(“右借”、“左借”、合并)，是因为叶结点删除前关键码个数小于 [ ]

A 、⎡m/2⎤-1

B 、[m/2]

C 、[m/2]-1

D 、⎡m/2⎤

二、填空题（本大题共10小题，每小题2分，共20分）

（装订线内不要答题）16、对整数序列1，3，7，6，0，2

作从小到大选择排序，需经多轮处理，经过两轮处理后，该整数序列变成_______。

17、对整数序列20, 22, 56, 21, 17, 10作从小到大排序。采用shell排序方法，第一轮取间隔g为3，经这一轮处理序列变成__________。

18、在插入排序、选择排序、归并排序和基数排序这四种排序方法中，最好和最坏情况下的时间复杂度均为O(n lb n)，且稳定的排序方法是_______。

19、二叉检索树从空开始，依次插入40、57、49、21、63、28，然后对该二叉检索树作前序遍历，遍历结果是___________。

20、用散列表表示集合时，要合理选用散列中的关键技术，散列的关键技术是__________。

21、为一个连通的带权无向图构造最小生成树时，对能使用和不能使用的边的要求是_______。

22、在动态规划算法中，首先要寻找大问题的解由子问题解表示的动态方程，另为了避免求解相同子问题的解，采用的措施是________。

23、采用KMP算法，在正文中寻找与模式xyxxyzxu匹配的子串，该模式各字符的失败链接值依次为_______。 …… 此处隐藏：2986字，全部文档内容请下载后查看。喜欢就下载吧 ……