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

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

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

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

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

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

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