習題及答案文檔

習題二1簡述以下術語：線性表，順序表，鏈表。線性表：最經(jīng)常使用且最簡單的一種數(shù)據(jù)結(jié)構(gòu)。一個線性表是n個數(shù)據(jù)元素的有限序列。順序表：是指用一組持續(xù)的存儲單元一次存儲線性表中的數(shù)據(jù)元素。物理結(jié)構(gòu)和邏輯結(jié)構(gòu)都相鄰。鏈表：邏輯結(jié)構(gòu)相鄰的數(shù)據(jù)元素物理結(jié)構(gòu)不必然相鄰。采納指針的形式連接起來。2何時選用順序表，何時選用鏈表作為線性表的存儲結(jié)構(gòu)適合?各自的要緊優(yōu)缺點是什么?不需要常常大量的修改表或需要隨機存取的情形下能夠選用順序表；相反需要常常大量的修改表，但不是頻繁的隨機存取的情形下可選用鏈式表。3在順序表中插入和刪除一個結(jié)點平均需要移動多少個結(jié)點?具體的移動次數(shù)取決于哪兩個因素?答：平均需要移動n/2個結(jié)點。表的長度，和要插入的位置。4鏈表所表示的元素是不是有序?如有序，那么有序性表現(xiàn)于何處?鏈表所表示的元素是不是必然要在物理上是相鄰的?有序表的有序性又如何明白得?答：有序。有序性體此刻通過指針數(shù)據(jù)元素有序的相連。物理上不必然要相鄰。5設順序表L是遞增有序表，試寫一算法，將x插入到L中并使L仍是遞增有序表。StatusListInsert(SqList&L,inti,ElemTypee){ if((i>+1)||i<1) returnERROR; if>= { newbase=(ElemType*)realloc(+LISTINCREMENT)*sizeof(ElemType)); if(!newbase) exit(-1); =newbase; +=LISTINCREMENT; } ElemType*q,*p; q=&[i-1]; for(p=&[];p>=q;p--) *(p+1)=*p; *q=e; ++; returnOK;}9設A和B是兩個按元素值遞增有序的單鏈表，寫一算法將A和B歸并為按按元素值遞減有序的單鏈表C，試分析算法的時刻復雜度。voidListInsert(SqListA,SqListB,SqListC){ ElemType*p,*q,*s; P=&A; q=&B; s=&C; while!=NULL||!=NULL) { if { if!=NULL) =; =; p++; } else { if!=NULL) =; =; q++; } } while!=NULL) { =; =; } while!=NULL) { =; =; }習題三1設有一個棧，元素進棧的順序為a,b,c。問通過棧操作后能夠取得哪些輸出序列？Abc,acb,bac,bca,cba.2循環(huán)隊列的優(yōu)勢是什么?如何判定它的空和滿?優(yōu)勢：能夠克服順序隊列的“假上溢”現(xiàn)象，能夠使存儲隊列的向量空間取得充分利用。判定循環(huán)隊列的空或滿不能以頭尾指針是不是相等來確信，一樣是通過以下幾種方式：一是另設一布爾變量來區(qū)別隊列的空和滿。二是約定入隊前，測試尾指針在循環(huán)意義下加1后是不是等于頭指針，假設相等那么以為隊滿。三是設置一計數(shù)器記錄隊列中元素的總數(shù)，不僅可判別空或滿，還能夠取得隊列中元素的個數(shù)。3設有一個靜態(tài)順序隊列，向量大小為MAX，判定隊列為空的條件是什么？隊列滿的條件是什么？隊列為空：front=rear。隊滿：rear=MAX-1或front=rear(隊首指針front，一個隊尾指針rear)4設有一個靜態(tài)循環(huán)隊列，向量大小為MAX，判定隊列為空的條件是什么？隊列滿的條件是什么？循環(huán)隊列為空：front=rear。循環(huán)隊列滿：(rear+1)%MAX=front。(隊首指針front，一個隊尾指針rear)5利用棧的大體操作，寫一個返回棧S中結(jié)點個數(shù)的算法intStackSize(SeqStackS)，并說明S為何不作為指針參數(shù)的算法?intStackSize(SeqStackS)

{主串和子串的區(qū)別：主串是相關于子串而言的，子串是主串中持續(xù)的一段，是主串的一個子集。目標串和模式串的區(qū)別：目標串是在模式匹配中的主串，是相關于模式串運算的母串，而模式串是子串，是在主串中運算的子串。⑵假設x和y是兩個采納順序結(jié)構(gòu)存儲的串，寫一算法比較這兩個字符串是不是相等。解：intstreql(Hstringx,Hstringy)if(x[0]!=y[0])return(0);elsei=1;while(x[i]==y[i]&&i<x[0])i++;if(i==x[0])return(1)elsereturn(0)習題五⑴什么是廣義表？請簡述廣義表與線性表的區(qū)別？廣義表是零最多個元素的有限序列，廣義表中的元素能夠是原子，也能夠是子表。從“元素的有限序列”角度看，廣義表知足線性結(jié)構(gòu)的特性：在非空線性結(jié)構(gòu)中，只有一個稱為“第一個”的元素，只有一個稱為“最后一個”的元素，第一元素有后繼而沒有前驅(qū)，最后一個元素有前驅(qū)而沒有后繼，其余每一個元素有唯一前驅(qū)和唯一后繼。從那個意義上說，廣義表屬于擴充的線性結(jié)構(gòu)（只只是元素并非具有同一類型：能夠是原子，也能夠是廣義表）。當廣義表中的元素都是原子時，廣義表就蛻變成線性表。廣義表是線性表的推行，線性表是廣義表的特例。當廣義表中的元素都是原子時，即為線性表⑵一個廣義表是(a,(a,b),d,e,(a,(i,j),k))，請畫出該廣義表的鏈式存儲結(jié)構(gòu)。圖解：⑶設有二維數(shù)組a[6][8]，每一個元素占相鄰的4個字節(jié)，存儲器按字節(jié)編址，已知a的起始地址是1000，試計算：①數(shù)組a的最后一個元素a[5][7]起始地址；②按行序優(yōu)先時，元素a[4][6]起始地址；③按行序優(yōu)先時，元素a[4][6]起始地址。LOC(a[5][7])=LOC(a[0][0])+47*4=1188LOC(a[4][6])=LOC(a[0][0])+(48+6)4=1152LOC(a[4][6])=LOC(a[0][0])+（6*6+4）4=1160⑸設有稀疏矩陣B如以下圖所示，請畫出該稀疏矩陣的三元組表和十字鏈表存儲結(jié)構(gòu)。圖解：圖中未標記空指針，作業(yè)中請注意標記習題六⑴假設在樹中，結(jié)點x是結(jié)點y的雙親時，用(x,y)來表示樹邊。已知一棵樹的樹邊集合為{(e,i),(b,e),(b,d),(a,b),(g,j),(c,g),(c,f),(h,l),(c,h),(a,c)}，用樹型表示法表示該樹，并回答以下問題：①哪個是根結(jié)點?哪些是葉子結(jié)點?哪個是g的雙親?哪些是g的先人?哪些是g的小孩?那些是e的子孫?哪些是e的兄弟?哪些是f的兄弟?②b和n的層次各是多少?樹的深度是多少?以結(jié)點c為根的子樹的深度是多少?⑵一棵深度為h的滿k叉樹有如下性質(zhì)：第h層上的結(jié)點都是葉子結(jié)點，其余各層上每一個結(jié)點都有k棵非空子樹。若是按層次順序(同層自左至右)從1開始對全數(shù)結(jié)點編號，問：①各層的結(jié)點數(shù)是多少?②編號為i的結(jié)點的雙親結(jié)點(假設存在)的編號是多少?③編號為i的結(jié)點的第j個小孩結(jié)點(假設存在)的編號是多少?④編號為i的結(jié)點的有右兄弟的條件是什么?其右兄弟的編號是多少?⑶設有如圖6-27所示的二叉樹。①別離用順序存儲方式和鏈接存儲方式畫出該二叉樹的存儲結(jié)構(gòu)。②寫出該二叉樹的先序、中序、后序遍歷序列。⑷已知一棵二叉樹的先序遍歷序列和中序遍歷序列別離為ABDGHCEFI和GDHBAECIF，請畫出這棵二叉樹，然后給出該樹的后序遍歷序列。⑸設一棵二叉樹的中序遍歷序列和后序遍歷序列別離為BDCEAFHG和DECBHGFA，請畫出這棵二叉樹，然后給出該樹的先序序列。⑹已知一棵二叉樹的中序遍歷序列和后序遍歷序列別離為dgbaekchif和gdbkeihfca，請畫出這棵二叉樹對應的中序線索樹和后序線索樹。⑺以二叉鏈表為存儲結(jié)構(gòu)，請別離寫出求二叉樹的結(jié)點總數(shù)及葉子結(jié)點總數(shù)的算法。⑻設圖6-27所示的二叉樹是叢林F所對應的二叉樹，請畫出叢林F。⑼設有一棵樹，如圖6-28所示。①請別離用雙親表示法、小孩表示法、小孩兄弟表示法給出該樹的存儲結(jié)構(gòu)。②請給出該樹的先序遍歷序列和后序遍歷序列。③請將這棵樹轉(zhuǎn)換成二叉樹。⑽設給定權(quán)值集合w={3,5,7,8,11,12}，請構(gòu)造關于w的一棵huffman樹，并求其加權(quán)途徑長度WPL。⑾假設用于通信的電文是由字符集{a,b,c,d,e,f,g,h}中的字符組成，這8個字符在電文中顯現(xiàn)的概率別離為{,,,,,,,}。①請畫出對應的huffman樹(按左子樹根結(jié)點的權(quán)小于等于右子樹根結(jié)點的權(quán)的順序構(gòu)造)。②求出每一個字符的huffman編碼習題七⑴分析并回答以下問題：①圖中極點的度之和與邊數(shù)之和的關系?②有向圖中極點的入度之和與出度之和的關系?③具有n個極點的無向圖，至少應有多少條邊才能確保是一個連通圖?假設采納鄰接矩陣表示，那么該矩陣的大小是多少?④具有n個極點的有向圖，至少應有多少條弧才能確保是強連通圖的?什么緣故?⑵設一有向圖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>}①請畫出該有向圖，并求各極點的入度和出度。②別離畫出有向圖的正鄰接鏈表和逆鄰接鏈表。⑶對圖7-27所示的帶權(quán)無向圖。①寫出相應的鄰接矩陣表示。②寫出相應的邊表表示。③求出各極點的度。⑷已知有向圖的逆鄰接鏈表如圖7-28所示。①畫出該有向圖。②寫出相應的鄰接矩陣表示。③寫出從極點a開始的深度優(yōu)先和廣度優(yōu)先遍歷序列。④畫出從極點a開始的深度優(yōu)先和廣度優(yōu)先生成樹。⑸一個帶權(quán)連通圖的最小生成樹是不是唯一?在什么情形下可能不唯一?⑹關于圖7-27所示的帶權(quán)無向圖。①依照Prime算法給出從極點2開始構(gòu)造最小生成樹的進程。②依照Kruskal算法給出最小生成樹的進程。⑺已知帶權(quán)有向圖如圖7-29所示，請利用Dijkstra算法從極點V4動身到其余極點的最短途徑及長度，給出相應的求解步驟。⑻已知帶權(quán)有向圖如圖7-30所示，請利用Floyd算法求出每對極點之間的最短途徑及途徑長度。⑼一個AOV網(wǎng)用鄰接矩陣表示，如圖7-31。用拓撲排序求該AOV網(wǎng)的一個拓撲序列，給出相應的步驟。⑽拓撲排序的結(jié)果不是唯一的，請給出如圖7-32所示的有向圖的所有可能的拓撲序列。⑾請在深度優(yōu)先搜索算法的基礎上設計一個對有向無環(huán)圖進行拓撲排序的算法。⑿設計一個算法利用圖的遍歷方式輸出一個無向圖G中從極點Vi到Vj的長度為S的簡單途徑，設圖采納鄰接鏈表作為存儲結(jié)構(gòu)。⒀假設一個工程的進度打算用AOE網(wǎng)表示，如圖7-33所示。①求出每一個事件的最先發(fā)生時刻和最晚發(fā)生時刻。②該工程完工至少需要多少時刻?③求出所有關鍵途徑和關鍵活動。習題九⑴關于一個有n個元素的線性表，假設采納順序查找方式時的平均查找長度是什么？假設結(jié)點是有序的，那么采納折半查找法是的平均查找長度是什么?⑵設查找表采納單鏈表存儲，請別離寫出對該表進行順序查找的靜態(tài)查找和動態(tài)查找的算法。⑶設二叉排序樹中的關鍵字互不相同：那么①最小元素無左小孩，最大元素無右小孩，此命題是不是正確？②最大和最小元素必然是葉子結(jié)點嗎？③一個新結(jié)點老是插入在葉子結(jié)點上嗎？⑷試比較哈希表構(gòu)造時幾種沖突處置方式的優(yōu)勢和缺點。⑸將關鍵字序列(10,2,26,4,18,24,21,15,8,23,5,12,14)依次插入到初態(tài)為空的二叉排序樹中，請畫出所取得的樹T；然后畫出刪除10以后的二叉排序樹T1；假設再將10插入到T1中取得的二叉排序樹T2是不是與T1相同?請給出T2的先序、中序和后序序列。⑹設有關鍵字序列為：(Dec,Feb,Nov,Oct,June,Sept,Aug,Apr,May,July,Jan,Mar)，請手工構(gòu)造一棵二叉排序樹。該樹是平穩(wěn)二叉排序樹?假設不是，請為其構(gòu)造一棵平穩(wěn)二叉排序樹。⑺設關鍵字序列是(19,14,23,01,68,84,27,55,11,34,79)，散列表長度是11，散列函數(shù)是H(key)=keyMOD11，①采納開放地址法的線性探測方式解決沖突，請構(gòu)造該關鍵字序列的哈希表。②采納開放地址法的二次探測方式解決沖突，請構(gòu)造該關鍵字序列的哈希表。⑻試比較線性索引和樹形索引的優(yōu)勢和缺點。⑼設關鍵字序列是(19,24,23,17,38,04,27,51,31,34,69)，散列表長度是11，散列函數(shù)是H(key)=keyMOD11，①采納開放地址法的線性探測方式解決沖突，請構(gòu)造該關鍵字序列的哈希表。②求出在等概率情形下，該方式的查找成功和不成功的平均查找長度ASL。⑽以下圖是一棵3階B_樹，請畫出插入關鍵字B,L,P,Q后的樹形。習題十⑴回答以下各題：①從未排序序列中挑選元素，并將其依次放入到已排序序列中(初始時為空)的一端的方式是什么？②在待排序的元素大體有序的前提下，效率最高的排序方式是什么?③從未排序序列中依次掏出元素與已排序序列(初始時為空)中的元素進行比較，將其放入已排序序列的正確位置方式是什么？④設有1000個元素，希望采納最快的速度挑選出其中前10個最大的元素，最好的方式是什么?⑵假設對關鍵字序列為(54,37,93,25,17,68,58