一、单项选择题(每空2分，共20分)
1．下列函数中渐近时间复杂度最小的是( )。
A．T1(n)=nlog2n+5000n B．T2(n)=n2-8000n
C．T3(n)=nlog221-6000n D．T4(n)=2nlog2n-7000n
2．线性表的静态链表存储结构与顺序存储结构相比优点是( )。
A．所有的操作算法实现简单
B．便于随机存取
C．便于插入和删除
D．便于利用零散的存储器空间
3．设栈的输入序列为1，2，…，n，输出序列为a1，a2，…，an，若存在1≤k≤n使得ak=n，则当k≤i≤n时，ai为( )。
A．n-i+l B．n-(i-k) C．不确定
4．设高度为h的二叉树(根的层数为1)上只有度为0和度为2的节点，则此类二叉树中所包含的节点数至少为( )。
A．2h B．2h-1 C．2h+l D．h+l
5．设指针p指向线索树中的某个结点，则查找p在某种次序下的前驱或后继不能获得加速的是( )。
A．前序线索树中查找p的前序后继
B．中序线索树中查找p的中序后继
C．中序线索树中查找p的中序前继
D．后序线索树中查找*p的后序前继
6．假定有k个关键字互为同义词，若用线性探测法将这k个关键字存入散列表中，至少需要进行( )次探测。
A．k-1 B．k C．k+l D．k(k+1)/2
7．若待排序元素基本有序，则下列排序中平均速度最快的排序是( )；若要求辅助空间为O(1)，则平均速度最快的排序是( )；若要求排序是稳定的，且关键字为实数，则平均速度最快的排序是( )。
A．直接插入排序 B．直接选择排序 C．Shell排序
D．冒泡排序 E．快速排序 F．堆排序
C．归并排序 H．基数排序
8．对于多关键字而言，( )是一种方便而又高效的文件组织文式。
A．顺序文件 B．索引文件 C．散列文件 D．倒排文件
二、问答题(共25分)
1．设A[-2：6；-3：6]是一个用行主序存储的二维数组，已知A[-2，-3]的起始存储位置为loc(-2，-3)=1000，每个数组元素占用4个存储单元，求：(6分)
1)A[4，5]的起始存储位置loc(4，5)；
2)起始存储位置为1184的数组元素的下标。
2．给定二叉树的先序和后序遍历序列，能否重构出该二叉树?若能，试证明之，否则给出反例。(6分)
3．在含有n个关键字的m阶B-树中进行查找，至多读盘多少次?完全平衡的二叉排序树的读盘次数大约比它大多少倍?(设两种树中的每个节点均是一个存储块)。(8分)
4．用向量表示的循环队列的队首和队尾位置分别为1和max_size，试给出判断队列为空和为满的边界条件。(5分)
三、阅读程序题(共10分)
1．设G是一个有向无环图，试指出下述算法的功能，输出的序列是G的什么序列?(10分)
void Demo (ALGraph G)
{//G是图的逆邻接表，向量outdegree的各分量初值为0。
for(i=0；i<G.NodeNum；i++)
for(p=G.adjlist[i].firstedge；p；p=p->next)
//扫描i的入边表
outdegree[p->adjvex]++； //设p->adjvex=j，则将<i，j>的起点
j的出度加1
initStack(&s)； //设置空栈s
for(i=0；i<G.NodeNum；i++)
if(outdegree[i]==0)
Push(&s，i)； //出度为0的顶点i入栈
while(!StackEmpty(s)) //栈s非空
{ i=Pop(&Q)； //出栈，相当于删去顶点i
prinft(“%c”，G.adjlist[i].vertex)；//输出顶点i
for(p=G.adjlist[i].firstedge；p；p=p->next)
{ //扫描i的入边表
j=p->adjvex； //j是i的入边<j，i>的起点
outdegree[j]–； //j的出度减1，即删去i的入边<j，i>
if(!outdegree[j])
Push(&s’，j)； //若j的出度为0，则令其入栈
}//endfor
}//endwhile
}//endDemo
四、算法题(每题15分，共45分)
1．试设计算法在O(n)时间内将数组A[1．．n]划分为左右两个部分，使得左边的所有元素值均为奇数，右边的所有元素值均为偶数，要求所使用的辅助存储空间大小为O(1)。
2．试写一递归算法，从大到小输出二叉排序中所有的值不小于x的关键字，要求算法的时间为O(h+m)，其中h为树的高度，m为输出的关键字个数。
3．设G是以邻接表表示的无向图，v0是G中的一个顶点，k是一个正的常数。要求写一算法打印出图中所有与v0有简单路径相通，且路径长度小于等于k的所有顶点(不含v0)，路径长度由路径上的边数来定义。
