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

1、弘成無錫數(shù)字化學習中心批次層次：專升本專業(yè)：計算機科學與技術(shù)姓名：劉鵬亮學號： 159406731 / 12第一次作業(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)定義相應的 ，設(shè)計出相應的。參考答案：邏輯結(jié)構(gòu)，物理結(jié)構(gòu)，運算，算法第二次作業(yè)三、主觀題(共22道小題)24. 向一個長度為n的順序表中的第i個元素之前插入一個元素時，需要向后移動個元素。參考答案：n-i+125. 在

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

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

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

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

6、驅(qū)結(jié)點。如果沒有頭結(jié)點，在首元結(jié)點前插入結(jié)點或刪除首元結(jié)點都要修改頭指針，其 雜些。其次，帶頭結(jié)點的鏈表結(jié)構(gòu)，初始化后的頭指針就固定了，除撤銷算法外，所有算法都不會修改頭指針43. 已知一個線性表用含頭結(jié)點的單鏈表做存儲結(jié)構(gòu)，寫一個算法求單鏈表的長度。參考答案：int listlenght(linklist L) int len gth=0;P=L->n ext;while(p) len gth+;p=p->n ext;return(le ngth);44. 已知一個順序表L,其中的元素按值遞增有序排列，設(shè)計一個算法插入一個值為x的元素后保持該順序表仍0( 1 )。參考答案：voi

7、d in sertsq(sqlist L,elemtype x) n=L.le ngth-1;if(LT(L.elem n ,x) n+;L.elem n=x;elsewhile( n>=0&&LT(x ,L .elem n) L.elem n+1=L.elem n;n-;L.elem n+1=L.elem n;return;45. 寫一個算法，從順序表中刪除值為x的所有元素。參考答案：void delallsq(Sqlist &L) int i=0,j=0;while(j<L .len gth) if(L.elemj!=x)L.elemi+=L.elemj

8、;j+;L.lon gth=i;第三次作業(yè)三、主觀題(共50道小題)60. 循環(huán)隊列的引入，目的是為了克服 。參考答案：順序隊列的假溢出61. 區(qū)分循環(huán)隊列的空與滿有3種方法，它們是 、 。參考答案：少用一個元素、設(shè)空滿標志、用計數(shù)器記錄隊列中元素個數(shù)62. 棧和隊列的區(qū)別是 ,參考答案：棧只能在表一端進行插入和刪除操作，隊列限制在表的一端進行插入操作，在另一端進行刪除操作63. 個棧的輸入序列是12345，則棧的輸出序列 43512是。參考答案：錯誤的64. 設(shè)棧采取順序存儲結(jié)構(gòu)，棧中已有i-1個元素，則第i個元素進棧操作的算法時間復雜度是 。參考答案：0( 1)65. 棧的特點是【】，隊列

9、的特點是【】；棧和隊列都是【】若入棧序列是1,是不可能的出棧序列；若進隊列的序列是1，2，3, 4，則【】是可能的出隊序列。參考答案： 后進先出先進先出限制存取點的線性結(jié)構(gòu)3,2,1,41,2,3,466. 若用不帶頭結(jié)點的單鏈表表示棧，則創(chuàng)建一個空棧要執(zhí)行的操作是。參考答案：top=NULL67. 從循環(huán)隊列中刪除一個元素的操作是 。參考答案：Q.fron t=(Q.fro nt+1)%QSize68. 從循環(huán)隊列中插入一個元素的操作是 。參考答案：Q.rear=(Q.rear+1)%QSize69. 判斷鏈隊列中只有一個結(jié)點的條件是 。參考答案：Q.fron t-> next=Q.r

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

11、，但按照操作規(guī)則而使進隊解決假溢出問題的方法是在隊列的順序存儲分配中，分配給隊列的存儲空間可以循環(huán)使用，其進本原理是用隊列的存儲空間長度進行取模運算。即：入隊操作：Q.rear=(Q.rear+1)%MSize出隊操作：Q.fro nt=(Q.fro nt+1)%MSize74. 隊列可以用單循環(huán)鏈表來實現(xiàn)，故可以只設(shè)一個頭指針或只設(shè)一個尾指針，請分析用哪種方案最合適。 參考答案：使用循環(huán)鏈表來表示隊列，設(shè)置尾指針比較合適，因為入隊操作可以直接在尾結(jié)點后進行插入操作，出隊操到鏈表的頭結(jié)點，入隊出隊操作的算法時間復雜度均為雜度為0(n)。0(1)。若只設(shè)頭指針，則出隊操作的算法時間復雜度為75.

12、 深度為k的完全二叉樹至少有 個結(jié)點，至多有 個結(jié)點。參考答案：2k-1,2 K-176. 在一棵二叉樹中，度為0的結(jié)點個數(shù)為n0,度為2的結(jié)點個數(shù)為n2,則有n0= 。參考答案：n2+177. 一棵二叉樹第i層最多有個結(jié)點，一棵有 n個結(jié)點的滿二叉樹共有 個結(jié)點，共有 _個葉結(jié)點。參考答案：2i-1,2 K-1,2K-178.根據(jù)二叉樹的定義，具有3個結(jié)點的二叉樹共有種不同形態(tài)，它們分別是 7 / 12# / 1279. 有一棵如下圖所示的樹，回答下列問題： 這棵樹的根結(jié)點是 。 這棵樹的葉子結(jié)點是 結(jié)點C的度為。 這棵樹的深度是 。 結(jié)點c的孩子結(jié)點是。 結(jié)點c的雙親結(jié)點是 。 a b,e

13、,g,d 2 4 e,f a 380. 樹與二叉樹的兩個主要差別是 、參考答案：樹中結(jié)點的最大度沒有限制，二叉樹結(jié)點的最大度限定為2、樹的結(jié)點無左右之分，二叉樹參考答案：前序序列：eadcbifghj中序序列：abcdiefhgj 后序序列：bcidahjgfe82. 給出下圖所示的樹的二叉樹表示。參考答案：下圖為其樹的二叉樹表示。83. 有一份電文共有 5個字符：a,b,c,d,e,它們出現(xiàn)的頻率依次為4, 7, 5, 2, 9,構(gòu)造對應的哈夫曼樹，求哈字符的哈夫曼編碼。參考答案：11 / 1229字符編碼:1812 / 12011b: 10c: 00 d: 010e: 1184.假設(shè)一棵二

14、叉樹采用順序存儲結(jié)構(gòu)，如下圖所示05101520eafdgcjh ib回答些列問題： 畫出二叉樹表示。 寫岀先序、中序和后序遍歷結(jié)果 寫出結(jié)點c的雙親結(jié)點和左、右孩子結(jié)點 畫出此二叉樹還原成森林的圖參考答案：二叉樹表示如下圖所示。# / 12# / 1213 / 12 先序序列為：eadcbjfghi中序序列為：acbdjefhgi后序序列為：bcjdahigfe 結(jié)點c的雙親結(jié)點是d,左孩子為b,無右孩子14 / 12# / 1285.有n個頂點的無向圖最多有 條邊。參考答案：n(n-1)/286. 一個圖的 表示法是唯一的，而表示法是不唯一的。# / 12參考答案：鄰接矩陣， 鄰接表87.

15、 具有10個頂點的無向圖，邊的總數(shù)最多為 參考答案：4588. 在有n個頂點的有向圖中，每個頂點的度最大可達 參考答案：2(n-1)89. 已知一個有向圖采用鄰接矩陣表示，計算第i個頂點的入度的方法是。參考答案：求第i列非0元素個數(shù)90. 從占用的存儲空間來看，對于稠密圖和稀疏圖，采用鄰接矩陣和鄰接表那個更好些？參考答案：從占用存儲空間看，稠密圖采用鄰接矩陣更好，稀疏圖采用鄰接表更好。91. 用鄰接矩陣表示圖時，矩陣元素的個數(shù)與頂點個數(shù)是否相關(guān)？與邊的條數(shù)是否相關(guān)？為什么？。 參考答案：用鄰接矩陣表示圖，矩陣元素的個數(shù)與圖的定點個數(shù)直接相關(guān)，與邊的條數(shù)無關(guān)。因為假設(shè)定點個數(shù)為n，則鄰92. 對

16、于一個具有n個頂點和e條邊的無向圖，若采用鄰接表表示，則表頭向量的大小為【】；所有鄰接表參考答案： n 2e93. 順序查找含n個元素的順序表，若查找成功，則比較關(guān)鍵字的次數(shù)最多為 次；若查找不成為 次。參考答案：nn+194. 在含有n個元素的有序順序表中進行二分查找，最大的比較次數(shù)是 。參考答案：|log 2" +195. 用二分查找一個查找表，該查找表必須具有的特點是 。參考答案：順序存儲且關(guān)鍵字有序96.分塊查找發(fā)將待查找的表均勻地分成若干塊且塊中諸記錄的順序可以是任意的，但塊與塊之間。參考答案：關(guān)鍵字有序96. 在分塊查找方法中，首先查找 ，然后再查找相應的 。參考答案：關(guān)

17、鍵字表，對應的塊97. 用二叉排序樹在 n個元素中進行查找，最壞情況下查找時間復雜度為 ，最好情況的查找時間復雜度為參考答案：0(n)，O(log 2n)98. 折半查找的存儲結(jié)構(gòu)僅限于 ，且是。參考答案：順序存儲結(jié)構(gòu)，關(guān)鍵字有序排歹U99. 一個無序序列可以通過構(gòu)造一棵 樹而變成有序序列，構(gòu)造樹的過程即是對無序序列進行排序的過程參考答案：二叉排序100. 畫出對長度為10的右序表進行折半查找的一棵判定樹，并求其等概率時查找成功的平均查找長度。參考答案：平均查找長度 =(1+2*2+4*3+3*4)/10=2.9102.設(shè)有數(shù)據(jù)集合 d=1，12，5，8，3，10，7，13，9，回答下列問題:

18、依次取d中各數(shù)據(jù)，構(gòu)造一棵二叉排序樹；如何依據(jù)此二叉排序樹得到d的一個有序序列。參考答案：構(gòu)造的二叉排序樹如下圖所示。對該二叉排序樹進行中序遍歷，就可以得到d的一個有序序列：1，3，5，7, 8，9，10，12，13103. 每次從無序子表中取出一個元素，把它插入到有序子表中恰當位置，此種排序方法叫做排序；若每次大元素，把它交換到有序表的一端，此種排序方法叫做 排序。參考答案： 插入； 直接選擇104. 每次通過基準元素間接比較兩個元素，不滿足約定要求時就交換位置，該排序方法叫做排序；每次使兩表的排序方法叫做排序。參考答案：快速；歸并105. 排序方法采用二分法的思想，排序方法將數(shù)據(jù)的組織采用完全二叉樹的結(jié)構(gòu)。參考答案：快速， 堆106.