數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)-鐵宇彤完整版 v.0.1

1、考試題型選擇題：21分填空題：18分判斷題：15分圖表題：26分算法題：20分1.什么是圖的鄰接矩陣表示法？什么是圖的鄰接表表示法？在這兩種存儲(chǔ)結(jié)構(gòu)上如何計(jì)算頂點(diǎn)的度？鄰接矩陣鄰接矩陣一個(gè)有n個(gè)頂點(diǎn)的圖G=(VE)的鄰接矩陣是一個(gè)n?n的矩陣A，A的每個(gè)元素是0或1。設(shè)V=012……n1如果G是無(wú)向圖無(wú)向圖，則A的元素定義為：1(uv)?EA(uv)=0其他如果G是有向圖有向圖，則A的元素定義為：1?EA(uv)=0其他如果G是帶權(quán)的圖

2、帶權(quán)的圖，則鄰接矩陣中值為1的元素應(yīng)替換為權(quán)值，有時(shí)需要將0替換為?。(詳見(jiàn)PPTunit712021)鄰接表鄰接表否則后序遍歷左子樹；后序遍歷右子樹；訪問(wèn)根結(jié)點(diǎn)。(詳見(jiàn)PPTunit412122)4.什么是二叉搜索樹和AVL樹？有何性質(zhì)？如何進(jìn)行插入和查找的操作？二叉搜索樹二叉搜索樹（binarysearchtree）也稱二叉排序樹（binarysttree）。二叉搜索樹或者是一棵空二叉樹，或者是具有下列性質(zhì)的二叉樹：（1）每個(gè)結(jié)點(diǎn)由

3、關(guān)鍵字值表征，所有結(jié)點(diǎn)的關(guān)鍵字值各不相同；（2）若左子樹不空，則左子樹上所有結(jié)點(diǎn)的關(guān)鍵字值均小于根結(jié)點(diǎn)的關(guān)鍵字值；（3）若右子樹不空，則右子樹上所有結(jié)點(diǎn)的關(guān)鍵字值均大于根結(jié)點(diǎn)的關(guān)鍵字值；（4）左、右子樹也分別是二叉搜索樹。(詳見(jiàn)PPTunit5122)二叉搜索樹的搜索二叉搜索樹的搜索算法搜索算法思路是：若二叉樹為空，則搜索失敗。否則，將k與根的關(guān)鍵字值比較，若k小于該關(guān)鍵字值，則用同樣的方法搜索左子樹，而不必搜索右子樹若k大于該關(guān)鍵字值

4、，則用同樣的方法搜索右子樹，而不必搜索左子樹若k等于該關(guān)鍵字值，則搜索成功終止。二叉搜索樹的插入算法二叉搜索樹的插入算法插入算法思路是：(1)確定新元素的插入位置。搜索插入位置的方法與Search函數(shù)的做法類似，但要求在從根結(jié)點(diǎn)往下搜索過(guò)程中，用指針q記錄下當(dāng)前元素的雙親結(jié)點(diǎn)。如果在搜索中，遇到相同關(guān)鍵字值的元素，則表明有重復(fù)元素，那么顯示Duplicate信息。(2)插入新元素如果二叉搜索樹是空樹，則新元素e成為樹根。如果e的關(guān)鍵字值

5、小于q結(jié)點(diǎn)的值，則將新元素e作為q的左孩子，否則作為其右孩子。AVL樹：一棵AVL樹或者是空樹，或者是具有下列性質(zhì)的二叉搜索樹：它的左子樹和右子樹都是AVL樹，且左子樹和右子樹的高度之差的絕對(duì)值不超過(guò)1。（每個(gè)結(jié)點(diǎn)附加一個(gè)數(shù)字，給出該結(jié)點(diǎn)右子樹的高度減去左子樹的高度所得的高度差。這個(gè)數(shù)字即為結(jié)點(diǎn)的平衡因子平衡因子balance。）(詳見(jiàn)PPTunit524)AVL樹的插入樹的插入（詳見(jiàn)PPTunit52）在向一棵本來(lái)是高度平衡的AVL樹