天大數(shù)據(jù)結(jié)構(gòu)2017年12月考試期末大作業(yè)

內(nèi)療得手網(wǎng)謀學(xué)網(wǎng)www.mouxue.c.om數(shù)據(jù)結(jié)構(gòu)要求：一、 獨(dú)立完成，下面五組題目中，請(qǐng)任選其中一組題目作答，滿分100分；二、答題步驟：.使用A4紙打印學(xué)院指定答題紙（答題紙請(qǐng)?jiān)斠姼郊?在答題紙上使用黑色水筆按題目要求手寫作答;答題紙上全部信息要求手???? ??寫，包括中心、學(xué)號(hào)、姓名、科目、答題組數(shù)等基本信息和答題內(nèi)容，請(qǐng)寫明題型、題號(hào)；三、提交方式：請(qǐng)將作答完成后的整頁答題紙以圖片形式依次粘貼在一個(gè)Word???????????文檔中上傳（只粘貼部分內(nèi)容的圖片不給分），圖片請(qǐng)保持正向、清晰；???.上傳文件命名為“中心-學(xué)號(hào)-姓名-科目"。。”.文件容量大?。翰坏贸^20MB。提示：未按要求作答題目的作業(yè)及雷同作業(yè)，成績(jī)以0分記！題目如下：第一組：一、編程題（每小題30分，共60分）（一）對(duì)于二維整數(shù)數(shù)組A[m][n],對(duì)下列三種情況，分別編寫相應(yīng)的函數(shù)。.求數(shù)組所有邊緣元素的數(shù)值和。intsum1（intA[M][N],intm,intn）{.求從A[0][0]開始的互不相鄰的所有元素的和注：一個(gè)元素的八個(gè)方向上的第一個(gè)元素均為相鄰元素。intsum2（intA[M][N],intm,intn）{.假定m=n，并為偶數(shù)，請(qǐng)分別計(jì)算正、反兩條對(duì)角線上的元素值之和。intsum3（intA[M][N],intn）{已知某哈希表的裝載因子小于1,哈希函數(shù)H（key）為關(guān)鍵字（標(biāo)識(shí)符）的第一個(gè)字母在字母移謀學(xué)網(wǎng)謀"n?L"F「輔'：St? 謀學(xué)網(wǎng)表中的序號(hào)，處理沖突的方法為線性探測(cè)開放定址法。試編寫一個(gè)按第一個(gè)字母的順序輸出哈希表中所有關(guān)鍵字的算法。二、解答題（20分）（一）設(shè)待排序記錄的關(guān)鍵字序列為｛46,55,13,42,94,05,17,70寫出其第一趟快速排序過程。（要求寫出每次交換后的序列，并且樞軸記錄到位也算一次交換）初始關(guān)鍵字：46 55 13 42 94 05 17 701次交換后：2次交換后：3次交換后：4次交換后：5次交換后：三、畫圖題（20分）（一）已知二維數(shù)組表示的圖的鄰接矩陣如下圖所示。試分別畫出自頂點(diǎn)1出發(fā)進(jìn)行遍歷所得的深度優(yōu)先生成樹和廣度優(yōu)先生成樹。第二組：一、編程題（每小題30分，共60分）（一）設(shè)順序表L是一個(gè)遞增有序表，試寫一算法，將x插入1中，并使L仍是一個(gè)有序表。助得學(xué)網(wǎng)謀學(xué)網(wǎng)www.mouxue.c.om（二）用標(biāo)準(zhǔn)C語言實(shí)現(xiàn)Hanoi塔問題二、解答題（20分）（一）對(duì)下面的帶權(quán)無向圖采用prim算法從頂點(diǎn)①開始構(gòu)造最小生成樹。（寫出加入生成樹頂點(diǎn)集合S和選擇Edge的順序）S：頂點(diǎn)號(hào)Edge：（頂點(diǎn)，頂點(diǎn)，權(quán)值）①（，，）①（，，）①（，，）①（，，）①（，，）①三、畫圖題（20分）（一）南港學(xué)網(wǎng)謀學(xué)網(wǎng)www.mouxue.c.om第三組：一、編程題（每小題30分，共60分）（一）.設(shè)單鏈表中有僅三類字符的數(shù)據(jù)元素（大寫字母、數(shù)字和其它字符），要求利用原單鏈表中結(jié)點(diǎn)空間設(shè)計(jì)出三個(gè)單鏈表的算法，使每個(gè)單鏈表只包含同類字符。.設(shè)計(jì)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上交換二叉樹中所有結(jié)點(diǎn)左右子樹的算法。（二）.設(shè)有一組初始記錄關(guān)鍵字序列（K1，K2，?，Kn）,要求設(shè)計(jì)一個(gè)算法能夠在O（n）的時(shí)間復(fù)雜度內(nèi)將線性表劃分成兩部分，其中左半部分的每個(gè)關(guān)鍵字均小于Ki,右半部分的每個(gè)關(guān)鍵字均大于等于Ki。. 設(shè)有兩個(gè)集合A和集合B,要求設(shè)計(jì)生成集合C=AHB的算法，其中集合A、B和C用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示。二、解答題（20分）（一）明謀學(xué)網(wǎng)*"一"謀處1'燉＜：,社" 謀學(xué)網(wǎng)www.mouxue.c.om若二叉樹中各結(jié)點(diǎn)的值均不相同，則由二叉樹的前序序列和中序序列，或由其后序序列和中序序列均能唯一地確定一棵二叉樹，但由前序序列和后序序列卻不一定能唯一地確定一棵二叉樹。(1)已知一棵二叉樹的前序序列和中序序列分別為ABDGHCEFI和GDHBAECIF，請(qǐng)畫出此二叉樹。(2)已知一棵二叉樹的在序序列和后序序列分別為BDCEAFHG和DECBHGFA，請(qǐng)畫出此二叉樹。(3)已知一棵二叉樹的前序序列和后序序列分別為AB和BA，請(qǐng)畫出這兩棵不同的二叉樹。三、畫圖題(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分)(一)對(duì)于二維整數(shù)數(shù)組A[m][n]，對(duì)下列三種情況，分別編寫相應(yīng)的函數(shù)。.求數(shù)組所有邊緣元素的數(shù)值和。intsum1(intA[M][N],intm,intn){.求從A[0][0]開始的互不相鄰的所有元素的和

物]臬字網(wǎng)謀學(xué)網(wǎng)www.mouxue.c.om專能遠(yuǎn)健*謀學(xué)網(wǎng)www.mouxue.c.om注：一個(gè)元素的八個(gè)方向上的第一個(gè)元素均為相鄰元素。intsum2（intA[M][N],intm,intn）{.假定m=n，并為偶數(shù)，請(qǐng)分別計(jì)算正、反兩條對(duì)角線上的元素值之和。intsum3（intA[M][N],intn）{1.設(shè)有一組初始記錄關(guān)鍵字序列（K1,K2,，，，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=AHB的算法，其中集合A、B和C用式存儲(chǔ)結(jié)構(gòu)表示。二、解答題（20分）（一）寫出下圖所示的AOV網(wǎng)的可能拓?fù)湫蛄?，要求至少寫出五個(gè)三、畫圖題（20分）（一）內(nèi)浮港學(xué)網(wǎng)■V.ww*.圖由lihijZ上白版謀學(xué)網(wǎng)www.mouxue.c.om第五組：一、編程題（每小題30分，共60分）（一）用標(biāo)準(zhǔn)C語言實(shí)現(xiàn)Hanoi塔問題.設(shè)單鏈表中有僅三類字符的數(shù)據(jù)元素（大寫字母、數(shù)字和其它字符），要求利用原單鏈表中結(jié)點(diǎn)空間設(shè)計(jì)出三個(gè)單鏈表的算法，使每個(gè)單鏈表只包含同類字符。.設(shè)計(jì)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上交換二叉樹中所有結(jié)點(diǎn)左右子樹的算法。二、解答題（20分）（一）已知一棵二叉樹的先序序列是ABCDEFGHIJK，中序序列是CDBGFEAHJIK，請(qǐng)構(gòu)造出該二叉樹。三