數(shù)據(jù)結(jié)構(gòu)課件：作業(yè)

作業(yè)習(xí)題講解第一章習(xí)題：1.簡(jiǎn)要回答術(shù)語：數(shù)據(jù)，數(shù)據(jù)元素，數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)類型，抽象數(shù)據(jù)類型。2.數(shù)據(jù)的邏輯結(jié)構(gòu)？數(shù)據(jù)的物理結(jié)構(gòu)？邏輯結(jié)構(gòu)與物理結(jié)構(gòu)的區(qū)別和聯(lián)系是什么？3.數(shù)據(jù)結(jié)構(gòu)的四種基本結(jié)構(gòu)有哪些？4.算法設(shè)計(jì)的要求？5.分析以下程序段的時(shí)間復(fù)雜度，請(qǐng)說明分析的理由或原因。⑴Sum1(intn){intp=1,sum=0,m;for(m=1;m<=n;m++){p*=m;sum+=p;}return(sum);}⑵Sum2(intn){intsum=0,m,t;for(m=1;m<=n;m++){p=1;for(t=1;t<=m;t++)p*=t;sum+=p;}return(sum);}⑶遞歸函數(shù)fact(intn){if(n<=1)return(1);elsereturn(n*fact(n-1));}第二章習(xí)題：1.簡(jiǎn)述下列術(shù)語：線性表，順序表，鏈表。2.何時(shí)選用順序表，何時(shí)選用鏈表作為線性表的存儲(chǔ)結(jié)構(gòu)合適?各自的主要優(yōu)缺點(diǎn)是什么?3.在順序表中插入和刪除一個(gè)結(jié)點(diǎn)平均需要移動(dòng)多少個(gè)結(jié)點(diǎn)?具體的移動(dòng)次數(shù)取決于哪兩個(gè)因素?4.鏈表所表示的元素是否有序?如有序，則有序性體現(xiàn)于何處?鏈表所表示的元素是否一定要在物理上是相鄰的?有序表的有序性又如何理解?5.已知L是帶表頭結(jié)點(diǎn)的非空單鏈表，且P結(jié)點(diǎn)既不是首元結(jié)點(diǎn)，也不是尾元結(jié)點(diǎn)，試從下列提供的答案中選擇合適的語句序列。A.刪除P結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)的語句序列是

________。B.刪除P結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)的語句序列是

________。C.刪除P結(jié)點(diǎn)的語句序列是________。D.刪除首元結(jié)點(diǎn)的語句序列是________。E.刪除尾元結(jié)點(diǎn)的語句序列是________。(1)P=P->next;(2)P->next=P;(3)P->next=P->next->next;(4)P=P->next->next;(5)while(P!=NULL)P=P->next;(6)while(Q->next!=NULL){P=Q;Q=Q->next;}(7)while(P->next!=Q)P=P->next;(8)while(P->next->next!=Q)P=P->next;(9)while(P->next->next!=NULL)P=P->next;(10)Q=P;(11)Q=P->next；(12)P=L;(13)L=L->next；(14)Free(Q);第三章習(xí)題：1.設(shè)有一個(gè)棧，元素進(jìn)棧的次序?yàn)閍,b,c。問經(jīng)過棧操作后可以得到哪些輸出序列？2.循環(huán)隊(duì)列的優(yōu)點(diǎn)是什么?如何判斷它的空和滿?3.簡(jiǎn)述隊(duì)列和棧這兩種數(shù)據(jù)類型的相同點(diǎn)和差異處？4.寫出下列程序段的輸出結(jié)果（棧的元素類型SElemType為char）voidmain(){

StackS;

charx,y;

InitStack(S);

x='c';y='k';

Push(S,x);Push(S,'a');Push(S,y);

Pop(S,x);Push(S,'t');Push(S,x);

Pop(S,x);Push(S,'s');

while(!StackEmpty(S)){Pop(S,y);printf(y);}

printf(x);}5.假設(shè)Q[0,5]是一個(gè)循環(huán)隊(duì)列，初始狀態(tài)為front=rear=0，請(qǐng)畫出做完下列操作后隊(duì)列的頭尾指針的狀態(tài)變化情況，若不能入隊(duì)，請(qǐng)指出其元素，并說明理由。d,e,b,g,h入隊(duì)d,e出隊(duì)i,j,k,l,m入隊(duì)b出隊(duì)n,o,p,q,r入隊(duì)第四章習(xí)題：1.解釋空串和空格串的區(qū)別，主串和子串的區(qū)別。2.設(shè)s=‘IAMASTUDENT’,t=‘GOOD’,q=‘WORKER’。求：①StrLength(s)，②StrLength(t)，③SubString(s，8，7)，④SubString(t，2，1)，⑤Index(s，‘A’),⑥Index(s，t),⑦Replace(s，‘STUDENT’，q),⑧Concat(SubString(s，6，2),Concat(t，SubString（s，7,8）))。3.試問執(zhí)行以下函數(shù)會(huì)產(chǎn)生怎樣的輸出結(jié)果?

voiddemonstrate()

{

StrAssign(s,'THISISABOOK');

Replace(s,SubString(s,3,7),'ESEARE');

StrAssign(t,Concat(s,'S'));

StrAssign(u,'XYXYXYXYXYXY');

StrAssign(v,SubString(u,6,3));

StrAssign(w,'W');

printf('t=',t,'v=',v,'u=',Replace(u,v,w));

}//demonstrate4.已知：s='(XYZ)+*'，t='(X+Z)*Y'。試?yán)寐?lián)接、求子串和置換等基本運(yùn)算，將s轉(zhuǎn)化為t。第五章習(xí)題：1.設(shè)有二維數(shù)組a[6][8]，每個(gè)元素占相鄰的4個(gè)字節(jié)，存儲(chǔ)器按字節(jié)編址，已知a的起始地址是1000，試計(jì)算：①數(shù)組a的體積（即存儲(chǔ)量）；②數(shù)組a的最后一個(gè)元素a57起始地址；③按行序優(yōu)先時(shí)，元素a46起始地址。2.什么是廣義表？請(qǐng)簡(jiǎn)述廣義表與線性表的區(qū)別？3.一個(gè)廣義表是(a,(b,c),d,e,(f,(i,j),k))，請(qǐng)畫出該廣義表的圖形表示和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。0300000000000000-300000040020020001800000000004050B=00-3000004.設(shè)有稀疏矩陣B如下圖所示，請(qǐng)畫出該稀疏矩陣的三元組表存儲(chǔ)結(jié)構(gòu)。第六章習(xí)題：⑴假設(shè)在樹中，結(jié)點(diǎn)x是結(jié)點(diǎn)y的雙親時(shí)，用(x,y)來表示樹邊。已知一棵樹的樹邊集合為{(e,i),(b,e),(b,d),(a,b),(g,j),(c,g),(c,f),(h,l),(c,h),(a,c)}，用樹型表示法表示該樹，并回答下列問題：①哪個(gè)是根結(jié)點(diǎn)?哪些是葉子結(jié)點(diǎn)?哪個(gè)是g的雙親?哪些是g的祖先?哪些是g的孩子?那些是e的子孫?哪些是e的兄弟?哪些是f的兄弟?②b和n的層次各是多少?樹的深度是多少?以結(jié)點(diǎn)c為根的子樹的深度是多少?（2）設(shè)有下圖所示的二叉樹。①分別用順序存儲(chǔ)方法和鏈接存儲(chǔ)方法畫出該二叉樹的存儲(chǔ)結(jié)構(gòu)。②寫出該二叉樹的先序、中序、后序遍歷序列。（3）已知一棵二叉樹的先序遍歷序列和中序遍歷序列分別為ABDGHCEFI和GDHBAECIF，請(qǐng)畫出這棵二叉樹，然后給出該樹的后序遍歷序列。adebfgchkmn（4）設(shè)有一棵樹，如圖下圖所示。①請(qǐng)分別用雙親表示法、孩子表示法、孩子兄弟表示法給出該樹的存儲(chǔ)結(jié)構(gòu)。②請(qǐng)給出該樹的先序遍歷序列和后序遍歷序列。③請(qǐng)將這棵樹轉(zhuǎn)換成二叉樹。adebfgmhkcn（5）設(shè)給定權(quán)值集合w={3,5,7,8,11,12}，請(qǐng)構(gòu)造關(guān)于w的一棵huffman樹，并求其加權(quán)路徑長(zhǎng)度WPL。（6）假設(shè)用于通信的電文是由字符集{a,b,c,d,e,f,g,h}中的字符構(gòu)成，這8個(gè)字符在電文中出現(xiàn)的概率分別為{0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10}。①請(qǐng)畫出對(duì)應(yīng)的huffman樹(按左子樹根結(jié)點(diǎn)的權(quán)小于等于右子樹根結(jié)點(diǎn)的權(quán)的次序構(gòu)造)。②求出每個(gè)字符的huffman編碼。第七章習(xí)題：（1）設(shè)一有向圖G=(V,E)，其中V={a,b,c,d,e}，E={<a,b>,<a,d>,<b,a>,<c,b>,<c,d>,<d,e>,<e,a>,<e,b>,<e,c>}①請(qǐng)畫出該有向圖，并求各頂點(diǎn)的入度和出度。③

請(qǐng)寫出該有向圖的鄰接矩陣。②分別畫出有向圖的正鄰接鏈表和逆鄰接鏈表。（2）已知有向圖的逆鄰接鏈表如下圖所示。①畫出該有向圖。②寫出相應(yīng)的鄰接矩陣表示。③寫出從頂點(diǎn)a開始的深度優(yōu)先和廣度優(yōu)先遍歷序列。④畫出從頂點(diǎn)a開始的深度優(yōu)先和廣度優(yōu)先生成樹。（3）對(duì)于下圖所示的帶權(quán)無向圖。①按照Prime算法給出從頂點(diǎn)2開始構(gòu)造最小生成樹的過程。②按照Kruskal算法給出最小生成樹的過程。（4）一個(gè)AOV網(wǎng)如下圖所示，請(qǐng)寫出所有可能的拓?fù)渑判蛐蛄小?/p>

FECDAB（5）假設(shè)一個(gè)工程的進(jìn)度計(jì)劃用AOE網(wǎng)表示，如下圖所示。①求出每個(gè)事件的最早發(fā)生時(shí)間和最晚發(fā)生時(shí)間。②該工程完工至少需要多少時(shí)間?③求出所有關(guān)鍵路徑和關(guān)鍵活動(dòng)。

一個(gè)AOE網(wǎng)v0v5v4v7v3v2v1v6v8a1=5a2=6a3=3a8=5a4=12a5=3a10=4a9=1a12=5a11=4a6=3a7=3a13=2v9a14=2第八章習(xí)題：（1）對(duì)于一個(gè)有n個(gè)元素的線性表，若采用順序查找方法時(shí)的平均查找長(zhǎng)度是什么？若結(jié)點(diǎn)是有序的，則采用折半查找法是的平均查找長(zhǎng)度是什么?（2）輸入序列{30、12、57、23、18、3、96、75、83}：①寫出生成一棵二叉排序樹的過程，求出其平均查找長(zhǎng)度。②刪除關(guān)鍵字為57的結(jié)點(diǎn)之后的二