版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)
文檔簡介
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分)【解答】出局人的順序?yàn)?17436928。二、列出右圖所示二叉樹的葉結(jié)點(diǎn)、分支結(jié)點(diǎn)和每個結(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。三.線性表可用順序表或鏈表存儲。試問:(9分)(1)兩種存儲表示各有哪些主要優(yōu)
3、缺點(diǎn)(3分)(2)如果有n個表同時并存,并且在處理過程中各表的長度會動態(tài)發(fā)生變化,表的總數(shù)也可能自動改變、在此情況下,應(yīng)選用哪種存儲表示?為什么?(3分)(3)若表的總數(shù)基本穩(wěn)定,且很少進(jìn)行插入和刪除,但要求以最快的速度存取表中的元素,這時,應(yīng)采用哪種存儲表示?為什么?(3分)【解答】(1)順序存儲表示是將數(shù)據(jù)元素存放于一個連續(xù)的存儲空間中,實(shí)現(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é)點(diǎn)的二叉樹。七、已知一棵二叉樹的前序遍歷的結(jié)果是ABECDFGHIJ中序遍歷的結(jié)果是EBCDAFHIGJ試畫出這棵二叉樹。(9分)【解答】當(dāng)前序序列為ABECDFGHIJ,中序序列為EBCDAFHIGJ時,逐步形成二叉樹的過程如下圖所示
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 《數(shù)據(jù)結(jié)構(gòu)》課期末考試
- 數(shù)據(jù)結(jié)構(gòu)期末考試題及答案
- 數(shù)據(jù)結(jié)構(gòu) 期末考試試卷
- 數(shù)據(jù)結(jié)構(gòu)期末考試試題及答案
- 數(shù)據(jù)結(jié)構(gòu)期末考試試題及答案
- 大學(xué)數(shù)據(jù)結(jié)構(gòu)期末考試試題有答案
- 大學(xué)數(shù)據(jù)結(jié)構(gòu)期末考試試題(有答案)
- 2017《數(shù)據(jù)結(jié)構(gòu)》期末考試試題及答案
- 藝術(shù)導(dǎo)論2017期末考試答案
- 魅力科學(xué)2017期末考試答案
- 數(shù)據(jù)結(jié)構(gòu)與算法期末考試復(fù)習(xí)試題
- 高二期末考試地理答案
- 2022期末考試試卷及答案
- 2022期末考試試卷及答案
- 2017年數(shù)據(jù)結(jié)構(gòu)期末考試題及答案a
- 2015年數(shù)據(jù)結(jié)構(gòu)期末考試題及答案
- 商法總論2014期末考試答案要點(diǎn)
- 2022期末考試試卷
- 從愚昧到科學(xué)2015期末考試答案
- 西方哲學(xué)智慧,2016期末考試答案
評論
0/150
提交評論