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

1、”數(shù)據(jù)構(gòu)造”習(xí)題集第一章序論思考題：1.1 簡述以下術(shù)語：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對象、數(shù)據(jù)構(gòu)造、存儲構(gòu)造、數(shù)據(jù)類型、抽象數(shù)據(jù)類型作業(yè)題：1.2 設(shè)有數(shù)據(jù)構(gòu)造D,R,其中D=d1,d2,d3,d4R=r1,r2r1=,r2=(d1,d2),(d1,d3),(d1,d4),(d2,d4),(d2,d3)試?yán)L出其邏輯構(gòu)造示意圖。1.3 設(shè)n是正整數(shù)。試寫出以下程序段中用記號”標(biāo)注的語句的頻度：(1) i=1;k=0;while(i=n-1)k+=10*i;i+;(2) i=1;k=0;dok+=10*i;i+;while(i=n-1)(3) i=1;k=0;dok+=10*i;i+;while(i=n

2、);i=1;j=0;while(i+jn)if(i=(y+1)*(y+1)y+；)(6) x=91;y=100;while(y0)if(x100)x-=10;y-;elsex+;(7) for(i=0;in;i+)for(j=i;jn;j+)for(k=j;kn;k+)x+=2;1.4 試寫一算法，自大至小依次輸出順序讀入的三個整數(shù)X,Y和Z的值。1.5 k階斐波那契序列的定義為：f0=0,f1=0,fk-2=0,fk-1=1；fn=fn-1+fn-2+fn-k,n=k,k+1,試編寫求k階斐波那契序列的第m項值的函數(shù)算法，k和m均以值調(diào)用的形式在函數(shù)參數(shù)表中出現(xiàn)。第二章線性表思考題：2.1

3、描述以下三個概念的區(qū)別：頭指針、頭結(jié)點、首元結(jié)點。2.2 描述以下幾個概念：順序存儲構(gòu)造、鏈?zhǔn)酱鎯?gòu)造、順序表、有序表。作業(yè)題：2.3 順序表La中數(shù)據(jù)元素按非遞減有序排列。試寫一個算法，將元素x插到La的適宜位置上，保持該表的有序性。2.4 單鏈表La中數(shù)據(jù)元素按非遞減有序排列。按兩種不同情況，分別寫出算法，將元素x插到La的適宜位置上，保持該表的有序性：1La帶頭結(jié)點；2La不帶頭結(jié)點。2.5 試寫一個算法，實現(xiàn)順序表的就地逆置，即在原表的存儲空間將線性表a1,a2,.,an-1,an逆置為(an,an-1,.,a2,a1)2.6 試寫一個算法，對帶頭結(jié)點的單鏈表實現(xiàn)就地逆置。jz*2.7

4、 線性表L采用順序存儲構(gòu)造存放。對兩種不同情況分別寫出算法，刪除L中值一樣的多余元素，使得L中沒有重復(fù)元素：(1)L中數(shù)據(jù)元素?zé)o序排列；(2)L中數(shù)據(jù)元素非遞減有序排列。2.8 將2.7題中L的存儲構(gòu)造改為單鏈表，寫出相應(yīng)的實現(xiàn)算法。2.9 設(shè)有兩個非遞減有序的單鏈表A和Bo請寫出算法，將A和B”就地歸并成一個按元素值非遞增有序的單鏈表Co2.10 設(shè)有一個長度大于1的單向循環(huán)鏈表，表中既無頭結(jié)點，也無頭指針，s為指向表中某個結(jié)點的指針，如圖2-1所示。試編寫一個算法，刪除鏈表中指針s所指結(jié)點的直接前驅(qū)。圖2-12.11 線性表用帶頭結(jié)點的單鏈表表示，表中結(jié)點由三類字符組成：字母、數(shù)字和其他字

5、符。試編寫算法，將該線性鏈表分割成三個循環(huán)單鏈表，每個循環(huán)單鏈表中均只含有一類字符。2.12 線性表用順序存儲構(gòu)造表示，表中數(shù)據(jù)元素為n個正整數(shù)。試寫一算法，別離該表中的奇數(shù)和偶數(shù)，使得所有奇數(shù)集中放在左側(cè)，偶數(shù)集中放在右側(cè)。要求：(1)不借助輔助數(shù)組；(2)時間復(fù)雜度為O(n)。2.13 設(shè)以帶頭結(jié)點的雙向循環(huán)鏈表表示的線性表L=(a1,a2,a3,.,an)。試寫一時間復(fù)雜度為O(n)的算法，將L改造為L=(a1,a3,.,an,.,a4,a2)。第三章棧和隊列思考題：3.1 簡述棧和線性表的差異。3.2 如果進(jìn)棧序列為A、B、C、D,寫出所有可能的出棧序列jz*3.3 簡述棧和隊列的一樣

6、點和差異。3.4 棧S中存放了8個數(shù)據(jù)元素，自棧底至棧頂依次為(1,2,3,4,5,6,7,8)。1寫出在執(zhí)行了函數(shù)調(diào)用algo1(S)后，S中的元素序列。2在1的根底上，又執(zhí)行了函數(shù)調(diào)用algo2(S,5),寫出此時S中的元素序列。voidalgo1(Stack&S)inta10,i,n=0;while(!StackEmpty(S)n+;Pop(S,an);for(i=1;i=n;i+)Push(S,ai);voidalgo2(Stack&S,inte)StackT;intd;InitStack(T);while(!EmptyStack(S)Pop(S,d);if(d!=e)Push(T,d

7、);while(!StackEmpty(T)Pop(T,d);Push(S,d);3.5 隊列Q中自隊頭至隊尾依次存放著(1,2,3,4,5,6,7,8)。寫出在執(zhí)行了函數(shù)調(diào)用algo3(Q)后，Q中的元素序列。voidalgo3(Queue&Q)StackS;intd;InitStack(S);jz*while(!QueueEmpty(Q)DeQueue(Q,d);Push(S,d);)while(!StackEmpty(S)Pop(S,d);EnQueue(Q,d);)作業(yè)題：3.6 試寫一個算法，識別依次讀入的一個以為完畢符的字符序列是否為形如“序列1&序歹(J2”模式的字符序列。其中，

8、序列1和序列2中都不包含字符&,且序列2是序列1的逆序。例如，a+b&b+a是屬于該模式的字符序列，而“1+3&31那么不是。3.7 假設(shè)一個算術(shù)表達(dá)式中可以包含三種符號：圓括號”(和”)、方括號和“、花括號”和“，且這三種括號可按任意次序嵌套使用。編寫判別給定表達(dá)式中所含的括號是否正確配對的算法表達(dá)式已存入數(shù)據(jù)元素為字符的順序表中。3.8 設(shè)表達(dá)式由單字母變量、雙目運算符和圓括號組成如：”(a*(b+c)-d)/e。試寫一個算法，將一個書寫正確的表達(dá)式轉(zhuǎn)換為逆波蘭式。3.9 試用類C寫一個算法，對逆波蘭式求值。3.10 假設(shè)以帶頭結(jié)點的單循環(huán)鏈表表示隊列，只設(shè)一個尾指針指向隊尾元素，不設(shè)頭指

9、針。試編寫相應(yīng)的隊列初始化、入隊和出隊的算法。3.11 假設(shè)將循環(huán)隊列定義為：以rear和length分別指示隊尾元素和隊列長度。試給出此循環(huán)隊列的隊滿條件，并寫出相應(yīng)的入隊和出隊算法在出隊算法中要傳遞回隊頭元素的值03.12 試寫一個算法：判別讀入的一個以為完畢符的字符序列是否是“回文所謂“回文是指正讀和反讀都一樣的字符序列，如“*yzy*是回文，而“abcab那么不是回文。jz*第五章多維數(shù)組5.1多維數(shù)組A2233按行優(yōu)先方式存儲。試按存儲位置的先后次序，列出所有數(shù)組元素Aijkl序列為了簡化表達(dá)，可以只列出形如“i,j,k,l的序列，如元素A0021可表示為“0,0,2,1。5.2假設(shè)

10、有一個二維數(shù)組A0.50.7的地址為1000,求：(1)A的體積；(2)最后一個元素A57的地址；(3)按行主序方式存儲時，(4)按列主序方式存儲時，5.3 設(shè)有上三角矩陣AnXn,a11a12a22C將其上三角的元素逐行存于數(shù)組f1(i)+f2(j)+c。試推導(dǎo)出函數(shù)f1、5.4 設(shè)有一個準(zhǔn)對角矩陣,每個元素占6個字節(jié)，首元素A00A24的地址;A24的地址;a13.ana23.a2na33.a3nannB0.m-1中m充分大,使得Bk=aij且k=f2和常數(shù)C要求f1和f2中不含常數(shù)項a11a12a21a22a33a34a43a44a2m1,2m1a2m1,2ma2m,2m1a2m,2m按

11、以下方式存于一維數(shù)組B4m中:01234564m-24m-1jz*a11a12a21a22a33a34a43.aaij.a2m-1,2ma2m,2m寫出由一對下標(biāo)(i,j)求k的轉(zhuǎn)換公式5.5 稀疏夕!陣A”5如下：0100523060A0000004007(1)用三元組表作為存儲構(gòu)造，繪出相應(yīng)的三元組表示意圖；用十字鏈表作為存儲構(gòu)造，繪出相應(yīng)的十字鏈表示意圖。5.6 設(shè)稀疏矩陣A和B均以三元組順序表作為存儲構(gòu)造。試寫出計算矩陣相加C=A+B的算法，其中，C是另設(shè)的、存放結(jié)果的三元組表提示：可用類似于兩個有序順序表歸并的處理方法。5.7 試編寫一個算法，實現(xiàn)以三元組的形式打印用十字鏈表表示的稀

12、疏矩陣中所有非零元素及其下標(biāo)。5.8 試編寫一個算法，實現(xiàn)以矩形陣列的形式打印用十字鏈表表示的稀疏矩陣。第六章樹和二叉樹6.1 試分別繪出具有3個結(jié)點的樹和3個結(jié)點的二叉樹的所有不同形態(tài)。6.2 設(shè)結(jié)點X是二叉樹上一個度為1的結(jié)點，X有幾個子樹？6.3 描述滿足以下條件的二叉樹形態(tài)：(1)先序遍歷序列與中序遍歷序列一樣；(2)后序遍歷序列與中序遍歷序列一樣；(3)先序遍歷序列與后序遍歷序列一樣；6.4 一個深度為H的滿k叉樹有如下性質(zhì)：第H層上所有結(jié)點都是葉子結(jié)點，其余各層上每個結(jié)點都有k棵非空子樹。如果從1開場按自上而下、自左向右的次序?qū)θ拷Y(jié)點編號，問：(1)各層的結(jié)點數(shù)目是多少？(2)編

13、號為i的結(jié)點的父結(jié)點(假設(shè)存在)的編號是多少？jz*（3）編號為i的結(jié)點的第j個孩子d貿(mào)設(shè)存在）的編號是多少？（4）編號為i的結(jié)點有右兄弟的條件是什么？其右兄弟的編號是多少？6.5 一棵度為k的樹中有n1個度為1的結(jié)點，n2個度為2的結(jié)點，.，nk個度為k的結(jié)點，問該樹中有多少個葉子結(jié)點？6.6 在一棵含有n個結(jié)點的樹中，只有度為k的分支結(jié)點和度為0的葉子結(jié)點。試求該樹含有的葉子結(jié)點的數(shù)目。6.7 設(shè)n和m為二叉樹中兩個結(jié)點，用“1、”0、和“分別表示肯定，否認(rèn)和不一定填寫下表：先序遍歷時n在m之前？中序遍歷時n在m之前？后序遍歷時n在m之前？n在m左力n在m右力n是m祖先n是m子孫注：如果離

14、n和m的最近的共同祖先X存在，且n位于X的左子樹中，m位于X的右子樹中，那么稱“n在m的左方”或m在n的右方。6.8 一棵樹如圖6-1所示，畫出與該樹對應(yīng)的二叉樹，并寫出該樹的先根遍歷序列和后根遍歷序列。jz*6.9 將如圖6-2所示的森林轉(zhuǎn)化為對應(yīng)的二叉樹。AJ圖6-26.10 回出和以下二叉樹如圖6-3所示相應(yīng)的森林。AQQ圖6-36.11 某二叉樹的中序序列為DCBGEAHFIJK后序序列為該二叉樹。6.12 樹T的先根遍歷訪問序列為GFKDAIEBCHJDIAEKFCJHBG請回出樹T。DCEGBFHKJIA請回出后根遍歷訪問序列為jz*6.13 森林F的先根遍歷訪問序列為ABCDEF

15、GHIJKL中根遍歷訪問序列為CBEFDGAJIKLH請畫出這個森林F。6.14 假設(shè)某個電文由(a,b,c,d,e,f,g,h)8個字母組成，每個字母在電文中出現(xiàn)的次數(shù)分別為(7,19,2,6,32,3,21,10),試解答以下問題：(1)畫出出huffman樹；(2)寫出每個字母的huffman編碼；(3)在對該電文進(jìn)展最優(yōu)二進(jìn)制編碼處理后，電文的二進(jìn)制位數(shù)。6.15 寫出復(fù)制一棵二叉樹的算法。6.16 試編寫算法，實現(xiàn)將二叉樹所有結(jié)點的左右子樹互換。6.17 寫出按層次遍歷二叉樹的算法。6.18 寫出判斷給定二叉樹是否為完全二叉樹的算法。6.19 寫出判斷兩棵給定二叉樹是否相似的算法。(

16、注：兩棵二叉樹B1和B2相似是指：B1和B2皆空，或者皆不空且B1的左、右子樹和B2的左、右子樹分別相似。)6.20 利用棧的根本操作，寫出二叉樹先序遍歷的非遞歸算法。6.21 寫出統(tǒng)計樹中葉子結(jié)點個數(shù)的算法，樹用孩子兄弟鏈表表示。6.22 寫出計算樹的深度的算法，樹用孩子兄弟鏈表表示。6.23 寫出計算二叉樹第K層結(jié)點數(shù)的算法。6.24 寫出計算二叉樹深度的算法。7.1有向圖如圖7-1所示,圖7-1第七章圖(1)鄰接矩陣示意圖請給出該圖的(2)鄰接表示意圖(3)逆鄰接表jz*(4)所有強(qiáng)連通分量7.2 圖G的鄰接矩陣如圖7-2所示。寫出該圖從頂點1出發(fā)的深度優(yōu)先搜索序列和廣度優(yōu)先搜索序列，并

17、畫出相應(yīng)的深度優(yōu)先生成樹和廣度優(yōu)先生成樹。12345678910100000010102001000100030001000100400001000105000001000161100000000700100000018100100001090000101001101000010000圖7-27.3 無向帶權(quán)圖如圖7-3所示，(1)畫出它的鄰接矩陣，并按Prim算法求其最小生成樹，(2)畫出它的鄰接表，并按Kruskal算法求其最小生成樹7.4 有向圖如圖7-4所示，試寫出其所有可能的拓?fù)湫蛄衘z*V1圖7-47.5 試?yán)肈ijkstra算法求圖7-5中頂點A到其他各頂點之間的最短路徑。要求

18、寫出執(zhí)行算法過程中，數(shù)組D、P和S各步的狀態(tài)。7.6試在鄰接矩陣存儲構(gòu)造上實現(xiàn)圖的根本操作：InsertVex(G,v),InsertArc(G,v,w),DeleteVex(G,v)和DeleteArc(G,v,w)。7.7 試在鄰接表存儲構(gòu)造上實現(xiàn)圖的根本操作：InsertVex(G,v),InsertArc(G,v,w),DeleteVex(G,v)和DeleteArc(G,v,w)。7.8 設(shè)具有n個頂點的有向圖用鄰接表存儲。試寫出計算所有頂點入度的算法，可將每個頂點的入度值分別存入一維數(shù)組intIndegreen中。7.9 假設(shè)有向圖以鄰接表作為存儲構(gòu)造。試基于圖的深度優(yōu)先搜索策略寫

19、一算法,判斷有向圖中是否存在由頂點Vi至頂點Vj(i!=j)的路徑。7.10 假設(shè)有向圖以鄰接表作為存儲構(gòu)造。試基于圖的廣度優(yōu)先搜索策略寫一算法，判斷有向圖中是否存在由頂點Vi至頂點Vj(i!=j)的路徑。7.11 以鄰接表作為存儲構(gòu)造，實現(xiàn)求單源最短路徑的Dijkstra算法。jz*第九章查找9.1 假設(shè)對大小均為n的有序順序表和無序順序表分別進(jìn)展順序查找，試在以下三種情況下分別討論兩者在等概率時平均查找長度是否一樣？(1)查找不成功，即表中沒有關(guān)鍵字等于給的值K的記錄；(2)查找成功，且表中只有一個關(guān)鍵字等于給定值K的記錄；(3)查找成功，且表中有假設(shè)干個關(guān)鍵字等于給定值K的記錄，要求找出

20、所有這些t己錄。9.2 試分別寫出在對有序線性表(a,b,c,d,e,f,g)中進(jìn)展折半查找，查值等于e、f和g的元素時，先后與哪些元素進(jìn)展了比較。9.3 畫出對長度為13的有序表進(jìn)展折半查找的判定樹，并分別求其等概率時查找成功和查找失敗的ASL。9.4 如下所示長度為12的表：(Jan,Feb,Mar,Apr,May,Jun,July,Aug,Sep,Oct,Nov,Dec)表中，每個元素的查找概率分別為：(0.1,0.25,0.05,0.13,0.01,0.06,0.11,0.07,0.02,0.03,0.1,0.07)(1)假設(shè)對該表進(jìn)展順序查找，求查找成功的平均查找長度；(2)畫出從初態(tài)為空開場，依次插入結(jié)點，生成的二叉排序樹；(3)計算該二叉排序樹查找成功的平均查找長度；(4)將二叉排序樹中的結(jié)點Mar刪除，畫出經(jīng)過刪除處理后的二