一、簡答題（20分）
1.數(shù)據(jù)類型和抽象數(shù)據(jù)類型的含義
2.算法的特性與算法的時間復(fù)雜度
3.快速排序方法和最壞的情況是什么？簡要分析說明
4.棧、隊列的共同點與不同點，說明其屬于線形表的原因
二、方法選擇（20分）
1.一棵二叉排序樹中各結(jié)點不相同，欲得到一個由大到小的結(jié)點值遞減序列，你認為采用什么方法能得到要求的結(jié)果？
2.設(shè)有1000個無序元素，僅要求找出前10個最小元素，在下列排序方法中（歸并排序，基數(shù)排序，快速排序，堆排序，插入排序），那種方法，為什么？
三、（40分，每題8分）
１。已知一個循環(huán)單鏈表la，av是可利用棧的頭指針，請用３個賦值語句，完成將整個循環(huán)鏈表釋放的功能。（即將表整個歸還到可用的?？臻g）
2.給出求N階hanoi塔的函數(shù)定義如下：Hanoi （ int n，char x，char y ，char
z ）
{ if （ n= =1） move （ x ，1，z）
Else{ hanoi（ n-1， x，z，y）；
Move（x，n，z）；
Hanoi（n-1，y，x，z）；
}
}
寫出執(zhí)行hanoi（3，a，b，c）時遞歸函數(shù)的實在參變量變化，以及move的搬運過程。
3.已知關(guān)鍵字序列為：（75，33，52，41，12，88，66，27），哈希表長為１０，哈希函數(shù)為：Ｈ（ｋ）＝ｋＭＯＤ７，解決沖突用線性探測再散列法，要求構(gòu)造哈希表，求出等概率下查找成功查找長度。
4.已知一棵二叉樹，中序序列DBCAFGE，后序序列DCBGFEA，構(gòu)造該二叉樹。
5.給定權(quán)值｛8，12，4，5，26，16，9｝，構(gòu)造一個哈夫曼樹，并計算其帶權(quán)路徑長度。
四、編寫程序（15分）
建立線形表，（a1，a2，a3…。，an）的單鏈表存儲，并實現(xiàn)其就地逆置為（an， ，an-1…a2.，a1）。
五、編寫程序（10分）
在中序線索樹中，要找出Ｘ結(jié)點的前驅(qū)結(jié)點，請寫出相關(guān)函數(shù)定義。
Ltag Lc Data Rtag Rc
六、編寫算法（20分）
已知有Ｎ個結(jié)點的無向圖，采用鄰接表結(jié)構(gòu)存儲，要求對每個連通子圖中一個生成樹中的各條邊逐層輸出，邊的輸出格式為（ki，kj）。
七、編寫算法（25分）
1.寫出建立二叉樹，二叉鏈表存儲結(jié)構(gòu)的算法。（10分）
2.已知二叉樹采用二叉鏈表方式存放，要求對二叉樹從１開始進行連續(xù)編號，要求每個結(jié)點的編號大于其左右孩子的編號，同一結(jié)點的左右孩子中，左孩子編號小于右孩子編號。給出在二叉樹中結(jié)點的數(shù)據(jù)域部分填寫，實現(xiàn)如上要求編號的非遞歸算法。（10分）
3.已知二叉樹采用二叉鏈表方式存放，給出判定它是否為一棵二叉排序樹的算法。（5分）
1.數(shù)據(jù)類型和抽象數(shù)據(jù)類型的含義
2.算法的特性與算法的時間復(fù)雜度
3.快速排序方法和最壞的情況是什么？簡要分析說明
4.棧、隊列的共同點與不同點，說明其屬于線形表的原因
二、方法選擇（20分）
1.一棵二叉排序樹中各結(jié)點不相同，欲得到一個由大到小的結(jié)點值遞減序列，你認為采用什么方法能得到要求的結(jié)果？
2.設(shè)有1000個無序元素，僅要求找出前10個最小元素，在下列排序方法中（歸并排序，基數(shù)排序，快速排序，堆排序，插入排序），那種方法，為什么？
三、（40分，每題8分）
１。已知一個循環(huán)單鏈表la，av是可利用棧的頭指針，請用３個賦值語句，完成將整個循環(huán)鏈表釋放的功能。（即將表整個歸還到可用的?？臻g）
2.給出求N階hanoi塔的函數(shù)定義如下：Hanoi （ int n，char x，char y ，char
z ）
{ if （ n= =1） move （ x ，1，z）
Else{ hanoi（ n-1， x，z，y）；
Move（x，n，z）；
Hanoi（n-1，y，x，z）；
}
}
寫出執(zhí)行hanoi（3，a，b，c）時遞歸函數(shù)的實在參變量變化，以及move的搬運過程。
3.已知關(guān)鍵字序列為：（75，33，52，41，12，88，66，27），哈希表長為１０，哈希函數(shù)為：Ｈ（ｋ）＝ｋＭＯＤ７，解決沖突用線性探測再散列法，要求構(gòu)造哈希表，求出等概率下查找成功查找長度。
4.已知一棵二叉樹，中序序列DBCAFGE，后序序列DCBGFEA，構(gòu)造該二叉樹。
5.給定權(quán)值｛8，12，4，5，26，16，9｝，構(gòu)造一個哈夫曼樹，并計算其帶權(quán)路徑長度。
四、編寫程序（15分）
建立線形表，（a1，a2，a3…。，an）的單鏈表存儲，并實現(xiàn)其就地逆置為（an， ，an-1…a2.，a1）。
五、編寫程序（10分）
在中序線索樹中，要找出Ｘ結(jié)點的前驅(qū)結(jié)點，請寫出相關(guān)函數(shù)定義。
Ltag Lc Data Rtag Rc
六、編寫算法（20分）
已知有Ｎ個結(jié)點的無向圖，采用鄰接表結(jié)構(gòu)存儲，要求對每個連通子圖中一個生成樹中的各條邊逐層輸出，邊的輸出格式為（ki，kj）。
七、編寫算法（25分）
1.寫出建立二叉樹，二叉鏈表存儲結(jié)構(gòu)的算法。（10分）
2.已知二叉樹采用二叉鏈表方式存放，要求對二叉樹從１開始進行連續(xù)編號，要求每個結(jié)點的編號大于其左右孩子的編號，同一結(jié)點的左右孩子中，左孩子編號小于右孩子編號。給出在二叉樹中結(jié)點的數(shù)據(jù)域部分填寫，實現(xiàn)如上要求編號的非遞歸算法。（10分）
3.已知二叉樹采用二叉鏈表方式存放，給出判定它是否為一棵二叉排序樹的算法。（5分）