西南交大數(shù)據(jù)結(jié)構(gòu)主觀題作業(yè)

1、弘成無錫數(shù)字化學(xué)習(xí)中心批次層次：專升本專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)姓名：劉鵬亮學(xué)號：15940673第一次作業(yè)三、主觀題(共3道小題)14.數(shù)據(jù)的物理結(jié)構(gòu)包括的表示和的表示。參考答案：線性結(jié)構(gòu),非線性結(jié)構(gòu)15.數(shù)據(jù)邏輯結(jié)構(gòu)包括、和四種，樹結(jié)構(gòu)和圖結(jié)構(gòu)統(tǒng)稱為。參考答案：集合、線性結(jié)構(gòu)、樹、圖、非線性結(jié)構(gòu)16.數(shù)據(jù)結(jié)構(gòu)研究的是和以及它們之間的相互關(guān)系，并對于這種結(jié)構(gòu)定義相應(yīng)的，設(shè)計(jì)出相應(yīng)的。參考答案：邏輯結(jié)構(gòu)，物理結(jié)構(gòu)，運(yùn)算，算法第二次作業(yè)三、主觀題(共22道小題)24.向一個(gè)長度為n的順序表中的第i個(gè)元素之前插入一個(gè)元素時(shí)，需要向后移動(dòng) 個(gè)元素。參考答案：n-i+125.在一個(gè)長度為n的順序表中刪除第

2、i個(gè)元素時(shí)，需要向前移動(dòng)元素。參考答案：n-i26.在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是。參考答案：簡單插入、刪除算法27.在單鏈中要?jiǎng)h除某一指定結(jié)點(diǎn)，必須找到該結(jié)點(diǎn)的結(jié)點(diǎn)。參考答案：直接前驅(qū)28.訪問單鏈表中的結(jié)點(diǎn)，必須沿著依次進(jìn)行。參考答案：指針域29.在雙鏈表中每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，一個(gè)指向，一個(gè)指向。參考答案：直接前驅(qū)結(jié)點(diǎn)，直接后繼結(jié)點(diǎn)30.在鏈表中，刪除最后一個(gè)結(jié)點(diǎn)的算法時(shí)間復(fù)雜度為O(1)。參考答案：雙向循環(huán)31.訪問一個(gè)線性表中具有給定值的時(shí)間復(fù)雜度的數(shù)量級是。參考答案：O(n)32.由n個(gè)數(shù)據(jù)元素生成一個(gè)順序表，若每次都調(diào)用插入算法把一個(gè)元素插入到表頭，則整個(gè)算法的時(shí)間復(fù)雜度為，若每次

3、都調(diào)用插入算法把一個(gè)元素插入到表尾，則整個(gè)算法的時(shí)間復(fù)雜度為。參考答案：O(n)，O(n2)33.在鏈表中，可以用表尾指針代替表頭指針。參考答案：雙向34.在鏈表中，可以用表尾指針代替表頭指針。參考答案：雙向35.根據(jù)n個(gè)數(shù)據(jù)元素建立對應(yīng)的順序表和單鏈表存儲(chǔ)結(jié)構(gòu)，其算法的時(shí)間復(fù)雜度最好的情況是，最壞的情況是。參考答案：O(n)，O(n2)36.求線性表的順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)的長度的算法時(shí)間復(fù)雜度分別是和。參考答案：O(1) ,O(n)37.在一個(gè)帶頭結(jié)點(diǎn)的單鏈表中，在表頭插入或刪除與在其他位置插入或刪除，其操作過程是否相同？。參考答案：相同38.在一個(gè)不帶頭結(jié)點(diǎn)的單鏈表中，在表頭插入或刪除與在其

4、他位置插入或刪除，其操作過程是否相同？。參考答案：不相同39.闡述順序表和鏈表存儲(chǔ)方式的特點(diǎn)。參考答案：順序表存儲(chǔ)方式為數(shù)據(jù)分配連續(xù)的存儲(chǔ)單元，數(shù)據(jù)元素按邏輯順序依次存儲(chǔ)到相應(yīng)存儲(chǔ)單元中，使得邏輯相鄰的數(shù)據(jù)元素物理也相鄰，因此可以實(shí)現(xiàn)隨即訪問線性表的數(shù)據(jù)元素，即數(shù)據(jù)訪問的時(shí)間復(fù)雜度為O(1)。鏈表存儲(chǔ)方式分配的存儲(chǔ)單元可以不連續(xù)，通過每個(gè)結(jié)點(diǎn)的指針域來表示數(shù)據(jù)元素之間的邏輯關(guān)系，只能順序訪問線性表中的數(shù)據(jù)元素。40.若頻繁地對一個(gè)線性表進(jìn)行插入和刪除操作，則該線性表宜采用何種存儲(chǔ)結(jié)構(gòu)，為什么？參考答案：若頻繁地對一個(gè)線性表進(jìn)行插入和刪除操作，則該線性表宜采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。因此鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)在插入

5、和刪除數(shù)據(jù)元素時(shí)不需要移動(dòng)數(shù)據(jù)元素，只需要修改結(jié)點(diǎn)的指針域就可以改變數(shù)據(jù)元素之間的邏輯關(guān)系。41.在單鏈表、雙向循環(huán)鏈表和單循環(huán)鏈表中，若僅知道指針p指向某結(jié)點(diǎn)，不知道頭指針，能否將結(jié)點(diǎn)p從相應(yīng)的鏈表中刪除？若可以，時(shí)間復(fù)雜度各為多少。參考答案：要實(shí)現(xiàn)刪除p結(jié)點(diǎn)的操作，必須找到其前驅(qū)結(jié)點(diǎn)，修改其指針域的值使其指向p的后繼結(jié)點(diǎn)，以實(shí)現(xiàn)刪除結(jié)點(diǎn)p。單鏈表不行，因此不知道頭指針就無法找到結(jié)點(diǎn)p的前驅(qū)結(jié)點(diǎn)。雙向循環(huán)鏈表和單循環(huán)鏈表可以可以實(shí)現(xiàn)刪除p結(jié)點(diǎn)。單循環(huán)鏈表刪除p結(jié)點(diǎn)的時(shí)間復(fù)雜度為O(n)，雙循環(huán)鏈表刪除P結(jié)點(diǎn)的時(shí)間復(fù)雜度為O(1)。42.對鏈表設(shè)置頭結(jié)點(diǎn)的作用是什么？參考答案：對帶頭結(jié)點(diǎn)的鏈表

6、，在表的任何結(jié)點(diǎn)之前插入結(jié)點(diǎn)或刪除任何位置的結(jié)點(diǎn)，所要做的都是修改前一個(gè)結(jié)點(diǎn)的指針域，因?yàn)樵趲ь^結(jié)點(diǎn)的鏈表中任何元素結(jié)點(diǎn)都有前驅(qū)結(jié)點(diǎn)。如果沒有頭結(jié)點(diǎn)，在首元結(jié)點(diǎn)前插入結(jié)點(diǎn)或刪除首元結(jié)點(diǎn)都要修改頭指針，其算法要比不帶頭結(jié)點(diǎn)的算法復(fù)雜些。 其次，帶頭結(jié)點(diǎn)的鏈表結(jié)構(gòu)，初始化后的頭指針就固定了，除撤銷算法外，所有算法都不會(huì)修改頭指針，可以減少出錯(cuò)的可能性。43.已知一個(gè)線性表用含頭結(jié)點(diǎn)的單鏈表做存儲(chǔ)結(jié)構(gòu)，寫一個(gè)算法求單鏈表的長度。參考答案：int listlenght(linklist L) int length=0;P=L-next;while(p) length+;p=p-next;return(

7、length);44.已知一個(gè)順序表L，其中的元素按值遞增有序排列，設(shè)計(jì)一個(gè)算法插入一個(gè)值為x的元素后保持該順序表仍然遞增有序，且空間復(fù)雜度為0（1）。參考答案：void insertsq(sqlist L,elemtype x) n=L.length-1;if(LT(L.elemn,x) n+;L.elemn=x;elsewhile(n=0<(x,L.elemn) L.elemn+1=L.elemn;n-;L.elemn+1=L.elemn;return;45.寫一個(gè)算法，從順序表中刪除值為x的所有元素。參考答案：void delallsq(Sqlist &L) int i=0,j=0;

8、while(jnext=Q.rear70.如果棧的最大長度難以估計(jì)，最好使用。參考答案：鏈棧71.為什么說棧是一種后進(jìn)先出表？參考答案：因?yàn)闂Ｊ窍薅ㄔ诒淼囊欢诉M(jìn)行插入和刪除操作，所以后入棧的數(shù)據(jù)元素總是先出棧，所以說棧是一種后進(jìn)先出表。72.對于一個(gè)棧，其輸入序列是A,B,C,試給出全部可能的輸出序列。參考答案：可能的出棧序列是：ABC、ACB、BAC、BCA、CBA。73.何謂隊(duì)列上溢？何為假溢出現(xiàn)象？有哪些解決假溢出問題的方法，并分別闡述其工作原理。參考答案：隊(duì)列上溢指在隊(duì)列的順序存儲(chǔ)分配中，按照隊(duì)列的操作規(guī)則，需要進(jìn)隊(duì)的元素因找不到合適的存儲(chǔ)單元而無法進(jìn)入隊(duì)列。假溢出指在隊(duì)列的順序存儲(chǔ)分

9、配中，分配給隊(duì)列的存儲(chǔ)空間有存儲(chǔ)單元未被占用，但按照操作規(guī)則而使進(jìn)隊(duì)的數(shù)據(jù)元素?zé)o法進(jìn)隊(duì)的現(xiàn)象。解決假溢出問題的方法是在隊(duì)列的順序存儲(chǔ)分配中，分配給隊(duì)列的存儲(chǔ)空間可以循環(huán)使用，其進(jìn)本原理是用表示隊(duì)頭和隊(duì)尾指針與分配給隊(duì)列的存儲(chǔ)空間長度進(jìn)行取模運(yùn)算。即：入隊(duì)操作：Q.rear=(Q.rear+1)%MSize出隊(duì)操作：Q.front=(Q.front+1)%MSize74.隊(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ù)尾指針很容易找到鏈表的

10、頭結(jié)點(diǎn)，入隊(duì)出隊(duì)操作的算法時(shí)間復(fù)雜度均為O(1)。若只設(shè)頭指針，則出隊(duì)操作的算法時(shí)間復(fù)雜度為O(1)，入隊(duì)操作的算法時(shí)間復(fù)雜度為O(n)。75.深度為k的完全二叉樹至少有個(gè)結(jié)點(diǎn)，至多有個(gè)結(jié)點(diǎn)。參考答案：2K-1 ,2K-176.在一棵二叉樹中，度為0的結(jié)點(diǎn)個(gè)數(shù)為n0，度為2的結(jié)點(diǎn)個(gè)數(shù)為n2,則有n0=。參考答案：n2+177.一棵二叉樹第i層最多有個(gè)結(jié)點(diǎn)，一棵有n個(gè)結(jié)點(diǎn)的滿二叉樹共有個(gè)結(jié)點(diǎn)，共有個(gè)葉結(jié)點(diǎn)。參考答案：2i-1 ,2K-1 ,2K-178.根據(jù)二叉樹的定義，具有3個(gè)結(jié)點(diǎn)的二叉樹共有 種不同形態(tài)，它們分別是。參考答案：5 ,79.有一棵如下圖所示的樹，回答下列問題：這棵樹的根結(jié)點(diǎn)是。

11、這棵樹的葉子結(jié)點(diǎn)是。結(jié)點(diǎn)c的度為。這棵樹的深度是。結(jié)點(diǎn)c的孩子結(jié)點(diǎn)是。結(jié)點(diǎn)c的雙親結(jié)點(diǎn)是。這棵樹的度是。參考答案： ab,e,g,d 2 4e,f a 380.樹與二叉樹的兩個(gè)主要差別是、。參考答案：樹中結(jié)點(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)的頻率依

12、次為4，7，5，2，9，構(gòu)造對應(yīng)的哈夫曼樹，求哈夫曼樹的帶權(quán)路徑長度和每個(gè)字符的哈夫曼編碼。參考答案：字符編碼：a：011b：10c：00d：010e：1184.假設(shè)一棵二叉樹采用順序存儲(chǔ)結(jié)構(gòu)，如下圖所示。05101520eafdgcjhib回答些列問題：畫出二叉樹表示。寫出先序、中序和后序遍歷結(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)的無向圖最多有條邊。參考答案

13、：n(n-1)/286.一個(gè)圖的表示法是唯一的，而表示法是不唯一的。參考答案：鄰接矩陣,鄰接表87.具有10個(gè)頂點(diǎn)的無向圖，邊的總數(shù)最多為。參考答案：4588.在有n個(gè)頂點(diǎn)的有向圖中，每個(gè)頂點(diǎn)的度最大可達(dá)。參考答案：2(n-1)89.已知一個(gè)有向圖采用鄰接矩陣表示，計(jì)算第i個(gè)頂點(diǎn)的入度的方法是。參考答案：求第i列非0元素個(gè)數(shù)90.從占用的存儲(chǔ)空間來看，對于稠密圖和稀疏圖，采用鄰接矩陣和鄰接表那個(gè)更好些？參考答案：從占用存儲(chǔ)空間看，稠密圖采用鄰接矩陣更好，稀疏圖采用鄰接表更好。91.用鄰接矩陣表示圖時(shí)，矩陣元素的個(gè)數(shù)與頂點(diǎn)個(gè)數(shù)是否相關(guān)？與邊的條數(shù)是否相關(guān)？為什么？。參考答案：用鄰接矩陣表示圖，矩

14、陣元素的個(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ù)為【 】 。參考答案：n2e93.順序查找含n個(gè)元素的順序表，若查找成功，則比較關(guān)鍵字的次數(shù)最多為次；若查找不成功，則比較關(guān)鍵字的次數(shù)為次。參考答案：n ,n+194.在含有n個(gè)元素的有序順序表中進(jìn)行二分查找，最大的比較次數(shù)是。參考答案：.log2n+195.用二分查找一個(gè)查找表，該查找表必須具有的特點(diǎn)是。參考答案：順序存儲(chǔ)且關(guān)鍵字有序96.分塊查找發(fā)將待查找的表均勻地分成若干塊且塊中諸記錄

15、的順序可以是任意的，但塊與塊之間。參考答案：關(guān)鍵字有序97.在分塊查找方法中，首先查找，然后再查找相應(yīng)的。參考答案：關(guān)鍵字表，對應(yīng)的塊98.用二叉排序樹在n個(gè)元素中進(jìn)行查找，最壞情況下查找時(shí)間復(fù)雜度為，最好情況的查找時(shí)間復(fù)雜度為。參考答案：O(n)，O(log2n)99.折半查找的存儲(chǔ)結(jié)構(gòu)僅限于，且是。參考答案：順序存儲(chǔ)結(jié)構(gòu)，關(guān)鍵字有序排列100.一個(gè)無序序列可以通過構(gòu)造一棵樹而變成有序序列，構(gòu)造樹的過程即是對無序序列進(jìn)行排序的過程。參考答案：二叉排序101.畫出對長度為10的右序表進(jìn)行折半查找的一棵判定樹，并求其等概率時(shí)查找成功的平均查找長度。參考答案：平均查找長度=(1+2*2+4*3+3

16、*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)行中序遍歷，就可以得到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)鍵字