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

1、構(gòu)題第思考題型、抽象 據(jù)類型作業(yè)題1.2 設(shè)有數(shù)（D，R構(gòu)題第思考題型、抽象 據(jù)類型作業(yè)題1.2 設(shè)有數(shù)（D，R，=d , 2 d3,d4r1,r1=, r2= (d1, d2), (d1, d3), (d1, d4), (d2, d4) d2, d3) 試其邏構(gòu)示意圖4, 13 n1;whii+ =-1)1;doi+;whi e(n-d+ wh lii=n) 1j=0wh + n) if i=(y+1) * (y+1) x=91; y=100while ( y0 x=n; y=0n1whil e(x=(y+1) * (y+1) x=91; y=100while ( y0 if(x100) x

2、-=10; y-; elx+ for( i=0iifor( j=ijjfor( k=j; kn; x+=2思考題1 2 作業(yè)題3La xLa4La 出算法，將元素 x 插到 La 的合適位置上，保持該表的有（1）La 點結(jié)（2）La 2 . 試寫一個算法，實現(xiàn)順序表的就地逆置，即在原表的空間將線性表2 . 6 試寫一個算法結(jié)點的單鏈表實現(xiàn)就地逆2. 7 已知線性表 L 采用順結(jié)構(gòu)存放。對兩種不同情況分別寫出算法，刪L 中值相同的多余 L 中沒有重復(fù)元素：1L 中數(shù)據(jù)元素無序排列；22 28 27 L 結(jié)構(gòu)改為單鏈表，寫出相應(yīng)的實現(xiàn)算法。2設(shè)28 27 L 結(jié)構(gòu)改為單鏈表，寫出相應(yīng)的實現(xiàn)算法。2

3、設(shè)有兩個非遞減有序的單鏈表A 和 B。請寫出算法，將 A 和 B成一個按元素值非遞增有序的單鏈表 C210 1 為指向表中某個結(jié)點的指針,21ss2-211 212 要求：(1不借助輔助數(shù)組; (2)時間復(fù)雜度為 O(n)2設(shè)結(jié)點的雙向循環(huán)鏈表表示的線性表L=(a1a2a3 ,., a n)。試寫時間復(fù)雜On)的算法，將L 改造L=(a1 a3 ,., a n ,., a 4 a2)思考題3.3.如果進棧序列為A、B、C、D，寫出所有可能的出棧序3.3 34 已知棧S 中存放8 個數(shù)據(jù)34 已知棧S 中存放8 個數(shù)據(jù)自棧底至棧頂依次為(1 2345678)（1）寫出在執(zhí)行了函數(shù)調(diào)用 a l g

4、o1(S)后，S 中的元素（2）在（1）的基礎(chǔ)上，又執(zhí)行了函數(shù)調(diào)用 a l go2(S, 5)，寫出此S 中的元voialgo1(Stack &S)a10,i, n=0while(!StackEmpty(S) n+; Pop(S, an)for(i=1i=n; i+) a i)voialgo2(Stack &S, e) Stack T;d;InitStack(T); wh il e( !EmptyStack(S) Pop( S, d) ;if(d!=e) Push(T,d)whil e( StackEmpty(T) Pop( T, d) ;35 已知隊列 Q 中自隊頭至隊尾依次存放著(1234

5、5678)。寫出在執(zhí)行了函數(shù)調(diào)用 algo3(Q)后，Q 中的元素序列。void al&Q) Stack S;d;Ini tStack(S) while( !QueueEmpty(Q)4 DeQueue(Q,d) Push(S, d) while( !StackEmpty(S)Pop(S, d) EnQueue(Q,DeQueue(Q,d) Push(S, d) while( !StackEmpty(S)Pop(S, d) EnQueue(Q,d) 作業(yè)題 “序1&序列 2”模式的字符序列。其中，序列 和序列 中都不包含2且序是序的逆序。例如，“a+b&b+a”是屬于該模式的字符序列，211”

6、則 3.設(shè)表達式由單字雙目運算符和圓括號（如:“(a* (b+c)-d) / e39 310 311 假設(shè)將循環(huán)隊列定義為：以rear length 分別指示隊尾元素和隊列長度。傳遞回隊頭元素的值3.試寫一個讀入的一個以為結(jié)束符的字符序列是否是“回文5 5已數(shù)組 A2233 按行優(yōu)先方。試位置的先后A i jk l 序列（ijklA0021可表示為“0021” 2 假設(shè)有一個二維數(shù)組5已數(shù)組 A2233 按行優(yōu)先方。試位置的先后A i jk l 序列（ijklA0021可表示為“0021” 2 假設(shè)有一個二維數(shù)組A0 .507每個元素占 6 個字首元A0 0的地址為 1000，求： 最后一個元

7、素A5 7的地按行主序方時，A2 4的地址53 設(shè)有上三角矩陣a1n aaa2n a3n . Cann 將其上三角的元素逐行存于B0 m1中（m 充分大Bk =aij f1if2jc。試推導(dǎo)出函f1、f2和常f1 和 f2 中不含常數(shù)項54 aa aa2m1,2m 按以下方式存于一維數(shù)B 4m0123456k4m-4m-6 a2m-1,a2m,寫出由一對下標ijk5.已知稀疏矩陣A45 如下A 0(1) 用三元組表(2) 寫出由一對下標ijk5.已知稀疏矩陣A45 如下A 0(1) 用三元組表(2) 5設(shè)稀疏矩陣A 和 B 均以三元組順序表作結(jié)構(gòu)。試寫出計算矩陣相加 AB 的算法，其中，C 是

8、另設(shè)的、存放結(jié)果的三元組表（提示：可用類似 6.試分別繪出具有3 個結(jié)點的樹和 3 個結(jié)點的二叉樹的所有不同形6.設(shè)結(jié)點X 是二叉樹上一個度為 1 的結(jié)點，X 有幾？6.6.一個深度為H 的滿 k 叉樹有如下性質(zhì)：第 H 層上所有結(jié)點都是葉子結(jié)點，i 的結(jié)點的父結(jié)點(若存在)i j 個孩子(若存在)i 7 65已知一棵度為kn11的結(jié)點，n22. 65已知一棵度為kn11的結(jié)點，n22. （n 和mXnX樹中，則稱“n 在m“m 在n的右方”。）中，mX6 . 8 已知一棵樹如圖 61 所示，畫出與該樹對應(yīng)的二叉樹，并寫出該樹的先根ABCDEFGHIJK6-69 將如圖628 問 nm之前nm

9、之前nm之前nm nm nm nm AIKLBJMNCDEOFGH6-6.畫出和下列二叉樹（如圖6 - 所示）相應(yīng)的森AAAABBBCBCDEFCCGHIAIKLBJMNCDEOFGH6-6.畫出和下列二叉樹（如圖6 - 所示）相應(yīng)的森AAAABBBCBCDEFCCGHIJKL6-6.已知某二叉樹的中序序列為 DCBGEAHFIJK，后序序列DCEGBFHKJIA6.12 已知樹T 的先根遍序列為GFKDAIEBCHJ，后根遍DIAEKFCJHBG。請畫出樹 T613FABCDEFGHIJKL9 6假設(shè)某個電文由(a b, c, d, e,f, g, h)8 個字母組成，每個字母在電文的次數(shù)分

10、別為(76假設(shè)某個電文由(a b, c, d, e,f, g, h)8 個字母組成，每個字母在電文的次數(shù)分別為(7 19263232110)，試解答下列問huffman 寫出每個huffman 編碼6.6.6.6.6.(注：兩棵二叉樹B1 和B2B1 和B2B1和B26.6.6.71 已知有向圖如圖7-1(1)鄰接矩陣(2) 鄰接(3) 逆鄰接(4)所有強連7-10 7已知圖G 的鄰接矩陣如圖 72 所示 1 1234567891234567890000010101000007已知圖G 的鄰接矩陣如圖 72 所示 1 12345678912345678900000101010000010000

11、0100001000001000010000010000100000100001110000001000100000001001000100000010101077.無向帶權(quán)圖如圖73 所示(1) Pr i 算法求其最小生(2) Kruska 算法求其最小E93B7F4655AD255G3C465H7-7.有向圖7所示，試寫出其所有可能的拓撲序117- 46BE982ACG4F5D37-6 7- 46BE982ACG4F5D37-6 結(jié)構(gòu)上實現(xiàn)圖的基本操作：InsertVex(G,DeleteVex(Gv)DeleteArcGvw)v)， Inser tArc(G, v,w) 7 結(jié)構(gòu)上實現(xiàn)圖

12、的基本操作：InsertVex(G,v)， Inser tArc(Gvw) , DeleteVex(G, v)DeleteArcGvw)78 設(shè)具有n可將每個頂點的入度值分別存入一維Indegree n79 法，判斷有向圖中是否存在由頂點 V 至頂Vji j)的路10 以鄰接表作結(jié)構(gòu)，實現(xiàn)求單源最短路徑的D ij kst ra 算法12 查找不成功，即表中沒有關(guān)鍵字等于給的值查找成功，且表中只有一個關(guān)鍵字等于給定值的；的 查找不成功，即表中沒有關(guān)鍵字等于給的值查找成功，且表中只有一個關(guān)鍵字等于給定值的；的；(3) 查找成功，且表中有若干個關(guān)鍵字等于給定值K 。e2試分別寫出在對有序線性表(ab

13、cde,f, g)f g 3 134 已知如下所示長度為12(Jan, Feb, Mar, Apr, May, Jun, July, Aug, Sep, Oct, Nov, (0.1,0.25,0.05,0.13,0.01,0.06,0.11,0.07,0.02,0.03,0.1,0.(1)若對該表進行順序查找，求查找成功的平均查找長度；(2)畫出從初態(tài)為空開始，依結(jié)點，生成的二叉排序樹；(3)計算該二叉排序樹查找成功的平均查(4)將二叉排序樹中的結(jié)點刪除，畫出經(jīng)過刪除處理后的二叉9 . 5 在地址空間為 016 的散列區(qū)中，對以下關(guān)鍵字序列構(gòu)造兩個哈希表：(Jan, Feb, Mar, Apr, May, Jun, July, Aug, Sep, Oct, Nov, (1) 用線性探測開放定址法(2) 用鏈地址法處設(shè)哈希函數(shù)為H(k)= i / 2,其中 i 為關(guān)鍵字首字母在字母表中的序96 13 9假設(shè)哈希表長為 m， 哈希函數(shù)