數(shù)據(jù)結(jié)構(gòu)習(xí)題doc

1、習(xí)題一：1、 什么是算法，算法設(shè)計(jì)的要求有哪些？怎樣進(jìn)行算法評(píng)價(jià)？2、 簡(jiǎn)述下列術(shù)語(yǔ)：數(shù)據(jù)、結(jié)點(diǎn)、邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、數(shù)據(jù)結(jié)構(gòu)。 3、 試確定下列程序段中的時(shí)間復(fù)雜度1) For (i=1;i<=n; +i)for (j=1; j<=i; +j)for (k=1; k<=j; +k) x:=x+1;2) x:=n;y:=0;while (x>=(n+1)*(n+1) y:=y+1;習(xí)題二：1、 什么是順序存儲(chǔ)結(jié)構(gòu)？什么是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)？2、 順序表、單鏈表存儲(chǔ)結(jié)構(gòu)各有什么特點(diǎn)？3、 分別畫出下列數(shù)據(jù)結(jié)構(gòu)的圖示（鏈表為帶頭節(jié)點(diǎn)的空表與非空表）：順序表 單鏈表 雙向循環(huán)鏈表。

2、4、 編寫算法將一無(wú)序鏈表轉(zhuǎn)換成按升序排列的有序鏈表。并分析算法的時(shí)間復(fù)雜度。A=(11,16,8,5,14,10,38,23)5、 已知線性表中的元素以值遞增有序排列，試寫一算法，刪除表中所有值相同的多余的元素。并分析算法的時(shí)間復(fù)雜度。習(xí)題三：1、 何為棧和隊(duì)列？簡(jiǎn)述兩者的區(qū)別和聯(lián)系。2、 若依次讀入數(shù)據(jù)元素序列a,b,c,d進(jìn)棧，進(jìn)棧過程中允許出棧,試寫出各種可能的出棧元素序列（含中間步驟）。3、 將下列各算術(shù)運(yùn)算式表示成波蘭式和逆波蘭式：(A*(B+C)+D)*E-F*GA*(B-D)+H/(D+E)-S/N*T(A-C)*(B+D)+(E-F)/(G+H)4、 對(duì)于一個(gè)具有m個(gè)單元的循

3、環(huán)隊(duì)列，寫出求隊(duì)列中元素個(gè)數(shù)的公式。習(xí)題五：1、 分別寫出在按行優(yōu)先存儲(chǔ)方式和列優(yōu)先存儲(chǔ)方式下，三維數(shù)組A324的地址計(jì)算公式（假設(shè)每個(gè)數(shù)組元素占用L個(gè)字節(jié)的內(nèi)存單元，a000的內(nèi)存地址為L(zhǎng)oc(a000)）。2、 求下列廣義表的運(yùn)算的結(jié)果：A= (a,b), (c,d) B= (p,h,w) C=(b,k,p,h) (1)head(B)(2)tail(C)(3)head(A)(4)tail(A)(5)head(tail(A)(6)tail(head(A)(7)head(tail(head(A) ) )(8)tail(head(tail(A)習(xí)題六：1、 有樹如圖(a)所示，指出樹的根結(jié)點(diǎn)、葉

4、子結(jié)點(diǎn)、樹的度、樹的路徑長(zhǎng)度。2、 將如圖(a)所示的樹轉(zhuǎn)換成對(duì)應(yīng)的二叉樹。3、 有二叉樹如圖(b)所示。寫出其前序、中序和后序遍歷的結(jié)點(diǎn)序列。 4、 設(shè)二叉樹的前序序列為ABCDEFGHR，中序序列為BDCEAFHGR，請(qǐng)畫出這棵二叉樹。5、 設(shè)字符A、B、C、D、E、F、G、H、I出現(xiàn)頻率分別為1，4，9，16，25，36，49，46，81，試設(shè)計(jì)哈夫曼編碼，并求出哈夫曼樹的帶權(quán)路徑長(zhǎng)度。習(xí)題七：1、 對(duì)于圖1的帶權(quán)圖，寫出其鄰接矩陣，并畫出其鄰接表、逆鄰接表的表示。2、 對(duì)于圖2，從頂點(diǎn)V1出發(fā)分別畫出按深度方向和按寬度方向的生成樹。3、 按Prim算法和Kruskal算法求圖3的最小生

5、成樹，畫出分步結(jié)果。4、 求圖4有向圖中從頂點(diǎn)V1到其它各頂點(diǎn)的最短路徑，要求寫出此圖的鄰接矩陣adj和數(shù)組dis在算法執(zhí)行過程中的變化及每一條最短路徑 。5、 請(qǐng)寫出圖5的鄰接表與按算法7.12生成的拓?fù)渑判蛐蛄?。?xí)題九、1、 什么是靜態(tài)查找表？什么是動(dòng)態(tài)查找表？2、 試比較順序查找、折半查找查找、分塊查找的各自特點(diǎn)。3、 什么是二叉排序樹？設(shè)從空樹出發(fā)，查找的關(guān)鍵字序列為（503，87，512，61，908，170，897，275，653，426），畫出各次查找后的二叉排序樹。4、 什么是哈希表？哈希查找的特點(diǎn)是什么？ 習(xí)題十：1、 以關(guān)鍵碼序列（503，87，512，61，908，170，897，275，653，426）為例，給出以下算法的每趟