數(shù)據(jù)結(jié)構(gòu)(僅供參考)(共15頁).docx
《數(shù)據(jù)結(jié)構(gòu)(僅供參考)(共15頁).docx》由會(huì)員分享,可在線閱讀,更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)(僅供參考)(共15頁).docx(15頁珍藏版)》請(qǐng)?jiān)趨R文網(wǎng)上搜索。
1、精選優(yōu)質(zhì)文檔-傾情為你奉上PS(邊看書邊做的,一年了忘記的差不多了,答案僅供參考不喜勿噴)1. 有函數(shù)段,分析其時(shí)間復(fù)雜度。根據(jù)公式:T(n)=O(f(n))可以得出:常數(shù)階O(1),對(duì)數(shù)階O(log2n),線性階O(n),線性對(duì)數(shù)階O(nlog2n),平方階O(n2),立方階O(n3),.,k次方階O(nk),指數(shù)階O(2n)由此可見,隨著問題規(guī)模的n不斷增大,時(shí)間復(fù)雜度也不斷增加,因此算法的執(zhí)行效率越低2. 試證二叉樹的性質(zhì)1及2.性質(zhì)1:在二叉樹的第i層上之多有2(i-1)個(gè)結(jié)點(diǎn)(i>=1)當(dāng)i=1,時(shí),只有一個(gè)節(jié)點(diǎn)為根結(jié)點(diǎn),所以正確。當(dāng)i>=1時(shí),每一層每個(gè)結(jié)點(diǎn)至多只有2個(gè)
2、度及i層上至有2(i-1)個(gè)結(jié)點(diǎn),所以 i上的結(jié)點(diǎn)數(shù)為i-1上的兩倍 。i-1上的結(jié)點(diǎn)為2(i-2)所以2*2(i-2)= 2(i-1)所以性質(zhì)1正確性質(zhì)2:深度為K的二叉樹之多有2(k-1)個(gè)結(jié)點(diǎn)P123公式個(gè)人理解性質(zhì)2跟性質(zhì)1其實(shí)差不多,就是把性質(zhì)1中的i=(0,1k)然后求和。3 棧和隊(duì)列的共同點(diǎn)和不同點(diǎn)。共同點(diǎn):都是只能在線性表的端點(diǎn)插入和刪除不同點(diǎn):棧的插入和刪除都在線性表的同一個(gè)端點(diǎn),該點(diǎn)通稱棧頂,相應(yīng)地,不能插入刪除的另一個(gè)端點(diǎn)通稱棧底,其特性是后進(jìn)先出 隊(duì)列在線性表的表頭插入,表尾刪除,表頭一般稱隊(duì)頭,表尾一般稱隊(duì)尾,其特性是先進(jìn)先出(記住加粗部分就行)4 在雙鏈表中插入(刪
3、除)指針p指的結(jié)點(diǎn)的關(guān)鍵語句。q->next = p->next;/刪除的結(jié)點(diǎn)的后一結(jié)點(diǎn)的首地址賦值給刪除的結(jié)點(diǎn)的前一結(jié)點(diǎn)的nextp->next->prior = q;/刪除的結(jié)點(diǎn)的后一結(jié)點(diǎn)的prior指向刪除的結(jié)點(diǎn)的前一結(jié)點(diǎn)的首地址free(p);5 一棵二叉樹的結(jié)點(diǎn)數(shù)據(jù)采用順序存儲(chǔ),如下圖所示,試用二叉鏈表表示它。ABC0D0E00FJ00P6某二叉樹結(jié)點(diǎn)的先根序列和中根序列為已知,試構(gòu)造該樹。(自行舉例)先序遍歷是先訪問當(dāng)前節(jié)點(diǎn),然后再遍歷左子樹,最后是右子樹。中序遍歷是先遍歷左子樹,再訪問當(dāng)前節(jié)點(diǎn),最后是右子樹。P.1297 某帶權(quán)無向圖的鄰接矩陣已知(自行舉
4、例),試畫出該圖,并用Prim或者Kruskal算法構(gòu)造出該圖的一棵最小生成樹的步驟。8 下面是某文件中各字母頻度表(自行舉例)。(1)構(gòu)造其Huffman樹(2)求得各字母的Huffman編碼。 P1469算法設(shè)計(jì)利用棧實(shí)現(xiàn)將十進(jìn)制數(shù)轉(zhuǎn)變成7進(jìn)制數(shù)。略10算法設(shè)計(jì):設(shè)一棵二叉樹以二叉鏈表為存儲(chǔ)結(jié)構(gòu),結(jié)點(diǎn)結(jié)構(gòu)為lchilddatarchild若data為整數(shù),求此二叉樹中data值最大的結(jié)點(diǎn)。略。11從數(shù)據(jù)的邏輯結(jié)構(gòu)來看,可分為線性結(jié)構(gòu)(如線性表)和非線性結(jié)構(gòu)兩大類,棧和圖分別屬于哪類?棧是線性結(jié)構(gòu)。圖是非線性結(jié)構(gòu)。12 樹中,沒有后繼結(jié)點(diǎn)的結(jié)點(diǎn)稱為什么結(jié)點(diǎn),有向圖中,頂點(diǎn)的度是?沒有后繼結(jié)點(diǎn)
- 1.請(qǐng)仔細(xì)閱讀文檔,確保文檔完整性,對(duì)于不預(yù)覽、不比對(duì)內(nèi)容而直接下載帶來的問題本站不予受理。
- 2.下載的文檔,不會(huì)出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入(下載+內(nèi)容+預(yù)覽)歸上傳者、原創(chuàng)作者;如果您是本文檔原作者,請(qǐng)點(diǎn)此認(rèn)領(lǐng)!既往收益都?xì)w您。
下載文檔到電腦,查找使用更方便
20 積分
下載 | 加入VIP,下載共享資源 |
- 配套講稿:
如PPT文件的首頁顯示word圖標(biāo),表示該P(yáng)PT已包含配套word講稿。雙擊word圖標(biāo)可打開word文檔。
- 特殊限制:
部分文檔作品中含有的國旗、國徽等圖片,僅作為作品整體效果示例展示,禁止商用。設(shè)計(jì)者僅對(duì)作品中獨(dú)創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞:
- 數(shù)據(jù)結(jié)構(gòu) 僅供參考 15