華南理工大學(xué)網(wǎng)絡(luò)教育學(xué)院數(shù)據(jù)結(jié)構(gòu)同步練習(xí)冊答案

1、第1章緒論習(xí)題11.1什么是數(shù)據(jù)、數(shù)據(jù)元素、原子元素？，它們有何區(qū)別？。答：數(shù)據(jù)：用以描述客觀事物的數(shù)、字符以及所有能被計算機接受和處理的符號的集合 稱為數(shù)據(jù)。例如整數(shù)、實數(shù)、字符、字符串、表格及各種圖像、聲音等。數(shù)據(jù)元素：就是數(shù) 據(jù)的基本單位，在某些情況下，數(shù)據(jù)元素也稱為元素、結(jié)點、頂點、記錄。數(shù)據(jù)元素有時可 以由若干數(shù)據(jù)項組成。原子元素是物理學(xué)的概念。1.2分析下列程序段的運行時間(時間復(fù)雜度)。void mysteiy (mt n) mt i,j, k,for(i=l;i<n; i卄)foi (j = i+l, j<= n, j+)for (k = l;k<=j;k+)

2、;)答：0(2)void odd (int n) int 1, j, x = 0, y = 0;foi (1 =1, i <= li, i卄)if odd(i) foiQ = i, j <= n, j+)x+;for( j = l;j<= i; j+-b)y十)答：0(1?)void lecuisive (int n) if (n <= 1) leturn 1,else letinn (recursive (n -1)十 recuisive(n -1);)答：0(11)1.3設(shè)舁為正整數(shù)，試確定下列各程序段中帶標(biāo)號的語句的頻度。(1) int 1 =l,k= 0：whi

3、le (i <= n-1) k = k十10*i： i = i+l： 答：n-1(2丿 int 1 -1, j - 0；wlule (i+j) <= n)if (i>i)卄七else 1十十；答：ii/2(3丿 int 1 =l,k= 0：while (1 <= u) k = k+10h;i卄；)答：11-1解析:1=1;/Ik=O,/lwlule(i<n) /nk=k+10*i,/n-l1+; /ll-l)由以上列出的各語句的頻度，可得該程序段的時間消耗：T (n)= 1+1 +n+ (n-1)+(n-1 )=3n可表示為T(n)=O(n)(4丿 100：wlu

4、le (v > 0) if (x> 100) x = x -10, v;)else x十十；答：100解析：x=91;/lv=100, /Iv4ule(v>0) /1101if(x>100)/1100 x=x-10,/100y;/100)elsex-H-; /1000以上程序段右側(cè)列出了執(zhí)行次數(shù)。該程序段的執(zhí)行時間為：T(n)=O(l)(5) mtx- 0,for (int 1 =1; 1 <= n; i卄)for (int j=l, j<=i, j+) for (int k = 1; k <= j; k卄)x卄;答：ir/2+ii(6) int x

5、= n, y = 0,/ n> 1while (x >= (y+l)*(v+l) v十十;答：yfy-1解析：由x=n且x的值在程序中不變，又wiule的循環(huán)條件(x>=(y十l)*(y十1)可知：當(dāng) (y+i)*(v+i)剛超過a的值時退出循環(huán)。fb(y4-l)*(y4-l)<n 得：yvM0.5-l所以，該程序段的執(zhí)行時間為：向下取整(110.5-1)第2章線性表習(xí)題22.1描述以下三個概念的區(qū)別：頭指針、頭結(jié)點、首元結(jié)點。此外敘述有序表的特性何在?， 以及向量與有序表的異同點？，頭指針變量和頭結(jié)點的作用？。并比較順序存儲結(jié)構(gòu)和鏈?zhǔn)酱?儲結(jié)構(gòu)的優(yōu)缺點。答：首元結(jié)點是

6、指鏈表中的第一個結(jié)點，也就是沒有直接前驅(qū)的那個結(jié)點。鏈表的頭指 針是一指向鏈表開始結(jié)點的指引(沒有頭結(jié)點時)。單鏈表由頭指針唯一確定，因此單鏈表可 以用頭指針的名字來命名。頭結(jié)點是人為地在鏈表做開始結(jié)點之前附加的一個結(jié)點。有了頭 結(jié)點之后.頭指針指向頭結(jié)點，不論鏈表是否為空，頭指針總是非空.而且頭指針的設(shè)置使 得對鏈表的第一個位置的操作與在表其他位置上的操作一致(都是在某一結(jié)點之后)。2.2試寫出將鏈表L從某元素R處分成兩個鏈表L和K的算法。R為K表的第一個元素。答：提示：鏈表最終將分成兩個鏈表。處理好L的尾結(jié)點(即R的前驅(qū)結(jié)點)，和K的 頭結(jié)點(R)。void depaii_Node(Nod

7、e * head,mt R,Node *head_K)Node *p=head,*temp,while (p) if(p->data=R) break, te j)p=p,p=p->next,)tejnp->next=NUll;liead_k->next=p,)23給定一個n項元素的線性表V,寫一個過程，將元素排列的次序顛倒過來。要求占用原 來的空間，并且用順序表和單表兩種方法表示(要求用最少的附加空間來完成)。答：假設(shè)向量A的數(shù)據(jù)元素存于一維向量“c C0.R-1中，算法可為:int invert ( L ) sequenlist * L;int i;八逆置向童n*/

8、"L是順斥表類型指針變量，其口一個域用于存放一維向量datatype x;( *L ) -last /*last用丁描示向量的最:后一個元素所在的位置*/ for ( L = 0； l < k%2; i + + ) x= ( *L)<veci;(*L) <veciJ = (*L> .vecfk-i+1 ； (*L)vec(k-i+YJ-x;1return ( 1 )： /,Tmver t"/void LinkL st_xcversc (Link list 61) 徒表的就地逆宣；為簡化算法'假設(shè)衣忙大于L 匸一>nexL；q=p->

9、;nexL；s=q->next;p->next=NULL;while (s->next) q->next=p;p=q；q = s; s=s->nex;/ /把L的元素逐個插入新表表頭Iq->next-p;>ne2ct-q;A- >n;1/Linklist reverse2.4已知單鏈表L中的結(jié)點是按值非遞減有序排列的。試寫一算法將值為x的結(jié)結(jié)點插入表L 中，使得L仍然有序。答：因已知順序表L是按值非遞減有序表，所以只要從頭找起找到第一個比它大(或相等) 的結(jié)點數(shù)據(jù)，把只插入到這個數(shù)所在的位置就可以了。void InsertIncreaseList

10、( Seqlist *L , Datatype x int i;for (i-0; i<L-> length && L->data 1 <x； i + +)；j ：魚找并比較'分號不能InseitList ( L , x , 1 ) ;/調(diào)川順序農(nóng)捕人晅數(shù)2.5假設(shè)分別以兩個元素值遞增有序的線性表A, B表示兩個集合(即同一個線性表中的元素 各不相同)?，F(xiàn)要求構(gòu)成一個新的線性表CC表示真合A與B的交，且C中元素也遞增有 序。試分別以下順序表和單鏈表為存儲結(jié)構(gòu)，編寫實現(xiàn)上述運算的算法.答：void LinkList_Intersect(LinkLi

11、st A,LinkList B,LinkList &C)p=A>next;q=B->next;pc» (LNode*)malloc(sizeof(LNode);while (p&&q)if g>data<q->data) p=p->next;else if (p->data>q->data) q=q->next;else(9= (LNode*)malloc(sizeof CLNode);s->data-p>data;pc->next=s;pc=s;p=p>next;q=q-&g

12、t;next;/whileC=pc；/LinkList Intersect第3章棧、隊列習(xí)題33-1對于一個適當(dāng)大小的棧，設(shè)輸入項序列為A、B、C、D、E。為得到下列的處理序列，需 要做什么樣的運算序列(由PUSH、POP組成)？。如果其中某處理序列得不到時，試說明理 由？： A、B、C、D、E； B、C、D、E、A；E、A、B、C、D; E、D、C、B、A。答：(D PUSH(A), POP(A), PUSH(B), POP(B), PUSH(C), POP(C), PUSH(D), POP(D), PUSH(E), POP(E) PUSH(A), PUSH(B), POP(B), PUSH

13、(C), POP(C), PUSH(D), POP(D), PUSH(E), POP(E), POP(A) 無法實現(xiàn)。 PUSH(A), PUSH(B), PUSH(C), PUSH(D), PUSH(E), POP(E), POP(D), POP(C), POP(B), POP(A)3-2用鏈表存放著個字符，試用算法判斷讀字符串是否有中心對稱關(guān)系。例如obccba, abcbo 都算是中心對稱的字符串。要求用盡可能少的時間完成判斷(提示：將一半的字符先依次進 棧)。答：int judgA)linkllsc seqscack s；inc I;Linklisltz j5->top- *1;

14、r=i；P-head:wUle(pi=null)(S->tOp3->LQp4-l；c- ><3ata a->copPP款二,)p-heed；vhlle(pj-null)(p=p->noxt；3->top一)els亡(1=0;p-s-null;return(I);J3-3現(xiàn)有中綴表達式E = (100-4) -3 + 3x (36-7) *2、寫出與E等價的后綴表達式. 并用棧來模擬表達式的轉(zhuǎn)換過程，畫出轉(zhuǎn)換過程中棧的內(nèi)容的變化圖。答：1004 3 專 3 36 7 x 十2 x圖略。第4章多維數(shù)組、廣義表、串習(xí)題44.1現(xiàn)有三個數(shù)組An+1, Bn+l

15、ni和CMln十2,試問各個數(shù)組能存放多少個元素。 答：11 十 1(n+l)*m (n-t-1 )*(n+2)4.2有三維數(shù)組A (2, 3, 4、)、數(shù)組中元素長度為4個字節(jié)。試求元素A232的相對地址。 答：1524.3已知下圖為廣義表的存儲結(jié)構(gòu)圖，寫出此圖表示的廣義表。答：©,(y),(0),0,)4.4 有廣義表人=(),B = (A, e, d), C = (A), D = (e, (a, b, B), A, C)。( 1)畫出上 述各廣義表的圖形。(2)求表D的長度和深度；(3)畫出D表的鏈表表示。答：(2)長度：4深度：24.5簡述下列每對術(shù)語的區(qū)別：空串和空格串；串

16、變量和串常量，主串和子串，串變量的名 字與串變量的值。答：詳見課本。4.6在順序串上實現(xiàn)串的判等運算equal(s,t),在鏈串上實現(xiàn)判等運算equal(s,t)的算法.答：int StrComp(cliar *sl, chai *s2)lilt 1=0；wlule (sli=s2i && sli!=,0>) HH-,return (sli-s2i);mt Sti Con)p(liuk *headL link * head 2)link *pl,*p2;pl=headl->next;p2=headl->next;while (pl ->data=p2-&

17、gt;data && po&&p2)p 1 =p 1 ->next,p2=p2->next,if(pl|p2)return 0,elseretiiin 1;第6章樹、二叉樹習(xí)題66.1分別就下圖中的二叉樹和樹回答下列問題：哪個是根結(jié)點?；哪些是葉子結(jié)點?；哪 個是G的雙親?，哪些是G的祖先?，哪些是E的子孫?；哪些是E的兄弟?，哪些是C 的兄弟?；結(jié)點B和I的層數(shù)分別是多少?。答：左邊的圖形1 ) A 2)D,J3)E 4)E A 5)GH,I ,J 6)E 兄弟：B,C 兄弟：F,G7)2 和 5右邊的圖形1 ) A 2)DHJ,J,F,G 3)C

18、 4)C,A5)H,IJ 6)E 兄弟：D,C 兄弟：B 7) 2 和 46.2分別畫出含3個結(jié)點的無序樹與二叉樹的所有不同形態(tài)。答：二又樹6.3分別寫出題6.1所示二叉樹的先根，中根和后根序列。答：先根：ABCDEFGHIJ 中根：DCBAFEHJIG 后根：DCBFJIHGEA6.4已知一棵二叉樹的中根序列和后根序列分別為BDCEAFHG和DECBHGFA,試畫出這棵 二叉樹。答：由后根遍歷序列得到二叉樹的根結(jié)點A（后根序列中最后一個結(jié)點）；在中序序列中,A的左力是A的左子樹上的結(jié)點，A的右邊是A的右子樹上的結(jié)點；再到后根序列中找左子樹和右子樹的根結(jié)點，依次類推，直到畫出該二叉樹。6.5將

19、下圖所示的森林轉(zhuǎn)換成二叉樹。06.6分別畫出下圖所示各二叉樹對應(yīng)的森林。#C O R 0 A 0CizbftOOLFOco6.7給定權(quán)值7, 18, 3, 32, 5, 26, 12, 8、構(gòu)造相應(yīng)的哈夫曼樹。答：按權(quán)值大小排列后3 5 78 12 18 26 32只要按照將最小的兩個合并，合并后的值再 入列中（最小的兩個出列），至到列中只有一個值.按上面要求構(gòu)造哈夫曼樹如下：/樹列完后，可取左樹編碼為0,右為1,（左為1,右為0亦可）3、'小57'、'小8小(8)小'120YT1小'(15)小180，',7'1X WW''

20、;(20)小26Of門 q q /|(33)小320,',7,1O'WlV7'7(46)(65)則按上面的樹可得到各權(quán)值所對應(yīng)的編碼i/其編碼是從樹頂?shù)皆摍?quán)值點所經(jīng)過的1或0的序列 7:' 10 0 018：'ro i3宀 0 0 0 032宀115:' 0 0 0 126:''0 112小 0 0 8:' 10 0 1第7章圖習(xí)題77.1對有向圖，試給出：每個頂點的入度和出度；鄰接矩陣；鄰接表；強連通分量;該圖是強連通的嗎?。答：節(jié)點1:入度2,出度1節(jié)點2:入度2,出度2節(jié)點3:入度1,出度2節(jié)點4:入度1,出度3節(jié)點

21、5:入度3,出度0節(jié)點6:入度2,出度3 強連通分量2T4T3T6 不是7.2對下圖從頂點Vi出發(fā)，分別畫出其深度和廣度生成樹。答：圖略。7.3對于下面給出的AOE網(wǎng)絡(luò)：求出每個活動的最早開始時間和最遲開始時間；完成該 工程的最早時間為多少?；哪些活動是關(guān)鍵活動；是否存在某些活動，只要提高其速度就 可以縮短工程的時間；畫出所有可能的拓?fù)渑判蚪Y(jié)果。44答： 參照課本進行計算，列表。 23天 1-6-5-8-910 提高關(guān)鍵活動的速度就可以縮短工程時間。 圖略。7.4 按順序輸入頂點對：（1、2）, （1、6）, （2、6） （、4）, （6、4）, （1、3）, （3、4）, （6、5）, （4

22、、5）, （1、5）, （3、5）, （0、0）,根據(jù)生成算法畫出相應(yīng)的鄰接表.給定V°=4,寫出 按深度優(yōu)先和廣度優(yōu)先搜索的思想寫一個算法，求一條從V。出發(fā)到點的簡單路徑.答：按題中順序輸入各條邊后建立起來的鄰接表圖略。在鄰接表上進行深度優(yōu)先遍歷所得到的DFS序列為4, 5, 3, 1, 6, 2;在鄰接表上進行 廣度優(yōu)先遍歷所得到的BFS序列為4, 5, 3, 6, 1, 2.mt visitedMAXSIZE; 指示頂點是否在當(dāng)前路徑上intexist_path_DFS（ALGraphG,int Mnt j）/深度優(yōu)先判斷有向圖G中頂點1到頂點j是否有路徑, 是則返回1,否則返

23、回0if（i=j） letum 1, /i 就是 jelsevisited i=l;for(p=G.veiticesi.fiistaic.p,p=p->nextaic)kp->adjvex,if(!visi(edk&&exist_path(k,j) retiun l;/i 下游的頂點到 j 有路徑/for/else)/exist_path_DFSint exist_path_BFS(ALGraph G,mt ljnt j)廣度優(yōu)先判斷有向圖G中頂點1到頂點j是否有路徑, 是則返回1,否則返回0mt isited MAXSIZE;IiutQueue(Q),Eli Qu

24、eue (Qj);while (! QueueEmpty(Q)DeQueue(Q,u);visitedu=l,for(p=G.verticesi.firstaic,p,p=p->nextaic)k=p->adjvex,if(k=j) l etimi 1;if(?visitedk) EnQueue(Q,k);/for)/wluleletin ii 0、 /exi st_path_B FS7.5試?yán)米疃搪窂降乃惴ㄇ笙聢D從頂點1到其它各點間的最短路徑，寫出執(zhí)行算法過程中各步的狀態(tài)。答：1-2: 1-3-2 9;1-3: 1-3 5;1-4: 1-6-419;1-5: 1-3-2-5 1

25、9;1-6: 1-3-6 15;7.6畫出下圖的最小生成樹。25答：12; 1-6; 3-6; 4-6; 5-6;總共5條邊構(gòu)成最小生成樹。圖略。第9章查找表習(xí)題99.1 設(shè)一有序文件的關(guān)鍵字為 2, 5, 8, 11, 13, 17, 25, 36, 47, 55, 60, 63, 65, 67, 76, 94,當(dāng)用折半查找算法查找關(guān)鍵字2, 55, 63時，試決定關(guān)鍵字的比較次數(shù)。答：2 :比較4次；55:比較3次；63:比較4次9.2若用分塊查找法，一個有144項的表，分成幾塊最好？。每塊的最佳長度是多少？，假 定每塊長度為8,則其平均查長度是多少？。答：分為12塊，144的開平方;平均

26、長度：0.5（8十144/8）十1=149.3試比較開放地址法和鏈地址法沖突處理技術(shù)的優(yōu)缺點。答：開放定址法，即是由關(guān)鍵碼得到的哈希地址一旦產(chǎn)生了沖突，也就是說，該地址已 經(jīng)存放了數(shù)據(jù)元素，就去尋找下一個空的哈希地址，只要哈希表足夠大，空的哈希地址總能 找到，并將數(shù)據(jù)元素存入。鏈地址法的相關(guān)內(nèi)容見課本。9.4假設(shè)結(jié)點序列F= （60, 30, 90, 50, 120, 70, 40, 80）。試用查找樹的插入算法，用F 中的結(jié)點俅次進行插入，畫出P中結(jié)點所構(gòu)成的查找樹g.再用查找樹的刪除算法，從查找 樹"中刪除60,畫出刪除后的查找樹4答：圖略。第10章內(nèi)部排序、外部排序習(xí)題1010

27、.1 有如下 12 個整數(shù):23, 37, 7, 79, 29, 43, 73, 19, 31, 61, 23, 47,按下列方法將 這組整數(shù)排序，分別寫出每遍處理后的數(shù)列：氣泡排序；插入排序；選擇排序；快速 排序；歸并排序；基數(shù)排序。答：以排序碼序列為12, 2,16, 30,28,10,16*, 20,6,18為例子,題目的做法跟卜面一致.（1）直接插入排序初始樣列0 123456789拮序碼比較次數(shù)1-11221630281016*20618L1-22、121630281016*206L811-32121630281016*2061811 421216302810162061821 -5

28、2 12162830io16*2061851 -62 10、2、6、28、3016206L831 -72 10121616、8、302061831-82 1012161620、28、301 61831 -92 6、6、“、20、28、01882 610121616*18、20、28>30(2)快速;排序PivotPvtpos0123456789排序碼比較次數(shù)120231 1221630281016*20618 1960,16fpos2 10tP°s12 28 1616#2030182284,5,6,7,826 1012128 16fpos fpos16*fpos2030fpos

29、 |pos1«15134,626 101218 16|pos fpos16*fpos202830】316-426101216 16 |po01216 16 18202830左子仔列遞歸深度為b右子序列遞歸深度為3。（3）堆排序第一步，形成初始的最大堆（略八第二步，做堆排序。交換與9°對象交換琳與7#對象 從0#到6#幣:新形成堆交換0#與3#對象（4）基數(shù)排序按址低位分配f0 fll f2 耳習(xí) fl4 耳5f6f7f8f9收集 | 30 W L0 田 20 円 L2 L6 円 G28 円 18 |flO fll 臟】 f3耳4】f5f6 fI7

30、flS fI910.2假定被排序的數(shù)據(jù)集合用一個單向鏈表表示，其表頭結(jié)點指針為f,結(jié)點的類型定義如 下：Type celltype = RecordData : lecoidsnext: t celltypeEud,ist = celltype;分別按下列算法寫岀分類過程soi(F):插入排序;選擇排序。答：略。第12章文件習(xí)題1212.1什么是文件的邏輯記錄和物理記錄?，它們有什么區(qū)別與聯(lián)系？。答：邏輯結(jié)構(gòu)是記錄在用戶或應(yīng)用程序面前呈現(xiàn)的方式，是用戶對數(shù)據(jù)的表示和存取方 式。物理結(jié)構(gòu)是數(shù)據(jù)在物理存儲器上存儲的方式，是數(shù)據(jù)的物理表示和組織。12.2如何選擇合適的文件組織形式？，決定于哪些因素?

31、，簡述文件組織的基本方法。答：文件采用何種存儲結(jié)構(gòu)應(yīng)綜合考慮各種因素，如：存儲介質(zhì)類型、記錄的類 型、大小和關(guān)鍵字的數(shù)目以及對文件作何種操作。文件的基本組織方式有順序組織、索引組織、散列組織和鏈組織。文件的存儲結(jié)構(gòu)可 以采用將基本組織結(jié)合的方法，常用的結(jié)構(gòu)有順序結(jié)構(gòu)、索引結(jié)構(gòu)、散列結(jié)構(gòu).(1) 順序結(jié)構(gòu)，相應(yīng)文件為順序文件，其記錄按存入文件的先后次序順序存放。順序文件 本質(zhì)上就是順序表.若邏輯上相鄰的兩個記錄在存儲位置上相鄰，則為連續(xù)文件；若記錄之 間以指針相鏈接，則稱為串聯(lián)文件。順序文件只能順序存取，要更新某個記錄，必須復(fù)制整 個文件。順序文件連續(xù)存取的速度快，主要適用于順序存取，批量修改的情況.(2) 帶索引的結(jié)構(gòu)，相應(yīng)文件為索引文件。索引文件包括索引表和數(shù)據(jù)表，索引表中的索 引項包括數(shù)據(jù)表中數(shù)據(jù)的關(guān)鍵字和相應(yīng)地址，索引弟有序，其物理順序體現(xiàn)了文件的邏輯次 序，實現(xiàn)了文件的線性結(jié)構(gòu)。索引文件只能是磁盤文件，既能順序存取，又能隋機存取。(3) 散列結(jié)構(gòu)，也稱計算尋址結(jié)構(gòu)，相應(yīng)文件稱為