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

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

2、一個(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ù)雜度為0(1)。參考答案：雙向循環(huán)31. 訪問(wèn)一個(gè)線性表中具有給定值的時(shí)間復(fù)雜度的數(shù)量級(jí)是 。參考答案：oim32. 由n個(gè)數(shù)據(jù)元素生成一個(gè)順序表，若每次都調(diào)用插入算

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

4、帶頭結(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ù)雜度為0(1)。鏈表存儲(chǔ)方式分配的存儲(chǔ)單元可以不連續(xù)，通過(guò)每個(gè)結(jié)點(diǎn)的指針域來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系，只能順40. 若頻繁地對(duì)一個(gè)線性表進(jìn)行插入和刪除操作，則該線性表宜采用何種存儲(chǔ)結(jié)構(gòu)，為什么？參考答案：若頻繁地對(duì)一個(gè)線性表進(jìn)行插入和刪除操作，則該線性表宜采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。因此鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)在移動(dòng)數(shù)據(jù)元

5、素，只需要修改結(jié)點(diǎn)的指針域就可以改變數(shù)據(jù)元素之間的邏輯關(guān)系。41. 在單鏈表、雙向循環(huán)鏈表和單循環(huán)鏈表中，若僅知道指針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)鏈0(n)，雙循環(huán)鏈表刪除 P結(jié)點(diǎn)的時(shí)間復(fù)雜度為 0(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)都有前

6、驅(qū)結(jié)點(diǎn)。如果沒(méi)有頭結(jié)點(diǎn)，在首元結(jié)點(diǎn)前插入結(jié)點(diǎn)或刪除首元結(jié)點(diǎn)都要修改頭指針，其 雜些。其次，帶頭結(jié)點(diǎn)的鏈表結(jié)構(gòu)，初始化后的頭指針就固定了，除撤銷算法外，所有算法都不會(huì)修改頭指針43. 已知一個(gè)線性表用含頭結(jié)點(diǎn)的單鏈表做存儲(chǔ)結(jié)構(gòu)，寫(xiě)一個(gè)算法求單鏈表的長(zhǎng)度。參考答案：int listlenght(linklist L) int len gth=0;P=L->n ext;while(p) len gth+;p=p->n ext;return(le ngth);44. 已知一個(gè)順序表L,其中的元素按值遞增有序排列，設(shè)計(jì)一個(gè)算法插入一個(gè)值為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. 寫(xiě)一個(gè)算法，從順序表中刪除值為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)隊(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è)棧采取順序存儲(chǔ)結(jié)構(gòu)，棧中已有i-1個(gè)元素，則第i個(gè)元素進(jìn)棧操作的算法時(shí)間復(fù)雜度是 。參考答案：0( 1)65. 棧的特點(diǎn)是【】，隊(duì)列

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

10、ear70. 如果棧的最大長(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 CBA73. 何謂隊(duì)列上溢？何為假溢出現(xiàn)象？有哪些解決假溢出問(wèn)題的方法，并分別闡述其工作原理。 參考答案：隊(duì)列上溢指在隊(duì)列的順序存儲(chǔ)分配中，按照隊(duì)列的操作規(guī)則，需要進(jìn)隊(duì)的元素因找不到合適的存儲(chǔ)單元而無(wú)假溢出指在隊(duì)列的順序存儲(chǔ)分配中，分配給隊(duì)列的存儲(chǔ)空間有存儲(chǔ)單元未被占用

11、，但按照操作規(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.fro nt=(Q.fro nt+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ì)操到鏈表的頭結(jié)點(diǎn)，入隊(duì)出隊(duì)操作的算法時(shí)間復(fù)雜度均為雜度為0(n)。0(1)。若只設(shè)頭指針，則出隊(duì)操作的算法時(shí)間復(fù)雜度為75.

12、 深度為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)。參考答案：2i-1,2 K-1,2K-178.根據(jù)二叉樹(shù)的定義，具有3個(gè)結(jié)點(diǎn)的二叉樹(shù)共有種不同形態(tài)，它們分別是 7 / 12# / 1279. 有一棵如下圖所示的樹(shù)，回答下列問(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)是 。 a b,e

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

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

15、 具有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)的入度的方法是。參考答案：求第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ì)

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

17、鍵字表，對(duì)應(yīng)的塊97. 用二叉排序樹(shù)在 n個(gè)元素中進(jìn)行查找，最壞情況下查找時(shí)間復(fù)雜度為 ，最好情況的查找時(shí)間復(fù)雜度為參考答案：0(n)，O(log 2n)98. 折半查找的存儲(chǔ)結(jié)構(gòu)僅限于 ，且是。參考答案：順序存儲(chǔ)結(jié)構(gòu)，關(guān)鍵字有序排歹U99. 一個(gè)無(wú)序序列可以通過(guò)構(gòu)造一棵 樹(shù)而變成有序序列，構(gòu)造樹(shù)的過(guò)程即是對(duì)無(wú)序序列進(jìn)行排序的過(guò)程參考答案：二叉排序100. 畫(huà)出對(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，回答下列問(wèn)題:

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