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

1、數(shù)據(jù)結(jié)構(gòu)習題集第一章 序論思考題：1.1 簡述下列術語：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對象、數(shù)據(jù)結(jié)構(gòu)、存儲結(jié)構(gòu)、數(shù)據(jù)類型、抽象數(shù)據(jù)類型作業(yè)題：1.2 設有數(shù)據(jù)結(jié)構(gòu)（D，R），其中D=d1, d2, d3, d4 R=r1, r2r1= <d1, d2>, <d2, d3>, <d3, d4>, <d1, d4>, <d4, d2>, <d4, d1> r2= (d1, d2), (d1, d3), (d1, d4), (d2, d4), (d2, d3) 試繪出其邏輯結(jié)構(gòu)示意圖。1.3 設n是正整數(shù)。試寫出下列程序段中用記號“”標注

2、的語句的頻度：(1)i=1; k=0;while(i<=n-1) k+=10*i;i+;(2)i=1; k=0;do k+=10*i;i+;while(i<=n-1)(3) i=1; k=0; do k+ = 10*i; i+;while(i=n);(4)i=1; j=0;while(i+jn) if(i<j) i+; else j+;(5)x=n; y=0; /n是不小于1的常數(shù)while(x>=(y+1)*(y+1)y+;(6)x=91; y=100;while ( y>0 )if(x>100) x-=10; y-; else x+ ; (7)for(

3、i=0; i<n; i+)for( j=i; j<n; j+)for( k=j; k<n; k+)x+=2;第二章 線性表思考題：2.1 描述以下三個概念的區(qū)別：頭指針、頭結(jié)點、首元結(jié)點。2.2 描述以下幾個概念：順序存儲結(jié)構(gòu)、鏈式存儲結(jié)構(gòu)、順序表、有序表。作業(yè)題：2.3已知順序表La中數(shù)據(jù)元素按非遞減有序排列。試寫一個算法，將元素x插到La的合適位置上，保持該表的有序性。2.4已知單鏈表La中數(shù)據(jù)元素按非遞減有序排列。按兩種不同情況，分別寫出算法，將元素x插到La的合適位置上，保持該表的有序性：（1）La帶頭結(jié)點；（2）La不帶頭結(jié)點。2.5試寫一個算法，實現(xiàn)順序表的就地逆

4、置，即在原表的存儲空間將線性表（a1,a2, ., an-1,an）逆置為(an,an-1, ., a2,a1)2.6試寫一個算法，對帶頭結(jié)點的單鏈表實現(xiàn)就地逆置。2.7已知線性表L采用順序存儲結(jié)構(gòu)存放。對兩種不同情況分別寫出算法，刪除L中值相同的多余元素，使得L中沒有重復元素：(1)L中數(shù)據(jù)元素無序排列；(2)L中數(shù)據(jù)元素非遞減有序排列。2.8將2.7題中L的存儲結(jié)構(gòu)改為單鏈表，寫出相應的實現(xiàn)算法。2.9 設有兩個非遞減有序的單鏈表A和B。請寫出算法，將A和B“就地”歸并成一個按元素值非遞增有序的單鏈表C。2.10 設有一個長度大于1的單向循環(huán)鏈表，表中既無頭結(jié)點，也無頭指針，s為指向表中某

5、個結(jié)點的指針,如圖2-1所示。試編寫一個算法，刪除鏈表中指針s所指結(jié)點的直接前驅(qū)。s待刪結(jié)點圖2-12.11 已知線性表用帶頭結(jié)點的單鏈表表示，表中結(jié)點由三類字符組成：字母、數(shù)字和其他字符。試編寫算法，將該線性鏈表分割成三個循環(huán)單鏈表，每個循環(huán)單鏈表中均只含有一類字符。2.12 已知線性表用順序存儲結(jié)構(gòu)表示，表中數(shù)據(jù)元素為n個正整數(shù)。試寫一算法，分離該表中的奇數(shù)和偶數(shù)，使得所有奇數(shù)集中放在左側(cè)，偶數(shù)集中放在右側(cè)。要求：(1)不借助輔助數(shù)組;(2)時間復雜度為O(n)。2.13 設以帶頭結(jié)點的雙向循環(huán)鏈表表示的線性表L=(a1,a2,a3,.,an)。試寫一時間復雜度為O(n)的算法，將L改造為

6、L=(a1,a3,.,an,.,a4,a2)。第三章 棧和隊列思考題：3.1 簡述棧和線性表的差別。3.2 如果進棧序列為A、B、C、D，寫出所有可能的出棧序列。3.3 簡述棧和隊列的相同點和差異。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中的元素序列。void algo1(Stack &S) int a10, i, n=0; while(!StackEmpty(S) n+; Pop(S, an); fo

7、r(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,d); 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中的元素序列。void algo3(Queue &Q) Stack S; int d; InitSt

8、ack(S); while(!QueueEmpty(Q) DeQueue(Q,d); Push(S,d); while(!StackEmpty(S) Pop(S,d); EnQueue(Q,d); 作業(yè)題：3.6 試寫一個算法，識別依次讀入的一個以為結(jié)束符的字符序列是否為形如“序列1&序列2”模式的字符序列。其中，序列1和序列2中都不包含字符&,且序列2是序列1的逆序。例如，“a+b&b+a”是屬于該模式的字符序列，而“13&31”則不是。3.7 假設一個算術表達式中可以包含三種符號：圓括號“(”和“)”、方括號“”和“”、花括號“”和“”，且這三種括號可按任意

9、次序嵌套使用。編寫判別給定表達式中所含的括號是否正確配對的算法（已知表達式已存入數(shù)據(jù)元素為字符的順序表中）。3.8 設表達式由單字母變量、雙目運算符和圓括號組成（如:“(a*(b+c)-d)/e”）。試寫一個算法，將一個書寫正確的表達式轉(zhuǎn)換為逆波蘭式。3.9 試寫一個算法，對逆波蘭式求值。3.10 假設以帶頭結(jié)點的單循環(huán)鏈表表示隊列，只設一個尾指針指向隊尾元素，不設頭指針。試編寫相應的隊列初始化、入隊和出隊的算法。3.11 假設將循環(huán)隊列定義為：以rear和length分別指示隊尾元素和隊列長度。試給出此循環(huán)隊列的隊滿條件，并寫出相應的入隊和出隊算法（在出隊算法中要傳遞回隊頭元素的值）。3.1

10、2 試寫一個算法：判別讀入的一個以為結(jié)束符的字符序列是否是“回文”（所謂“回文”是指正讀和反讀都相同的字符序列，如“xxyzyxx”是回文，而“abcab”則不是回文）。第五章 多維數(shù)組5.1 已知多維數(shù)組A2233按行優(yōu)先方式存儲。試按存儲位置的先后次序，列出所有數(shù)組元素Aijkl序列（為了簡化表達，可以只列出形如“i,j,k,l”的序列，如元素A0021可表示為“0,0,2,1” ）。5.2 假設有一個二維數(shù)組A0.50.7，每個元素占6個字節(jié)，首元素A00的地址為1000，求： (1)A的體積； (2)最后一個元素A57的地址； (3)按行主序方式存儲時，A24的地址； (4)按列主序方

11、式存儲時，A24的地址；5.3 設有上三角矩陣An×n， 將其上三角的元素逐行存于數(shù)組B0.m-1中（m充分大），使得Bk=aij且kf1(i)+f2(j)+c。試推導出函數(shù)f1、f2和常數(shù)c（要求f1和f2中不含常數(shù)項）。5.4 設有一個準對角矩陣按以下方式存于一維數(shù)組B4m中：0123456k4m-24m-1a11a12a21a22a33a34a43.aij.a2m-1,2ma2m,2m寫出由一對下標(i,j)求k的轉(zhuǎn)換公式。5.5 已知稀疏矩陣A4×5如下：(1)用三元組表作為存儲結(jié)構(gòu)，繪出相應的三元組表示意圖；(2)用十字鏈表作為存儲結(jié)構(gòu)，繪出相應的十字鏈表示意圖。

12、5.6 設稀疏矩陣A和B均以三元組順序表作為存儲結(jié)構(gòu)。試寫出計算矩陣相加CAB的算法，其中，C是另設的、存放結(jié)果的三元組表（提示：可用類似于兩個有序順序表歸并的處理方法）。5.7 試編寫一個算法，實現(xiàn)以三元組的形式打印用十字鏈表表示的稀疏矩陣中所有非零元素及其下標。5.8 試編寫一個算法，實現(xiàn)以矩形陣列的形式打印用十字鏈表表示的稀疏矩陣。第六章 樹和二叉樹6.1 試分別繪出具有3個結(jié)點的樹和3個結(jié)點的二叉樹的所有不同形態(tài)。6.2 設結(jié)點X是二叉樹上一個度為1的結(jié)點，X有幾個子樹？6.3 描述滿足下列條件的二叉樹形態(tài)： (1) 先序遍歷序列與中序遍歷序列相同； (2) 后序遍歷序列與中序遍歷序列

13、相同； (3) 先序遍歷序列與后序遍歷序列相同；6.4 一個深度為H的滿k叉樹有如下性質(zhì)：第H層上所有結(jié)點都是葉子結(jié)點，其余各層上每個結(jié)點都有k棵非空子樹。如果從1開始按自上而下、自左向右的次序?qū)θ拷Y(jié)點編號，問：(1) 各層的結(jié)點數(shù)目是多少？(2) 編號為i的結(jié)點的父結(jié)點(若存在)的編號是多少？(3) 編號為i的結(jié)點的第j個孩子(若存在)的編號是多少？(4) 編號為i的結(jié)點有右兄弟的條件是什么？其右兄弟的編號是多少？6.5 已知一棵度為k的樹中有n1個度為1的結(jié)點，n2個度為2的結(jié)點，.，nk個度為k的結(jié)點，問該樹中有多少個葉子結(jié)點？6.6 已知在一棵含有n個結(jié)點的樹中，只有度為k的分支結(jié)點

14、和度為0的葉子結(jié)點。試求該樹含有的葉子結(jié)點的數(shù)目。6.7 設n和m為二叉樹中兩個結(jié)點，用“1”、“0”、和“Æ”（分別表示肯定，否定和不一定）填寫下表：已知 問先序遍歷時n在m之前？中序遍歷時n在m之前？后序遍歷時n在m之前？n在m左方111n在m右方000n是m祖先1Æ0n是m子孫0Æ1（注：如果離n和m的最近的共同祖先X存在，且n位于X的左子樹中，m位于X的右子樹中，則稱“n在m的左方”或“m在n的右方”。）6.8已知一棵樹如圖6-1所示，畫出與該樹對應的二叉樹，并寫出該樹的先根遍歷序列和后根遍歷序列。ABCDEFGHKIJ圖6-16.9 將如圖6-2所示的森

15、林轉(zhuǎn)化為對應的二叉樹。K圖6-2ACDEBFGHJILMNO6.10 畫出和下列二叉樹（如圖6-3所示）相應的森林。圖6-3ABCCABCABADEBCFGHJKLI6.11已知某二叉樹的中序序列為DCBGEAHFIJK，后序序列為DCEGBFHKJIA。請畫出該二叉樹。6.12 已知樹T的先根遍歷訪問序列為GFKDAIEBCHJ，后根遍歷訪問序列為DIAEKFCJHBG。請畫出樹T。6.13 已知森林F的先根遍歷訪問序列為ABCDEFGHIJKL，中根遍歷訪問序列為CBEFDGAJIKLH。請畫出這個森林F。6.14 假設某個電文由(a,b,c,d,e,f,g,h)8個字母組成，每個字母在電

16、文中出現(xiàn)的次數(shù)分別為(7,19,2,6,32,3,21,10)，試解答下列問題： (1) 畫出出huffman樹； (2) 寫出每個字母的huffman編碼； (3) 在對該電文進行最優(yōu)二進制編碼處理后，電文的二進制位數(shù)。6.15 寫出復制一棵二叉樹的算法。6.16 試編寫算法，實現(xiàn)將二叉樹所有結(jié)點的左右子樹互換。6.17 寫出按層次遍歷二叉樹的算法。6.18 寫出判斷給定二叉樹是否為完全二叉樹的算法。6.19 寫出判斷兩棵給定二叉樹是否相似的算法。(注：兩棵二叉樹B1和B2相似是指：B1和B2皆空，或者皆不空且B1的左、右子樹和B2的左、右子樹分別相似。)6.20 利用棧的基本操作，寫出二叉

17、樹先序遍歷的非遞歸算法。6.21 寫出統(tǒng)計樹中葉子結(jié)點個數(shù)的算法，樹用孩子兄弟鏈表表示。6.22 寫出計算樹的深度的算法，樹用孩子兄弟鏈表表示。圖7-1V5V4V2V3V1V6第七章 圖7.1 已知有向圖如圖7-1所示，請給出該圖的 (1)鄰接矩陣示意圖 (2)鄰接表示意圖 (3)逆鄰接表 (4)所有強連通分量7.2 已知圖G的鄰接矩陣如圖7-2所示。寫出該圖從頂點1出發(fā)的深度優(yōu)先搜索序列和廣度優(yōu)先搜索序列，并畫出相應的深度優(yōu)先生成樹和廣度優(yōu)先生成樹。123456789101000000101020010001000300010001004000010001050000010001611000

18、00000700100000018100100001090000101001101000010000圖7-27.3 無向帶權圖如圖7-3所示， (1)畫出它的鄰接矩陣，并按Prim算法求其最小生成樹。 (2)畫出它的鄰接表，并按Kruskal算法求其最小生成樹圖7-3ABCEHFDG435555974566237.4 有向圖如圖7-4所示，試寫出其所有可能的拓撲序列。圖7-4V1V5V2V3V6V47.5 試利用Dijkstra算法求圖7-5中頂點A到其他各頂點之間的最短路徑。要求寫出執(zhí)行算法過程中，數(shù)組D、P和S各步的狀態(tài)。GABDCEF圖7-5151225684910437.6 試在鄰接矩

19、陣存儲結(jié)構(gòu)上實現(xiàn)圖的基本操作：InsertVex(G,v)，InsertArc(G,v,w), DeleteVex(G,v)和DeleteArc(G,v,w)。7.7 試在鄰接表存儲結(jié)構(gòu)上實現(xiàn)圖的基本操作：InsertVex(G,v)，InsertArc(G,v,w), DeleteVex(G,v)和DeleteArc(G,v,w)。7.8 設具有n個頂點的有向圖用鄰接表存儲。試寫出計算所有頂點入度的算法，可將每個頂點的入度值分別存入一維數(shù)組int Indegreen中。7.9 假設有向圖以鄰接表作為存儲結(jié)構(gòu)。試基于圖的深度優(yōu)先搜索策略寫一算法，判斷有向圖中是否存在由頂點Vi至頂點Vj(i!=

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

21、,d,e,f,g)中進行折半查找，查值等于e、f和g的元素時，先后與哪些元素進行了比較。9.3 畫出對長度為17的有序表進行折半查找的判定樹，并分別求其等概率時查找成功和查找失敗的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)若對該表進行順序查找，求查找成功的平均查找長度； (2)畫出從初態(tài)為空開始，依次插入結(jié)點，生成的二叉排序樹； (3)計算該二叉排序樹查找成功的平均查找長度； (4)將二叉排序樹中的結(jié)點M