河南理工大學(xué)數(shù)據(jù)結(jié)構(gòu)習(xí)題答案

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

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

3、(n)。只求出 T( n)的最高階，忽略低階和常數(shù)。這樣既可簡化T(n)的計算，也可以反映時間算法的性能。0(1 )O(log2n)O(n)O(nlog2n)O(nA2)O(nA3)O(2An)O(n!)找出算法中的基本語句； 算法中執(zhí)行次數(shù)最多的那條語句就是基本語句，通常是最內(nèi)層循環(huán)的循環(huán)體。(2) 計算基本語句的執(zhí)行次數(shù)的數(shù)量級；只需計算基本語句執(zhí)行次數(shù)的數(shù)量級，這就意味著只要保 證基本語句執(zhí)行次數(shù)的函數(shù)中的最高次幕正確即可，可以忽略所有低次幕和最高次幕的系數(shù)。 這樣能夠簡化算法分析，并且使注意力集中在最重要的一點(diǎn)上：增長率。用大O記號表示算法的時間性能。將基本語句執(zhí)行次數(shù)的數(shù)量級放入大O

4、記號中O問題1.8如何分析算法的空間復(fù)雜度？空間復(fù)雜度是對一個算法在運(yùn)行過程中臨時占用存儲空間大小的量 度。一個算法在計算機(jī)存儲器上所占用的存儲空間，包括存儲算法本身所占用的存儲空間，算 法的輸入輸出數(shù)據(jù)所占用的存儲空間和算法在運(yùn)行過程中臨時占用的存儲空間這三個方面。記 作：S(n)=O(g(n)問題1.9如何理解程序=數(shù)據(jù)結(jié)構(gòu)+算法？將松散、無組織的數(shù)據(jù)按某種要求組成一種數(shù)據(jù)結(jié)構(gòu)，對于設(shè)計 一個簡明、高效、可靠的程序是大有益處的。程序就是在數(shù)據(jù)的某些特定的表示方法和結(jié)構(gòu)的基 礎(chǔ)上，對抽象算法的具體描述。算法是解題的方法，沒有了算法，程序就成了無源之水，有了算法，表達(dá)程序?qū)⒉辉倌敲蠢?難，算法

5、在程序設(shè)計、軟件開發(fā)甚至整個計算機(jī)科學(xué)領(lǐng)域都極其重要。所以：程序二數(shù)據(jù)結(jié)構(gòu)+ 算法問題1.10數(shù)據(jù)結(jié)構(gòu)和C語言的區(qū)別是什么？C語言是一種編程的語言，編程的語言有很多種。而數(shù)據(jù)結(jié)構(gòu)則是講的是尖于一些數(shù)據(jù)的理論 知識?？梢哉f不管什么編程語言都能用到數(shù)據(jù)結(jié)構(gòu)的知識，數(shù)據(jù)結(jié)構(gòu)是程序設(shè)計基礎(chǔ)又核心的 知識。第2章線性表問題2.1線性表的定義是什么？線性表：具有相同特性的數(shù)據(jù)元素的一個有限序列。問題2.2線性表的抽象數(shù)據(jù)類型如何描述？數(shù)據(jù)對象、數(shù)據(jù)尖系、基本運(yùn)算、lnit_List(&L):線性表初始 化，構(gòu)造一個空的線性表L. DestroyList(&L):銷毀線性表，釋放線性表L占用的內(nèi)存空間。Li

6、stEmpty(L):判斷線性表是否為空表，若L為空表，則返回真，否則返回假。ListLength(L):求 線性表的長度，返回線性表中的所含元素的個數(shù)DispList(L):輸出線性表，當(dāng)線性表L不為空時，順序顯示L中個節(jié)點(diǎn)的值域。GetList(L,i,&e): 求線性表中某個數(shù)據(jù)元素值，用e返回L中第i(1=i=n)個元素的值。LocateElem(L,e):按元素值查找，返回在L中第一個值域與e相等的序號值。若這樣的元素在 L中不存在，則返回值為0.Listlnsert( &L,i,&e)：插入數(shù)據(jù)元素，在線性表L中刪除序號第i(1=i=n+1)個元素之前插 入新的元素e，L的長度增1

7、 ListDelete(&L,i,&e):刪除數(shù)據(jù)元素，在線性表L中刪除序號第i(1=itop=1。(4) 進(jìn)棧Push(s,e)。在棧不滿的條件下，先將棧頂指針增1，然后在棧頂指針指向位置插入 元素e (5) 出棧Pop(s,e)。在棧不為空的條件下，先將棧頂元素賦給e,然后將棧頂指針減1。(6) 取棧頂元素GetTop(s,e)。在棧不為空的條件下，將棧頂元素賦給e。問題3.4棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)運(yùn)算有哪些？如何實現(xiàn)？(1) 初始化棧InitStack (s)。建立一個空棧s。實際上是創(chuàng)建鏈棧的頭節(jié)點(diǎn)，并將其next 域置為NULL。(2) 銷毀棧DestoryStack (s)。釋放棧s占用

8、的全部存儲空間。(3) 判斷棧是否為空StackEmpty (s)。棧s為空的條件是s-next=NULL,即單鏈表中沒 有數(shù)據(jù)節(jié)點(diǎn)。(4) 進(jìn)棧Push (s,e)。將新數(shù)據(jù)節(jié)點(diǎn)插入到頭節(jié)點(diǎn)之后。(5)出棧Pop (s,e)。在棧不 為空的條件下，將頭節(jié)點(diǎn)的指針域所指數(shù)據(jù)節(jié)點(diǎn)的數(shù)據(jù)域賦給e，然后將該數(shù)據(jù)節(jié)點(diǎn)刪除。(6) 取棧頂元素GetTop (s,e)。在棧不為空的條件下，將頭節(jié)點(diǎn)的指針域所指數(shù)據(jù)節(jié)點(diǎn)的數(shù) 據(jù)節(jié)點(diǎn)的數(shù)據(jù)域賦給e。問題3.5如何通過棧實現(xiàn)表達(dá)式求解？將算術(shù)表達(dá)式轉(zhuǎn)換成后綴表達(dá)式，后綴表達(dá)式求值，設(shè)計求解程序。問題3.6采用棧解決迷宮問題的思路是什么？如何利用了棧的特點(diǎn)。從入口

9、出發(fā)，順某一方向向前試探，若 能走通，則繼續(xù)往前走，否則沿原路返回，換一個方向繼續(xù)試探，直至所以困難的通路都是試探 完為止。利用了棧后進(jìn)先出的特點(diǎn)問題3.7什么是隊列？其抽象數(shù)據(jù)類型是什么？隊列是一種操作受限的線性表，其限制為僅允許在表的一端 進(jìn)行插入，而在表的另一端進(jìn)行刪除。是先進(jìn)先出表。問題3.8隊列的順序存儲結(jié)構(gòu)運(yùn)算如何實現(xiàn)？需要使用一個數(shù)組和兩個整數(shù)型變量來實現(xiàn)，利用數(shù)組順序存 儲隊列中的所有元素，利用兩個整型變量分別存儲隊首元素和隊尾元素的下標(biāo)位置。問題3.9為什么提出環(huán)形隊列，與隊列的區(qū)別有哪些？為了能夠充分的使用數(shù)組中的存儲結(jié)構(gòu)，把數(shù)組的前 端和后端連接起來，形成一個環(huán)形的順序表

10、，即把存儲隊列有多少的表從邏輯上看出一個環(huán)，稱 為環(huán)形隊列。問題3.10隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)如何實現(xiàn)？通過由節(jié)點(diǎn)構(gòu)成的單鏈表實現(xiàn)，此時只允許在單鏈表的表首進(jìn)行 刪除操作和在單鏈表表尾進(jìn)行插入操作。問題3.11采用隊列解決迷宮問題的思路是什么？與采用棧的思想有什么不同？用隊列解決迷宮路徑問題。使 用一個順序隊qu保存走過的方塊，該隊列的結(jié)構(gòu)如下：這里使用的順序隊列qu不是環(huán)形隊列，因此在出隊時，不會將出隊元素真正從隊列中刪除， 因為要利用它們輸岀迷宮路徑。算法：搜索從(xi，yi )到(xe，ye)路徑的過程是，首先將(xi，yi )進(jìn)隊，在隊列qu不為空 時循環(huán)；出隊一次(由于不是環(huán)形隊列，該岀

11、隊元素仍在隊列中)，稱該出隊的方塊為當(dāng)前方塊，qu.front 為該方塊在隊列中的下標(biāo)位置，如果當(dāng)前方塊是出口，則按入口到出口的次序輸出該路徑并結(jié)束；否則， 按順時針方向找出當(dāng)前方塊的4個方位中可走的相鄰方塊(對應(yīng)的mg數(shù)組值為0)，將這些可走的相 鄰方塊均插入到隊列qu中，其pre設(shè)置為本搜索路徑中上一方快在qu中的下標(biāo)值，也就是當(dāng)前方塊 的qu.front值，并將相鄰方塊對應(yīng)的，mg數(shù)組值置為-1 ，以避免回過來重復(fù)搜索。如此隊列為空， 表示未找到出口，即不存在路徑。相比于采用棧的思想設(shè)計的算法，采用隊列的算法找到的路徑是最優(yōu)路徑。第7章樹和二叉樹問題7.1樹的定義是什么？樹是由n (n=

12、0)個節(jié)點(diǎn)組成的有限集合。問題7.2樹的邏輯表示方法有哪些？樹形表示法，文氏圖表示法，凹入表示法，括號表示法。問題7.3樹的度、分支節(jié)點(diǎn)、葉子節(jié)點(diǎn)、路徑、路徑長度、孩子節(jié)點(diǎn)、雙親節(jié)點(diǎn)、兄弟節(jié)點(diǎn)、樹的高度、有序樹、森林的定義是什么？(1) 樹中某個節(jié)點(diǎn)的子樹的個數(shù)稱為該節(jié)點(diǎn)的度。樹中個節(jié)點(diǎn)的度的最大值稱為樹 的度。(2) 度不為零的節(jié)點(diǎn)稱為非終端節(jié)點(diǎn)，又叫分支節(jié)點(diǎn)。度為零的節(jié)點(diǎn)稱為終端節(jié)點(diǎn)或葉子節(jié) 占O八、(3) 對于任意兩個節(jié)點(diǎn)ki和kj,若樹中存在一個節(jié)點(diǎn)序列ki,ki1,ki2,kin,kj,使得序列中除ki外的任一節(jié)點(diǎn)都是其在序列中的前一個節(jié)點(diǎn)的后繼節(jié)點(diǎn)，則稱該節(jié)點(diǎn)序列為由ki 至| k

13、j的一條路徑，用路徑所通過的節(jié)點(diǎn)序列(ki,ki1 ,ki2,kj)表示這條路徑。路徑長度等于路徑所通過的節(jié)點(diǎn)數(shù)目減1。(4) 在一棵樹中，每個節(jié)點(diǎn)的后繼節(jié)點(diǎn)，被稱為該節(jié)點(diǎn)的孩子節(jié)點(diǎn)。相應(yīng)的，該節(jié)點(diǎn)被稱作其他 孩子節(jié)點(diǎn)的雙親節(jié)點(diǎn)。具有同一雙親的孩子節(jié)點(diǎn)互為兄弟節(jié)點(diǎn)。(5) 樹中的最大層次稱為樹的高度。(6) 若樹中各節(jié)點(diǎn)的子樹是按照一定的次序從左向右安排的，且相對次序是不能隨 意變換的，則稱為有序樹J否則稱為無序樹。(7) n (n0)個互不相交的樹的集合稱為森林。問題7.4樹的性質(zhì)有哪些？(1) 樹中的節(jié)點(diǎn)數(shù)等于所以節(jié)點(diǎn)的度數(shù)加1。(2) 度為m的樹中第i層上至多有計(i-1 )個節(jié)點(diǎn)(i=

14、1)。(3) 高度為h的m次樹至多有m八(h-1) / (m-1)個節(jié)點(diǎn)。(4) 具有n個節(jié)點(diǎn)的m次樹的最小高度為log (n (m1) +1)。問題7.5樹的存儲結(jié)構(gòu)有哪幾類？雙親存儲結(jié)構(gòu)，孩子鏈存儲結(jié)構(gòu)，孩子兄弟鏈存儲結(jié)構(gòu)問題7.6二叉樹、滿二叉樹的定義是什么？ 二叉樹是有限的節(jié)點(diǎn)的集合這個集合或者是空或者是由一個根節(jié)點(diǎn)和兩棵互不相交的稱為左子 樹和右子樹的二叉樹組成。在一棵二叉樹中，如果所以分支節(jié)點(diǎn)都有左孩子樹節(jié)點(diǎn)和右孩子樹節(jié) 點(diǎn)，并且葉子節(jié)點(diǎn)都集中在二叉樹的最下一層，這樣的二叉樹稱為滿二叉樹。問題7.7二叉樹的性質(zhì)有哪些？(1 )非空二叉樹上葉子節(jié)點(diǎn)數(shù)等于雙分支節(jié)點(diǎn)數(shù)加1。(2) 非空

15、二叉樹上第i層上至多有(i-1)個節(jié)點(diǎn)(i=1).(3) 高度為h的二叉樹至多有2Ah-1個節(jié)點(diǎn)(和=1) o(4) 對完全二叉樹中編號為i的節(jié)點(diǎn)(1v=iv=n,n=1,n為節(jié)點(diǎn)數(shù))有若2i0)節(jié)點(diǎn)的完全二叉樹的高度為Log2 (n+1)或(Iog2 ( n) ) +1.問題7.8樹為什么要轉(zhuǎn)換成二叉樹，他們之間的轉(zhuǎn)換怎么實現(xiàn)？樹轉(zhuǎn)化成二叉樹可簡化問題(1) 在所有相鄰兄弟節(jié)點(diǎn)(森林中每棵樹的根節(jié)點(diǎn)可看成是兄弟節(jié)點(diǎn))之間加一條水平連線。(2) 對每個非葉子節(jié)點(diǎn)K，除了其最左邊的孩子節(jié)點(diǎn)外，刪去k與其他孩子節(jié)點(diǎn)的 連線。(3) 所有水平線段以左邊節(jié)點(diǎn)為軸心順時針旋轉(zhuǎn)45度。問題7.9二叉樹的順

16、序存儲結(jié)構(gòu)如何實現(xiàn)？對該樹中每個節(jié)點(diǎn)進(jìn)行編號，其編號從小到大的順序就是節(jié)點(diǎn)存 放在連續(xù)存儲單元的先后次序。若把二叉樹存儲到一維數(shù)組中，則該編號就是下標(biāo)值加1.問題7.10二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)如何實現(xiàn)，相比順序存儲結(jié)構(gòu)有什么優(yōu)點(diǎn)和缺點(diǎn)？二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)是指用一個鏈表來存儲一顆二叉樹,二叉樹中每一個節(jié)點(diǎn)用鏈表中的一個鏈接的來存儲。問題7.11二叉樹的基本運(yùn)算有哪些，如何實現(xiàn)？(1) 創(chuàng)建二叉樹CreateBTNode ( *b，*str ):根據(jù)二叉樹表示法字符串str生成 對應(yīng)的二叉鏈存儲結(jié)構(gòu)，后者的根節(jié)點(diǎn)為*b。(2) 查找結(jié)點(diǎn)FindNode ( *b，x )：在二叉樹b中尋找data域

17、值為x的節(jié)點(diǎn)，并返回 指向該節(jié)點(diǎn)的指針。(3) 找孩子節(jié)點(diǎn)LchildNode (P)和RchildNode (p):分別求二叉樹中節(jié)點(diǎn)8的左孩子 節(jié)點(diǎn)和右孩子節(jié)點(diǎn)。(4) 求高度BTNodeDepth (*b):求二叉樹b的高度，若二叉樹為空，則其高度為0，其高度等于其左子樹和右子樹的高度中的最大高度加1。(5) 輸出二叉樹DispBTNode ( *b )：以括號表示法輸出一顆二叉樹。問題7.11什么是二叉樹的遍歷？遍歷方法有哪幾種？二叉樹的遍歷是指按照一定次序訪問二叉樹中所有節(jié) 點(diǎn)，并且每個節(jié)點(diǎn)僅訪問一次的過程。遍歷方法有：先序遍歷，中序遍歷，后序遍歷，層次遍歷問題7.12二叉樹遍歷的遞

18、歸算法如何實現(xiàn)？先序遍歷的遞歸算法：訪問根節(jié)點(diǎn)，先序遍歷左子樹，先序遍 歷右子樹中序遍歷的遞歸算法：中序遍歷左子樹，訪問根節(jié)點(diǎn)，中序遍歷右子樹后序遍歷的遞 歸算法：后序遍歷左子樹，后序遍歷右子樹，訪問根節(jié)點(diǎn)問題7.13二叉樹遍歷的非遞歸算法如何實現(xiàn)？先序遍歷的非遞歸算法：先將根節(jié)點(diǎn)進(jìn)棧在棧不空時循環(huán)：訪問*P節(jié)點(diǎn)，若其右孩子節(jié)點(diǎn)不 空將右孩子節(jié)點(diǎn)進(jìn)棧，若其左孩子節(jié)點(diǎn)不空再將其左孩子節(jié)點(diǎn)進(jìn)棧。中序遍歷的遞歸算法：先找 到二叉樹的開始節(jié)點(diǎn)，訪問它再處理其右子樹。后序遍歷的遞歸算法：與中序遍歷情況類似， 后序遍歷中第一個訪問的節(jié)點(diǎn)是二叉樹的最左下節(jié)點(diǎn)。問題7.14如何構(gòu)造二叉樹？任何n (n=0 )

19、個不同節(jié)點(diǎn)的二叉樹，都可以由它的中序序列和先序序列唯一確定。任何n ( n=0 )個不同節(jié)點(diǎn)的二叉樹，都可以由它的中序序列和后序序列唯一確定。問題7.15什么是線索二叉樹？如何線索化？對于具有n個節(jié)點(diǎn)的二叉樹，采用二叉鏈存儲結(jié)構(gòu)時，每個節(jié)點(diǎn)有兩個指針域，總共有個 指針域，又由于只有個節(jié)點(diǎn)被有效指針?biāo)赶?，則有n+1個空鏈域，遍歷二叉樹的結(jié)果是一個節(jié) 點(diǎn)的線性序列?？梢岳眠@些空鏈域存放指向節(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)和后繼節(jié)點(diǎn)的指針。這樣的指向該線性 序列中的前驅(qū)結(jié)點(diǎn)和后繼節(jié)點(diǎn)的指針叫做線索。二叉樹的線索化，實質(zhì)上就是遍歷一顆二叉樹，在遍歷的過程中，檢查當(dāng)前節(jié)點(diǎn)的左右指針域 是否為空，如果為空，將他們改為指

20、向前驅(qū)結(jié)點(diǎn)和后繼節(jié)點(diǎn)的線索。問題7.16什么是哈夫曼樹？如何構(gòu)造哈夫曼樹？從根節(jié)點(diǎn)到某節(jié)點(diǎn)之間的路徑長度與該節(jié)點(diǎn)上權(quán)值的乘積 稱為該節(jié)點(diǎn)的帶權(quán)路徑長度，樹中所有葉子節(jié)點(diǎn)的帶權(quán)路徑長度之和稱為的帶權(quán)路徑長度。在n個帶權(quán)葉子 節(jié)點(diǎn)構(gòu)成的所有二叉樹中，帶權(quán)路徑長度WPL最小的二叉樹稱為哈夫曼樹。問題7.17什么是哈夫曼編碼？如何編碼？在數(shù)據(jù)通信中，經(jīng)常需要將傳送的文字轉(zhuǎn)化為二進(jìn)制字符0和1 組成的字符串，這個過程稱為編碼。設(shè)需要編碼的字符集和為(d1 ,d2,.,dn,各個字符在電文中出現(xiàn)的次數(shù)集合為w1,.,wn,以d1,.,dn作為葉子節(jié)點(diǎn)，以w1,w2,.,wn作為各個葉子節(jié)點(diǎn)的權(quán)值構(gòu) 造一顆

21、哈夫曼樹，規(guī)定哈夫曼樹中的左分支為0，右分支為1，則從根節(jié)點(diǎn)到每個葉子節(jié)點(diǎn)所經(jīng)過的 分支對應(yīng)的0和1組成的序列便為該節(jié)點(diǎn)對應(yīng)字符的編碼，這樣的編碼成為哈夫曼編碼。第9章查找問題9.1查找的基本概念有哪些？給定一個值k,在含有n個元素的表中找出尖鍵字等于k的元素。若找到，則查找成功，返回該 元素的信息或該元素在表中的位置，否則查找失敗，返回相尖的指示信息。問題9.2線性表的查找方法有哪些？順序查找、折半查找、索引存儲結(jié)構(gòu)和分塊查找問題9.3順序查找、折半查找、分塊查找的思路各是什么？如何分析查找效率？順序查找的基本思路是：從 表的一端開始，順序掃描線性表，依次將掃描到的尖鍵字和給定值k相比較，若

22、當(dāng)前掃描到的尖鍵字與k 值相等，則查找成功；若掃描結(jié)束，仍未找到尖鍵字等于k值的元素，則查找失敗。折半查找的基本思路是：設(shè)Rlow.high是當(dāng)前的查找區(qū)間，首先確定該區(qū)間的中間位置 mid=6(low+high)/2然后將待查的 k 值與 Rmid.key 比較。分塊查找的思路：先查找索引表，再在已確定的塊中進(jìn)行順序查找。順序查找的效率分塊查找 的效率折半查找問題9.4樹表的查找相對線性表查找的優(yōu)點(diǎn)是什么？可以對動態(tài)查找表進(jìn)行高效率的查找。問題9.5什么是二叉排序樹？二叉排序樹或者是空樹，或者是滿足如下性質(zhì)二叉樹：(1若它的左子樹非空，則左子樹上所有元素的值均小于根元素的值；(2)若它的右子

23、樹飛空，則右子樹上所有元素的值均大于根元 素的值；(3)左右子樹本身又各是一棵二叉排序樹問題9.6如何建立二叉排序樹？從一個空樹開始，每插入一個尖鍵字，就調(diào)用一次插入算法將它插入到當(dāng)前已生成的二叉排序 樹中。問題9.7如何實現(xiàn)二叉排序樹的查找，其平均查找長度如何分析？逐步縮小查找范圍，使用遞歸查找算法SearchBST()，如果二叉排序樹蛻化為一個深度為n的單支樹，它的平均查找長度和在單鏈表上的順序查找相同，即(n+1)/2。如果蛻化為一個形態(tài)與折半查找的判定樹相似的二叉排序樹，則其平均查找長度大約是以2為底n的對數(shù) log 2n。問題9.8什么是平衡二叉樹？其具有什么優(yōu)點(diǎn)？若一棵二叉樹中每個

24、節(jié)點(diǎn)的左右子樹的高度至多相差1的是 平衡二叉樹。使在樹插入或刪除元素時保持BST性質(zhì)不變又保證樹的高度在任何情況下均為O(log2n)問題9.9平衡二叉樹調(diào)整方法有哪些？分別如何調(diào)整?LL型調(diào)整、RR型調(diào)整、LR型調(diào)整、RL型調(diào)整LL型調(diào)整：單向右旋平衡。RR型調(diào)整：單向左旋平衡。LR型平衡：先左旋轉(zhuǎn)后向右旋轉(zhuǎn)平衡。RL型平衡：先右旋轉(zhuǎn)后左旋轉(zhuǎn)平衡。問題9.10什么是哈希表？其查找思想是什么？有什么優(yōu)點(diǎn)？哈希表又稱散列表，是一種存儲線性表的存儲 結(jié)構(gòu)。查找思想：設(shè)要存儲的對象個數(shù)為n,設(shè)置一個長度為m(m n)的連續(xù)內(nèi)存單元，以線性表中每個對 象的尖鍵字ki為自變量，通過一個稱為哈希函數(shù)的函數(shù)

25、h(ki),把k映射為內(nèi)存單元的地址h(ki),并把該對象存儲在這個內(nèi)存單元中。優(yōu)點(diǎn)：計算過程簡單，高的時間效率第10章內(nèi)排序問題10.1什么是排序？怎么理解排序的穩(wěn)定性排序就是整理表中的元素，使之按尖鍵字遞增或遞減的順序排列；如果待排序的表中，存在多 個尖鍵字相同的元素，經(jīng)過排序后這些具有相同尖鍵字的元素之間的相對次序保持不變，則稱這種排序 方法是穩(wěn)定的，反之，則稱這種排序方法是不穩(wěn)定的。問題10.2什么是內(nèi)排序和外排序？各種排序方法可以按照不同的原則加以分類。在排序的過程中，若整個 表都是放在內(nèi)存中處理，排序時不涉及內(nèi)外存數(shù)據(jù)的交換，則稱為內(nèi)排序；反之，成為外排序。問題10.3插入排序、交

26、換排序、選擇排序的概念是什么？插入排序：每次將一個待排序的元素，按其尖鍵字大小插入到已經(jīng)排好序的子表中的適當(dāng)位置， 直到全部元素插入完成為止。交換排序：兩兩比較待排序元素的尖鍵字，發(fā)現(xiàn)兩個元素的次序相反時即進(jìn)行交換，直到?jīng)]有反 排序的元素為主。選擇排序：每一趟從待排序的元素中選出尖鍵字最小的元素，順序放在一排序好的子表的最后， 直到全部元素掃乍序完畢。問題10.4解釋直接插入排序、折半插入排序、希爾排序的思路和效率分析。直接插入排序：假設(shè)待排序的元素存放在數(shù)組R0.n-1中，排序過程中的某一時刻，R被劃分成個 子區(qū)間R01和Ri.n-1，其中，前一個子區(qū)間是已經(jīng)排序排序好的有序區(qū)，后一個子區(qū)間

27、則是當(dāng) 前未排序的部分，稱其為無序區(qū)。直接插入排序的一趟操作是將當(dāng)前無序區(qū)的開頭元素Ri插入到有序 區(qū)R0.i-1沖的適當(dāng)位置上，使R0.i變?yōu)樾碌挠行騾^(qū)。折半插入排序：直接插入排序?qū)o序區(qū)中開頭元素Ri插入到有序區(qū)R0.i-1中，此時可以采用折半查找方法先在R0.i-1中找到插入位置再通過移動元素進(jìn)行插入。希爾排序：希爾排序 實際上是一種分組插入方法。其基本思路為：先定義一個小于n的整數(shù)d1作為第一個增量，把表的全部 元素分成d1個組，所有相互之間距離為d1的倍數(shù)的元素放在一個組中，在各組中進(jìn)行直接插入排序；然后取第二個增量d2(d1),重復(fù)上述的分組和排序過程，直至所取的增量dt (dtdt-1.d2d1)，即素有元素放在同一組中進(jìn)行 直接插入排序。問題10.5深入分析冒泡排序、快速排序的思想和差異。冒泡排序：通過無序區(qū)中相鄰元素間尖鍵字的比較 和位置的交換，使尖鍵字最小的元素如氣泡一般往上漂浮直至水面。整個算法是從最下面的元素開始，對每 兩個相鄰的尖鍵字進(jìn)行比較對每兩個相鄰的尖鍵字進(jìn)行比較，且使尖鍵字較小的元素?fù)Q至尖鍵字較大的元素 之上，使得經(jīng)過一趟冒泡排序后，尖鍵字最小的元素到達(dá)最上端，接著，再在剩下的元素中，找尖鍵字次小 的元素，并把它換到第二個位置上。以此類推，一直到所有元素都有序為止。快速排序：