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

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

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ù)結(jié)構(gòu)與算法作業(yè)全文共6頁，當前為第2頁。若設(shè)串類型為：typedefstructstrNode{

charchdata;

strNode*next;

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