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

1、數(shù)據(jù)結(jié)構(gòu)填空作業(yè)題答案第1章緒論（已校對無誤）1 ?數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu)和數(shù)據(jù)的運算三方面的內(nèi)容。2 ?程序包括兩個內(nèi)容：數(shù)據(jù)結(jié)構(gòu)和算法。3 .數(shù)據(jù)結(jié)構(gòu)的形式定義為：數(shù)據(jù)結(jié)構(gòu)是一個二元組：DataStructure=（D,S）。4 .數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存儲器內(nèi)的表示，稱為數(shù)據(jù)的存儲結(jié)構(gòu)。5 .數(shù)據(jù)的邏輯結(jié)構(gòu)可以分類為線住結(jié)構(gòu)和非線性結(jié)構(gòu)兩大類。6 .在圖狀結(jié)構(gòu)中，每個結(jié)點的前驅(qū)結(jié)點數(shù)和后繼結(jié)點數(shù)可以有多個。7 .在樹形結(jié)構(gòu)中，數(shù)據(jù)元素之間存在一對多的關(guān)系。8 .數(shù)據(jù)的物理結(jié)構(gòu)，指數(shù)據(jù)元素在計算機中的標識（映象），也即存儲結(jié)構(gòu)。9 .數(shù)據(jù)的邏輯結(jié)構(gòu)包括線性結(jié)構(gòu)、樹形結(jié)構(gòu)

2、禾圖形結(jié)構(gòu)3種類型，樹型結(jié)構(gòu)和有向圖結(jié)構(gòu)合稱為非線性結(jié)構(gòu)010 .順序存儲結(jié)構(gòu)是把邏輯上相鄰的結(jié)點存儲在物理上連續(xù)的存儲單元里,結(jié)點之間的邏輯關(guān)系由存儲單元位置的鄰接關(guān)系來體現(xiàn)。11 .鏈式存儲結(jié)構(gòu)是把邏輯上相鄰的結(jié)點存儲在物理上任意的存儲單元里，節(jié)點之間的邏輯關(guān)系由附加的指針域來體現(xiàn)。12 .數(shù)據(jù)的存儲結(jié)構(gòu)可用4種基本的存儲方法表示，它們分別是順序存儲、鏈式存儲、索引存儲和散列存儲。13 .線性結(jié)構(gòu)反映結(jié)點間的邏輯關(guān)系是一對一的，非線性結(jié)構(gòu)反映結(jié)點間的邏輯關(guān)系是一對多或多對多。14 .數(shù)據(jù)結(jié)構(gòu)在物理上可分為順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)。15 .我們把每種數(shù)據(jù)結(jié)構(gòu)均視為抽象類型，它不但定義了數(shù)據(jù)

3、的表示方式，還給出了處理數(shù)據(jù)的實現(xiàn)方法。16 .數(shù)據(jù)元素可由若干個數(shù)據(jù)項組成。17 .算法分析的兩個主要方面是時回復(fù)雜度和空間復(fù)雜度。18 .一個算法的時間復(fù)雜度是用該算法所消耗的時間的多少來度量的，一個算法的空間復(fù)雜度是用該算法在運行過程中所占用的存儲空間的大小來度量的。19 .算法具有如下特點：有窮性、確定性、可行性、輸入、輸出。20. 對于某一類特定的問題，算法給出了解決問題的一系列操作，每一操作都有它的確切的定義，并在有窮時間內(nèi)計算出結(jié)果。21.下面程序段的時間復(fù)雜度為3Li=1；while(i<=n)i=i*3;第2章線性表（已校對無誤）1 .一線性表表示如下：（ai,a2,，

4、ai-i,a,a+i,，an）,其中每個a代表一個數(shù)據(jù)元素（或結(jié)點）。ai稱為起始結(jié)點，an稱為終端.結(jié)點，i稱為a在線性表中的位置（或序號）。對任意一對相鄰結(jié)點ai,ai+i,（Ki<n）,a稱為a+i的直接前驅(qū),a+i稱為a的直接后繼。2 .對一個長度為n的線性表，要刪除第i個元素，則在順序表示的情況下，計算復(fù)雜性為0（n）,在鏈式表示的情況下，計算復(fù)雜性為0D3 .在一個長度為n的順序表中，向第i個元素（Ki<n）之前插入一個新元素時，需向后移動_ni+i個）o4.順序表中邏輯上相鄰的元素在物理位置上一定相連。10n2個結(jié)點，具體的移動次數(shù)取決于_表09，因此，順序表也稱為隨

5、機訪問5 .在n個結(jié)點的順序表中插入一個結(jié)點需平均移動長n和插入位置i。6 .在順序表中訪問任意一個結(jié)點的時間復(fù)雜度均為的數(shù)據(jù)結(jié)構(gòu)。7 .順序表相對于鏈表的優(yōu)點有隨機訪問和空間利用率高。8 .在長度為n的順序表中插入一個元素的時間復(fù)雜度為0山。9 .在帶有頭結(jié)點的單鏈表L中，若要刪除第一個結(jié)點，則須執(zhí)行下列三條語句：U=L->next;L->next=U->next;free（U）。直接前驅(qū) 結(jié)點中的指針指示。10 .鏈表相對于順序表的優(yōu)點有插入和刪除操作方便。11 .在單鏈表中除首結(jié)點外，任意結(jié)點的存儲位置都由12 .在n個結(jié)點的單鏈表中要刪除已知結(jié)點*p,需找到它的直接前

6、驅(qū)結(jié)點的地址,其時間復(fù).雜度為O（n）o13 .單鏈表中設(shè)置頭結(jié)點的作用是簡化操作、減少邊界條件的判14.斷O在帶表頭結(jié)點的單鏈表中，當(dāng)刪除某一指定結(jié)點時，必須找到該結(jié)點的前驅(qū)結(jié)點。15 .在雙鏈表中，每個結(jié)點有兩個指針域，一個指向前驅(qū)結(jié)點一,另一個指向后續(xù)結(jié)點一。16 .帶頭結(jié)點的單鏈表L為空的判定條件是L->next=NULL,不帶頭結(jié)點的單鏈表L為空的判定條件是L=NULL。17 .在單鏈表中，指針p所指結(jié)點為最后一個結(jié)點的條件是p->next=NULL。18 .循環(huán)鏈表的最大優(yōu)點是從表中任意結(jié)點出發(fā)都可訪問到表中每一個元素（或從表中任意結(jié)點出發(fā)都可遍歷整個鏈表）。19 .設(shè)

7、rear是指向非空、帶頭結(jié)點的循環(huán)單鏈表的尾指針，則該鏈表首結(jié)點的存儲位置是rear->next->next。20 .帶頭結(jié)點的雙向循環(huán)表L為空表的條件是L->prior=L->next。21 .在循環(huán)鏈表中，可根據(jù)任一結(jié)點的地址遍歷整個鏈表，而單鏈表中需知道頭指針才能遍歷整個鏈表。22 .將兩個各有n個元素的有序表歸并成一個有序表，其最少的比較次數(shù)是1o第3章棧和隊列（已校對無誤）1 .棧又稱為后進先出表，隊列又稱為先進先出表。2 .向一個順序棧插入一個元素時，首先使棧頂指針后移一個位置，然后把待插入元素寫入（或插入）到這個位置上。3 .從一個棧刪除元素時，需要前移一

8、位棧頂指針。4 .在一個順序棧中，若棧頂指針等于二1,則為空棧；若棧頂指針等于maxSize1,則為滿棧。5 .在一個鏈式棧中，若棧頂指針等于NULL,則為空棧：在一個鏈式隊列中，若隊頭指針與隊尾指針的值相同，則表示該隊列為空或該隊列只含有一個結(jié)點。6 .向一個鏈式棧插入一個新結(jié)點時，首先把棧頂指針的值賦給新結(jié)點的指針域,然后把新結(jié)點的存儲位置賦給棧頂指針。7?在求表達式值的算符優(yōu)先算法中使用的主要數(shù)據(jù)結(jié)構(gòu)是棧。8 .設(shè)有一個順序棧S,元素s1,s2,s3,s4,s5,s6依次進棧，如果6個元素的出棧順序為s2,s3,s4,s6,s5,s1,則順序棧的容量至少為3。9 .設(shè)有一個空棧，現(xiàn)輸入序

9、列為1,2,3,4,5。經(jīng)過push,push,pop,push,pop,push,pop,push后，輸出序列是234o10 .在按算符優(yōu)先法求解表達式3-1+5*2時，最先執(zhí)行的運算是X,最后執(zhí)行的運算是11 .在棧的ADT定義中，除初始化操作外，其他基本操作的初始條件都要求棧存在。12 .僅允許在同一端進行插入和刪除的線性表稱為棧。13 .在順序棧s中，棧為空的條件是s.top=s.base,棧為滿的條件是s.top-s.base>=s.stacksize。14 .設(shè)有算術(shù)表達式x+a*（yb）c/d,該表達式的前綴表示為一+x*ayb/cd。后綴表示為xayb*+cd/。1234

10、,為了得到1342出棧順序,15 .用S表示入棧操作，X表示出棧操作，若元素入棧順序為相應(yīng)的S、X操作串為SXSSXSXX16 .向一個棧頂指針為top的鏈式棧中插入一個新結(jié)點*p時，應(yīng)執(zhí)行p->link=top和top=p操作17 .從一個棧頂指針為top的非空鏈式棧中刪除結(jié)點并不需要返回棧頂結(jié)點的值和回收結(jié)點時，應(yīng)執(zhí)行top=top->link操作。18 .設(shè)有一個空棧，棧頂指針為1000H（十六進制?，F(xiàn)有輸入序列為1,2,3,4,5,經(jīng)過PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，輸出序列是2金，而棧頂指針是100CH。設(shè)棧為順序棧，每個元素占4個字

11、節(jié)。19 .在作入棧運算時應(yīng)先判別棧是否逋：在作出棧運算時應(yīng)先判別棧是否空。10.用一個大小為1000的數(shù)組來實現(xiàn)循環(huán)隊列，當(dāng)前rear和front的值分別為0和994,若要達到隊滿的條件,還需要繼續(xù)入隊的元素個數(shù)是993 o20 .隊列的插入操作在隊屋 進行，刪除操作在21 .在一個循環(huán)隊列Q中，判斷隊空的條件為（Q.rear+ 1） % maxSize=Q.fr ont 。22 .向一個循環(huán)隊列中插入元素時，需要首先移動 插入）新插入的元素。23 .當(dāng)用長度為n的數(shù)組順序存儲一個棧時，若用 top = = 0 O隊頭進行。Q.front=Q.rear ,判斷隊滿的條件為隊尾指針,然后再向所

12、指位置寫入（或top=n表示?？?，則表示棧滿的條件為24.循環(huán)隊列的引入，目的是為了克服假溢出時大量移動數(shù)據(jù)元素第4章串（已校對無誤）1 .兩個串相等的充分必要條件是兩個串的長度相等且對應(yīng)位置的字符相同。2 .空格串是由一個或多個空格字符組成的串:其長度等干其包含的空格個數(shù)3 .模式串'abaabade的next函數(shù)值為01122341補充：1 .串的兩種最基本的存儲方式是順序存儲方式和鏈接存儲方式。2 .空串是零個字符的串:其長度等干變。3 .組成串的數(shù)據(jù)元素只能是包。4 .串是一種特殊的線性表，其特殊性表現(xiàn)在其數(shù)據(jù)元素都是字符。第5章數(shù)組（已校對無誤）1 .將下三角矩陣A1.8,1

13、.8的下三角部分逐行地存儲到起始地址為1000的內(nèi)存單元中，已知每個元素占4個單元，則元素A7,5的地址為1100。2 .二維數(shù)組A0,9,。19采用列序為主方式存儲，每個元素占一個存儲單元，并且元素A0,0的存儲地址是200,則元素A6,12的地址是332。3 .二維數(shù)組A1020,5-10采用行序為主方式存儲，每個元素占4個存儲單元，并且元素A10,5的存儲地址是1000,則元素A18,9的地址是1208。補充：1 .一維數(shù)組的邏輯結(jié)構(gòu)是線性結(jié)構(gòu),存儲結(jié)構(gòu)是順序存儲結(jié)構(gòu)。2 .對于二維數(shù)組或多維數(shù)組，分為按以行為主序和按以列為主序兩種不同的存儲方式存儲。3 .對矩陣壓縮存儲是為了節(jié)省存儲空

14、間。4 .二維數(shù)組是一種非線性結(jié)構(gòu)，其中的每一個數(shù)組元素最多有二個直接前驅(qū)（或直接后繼）第6章樹（已校對無誤）5 .結(jié)點最少的樹為只有一個結(jié)點的樹,結(jié)點最少的二叉樹為空的二叉樹。6 .根據(jù)二叉樹的定義，具有三個結(jié)點的二叉樹有5種不同的形態(tài)，它們分別是。7 .具有n個結(jié)點的完全二叉樹的深度為。8 .以數(shù)據(jù)集4,5,6,7,10,12,18為結(jié)點權(quán)值所構(gòu)造的哈夫曼樹為需用圖示,其帶權(quán)路徑長度為165。9 .哈夫曼樹是帶權(quán)路徑長度量翅的樹，通常權(quán)值較大的結(jié)點離根較近。10 .在先序遍歷二叉樹的序列中,任何結(jié)點的子樹上的所有結(jié)點，都是直接跟在該結(jié)點之后。第7章圖（已校對無誤）1.n個頂點的連通圖至少有

15、n1條邊2?在無權(quán)圖G的鄰接矩陣A中，若（vi,vj）或vi,vj屬于圖G的邊集，則對應(yīng)元素Aij等于一,否則在無向圖G的鄰接矩陣A中，若Aij等于0。3.等于1,Aji等于14.已知圖G的鄰接表如下圖所示，其從頂點v1出發(fā)的深度優(yōu)先搜索序列為v1v2v3v6v5v4,其從頂點v1出發(fā)的廣度優(yōu)先搜索序列為v1v2v5v4v3v6。5.設(shè) x,y是圖G中的兩頂點，貝U （ x, 丫）與（y, x）被認為無向,但x, 丫與y, x是有向的兩條弧6 .已知一個圖的鄰接矩陣表示，刪除所有從i個結(jié)點出發(fā)的邊的方法是將矩陣的第i行全部置為0o7 .在有向圖的鄰接矩陣上，由第i行可得到第i個結(jié)點的出度，而由

16、第j列可得到第個結(jié)點的入度8 .在無向圖中，如果從頂點v到頂點v有路徑，則稱v和v'是連通第8章查找（已校對無誤）1 .順序查找法的平均查找長度為（n+1）12;哈希表查找法采用鏈接法處理沖突時的平均查找長度為1+?o2 .在各種查找方法中，平均查找長度與結(jié)點個數(shù)n無關(guān)的查找方法是哈希表查找法。3 .二分查找的存儲結(jié)構(gòu)僅限于有序的順序存儲結(jié)構(gòu)。4 .長度為255的表，采用分塊查找法，每塊的最佳長度是15o5 .N個記錄的有序順序表中進行折半查找，最大的比較次數(shù)是10g?N?。6 .對于長度為n的線性表，若進行順序查找，則時間復(fù)雜度為O（n）;若采用二分法查找，則時間復(fù)雜度為0伽如）;若

17、采用分塊查找（假定總塊數(shù)和每塊長度均接近花），則時間復(fù)雜度為O（n）Q:a的值越小，貝U仝7 .在散列存儲中，裝填因子a的值越大，則存取元素時發(fā)生沖突的可能性就越大取元素時發(fā)生沖突的可能性就越小8 .對于二叉排序樹的查找，若根結(jié)點元素的鍵值大于被查元素的鍵值，則應(yīng)該在二叉樹的左子樹上繼續(xù)查找。9 .高度為8的平衡二叉樹至少有_54個結(jié)點。10 .在散列函數(shù)H（key）=key%p中，p應(yīng)取素數(shù)。第9章排序(已校對無誤)1 .在對一組記錄(54,38,96,23,15,72,60,45,83)進行直接插入排序時，當(dāng)把第8個記錄45插入到有序表時，為尋找插入位置需比較5_次2 .對于關(guān)鍵字序列(12,13,11,18,60,15,7,20,25,100),用篩選法建堆，必須從鍵值為_60的關(guān)鍵字開始。3 .對n個記錄的表r1川進行簡單選擇排序，所需要進行的關(guān)鍵字間的比較次數(shù)為n(n112。4 .在插入排序、希爾排序、選擇排序、快速