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

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