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