數(shù)據(jù)結(jié)構(gòu)與算法 作業(yè).doc

習 題 11 簡述下列術(shù)語：數(shù)據(jù) 數(shù)據(jù)元素 數(shù)據(jù)結(jié)構(gòu) 存儲結(jié)構(gòu) 數(shù)據(jù)類型 抽象數(shù)據(jù)類型 2在下面兩列中，左側(cè)是算法的執(zhí)行時間，右側(cè)是一些時間復雜度。請用連線的方式表示每個算法的時間復雜度。 100n3(1)(a)O(1)6n2-12n+1(2)(b)O(2n)1024(3)(c)O(n)n+2log2n(4)(d)O(n2)n(n+1)(n+2)/6(5)(e)O(log2n)2n+1+100n(6)(f)O(n3)3. 試編寫算法，求一元多項式Pn(x)=的值Pn(x0)，并確定算法中每一語句的執(zhí)行次數(shù)和整個算法的時間復雜度。注意選擇你認為較好的輸入和輸出方法，本題輸入為ai(i=0,1,n)，x0和n，輸出為Pn(x0)。習 題 21 填空題：a) 在順序表中插入和刪除一個元素，需要平均移動 表中一半 元素，具體移動的元素個數(shù)與 插入或刪除元素的位置 有關。b) 順序表中邏輯上相鄰的元素的物理位置 要求 緊鄰。單鏈表中邏輯上相鄰的元素的物理位置 不要求 緊鄰。c) 在單鏈表中，除了首結(jié)點外，任一結(jié)點的存儲位置由 前一結(jié)點的指針 指示。d) 在單鏈表中設置頭結(jié)點的作用是 儲存指向第一個結(jié)點的指針 。2 已知順序線性表A和B中各存放一個英語單詞，字母均為小寫。試編寫一個判定那個單詞在字典中排在前面的算法。3 試寫一算法，實現(xiàn)順序表的就地逆置，即利用原表的存儲空間將線性表（a1，a2，, an）逆置為（an，an-1，a1）。4 已知指針ha和hb分別指向兩個單鏈表的頭結(jié)點，并且已知兩個鏈表的長度分別為m和n。試寫一算法將這兩個鏈表連接在一起（即令其中一個表的首元結(jié)點連在另一個表的最后一個結(jié)點之后），假設指針hc指向連接后的鏈表的頭結(jié)點，并要求算法以盡可能短的時間完成連接運算。請分析你的算法的時間復雜度。5 設線性表A=( a1，a2，, am)，B=( b1，b2，, bn)，試寫一個按下列規(guī)則合并A、B為線性表C的算法，即使得C=( a1，b1，a2， b2，, am，bm，bm+1，, bn) 當 mn時；C=( a1，b1，a2， b2，, an，bn，an+1，, am) 當nm時.線性表A、B和C均以單鏈表作存儲結(jié)構(gòu)，且C表利用A表和B表中的結(jié)點空間構(gòu)成。注意：單鏈表的長度值m和n均未顯式存儲。注意： 2-5題完成后在上機實習時，通過程序?qū)崿F(xiàn)檢驗算法的正確性（至少上機檢驗算法2）習題 31. 若按教科書3.1.1節(jié)中圖3.1(b)所示鐵道進行車廂調(diào)度（注意：兩側(cè)鐵道均為單向行駛道），則請問：(1) 如果進站的車廂序列為123，則可能得到的出站車廂序列是什么？ (2) 如果進站的車廂序列為123456，則能否得到435612和135426的出站序列，并說明為什么（即寫出以S表示進棧和以X表示出棧的棧操作序列）。2. 試寫一個判別表達式中開、閉括號是否合法匹配的算法。3. 按照四則運算加、減、乘、除和冪運算（）優(yōu)先關系的慣例，并仿照3.2節(jié)（p.54）例3-1的格式，畫出下列算術(shù)表達式求值時操作數(shù)棧和運算符棧的變化過程：A-BCD+EF4. 以T=16，各件物品體積=2，5，8，3，4，6為例，畫出背包問題算法執(zhí)行過程中棧的變化。5. 假設以帶頭結(jié)點的循環(huán)鏈表表示隊列，并且只設一個指向尾結(jié)點的指針，不設頭指針，寫出相應的入隊出隊操作。習題 44.1 已知下列字符串a(chǎn)=THIS , f= A SAMPLE, c=GOOD, d=NE, b= ,s=Concat (a, Concat ( SubString(f,2,7),Concat(b,SubString(a,3,2),t=Replac (f, SubString(f,3,6),c),u=Concat (SubString(c,3,1),d), g=IS,v=concat (s, Concat(b,Concat(t, Concat(b,u),試問：s, t, v, StrLength(s), index(v,g), index(u,g)各是什么？ 4.2 試問執(zhí)行一下函數(shù)會產(chǎn)生怎樣的輸出結(jié)果？ void demonstrate( )StrAssign( s, THIS IS A BOOK);Replace( s, SubString(s,3,7), ESE ARE);StrAssign( t, Concat(s, S);StrAssign(u, XYXYXYXYXYXY);StrAssign( v,SubString(u, 6, 3);StrAssign(w, W);printf( t=, t , v=, v, u=, Replace(u,v,w);/demonstrate 4.3 用串的定長順序存儲表示編寫算法，實現(xiàn)串的基本操作Replace(SString &NewS, SString S, SString T, SString V); （提示：可利用書中已實現(xiàn)的基本操作）。4.4 假設以結(jié)點大小為1（且附設頭結(jié)點）的鏈表結(jié)構(gòu)表示串。若設串類型為：typedef struct strNodechar chdata;strNode *next;strNode,*strPtr;試編寫程序?qū)崿F(xiàn)下列串的基本操作StrAssign , StrLength , StrCompare和SubString的函數(shù)。 習題51、設有三對角矩陣(aij)n*n ,將其三對角線上的元素存于數(shù)組B3n中，使得元素Buv=aij,試推導出從(i,j)到(u,v)的下標變換公式。2、假設按右下標優(yōu)先存儲整數(shù)數(shù)組A9*3*5*8時，第一個元素的字節(jié)地址是100，每個整數(shù)占4個字節(jié)。問下列元素的存儲地址是什么？ (1)a0000 (2)a1111 (3)a3125 (4)a82473、按教科書5.5節(jié)中圖5.8所示結(jié)點結(jié)構(gòu)，畫出下列廣義表的存儲結(jié)構(gòu)圖，并求它的深度。 1) ( ),a,(b,c),( ),d),(e) 2) (a),b),( ),d),(e,f)4、三元組順序表的一種變形是，從三元組順序表中去掉行下標域得到二元組順序表，另設一行起始向量，其每個分量是二元組順序表的一個下標值，指示該行中第一個非零元素在二元組順序表中的起始位置。試編寫一個算法，由矩陣元素的下標值i,j求矩陣元素。試討論這種方法和三元組順序表相比的優(yōu)缺點習題 61. 試分別畫出具有3個結(jié)點的樹和3個結(jié)點的二叉樹的所有不同形態(tài)。從而對比一棵度為2的樹與一棵二叉樹有何區(qū)別？2. 一棵深度為H的滿k叉樹有如下性質(zhì)：第H層上的結(jié)點都是葉子結(jié)點，其余各層上每個結(jié)點都有k棵非空子樹。如果按層次順序從1開始對全部結(jié)點編號，則(1) 各層的結(jié)點數(shù)目是 。(2) 編號為p的結(jié)點的父結(jié)點(若存在)的編號是 。(3) 編號為p的結(jié)點的第I個兒子結(jié)點(若存在)的編號是 。(4) 編號為p的結(jié)點有右兄弟的條件是 。其右兄弟的編號是 。3. 已知一棵度為k的樹中有n1個度為1的結(jié)點，n2個度為2的結(jié)點，nk個度為k的結(jié)點，該樹中有個葉子結(jié)點。4. 已知在一棵含有n個結(jié)點的樹中，只有度為k的分支結(jié)點和度為0的葉子結(jié)點。則該樹含有的葉子結(jié)點的數(shù)目為。5. 一棵含有n個結(jié)點的k叉樹，可能達到的最大深度和最小深度各為多少？ 6. 找出所有滿足下列條件的二叉樹：a) 它們在先序遍歷和中序遍歷時，得到的結(jié)點訪問序列相同？b) 它們在先序遍歷和中序遍歷時，得到的結(jié)點訪問序列相同？ABCDEFGHIJKc) 它們在先序遍歷和中序遍歷時，得到的結(jié)點訪問序列相同？7. 畫出如圖所示各棵樹對應的二叉樹8. 畫出如圖所示二叉樹對應的森林ABCDEFGHIJKM9假設用于通信的電文僅由8個字母組成，字母在電文中出現(xiàn)的頻率分別為0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10，試為這8個字母設計哈夫曼編碼。習題 71263541. 已知圖所示的有向圖，請給出該圖的1) 每個頂點的入度和出度2) 鄰接矩陣3) 鄰接表4) 逆鄰接表5) 強連通分量2請對如圖所示的無向帶權(quán)圖1) 寫出它的鄰接矩陣，并按Prim Algorithm求其最小生成樹2) 寫出它的鄰接矩陣，并按Kruskal Algorithm求其最小生成樹bacdegfh934535456756254、對下圖所示的AOE-網(wǎng)，計算各活動弧的e(ai)和l(aj)函數(shù)值、各事件（頂點）的ve(vi)和vl(vj)函數(shù)值；列出各條關鍵路徑 ABDFGICHKJE16343169934121062188652711