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

1、WORD格式弘成*數(shù)字化學(xué)習(xí)中心批次層次：專升本專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)*：X鵬亮學(xué)號(hào)： 15940673專業(yè)資料整理WORD格式1/12專業(yè)資料整理WORD格式第一次作業(yè)三、主觀題 ( 共 3 道小題 )14.數(shù)據(jù)的物理構(gòu)造包括的表示和的表示。參考答案： 線性構(gòu)造 , 非線性構(gòu)造15.數(shù)據(jù)邏輯構(gòu)造包括、和四種，樹(shù)構(gòu)造和圖構(gòu)造統(tǒng)稱為。參考答案： 集合 、 線性構(gòu)造、 樹(shù) 、 圖 、非線性構(gòu)造16.數(shù)據(jù)構(gòu)造研究的是和以及它們之間的相互關(guān)系，并對(duì)于這種構(gòu)造定義相應(yīng)的，設(shè)計(jì)出相應(yīng)的。參考答案： 邏輯構(gòu)造 ， 物理構(gòu)造， 運(yùn)算，算法第二次作業(yè)三、主觀題 ( 共 22 道小題 )24.向一個(gè)長(zhǎng)度為n 的順

2、序表中的第i 個(gè)元素之前插入一個(gè)元素時(shí)，需要向后移動(dòng)個(gè)元素。參考答案： n-i+125.在一個(gè)長(zhǎng)度為n 的順序表中刪除第i 個(gè)元素時(shí)，需要向前移動(dòng)元素。參考答案：n-i26.在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是。參考答案： 簡(jiǎn)單插入、刪除算法27.在單鏈中要?jiǎng)h除某一指定結(jié)點(diǎn)，必須找到該結(jié)點(diǎn)的結(jié)點(diǎn)。參考答案： 直接前驅(qū)28.訪問(wèn)單鏈表中的結(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.訪問(wèn)一個(gè)線性表中具有給定值的時(shí)間復(fù)雜度的數(shù)量級(jí)

3、是。參考答案： O(n)32. 由 n 個(gè)數(shù)據(jù)元素生成一個(gè)順序表，假設(shè)每次都調(diào)用插入算法把一個(gè)元素插入到表頭，那么整個(gè)算法的時(shí)間復(fù)雜度插入算法把一個(gè)元素插入到表尾，那么整個(gè)算法的時(shí)間復(fù)雜度為。參考答案： O(n)， O(n2)33.在鏈表中，可以用表尾指針代替表頭指針。參考答案：雙向?qū)I(yè)資料整理WORD格式2/12專業(yè)資料整理WORD格式34.在鏈表中，可以用表尾指針代替表頭指針。參考答案：雙向35.根據(jù) n 個(gè)數(shù)據(jù)元素建立對(duì)應(yīng)的順序表和單鏈表存儲(chǔ)構(gòu)造，其算法的時(shí)間復(fù)雜度最好的情況是，是。參考答案： O(n) ， O(n2)36.求線性表的順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)的長(zhǎng)度的算法時(shí)間復(fù)雜度分別是和。參考

4、答案：O(1),O(n)37. 在一個(gè)帶頭結(jié)點(diǎn)的單鏈表中，在表頭插入或刪除與在其他位置插入或刪除，其操作過(guò)程是否一樣？參考答案： 一樣38.在一個(gè)不帶頭結(jié)點(diǎn)的單鏈表中，在表頭插入或刪除與在其他位置插入或刪除，其操作過(guò)程是否一樣？。參考答案： 不一樣39.闡述順序表和鏈表存儲(chǔ)方式的特點(diǎn)。參考答案：順序表存儲(chǔ)方式為數(shù)據(jù)分配連續(xù)的存儲(chǔ)單元，數(shù)據(jù)元素按邏輯順序依次存儲(chǔ)到相應(yīng)存儲(chǔ)單元中，使得邏輯相此可以實(shí)現(xiàn)隨即訪問(wèn)線性表的數(shù)據(jù)元素，即數(shù)據(jù)訪問(wèn)的時(shí)間復(fù)雜度為O(1) 。鏈表存儲(chǔ)方式分配的存儲(chǔ)單元可以不連續(xù)，通過(guò)每個(gè)結(jié)點(diǎn)的指針域來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系，只能順40. 假設(shè)頻繁地對(duì)一個(gè)線性表進(jìn)展插入和刪除

5、操作，那么該線性表宜采用何種存儲(chǔ)構(gòu)造，為什么？參考答案： 假設(shè)頻繁地對(duì)一個(gè)線性表進(jìn)展插入和刪除操作，那么該線性表宜采用鏈?zhǔn)酱鎯?chǔ)構(gòu)造。因此鏈?zhǔn)酱鎯?chǔ)構(gòu)造在移動(dòng)數(shù)據(jù)元素，只需要修改結(jié)點(diǎn)的指針域就可以改變數(shù)據(jù)元素之間的邏輯關(guān)系。41.在單鏈表、雙向循環(huán)鏈表和單循環(huán)鏈表中，假設(shè)僅知道指針p 指向某結(jié)點(diǎn)，不知道頭指針，能否將結(jié)點(diǎn)p 從間復(fù)雜度各為多少。參考答案： 要實(shí)現(xiàn)刪除p 結(jié)點(diǎn)的操作，必須找到其前驅(qū)結(jié)點(diǎn)，修改其指針域的值使其指向p 的后繼結(jié)點(diǎn)，以實(shí)現(xiàn)此不知道頭指針就無(wú)法找到結(jié)點(diǎn)p 的前驅(qū)結(jié)點(diǎn)。 雙向循環(huán)鏈表和單循環(huán)鏈表可以可以實(shí)現(xiàn)刪除p 結(jié)點(diǎn)。單循環(huán)鏈O(n) ，雙循環(huán)鏈表刪除P 結(jié)點(diǎn)的時(shí)間復(fù)雜度為O

6、(1) 。42. 對(duì)鏈表設(shè)置頭結(jié)點(diǎn)的作用是什么？參考答案：對(duì)帶頭結(jié)點(diǎn)的鏈表，在表的任何結(jié)點(diǎn)之前插入結(jié)點(diǎn)或刪除任何位置的結(jié)點(diǎn)，所要做的都是修改前一個(gè)結(jié)點(diǎn)的表中任何元素結(jié)點(diǎn)都有前驅(qū)結(jié)點(diǎn)。如果沒(méi)有頭結(jié)點(diǎn)，在首元結(jié)點(diǎn)前插入結(jié)點(diǎn)或刪除首元結(jié)點(diǎn)都要修改頭指針，其雜些。其次，帶頭結(jié)點(diǎn)的鏈表構(gòu)造，初始化后的頭指針就固定了，除撤銷算法外，所有算法都不會(huì)修改頭指針43. 一個(gè)線性表用含頭結(jié)點(diǎn)的單鏈表做存儲(chǔ)構(gòu)造，寫一個(gè)算法求單鏈表的長(zhǎng)度。參考答案：int listlenght(linklist L) int length=0; P=L-next; while(p) length+;專業(yè)資料整理WORD格式3/12專

7、業(yè)資料整理WORD格式p=p-next;return(length);44.一個(gè)順序表L，其中的元素按值遞增有序排列，設(shè)計(jì)一個(gè)算法插入一個(gè)值為x 的元素后保持該順序表仍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

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

9、單元而無(wú)假溢出指在隊(duì)列的順序存儲(chǔ)分配中，分配給隊(duì)列的存儲(chǔ)空間有存儲(chǔ)單元未被占用，但按照操作規(guī)那么而使進(jìn)隊(duì)解決假溢出問(wèn)題的方法是在隊(duì)列的順序存儲(chǔ)分配中， 分配給隊(duì)列的存儲(chǔ)空間可以循環(huán)使用， 其進(jìn)本原理是用隊(duì)列的存儲(chǔ)空間長(zhǎng)度進(jìn)展取模運(yùn)算。即：入隊(duì)操作： Q.rear=(Q.rear+1)%MSize出隊(duì)操作： Q.front=(Q.front+1)%MSize74. 隊(duì)列可以用單循環(huán)鏈表來(lái)實(shí)現(xiàn)，故可以只設(shè)一個(gè)頭指針或只設(shè)一個(gè)尾指針，請(qǐng)分析用哪種方案最適宜。參考答案：使用循環(huán)鏈表來(lái)表示隊(duì)列， 設(shè)置尾指針比較適宜， 因?yàn)槿腙?duì)操作可以直接在尾結(jié)點(diǎn)后進(jìn)展插入操作，出隊(duì)操專業(yè)資料整理WORD格式5/12專業(yè)

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

11、的樹(shù)，答復(fù)以下問(wèn)題：這棵樹(shù)的根結(jié)點(diǎn)是。這棵樹(shù)的葉子結(jié)點(diǎn)是。結(jié)點(diǎn) c 的度為。這棵樹(shù)的深度是。結(jié)點(diǎn) c 的孩子結(jié)點(diǎn)是。結(jié)點(diǎn) c 的雙親結(jié)點(diǎn)是。這棵樹(shù)的度是。參考答案： a b,e,g,d 2 4 e,f專業(yè)資料整理WORD格式6/12專業(yè)資料整理WORD格式 a 380.樹(shù)與二叉樹(shù)的兩個(gè)主要差異是、參考答案： 樹(shù)中結(jié)點(diǎn)的最大度沒(méi)有限制，二叉樹(shù)結(jié)點(diǎn)的最大度限定為2、樹(shù)的結(jié)點(diǎn)無(wú)左右之分，二叉樹(shù)81.設(shè)有如以下列圖所示的二叉樹(shù)，給出其前序、中序和后序遍歷結(jié)果。參考答案：前序序列： eadcbifghj中序序列： abcdiefhgj后序序列： bcidahjgfe82. 給出以下列圖所示的樹(shù)的二叉樹(shù)表

12、示。專業(yè)資料整理WORD格式7/12專業(yè)資料整理WORD格式參考答案：以下列圖為其樹(shù)的二叉樹(shù)表示。83.有一份電文共有5 個(gè)字符： a,b,c,d,e,它們出現(xiàn)的頻率依次為4，7， 5， 2， 9，構(gòu)造對(duì)應(yīng)的哈夫曼樹(shù)，求哈字符的哈夫曼編碼。參考答案：專業(yè)資料整理WORD格式8/12專業(yè)資料整理WORD格式字符編碼：a： 011b： 10c： 00d： 010e： 1184.假設(shè)一棵二叉樹(shù)采用順序存儲(chǔ)構(gòu)造，如以下列圖所示。05101520eafdgcjhib答復(fù)些列問(wèn)題：畫出二叉樹(shù)表示。寫出先序、中序和后序遍歷結(jié)果寫出結(jié)點(diǎn)c 的雙親結(jié)點(diǎn)和左、右孩子結(jié)點(diǎn)畫出此二叉樹(shù)復(fù)原成森林的圖參考答案：二叉樹(shù)表

13、示如以下列圖所示。專業(yè)資料整理WORD格式9/12專業(yè)資料整理WORD格式先序序列為：eadcbjfghi中序序列為：acbdjefhgi后序序列為：bcjdahigfe結(jié)點(diǎn) c 的雙親結(jié)點(diǎn)是d，左孩子為b，無(wú)右孩子該二叉樹(shù)對(duì)應(yīng)的森林為85.有 n 個(gè)頂點(diǎn)的無(wú)向圖最多有條邊。參考答案： n(n-1)/286.一個(gè)圖的表示法是唯一的，而表示法是不唯一的。參考答案： 鄰接矩陣 ,鄰接表87.具有 10個(gè)頂點(diǎn)的無(wú)向圖，邊的總數(shù)最多為。參考答案： 4588.在有 n 個(gè)頂點(diǎn)的有向圖中，每個(gè)頂點(diǎn)的度最大可達(dá)。參考答案： 2(n-1)89.一個(gè)有向圖采用鄰接矩陣表示，計(jì)算第i 個(gè)頂點(diǎn)的入度的方法是。參考答

14、案： 求第 i 列非 0元素個(gè)數(shù)90. 從占用的存儲(chǔ)空間來(lái)看，對(duì)于稠密圖和稀疏圖，采用鄰接矩陣和鄰接表那個(gè)更好些？參考答案： 從占用存儲(chǔ)空間看，稠密圖采用鄰接矩陣更好，稀疏圖采用鄰接表更好。91. 用鄰接矩陣表示圖時(shí)，矩陣元素的個(gè)數(shù)與頂點(diǎn)個(gè)數(shù)是否相關(guān)？與邊的條數(shù)是否相關(guān)？為什么？。參考答案：用鄰接矩陣表示圖，矩陣元素的個(gè)數(shù)與圖的定點(diǎn)個(gè)數(shù)直接相關(guān)，與邊的條數(shù)無(wú)關(guān)。因?yàn)榧僭O(shè)定點(diǎn)個(gè)數(shù)為n，那么鄰92.對(duì)于一個(gè)具有n 個(gè)頂點(diǎn)和e 條邊的無(wú)向圖，假設(shè)采用鄰接表表示，那么表頭向量的大小為【】；所有鄰接表參考答案：n2e93.順序查找含n 個(gè)元素的順序表，假設(shè)查找成功，那么比較關(guān)鍵字的次數(shù)最多為次；假設(shè)查找

15、不成為次。參考答案： n,n+1專業(yè)資料整理WORD格式10/12專業(yè)資料整理WORD格式94.在含有 n 個(gè)元素的有序順序表中進(jìn)展二分查找，最大的比較次數(shù)是。參考答案：n. log 2 +195.用二分查找一個(gè)查找表，該查找表必須具有的特點(diǎn)是。參考答案： 順序存儲(chǔ)且關(guān)鍵字有序96.分塊查找發(fā)將待查找的表均勻地分成假設(shè)干塊且塊中諸記錄的順序可以是任意的，但塊與塊之間。參考答案： 關(guān)鍵字有序97.在分塊查找方法中，首先查找，然后再查找相應(yīng)的。參考答案： 關(guān)鍵字表，對(duì)應(yīng)的塊98.用二叉排序樹(shù)在n 個(gè)元素中進(jìn)展查找，最壞情況下查找時(shí)間復(fù)雜度為，最好情況的查找時(shí)間復(fù)雜度為參考答案：O(n)n， O(l

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

17、專業(yè)資料整理WORD格式11/12專業(yè)資料整理WORD格式對(duì)該二叉排序樹(shù)進(jìn)展中序遍歷，就可以得到d 的一個(gè)有序序列：1 ， 3， 5， 7， 8， 9， 10， 12， 13103.每次從無(wú)序子表中取出一個(gè)元素，把它插入到有序子表中恰當(dāng)位置，此種排序方法叫做排序；假設(shè)每次大元素，把它交換到有序表的一端，此種排序方法叫做排序。參考答案： 插入；直接選擇104.每次通過(guò)基準(zhǔn)元素間接比較兩個(gè)元素，不滿足約定要求時(shí)就交換位置，該排序方法叫做排序；每次使兩表的排序方法叫做排序。參考答案： 快速； 歸并105.排序方法采用二分法的思想，排序方法將數(shù)據(jù)的組織采用完全二叉樹(shù)的構(gòu)造。參考答案： 快速 ，堆106.對(duì) n 個(gè)元素的表進(jìn)展直接選擇排序，所需要的關(guān)鍵字的比較次數(shù)為。參考答案