數(shù)據(jù)結(jié)構(gòu)期末考試復(fù)習(xí)總結(jié)

1、-WORD格式-可編輯-專業(yè)資料-學(xué)習(xí)資料分享-（1 ）簡(jiǎn)答題6題*5分=30分（2）分析題6題*5分=30分（3）設(shè)計(jì)題1題*10分=10分（4）編程題1題*10分=10分（5）綜合題1題*20分=20分定義=功能（ADT ）數(shù)據(jù)結(jié)構(gòu)期末考試題型及分值簡(jiǎn)要回答要點(diǎn)給出結(jié)果設(shè)計(jì)思想及結(jié)果完整代碼抽象數(shù)據(jù)類型的定義、表示、實(shí)現(xiàn)、算法分析表示=存儲(chǔ)結(jié)構(gòu)體 實(shí)現(xiàn)=算法（基本操作）算法分析 =時(shí)間、空間復(fù)雜度考試概念有：1.數(shù)據(jù)結(jié)構(gòu) 一、線性表（棧-隊(duì)-列-串-數(shù)組-廣義表-邏輯結(jié)構(gòu)-存儲(chǔ)結(jié)構(gòu)-運(yùn)算結(jié)構(gòu)）、非線性表（集合-樹-圖）分析題考試題目參考（1 ） 1-2-3-4-5-6 順序建 BBST2.

2、抽象數(shù)據(jù)類型數(shù)據(jù)對(duì)象-數(shù)據(jù)關(guān)系-基本操作3.算法性質(zhì)-要求（設(shè)計(jì)）-效率（度量）4.實(shí)例查找：高效查找算法排序：高效的排序算法-WORD格式-可編輯-專業(yè)資料-學(xué)習(xí)資料分享-(2 ) 6-5-4-3-2-1 順序建 BBST-WORD格式-可編輯-專業(yè)資料-學(xué)習(xí)資料分享-頭結(jié)點(diǎn)的樸fflttt空表與非空表眩理一樣2沖點(diǎn)2前怔林吏力更數(shù)據(jù)編構(gòu)復(fù)習(xí)資料*填空題L 敘據(jù)蠟構(gòu)是一門研究非數(shù)值計(jì)再的糧序植計(jì)問區(qū)中計(jì)掃機(jī)的 拠柞刈毎以及它們之間他 M和運(yùn)算等的學(xué)科.2.2.數(shù)據(jù)結(jié)構(gòu)被形式地定文曲CD,R）T其屮n丸數(shù)據(jù)尤舉的右限集ih R R是n n上的_薑屯限集3.3.數(shù)掘箱構(gòu)包括數(shù)堆時(shí)_逆輿址構(gòu)一、數(shù)

3、拯時(shí)_血描結(jié)抱一和數(shù)枷的 遠(yuǎn)岸 這三個(gè)方面的內(nèi)容匚4.4.數(shù)據(jù)給構(gòu)按邏艸結(jié)構(gòu)可分為兩人類，它們好別是線誓島掏和11線住結(jié)_，5.5.域性給構(gòu)中元累之問存在二戲二關(guān)系昇形箱鞫屮元蹇之間存在一對(duì)墨關(guān)乘.圖形緒構(gòu)中元蹇之間存在 姜対婁關(guān)嘉.6.6.在線性結(jié)構(gòu)屮，第一個(gè)結(jié)點(diǎn)前鑒結(jié)點(diǎn)，其余海個(gè)結(jié)點(diǎn)有且只有牛前驅(qū)結(jié)點(diǎn)i&Jn-i&Jn-個(gè)結(jié)點(diǎn) 汝 宜_訂續(xù)第點(diǎn)，其余毎個(gè)結(jié)點(diǎn)有且只育丨牛扃壩結(jié)點(diǎn)，7.7.在樹形焙構(gòu)屮，樹報(bào)結(jié)點(diǎn)沒有前驅(qū) 結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有_亍前驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒有肪續(xù) 結(jié)點(diǎn).艮氽每個(gè)結(jié)成的后續(xù)結(jié)點(diǎn)數(shù)可以任意多亍。執(zhí)在圖形蜻構(gòu)中.毎個(gè)站點(diǎn)的前驅(qū)錯(cuò)點(diǎn)數(shù)和岳續(xù)結(jié)點(diǎn)數(shù)可以任盤賽個(gè)9.數(shù)抓的存

4、儲(chǔ)箱構(gòu)可用四種基木的存儲(chǔ)方祛表樂，它們分別是額序、毬式*除別和股利，10-數(shù)舸的運(yùn)算堆常用的有種，它們分別是插入制除，惓改，逵找，押序.ih -個(gè)IT法的效率可0為時(shí)間 效率和空間效率*12.初順序表屮插入讖捌階一個(gè)元壷.需發(fā)平均稲動(dòng)衷屮一半元蠹具體移動(dòng)的元貴個(gè)數(shù)與蟄遜紜 索在憲屮的號(hào)置電応13.線性表屮給點(diǎn)的集合是有限檢結(jié)點(diǎn)何的關(guān)果是 一對(duì)一一趴14.向一個(gè)悵度対亂的向傲的第1個(gè)元（lln+JlZ前插入一個(gè)元索時(shí)，需向片移動(dòng)n-kl元素15.軻一個(gè)長(zhǎng)度為刖的向?qū)徶袆h除第i個(gè)元爲(wèi)（1曲荃n）時(shí)*需閒前移動(dòng)nY個(gè)元累.簡(jiǎn)答題實(shí)例?.簡(jiǎn)述順序表和讎表存儲(chǔ)方式的持點(diǎn)*靳順序表的優(yōu)點(diǎn)是可以隧機(jī)訪問數(shù)據(jù)

5、7U索,缺點(diǎn)是:大小固定.不利亍増減結(jié)點(diǎn):（增礴結(jié)點(diǎn)操作需蠻移功無盤】一陸喪的優(yōu)點(diǎn)是采用指針方式憎減站點(diǎn)，非常方便（貝需改變揺甘捐向“不移動(dòng)結(jié)點(diǎn)嘰其缺點(diǎn)足不能誑行隨機(jī)訪問*只能順序訪問*另外.每牛結(jié)點(diǎn)1*0加指計(jì)域. 造出額外心儲(chǔ)空間憎丿二3.対籬表設(shè)靈沃站必的件用是什么？（至少說出苗茶好辿）答I其好處幷；對(duì)帶頭站點(diǎn)的越表，畫表的任何結(jié)心znf插入站點(diǎn)或刪除表m任何結(jié)點(diǎn)，所要做的都 是條改前-個(gè)結(jié)點(diǎn)的指針域，因?yàn)槿魏螙X養(yǎng)結(jié)點(diǎn)都有前馳結(jié)點(diǎn)（若鏈表沒有頭結(jié)點(diǎn)則宵尤 盂結(jié)點(diǎn)沒ft朋駆結(jié)點(diǎn)隹H前前入結(jié)點(diǎn)和刪除謹(jǐn)給點(diǎn)時(shí)揀作也雜些）U（2）燉帶頭結(jié)點(diǎn)的鏈表表頭抬針是指向頭結(jié)點(diǎn)的非空fl（岡此空表與非空表的

6、處理足 一樣禮-WORD格式-可編輯-專業(yè)資料-學(xué)習(xí)資料分享-設(shè)計(jì)題:-WORD格式-可編輯-專業(yè)資料-學(xué)習(xí)資料分享-(1 )E i殳計(jì)計(jì)算二義樹巾所有給點(diǎn)值之和的算法void siun(bitiee *bt.nit(ifbt!=O) s=s+bt-datai siun(bt-lcluld,s): suni(bt-rchild,s);(2)設(shè)計(jì)在鏈?zhǔn)浇Y(jié)構(gòu)I實(shí)現(xiàn)簡(jiǎn)單選擇誹序算法void sunpleselec ts orlkli st( Ikl 1 st *&head)lklist *p.*q.*s: int mm.t:if(head=O head-iiext=() retiinnfbr(q=h

7、ead: q!二CLq=q- next)mm=q-datai s=q:for(p=q-iiext: p!=Oip=p-iiexl) iftinnipdata)inin=p- datai s=p: if(s! =q) t=s-data: s-data=q-data: q- data=ti)數(shù)據(jù)結(jié)構(gòu)試卷（一）三、計(jì)算題（每題 6分，共24分）1.在如下數(shù)組A中鏈接存儲(chǔ)了一個(gè)線性表，表頭指針為A0.next，試寫出該線性表。A 01234605078903440-WORD格式-可編輯-專業(yè)資料-學(xué)習(xí)資料分享-567datanext3572041-WORD格式-可編輯-專業(yè)資料401110(4,7)2

8、04.畫出向小根堆中加入數(shù)據(jù)4, 2, 5, 8, 3時(shí)，每加入一1線性表為：(78 ,50 , 40 , 60 ,34 ,90 ) .02請(qǐng)畫出下圖的鄰接矩陣和鄰接表。3.已知一個(gè)圖的頂點(diǎn)集V和邊集E分別為：V=1,2,3,4,5,6,7;E=(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25;用克魯斯卡爾算法得到最小生成樹，試寫出在最小生成 樹中依次得到的各條邊。用克魯斯卡爾算法得到的最小生成樹為：(1,2)3,(4,6)4,(1,3)5,(1,4)8,(2,5)

9、10,個(gè)數(shù)據(jù)后堆的變化。見圖12-WORD格式-可編輯-專業(yè)資料-學(xué)習(xí)資料分享-圖12圖11四、閱讀算法(每題 7分，共14分)1. LinkList mynote(LinkList L)/L是不帶頭結(jié)點(diǎn)的單鏈表的頭指針if(L&L-next)q=L ； L=L next ; P=L ；51:while(p next) p=p next ;52:p next=q ; q next=NULL ; return L;請(qǐng)回答下列問題：(1 )說明語句S1的功能；查詢鏈表的尾結(jié)點(diǎn)(2)說明語句組S2的功能； 將第一個(gè)結(jié)點(diǎn)鏈接到鏈表的尾部，作為新的尾結(jié)占八、(3)設(shè)鏈表表示的線性表為(玄恫？，,an),

10、寫出 算法執(zhí)行后的返回值所表示的線性表。返回的線性表為(.a.,a迢丄)2. void ABC(BTNode * BT)-WORD格式-可編輯-專業(yè)資料-學(xué)習(xí)資料分享-if BT ABC (BT-left);ABC (BT-right); coutvdatavv;該算法的功能是：遞歸地后序遍歷鏈?zhǔn)酱鎯?chǔ)的二叉樹五、算法填空(共8分)二叉搜索樹的查找一一遞歸算法：bool Find(BTreeNode* BST,ElemType & item)if (BST=NULL)return false; / 查找失敗else if (item=BST-data) item=BST-data;查找成功ret

11、urntrue ;else if(itemdata) returnFind(BST- left_,item);elsereturn Find(BST-right,item);/if六、編寫算法（共8分）統(tǒng)計(jì)出單鏈表HL中結(jié)點(diǎn)的值等于給定值X的結(jié)點(diǎn)數(shù)。int CountX(LNode* HL,ElemType x)int CountX(LNode* HL,ElemType x) int i=0; LNode* p=HL;/i為計(jì)數(shù)器-WORD格式-可編輯-專業(yè)資料-學(xué)習(xí)資料分享-while(p!=NULL) if (P-data=x) i+;p=p-n ext;/while, 出循環(huán)時(shí)i中的值即

12、為x結(jié)點(diǎn)個(gè)數(shù) return i;/CountX數(shù)據(jù)結(jié)構(gòu)試卷(二)三、應(yīng)用題(36分)1.設(shè)一組初始記錄關(guān)鍵字序列為(45 , 80 ,48 , 40 , 22 ,78)，則分別給出第4趟簡(jiǎn)單選擇排序和第 4趟直接插入 排序后的結(jié)果。(22 , 40 , 45 , 48 , 80 , 78) , (40 , 45 , 48 , 80 , 22 , 78)2. 設(shè)指針變量p指向雙向鏈表中結(jié)點(diǎn)A，指針變量q指向被插入結(jié)點(diǎn) B，要求給出在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)B的操作序列(設(shè)雙向鏈表中結(jié)點(diǎn)的兩個(gè)指針域分別為 llink 和 rlink )。q-llink=p; q-rlink=p-rlink; p-rl

13、ink-llink=q; p-rli nk=q;3.設(shè)一組有序的記錄關(guān)鍵字序列為(13 , 18 , 24 , 35 ,47 , 50 , 62 , 83 , 90)，查找方法用二分查找，要求計(jì) 算出查找關(guān)鍵字62時(shí)的比較次數(shù)并計(jì)算出查找成功時(shí)的平均查找長(zhǎng)度。-WORD格式-可編輯-專業(yè)資料-學(xué)習(xí)資料分享-2, ASL=91*1+2*2+3*4+4*2)=25/94.設(shè)一棵樹T中邊的集合為(A , B) , (A, C), (A, D),(B , E) , (C , F), (C , G)，要求用孩子兄弟表示法(二 叉鏈表)表示出該樹的存儲(chǔ)結(jié)構(gòu)并將該樹轉(zhuǎn)化成對(duì)應(yīng)的二 叉樹。樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)略，

14、二叉樹略5. 設(shè)有無向圖G,要求給出用普里姆算法構(gòu) 造最小生成樹所走過的邊的集合。E=(1 , 3) , (1 , 2), (3 , 5), (5 , 6), (6 , 4)6.設(shè)有一組初始記錄關(guān)鍵字為(45 , 80 , 48 , 40 , 22 ,78)，要求構(gòu)造一棵二叉排序樹并給出構(gòu)造過程。四、算法設(shè)計(jì)題(16分)1.設(shè)有一組初始記錄關(guān)鍵字序列(K1 , K2，Kn),要求設(shè)計(jì)一個(gè)算法能夠在0(n)的時(shí)間復(fù)雜度內(nèi)將線性表劃分成兩部分，其中左半部分的每個(gè)關(guān)鍵字均小于Ki,右半部分的每個(gè)關(guān)鍵字均大于等于Ki。設(shè)有一組初始記錄關(guān)鍵字序列(K1, K2，Kn),要求設(shè)計(jì)一個(gè)算法能夠在 0(n)的

15、時(shí)間復(fù)雜度內(nèi)將線性表劃分成兩 部分，其中左半部分的每個(gè)關(guān)鍵字均小于Ki,右半部分的每個(gè)關(guān)鍵字均大于等于 Ki。void quickpass(int r, int s, int t)-WORD格式-可編輯-專業(yè)資料-學(xué)習(xí)資料分享-int i=s, j=t, x=rs;while(ivj)while (ix) j=j-1; if (ivj)ri=rj;i=i+1;while (ivj & rin ext) for(q=hb;q!=0;q=q-n ext) if(q-data=p-data) break;if(q!=O) t=(lklist *)malloc(sizeof(lklist);t-dat

16、a=p-data;t-next=hc; hc=t;數(shù)據(jù)結(jié)構(gòu)試卷(三)-WORD格式-可編輯-專業(yè)資料-學(xué)習(xí)資料分享-36 , 15 , 40 , 63 , 22 )，散三、計(jì)算題（每題10分，共30分）1.已知二叉樹的前序遍歷序列是AEFBGCDHIKJ ，中序遍 歷序列是EFAGBCHKIJD ，畫出此二叉樹，并畫出它的后 序線索二叉樹NULL KFlife2 .已知待散列的線性表為（列用的一維地址空間為0.6，假定選用的散列函數(shù)是H ( K)=K mod 7 ，若發(fā)生沖突采用線性探查法處理，試：H(36)=36 mod 7=1;H i (22)=(1+1)mod 7=2;.沖突H(15)=

17、15 mod 7=1;.沖突出(22)=(2+1)mod 7=3;H i (15)=(1+1) mod 7=2;H(40)=40 mod 7=5;H(63)=63 mod 7=0;H(22)=22 mod 7=1;.沖突（1 ）計(jì)算出每一個(gè)元素的散列地址并在下圖中填寫出散列表：01234566336152240-WORD格式-可編輯-專業(yè)資料-學(xué)習(xí)資料分享-(2)求出在查找每一個(gè)元素概率相等情況下的平均查找長(zhǎng) 度。ASL= 1 211 3“.653 .已知序列(10 , 18 , 4 , 3 , 6 , 12 , 1 , 9 , 18, 8) 請(qǐng)用快速排序?qū)懗雒恳惶伺判虻慕Y(jié)果。(8,9,4,3

18、,6,1),10,(12,18,18) (1,643),8,(9),10,12,(18,18)1, (3,4,6),8,9,10,12,18,(18)1.3, (4,6),8,9,10,12,18,181.3, 4,6,8,9,10,12,18,18四、算法設(shè)計(jì)題(每題15分，共30分)1 .設(shè)計(jì)在單鏈表中刪除值相同的多余結(jié)點(diǎn)的算法。設(shè)計(jì)在單鏈表中刪除值相同的多余結(jié)點(diǎn)的算法。typedef int datatype;typedef struct node datatype data; struct node *next;lklist;void delredundant(lklist *&hea

19、d)lklist *p,*q,*s;for(p=head;p!=0;p=p-n ext)for(q=p-n ext,s=q;q!=0;)if (q-data=p-data)s-n ext=q-n ext;free(q);q=s-n ext;else s=q,q=q-n ext;2 .設(shè)計(jì)一個(gè)求結(jié)點(diǎn)x在二叉樹中的雙親結(jié)點(diǎn)算法。設(shè)計(jì)一個(gè)求結(jié)點(diǎn)x在二叉樹中的雙親結(jié)點(diǎn)算法。typedef struct node datatype data; struct node *lchild,*rchild; bitree;-WORD格式-可編輯-專業(yè)資料-學(xué)習(xí)資料分享-bitree *q20; int r=O,

20、f=O,flag=O;void preorder(bitree *bt, char x)if (bt!=O & flag=0)if (bt-data=x) flag=1; return;elser=(r+1)%20;qr=bt;preorder(bt-lchild,x); preorder(bt-rchild,x); void parent(bitree *bt,char x)int i;preorder(bt,x);for(i=f+1; ilchild-data=x | qi-rchild-data) break;if (flag=0) printf(not found xn);else i

21、f (idata);elseprintf(not parent);數(shù)據(jù)結(jié)構(gòu)試卷(四)三、計(jì)算題(每題10分，共30分)1、畫出廣義表 LS=( ) , (e) , (a , (b , c , d )的頭尾鏈表存儲(chǔ)結(jié)構(gòu)。-WORD格式-可編輯-專業(yè)資料-學(xué)習(xí)資料分享-1 ,A1 I -0b0 d(1) ABCDEF; BDEFCAIJKHGBDEFCA ；(2) ABCDEFGHIJK;2、下圖所示的森林: 求樹(a)的先根序列和后根序列;(2)求森林先序序列和中序序列;ABCDEF; BDEFCA ；(3)將此森林轉(zhuǎn)換為相應(yīng)的二叉樹;BDEFCAIJKHG林轉(zhuǎn)換為相應(yīng)的LS0 Ic|101d林

22、轉(zhuǎn)換為相應(yīng)的二叉樹;(2) ABCDEFGHIJK;二叉樹;AGBCHIDJEFK-WORD格式-可編輯-專業(yè)資料-學(xué)習(xí)資料分享-3、設(shè)散列表的地址范圍是0.9 ，散列函數(shù)為H ( key )= (key 2 +2)MOD 9,并采用鏈表處理沖突，請(qǐng)畫出元素7、4、5、3、6、2、8、9依次插入散列表的存儲(chǔ)結(jié)構(gòu)。H(4)=H(5)=0,H(3)=H(6)=H(9)=2,H(8)=3,H(2)=H(7)=60123456789四、算法設(shè)計(jì)題(每題10分，共30分)1 .設(shè)單鏈表中有僅三類字符的數(shù)據(jù)元素(大寫字母、數(shù)字和其它字符)，要求利用原單鏈表中結(jié)點(diǎn)空間設(shè)計(jì)出三個(gè) 單鏈表的算法，使每個(gè)單鏈表只

23、包含同類字符。設(shè)單鏈表中有僅三類字符的數(shù)據(jù)元素(大寫字母、數(shù)字和其 它字符),要求利用原單鏈表中結(jié)點(diǎn)空間設(shè)計(jì)出三個(gè)單鏈表 的算法，使每個(gè)單鏈表只包含同類字符。typedef char datatype;typedef struct node datatype data; struct node *next;lklist;-WORD格式-可編輯-專業(yè)資料-學(xué)習(xí)資料分享-void split(lklist*head,lklist*&ha,lklist*&hb,lklist *&hc)lklist *p; ha=0,hb=0,hc=0;for(p=head;p!=0;p=head)head=p-ne

24、xt; p-next=O;if (p-data=A&p-datan ext=ha; ha=p;else if (p-data=0&p-datanext=hb; hb=p; else p-next=hc; hc=p;2.設(shè)計(jì)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上交換二叉樹中所有結(jié)點(diǎn)左右子樹 的算法。設(shè)計(jì)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上交換二叉樹中所有結(jié)點(diǎn)左右子樹 的算法。typedef struct node int data; struct node *lchild,*rchild; bitree;void swapbitree(bitree *bt)bitree *p;if(bt=0) return;swapbitree(bt-

25、lchild); swapbitree(bt-rchild); p=bt-lchild;bt-lchild=bt-rchild;bt-rchild=p;3.在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上建立一棵二叉排序樹。 在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上建立一棵二叉排序樹。-WORD格式-可編輯-專業(yè)資料-學(xué)習(xí)資料分享-#define n 10typedef struct nodeint key; struct node *lchild,*rchild;bitree;-WORD格式-可編輯-專業(yè)資料-學(xué)習(xí)資料分享-void bstinsert(bitree *&bt,int key)if (bt=0)bt=(bitree *)mallo

26、c(sizeof(bitree); bt-key=key;bt-lchild=bt-rchild=O;else if (bt-keykey) bstinsert(bt-lchild,key); else bstinsert(bt-rchild,key);void createbsttree(bitree *&bt)int i;for(i=1;iv=n;i+) bstinsert(bt,random(100);數(shù)據(jù)結(jié)構(gòu)試卷(五) 三、應(yīng)用題(32分)1.設(shè)某棵二叉樹的中序遍歷序列為DBEAC，前序遍歷序列為 ABDEC，要求給出該二 叉樹的的后序遍歷序列。DEBCA2.設(shè)無向圖G (如右圖所示)

27、，給出該圖的最小生成樹上邊 的集合并計(jì)算最小生成樹各邊上的權(quán)值之和。E=(1,5),(5,2),(5,3),(3,4),W=103.設(shè)一組初始記錄關(guān)鍵字序列為(15，17，18，22，35，51，60)，要求計(jì)算出成功查找時(shí)的平均查找長(zhǎng)度。ASL=(1*1+2*2+3*4)/7=17/74.設(shè)散列表的長(zhǎng)度為-WORD格式-可編輯-專業(yè)資料-學(xué)習(xí)資料分享-8，散列函數(shù)H(k)=k mod 7，初始記錄關(guān)鍵字序列為(25，31，8，27，13，68)，要求分別 計(jì)算出用線性探測(cè)法和鏈地址法作為解決沖突方法的平 均查找長(zhǎng)度。ASL1=7/6，ASL2=4/3四、算法設(shè)計(jì)題(28分)1.設(shè)計(jì)判斷兩個(gè)二

28、叉樹是否相同的算法。設(shè)計(jì)判斷兩個(gè)二叉樹是否相同的算法。typedef struct node datatype data; struct node *lchild,*rchild; bitree;int judgebitree(bitree *bt1,bitree *bt2)if (bt1=0 & bt2=0) return(1);elseif(bt1=O|bt2=0|bt1-data!=bt2-data) return(O);elsereturn(judgebitree(bt1-lchild,bt2-lchild)*judgebitre e(bt1-rchild,bt2-rchild);2.

29、設(shè)計(jì)兩個(gè)有序單鏈表的合并排序算法。設(shè)計(jì)兩個(gè)有序單鏈表的合并排序算法。void mergelklist(lklist *ha,lklist *hb,lklist *&hc)lklist *s=hc=0;while(ha!=0 & hb!=0)if(ha-datadata)if(s=O) hc=s=ha; elses-next=ha; s=ha;ha=ha-next;-WORD格式-可編輯-專業(yè)資料-學(xué)習(xí)資料分享-else if(s=0) hc=s=hb; else s-next=hb;s=hb;hb=hb-n ext;if(ha=0) s-next=hb; else s-next=ha;數(shù)據(jù)結(jié)構(gòu)

30、試卷(六)四、算法設(shè)計(jì)題(20分)1.設(shè)計(jì)在順序有序表中實(shí)現(xiàn)二分查找的算法。設(shè)計(jì)在順序有序表中實(shí)現(xiàn)二分查找的算法。struct record int key; int others;int bisearch(struct record r , int k)int low=0,mid,high=n-1;while(lowv=high)mid=(low+high)/2;if(rmid.key=k)return(mid+1);elseif(rmid.keyk) high=mid-1; else low=mid+1;return(O);2.設(shè)計(jì)判斷二叉樹是否為二叉排序樹的算法。設(shè)計(jì)判斷二叉樹是否為二叉

31、排序樹的算法。int minnum=-32768,flag=1;typedef struct nodeint key; struct node*lchild,*rchild;bitree;void inorder(bitree *bt)-WORD格式-可編輯-專業(yè)資料-學(xué)習(xí)資料分享-if(bt!=O)inorder(bt-lchild);if(minnumbt-key)flag=O; minnum=bt-key;inorder(bt-rchild);3.在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上設(shè)計(jì)直接插入排序算法 在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上設(shè)計(jì)直接插入排序算法void straightinsertsort(lklist *&h

32、ead)lklist *s,*p,*q; int t;if (head=0 | head-next=0) return;else for(q=head,p=head-next;p!=0;p=q-next)for(s=head;s!=q-next;s=s-next)if(s-datap-data) break;if(s=q-n ext)q=p;elseq-next=p-next;p-next=s-next;s-next=p; t=p-data;p-data=s-data;s-data=t;數(shù)據(jù)結(jié)構(gòu)試卷(七)四、算法設(shè)計(jì)題(20分)1.設(shè)計(jì)在鏈?zhǔn)浇Y(jié)構(gòu)上實(shí)現(xiàn)簡(jiǎn)單選擇排序算法。設(shè)計(jì)在鏈?zhǔn)浇Y(jié)構(gòu)上實(shí)現(xiàn)簡(jiǎn)單

33、選擇排序算法。void simpleselectsorlklist(lklist *&head)lklist *p,*q,*s; int min,t;if(head=0 |head-next=0) return;-WORD格式-可編輯-專業(yè)資料-學(xué)習(xí)資料分享-for(q=head; q!=0;q=q-n ext)-WORD格式-可編輯-專業(yè)資料-學(xué)習(xí)資料分享-min=q-data; s=q;for(p=q-n ext;p!=O;p=p-n ext)if(min p-data)mi n=p-data; s=p;if(s!=q)t=s-data;s-data=q-data;q-data=t;2.設(shè)

34、計(jì)在順序存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)求子串算法。 設(shè)計(jì)在順序存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)求子串算法。void substring(char s , long start, long count, char t)long i,j,length=strlen(s);if (startlength) printf(The copy position is wrong);else if (start+count-1length)printf(Toocharacters to be copied);else for(i=start-1,j=0; ikey=x) return; else if (bt-keyx) level(bt-

35、lchild,x); else level(bt-rchild,x);數(shù)據(jù)結(jié)構(gòu)試卷(八)四、算法設(shè)計(jì)題(20分)1.設(shè)計(jì)一個(gè)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上統(tǒng)計(jì)二叉樹中結(jié)點(diǎn)個(gè)數(shù)的算 法。設(shè)計(jì)一個(gè)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上統(tǒng)計(jì)二叉樹中結(jié)點(diǎn)個(gè)數(shù)的算法。void countnode(bitree *bt,int &count)if(bt!=0)count+;countnode(bt-lchild,count);countnode(bt-rchild,count);2.設(shè)計(jì)一個(gè)算法將無向圖的鄰接矩陣轉(zhuǎn)為對(duì)應(yīng)鄰接表的算 法。設(shè)計(jì)一個(gè)算法將無向圖的鄰接矩陣轉(zhuǎn)為對(duì)應(yīng)鄰接表的算法。typedef structint vertexm;e

36、dgemm;gadjmatrix;typedef struct node1int info;int adjvertex; struct node1 *nextarc;glinklistnode;typedef struct node2int vertexinfo;glinklistnode *firstarc;glinkheadnode;voidadjmatrixtoadjlist(gadjmatrixg1 ,glinkheadnode g2)int i,j; glinklistnode *p;for(i=0;iv=n-1;i+) g2i.firstarc=0;for(i=0;i=n-1;i+

37、) for(j=0;jadjvertex=j;p-n extarc=gi.firstarc; gi.firstarc=p;p=(glinklistnode*)malloc(sizeof(glinklistnode);p-adjvertex=i;p-n extarc=gj.firstarc; gj.firstarc=p;數(shù)據(jù)結(jié)構(gòu)試卷(九)五、算法設(shè)計(jì)題(20分)1.設(shè)計(jì)計(jì)算二叉樹中所有結(jié)點(diǎn)值之和的算法。設(shè)計(jì)計(jì)算二叉樹中所有結(jié)點(diǎn)值之和的算法。void sum(bitree *bt,int &s)if(bt!=O) s=s+bt-data; sum(bt-lchild,s);sum(bt-rchil

38、d,s);2.設(shè)計(jì)將所有奇數(shù)移到所有偶數(shù)之前的算法。設(shè)計(jì)將所有奇數(shù)移到所有偶數(shù)之前的算法。void quickpass(int r, int s, int t)int i=s,j=t,x=rs;while(ij)-WORD格式-可編輯-專業(yè)資料-學(xué)習(xí)資料分享-if (ij)if (ij)p!=0;while(ivj&rj%2=0)j=j-1;ri=rj;i=i+1;while(inext=O) return(1);else for(q=head,p=head-next;q=p,p=p-n ext)if(q-datap-data) retu rn( 0); return(1);數(shù)據(jù)結(jié)構(gòu)試卷(十)

39、三、算法設(shè)計(jì)題(22分)1.設(shè)計(jì)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上合并排序的算法。設(shè)計(jì)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上合并排序的算法。void mergelklist(lklist *ha,lklist *hb,lklist *&hc) lklist *s=hc=0;while(ha!=0 & hb!=0)if(ha-datadata)if(s=O) hc=s=ha; elses-next=ha; s=ha;ha=ha-next;-WORD格式-可編輯-專業(yè)資料-學(xué)習(xí)資料分享-else if(s=0) hc=s=hb; else s-next=hb;s=hb;hb=hb-n ext;if(ha=0) s-next=hb; el

40、se s-next=ha;2.設(shè)計(jì)在二叉排序樹上查找結(jié)點(diǎn)X的算法。設(shè)計(jì)在二叉排序樹上查找結(jié)點(diǎn)X的算法。bitree *bstsearch1(bitree *t, int key)bitree *p=t;while(p!=0) if (p-key=key) return(p);else if(p-keykey)p=p-lchild; else p=p-rchild;return(O);3.設(shè)關(guān)鍵字序列(k 1, k2，kn-1)是堆，設(shè)計(jì)算法將關(guān)鍵字序列(k1, k2，kn-1 , x)調(diào)整為堆。設(shè)關(guān)鍵字序列(k , k2，kn-1 )是堆，設(shè)計(jì)算法將關(guān)鍵字 序列(k1, k2，kn-1 , x

41、)調(diào)整為堆。void adjustheap(int r ,int n)int j=n,i=j/2,temp=rj-1;while(i=1) if (temp=ri-1)break;elserj-1=ri-1; j=i; i=i/2;rj-1=temp;-WORD格式-可編輯-專業(yè)資料-學(xué)習(xí)資料分享-1.線性表為:2.鄰接矩陣:(78，50，40，60，34，90)0 111010 10 1110 1110 10 10 1110數(shù)據(jù)結(jié)構(gòu)試卷(一)參考答案三、計(jì)算題(每題6分，共24分)鄰接表如圖11所示:123滬 L.、-L-1-1_ | -1| -1213|，丨3i工.斗1 4 1f 35 |

42、 1 - - _ 151 ,tan節(jié)2* 3一* 4 j - |圖113.用克魯斯卡爾算法得到的最小生成樹為：(1,2)3,(4,6)4,(1,3)5,(1,4)8,(2,5)10,(4,7)204.見圖12圖12-WORD格式-可編輯-專業(yè)資料-學(xué)習(xí)資料分享-四、讀算法(每題7分，共14分)1.(1 )查詢鏈表的尾結(jié)點(diǎn)(2)將第一個(gè)結(jié)點(diǎn)鏈接到鏈表的尾部，作為新的尾結(jié)點(diǎn)(3)返回的線性表為(a2,a3,an,ai)2.遞歸地后序遍歷鏈?zhǔn)酱鎯?chǔ)的二叉樹。五、法填空(每空2分，共8分)trueBST-leftBST-right六、編寫算法(8分)int CountX(LNode* HL,ElemTy

43、pe x) int i=0; LNode* p=HL;/i為計(jì)數(shù)器while(p!=NULL) if (P-data=x) i+; p=p-n ext;/while, 出循環(huán)時(shí)i中的值即為x結(jié)點(diǎn)個(gè)數(shù) return i;/CountX數(shù)據(jù)結(jié)構(gòu)試卷(二)參考答案 四、算法設(shè)計(jì)題1.設(shè)有一組初始記錄關(guān)鍵字序列(K1 , K2，Kn)，要求設(shè)計(jì)一個(gè)算法能夠在0(n)的時(shí)間復(fù)雜度內(nèi)將線性表劃分成兩部分，其中左半部分的每個(gè)關(guān)鍵字均小于Ki,右半部分的每個(gè)關(guān)鍵字均大于等于Ki ovoid quickpass(int r, int s, int t)int i=s, j=t, x=rs;while(ivj)-

44、WORD格式-可編輯-專業(yè)資料1 .-學(xué)習(xí)資料分享-while (ivj & rjx) j=j-1; if (ivj)ri=rj;i=i+1;while (ivj & rin ext) for(q=hb;q!=0;q=q-n ext) if(q-data=p-data) break;if(q!=0) t=(lklist *)malloe(sizeof(lklist);t-data=p-data;t-next=he; he=t;數(shù)據(jù)結(jié)構(gòu)試卷(三)參考答案三、計(jì)算題-WORD格式-可編輯-專業(yè)資料-學(xué)習(xí)資料分享-2、H(36)=36 mod 7=1; mod 7=2;.沖突H(15)=15 mod

45、 7=1; mod 7=3;H i (15)=(1+1) mod 7=2;H 1 (22)=(1+1).沖突H2(22)=(2+1).沖突H(40)=40 mod 7=5;H(63)=63 mod 7=0;H(22)=22 mod 7=1;(1 ) 0 1 23、(8,9,4,3,6,1),10,(12,18,18)(1,6,4,3),8,(9),10,12,(18,18L1,(3,4,6),8,9,10,12,18,(1型1.3, (4,6),8,9,10,12,18,18_1.3, 4,6,8,9,10,12,18,18_6312436520121135= 1.6ASL=-WORD格式-可

46、編輯-專業(yè)資料-學(xué)習(xí)資料分享-四、算法設(shè)計(jì)題1.設(shè)計(jì)在單鏈表中刪除值相同的多余結(jié)點(diǎn)的算法。typedef int datatype;typedef struct node datatype data; struct node *next;lklist;void delredundant(lklist *&head)lklist *p,*q,*s;for(p=head;p!=0;p=p-n ext)for(q=p-n ext,s=q;q!=0;)if (q-data=p-data)s-n ext=q-n ext;free(q);q=s-n ext;else s=q,q=q-n ext;2.設(shè)計(jì)一

47、個(gè)求結(jié)點(diǎn)x在二叉樹中的雙親結(jié)點(diǎn)算法。typedef struct node datatype data; struct node *lchild,*rchild; bitree;bitree *q20; int r=O,f=O,flag=O;void preorder(bitree *bt, char x)if (bt!=0 & flag=0)if (bt-data=x) flag=1; return;elser=(r+1)%20;qr=bt;preorder(bt-lchild,x); preorder(bt-rchild,x); void parent(bitree *bt,char x)

48、-WORD格式-可編輯-專業(yè)資料-學(xué)習(xí)資料分享-int i;preorder(bt,x);-WORD格式-可編輯-專業(yè)資料9-學(xué)習(xí)資料分享-elseLS人11A1-一0 a1 .A1 1-0b1 lL0c0 d(1) ABCDEF; BDEFCAIJKHGBDEFCA ;(2) ABCDEFGHIJK;林轉(zhuǎn)換為相應(yīng)的二叉樹；for(i=f+1; ilchild-data=x | qi-rchild-data) break;if (flag=0) printf(not found xn);else if (idata); printf(not parent);數(shù)據(jù)結(jié)構(gòu)試卷(四)參考答案二、計(jì)算題

49、3. H(4)=H(5)=0,H(3)=H(6)=H(9)=2,H(8)=3,H(2)=H(7)=601234567811士0 e-WORD格式-可編輯-專業(yè)資料bitree *p;if(bt=0) return;swapbitree(bt-lchild); swapbitree(bt-rchild);- 學(xué)習(xí)資料分享 四、算法設(shè)計(jì)題1. 設(shè)單鏈表中有僅三類字符的數(shù)據(jù)元素 (大寫字母、數(shù)字和 其它字符 )，要求利用原單鏈表中結(jié)點(diǎn)空間設(shè)計(jì)出三個(gè)單 鏈表的算法，使每個(gè)單鏈表只包含同類字符。typedef char datatype;typedef struct node datatype data

50、;*next;lklist;void split(lklist*&hb,lklist *&hc)lklist *p; ha=0,hb=0,hc=0;for(p=head;p!=0;p=head)head=p-next; p-next=0;if (p-data=A &p-next=ha; ha=p;else if (p-data=0 &p-next=hb; hb=p; else p-next=hc; hc=p;2. 設(shè)計(jì)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上交換二叉樹中所有結(jié)點(diǎn)左右子樹 的算法。*head,lkliststruct node*&ha,lklistp-datadatalchild); swapbitre

51、e(bt-rchild);- 學(xué)習(xí)資料分享 -WORD格式-可編輯-專業(yè)資料1. 設(shè)單鏈表中有僅三類字符的數(shù)據(jù)元素（大寫字母、數(shù)字和其它字符 ），要求利用原單鏈表中結(jié)點(diǎn)空間設(shè)計(jì)出三個(gè)單bitree *p;if(bt=0) return;swapbitree(bt-lchild); swapbitree(bt-rchild);- 學(xué)習(xí)資料分享 *&ha,lklistp-datadatanext; p-next=0;if (p-data=A & p-next=ha; ha=p;else if (p-data=0 & p-next=hb; hb=p; else p-next=hc; hc=p;2.設(shè)

52、計(jì)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上交換二叉樹中所有結(jié)點(diǎn)左右子樹的算法。typedef struct node int data; struct node *lchild,*rchild; bitree;void swapbitree(bitree *bt)-WORD格式-可編輯-專業(yè)資料1. 設(shè)單鏈表中有僅三類字符的數(shù)據(jù)元素（大寫字母、數(shù)字和其它字符 ），要求利用原單鏈表中結(jié)點(diǎn)空間設(shè)計(jì)出三個(gè)單bitree *p;if(bt=0) return;swapbitree(bt-lchild); swapbitree(bt-rchild);- 學(xué)習(xí)資料分享 *&ha,lklistp-datadatanext; p-n

53、ext=0;if (p-data=A & p-next=ha; ha=p;else if (p-data=0 & p-next=hb; hb=p; else p-next=hc; hc=p;2. 設(shè)計(jì)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上交換二叉樹中所有結(jié)點(diǎn)左右子樹的算法。typedef struct node int data; struct node *lchild,*rchild; bitree;void swapbitree(bitree *bt)-WORD格式-可編輯-專業(yè)資料1. 設(shè)單鏈表中有僅三類字符的數(shù)據(jù)元素（大寫字母、數(shù)字和其它字符 ），要求利用原單鏈表中結(jié)點(diǎn)空間設(shè)計(jì)出三個(gè)單bitree *p;i

54、f(bt=0) return;swapbitree(bt-lchild); swapbitree(bt-rchild);- 學(xué)習(xí)資料分享 *&ha,lklistp-datadatanext; p-next=0;if (p-data=A & p-next=ha; ha=p;else if (p-data=0 & p-next=hb; hb=p; else p-next=hc; hc=p;2. 設(shè)計(jì)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上交換二叉樹中所有結(jié)點(diǎn)左右子樹的算法。typedef struct node int data; struct node *lchild,*rchild; bitree;void swapbitree(bitree *bt)-WORD格式-可編輯-專業(yè)資料1. 設(shè)單鏈表中有僅三類字符的數(shù)據(jù)元素（大寫字母、數(shù)字和其它字符 ），要求利用原單鏈表中結(jié)點(diǎn)空間設(shè)計(jì)出三個(gè)單bitree *p;if(bt=0) return;swapbitree(bt-lchild); swapbitree(bt-rchild);- 學(xué)習(xí)資料分享 *&ha,lklistp-datadatanex