數(shù)據(jù)結(jié)構(gòu)03-04期末考試b答案

1、四川大學(xué)期末考試題四川大學(xué)期末考試題解答解答(20032004學(xué)年第二學(xué)期)課程名:數(shù)據(jù)結(jié)構(gòu)(B)計算機(jī)科學(xué)與技術(shù)專業(yè)適用人數(shù):學(xué)院:專業(yè):教師姓名:姓名:學(xué)號:成績:一、設(shè)n個人圍坐在一個圓桌周圍，現(xiàn)在從第s個人開始報數(shù)，數(shù)到第m個人，讓他出局；然后從出局的下一個人重新開始報數(shù)，數(shù)到第m個人，再讓他出局，……，如此反復(fù)直到所有的人全部出局為止。下面要解決的Josephus問題是：對于任意給定的ns和m，求出這n個人的出局序列。請以n=

2、9s=1m=5為例，人工模擬Josephus的求解過程以求得問題的解。（9分）【解答】出局人的順序為517436928。二、列出右圖所示二叉樹的葉結(jié)點、分支結(jié)點和每個結(jié)點的層次。（9分）【解答】二叉樹的葉結(jié)點有⑥、⑧、⑨。分支結(jié)點有①、②、③、④、⑤、⑦。結(jié)點①的層次為0；結(jié)點②、③的層次為1；結(jié)點④、⑤、⑥的層次為2；結(jié)點⑦、⑧的層次為3；結(jié)點⑨的層次為4。三.線性表可用順序表或鏈表存儲。試問：（9分）(1)兩種存儲表示各有哪些主要優(yōu)

3、缺點（3分）(2)如果有n個表同時并存，并且在處理過程中各表的長度會動態(tài)發(fā)生變化，表的總數(shù)也可能自動改變、在此情況下，應(yīng)選用哪種存儲表示？為什么？（3分）(3)若表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除，但要求以最快的速度存取表中的元素，這時，應(yīng)采用哪種存儲表示？為什么？（3分）【解答】(1)順序存儲表示是將數(shù)據(jù)元素存放于一個連續(xù)的存儲空間中，實現(xiàn)順序存取或(按下標(biāo))直接存取。它的存儲效率高，存取速度快。但它的空間大小一經(jīng)定義，在程序整個

4、運(yùn)行期間不會發(fā)生改變，因此，不易擴(kuò)充。同時，由于在插入或刪除時，為保持原有次序，平均需要移動一半(或近一半)元素，修改效率不高。鏈接存儲表示的存儲空間一般在程序的運(yùn)行過程中動態(tài)分配和釋放，且只要存儲器中還有空間，就不會產(chǎn)生存儲溢出的問題。同時在插入和刪除時不需要保持?jǐn)?shù)據(jù)元素原來的物理順序，只需要保持原來的邏輯順序，因此不必移動數(shù)據(jù)，只需修改它們的鏈接指針，修改效率較高。但存取表中的數(shù)據(jù)元素時，只能循鏈順序訪問，因此存取效率不高。(2)如

5、果有n個表同時并存，并且在處理過程中各表的長度會動態(tài)發(fā)生變化，表的總數(shù)也可能自動改變、在此情況下，應(yīng)選用鏈接存儲表示。如果采用順序存儲表示，必須在一個連續(xù)的可用空間中為這n個表分配空間。初始時因不知道哪個表增長得快，必須平均分配空間。在程序運(yùn)行過程中，有的表占用的空間增【解答】六、試分別找出滿足以下條件的所有二叉樹:（9分）(1)二叉樹的前序序列與中序序列相同(3分)(2)二叉樹的中序序列與后序序列相同（3分）(3)二叉樹的前序序列與后

6、序序列相同。（3分）【解答】(1)二叉樹的前序序列與中序序列相同：空樹或缺左子樹的單支樹；(2)二叉樹的中序序列與后序序列相同：空樹或缺右子樹的單支樹；(3)二叉樹的前序序列與后序序列相同：空樹或只有根結(jié)點的二叉樹。七、已知一棵二叉樹的前序遍歷的結(jié)果是ABECDFGHIJ中序遍歷的結(jié)果是EBCDAFHIGJ試畫出這棵二叉樹。（9分）【解答】當(dāng)前序序列為ABECDFGHIJ，中序序列為EBCDAFHIGJ時，逐步形成二叉樹的過程如下圖所示