武漢大學(xué)計算機學(xué)院數(shù)據(jù)結(jié)構(gòu)06級試題(a)含答案(編輯修改稿)
2025-07-17 08:31 本頁面
【文章內(nèi)容簡介】 （2）含n個頂點的無向圖采用鄰接表存儲；（3）含n個頂點的有向圖采用鄰接矩陣存儲；（4）含n個頂點的有向圖采用鄰接表存儲。3. 將整數(shù)序列{4,5,7,2,1,3,6}中的數(shù)依次插入到一棵空的平衡二叉樹中，試構(gòu)造相應(yīng)的平衡二叉樹。（要求畫出每個元素插入過程，若需調(diào)整，還需給出調(diào)整后的結(jié)果，并指出是什么類型的調(diào)整，12分）4. 當(dāng)實現(xiàn)插入直接排序過程中，假設(shè)R[0..i1]為有序區(qū)，R[i..n1]為無序區(qū)，現(xiàn)要將R[i]插入到有序區(qū)中，可以用二分查找來確定R[i]在有序區(qū)中的可能插入位置，這樣做能否改善直接插入排序算法的時間復(fù)雜度?為什么?（8分）5. 簡述外排序的兩個階段。（4分）四、算法設(shè)計題（共30分）1. 設(shè)計一個算法delminnode(LinkList *amp。L)，在帶頭結(jié)點的單鏈表L中刪除所有結(jié)點值最小的結(jié)點（可能有多個結(jié)點值最小的結(jié)點）。（15分）2．假設(shè)二叉樹采用二叉鏈存儲結(jié)構(gòu)存儲，設(shè)計一個算法copy(BTNode *b,BTNode *amp。t)，由二叉樹b復(fù)制成另一棵二叉樹t。（15分）參 考 答 案一、單項選擇題（每小題2分，共20分）1. C 2. D 3. A 4. A 5. B 6. B 7. B 8. C 9. D 10. A二、填空題（每題2分，共10分）1. 存儲方法或存儲結(jié)構(gòu)。 2. 2(n1)。 3. 34. n(n1)/2。 5. 10,8,9,6,7,2,4,5,3,1。（序列不全對不給分）三、問答題（共40分）1. 答：二叉樹中度為1的結(jié)點個數(shù)只能是1或0。設(shè)n1=1，n=n0+n1+n2=n0+n
數(shù)學(xué)相關(guān)推薦
鄂ICP備17016276號-1