一、單項選擇題（本大題共10道小道小題，每小題3分，共30分）
1. 算法的時間復雜度取決于 【 】
A. 問題的規模 B. 待處理數據的初始狀態
C. 軟件和硬件的組合 D. 操作系統
2. 向一個棧頂指針為top的鏈棧中插入一個s結點，則執行 【 】
A. top->next=s; B. s->next=top->next; top->next=s;
C. s->next=top; top=s; D. s->next=top; top=top->next;
3. 廣義表（（a））的表頭是 【 】
A. a B. (a) C. () D. ((a))
4. 由帶權為8、2、5、7的葉子結點構造一棵哈夫曼樹，該樹的帶權路徑長度為 【 】
A. 37 B. 32 C. 46 D. 43
5. 采用鄰接表存儲的圖，其BFS算法類似于二叉樹的 【 】
A. 中序遍歷 B. 先序遍歷 C. 后序遍歷 D. 按層遍歷
6. 在非空m階B_樹上，除根結點之外的所有其他非終端結點 【 】
A. 至少有 棵子樹 B. 至多有 棵子樹
C. 至少有 棵子樹 D. 至多有 棵子樹
7. 對線性表進行順序查找時，要求線性表的存儲結構為 【 】
A. 散列存儲 B. 順序存儲或者鏈式存儲
C. 壓縮存儲 D. 索引存儲
8. 在關鍵字“基本有序”的情況下，最佳排序算法為 【 】
A. 快速排序 B. 冒泡排序 C. 直接插入排序 D. 基數排序
9. 折半查找法和二叉排序樹的時間性能 【 】
A. 與處理數據量有關 B. 相同 C. 不相同 D. 不確定
10. 串是一種特殊的線性表，其特殊性體現在 【 】
A. 可以順序存儲 B. 數據元素是一個字符
C. 可以鏈接存儲 D. 數據元素可以是多個字符

二、填空題（本大題共10小題，每小題2分，共20分）
1. 在具有n個單元的循環隊列中，隊滿時共有____________個元素。
2. 單鏈表中設置頭結點的目的是____________。
3. 消除遞歸_____________需要使用棧。
4. 在具有n(n≥1)個結點的k叉樹中，有_____________個空指針。
5. 深度為5的二叉樹至多有_________個結點。
6. 一個連通圖的__________是一個極小連通子圖。
7. 對稀疏圖進行DFS遍歷時，應該采用___________作為其存儲結構。
8. 在哈希表中，裝填因子α越大，則_______________________。
9. 在堆排序和快速排序中，若原始記錄接近有序，則應該選擇____________。
10. 設關鍵字序列為｛3, 7, 6, 9, 7, 1, 4, 5, 20｝，對其排序的最少交換次數為_________。

三、簡答題（本大題共6道小題，共56分）
1. 若中序序列為ABC，試問有多少種不同的形態的二叉樹可以得到這一遍歷結果？畫出所有的二叉樹。（9分）
2. 對于下圖，請給出：
（1） 對應的鄰接矩陣，并給出V1、V2、V3的出度和入度;
（2） 鄰接表和逆鄰接表;
（3） 強連通分量。（10分）
3. 已知關鍵字序列為｛9, 6, 2, 5, 4, 3, 1, 10, 7, 11, 8｝，試回答：
（1） 按表中元素的順序，構造一棵平衡二叉排序樹。
（2） 在等概率的情況下，求查找成功的ASL值。（10分）
4. 在采用線性探測再散列法解決沖突的散列表中，所有同義詞在表中是否一定相鄰？試說明理由。（9分）
5. 有關鍵字｛25, 50, 55, 20, 30, 45, 40, 15, 10, 35｝，判斷其是否為堆，若不是堆，請調整為一個小根堆。要求寫出調整過程。（9分）
6. 什么是內部排序？穩定性指的是什么？（9分）

四、算法閱讀題（本大題共3道小題，每小題8分，共24分）
【說明】結構定義
struct ListNode {
elemtype data;
struct ListNode *next;
};

struct BtreeNode {
elemtype data;
struct BtreeNode *lchild, *rchild;
};

1. 下面算法的功能是將隊列中的數據元素進行逆置。設棧和隊列的元素類型均為int。請在空白處填入正確的語句。
Void unknown(queue &q)
{
__________①_________;
int d;
InitStack(s);
while(_______②_______){
Dequeue(q, d);
Push(s, d);
}
while(!StackEmpty(s)){
_______③______;
Enqueue(q, d);
}
}
2. 下面的算法是統計單鏈表中數據域的值為X的結點個數。請在空白處填入正確的語句。
int CountNodeX(struct ListNode *head, Elemtype x)
{
struct ListNode *p;
_______①______;
p = head;
while(______②_____){
if(_______③______) n++;
p=p->next;
}
________④_________;
}
3. 下面的算法完成了對一棵二叉樹中所有的左、右子樹的相互交換。請在空白入填入正確的語句。
Void TNodeExchang(struct BTreeNode *root)
{
if(________①________){
TNodeExchang(root->lchild);
_________②__________;
struct BTreeNode *p;
p = _______③_________;
root->lchild = root->rchild;
root->rchild = _______④______;
}
}

五、算法設計題（本大題共3道小題，共20分）
1. 已知Head是帶頭結點的單鏈表的頭指針，試編寫逆序輸出表中各元素的遞歸算法。假設數據為整數。
Void FindLinkData(struct ListNode *head){…}（7分）
2. 試設計一個算法，求出指定結點在給定的二叉排序樹中的層次。
【要求】1. 給出算法的設計思想;
2. 給出算法代碼。（7分）
int pLevel(struct BTreeNode *root, struct BTreeNode *p)
{//求指定結點p在以root為根的二叉樹中的層次}
3. 給出一棵二叉樹的前序序列和后序序列，能否唯一地確定一棵二叉樹？試證明你的論斷。（6分）