可做奧鵬院校所有作業(yè)，畢業(yè)論文，咨詢請?zhí)砑観Q：296856541 微信：aopopengzs
數(shù)據(jù)結(jié)構(gòu)
要求：
一、 獨(dú)立完成，下面已將五組題目列出，任選一組進(jìn)行作答，每人只答一組題目，多答無效，滿分100分
二、答題步驟：
1. 使用A4紙打印學(xué)院指定答題紙（答題紙請?jiān)斠姼郊?/p>
2. 在答題紙上使用黑色水筆按題目要求手寫作答；答題紙上全部信息要求手寫，包括學(xué)號、姓名等基本信息和答題內(nèi)容，請寫明題型、題號；
三、提交方式：請將作答完成后的整頁答題紙以圖片形式依次粘貼在一個Word
文檔中上傳（只粘貼部分內(nèi)容的圖片不給分），圖片請保持正向、清晰；
1. 完成的作業(yè)應(yīng)另存為保存類型是“Word97-2003”提交;
2. 上傳文件命名為“中心-學(xué)號-姓名-科目.doc”;
3. 文件容量大?。翰坏贸^20MB。
提示：未按要求作答題目的作業(yè)及雷同作業(yè)，成績以0分記！
題目如下：
第一組：
一、編程題（每小題30分，共60分）
(一)
已知某哈希表的裝載因子小于1，哈希函數(shù)H(key)為關(guān)鍵字（標(biāo)識符）的第一個字母在字母表中的序號，處理沖突的方法為線性探測開放定址法。試編寫一個按第一個字母的順序輸出哈希表中所有關(guān)鍵字的算法。
(二)
用標(biāo)準(zhǔn)C語言實(shí)現(xiàn)Hanoi塔問題
二、解答題（20分）
(一)
設(shè)待排序記錄的關(guān)鍵字序列為{46, 55, 13, 42, 94, 05, 17, 70}寫出其第一趟快速排序過程。（要求寫出每次交換后的序列，并且樞軸記錄到位也算一次交換）
初始關(guān)鍵字： 46 55 13 42 94 05 17 70
1次交換后：
2次交換后：
3次交換后：
4次交換后：
5次交換后：
三、畫圖題（20分）
(一)
將下面的森林變換成二叉樹
第二組：
一、編程題（每小題30分，共60分）
(一)
用標(biāo)準(zhǔn)C語言實(shí)現(xiàn)Hanoi塔問題
(二)
1.設(shè)單鏈表中有僅三類字符的數(shù)據(jù)元素(大寫字母、數(shù)字和其它字符)，要求利用原單鏈表
中結(jié)點(diǎn)空間設(shè)計(jì)出三個單鏈表的算法，使每個單鏈表只包含同類字符。
2. 設(shè)計(jì)在鏈?zhǔn)酱鎯Y(jié)構(gòu)上交換二叉樹中所有結(jié)點(diǎn)左右子樹的算法。
二、解答題（20分）
(一)
已知一棵二叉樹的先序序列是ABCDEFGHIJK，中序序列是CDBGFEAHJIK，請構(gòu)造出該二叉樹。
三、畫圖題（20分）
(一)
設(shè)有序順序表中的元素依次為017, 094, 154, 170, 275,503, 509, 512, 553, 612, 677, 765, 897, 908。試畫出對其進(jìn)行折半搜索時的判定樹, 并計(jì)算搜索成功的平均搜索長度和搜索不成功的平均搜索長度。
第三組：
一、編程題（每小題30分，共60分）
(一)
1.設(shè)單鏈表中有僅三類字符的數(shù)據(jù)元素(大寫字母、數(shù)字和其它字符)，要求利用原單鏈表
中結(jié)點(diǎn)空間設(shè)計(jì)出三個單鏈表的算法，使每個單鏈表只包含同類字符。
2. 設(shè)計(jì)在鏈?zhǔn)酱鎯Y(jié)構(gòu)上交換二叉樹中所有結(jié)點(diǎn)左右子樹的算法。
(二)
1.設(shè)有一組初始記錄關(guān)鍵字序列（K1，K2，?，Kn），要求設(shè)計(jì)一個算法能夠在O(n)的時間
復(fù)雜度內(nèi)將線性表劃分成兩部分，其中左半部分的每個關(guān)鍵字均小于Ki，右半部分的每個關(guān)鍵字均大于等于Ki。
2． 設(shè)有兩個集合A和集合B，要求設(shè)計(jì)生成集合C=A∩B的算法，其中集合A、B和C用鏈?zhǔn)酱鎯Y(jié)構(gòu)表示。
二、解答題（20分）
(一)
若二叉樹中各結(jié)點(diǎn)的值均不相同，則由二叉樹的前序序列和中序序列，或由其后序序列和中序序列均能唯一地確定一棵二叉樹，但由前序序列和后序序列卻不一定能唯一地確定一棵二叉樹。
(1)已知一棵二叉樹的前序序列和中序序列分別為ABDGHCEFI和GDHBAECIF，請畫出此二叉樹。
(2)已知一棵二叉樹的在序序列和后序序列分別為BDCEAFHG和DECBHGFA，請畫出此二叉樹。
(3)已知一棵二叉樹的前序序列和后序序列分別為AB和BA，請畫出這兩棵不同的二叉樹。
三、畫圖題（20分）
(一)
某子系統(tǒng)在通信聯(lián)絡(luò)中只可能出現(xiàn)8種字符，其出現(xiàn)的概率分別為0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11試設(shè)計(jì)赫夫曼編碼
第四組：
一、編程題（每小題30分，共60分）
(一)
已知某哈希表的裝載因子小于1，哈希函數(shù)H(key)為關(guān)鍵字（標(biāo)識符）的第一個字母在字母表中的序號，處理沖突的方法為線性探測開放定址法。試編寫一個按第一個字母的順序輸出哈希表中所有關(guān)鍵字的算法。
(二) 設(shè)順序表L是一個遞增有序表，試寫一算法，將x插入L中，并使L仍是一個有序表。
二、解答題（20分）
(一)
寫出下圖所示的AOV網(wǎng)的可能拓?fù)湫蛄?，要求至少寫出五個
三、畫圖題（20分）
(一)
設(shè)有序順序表中的元素依次為017, 094, 154, 170, 275,503, 509, 512, 553, 612, 677, 765, 897, 908。試畫出對其進(jìn)行折半搜索時的判定樹, 并計(jì)算搜索成功的平均搜索長度和搜索不成功的平均搜索長度。
第五組：
一、編程題（每小題30分，共60分）
(一)
對于二維整數(shù)數(shù)組A[m][n]，對下列三種情況，分別編寫相應(yīng)的函數(shù)。
1. 求數(shù)組所有邊緣元素的數(shù)值和。
int sum1(int A[M][N],int m ,int n)
{
2.求從A[0][0]開始的互不相鄰的所有元素的和
注：一個元素的八個方向上的第一個元素均為相鄰元素。
int sum2 (int A[M][N] , int m , int n)
{
3. 假定m=n，并為偶數(shù)，請分別計(jì)算正、反兩條對角線上的元素值之和。
int sum3(int A[M][N] , int n)
{
(二)
已知某哈希表的裝載因子小于1，哈希函數(shù)H(key)為關(guān)鍵字（標(biāo)識符）的第一個字母在字母表中的序號，處理沖突的方法為線性探測開放定址法。試編寫一個按第一個字母的順序輸出哈希表中所有關(guān)鍵字的算法。
二、解答題（20分）
(一)
設(shè)待排序記錄的關(guān)鍵字序列為{46, 55, 13, 42, 94, 05, 17, 70}寫出其第一趟快速排序過程。（要求寫出每次交換后的序列，并且樞軸記錄到位也算一次交換）
初始關(guān)鍵字： 46 55 13 42 94 05 17 70
1次交換后：
2次交換后：
3次交換后：
4次交換后：
5次交換后：
三、畫圖題（20分）
(一)
已知二維數(shù)組表示的圖的鄰接矩陣如下圖所示。試分別畫出自頂點(diǎn)1出發(fā)進(jìn)行遍歷所得的深度優(yōu)先生成樹和廣度優(yōu)先生成樹。
