1、一个算法必须保证执行有限步之后结束，这是算法的    性

A) 有穷       B) 确定      C) 可行    D)输出

2、A算法的时间复杂度为O（n3）,B算法的时间复杂度为O（2n）,则说明    

A)对于任何数据量，A算法的时间开销都比B算法小  

B)随着问题规模n的增大，Ａ算法比Ｂ算法有效

C)随着问题规模n的增大，Ｂ算法比Ａ算法有效

D)对于任何数据量，Ｂ算法的时间开销都比A算法小

3、 对线性表，在     情况下应当采用链表表示 

A)经常需要随机地存取元素                B)经常需要进行插入和删除运算

   C)表中元素需要占据一片连续的存储空间    D)表中元素的个数不变 

4、 对线性表进行二分查找，其前提条件是     

A)顺序表        B) 有序的顺序表     C) 链表       D) 有序的链表

5、对于链队，在进行删除操作时，      。

A）仅修改头指针                 B) 仅修改尾指针

C）头、尾指针都要修改         D) 头、尾指针可能都要修改

6、设二维数组A[m][n]，每个数组元素占用k个字节，第一个数组元素的存储地址是Loc(a[0][0]),求按行优先顺序存放的数组元素a[i][j](0≤i≤m-1,0≤j≤n-1)的存储地址为   

A) Loc(a[0][0])+((i-1)*n-1)*k      B) Loc(a[0][0])+(i*n+j)*k  

C) Loc(a[0][0])+(j*m+i)*k          D) Loc(a[0][0])+((j-1)*m+i-1)*k

7、如果二叉树T2是由树T1转换而来的二叉树，那么T1中结点的先序就是T2中结点的     。

A)先序    B)中序    C)后序     D)无对应关系

8、一个具有1025个结点的二叉树的高h为    

    A) 11    B)10     C)11到1025     D)12到1024

9、一棵二叉树的后序遍历序列为EFHIGJK，中序遍历序列为HFIEJKG      ，则该二叉树根结点的右孩子为      。

A)E     B)F      C)G   D)H

10、n个结点的线索二叉树上含有的线索数为      。

A)2n     B)n-1    C)n+1    D)n

11、堆是   

A)完全二叉树       B)线性表       C)二叉排序树      D)平衡二叉树 

12、假定在一棵二叉树中，度为2的结点数为15，度为1的结点数为30，则叶子结点数为     。

A)15      B) 16    C) 17       D）18

13、由带权为9、2、5、7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为     

   A)23     B) 37      C)46         D) 44

14、下面的叙述中，不正确的是     

A)关键活动不按期完成就会影响整个工程完成时间

B)任何一个关键活动提前完成，将使整个工程提前完成

C)所有关键活动提前完成，则整个工程提前完成  

D)某些关键活动若提前完成，将可能使整个工程提前完成

15、设哈希表长为14，哈希函数为h(key)=key%11。表中现有数据15、38、61和84，其余位置为空，如果用二次探测再散列处理冲突，则49的位置是       

    A)8     B)3     C)5   D)9

16、在一棵二叉排序树上查找值为35的数据，以下比较的数据序列正确的为     

    A）28、36、18、46、35    B）18、36、28、46、35

C）46、28、18、36、35    D）46、36、18、28、35

17、下面排序算法中，    算法可能会出现下面情况：初始数据有序时，花费的时间反而最多

 A)堆排序            B)冒泡排序     C)快速排序     D)希尔（Shell）排序        

18、任何一棵二叉树的叶子结点在先序、中序和后序遍历中的相对次序     。

A)不发生改变     B) 发生改变      C) 不能确定       D) 以上都不对

19、如果从无向图的任一顶点出发进行一次图遍历即可访问所有顶点，则该图一定是      。

A)完全图     B) 连通图     C)有回路     D) 一棵树

20、对有18个元素的有序表r[0..17],进行二分查找，则查找r[3]的比较序列下标为    

A)0、1、2   B)8、4、1、2    C)8、4、2   D) 8、3、1、2

二、填空题（24分,每空3分）

1、下面程序段的时间复杂度为  （1） 。

s=0;

for(i=1;i for(j=1;j       s+=i*j；

2、已知完全二叉树T的第5层只有7个结点，则该树共有（2）个叶子结点

3、始数据为（35、97，30，50，23，11，101，100，46 ）按快速排序算法一趟划分后，数据的排列是    （3）     。

4、n个顶点的连通图用邻接矩阵表示时，该矩阵至少有（4） 非零元素。

5、评价哈希函数好坏的标准是   （5） 。 

6、对于关键字序列：12、13、11、18、60、15、7、20、25、100，用筛选法建堆，必须从值为 （6）的关键字开始。

7、Dijkstra最短路径算法按（7）依次产生路径，在边（弧）上权有 （8）值时不能正确工作。

三、简答题（25分）

1、（4分）有O(1),O(log 2n),O(n),O(nlog2n),O(n2),O(n3),…,O(nk),O(2n),试用≤把它们从左向右连接起来。

2、 （9分）已知3阶B_树如图所示。

    (1)画出将关键字88插入之后的B-树；

    (2)画出将关键字47和66依次插入之后的B-树。

3、（4分）简述哈希查找中链地址法解决冲突的方法。

4、（8分）有一个AOE网如下：

                                                a7=4

                                     a6=3                         a12=4

                    a4=6                            

                                        a8=1             a10=5   a13=2

                   a5=4           a9=3               a11=4

(1)求出所有事件的最早发生时间与最迟发生时间（4分）

(2)列出所有关键活动（4分）

四、算法设计（用类-C/类-C++描述）（11分）

1、(5分)写一个递归的二分查找算法bina_s(d,x,l,h)。

  其中：d为一维数组，x为待查数据，l、h为查找的范围（l,h给出的是下标范围，下标从0计算）

2、(6分)在邻接表表示的无向图中加入一条边（u,v），完成算法：AddEdge(adj,u,v)

其中：adj为邻接表表头数组，u、v是顶点号，为方便，u、v假定是合法的，且邻接表中没有边(u,v)（顶点号从1计，数组下标从0计，图的顶点数为n）。