數據結構與算法作業(yè)

1、習 題 11 簡述下列術語：數據 數據元素 數據結構 存儲結構 數據類型 抽象數據類型 2在下面兩列中，左側是算法的執(zhí)行時間，右側是一些時間復雜度。請用連線的方式表示每個算法的時間復雜度。 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í)行次數和整個算法的時間復雜度。注意選擇你認為較好的輸入和輸出方法，本題輸入為ai(i=0,1,n

2、)，x0和n，輸出為pn(x0)。習 題 21 填空題：a) 在順序表中插入和刪除一個元素，需要平均移動 表中一半 元素，具體移動的元素個數與 插入或刪除元素的位置 有關。b) 順序表中邏輯上相鄰的元素的物理位置 要求 緊鄰。單鏈表中邏輯上相鄰的元素的物理位置 不要求 緊鄰。c) 在單鏈表中，除了首結點外，任一結點的存儲位置由 前一結點的指針 指示。d) 在單鏈表中設置頭結點的作用是 儲存指向第一個結點的指針 。2 已知順序線性表a和b中各存放一個英語單詞，字母均為小寫。試編寫一個判定那個單詞在字典中排在前面的算法。3 試寫一算法，實現順序表的就地逆置，即利用原表的存儲空間將線性表（a1，a2

3、，, an）逆置為（an，an-1，a1）。4 已知指針ha和hb分別指向兩個單鏈表的頭結點，并且已知兩個鏈表的長度分別為m和n。試寫一算法將這兩個鏈表連接在一起（即令其中一個表的首元結點連在另一個表的最后一個結點之后），假設指針hc指向連接后的鏈表的頭結點，并要求算法以盡可能短的時間完成連接運算。請分析你的算法的時間復雜度。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，

4、, am) 當nm時.線性表a、b和c均以單鏈表作存儲結構，且c表利用a表和b表中的結點空間構成。注意：單鏈表的長度值m和n均未顯式存儲。注意： 2-5題完成后在上機實習時，通過程序實現檢驗算法的正確性（至少上機檢驗算法2）習題 31. 若按教科書3.1.1節(jié)中圖3.1(b)所示鐵道進行車廂調度（注意：兩側鐵道均為單向行駛道），則請問：(1) 如果進站的車廂序列為123，則可能得到的出站車廂序列是什么？ (2) 如果進站的車廂序列為123456，則能否得到435612和135426的出站序列，并說明為什么（即寫出以s表示進棧和以x表示出棧的棧操作序列）。2. 試寫一個判別表達式中開、閉括號是否

5、合法匹配的算法。3. 按照四則運算加、減、乘、除和冪運算（）優(yōu)先關系的慣例，并仿照3.2節(jié)（p.54）例3-1的格式，畫出下列算術表達式求值時操作數棧和運算符棧的變化過程：a-bcd+ef4. 以t=16，各件物品體積=2，5，8，3，4，6為例，畫出背包問題算法執(zhí)行過程中棧的變化。5. 假設以帶頭結點的循環(huán)鏈表表示隊列，并且只設一個指向尾結點的指針，不設頭指針，寫出相應的入隊出隊操作。習題 44.1 已知下列字符串a=this , f= a sample, c=good, d=ne, b= ,s=concat (a, concat ( substring(f,2,7),concat(b,su

6、bstring(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í)行一下函數會產生怎樣的輸出結果？ void demonstrate( )strassign( s, this is a book);replace( s, substring(s,3,7), ese are);strass

7、ign( 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 用串的定長順序存儲表示編寫算法，實現串的基本操作replace(sstring &news, sstring s, sstring t, sstring v); （提示：可利用書中已實現的基本操作）。4.4 假設以結點大小為1（且附設頭結點）的鏈表結構表示串。若設串類型為：typedef

8、struct strnodechar chdata;strnode *next;strnode,*strptr;試編寫程序實現下列串的基本操作strassign , strlength , strcompare和substring的函數。 習題51、設有三對角矩陣(aij)n*n ,將其三對角線上的元素存于數組b3n中，使得元素buv=aij,試推導出從(i,j)到(u,v)的下標變換公式。2、假設按右下標優(yōu)先存儲整數數組a9*3*5*8時，第一個元素的字節(jié)地址是100，每個整數占4個字節(jié)。問下列元素的存儲地址是什么？ (1)a0000 (2)a1111 (3)a3125 (4)a82473、

9、按教科書5.5節(jié)中圖5.8所示結點結構，畫出下列廣義表的存儲結構圖，并求它的深度。 1) ( ),a,(b,c),( ),d),(e) 2) (a),b),( ),d),(e,f)4、三元組順序表的一種變形是，從三元組順序表中去掉行下標域得到二元組順序表，另設一行起始向量，其每個分量是二元組順序表的一個下標值，指示該行中第一個非零元素在二元組順序表中的起始位置。試編寫一個算法，由矩陣元素的下標值i,j求矩陣元素。試討論這種方法和三元組順序表相比的優(yōu)缺點習題 61. 試分別畫出具有3個結點的樹和3個結點的二叉樹的所有不同形態(tài)。從而對比一棵度為2的樹與一棵二叉樹有何區(qū)別？2. 一棵深度為h的滿k叉

10、樹有如下性質：第h層上的結點都是葉子結點，其余各層上每個結點都有k棵非空子樹。如果按層次順序從1開始對全部結點編號，則(1) 各層的結點數目是 。(2) 編號為p的結點的父結點(若存在)的編號是 。(3) 編號為p的結點的第i個兒子結點(若存在)的編號是 。(4) 編號為p的結點有右兄弟的條件是 。其右兄弟的編號是 。3. 已知一棵度為k的樹中有n1個度為1的結點，n2個度為2的結點，nk個度為k的結點，該樹中有個葉子結點。4. 已知在一棵含有n個結點的樹中，只有度為k的分支結點和度為0的葉子結點。則該樹含有的葉子結點的數目為。5. 一棵含有n個結點的k叉樹，可能達到的最大深度和最小深度各為多

11、少？ 6. 找出所有滿足下列條件的二叉樹：a) 它們在先序遍歷和中序遍歷時，得到的結點訪問序列相同？b) 它們在先序遍歷和中序遍歷時，得到的結點訪問序列相同？abcdefghijkc) 它們在先序遍歷和中序遍歷時，得到的結點訪問序列相同？7. 畫出如圖所示各棵樹對應的二叉樹8. 畫出如圖所示二叉樹對應的森林abcdefghijkm9假設用于通信的電文僅由8個字母組成，字母在電文中出現的頻率分別為0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10，試為這8個字母設計哈夫曼編碼。習題 71263541. 已知圖所示的有向圖，請給出該圖的1) 每個頂點的入度和出度2) 鄰接矩陣3) 鄰接表4) 逆鄰接表5) 強連通分量2請對如圖所示的無向帶權圖1) 寫出它的鄰接矩陣，并按prim algorithm求其最小生成樹2) 寫出它的鄰接矩陣，并按kruskal algorithm求其最小生成樹bacdegfh934535456756254、對下圖所示的aoe-網，計算各活動弧的e(ai)和l(aj)函數值、各事件（頂點）的ve(vi)和vl(vj)函數值；列出各條關鍵路徑 abdfgichkje16343169934121062188652711