《數(shù)據(jù)結(jié)構(gòu)》習(xí)題集

1、第第15頁(yè)數(shù)據(jù)結(jié)構(gòu)習(xí)題集第一章 序論思考題：1.1:抽象數(shù)據(jù)類(lèi)型作業(yè)題：12 設(shè)有數(shù)據(jù)結(jié)構(gòu)（，R D=d1， d2， d3, d4 R=r1r2d1d2d2d3d3d4, （y+1）*（y+1) y+；（6)x=91； y=100;while （ y0 if（x100) x-=10； y; elsex+ ；（7）for( i=0； in； for（j=i； jn； j+）for（ k=j; kn; k+）x+=2；1。4X,YZ1。5 已知 k 階斐波那契序列的定義為:f =0，f =0,，f=1；01f =f+f+fk1,n=k，k+1，nn2nkkmkm式在函數(shù)參數(shù)表中出現(xiàn).第二章 線(xiàn)性表

2、思考題：2.1 描述以下三個(gè)概念的區(qū)別:頭指針、頭結(jié)點(diǎn)、首元結(jié)點(diǎn).2。2 描述以下幾個(gè)概念：順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)、順序表、有序表.作業(yè)題：LaxLaLaxLa（1LaLa 不帶頭結(jié)點(diǎn)。25（a1a，.。.， a ，a）逆置為（a，a, ., a，a)2n-1nnn1212.6 試寫(xiě)一個(gè)算法，對(duì)帶頭結(jié)點(diǎn)的單鏈表實(shí)現(xiàn)就地逆置。27LLLL2。82.7L2.9ABAB“C。2101,s21所指結(jié)點(diǎn)的直接前驅(qū)。待刪結(jié)點(diǎn)待刪結(jié)點(diǎn)s圖 2-12。112。12n(1)不借助輔助數(shù)組;（2）（n。2.13L=(a，a,a。a。試寫(xiě)123nO（n）LL=（a,a。，a。 .，a,a13n42第三章 棧和隊(duì)

3、列思考題：3。1 簡(jiǎn)述棧和線(xiàn)性表的差別.A、B、C、D,寫(xiě)出所有可能的出棧序列。簡(jiǎn)述棧和隊(duì)列的相同點(diǎn)和差異。3。4S8(1，2,3，4，5,6，7,（1)algo1（S）S（2）在（1）algo2（S，5),S序列。void algo1(Stack S int 10， i， whil（!StackEmpty（S) n+； Pop（S, an； fo（i=1； i=n; i+) Push（S， ai；void algo2(Stack S, int e)Stack T； int d;InitStack（T)； while！EmptyStack（S）Pop(S,d)；if（d!=e） Push(T,

4、d); whil（！StackEmpty（TPop(T，d)； Push(S，d)；Q（1，2,3，4，5,6,7，8).algo3（Q）后,Qvoid algo3(Queue Stack S；int d;InitStack(S）;while！QueueEmpty(Q) DeQueue（Q，d）; Push（S，d)； whil（！StackEmpty（S)Pop（S,d）; EnQueue（Q，d）;作業(yè)題：試寫(xiě)一個(gè)算法，識(shí)別依次讀入的一個(gè)以為結(jié)束符的字符序列是否為形如“1212且序列 是序列 的逆序。例如,“a+bb+a”是屬于該模式的字符序列，而“121331”則不是。和“、花括號(hào)和“（

5、的順序表中).a（b+c）d)/e 3。9C3。10不設(shè)頭指針。試編寫(xiě)相應(yīng)的隊(duì)列初始化、入隊(duì)和出隊(duì)的算法。311rearlength試給出此循環(huán)隊(duì)列的隊(duì)滿(mǎn)條件,并寫(xiě)出相應(yīng)的入隊(duì)和出隊(duì)算法(在出隊(duì)算法中要傳遞回隊(duì)頭元素的值。3.12（所謂“回文”是指正讀和反讀都相同的字符序列,如“xxyzyxx”是回文，而“abcab”則不是回文)。第五章 多維數(shù)組51 已知多維數(shù)組 A2233按行優(yōu)先方式存儲(chǔ)。試按存儲(chǔ)位置的先后次序，列出所有數(shù)組元素 Aijkl序列(為了簡(jiǎn)化表達(dá),可以只列出ijk,l0021“021”60的地址為 1000，求:（1)A 的體積;（2）最后一個(gè)元素 A57的地址；（3)按行主

6、序方式存儲(chǔ)時(shí),A24的地址;（4)按列主序方式存儲(chǔ)時(shí),A24的地址;Ann，aaa.a 11a12a13.a1n 232naC.3n . ann將其上三角的元素逐行存于數(shù)組 B0。.m-1中（m 充分大)，使得 Bk=a 且ijkf(i）+f（j）+cffc（ff121212項(xiàng)。5。4 設(shè)有一個(gè)準(zhǔn)對(duì)角矩陣aa11a12a 2122aa33aa43.a2m1,2m1a2m1,2m 2m,2m1a2m,2m按以下方式存于一維數(shù)組 B4m中:a11a11a12a21a22a33a34a43.。aa2m1，ij。a2m,2m2m寫(xiě)出由一對(duì)下標(biāo)(i,j)求 k 的轉(zhuǎn)換公式。5。5已知稀疏矩陣A如下：45

7、02A 0001005306000004007（1）用三元組表作為存儲(chǔ)結(jié)構(gòu)，繪出相應(yīng)的三元組表示意圖；（2)用十字鏈表作為存儲(chǔ)結(jié)構(gòu)，繪出相應(yīng)的十字鏈表示意圖。56ABCAB,C（有序順序表歸并的處理方法。有非零元素及其下標(biāo)。試編寫(xiě)一個(gè)算法，實(shí)現(xiàn)以矩形陣列的形式打印用十字鏈表表示的稀疏矩陣.第六章 樹(shù)和二叉樹(shù)33X1，X描述滿(mǎn)足下列條件的二叉樹(shù)形態(tài)：（1）(2） 后序遍歷序列與中序遍歷序列相同；（3) 先序遍歷序列與后序遍歷序列相同;HkHk1序?qū)θ拷Y(jié)點(diǎn)編號(hào)，問(wèn)：(1） 各層的結(jié)點(diǎn)數(shù)目是多少?i（若存在)的編號(hào)是多少？ij（若存在)的編號(hào)是多少？ikn11，n22k6。6nk0結(jié)點(diǎn)。試求該樹(shù)含

8、有的葉子結(jié)點(diǎn)的數(shù)目。67nm1“0定和不一定)填寫(xiě)下表：已知nmnmnmnm先序遍歷時(shí)nm中序遍歷時(shí)nm后序遍歷時(shí)nm（注:如果離 n 和 m 的最近的共同祖先X 存在，且n 位于 X 的左子樹(shù)中,m 位于 X 的右子樹(shù)中，則稱(chēng)“n 在 m 的左方”或“m 在 n 的右方”。)6。861遍歷序列和后根遍歷序列.AABCDEFGHIJK圖 圖 6-16.9 將如圖 62 所示的森林轉(zhuǎn)化為對(duì)應(yīng)的二叉樹(shù).ABCDABCDEFGHIJKLMNO圖 6-2圖 6-2ABCAABCABCAABCBCDEFGHIJKL圖 圖 6-3611DCBGEAHFIJK,DCEGBFHKJIA請(qǐng)畫(huà)出該二叉樹(shù)。6。12

9、T GFKDAIEBCHJDIAEKFCJHBGT.6。13F ABCDEFGHIJKLCBEFDGAJIKLHF。614文中出現(xiàn)的次數(shù)分別為（7，19，2，6，32,3，2，10，試解答下列問(wèn)題：（1）畫(huà)出出 huffman 樹(shù)；（2)huffman(3）6。156.16 試編寫(xiě)算法,實(shí)現(xiàn)將二叉樹(shù)所有結(jié)點(diǎn)的左右子樹(shù)互換. 6。17 寫(xiě)出按層次遍歷二叉樹(shù)的算法.6。18 寫(xiě)出判斷給定二叉樹(shù)是否為完全二叉樹(shù)的算法.6。19 寫(xiě)出判斷兩棵給定二叉樹(shù)是否相似的算法。(注：兩棵二叉樹(shù)B1 和 B2 相似是指：B1 和 B2 皆空，或者皆不空且B1 的左、右子樹(shù)和 B2 的左、右子樹(shù)分別相似。)6.20

10、 利用棧的基本操作，寫(xiě)出二叉樹(shù)先序遍歷的非遞歸算法。6。21 寫(xiě)出統(tǒng)計(jì)樹(shù)中葉子結(jié)點(diǎn)個(gè)數(shù)的算法，樹(shù)用孩子兄弟鏈表表示。6。22 寫(xiě)出計(jì)算樹(shù)的深度的算法,樹(shù)用孩子兄弟鏈表表示。K寫(xiě)出計(jì)算二叉樹(shù)深度的算法。V1V1V5V6V2V4V37.171請(qǐng)給出該圖的鄰接矩陣示意圖鄰接表示意圖逆鄰接表圖 7-1圖 7-17。2G7-21索序列和廣度優(yōu)先搜索序列，并畫(huà)出相應(yīng)的深度優(yōu)先生成樹(shù)和廣度優(yōu)先生成樹(shù).123456789101000000101020010001000300010001004000010001050000010001611000000007001000000181001000010900001

11、0100110 1000010000圖 727。3 無(wú)向帶權(quán)圖如圖 73 所示，(1PrimKruskal9E9E3B7456FA5D2355GC465H圖 7-37。4 有向圖如圖 74 所示，試寫(xiě)出其所有可能的拓?fù)湫蛄?。V1V1V2V3V4V5V6圖 圖 7-47.5Dijkstra 75 A D、P S 各步的狀態(tài)。44B615E89A2C4G10125DF37-576 試在鄰接矩陣存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)圖的基本操作：， InsertAr（G，v,w， DeleteVex（G,v)DeleteArc(G,，w。7.7InsertVex（G,v)， InsertArc（G,v,wDeleteVex

12、（G，v）DeleteArc（G，v，w）.78nint Indegreen中。7.9ViVj（i！=j)的路徑.710ViVj(i！=j）的路徑.7.11 以鄰接表作為存儲(chǔ)結(jié)構(gòu)，實(shí)現(xiàn)求單源最短路徑的 Dijkstra 算法。第九章 查找9。1n三種情況下分別討論兩者在等概率時(shí)平均查找長(zhǎng)度是否相同？ (1）K（2)查找成功,且表中只有一個(gè)關(guān)鍵字等于給定值 K 的記錄；（3）K些記錄。9.2 試分別寫(xiě)出在對(duì)有序線(xiàn)性表e、fg9。313ASL。9.4 已知如下所示長(zhǎng)度為 12 的表：（Jan， Feb， Mar， Apr， May, Jun， July， Aug, Sep， Oct， Nov,表中

13、，每個(gè)元素的查找概率分別為：（1）若對(duì)該表進(jìn)行順序查找,求查找成功的平均查找長(zhǎng)度；（2)畫(huà)出從初態(tài)為空開(kāi)始，依次插入結(jié)點(diǎn)，生成的二叉排序樹(shù); (3)計(jì)算該二叉排序樹(shù)查找成功的平均查找長(zhǎng)度;Mar9.51025,331906,4377660010，哈希函數(shù)為 H （Key）=Key 11， 求：用開(kāi)放定址線(xiàn)性探測(cè)法處理沖突，構(gòu)造哈希表 HT1,HT1ASL；用開(kāi)放定址二次探測(cè)法處理沖突，構(gòu)造哈希表 HT2,HT2ASL；HT3，HT3ASL。9。6 寫(xiě)出折半查找的遞歸算法。97字值相同的結(jié)點(diǎn)。9.8m，H(x),關(guān)鍵字，建造哈希表的算法.第十章 內(nèi)部排序101（1）直接插入排序（2) 希爾排序（取增量