數(shù)據(jù)結(jié)構(gòu)天津大學(xué)網(wǎng)教離線作業(yè)考核試卷答案

1、數(shù)據(jù)結(jié)構(gòu)要求：一、獨(dú)立完成，下面已將五組題目列出，請按照學(xué)院平臺指定的做題組數(shù)作答，每人只答一組題目，多答無效，滿分100分；平臺查看做題組數(shù)操作：學(xué)生登錄學(xué)院平臺一系統(tǒng)登錄一學(xué)生登錄一課程考試一離線考核一離線考核課程查看一做題組數(shù),顯示的數(shù)字為此次離線考核所應(yīng)做哪一組題的標(biāo)識；例如：“做題組數(shù)”標(biāo)為1,代表學(xué)生應(yīng)作答“第一組”試題；二、答題步驟：1,使用A4紙打印學(xué)院指定答題紙(答題紙請?jiān)斠姼郊?；2.在答題紙上使用黑色本筆按題目要求手寫作答；答題紙上全部信息要求手寫，包括學(xué)號、姓名等基本信息和答題內(nèi)容，請寫明題型、題號；三、提交方式：請將作答完成后的整頁答題紙以圖片形式依次粘貼在一個(gè)Wor

2、dX檔中上傳(只粘貼部分內(nèi)容的圖片不給分),圖片請保持正向、清晰；1 .上傳文件命名為“中心-學(xué)號-姓名-科目.doc”2 .文件容量大?。翰坏贸^20MB提示：未按要求作答題目的作業(yè)及雷同作業(yè)，成績以0分記！題目如下：第一組：一、編程題(每小題30分，共60分)(一)對于二維整數(shù)數(shù)組Amn,對下列三種情況，分別編寫相應(yīng)的函數(shù)。1 .求數(shù)組所有邊緣元素的數(shù)值和。intsum1(intAMN,intm,intn)(2,求從A00開始的互不相鄰的所有元素的和注：一個(gè)元素的八個(gè)方向上的第一個(gè)元素均為相鄰元素。intsum2(intAMN,intm,intn)(3.假定m=n并為偶數(shù)，請分別計(jì)算正、反

3、兩條對角線上的元素值之和。intsum3(intAMN,intn)(（二）已知某哈希表的裝載因子小于1,哈希函數(shù)H（key）為關(guān)鍵字（標(biāo)識符）的第一個(gè)字母在字母表中的序號，處理沖突的方法為線性探測開放定址法。試編寫一個(gè)按第一個(gè)字母的順序輸出哈希表中所有關(guān)鍵字的算法。二、解答題（20分）（一）設(shè)待排序記錄的關(guān)鍵字序列為46,55,13,42,94,05,17,70）寫出其第一趟快速排序過程。（要求寫出每次交換后的序列，并且樞軸記錄到位也算一次交換）初始關(guān)鍵字：46551342940517701次交換后:2次交換后:3次交換后:4次交換后:5次交換后:三、畫圖題（20分）（一）已知二維數(shù)組表示的圖

4、的鄰接矩陣如下圖所示。試分別畫出自頂點(diǎn)1出發(fā)進(jìn)行遍歷所得的深度優(yōu)先生成樹和廣度優(yōu)先生成樹。第二組：一、編程題（每小題30分，共60分）（一）設(shè)順序表L是一個(gè)遞增有序表，試寫一算法，將x插入L中，并使L仍是一個(gè)有序表。（二）用標(biāo)準(zhǔn)C語后實(shí)現(xiàn)Hanoi塔問題二、解答題（20分）（一）對下面的帶權(quán)無向圖采用prim算法從頂點(diǎn)開始構(gòu)造最小生成樹。（寫出加入生成樹頂點(diǎn)集合S和選擇Edge的順序）S:頂點(diǎn)號Edge：（頂點(diǎn)，頂點(diǎn)，權(quán)值）(,)(,)(,)(,)(,)三、畫圖題（20分）（一）將給定的圖簡化為最小的生成樹，要求從頂點(diǎn)1出發(fā)。第三組:一、編程題（每小題30分，共60分）（1）1 .設(shè)單鏈表中有

5、僅三類字符的數(shù)據(jù)元素（大寫字母、數(shù)字和其它字符），要求利用原單鏈表中結(jié)點(diǎn)空間設(shè)計(jì)出三個(gè)單鏈表的算法，使每個(gè)單鏈表只包含同類字符。2 .設(shè)計(jì)在鏈?zhǔn)酱鎯Y(jié)構(gòu)上交換二叉樹中所有結(jié)點(diǎn)左右子樹的算法。（2）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=AAB的算法，其中集合A、B和C用鏈?zhǔn)酱鎯Y(jié)構(gòu)表示。二、解答題（20分）（一）若二叉樹中各結(jié)點(diǎn)的值均不相同，則由二叉樹的前序序列和中序序列，或由其后序序列和中序序

6、列均能唯一地確定一棵二叉樹，但由前序序列和后序序列卻不一定能唯一地確定一棵二叉樹。(1)已知一棵二叉樹的前序序列和中序序列分別為樹。(2)已知一棵二叉樹的在序序列和后序序列分別為(3)已知一棵二叉樹的前序序列和后序序列分別為ABDGHCE序口GDHBAECIF請畫出此二叉BDCEAFHGDECBHGFA!畫出此二叉樹。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分)(一)對于二維整數(shù)數(shù)

7、組Amn,對下列三種情況，分別編寫相應(yīng)的函數(shù)。1 .求數(shù)組所有邊緣元素的數(shù)值和。intsum1(intAMN,intm,intn)2 .求從A00開始的互不相鄰的所有元素的和注：一個(gè)元素的八個(gè)方向上的第一個(gè)元素均為相鄰元素。intsum2(intAMN,intm,intn)3 .假定m=n并為偶數(shù)，請分別計(jì)算正、反兩條對角線上的元素值之和。intsum3(intAMN,intn)（二）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

8、和集合B,要求設(shè)計(jì)生成集合C=AAB的算法，其中集合A、B和C用式存儲結(jié)構(gòu)表示。二、解答題（20分）（一）寫出下圖所示的AO颯的可能拓?fù)湫蛄?，要求至少寫出五個(gè)三、畫圖題（20分）（一）將給定的圖簡化為最小的生成樹，要求從頂點(diǎn)1出發(fā)。第五組:一、編程題（每小題30分，共60分）（1）用標(biāo)準(zhǔn)C語言實(shí)現(xiàn)Hanoi塔問題（2）1 .設(shè)單鏈表中有僅三類字符的數(shù)據(jù)元素（大寫字母、數(shù)字和其它字符），要求利用原單鏈表中結(jié)點(diǎn)空間設(shè)計(jì)出三個(gè)單鏈表的算法，使每個(gè)單鏈表只包含同類字符。2 .設(shè)計(jì)在鏈?zhǔn)酱鎯Y(jié)構(gòu)上交換二叉樹中所有結(jié)點(diǎn)左右子樹的算法。二、解答題（20分）（一）已知一棵二叉樹的先序序列是ABCDEFGHIJm序序列是CDBGFEAHJIK青構(gòu)造出該二叉樹。