1、學而不思則惘，思而不學則殆數據結構作業第1章緒論 問題1.1什么是數據？數據結構的定義是什么？數據：描述客觀事物的數和字符的集合 數據結構：所有數據元素以及數據元素之間的關系，可以看作是互相之間存在著某種特定關系的數據元素的集合，即可把數據結構看成是帶結構的數據元素的集合。問題1.2數據項、邏輯結構、存儲結構的關系是什么？數據項：具有獨立含義的最小數據單位，也稱為字段或域邏輯結構：從邏輯關系上描述數據，與數據的存儲無關，獨立與計算機。可以看作 是從具體問題抽象出來的數學模型。存儲結構：邏輯結構在計算機中的存儲方式，依賴于計算機語言。問題1.3邏輯結構的類型有哪些？1、集合2、線性結構3樹形結構

2、、4、圖形結構問題1.4存儲結構的類型有哪些？1、順序存儲2、鏈式存儲3、索引存儲4、散列存儲問題1.5數據結構和數據類型的區別是什么？數據結構：所有數據元素以及數據元素之間的關系，可以看作是互相之間存在著某種特定關系的數據元素的集合，即可把數據結構看成是帶結構的數據元素的集合。數據類型：一組性質相同的值的集合和定義在此集合上的一組操作的總稱。是某程序設計語言中已實現的數據結構。問題1.6算法的定義及其特性有哪些？定義：在具體存儲結構上實現某個抽象運算。 特性：有窮性、確定性、可行性、有輸入、有輸出。問題1.7如何分析算法的時間復雜度？由其中基本運算的執行次數來計量。記作：T(n)=0(f(n

3、)。只求出T (n)的最高階，忽略低階和常數。這樣既可簡化T(n)的計算，也可以反映時間算法的性能。O(1)<O(log2 n)< 0( n)<0( nl og2 n)<0( n2)<0(門人3)<0(2人 n)<0( n!)找出算法中的基本語句；算法中執行次數最多的那條語句就是基本語句，通常是最內層循環的循環體。計算基本語句的執行次數的數量級；只需計算基本語句執行次數的數量級，這就 意味著只要保證基本語句執行次數的函數中的最高次幕正確即可，可以忽略所有低次幕和最高次幕的系數。這樣能夠簡化算法分析，并且使注意力集中在最重要的一 點上：增長率。用大0記號

4、表示算法的時間性能。將基本語句執行次數的數量級放入大0記號中。問題1.8如何分析算法的空間復雜度？空間復雜度是對一個算法在運行過程中臨時占用存儲空間大小的量度。一個算法在計算機存儲器上所占用的存儲空間， 包括存儲算法本身所占用的存儲空間， 算法的 輸入輸出數據所占用的存儲空間和算法在運行過程中臨時占用的存儲空間這三個方面。記作：S( n)=O(g( n)問題1.9如何理解程序=數據結構+算法？將松散、無組織的數據按某種要求組成一種數據結構，對于設計一個簡明、高效、 可靠的程序是大有益處的。程序就是在數據的某些特定的表示方法和結構的基礎 上，對抽象算法的具體描述。算法是解題的方法， 沒有了算法，

5、程序就成了無源之水， 有了算法，表達程序將不 再那么困難，算法在程序設計、軟件開發甚至整個計算機科學領域都極其重要。所以：程序=數據結構+算法問題1.10數據結構和C語言的區別是什么？C語言是一種編程的語言，編程的語言有很多種。而數據結構則是講的是關于一些 數據的理論知識。可以說不管什么編程語言都能用到數據結構的知識，數據結構是程序設計基礎又核心的知識。第2章線性表 問題2.1線性表的定義是什么?線性表：具有相同特性的數據元素的一個有限序列。問題2.2線性表的抽象數據類型如何描述？數據對象、數據關系、基本運算、Init_List(&L):線性表初始化，構造一個空的線性表L.Destro

6、yList(&L):銷毀線性表，釋放線性表L占用的內存空間。ListEmpty(L):判斷線性表是否為空表，若L為空表，則返回真，否則返回假。ListLe ngth(L):求線性表的長度，返回線性表中的所含元素的個數DispList(L):輸出線性表，當線性表 L不為空時，順序顯示 L中個節點的值域。GetList(L,i,&e):求線性表中某個數據元素值，用e返回L中第i(1<=i<=n)個元素的值。LocateElem(L,e):按元素值查找，返回在L中第一個值域與 e相等的序號值。若這樣的元素在L中不存在，則返回值為0.List In sert( &L

7、, i,& e):插入數據元素，在線性表L中刪除序號第i(1<=i<=n+1)個元 素之前插入新的元素e，L的長度增1.ListDelete(&L,i,&e):刪除數據元素，在線性表L中刪除序號第i(1<=i<=n)個元素，并用e返回其值，L的長度減1.問題2.3線性表的順序存儲結構如何實現？線性表的順序存儲結構是利用數組來實現的，數組的基本類型就是線性表中元素的類型，數組的大小要大于等于線性表的長度。問題2.4實現順序表的基本運算有哪些？Init_List(&L)、DestroyList(&L)、ListEmpty(L)、Lis

8、tLength(L)、DispList(L)、GetList(L,i,&e)、LocateElem(L,e)、ListInsert ( &L,i,&e)、ListDelete(&L,i,&e)、問題2.5線性表的鏈式存儲結構如何實現？利用單鏈表、雙鏈表、循環鏈表實現。問題2.6什么是單鏈表？單鏈表的操作有哪些？單鏈表：在每個節點中，除數據域外，應只設置一個指針域，用以指向其后繼節點。插入和刪除節點操作。其基本運算可實現：Init_List(&L) 、DestroyList(&L)、ListEmpty(L)、ListLength(L)、Di

9、spList(L)、GetList(L,i，&e)、LocateElem(L,e)、ListInsert(&L,i,&e)、ListDelete(&L,i,&e)、問題2.7什么是雙鏈表？其操作有哪些？在每個節點中，除數據域外，設置兩個指針域，分別用以指向其前驅結點和后繼節 點。其基本運算與單鏈表相同，插入與刪除節點操作方法不同。問題2.8什么是循環鏈表？其和單鏈表、雙鏈表的區別是什么？循環鏈表中尾節點的指針域不再為空，而是指向頭節點，整個鏈表形成一個環。問題2.9有序表的概念及其歸并算法如何實現？有序表：其中所有元素以遞增或遞減的方式有序排列的線性表。

10、第3章棧和隊列 問題3.1什么是棧？其抽象數據類型是什么？棧是一種只能在一端進行插入或刪除操作的線性表問題3.2棧的特點是什么？棧的主要特點是“后進先出”，即后進棧的元素先彈出。問題3.3棧的順序存儲結構運算有哪些？如何實現？(1 )初始化棧InitStack(s).建立一個新的空棧 s,實際上將棧頂指針指向-1即可。(2) 銷毀棧DestoryStack(s)。釋放棧s占用的存儲空間。(3) 判斷棧是否為空 StackEmpty(s)。棧s為空的條件是s->top=1 。(4) 進棧Push(s,e)。在棧不滿的條件下，先將棧頂指針增1,然后在棧頂指針指 向位置插入元素e。(5) 出棧

11、Pop(s,e)。在棧不為空的條件下，先將棧頂元素賦給 e,然后將棧頂指針 減1。(6)取棧頂元素GetTop(s,e)。在棧不為空的條件下，將棧頂元素賦給e。問題3.4棧的鏈式存儲結構運算有哪些？如何實現？（1 ）初始化棧InitStack（s）。建立一個空棧 s。實際上是創建鏈棧的頭節點，并 將其next 域置為NULL（2） 銷毀棧DestoryStack（s）。釋放棧s占用的全部存儲空間。（3）判斷棧是否為空 StackEmpty（s）。棧s為空的條件是s->next=NULL,即單鏈 表中沒有數據節點。（4）進棧Push（s,e）。將新數據節點插入到頭節點之后。（5）出棧Pop

12、（s,e）。在棧不為空的條件下，將頭節點的指針域所指數據節點的數 據域賦給e，然后將該數據節點刪除。（6）取棧頂元素 GetTop（s,e）。在棧不為空的條件下，將頭節點的指針域所指數據節點的數據節點的數據域賦給e。問題3.5如何通過棧實現表達式求解？將算術表達式轉換成后綴表達式，后綴表達式求值，設計求解程序。問題3.6采用棧解決迷宮問題的思路是什么？如何利用了棧的特點。從入口出發，順某一方向向前試探，若能走通，則繼續往前走，否則沿原路返回， 換一個方向繼續試探，直至所以困難的通路都是試探完為止。利用了棧后進先出的特點問題3.7什么是隊列？其抽象數據類型是什么？隊列是一種操作受限的線性表，其限

13、制為僅允許在表的一端進行插入，而在表的另一端進行刪除。是先進先出表。問題3.8隊列的順序存儲結構運算如何實現？需要使用一個數組和兩個整數型變量來實現，利用數組順序存儲隊列中的所有元 素，利用兩個整型變量分別存儲隊首元素和隊尾元素的下標位置。問題3.9為什么提出環形隊列，與隊列的區別有哪些？為了能夠充分的使用數組中的存儲結構，把數組的前端和后端連接起來，形成一個環形的順序表，即把存儲隊列有多少的表從邏輯上看出一個環，稱為環形隊列。問題3.10隊列的鏈式存儲結構如何實現？通過由節點構成的單鏈表實現，此時只允許在單鏈表的表首進行刪除操作和在單鏈 表表尾進行插入操作。問題3.11采用隊列解決迷宮問題的

14、思路是什么？與采用棧的思想有什么不同？用隊列解決迷宮路徑問題。使用一個順序隊qu保存走過的方塊，該隊列的結構如下：'這里使用的順序隊列 qu不是環形隊列，因此在出隊時，不會將出隊元素真正從隊 列中刪除，因為要利用它們輸出迷宮路徑。算法：搜索從（xi，yi ）到（xe，ye）路徑的過程是，首先將（xi，yi ）進隊，在隊列 qu不為空時循環；出隊一次（由于不是環形隊列，該出隊元素仍在隊列中），稱該出 隊的方塊為當前方塊，qu.fro nt為該方塊在隊列中的下標位置，如果當前方塊是出口，則按入口到出口的次序輸出該路徑并結束；否則，按順時針方向找出當前方塊的4個方位中可走的相鄰方塊（對應的m

15、g數組值為0），將這些可走的相鄰方塊均插入到隊列qu中，其pre設置為本搜索路徑中上一方快在qu中的下標值，也就是當前方塊的qu.front 值，并將相鄰方塊對應的，mg數組值置為-1，以避免回過來重復搜索。如此隊列為空，表示未找到出口，即不存在路徑。相比于采用棧的思想設計的算法，采用隊列的算法找到的路徑是最優路徑。第7章樹和二叉樹 問題7.1樹的定義是什么？樹是由n（n>=0）個節點組成的有限集合。問題7.2樹的邏輯表示方法有哪些？樹形表示法，文氏圖表示法，凹入表示法，括號表示法。問題7.3樹的度、分支節點、葉子節點、路徑、路徑長度、孩子節點、雙親節點、兄弟節點、樹的高度、有序樹、森林

16、的定義是什么？（1） 樹中某個節點的子樹的個數稱為該節點的度。樹中個節點的度的最大值稱為樹 的度。（2） 度不為零的節點稱為非終端節點，又叫分支節點。度為零的節點稱為終端節點 或葉子節點。（3） 對于任意兩個節點ki和kj,若樹中存在一個節點序列ki,ki1,ki2,.kin,kj,使得序列中除ki外的任一節點都是其在序列中的前一個節點的后繼節點，則稱該 節點序列為由ki到kj的一條路徑，用路徑所通過的節點序列（ki,ki1,ki2,.kj） 表示這條路徑。路徑長度等于路徑所通過的節點數目減1。（4）在一棵樹中，每個節點的后繼節點，被稱為該節點的孩子節點。相應的，該節 點被稱作其他孩子節點的雙

17、親節點。具有同一雙親的孩子節點互為兄弟節點。（5）樹中的最大層次稱為樹的高度。（6） 若樹中各節點的子樹是按照一定的次序從左向右安排的，且相對次序是不能隨 意變換的，則稱為有序樹，否則稱為無序樹。（7）n（n>0）個互不相交的樹的集合稱為森林。問題7.4樹的性質有哪些？（1） 樹中的節點數等于所以節點的度數加1。（2）度為m的樹中第i層上至多有mA（i-1 ）個節點（i>=1）。（3）高度為h的m次樹至多有 mA（h-1）/（m-1） 個節點。（4）具有n個節點的 m次樹的最小高度為log（n（m-1）+1）。問題7.5樹的存儲結構有哪幾類？雙親存儲結構，孩子鏈存儲結構，孩子兄弟鏈

18、存儲結構 問題7.6二叉樹、滿二叉樹的定義是什么？二叉樹是有限的節點的集合，這個集合或者是空，或者是由一個根節點和兩棵互不 相交的稱為左子樹和右子樹的二叉樹組成。在一棵二叉樹中，如果所以分支節點都有左孩子樹節點和右孩子樹節點，并且葉子節點都集中在二叉樹的最下一層，這樣的二叉樹稱為滿二叉樹。問題7.7二叉樹的性質有哪些？（1） 非空二叉樹上葉子節點數等于雙分支節點數加1。（2） 非空二叉樹上第i層上至多有2A（i-1）個節點（i>=1）.（3）高度為h的二叉樹至多有2Ah-1個節點（和=1）。（4） 對完全二叉樹中編號為i的節點（1<=i<=n,n>=1,n為節點數）有若

19、 2i<=n,則編號為i的節點為分支節點，否則為葉子節點。若n為奇數，則每個分支節點都既 有做孩子節點，又有右孩子節點；若n為偶數，則編號最大的分支節點只有左孩子 節點，沒有右孩子節點，其余分支節點都有左，右孩子節點；若編號我Ii的節點有左孩子節點，則左孩子節點的編號為2i ;若編號為i的節點，有右孩子節點，則右孩子節點的編號為 2i+1 ；除根節點外，若一個節點的編號為i，則他的雙親節 點的編號為i/2，也就是說當i為偶數時，其雙親節點的編號為 i/2，它是雙親節 點的左孩子節點，當I為奇數時，其雙親節點的編號為（i-1）/2,它是雙親節點的 右孩子節點。（5）具有n個（n>0）

20、節點的完全二叉樹的高度為Log2（n+1）或（Iog2 （n）+1.問題7.8樹為什么要轉換成二叉樹，他們之間的轉換怎么實現？樹轉化成二叉樹可簡化問題（1） 在所有相鄰兄弟節點（森林中每棵樹的根節點可看成是兄弟節點）之間加一條 水平連線。（2） 對每個非葉子節點 K,除了其最左邊的孩子節點外，刪去k與其他孩子節點的 連線。（3） 所有水平線段以左邊節點為軸心順時針旋轉45度。問題7.9二叉樹的順序存儲結構如何實現？對該樹中每個節點進行編號，其編號從小到大的順序就是節點存放在連續存儲單元 的先后次序。若把二叉樹存儲到一維數組中，則該編號就是下標值加1.問題7.10二叉樹的鏈式存儲結構如何實現，相

21、比順序存儲結構有什么優點和缺點？二叉樹的鏈式存儲結構是指用一個鏈表來存儲一顆二叉樹，二叉樹中每一個節點用鏈表中的一個鏈接的來存儲。問題7.11二叉樹的基本運算有哪些，如何實現？（1） 創建二叉樹 CreateBTNode （ *b，*str）:根據二叉樹表示法字符串str生成 對應的二叉鏈存儲結構，后者的根節點為*b。（2）查找結點FindNode （ *b，x）:在二叉樹b中尋找data域值為x的節點，并 返回指向該節點的指針。（3） 找孩子節點 LchildNode （ P）和RchildNode （ p）：分別求二叉樹中節點 *p 的左孩子節點和右孩子節點。(4) 求高度BTNodeDe

22、pth(*b):求二叉樹b的高度，若二叉樹為空，則其高度為0,其高度等于其左子樹和右子樹的高度中的最大高度加1。(5) 輸出二叉樹 DispBTNode ( *b):以括號表示法輸出一顆二叉樹。問題7.11什么是二叉樹的遍歷？遍歷方法有哪幾種？二叉樹的遍歷是指按照一定次序訪問二叉樹中所有節點，并且每個節點僅訪問一次的過程。遍歷方法有：先序遍歷，中序遍歷，后序遍歷，層次遍歷問題7.12二叉樹遍歷的遞歸算法如何實現？先序遍歷的遞歸算法：訪問根節點，先序遍歷左子樹，先序遍歷右子樹中序遍歷的遞歸算法：中序遍歷左子樹，訪問根節點，中序遍歷右子樹 后序遍歷的遞歸算法：后序遍歷左子樹，后序遍歷右子樹，訪問根

23、節點問題7.13二叉樹遍歷的非遞歸算法如何實現？先序遍歷的非遞歸算法：先將根節點進棧在棧不空時循環：訪問*p節點，若其右孩子節點不空將右孩子節點進棧，若其左孩子節點不空再將其左孩子節點進棧。中序遍歷的遞歸算法：先找到二叉樹的開始節點，訪問它再處理其右子樹。后序遍歷的遞歸算法： 與中序遍歷情況類似，后序遍歷中第一個訪問的節點是二叉樹的最左下節點。問題7.14如何構造二叉樹？任何n (n>=0)個不同節點的二叉樹，都可以由它的中序序列和先序序列唯一確定。任何n (n>=0)個不同節點的二叉樹， 都可以由它的中序序列和后序序列唯一確定。問題7.15什么是線索二叉樹？如何線索化？對于具有n

24、個節點的二叉樹，采用二叉鏈存儲結構時，每個節點有兩個指針域，總共有2n個指針域，又由于只有 n-1個節點被有效指針所指向，則有n+1個空鏈域，遍歷二叉樹的結果是一個節點的線性序列。可以利用這些空鏈域存放指向節點的前驅結點和后繼節點的指針。這樣的指向該線性序列中的前驅結點和后繼節點的指針叫做線索。二叉樹的線索化，實質上就是遍歷一顆二叉樹，在遍歷的過程中，檢查當前節點的左右指針域是否為空，如果為空，將他們改為指向前驅結點和后繼節點的線索。問題7.16什么是哈夫曼樹？如何構造哈夫曼樹？從根節點到某節點之間的路徑長度與該節點上權值的乘積稱為該節點的帶權路徑長度，樹中所有葉子節點的帶權路徑長度之和稱為的

25、帶權路徑長度。在n個帶權葉子節點構成的所有二叉樹中，帶權路徑長度WPL最小的二叉樹稱為哈夫曼樹。問題7.17什么是哈夫曼編碼？如何編碼？在數據通信中，經常需要將傳送的文字轉化為二進制字符0和1組成的字符串，這個過程稱為編碼。設需要編碼的字符集和為(d1,d2,.,dn,各個字符在電文中出現的次數集合為w1,.,wn,以d1,.,dn作為葉子節點，以w1,w2,.,wn作為各個葉子節點的 權值構造一顆哈夫曼樹，規定哈夫曼樹中的左分支為0,右分支為1,則從根節點到每個葉子節點所經過的分支對應的0和1組成的序列便為該節點對應字符的編碼，這樣的編碼成為哈夫曼編碼。第9章查找問題9.1查找的基本概念有哪

26、些？給定一個值k,在含有n個元素的表中找出關鍵字等于k的元素。若找到，則查找成功，返回該元素的信息或該元素在表中的位置，否則查找失敗，返回相關的指示信息。問題9.2線性表的查找方法有哪些？順序查找、折半查找、索引存儲結構和分塊查找問題9.3順序查找、折半查找、分塊查找的思路各是什么？如何分析查找效率？順序查找的基本思路是：從表的一端開始，順序掃描線性表，依次將掃描到的關鍵字 和給定值k相比較，若當前掃描到的關鍵字與 k值相等，則查找成功；若掃描結束，仍 未找到關鍵字等于k值的元素，則查找失敗。折半查找的基本思路是：設Rlow.high是當前的查找區間，首先確定該區間的中間 位置mid=6(lo

27、w+high)/2然后將待查的 k值與Rmid.key比較。分塊查找的思路：先查找索引表，再在已確定的塊中進行順序查找。順序查找的效率v分塊查找的效率v折半查找問題9.4樹表的查找相對線性表查找的優點是什么？可以對動態查找表進行高效率的查找。問題9.5什么是二叉排序樹？二叉排序樹或者是空樹，或者是滿足如下性質二叉樹：若它的左子樹非空，則左子樹上所有元素的值均小于根元素的值；若它的右子樹飛空， 則右子樹上所有元素的值均大于根元素的值；左右子樹本身又各是一棵二叉排序樹問題9.6如何建立二叉排序樹？從一個空樹開始，每插入一個關鍵字，就調用一次插入算法將它插入到當前已生成 的二叉排序樹中。問題9.7如

28、何實現二叉排序樹的查找，其平均查找長度如何分析？逐步縮小查找范圍，使用遞歸查找算法SearchBST()，如果二叉排序樹蛻化為一個深度為n的單支樹，它的平均查找長度和在單鏈表上的順序查找相同，即(n+1)/2。如果蛻化為一個形態與折半查找的判定樹相似的二叉排序樹，則其平均查找長度大約是以2為底n的對數log 2n。問題9.8什么是平衡二叉樹？其具有什么優點？若一棵二叉樹中每個節點的左右子樹的高度至多相差1的是平衡二叉樹。使在樹插入或刪除元素時，保持 BST性質不變又保證樹的高度在任何情況下均為O(log2n)問題9.9平衡二叉樹調整方法有哪些？分別如何調整?LL型調整、RR型調整、LR型調整、

29、RL型調整LL型調整:單向右旋平衡。RR型調整:單向左旋平衡。LR型平衡:先左旋轉后向右旋轉平衡。RL型平衡：先右旋轉后左旋轉平衡。問題9.10什么是哈希表？其查找思想是什么？有什么優點？哈希表又稱散列表，是一種存儲線性表的存儲結構。查找思想：設要存儲的對象個數為n,設置一個長度為 m(m > n)的連續內存單元，以線性表中每個對象的關鍵字ki為自變量，通過一個稱為哈希函數的函數h(ki),把k映射為內存單元的地址 h(ki),并把該對象存儲在這個內存單元中。優點：計算過程簡單，高的時間效率第10章內排序問題10.1什么是排序？怎么理解排序的穩定性排序就是整理表中的元素， 使之按關鍵字遞

30、增或遞減的順序排列；如果待排序的表中，存在多個關鍵字相同的元素，經過排序后這些具有相同關鍵字的元素之間的相對次序保持不變，則稱這種排序方法是穩定的，反之，則稱這種排序方法是不穩定的。問題10.2什么是內排序和外排序？各種排序方法可以按照不同的原則加以分類。在排序的過程中，若整個表都是放 在內存中處理，排序時不涉及內外存數據的交換，則稱為內排序；反之，成為外排序。問題10.3插入排序、交換排序、選擇排序的概念是什么？插入排序：每次將一個待排序的元素，按其關鍵字大小插入到已經排好序的子表中的適當位置，直到全部元素插入完成為止。交換排序：兩兩比較待排序元素的關鍵字，發現兩個元素的次序相反時即進行交

31、換，直到沒有反排序的元素為主。選擇排序：每一趟從待排序的兀素中選出關鍵字最小的兀素，順序放在一排序好 的子表的最后，直到全部元素排序完畢。問題10.4解釋直接插入排序、折半插入排序、希爾排序的思路和效率分析。直接插入排序：假設待排序的元素存放在數組R0.n-1中，排序過程中的某一時刻,R被劃分成個子區間 R0.i-1和Ri.n-1，其中，前一個子區間是已經排序排序好的有序區， 后一個子區間則是當前未排序的部分，稱其為無序區。直接插入排序的一趟操作是將當 前無序區的開頭元素 Ri插入到有序區 R0.i-1中的適當位置上，使R0.i變為新的有序 區。折半插入排序：直接插入排序將無序區中開頭元素Ri

32、插入到有序區 R0.i-1中，此時可以采用折半查找方法先在R0.i-1中找到插入位置再通過移動元素進行插入。希爾排序：希爾排序實際上是一種分組插入方法。其基本思路為：先定義一個小于 n的整數d1作為第一個增量，把表的全部元素分成d1個組，所有相互之間距離為d1的倍數的元素放在一個組中，在各組中進行直接插入排序；然后取第二個增量d2(<d1),重 復上述的分組和排序過程，直至所取的增量dt（dt<dt-1<.<d2<d1）,即素有元素放在同一組 中進行直接插入排序。問題10.5深入分析冒泡排序、快速排序的思想和差異。冒泡排序：通過無序區中相鄰元素間關鍵字的比較和位置的交換，使關鍵字最小 的元素如氣泡一般往上漂浮直至水面。整個算法是從最下面的