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

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

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

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

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

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