1、第一章 作業(yè)1. 解釋下列術語 數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對象、數(shù)據(jù)類型、抽象數(shù)據(jù)類型、原子數(shù)據(jù)類型、結構數(shù)據(jù)類型、邏輯結構、存儲結構、數(shù)據(jù)結構、順序存儲結構、鏈式存儲結構、算法2設有數(shù)據(jù)邏輯結構為Data-structure=(D,R), 其中Dd1,d2,d3,d4,d5,d6, R=r, r=<d1, d2>, <d1, d3>, <d1, d4>, <d3, d5>, <d4, d5>, <d4, d6>, 試畫出其邏輯結構圖。3如圖所示為某種數(shù)據(jù)類型的邏輯結構圖，試用二元組方式表示此數(shù)據(jù)的邏輯結構：ABCGDFE4.

2、數(shù)據(jù)類型和抽象數(shù)據(jù)類型是如何定義的，二者有何相同和不同之處？抽象數(shù)據(jù)類型的主要特點是什么？使用抽象數(shù)據(jù)類型的主要好處是什么？5. 按照階由低到高的順序排列下列時間復雜度：6. 試編寫算法，對連續(xù)輸入的n個整數(shù)，找出其中最大值和最小值（規(guī)定輸入數(shù)在整數(shù)允許范圍內(nèi)）。7有若干學生（設有3個學生）的成績（設每個學生有4門課程），編程找出其中有不及格課程的學生，輸出他們的全部課程的成績。第二章作業(yè)：1. 已知線性表LA的數(shù)據(jù)元素（n個，n為偶數(shù)），現(xiàn)要求將LA拆開成兩個新的線性表LB，LC。要求LB中的數(shù)據(jù)元素為LA中的奇數(shù)位序的數(shù)據(jù)元素（a1, a3, , an-1），LC中的數(shù)據(jù)元素為LA中的偶數(shù)

3、位序的數(shù)據(jù)元素（a2, a4, , an）。2. 已知線性表LA的數(shù)據(jù)元素（n個），現(xiàn)要求將LA的數(shù)據(jù)元素復制到另一個線性表LB中。3. 設有一個線性表采用順序存儲結構，表中的數(shù)據(jù)元素值為正整數(shù)（n個）。設在O(n) 時間內(nèi)，將線性表分成兩為兩部分，其中左半部分每個元素都小于原表的第一個元素，而右半部分則相反。4.設線性表LA（a1, a2, , am），LB（b1, b2, , bn）。試編寫一個算法，將LA、LB合并為線性表LC，使要求LA、LB和LC均以單鏈表為存儲結構，且LC表利用LA和LB中結點空間，這里m和n的值沒有保存在頭結點中，并分析算法時間復雜度。5. 約瑟夫問題：設編號為1

4、，2，n的n（n>0）個人按順時針方向圍坐一圈，每人持有一正整數(shù)密碼。開始時任選一個正整數(shù)作為報數(shù)上限值m，從第一個人開始順時針方向自1起順序報數(shù)，報到m時停止報數(shù)，報m的人出列，將他的密碼作為新的m值，從他在順時針方向上的下一個人起重新從1報數(shù)。如此下去，直到所有人全部出列為止。令n最大值取30。要求設計一個程序模擬此過程，求出出列編號序列（采用循環(huán)單鏈表結構）。6. 試比較順序存儲結構和鏈表存儲結構的優(yōu)缺點第三章作業(yè)：3.1 設將整數(shù)1，2，3，4依次進棧，但只要出棧時棧非空，則可將出棧操作按任何次序夾入其中，請回答下述問題： (1)若入、出棧次序為Push(1), Pop(),Pu

5、sh(2),Push(3), Pop(), Pop( ),Push(4), Pop( ),則出棧的數(shù)字序列為何 (這里Push(i)表示i進棧，Pop( )表示出棧)? (2) 能否得到出棧序列1423和1432? 并說明為什么不能得到或者如何得到。 (3)請分析 1，2 ，3 ，4 的24種排列中，哪些序列是可以通過相應的入出棧操作得到的。3.2 設長度為n的鏈隊用單循環(huán)鏈表表示，若設頭指針，則入隊出隊操作的時間為何? 若只設尾指針呢?3.3 回文是指正讀反讀均相同的字符序列，如"abba"和"abdba"均是回文，但"good"不

6、是回文。試寫一個算法判定給定的字符向量是否為回文。(提示：將一半字符入棧) 3.4 設計算法判斷一個算術表達式的圓括號是否正確配對。 (提示： 對表達式進行掃描，凡遇到'('就進棧，遇')'就退掉棧頂?shù)?#39;('，表達式被掃描完畢，棧應為空。3.5 假設以帶頭結點的循環(huán)鏈表表示隊列，并且只設一個指針指向隊尾元素站點(注意不設頭指針) ，試編寫相應的置空隊、判隊空 、入隊和出隊等算法。3.6 假設循環(huán)隊列中只設rear和quelen 來分別指示隊尾元素的位置和隊中元素的個數(shù)，試給出判別此循環(huán)隊列的隊滿條件，并寫出相應的入隊和出隊算法，要求出隊時需返回隊

7、頭元素。第四章作業(yè)1. 假設以順序存儲結構存放字符串，試編寫算法，實現(xiàn)下列基本操作（用C語言編寫）：（1）CreatString(&S)。輸入并建立順序存儲的字符串S；（2）SubString(&T, S, pos, len)。求S串從pos開始長度為len的子串放入T串；（3）StrInsert(&S, i, T)。在串S的第i個字符前插入T；（4）StrDelele(&T, S, i, len)。從串S中刪除第i個字符起長度為len的子串送到T中。2. 設a=“ ”，b=“old friend”, c=“good”, d=“new”, 試完成下列運算：（1）

8、StrLength(a), StrLength(b); （2）SubString(sub, b, 4, 3);（3）Replace(b, old, d);（4）ConCat(S, c, ConCat(T, a, b).第六章 練習1 已知一棵樹的邏輯結構用以下二元組表示：D_structure=(D,S);D=A,B,C,D,E,F,G,H,I,J,K,L,M,NS=<I,M>,<I,N>,<E,I>,<B,E>,<B,D>,<A,B>,<G,J>,<G,K>,<C,G>,<C,F

9、>,<H,L>,<C,H>,<A,C>畫出樹的邏輯結構圖，并回答以下問題：（1） 哪個是根結點（2） 哪些是葉子結點？（3） 哪個是結點G的雙親？哪個是結點G的祖先？哪些是結點G的孩子？（4） 哪些是結點F的兄弟？（5） 樹的深度是多少？結點N在第幾層？2、設樹T的度為4，其中度為1、2、3、4的結點個數(shù)分別為4、2、1、1，問T有多少葉子結點？3、畫出只含有三個結點的二叉樹的所有不同形態(tài)，并分別寫出其先序邊歷、中序遍歷、后序遍歷的序列。已知二叉樹的先序遍歷序列為DBACFEG，中序遍歷序列為ABCDEFG。畫出二叉樹，并寫出后序遍歷序列。4、已知二叉

10、樹的中序遍歷序列為DCBGEAHFIJK，后序遍歷序列為DCEGBFHKJIA。畫出二叉樹，并寫出先序遍歷序列。5、分別對圖A和圖B進行中序線索化和后序線索化，為每個空指針建立相應的前驅或后繼線索。ACBDEFGACBDEFG（A） (B)6、畫出和下列二叉樹對應的森林7、將下列森林轉換為相應二叉樹8、畫出樹的二叉樹鏈表表示的邏輯結構圖9、設有7個帶權結點A,B,C,D,E,F,G。其權值分別為3、7、8、2、5、8、4。試以這些結點作為葉子結點，構造最優(yōu)二叉樹。要求左子樹根結點的權值小于右子樹根結點。10、設用于通信的電文僅由六個字符A,B,C,D,E,F組合而成，字符在電文中出現(xiàn)的概率分別

11、為0.32, 0.12, 0.16 , 0.03 ,0.21, 0.16，試為這6個字母設計赫夫曼編碼。11、編寫遞歸算法，在鏈式存儲的二叉樹中求位于先序序列中的K個位置的結點的值。12、編寫遞歸算法，計算二叉樹中葉子結點的數(shù)目13、編寫遞歸算法，將二叉樹中所有結點的左右子樹互換。14、編寫遞歸算法，求二叉樹的深度。第七章 圖1 設有一有向圖為G=(V，E)。其中，V=v0, v1, v2, v3，E=<v1, v0>, <v2, v1>, <v3, v2>, <v3, v1>, <v0, v3>。請畫出該有向圖。2對n個頂點的無向圖

12、G，采用鄰接矩陣表示，如何判別下列有關問題(1) 圖中有多少條邊?(2) 任意兩個頂點i和j是否有邊相連?(3) 任意一個頂點的度是多少?3 對于下面的帶權有向圖，寫出其相鄰矩陣表示，并畫出其鄰接表表示。4 對于圖7.27，從頂點v0出發(fā)分別畫出其深度優(yōu)先生成樹和廣度優(yōu)先生成樹。5 對于圖7.28所示的網(wǎng)絡，請分別用Prim算法和Kruskal算法構造該網(wǎng)絡的最小生成樹。第九章 查找1 試編寫利用折半查找確定記錄所在塊的分塊查找算法。并討論在塊中進行順序查找時使用“監(jiān)視哨”的優(yōu)缺點，以及必要時如何在分塊查找的算法中實現(xiàn)設置“監(jiān)視哨”的技巧。2在地址空間為016的散列區(qū)中，對以下關鍵字序列構造兩個哈希表：（Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec）（1）用線性探測開放定址法處理沖突；（2）用鏈地址法處理。設哈希函數(shù)為，其中i為關鍵字中第一個字母在字母表中的序號。3. 哈希函數(shù)H(k)=(3k)MOD11。用開放定址法處理沖突，di=i(7k)MOD10+1) (i=1,2,3,)。試在012的散列地址空間中對關鍵字序列（22，41，53，46，30，13，01，67，18，90）造哈希表。第10章 內(nèi)部排序1給出初始排序碼序