數(shù)據(jù)結(jié)構(gòu)(C語言)作業(yè)

其次章作業(yè)：1.指出以下算法中的錯誤和低效（即費時）之處，并將它改為一個既正確又高效的算法。ProcDeleteK(VARa:sqlist;i,k:integer);{從依次存儲結(jié)構(gòu)的線性表a中刪除自第i個元素起的K個元素}If(i<1)cor(i>a.last)thenerror(‘Argumentinvalid’)elseforcount:=1tokdo【forj:=a.lastdowntoi+1doa.elem[j-1]:=a.elem[j];a.last:=a.last-1】ENDP;{deleteK}2.設(shè)依次表Va中的數(shù)據(jù)元素遞增有序。試寫一算法，將X插入到依次表的適當(dāng)位置上，以保持該表的有序性。3.用單鏈表實現(xiàn)Locate(L,x)函數(shù)。（可參考P26算法2.5)4.上機題：設(shè)單鏈表Va中的數(shù)據(jù)元素遞增有序。試編寫程序，將數(shù)據(jù)X插入單鏈表Va，要求插入后保持該表的有序性。5.寫出雙向鏈表刪除第i個結(jié)點的算法。6.寫出求雙向循環(huán)鏈表長度的算法。（注：頭結(jié)點不算）第三章作業(yè)：1.上機題：編寫程序，判別表達(dá)式中（、）是否配對出現(xiàn)。2.寫出下列程序段的輸出結(jié)果（棧的元素類型為：char).vars:stack;x,y:char;beginx:=‘c’;y:=‘k’;push(s,x);push(s,‘a(chǎn)’);push(s,y);x:=pop(s);push(s,‘t’);push(s,x);x:=pop(s);push(s,‘s’);whilenotempty(s)do【y:=pop(s);write(y)】;writeln(x);end;第四章作業(yè):1.用4.1.2供應(yīng)的7種串的基本操作來實現(xiàn)insert(s,pos,t)和delete(s,pos,len)操作.2.上機題：編寫程序，完成靜態(tài)存儲串時的insert(s,pos,t)或delete(s,pos,len)操作。3.課堂練習(xí)：執(zhí)行以下程序段，寫出運行結(jié)果。

procp;creat(s,’thisisabook’);replace(s,substr(s,3,7),’eseare’);creat(t,concat(s,’s’));creat(u,’xyxyxyxyxyxy’);creat(v,substr(u,6,3));creat(w,’w’);writeln(t,v,replace(u,v,w))endp;{p}第五章作業(yè)：1.假設(shè)有二維數(shù)組a:array[1..6,0..7]ofelemtp;每個數(shù)據(jù)元素占6個字節(jié),存儲器按字節(jié)編址。a的基地址為1000,則：(1)數(shù)組a的體積；(2)數(shù)組a的最終一個元素的第一個字節(jié)的地址；(3)按行存儲時，a[2,4]的第一個字節(jié)的地址；(4)按列存儲時，a[5,7]的第一個字節(jié)的地址；第六章作業(yè)：1.一棵度為2的樹與一棵二叉樹有何區(qū)分？2.試分別畫出具有3個結(jié)點的樹和3個結(jié)點的二叉樹的全部不同形態(tài)。3.已知一棵度為k的樹中有n1個度為1的結(jié)點，n2個度為2的結(jié)點，……，nk個度為k的結(jié)點，問該樹中有多少個葉子結(jié)點。4.對題2所得的3個結(jié)點的二叉樹的5種不同形態(tài)，分別寫出先序、中序、后序的遍歷序列。5.一棵含有n個結(jié)點的k叉樹，可能達(dá)到的最大深度和最小深度各為多少？6.上機題：按先序次序建立以下二叉樹，然后分行輸出它的先序、中序、后序序列。ABFCJM7.寫出下列各樹的先根序列,后根序列,并且畫出對應(yīng)的二叉樹.AABCABCABCDEFGHIJK8.畫出第7題的森林相應(yīng)的二叉樹.9.畫出和下列已知序列對應(yīng)的樹T:

樹的先根次序訪問序列為:GFKDAIEBCHJ,而且樹的后根次序訪問序列為:DIAEKFCJHBG。10.畫出和下列二叉樹相應(yīng)的森林:AABCABCABDCHEKFGJMI11.假設(shè)用于通訊的電文僅由8個字母組成,字母在電文中出現(xiàn)的頻率分別為0.07、0.19、0.02、0.06、0.32、0.03、

0.21、0.10。試為這8種字母設(shè)計哈夫曼編碼。第七章作業(yè)：1.請給出下圖的:(1)每個頂點的入度和出度.(2)強連通重量(3)鄰接矩陣(4)鄰接表(5)逆鄰接表(6)十字鏈表1365422.寫出以數(shù)組為存儲結(jié)構(gòu),函數(shù)firstadj(G,v)的算法.3.寫出以數(shù)組為存儲結(jié)構(gòu),函數(shù)nextadj(G,v,w)的算法.4.上機題:建立下圖(以數(shù)組或鄰接表為存儲結(jié)構(gòu)),然后輸出圖的深度優(yōu)先序列、廣度優(yōu)先序列。ACEGFBHD5.對下圖用普里姆算法、克魯斯卡爾算法構(gòu)造最小生成樹.

（畫出構(gòu)造過程）。3145237946636.請列出下圖中全部可能的拓樸有序序列.1253647.對于下圖所示的AOE網(wǎng),計算各事務(wù)的ve(i)和vl(i),各活動的e(i)和l(i);列出關(guān)鍵活動和關(guān)鍵路徑.123465a1=6a2=6a3=1a5=2a6=7a7=4a4=28.用迪杰斯特拉(Dijkstra)算法求下圖中從頂點1到其它各頂點的最短路徑，畫出各步的狀態(tài)。112345

6

105

3129.用弗洛伊德（Floyd）算法求下圖所示有向圖中各頂點之間的最短路徑。ABC

6

10218第九章作業(yè):1.畫出對長度為10的有序表進(jìn)行折半查找的判定樹,并求出等概率時查找成功的平均查找長度.2.有一含有5個記錄的有序序列及權(quán)值如下：關(guān)鍵字：ABCDE權(quán)值：18256畫出對以上有序序列進(jìn)行折半查找的判定樹，并計算它的PH值。(2)構(gòu)造它的次優(yōu)查找樹并加以適當(dāng)調(diào)整，計算它的PH值。3.有關(guān)鍵字序列{5，37，90，53,60}表;(1)構(gòu)造它的二叉排序樹;(畫出構(gòu)造過程)(2)構(gòu)造它的平衡二叉排序樹;(畫出構(gòu)造、調(diào)整過程）4.某系部學(xué)生的學(xué)號由6位十進(jìn)制組成：C1C2C3C4C5C6。其中c1c2為入學(xué)年份的后兩位；c3為專業(yè)號；c4c5c6為同一系部的學(xué)生的依次編號。假設(shè)某系部在校生為500人，請用干脆定址法為該系部學(xué)生設(shè)計一個哈希表。5.有學(xué)生的生日數(shù)據(jù)如下：年.月.日75.10.03

75.11.23

76.03.02

76.07.12

75.04.21

76.02.15

...請以生日日期為關(guān)鍵字，設(shè)計一個長度為1000的哈希表，使其沖突盡量少。6.上機題：建立一棵二叉排序樹，輸入序列為（45，24，53，12，24，90），然后中序遍歷此樹，得到一個關(guān)鍵字的有序序列。7.在地址空間為0~13的散列區(qū)中,對以下關(guān)鍵字序列構(gòu)造兩個哈希表:(Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec)(1)用線性探測開放定址法處理沖突;(2)用鏈地址法處理沖突;(3)求出以上兩個哈希表在等概率情況下，查找成功、查找不成功時的平均查找長度（用公式計算）。設(shè)哈希函數(shù)為H(key)=|key的第一個字母在字母表的序號/2|第十章作業(yè):1.有一組待排序的記錄的關(guān)鍵字初始排列如下:(32,54,12,24,32`,47)(1)請用干脆插入排序算法對其進(jìn)行排序.(畫出每趟排序示圖)(2)請用希爾排序算法對其進(jìn)行排序.(畫出每趟排序示圖,d=2,1)(3)請用快速排序算法對其進(jìn)行排序.(畫出每趟排序示圖)(4)請用樹型選擇排