二、填空题(本大题共10小题，每小题2分，共20分)

请在每小题的空格中填上正确答案。错填、不填均无分。

16.如果某算法对于规模为n的问题的时间耗费为T（n）=3n³，在一台计算机上运行时间为t秒，则在另一台运行速度是其64倍的机器上，用同样的时间能解决的问题规模是原问题规模的                     倍。

17.将两个长度分别为m和n的递增有序单链表，归并成一个按元素递减有序的单链表，可能达到的最好的时间复杂度是                    。

18.已知循环队列的存储空间大小为m，队头指针front指向队头元素，队尾指针rear指向队尾元素的下一个位置，则在队列不满的情况下，队列的长度是            。

19.字符串“sgabacbadfgbacst” 中存在有             个与字符串“ba”相同的子串。

20.假设以列优先顺序存储二维数组A[5][8]，其中元素A[0][0]的存储地址为LOC（a₀₀）,且每个元素占4个存储单元，则数组元素A[i][j]的存储地址为                 。

21.假设用<x,y>表示树的边（其中x是y的双亲），已知一棵树的边集为

{<b,d>,<a,b>,<c,g>,<c,f>,<c,h>,<a,c>}，该树的度是                    。

22.n个顶点且含有环路的无向连通图中，至少含有                    条边。

23.在一般情况下用直接插入排序、选择排序和冒泡排序的过程中，所需记录交换次数最少的是                    。

24.和二分查找相比，顺序查找的优点是除了不要求表中数据元素有序之外，对      结构也无特殊要求。

25.顺序文件中记录存放的物理顺序和                    顺序一致。

三、解答题(本大题共4小题，每小题5分，共20分)

26.由森林转换得到的对应二叉树如图所示，写出原森林中第三棵树的前序序列和后序序列。

前序序列：

后序序列：

27.图的邻接表的类型定义如下所示：

#define MaxVertexNum    50

typedef struct node {

int adjvex;

struct  node  *next;

}EdgeNode;

typedef struct  {

VertexType  vertex;

EdgeNode  *firstedge;

}VertexNode;

typedef  VertexNode  AdjList[MaxVertexNum];

typedef  struct {

AdjList  adjlist;

int n, e;

}ALGraph;

为便于删除和插入图的顶点的操作，可将邻接表的表头向量定义为链式结构，两种定义的存储表示实例如下图所示，请写出重新定义的类型说明。

28.某类物品的编号由一个大写英文字母及2位数字（0..9）组成，形如E32。运用基数排序

对下列物品编号序列进行按字典序的排序，写出每一趟（分配和收集）后的结果。

E13，A37，F43，B32，B47，E12，F37，B12

第一趟：

第二趟：

第三趟：

29.（1）画出对表长为13的有序顺序表进行二分查找的判定树；

（2）已知关键字序列为（12，14，16，21，24，28，35，43，52，67，71，84，99），写出在该序列中二分查找37时所需进行的比较次数。

（1）

（2）

四、算法阅读题（本大题共4小题，每小题5分，共20分）

30.已知线性表的存储结构为顺序表，阅读下列算法，并回答问题：

（1）设线性表L=（21，-7，-8，19，0，-11，34，30，-10），写出执行f30(&L)后的L状态；

（2）简述算法f30的功能。

void  f30 (SeqList  *L) {

int  i,j;

for (i=j=0;i<L->length; i++)

if(L->data[i]>=0){

if(i!=j)L->data[j]=L->data[i];

j++；

}

L->le