可做奧鵬院校所有作業(yè)，畢業(yè)論文，咨詢請(qǐng)?zhí)砑観Q：296856541      微信：aopopengzs

數(shù)據(jù)結(jié)構(gòu)

要求：

一、 獨(dú)立完成，下面已將五組題目列出，任選一組進(jìn)行作答，每人只答一組題目，多答無(wú)效，滿分100分

二、答題步驟：

1. 使用A4紙打印學(xué)院指定答題紙（答題紙請(qǐng)?jiān)斠?jiàn)附件）；

2. 在答題紙上使用黑色水筆按題目要求手寫(xiě)作答；答題紙上全部信息要求手寫(xiě)，包括學(xué)號(hào)、姓名等基本信息和答題內(nèi)容，請(qǐng)寫(xiě)明題型、題號(hào)；

三、提交方式：請(qǐng)將作答完成后的整頁(yè)答題紙以圖片形式依次粘貼在一個(gè)Word

    文檔中上傳（只粘貼部分內(nèi)容的圖片不給分），圖片請(qǐng)保持正向、清晰；

1. 完成的作業(yè)應(yīng)另存為保存類(lèi)型是“Word97-2003”提交;

2. 上傳文件命名為“中心-學(xué)號(hào)-姓名-科目.doc”;

3. 文件容量大?。翰坏贸^(guò)20MB。

提示：未按要求作答題目的作業(yè)及雷同作業(yè)，成績(jī)以0分記！

題目如下：

第一組：

一、編程題（每小題30分，共60分）

(一)

已知某哈希表的裝載因子小于1，哈希函數(shù)H(key)為關(guān)鍵字（標(biāo)識(shí)符）的第一個(gè)字母在字母表中的序號(hào)，處理沖突的方法為線性探測(cè)開(kāi)放定址法。試編寫(xiě)一個(gè)按第一個(gè)字母的順序輸出哈希表中所有關(guān)鍵字的算法。

(二)

用標(biāo)準(zhǔn)C語(yǔ)言實(shí)現(xiàn)Hanoi塔問(wèn)題

二、解答題（20分）

(一)

設(shè)待排序記錄的關(guān)鍵字序列為{46, 55, 13, 42, 94, 05, 17, 70}寫(xiě)出其第一趟快速排序過(guò)程。（要求寫(xiě)出每次交換后的序列，并且樞軸記錄到位也算一次交換）

初始關(guān)鍵字：  46   55   13   42   94   05   17   70

1次交換后：

2次交換后：

3次交換后：

4次交換后：

5次交換后：

三、畫(huà)圖題（20分）

(一)

將下面的森林變換成二叉樹(shù)

第二組：

一、編程題（每小題30分，共60分）

(一)

用標(biāo)準(zhǔn)C語(yǔ)言實(shí)現(xiàn)Hanoi塔問(wèn)題

(二)

1.設(shè)單鏈表中有僅三類(lèi)字符的數(shù)據(jù)元素(大寫(xiě)字母、數(shù)字和其它字符)，要求利用原單鏈表

中結(jié)點(diǎn)空間設(shè)計(jì)出三個(gè)單鏈表的算法，使每個(gè)單鏈表只包含同類(lèi)字符。

2. 設(shè)計(jì)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上交換二叉樹(shù)中所有結(jié)點(diǎn)左右子樹(shù)的算法。

二、解答題（20分）

(一)

已知一棵二叉樹(shù)的先序序列是ABCDEFGHIJK，中序序列是CDBGFEAHJIK，請(qǐng)構(gòu)造出該二叉樹(shù)。

三、畫(huà)圖題（20分）

(一)

設(shè)有序順序表中的元素依次為017, 094, 154, 170, 275,503, 509, 512, 553, 612, 677, 765, 897, 908。試畫(huà)出對(duì)其進(jìn)行折半搜索時(shí)的判定樹(shù), 并計(jì)算搜索成功的平均搜索長(zhǎng)度和搜索不成功的平均搜索長(zhǎng)度。

第三組：

一、編程題（每小題30分，共60分）

(一)

1.設(shè)單鏈表中有僅三類(lèi)字符的數(shù)據(jù)元素(大寫(xiě)字母、數(shù)字和其它字符)，要求利用原單鏈表

中結(jié)點(diǎn)空間設(shè)計(jì)出三個(gè)單鏈表的算法，使每個(gè)單鏈表只包含同類(lèi)字符。

2. 設(shè)計(jì)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上交換二叉樹(shù)中所有結(jié)點(diǎn)左右子樹(shù)的算法。

(二)

1.設(shè)有一組初始記錄關(guān)鍵字序列（K1，K2，?，Kn），要求設(shè)計(jì)一個(gè)算法能夠在O(n)的時(shí)間

復(fù)雜度內(nèi)將線性表劃分成兩部分，其中左半部分的每個(gè)關(guān)鍵字均小于Ki，右半部分的每個(gè)關(guān)鍵字均大于等于Ki。

2． 設(shè)有兩個(gè)集合A和集合B，要求設(shè)計(jì)生成集合C=A∩B的算法，其中集合A、B和C用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示。

二、解答題（20分）

(一)

若二叉樹(shù)中各結(jié)點(diǎn)的值均不相同，則由二叉樹(shù)的前序序列和中序序列，或由其后序序列和中序序列均能唯一地確定一棵二叉樹(shù)，但由前序序列和后序序列卻不一定能唯一地確定一棵二叉樹(shù)。

(1)已知一棵二叉樹(shù)的前序序列和中序序列分別為ABDGHCEFI和GDHBAECIF，請(qǐng)畫(huà)出此二叉樹(shù)。

(2)已知一棵二叉樹(shù)的在序序列和后序序列分別為BDCEAFHG和DECBHGFA，請(qǐng)畫(huà)出此二叉樹(shù)。

(3)已知一棵二叉樹(shù)的前序序列和后序序列分別為AB和BA，請(qǐng)畫(huà)出這兩棵不同的二叉樹(shù)。

三、畫(huà)圖題（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)識(shí)符）的第一個(gè)字母在字母表中的序號(hào)，處理沖突的方法為線性探測(cè)開(kāi)放定址法。試編寫(xiě)一個(gè)按第一個(gè)字母的順序輸出哈希表中所有關(guān)鍵字的算法。

(二) 設(shè)順序表L是一個(gè)遞增有序表，試寫(xiě)一算法，將x插入L中，并使L仍是一個(gè)有序表。

二、解答題（20分）

(一)

寫(xiě)出下圖所示的AOV網(wǎng)的可能拓?fù)湫蛄?，要求至少?xiě)出五個(gè)

三、畫(huà)圖題（20分）

(一)

設(shè)有序順序表中的元素依次為017, 094, 154, 170, 275,503, 509, 512, 553, 612, 677, 765, 897, 908。試畫(huà)出對(duì)其進(jìn)行折半搜索時(shí)的判定樹(shù), 并計(jì)算搜索成功的平均搜索長(zhǎng)度和搜索不成功的平均搜索長(zhǎng)度。

第五組：

一、編程題（每小題30分，共60分）

(一)

對(duì)于二維整數(shù)數(shù)組A[m][n]，對(duì)下列三種情況，分別編寫(xiě)相應(yīng)的函數(shù)。

1. 求數(shù)組所有邊緣元素的數(shù)值和。

int sum1(int A[M][N],int m ,int n)

{

2.求從A[0][0]開(kāi)始的互不相鄰的所有元素的和

注：一個(gè)元素的八個(gè)方向上的第一個(gè)元素均為相鄰元素。

int sum2 (int A[M][N] , int m , int n)

{

3. 假定m=n，并為偶數(shù)，請(qǐng)分別計(jì)算正、反兩條對(duì)角線上的元素值之和。

int sum3(int A[M][N] , int n)

{

(二)

已知某哈希表的裝載因子小于1，哈希函數(shù)H(key)為關(guān)鍵字（標(biāo)識(shí)符）的第一個(gè)字母在字母表中的序號(hào)，處理沖突的方法為線性探測(cè)開(kāi)放定址法。試編寫(xiě)一個(gè)按第一個(gè)字母的順序輸出哈希表中所有關(guān)鍵字的算法。

二、解答題（20分）

(一)

設(shè)待排序記錄的關(guān)鍵字序列為{46, 55, 13, 42, 94, 05, 17, 70}寫(xiě)出其第一趟快速排序過(guò)程。（要求寫(xiě)出每次交換后的序列，并且樞軸記錄到位也算一次交換）

初始關(guān)鍵字：  46   55   13   42   94   05   17   70

1次交換后：

2次交換后：

3次交換后：

4次交換后：

5次交換后：

三、畫(huà)圖題（20分）

(一)

已知二維數(shù)組表示的圖的鄰接矩陣如下圖所示。試分別畫(huà)出自頂點(diǎn)1出發(fā)進(jìn)行遍歷所得的深度優(yōu)先生成樹(shù)和廣度優(yōu)先生成樹(shù)。