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

頁眉內(nèi)容數(shù)據(jù)結構與算法作業(yè)PAGE1頁眉內(nèi)容習題11．簡述下列術語： 數(shù)據(jù)數(shù)據(jù)元素數(shù)據(jù)結構存儲結構數(shù)據(jù)類型抽象數(shù)據(jù)類型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í)行次數(shù)和整個算法的時間復雜度。注意選擇你認為較好的輸入和輸出方法，本題輸入為ai(i=0,1,…,n)，x0和n，輸出為Pn(x0)。習題2填空題：在順序表中插入和刪除一個元素，需要平均移動表中一半元素，具體移動的元素個數(shù)與插入或刪除元素的位置有關。順序表中邏輯上相鄰的元素的物理位置要求緊鄰。單鏈表中邏輯上相鄰的元素的物理位置不要求緊鄰。在單鏈表中，除了首結點外，任一結點的存儲位置由前一結點的指針指示。在單鏈表中設置頭結點的作用是儲存指向第一個結點的指針。數(shù)據(jù)結構與算法作業(yè)全文共6頁，當前為第1頁。數(shù)據(jù)結構與算法作業(yè)全文共6頁，當前為第1頁。試寫一算法，實現(xiàn)順序表的就地逆置，即利用原表的存儲空間將線性表（a1，a2，…,an）逆置為（an，an-1，…，a1）。已知指針ha和hb分別指向兩個單鏈表的頭結點，并且已知兩個鏈表的長度分別為m和n。試寫一算法將這兩個鏈表連接在一起（即令其中一個表的首元結點連在另一個表的最后一個結點之后），假設指針hc指向連接后的鏈表的頭結點，并要求算法以盡可能短的時間完成連接運算。請分析你的算法的時間復雜度。設線性表A=(a1，a2，…,am)，B=(b1，b2，…,bn)，試寫一個按下列規(guī)則合并A、B為線性表C的算法，即使得C=(a1，b1，a2，b2，…,am，bm，bm+1，…,bn)當m≤n時；C=(a1，b1，a2，b2，…,an，bn，an+1，…,am)當n≤m時. 線性表A、B和C均以單鏈表作存儲結構，且C表利用A表和B表中的結點空間構成。注意：單鏈表的長度值m和n均未顯式存儲。注意：2-5題完成后在上機實習時，通過程序?qū)崿F(xiàn)檢驗算法的正確性（至少上機檢驗算法2）習題3若按教科書，則請問：如果進站的車廂序列為123，則可能得到的出站車廂序列是什么？如果進站的車廂序列為123456，則能否得到435612和135426的出站序列，并說明為什么（即寫出以‘S’表示進棧和以‘X’表示出棧的棧操作序列）。試寫一個判別表達式中開、閉括號是否合法匹配的算法。按照四則運算加、減、乘、除和冪運算（↑）優(yōu)先關系的慣例，并仿照3.2節(jié)（p.54）例3-1的格式，畫出下列算術表達式求值時操作數(shù)棧和運算符棧的變化過程：A-B×C／D+E↑F以T=16，各件物品體積={2，5，8，3，4，6}為例，畫出背包問題算法執(zhí)行過程中棧的變化。假設以帶頭結點的循環(huán)鏈表表示隊列，并且只設一個指向尾結點的指針，不設頭指針，寫出相應的入隊出隊操作。習題4數(shù)據(jù)結構與算法作業(yè)全文共6頁，當前為第2頁。4.1已知下列字符串

a=‘THIS’,f=‘ASAMPLE’,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)生怎樣的輸出結果？

voiddemonstrate(){

StrAssign(s,‘THISISABOOK’);

Replace(s,SubString(s,3,7),‘ESEARE’);

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,SStringS,SStringT,SStringV);（提示：可利用書中已實現(xiàn)的基本操作）數(shù)據(jù)結構與算法作業(yè)全文共6頁，當前為第2頁。若設串類型為：typedefstructstrNode{

charchdata;

strNode*next;

}strNode,*strPtr;試編寫程序?qū)崿F(xiàn)下列串的基本操作StrAssign,StrLength,StrCompare和SubString的函數(shù)。習題51、設有三對角矩陣(aij)n*n,將其三對角線上的元素存于數(shù)組B[3][n]中，使得元素B[u][v]=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所示結點結構，畫出下列廣義表的存儲結構圖，并求它的深度。1)((()),a,((b,c),(),d),(((e))))2)((((a),b)),(((),d),(e,f)))4、三元組順序表的一種變形是，從三元組順序表中去掉行下標域得到二元組順序表，另設一行起始向量，其每個分量是二元組順序表的一個下標值，指示該行中第一個非零元素在二元組順序表中的起始位置。試編寫一個算法，由矩陣元素的下標值i,j求矩陣元素。試討論這種方法和三元組順序表相比的優(yōu)缺點習題6數(shù)據(jù)結構與算法作業(yè)全文共6頁，當前為第3頁。數(shù)據(jù)結構與算法作業(yè)全文共6頁，當前為第3頁。一棵深度為H的滿k叉樹有如下性質(zhì)：第H層上的結點都是葉子結點，其余各層上每個結點都有k棵非空子樹。如果按層次順序從1開始對全部結點編號，則(1)各層的結點數(shù)目是。(2)編號為p的結點的父結點(若存在)的編號是。(3)編號為p的結點的第I個兒子結點(若存在)的編號是。(4)編號為p的結點有右兄弟的條件是。其右兄弟的編號是。已知一棵度為k的樹中有n1個度為1的結點，n2個度為2的結點，…nk個度為k的結點，該樹中有個葉子結點。已知在一棵含有n個結點的樹中，只有度為k的分支結點和度為0的葉子結點。則該樹含有的葉子結點的數(shù)目為。一棵含有n個結點的k叉樹，可能達到的最大深度和最小深度各為多少？找出所有滿足下列條件的二叉樹：它們在先序遍歷和中序遍歷時，得到的結點訪問序列相同？它們在先序遍歷和中序遍歷時，得到的結點訪問序列相同？ABABCDEFGHIJK畫出如圖所示各棵樹對應的二叉樹畫出如圖所示二叉樹對應的森林AABCDEFGHIJKM9．假設用于通信的電文僅由8個字母組成，字母在電文中出現(xiàn)的頻率分別為0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10，試為這8個字母設計哈夫曼編碼。數(shù)據(jù)結構與算法作業(yè)全文共6頁，當前為第4頁。習題7數(shù)據(jù)結構與算法作業(yè)全文共6頁，當前為第4頁。12126354每個頂點的入度和出度鄰接矩陣鄰接表逆鄰接表強連通分量2．請對如圖所示的無向帶權圖寫出它的鄰接矩陣，并按PrimAlgorithm求其最小生成樹寫出它的鄰接矩陣，并按KruskalAlgorithm求其最小生成樹bbacdegfh934535456756254、對下圖所示的AOE-網(wǎng)，計算各活動弧的e(ai)和l(aj)函數(shù)值、各事件（頂點）的ve(vi)和vl(vj)函數(shù)值；列出各條關鍵路徑116343169934121062188652711104習題10數(shù)據(jù)結構與算法作業(yè)全文共6頁，當前為第5頁。試以單鏈表為存儲結構實現(xiàn)簡單選擇排序的算法數(shù)據(jù)結構與算法