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

1、弘成無(wú)錫數(shù)字化學(xué)習(xí)中心批次層次：專(zhuān)升本專(zhuān)業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)姓名：劉鵬亮學(xué)號(hào)：第一次作業(yè)三、主觀題(共3道小題)數(shù)據(jù)的物理結(jié)構(gòu)包括的表示和的表示。參考答案：線性結(jié)構(gòu)，非線性結(jié)構(gòu)數(shù)據(jù)邏輯結(jié)構(gòu)包括、和四種，樹(shù)結(jié)構(gòu)和圖結(jié)構(gòu)統(tǒng)稱(chēng)為。參考答案：集合、線性結(jié)構(gòu)、樹(shù)、圖、非線性結(jié)構(gòu)數(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道小題)向一個(gè)長(zhǎng)度為n的順序表中的第i個(gè)元素之前插入一個(gè)元素時(shí)，需要向后移動(dòng)個(gè)元素。參考答案：n-i+1在一個(gè)長(zhǎng)度為n的順序表中刪除第i個(gè)元素時(shí)，需要向前移動(dòng)元素。參考答案：n_i_

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

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

4、儲(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)系，只能素。若頻繁地對(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ù)元素，只需要修改結(jié)點(diǎn)的指針域就可以改變數(shù)據(jù)元素之間的邏輯關(guān)系。在單鏈表、雙向循環(huán)鏈表和單循環(huán)鏈表中，若僅知道指針p指向某結(jié)點(diǎn)，不知道頭指針，能否將結(jié)點(diǎn)p從時(shí)間復(fù)雜度

5、各為多少。參考答案：要實(shí)現(xiàn)刪除p結(jié)點(diǎn)的操作，必須找到其前驅(qū)結(jié)點(diǎn)，修改其指針域的值使其指向p的后繼結(jié)點(diǎn)，以實(shí)因此不知道頭指針就無(wú)法找到結(jié)點(diǎn)p的前驅(qū)結(jié)點(diǎn)。雙向循環(huán)鏈表和單循環(huán)鏈表可以可以實(shí)現(xiàn)刪除p結(jié)點(diǎn)。單循.度為O(n)，雙循環(huán)鏈表刪除P結(jié)點(diǎn)的時(shí)間復(fù)雜度為O(1)。對(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)都要修改頭指針?lè)◤?fù)雜些。其次，帶頭結(jié)點(diǎn)的鏈表結(jié)構(gòu)，初始化后的頭指針就固定了，除撤銷(xiāo)算法外，所有算法都不會(huì)修改頭指針已知一個(gè)線

6、性表用含頭結(jié)點(diǎn)的單鏈表做存儲(chǔ)結(jié)構(gòu)，寫(xiě)一個(gè)算法求單鏈表的長(zhǎng)度。參考答案：intlistlenght(linklistL)intlength=0;P=L-next;while(p)length+;p=p-next;return(length);已知一個(gè)順序表L,其中的元素按值遞增有序排列，設(shè)計(jì)一個(gè)算法插入一個(gè)值為X的元素后保持該順序表仍為0(1)。參考答案：voidinsertsq(sqlistL,elemtypex)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

7、.elemn+1=L.elemn;return;寫(xiě)一個(gè)算法，從順序表中刪除值為X的所有元素。參考答案：voiddelallsq(Sqlist&L)inti=0,j=0;while(jL.length)if(L.elemj!=x)L.elemi+=L.elemj;j+;L.longth=i;第三次作業(yè)三、主觀題(共50道小題)循環(huán)隊(duì)列的引入，目的是為了克服。參考答案：順序隊(duì)列的假溢出區(qū)分循環(huán)隊(duì)列的空與滿(mǎn)有3種方法，它們是、。參考答案：少用一個(gè)元素、設(shè)空滿(mǎn)標(biāo)志、用計(jì)數(shù)器記錄隊(duì)列中元素個(gè)數(shù)TOC o 1-5 h z棧和隊(duì)列的區(qū)別是，參考答案：棧只能在表一端進(jìn)行插入和刪除操作，隊(duì)列限制在表的一端進(jìn)行插

8、入操作，在另一端進(jìn)行刪除操作一個(gè)棧的輸入序列是12345,貝9棧的輸出序列43512是。參考答案：錯(cuò)誤的設(shè)棧采取順序存儲(chǔ)結(jié)構(gòu)，棧中已有卜1個(gè)元素，則第i個(gè)元素進(jìn)棧操作的算法時(shí)間復(fù)雜度是。參考答案：0(1)棧的特點(diǎn)是【】，隊(duì)列的特點(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,4TOC o 1-5 h z若用不帶頭結(jié)點(diǎn)的單鏈表表示棧，則創(chuàng)建一個(gè)空棧要執(zhí)行的操作是。參考答案：top=NULL從循環(huán)隊(duì)列中刪除一個(gè)元素的操作是。參考答案：Q.front二(Q.f

9、ront+1)%QSize從循環(huán)隊(duì)列中插入一個(gè)元素的操作是。參考答案：Q.rear=(Q.rear+1)%QSize判斷鏈隊(duì)列中只有一個(gè)結(jié)點(diǎn)的條件是。參考答案：Q.front-next=二Q.rear如果棧的最大長(zhǎng)度難以估計(jì)，最好使用。參考答案：鏈棧為什么說(shuō)棧是一種后進(jìn)先出表？參考答案：因?yàn)闂Ｊ窍薅ㄔ诒淼囊欢诉M(jìn)行插入和刪除操作，所以后入棧的數(shù)據(jù)元素總是先出棧，所以說(shuō)棧是一對(duì)于一個(gè)棧，其輸入序列是A,B,C,試給出全部可能的輸出序列。參考答案：可能的出棧序列是：ABC、ACB、BAC、BCA、CBA。何謂隊(duì)列上溢？何為假溢出現(xiàn)象？有哪些解決假溢出問(wèn)題的方法，并分別闡述其工作原理。參考答案：隊(duì)列上

10、溢指在隊(duì)列的順序存儲(chǔ)分配中，按照隊(duì)列的操作規(guī)則，需要進(jìn)隊(duì)的元素因找不到合適的存儲(chǔ)單元而假溢出指在隊(duì)列的順序存儲(chǔ)分配中，分配給隊(duì)列的存儲(chǔ)空間有存儲(chǔ)單元未被占用，但按照操作規(guī)則而使進(jìn)象。解決假溢出問(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)%MSize隊(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)

11、后進(jìn)行插入操作，出隊(duì)找到鏈表的頭結(jié)點(diǎn)，入隊(duì)出隊(duì)操作的算法時(shí)間復(fù)雜度均為0(1)。若只設(shè)頭指針，則出隊(duì)操作的算法時(shí)間復(fù)雜度復(fù)雜度為0(n)。深度為k的完全二叉樹(shù)至少有個(gè)結(jié)點(diǎn)，至多有個(gè)結(jié)點(diǎn)。TOC o 1-5 h z參考答案：2k-1,2k-1在一棵二叉樹(shù)中，度為0的結(jié)點(diǎn)個(gè)數(shù)為n0，度為2的結(jié)點(diǎn)個(gè)數(shù)為n2,則有nO二。參考答案：n2+1一棵二叉樹(shù)第i層最多有個(gè)結(jié)點(diǎn)，一棵有n個(gè)結(jié)點(diǎn)的滿(mǎn)二叉樹(shù)共有個(gè)結(jié)點(diǎn)，共有_個(gè)葉結(jié)點(diǎn)。參考答案：2-1,2k1,2k-1根據(jù)二叉樹(shù)的定義，具有3個(gè)結(jié)點(diǎn)的二叉樹(shù)共有種不同形態(tài)，它們分別是有一棵如下圖所示的樹(shù)，回答下列問(wèn)題：TOC o 1-5 h z這棵樹(shù)的根結(jié)點(diǎn)。這棵樹(shù)的

12、葉子結(jié)點(diǎn)是結(jié)點(diǎn)c的度為。這棵樹(shù)的深度是。結(jié)點(diǎn)c的孩子結(jié)點(diǎn)結(jié)點(diǎn)c的雙親結(jié)點(diǎn)是參考答案：ab,e,g,d24efa3樹(shù)與二叉樹(shù)的兩個(gè)主要差別是、參考答案：樹(shù)中結(jié)點(diǎn)的最大度沒(méi)有限制，二叉樹(shù)結(jié)點(diǎn)的最大度限定為2、樹(shù)的結(jié)點(diǎn)無(wú)左右之分，二叉樹(shù)設(shè)有如下圖所示的二叉樹(shù)，給出其前序、中序和后序遍歷結(jié)果。參考答案：前序序列：eadcbifghj中序序列：abcdiefhgj后序序列：bcidahjgfe給出下圖所示的樹(shù)的二叉樹(shù)表示。參考答案：下圖為其樹(shù)的二叉樹(shù)表示。有一份電文共有5個(gè)字符：a,b,c,d,e,它們出現(xiàn)的頻率依次為4,7,5,2,9,構(gòu)造對(duì)應(yīng)的哈夫曼樹(shù)，求哈字符的哈夫曼編碼。參考答案：a：011b：

13、10c：00d：010e：11字符編碼：字符編碼：84.假設(shè)一棵二叉樹(shù)采用順序存儲(chǔ)結(jié)構(gòu)，如下圖所示。05101520eafdgcjhib回答些列問(wèn)題：畫(huà)出二叉樹(shù)表示。寫(xiě)出先序、中序和后序遍歷結(jié)果寫(xiě)出結(jié)點(diǎn)c的雙親結(jié)點(diǎn)和左、右孩子結(jié)點(diǎn)畫(huà)出此二叉樹(shù)還原成森林的圖參考答案：二叉樹(shù)表示如下圖所示。先序序列為：eadcbjfghi中序序列為：acbdjefhgi后序序列為：bcjdahigfe結(jié)點(diǎn)c的雙親結(jié)點(diǎn)是d,左孩子為b,無(wú)右孩子有n個(gè)頂點(diǎn)的無(wú)向圖最多有條邊。參考答案：n(n-l)/2一個(gè)圖的表示法是唯一的，而表示法是不唯一的。參考答案：鄰接矩陣，鄰接表TOC o 1-5 h z具有10個(gè)頂點(diǎn)的無(wú)向圖

14、，邊的總數(shù)最多為。參考答案：45在有n個(gè)頂點(diǎn)的有向圖中，每個(gè)頂點(diǎn)的度最大可達(dá)。參考答案：2(n-l)已知一個(gè)有向圖采用鄰接矩陣表示，計(jì)算第i個(gè)頂點(diǎn)的入度的方法是。參考答案：求第i列非0元素個(gè)數(shù)從占用的存儲(chǔ)空間來(lái)看，對(duì)于稠密圖和稀疏圖，采用鄰接矩陣和鄰接表那個(gè)更好些？參考答案：從占用存儲(chǔ)空間看，稠密圖采用鄰接矩陣更好，稀疏圖采用鄰接表更好。用鄰接矩陣表示圖時(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,則鄰對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖，若采用鄰接表表示，則表頭向量的

15、大小為【】；所有鄰接表參考答案：TOC o 1-5 h zn2e93順序查找含n個(gè)元素的順序表，若查找成功，則比較關(guān)鍵字的次數(shù)最多次；若查找不丿為次。參考答案：n,n+1在含有n個(gè)元素的有序順序表中進(jìn)行二分查找，最大的比較次數(shù)。參考答案：.I_logn_|+1-2用二分查找一個(gè)查找表，該查找表必須具有的特點(diǎn)是。參考答案：順序存儲(chǔ)且關(guān)鍵字有序96.分塊查找發(fā)將待查找的表均勻地分成若干塊且塊中諸記錄的順序可以是任意的，但塊與塊之間。參考答案：關(guān)鍵字有序在分塊查找方法中，首先查找，然后再查找相應(yīng)的。參考答案：關(guān)鍵字表，對(duì)應(yīng)的塊用二叉排序樹(shù)在n個(gè)元素中進(jìn)行查找，最壞情況下查找時(shí)間復(fù)雜度為，最好情況的查

16、找時(shí)間復(fù)雜度為參考答案：o(n)，O(log,n)折半查找的存儲(chǔ)結(jié)構(gòu)僅限于，且是。參考答案：順序存儲(chǔ)結(jié)構(gòu)，關(guān)鍵字有序排列一個(gè)無(wú)序序列可以通過(guò)構(gòu)造一棵樹(shù)而變成有序序列，構(gòu)造樹(shù)的過(guò)程即是對(duì)無(wú)序序列進(jìn)行排序的過(guò)程參考答案：二叉排序畫(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)題依次取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，13每次從無(wú)序子表中取出一個(gè)元素，把它插入到有序子表中恰當(dāng)位置，此種排序方法叫彳排序；若每次大元素，把它交換到有序表的一端，此種排序方法叫彳排序。參考答案：插入:直接選擇每次通過(guò)基準(zhǔn)元素間接比較兩個(gè)元素，不滿(mǎn)足約定要求時(shí)就交換位置，該排序方法叫彳排序；每次使兩序表的排序方法叫做排序。參考答案：快速：歸并排序方法采用二分法的思想，排序方法將數(shù)據(jù)的組織采用完全二叉樹(shù)的結(jié)構(gòu)。參考答案：快速，堆