數(shù)據(jù)結(jié)構(gòu)第4次作業(yè)

1、數(shù)據(jù)結(jié)構(gòu)第4次作業(yè)主觀題(共50道小題)60.循環(huán)隊(duì)列的引入，目的是為了克服順序隊(duì)列的假溢出 。61.區(qū)分循環(huán)隊(duì)列的空與滿有3種方法，它們是少用一個(gè)元素、設(shè)空滿標(biāo)志 、用計(jì)數(shù)器記錄隊(duì)列中元素個(gè)數(shù) 。62.棧和隊(duì)列的區(qū)別是 棧只能在表一端進(jìn)行插入和刪除操作，隊(duì)列限制在表的一端進(jìn)行插入操作，在另一端進(jìn)行刪除操作 。63.一個(gè)棧的輸入序列是12345，則棧的輸出序列43512是 錯(cuò)誤的 。64.設(shè)棧采取順序存儲結(jié)構(gòu)，棧中已有i-1個(gè)元素，則第i個(gè)元素進(jìn)棧操作的算法時(shí)間復(fù)雜度是 o（1） 。65.棧的特點(diǎn)是【后進(jìn)先出 】，隊(duì)列的特點(diǎn)是【先進(jìn)先出 】；棧和隊(duì)列都是【限制存取點(diǎn)的線性結(jié)構(gòu) 】若入棧序列是1

2、，2，3，4 ，則【3,2,1,4 】是不可能的出棧序列；若進(jìn)隊(duì)列的序列是1，2，3，4，則【1,2,3,4 】是可能的出隊(duì)序列。 66.若用不帶頭結(jié)點(diǎn)的單鏈表表示棧，則創(chuàng)建一個(gè)空棧要執(zhí)行的操作是top=null 。 67.從循環(huán)隊(duì)列中刪除一個(gè)元素的操作是 q.front=(q.front+1)%qsize 。68.從循環(huán)隊(duì)列中插入一個(gè)元素的操作是 q.rear=(q.rear+1)%qsize 。69.判斷鏈隊(duì)列中只有一個(gè)結(jié)點(diǎn)的條件是 q.front-next=q.rear 。70.如果棧的最大長度難以估計(jì)，最好使用鏈棧 。71.為什么說棧是一種后進(jìn)先出表？答：因?yàn)闂Ｊ窍薅ㄔ诒淼囊欢诉M(jìn)行插入

3、和刪除操作，所以后入棧的數(shù)據(jù)元素總是先出棧，所以說棧是一種后進(jìn)先出表。72.對于一個(gè)棧，其輸入序列是a,b,c,試給出全部可能的輸出序列。答：可能的出棧序列是：abc、acb、bac、bca、cba。 73.何謂隊(duì)列上溢？何為假溢出現(xiàn)象？有哪些解決假溢出問題的方法，并分別闡述其工作原理。答：隊(duì)列上溢指在隊(duì)列的順序存儲分配中，按照隊(duì)列的操作規(guī)則，需要進(jìn)隊(duì)的元素因找不到合適的存儲單元而無法進(jìn)入隊(duì)列。 假溢出指在隊(duì)列的順序存儲分配中，分配給隊(duì)列的存儲空間有存儲單元未被占用，但按照操作規(guī)則而使進(jìn)隊(duì)的數(shù)據(jù)元素?zé)o法進(jìn)隊(duì)的現(xiàn)象。 解決假溢出問題的方法是在隊(duì)列的順序存儲分配中，分配給隊(duì)列的存儲空間可以循環(huán)使用

4、，其進(jìn)本原理是用表示隊(duì)頭和隊(duì)尾指針與分配給隊(duì)列的存儲空間長度進(jìn)行取模運(yùn)算。即： 入隊(duì)操作：q.rear=(q.rear+1)%msize 出隊(duì)操作：q.front=(q.front+1)%msize 74.隊(duì)列可以用單循環(huán)鏈表來實(shí)現(xiàn)，故可以只設(shè)一個(gè)頭指針或只設(shè)一個(gè)尾指針，請分析用哪種方案最合適。答：使用循環(huán)鏈表來表示隊(duì)列，設(shè)置尾指針比較合適，因?yàn)槿腙?duì)操作可以直接在尾結(jié)點(diǎn)后進(jìn)行插入操作，出隊(duì)操作時(shí)可以根據(jù)尾指針很容易找到鏈表的頭結(jié)點(diǎn)，入隊(duì)出隊(duì)操作的算法時(shí)間復(fù)雜度均為o(1)。若只設(shè)頭指針，則出隊(duì)操作的算法時(shí)間復(fù)雜度為o(1)，入隊(duì)操作的算法時(shí)間復(fù)雜度為o(n)。 75.深度為k的完全二叉樹至少有

5、2k-1 個(gè)結(jié)點(diǎn)，至多有2k-1 個(gè)結(jié)點(diǎn)。76.在一棵二叉樹中，度為0的結(jié)點(diǎn)個(gè)數(shù)為n0，度為2的結(jié)點(diǎn)個(gè)數(shù)為n2,則有n0= n2+1 。 77.一棵二叉樹第i層最多有2i-1 個(gè)結(jié)點(diǎn)，一棵有n個(gè)結(jié)點(diǎn)的滿二叉樹共有 2k-1 個(gè)結(jié)點(diǎn)，共有2k-1 個(gè)葉結(jié)點(diǎn)。78.根據(jù)二叉樹的定義，具有3個(gè)結(jié)點(diǎn)的二叉樹共有 種不同形態(tài)，它們分別是5 。 79.有一棵如下圖所示的樹，回答下列問題： 這棵樹的根結(jié)點(diǎn)是 a 。這棵樹的葉子結(jié)點(diǎn)是 b,e,g,d 。結(jié)點(diǎn)c的度為 2 。這棵樹的深度是 4 。結(jié)點(diǎn)c的孩子結(jié)點(diǎn)是 e,f 。結(jié)點(diǎn)c的雙親結(jié)點(diǎn)是 a 。這棵樹的度是 3 。80.樹與二叉樹的兩個(gè)主要差別是 樹中結(jié)

6、點(diǎn)的最大度沒有限制，二叉樹結(jié)點(diǎn)的最大度限定為2 、 樹的結(jié)點(diǎn)無左右之分，二叉樹的的節(jié)點(diǎn)又左右之分 。81.設(shè)有如下圖所示的二叉樹，給出其前序、中序和后序遍歷結(jié)果。 答：前序序列：eadcbifghj中序序列：abcdiefhgj后序序列：bcidahjgfe82.給出下圖所示的樹的二叉樹表示。 答：下圖為其樹的二叉樹表示。83.有一份電文共有5個(gè)字符：a,b,c,d,e,它們出現(xiàn)的頻率依次為4，7，5，2，9，構(gòu)造對應(yīng)的哈夫曼樹，求哈夫曼樹的帶權(quán)路徑長度和每個(gè)字符的哈夫曼編碼。答： 字符編碼： a：011 b：10 c：00 d：010 e：1184. 假設(shè)一棵二叉樹采用順序存儲結(jié)構(gòu)，如下圖所

7、示。 0 5 10 15 20 e a f d g c j h i b 回答些列問題： 畫出二叉樹表示。 寫出先序、中序和后序遍歷結(jié)果 寫出結(jié)點(diǎn)c的雙親結(jié)點(diǎn)和左、右孩子結(jié)點(diǎn) 畫出此二叉樹還原成森林的圖 答：二叉樹表示如下圖所示。先序序列為：eadcbjfghi 中序序列為：acbdjefhgi 后序序列為：bcjdahigfe結(jié)點(diǎn)c的雙親結(jié)點(diǎn)是d，左孩子為b，無右孩子該二叉樹對應(yīng)的森林為 85.有n個(gè)頂點(diǎn)的無向圖最多有n(n-1)/2 條邊。86.一個(gè)圖的 鄰接矩陣 表示法是唯一的，而鄰接表 表示法是不唯一的。87.具有10個(gè)頂點(diǎn)的無向圖，邊的總數(shù)最多為 45 。88.在有n個(gè)頂點(diǎn)的有向圖中，

8、每個(gè)頂點(diǎn)的度最大可達(dá) 2(n-1) 。89.已知一個(gè)有向圖采用鄰接矩陣表示，計(jì)算第i個(gè)頂點(diǎn)的入度的方法是 求第i列非0元素個(gè)數(shù) 。90.從占用的存儲空間來看，對于稠密圖和稀疏圖，采用鄰接矩陣和鄰接表那個(gè)更好些？答：從占用存儲空間看，稠密圖采用鄰接矩陣更好，稀疏圖采用鄰接表更好。91.用鄰接矩陣表示圖時(shí)，矩陣元素的個(gè)數(shù)與頂點(diǎn)個(gè)數(shù)是否相關(guān)？與邊的條數(shù)是否相關(guān)？為什么？。答：用鄰接矩陣表示圖，矩陣元素的個(gè)數(shù)與圖的定點(diǎn)個(gè)數(shù)直接相關(guān)，與邊的條數(shù)無關(guān)。因?yàn)榧僭O(shè)定點(diǎn)個(gè)數(shù)為n，則鄰接矩陣的大小為n2。92.對于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無向圖，若采用鄰接表表示，則表頭向量的大小為【 】；所有鄰接表中結(jié)點(diǎn)總數(shù)為

9、【 】 。 答： n2e 93.順序查找含n個(gè)元素的順序表，若查找成功，則比較關(guān)鍵字的次數(shù)最多為n 次；若查找不成功，則比較關(guān)鍵字的次數(shù)為n+1 次。 94.在含有n個(gè)元素的有序順序表中進(jìn)行二分查找，最大的比較次數(shù)是.log2n+1 。 95.用二分查找一個(gè)查找表，該查找表必須具有的特點(diǎn)是 順序存儲且關(guān)鍵字有序 。 96. 分塊查找發(fā)將待查找的表均勻地分成若干塊且塊中諸記錄的順序可以是任意的，但塊與塊之間 關(guān)鍵字有序 。 97.在分塊查找方法中，首先查找 關(guān)鍵字表 ，然后再查找相應(yīng)的 對應(yīng)的塊 。98.用二叉排序樹在n個(gè)元素中進(jìn)行查找，最壞情況下查找時(shí)間復(fù)雜度為o(n) ，最好情況的查找時(shí)間復(fù)

10、雜度為 o(log2n) 。99.折半查找的存儲結(jié)構(gòu)僅限于 順序存儲結(jié)構(gòu) ，且是 關(guān)鍵字有序排列 。 100.一個(gè)無序序列可以通過構(gòu)造一棵 二叉排序 樹而變成有序序列，構(gòu)造樹的過程即是對無序序列進(jìn)行排序的過程。101.畫出對長度為10的右序表進(jìn)行折半查找的一棵判定樹，并求其等概率時(shí)查找成功的平均查找長度。答：平均查找長度=(1+2*2+4*3+3*4)/10=2.9102.設(shè)有數(shù)據(jù)集合d=1，12，5，8，3，10，7，13，9，回答下列問題： 依次取d中各數(shù)據(jù)，構(gòu)造一棵二叉排序樹； 如何依據(jù)此二叉排序樹得到d的一個(gè)有序序列。答： 構(gòu)造的二叉排序樹如下圖所示。對該二叉排序樹進(jìn)行中序遍歷，就可以

11、得到d的一個(gè)有序序列： 1，3，5，7，8，9，10，12，13103.每次從無序子表中取出一個(gè)元素，把它插入到有序子表中恰當(dāng)位置，此種排序方法叫做插入 排序；若每次從無序子表中挑選出最小或最大元素，把它交換到有序表的一端，此種排序方法叫做 直接選擇 排序。104.每次通過基準(zhǔn)元素間接比較兩個(gè)元素，不滿足約定要求時(shí)就交換位置，該排序方法叫做快速 排序；每次使兩個(gè)相鄰有序表合并成一個(gè)有序表的排序方法叫做歸并 排序。105. 快速 排序方法采用二分法的思想， 堆 排序方法將數(shù)據(jù)的組織采用完全二叉樹的結(jié)構(gòu)。 106.對n個(gè)元素的表進(jìn)行直接選擇排序，所需要的關(guān)鍵字的比較次數(shù)為 n(n-1)/2 。107.在堆和快速排序中，若原始記錄接近正序或反序，則選用 堆 ，若原始記錄無序，則選用 快速 。 108.在