一．單項選擇題（本大題共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. 至少有2/m棵子樹 B. 至多有2/m棵子樹

C. 至少有2/m棵子樹 D. 至多有2/m棵子樹

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分）