《數(shù)據(jù)結(jié)構(gòu)》填空作業(yè)題(答案)

PAGEPAGE3《數(shù)據(jù)結(jié)構(gòu)》填空作業(yè)題答案第1章緒論（已校對(duì)無(wú)誤）1．?dāng)?shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算三方面的內(nèi)容。2．程序包括兩個(gè)內(nèi)容：數(shù)據(jù)結(jié)構(gòu)和算法。3.數(shù)據(jù)結(jié)構(gòu)的形式定義為：數(shù)據(jù)結(jié)構(gòu)是一個(gè)二元組：DataStructure=（D，S）。4.數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器內(nèi)的表示，稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。5.數(shù)據(jù)的邏輯結(jié)構(gòu)可以分類為線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩大類。6.在圖狀結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)數(shù)和后繼結(jié)點(diǎn)數(shù)可以有多個(gè)。7.在樹(shù)形結(jié)構(gòu)中，數(shù)據(jù)元素之間存在一對(duì)多的關(guān)系。8.數(shù)據(jù)的物理結(jié)構(gòu)，指數(shù)據(jù)元素在計(jì)算機(jī)中的標(biāo)識(shí)（映象），也即存儲(chǔ)結(jié)構(gòu)。9.數(shù)據(jù)的邏輯結(jié)構(gòu)包括線性結(jié)構(gòu)、樹(shù)形結(jié)構(gòu)和圖形結(jié)構(gòu)3種類型，樹(shù)型結(jié)構(gòu)和有向圖結(jié)構(gòu)合稱為非線性結(jié)構(gòu)。10.順序存儲(chǔ)結(jié)構(gòu)是把邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理上連續(xù)的存儲(chǔ)單元里，結(jié)點(diǎn)之間的邏輯關(guān)系由存儲(chǔ)單元位置的鄰接關(guān)系來(lái)體現(xiàn)。11.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是把邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理上任意的存儲(chǔ)單元里，節(jié)點(diǎn)之間的邏輯關(guān)系由附加的指針域來(lái)體現(xiàn)。12.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)可用4種基本的存儲(chǔ)方法表示，它們分別是順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)、索引存儲(chǔ)和散列存儲(chǔ)。13.線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是一對(duì)一的，非線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是一對(duì)多或多對(duì)多。14.數(shù)據(jù)結(jié)構(gòu)在物理上可分為順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。15.我們把每種數(shù)據(jù)結(jié)構(gòu)均視為抽象類型，它不但定義了數(shù)據(jù)的表示方式，還給出了處理數(shù)據(jù)的實(shí)現(xiàn)方法。16.數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)組成。17.算法分析的兩個(gè)主要方面是時(shí)間復(fù)雜度和空間復(fù)雜度。18.一個(gè)算法的時(shí)間復(fù)雜度是用該算法所消耗的時(shí)間的多少來(lái)度量的，一個(gè)算法的空間復(fù)雜度是用該算法在運(yùn)行過(guò)程中所占用的存儲(chǔ)空間的大小來(lái)度量的。19.算法具有如下特點(diǎn)：有窮性、確定性、可行性、輸入、輸出。20.對(duì)于某一類特定的問(wèn)題，算法給出了解決問(wèn)題的一系列操作，每一操作都有它的確切的定義，并在有窮時(shí)間內(nèi)計(jì)算出結(jié)果。21.下面程序段的時(shí)間復(fù)雜度為㏒3n。i=1；while(i<=n)i=i﹡3；第2章線性表（已校對(duì)無(wú)誤）1.一線性表表示如下：（a1，a2，…，ai-1，ai，ai+1，…，an），其中每個(gè)ai代表一個(gè)數(shù)據(jù)元素（或結(jié)點(diǎn)）。a1稱為起始結(jié)點(diǎn)，an稱為終端結(jié)點(diǎn)，i稱為ai在線性表中的位置（或序號(hào)）。對(duì)任意一對(duì)相鄰結(jié)點(diǎn)ai，ai+1，（1≤i≤n），ai稱為ai+1的直接前驅(qū)，ai+1稱為ai的直接后繼。2.對(duì)一個(gè)長(zhǎng)度為n的線性表，要?jiǎng)h除第i個(gè)元素，則在順序表示的情況下，計(jì)算復(fù)雜性為O(n)，在鏈?zhǔn)奖硎镜那闆r下，計(jì)算復(fù)雜性為O(1)。3.在一個(gè)長(zhǎng)度為n的順序表中，向第i個(gè)元素（1≤i≤n）之前插入一個(gè)新元素時(shí)，需向后移動(dòng)n－i＋1個(gè)元素。4.順序表中邏輯上相鄰的元素在物理位置上一定相連。5.在n個(gè)結(jié)點(diǎn)的順序表中插入一個(gè)結(jié)點(diǎn)需平均移動(dòng)n/2個(gè)結(jié)點(diǎn)，具體的移動(dòng)次數(shù)取決于表長(zhǎng)n和插入位置i。6.在順序表中訪問(wèn)任意一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度均為O(1)，因此，順序表也稱為隨機(jī)訪問(wèn)的數(shù)據(jù)結(jié)構(gòu)。7.順序表相對(duì)于鏈表的優(yōu)點(diǎn)有隨機(jī)訪問(wèn)和空間利用率高。8.在長(zhǎng)度為n的順序表中插入一個(gè)元素的時(shí)間復(fù)雜度為O(n)。9.在帶有頭結(jié)點(diǎn)的單鏈表L中，若要?jiǎng)h除第一個(gè)結(jié)點(diǎn)，則須執(zhí)行下列三條語(yǔ)句：U＝L->next；L->next=U->next；free（U）。10.鏈表相對(duì)于順序表的優(yōu)點(diǎn)有插入和刪除操作方便。11.在單鏈表中除首結(jié)點(diǎn)外，任意結(jié)點(diǎn)的存儲(chǔ)位置都由直接前驅(qū)結(jié)點(diǎn)中的指針指示。12.在n個(gè)結(jié)點(diǎn)的單鏈表中要?jiǎng)h除已知結(jié)點(diǎn)*p，需找到它的直接前驅(qū)結(jié)點(diǎn)的地址，其時(shí)間復(fù)雜度為O(n)。13．單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是簡(jiǎn)化操作，減少邊界條件的判斷。14．在帶表頭結(jié)點(diǎn)的單鏈表中，當(dāng)刪除某一指定結(jié)點(diǎn)時(shí)，必須找到該結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)。15.在雙鏈表中，每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，一個(gè)指向前驅(qū)結(jié)點(diǎn)，另一個(gè)指向后續(xù)結(jié)點(diǎn)。16.帶頭結(jié)點(diǎn)的單鏈表L為空的判定條件是L->next==NULL，不帶頭結(jié)點(diǎn)的單鏈表L為空的判定條件是L==NULL。17.在單鏈表中，指針p所指結(jié)點(diǎn)為最后一個(gè)結(jié)點(diǎn)的條件是p->next==NULL。操作。17.從一個(gè)棧頂指針為top的非空鏈?zhǔn)綏Ｖ袆h除結(jié)點(diǎn)并不需要返回棧頂結(jié)點(diǎn)的值和回收結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行top＝top->link操作。18.設(shè)有一個(gè)空棧，棧頂指針為1000H（十六進(jìn)制。現(xiàn)有輸入序列為1，2，3，4，5，經(jīng)過(guò)PUSH，PUSH，POP，PUSH，POP，PUSH，PUSH之后，輸出序列是2，3，而棧頂指針是100CH。設(shè)棧為順序棧，每個(gè)元素占4個(gè)字節(jié)。19.在作入棧運(yùn)算時(shí)應(yīng)先判別棧是否滿；在作出棧運(yùn)算時(shí)應(yīng)先判別棧是否空。10.用一個(gè)大小為1000的數(shù)組來(lái)實(shí)現(xiàn)循環(huán)隊(duì)列，當(dāng)前rear和front的值分別為0和994，若要達(dá)到隊(duì)滿的條件，還需要繼續(xù)入隊(duì)的元素個(gè)數(shù)是993。20.隊(duì)列的插入操作在隊(duì)尾進(jìn)行，刪除操作在隊(duì)頭進(jìn)行。21.在一個(gè)循環(huán)隊(duì)列Q中，判斷隊(duì)空的條件為Q.front==Q.rear，判斷隊(duì)滿的條件為(Q.rear＋1)％maxSize==Q.front。22.向一個(gè)循環(huán)隊(duì)列中插入元素時(shí)，需要首先移動(dòng)隊(duì)尾指針，然后再向所指位置寫(xiě)入（或插入）新插入的元素。23.當(dāng)用長(zhǎng)度為n的數(shù)組順序存儲(chǔ)一個(gè)棧時(shí)，若用top==n表示棧空，則表示棧滿的條件為top==0。24.循環(huán)隊(duì)列的引入，目的是為了克服假溢出時(shí)大量移動(dòng)數(shù)據(jù)元素。第4章串（已校對(duì)無(wú)誤）1.兩個(gè)串相等的充分必要條件是兩個(gè)串的長(zhǎng)度相等且對(duì)應(yīng)位置的字符相同。2.空格串是由一個(gè)或多個(gè)空格字符組成的串，其長(zhǎng)度等于其包含的空格個(gè)數(shù)。3.模式串′abaabade′的next函數(shù)值為01122341補(bǔ)充：1.串的兩種最基本的存儲(chǔ)方式是順序存儲(chǔ)方式和鏈接存儲(chǔ)方式。2.空串是零個(gè)字符的串，其長(zhǎng)度等于零。3.組成串的數(shù)據(jù)元素只能是字符。4.串是一種特殊的線性表，其特殊性表現(xiàn)在其數(shù)據(jù)元素都是字符。第5章數(shù)組（已校對(duì)無(wú)誤）1.將下三角矩陣A[1..8，1..8]的下三角部分逐行地存儲(chǔ)到起始地址為1000的內(nèi)存單元中，已知每個(gè)元素占4個(gè)單元，則元素A[7，5]的地址為1100。2.二維數(shù)組A[0…9，0…19]采用列序?yàn)橹鞣绞酱鎯?chǔ)，每個(gè)元素占一個(gè)存儲(chǔ)單元，并且元素A[0，0]的存儲(chǔ)地址是200，則元素A[6，12]的地址是332。3.二維數(shù)組A[10…20，5…10]采用行序?yàn)橹鞣绞酱鎯?chǔ)，每個(gè)元素占4個(gè)存儲(chǔ)單元，并且元素A[10，5]的存儲(chǔ)地址是1000，則元素A[18，9]的地址是1208。補(bǔ)充：1.一維數(shù)組的邏輯結(jié)構(gòu)是線性結(jié)構(gòu)，存儲(chǔ)結(jié)構(gòu)是順序存儲(chǔ)結(jié)構(gòu)。2.對(duì)于二維數(shù)組或多維數(shù)組，分為按以行為主序和按以列為主序兩種不同的存儲(chǔ)方式存儲(chǔ)。3.對(duì)矩陣壓縮存儲(chǔ)是為了節(jié)省存儲(chǔ)空間。4.二維數(shù)組是一種非線性結(jié)構(gòu)，其中的每一個(gè)數(shù)組元素最多有二個(gè)直接前驅(qū)（或直接后繼）。第6章樹(shù)（已校對(duì)無(wú)誤）4.結(jié)點(diǎn)最少的樹(shù)為只有一個(gè)結(jié)點(diǎn)的樹(shù)，結(jié)點(diǎn)最少的二叉樹(shù)為空的二叉樹(shù)。5.根據(jù)二叉樹(shù)的定義，具有三個(gè)結(jié)點(diǎn)的二叉樹(shù)有5種不同的形態(tài)，它們分別是。6.具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為。8.以數(shù)據(jù)集{4，5，6，7，10，12，18}為結(jié)點(diǎn)權(quán)值所構(gòu)造的哈夫曼樹(shù)為需用圖示，其帶權(quán)路徑長(zhǎng)度為165。9.哈夫曼樹(shù)是帶權(quán)路徑長(zhǎng)度最短的樹(shù)，通常權(quán)值較大的結(jié)點(diǎn)離根較近。10.在先序遍歷二叉樹(shù)的序列中，任何結(jié)點(diǎn)的子樹(shù)上的所有結(jié)點(diǎn)，都是直接跟在該結(jié)點(diǎn)之后。第7章圖（已校對(duì)無(wú)誤）1．n個(gè)頂點(diǎn)的連通圖至少有n－1條邊。2．在無(wú)權(quán)圖G的鄰接矩陣A中，若（vi，vj）或〈vi，vj〉屬于圖G的邊集，則對(duì)應(yīng)元素A[i][j]等于1，否則等于0。3.在無(wú)向圖G的鄰接矩陣A中，若A[i][j]等于1，A[j][i]等于1。4.已知圖G的鄰接表如下圖所示，其從頂點(diǎn)v1出發(fā)的深度優(yōu)先搜索序列為v1v2v3v6v5v4，其從頂點(diǎn)v1出發(fā)的廣度優(yōu)先搜索序列為v1v2v5v4v3v6。V1V1v2v3v4^v5v6^V2V5V4^v3V5^V4V6V3^V6^5.設(shè)x，y是圖G中的兩頂點(diǎn)，則（x，y）與（y，x）被認(rèn)為無(wú)向，但〈x，y〉與〈y，x〉是有向的兩條弧。6.已知一個(gè)圖的鄰接矩陣表示，刪除所有從i個(gè)結(jié)點(diǎn)出發(fā)的邊的方法是將矩陣的第i行全部置為0。7.在有向圖的鄰接矩陣上，由第i行可得到第i個(gè)結(jié)點(diǎn)的出度，而由第j列可得到第j個(gè)結(jié)點(diǎn)的入度。8.在無(wú)向圖中，如果從頂點(diǎn)v到頂點(diǎn)v′有路徑，則稱v和v′是連通。第8章查找（已校對(duì)無(wú)誤）1.順序查找法的平均查找長(zhǎng)度為（n＋1）/2；哈希表查找法采用鏈接法處理沖突時(shí)的平均查找長(zhǎng)度為1＋？。2.在各種查找方法中，平均查找長(zhǎng)度與結(jié)點(diǎn)個(gè)數(shù)n無(wú)關(guān)的查找方法是哈希表查找法。3.二分查找的存儲(chǔ)結(jié)構(gòu)僅限于有序的順序存儲(chǔ)結(jié)構(gòu)。4.長(zhǎng)度為255的表，采用分塊查找法，每塊的最佳長(zhǎng)度是15。5.N個(gè)記錄的有序順序表中進(jìn)行折半查找，最大的比較次數(shù)是㏒2N？。6.對(duì)于長(zhǎng)度為n的線性表，若進(jìn)行順序查找，則時(shí)間復(fù)雜度為O(n)；若采用二分法查找，則時(shí)間復(fù)雜度為O(㏒2n)；若采用分塊查找（假定總塊數(shù)和每塊長(zhǎng)度均接近），則時(shí)間復(fù)雜度為O(n)。7.在散列存儲(chǔ)中，裝填因子a的值越大，則存取元素時(shí)發(fā)生沖突的可能性就越大；a的值越小，則存取元素時(shí)發(fā)生沖突的可能性就越小。8.對(duì)于二叉排序樹(shù)的查找，若根結(jié)點(diǎn)元素的鍵值大于被查元素的鍵值，則應(yīng)該在二叉樹(shù)的左子樹(shù)上繼續(xù)查找。9.高度為8的平衡二叉樹(shù)至少有54個(gè)結(jié)點(diǎn)。10.在散列函數(shù)H（key）=key%p中，p應(yīng)取素?cái)?shù)。第9章排序（已校對(duì)無(wú)誤）1.在對(duì)一組記錄（54，38，96，23，15，72，60，45，83）進(jìn)行直接插入排序時(shí)，當(dāng)把第8個(gè)記錄45插入到有序表時(shí)，為尋找插入位置需比較5次。2.對(duì)于關(guān)鍵字序列（12，13，11，18，60，15，7，20，25，100），用篩選法建堆，必須從鍵值為60的關(guān)鍵字開(kāi)始。3.對(duì)n個(gè)記錄的表r[1…n]進(jìn)行簡(jiǎn)單選擇排序，所需要進(jìn)行的關(guān)鍵字間的比較次數(shù)為n(n－1)/2。4.在插入排序、希爾排序、選擇排序、快速排序、堆排序、歸并排序和基數(shù)排序中，排序是不穩(wěn)定的有希爾排序、選擇排序、快