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

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

2、序表中的第i 個元素之前插入一個元素時，需要向后移動個元素。參考答案： n-i+125.在一個長度為n 的順序表中刪除第i 個元素時，需要向前移動元素。參考答案：n-i26.在單鏈表中設置頭結點的作用是。參考答案： 簡單插入、刪除算法27.在單鏈中要刪除某一指定結點，必須找到該結點的結點。參考答案： 直接前驅28.訪問單鏈表中的結點，必須沿著依次進展。參考答案： 指針域29.在雙鏈表中每個結點有兩個指針域，一個指向，一個指向。參考答案： 直接前驅結點，直接后繼結點30.在鏈表中，刪除最后一個結點的算法時間復雜度為O(1) 。參考答案：雙向循環(huán)31.訪問一個線性表中具有給定值的時間復雜度的數(shù)量級

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

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

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

6、(1) 。42. 對鏈表設置頭結點的作用是什么？參考答案：對帶頭結點的鏈表，在表的任何結點之前插入結點或刪除任何位置的結點，所要做的都是修改前一個結點的表中任何元素結點都有前驅結點。如果沒有頭結點，在首元結點前插入結點或刪除首元結點都要修改頭指針，其雜些。其次，帶頭結點的鏈表構造，初始化后的頭指針就固定了，除撤銷算法外，所有算法都不會修改頭指針43. 一個線性表用含頭結點的單鏈表做存儲構造，寫一個算法求單鏈表的長度。參考答案：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.一個順序表L，其中的元素按值遞增有序排列，設計一個算法插入一個值為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.寫一個算法，從順序表中刪除值為x 的所有元素。參考答案：void delallsq(Sqlist

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

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

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

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

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

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

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

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

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

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