一、單項選擇題(每空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)，路徑長度由路徑上的邊數來定義。