數(shù)據(jù)結(jié)構(gòu)導(dǎo)論串講筆記(編輯修改稿)
2025-07-19 14:18 本頁面
【文章內(nèi)容簡介】 面的那些結(jié)點(diǎn)為根結(jié)點(diǎn)的左子樹上的結(jié)點(diǎn)，根結(jié)點(diǎn)后面的那些結(jié)點(diǎn)為根結(jié)點(diǎn)的右子樹上的結(jié)點(diǎn)）。恢復(fù)該二叉樹的任何一棵子樹的過程仍然遵循這個原則。【解答】二叉樹如下圖所示BCDAKGHFE3）給出一棵二叉樹的后根遍歷和中根遍歷序列，恢復(fù)二叉樹，寫出先根遍歷的序列。（未考過，但可能考注意第四章的考核知識點(diǎn)的講解）5．樹的存儲結(jié)構(gòu)1）給出一棵樹，畫出該樹的雙親表示法、孩子鏈表表示法、帶雙親的孩子鏈表表示法及孩子兄弟鏈表表示法的示意圖。（[2000/4]考過）2）給出一棵樹的某一種存儲結(jié)構(gòu)的示意圖，畫出對應(yīng)的樹。（未考過）6．樹的遍歷給出一棵樹，寫出對該樹進(jìn)行先根遍歷、后根遍歷及層次遍歷的序列。（未考過）7．二叉樹與樹、林的相互轉(zhuǎn)換1）將一棵二叉樹轉(zhuǎn)換為樹。（未考過）2）將一棵樹轉(zhuǎn)換為二叉樹。（未考過）3）將林轉(zhuǎn)換為一棵二叉樹。（未考過）4）將二叉樹轉(zhuǎn)換為林。（未考過）8．夠造哈夫曼樹給出一組權(quán)值，構(gòu)造一棵哈夫曼樹并求帶權(quán)路徑長度。（未考過）9．圖的存儲結(jié)構(gòu)1）給出一個圖，畫出該圖的鄰接矩陣或鄰接表存儲示意圖。（考過）[2005/10]試給出下圖的鄰接矩陣和鄰接表表示。【分析】鄰接矩陣存儲方法是用一個二維數(shù)組存放頂點(diǎn)之間關(guān)系的信息。對于不帶權(quán)的有向圖，如果一個頂點(diǎn)到另一個頂點(diǎn)有邊，用1表示；否則，用0表示；對于帶權(quán)的有圖，如果一個頂點(diǎn)到另一個頂點(diǎn)有邊，用邊的權(quán)值表示；否則，用∞表示。 鄰接表存儲方法的核心思想是對于具有n個頂點(diǎn)的圖建立n個線性鏈表。每一個鏈表最前面都分別設(shè)置一個稱之為表頭結(jié)點(diǎn)的結(jié)點(diǎn)，n個結(jié)點(diǎn)構(gòu)成一個數(shù)組結(jié)構(gòu)。第i個鏈表中的每一個鏈結(jié)點(diǎn)稱之為表結(jié)點(diǎn)。對帶權(quán)的圖，其鄰接表中的每個表結(jié)點(diǎn)都要增加一個權(quán)值域?！窘獯稹款}中圖的鄰接矩陣為：V1V2V3V4V5V1 V2 V3 V4 V5題中圖的鄰接表為：
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號-1