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

1、學而不思則惘，思而不學則殆數(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ù)元素之間的關(guān)系，可以看作是互相之間存在著某種特定關(guān)系的數(shù)據(jù)元素的集合，即可把數(shù)據(jù)結(jié)構(gòu)看成是帶結(jié)構(gòu)的數(shù)據(jù)元素的集合。問題1.2數(shù)據(jù)項、邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)的關(guān)系是什么？數(shù)據(jù)項：具有獨立含義的最小數(shù)據(jù)單位，也稱為字段或域邏輯結(jié)構(gòu)：從邏輯關(guān)系上描述數(shù)據(jù)，與數(shù)據(jù)的存儲無關(guān)，獨立與計算機。可以看作 是從具體問題抽象出來的數(shù)學模型。存儲結(jié)構(gòu)：邏輯結(jié)構(gòu)在計算機中的存儲方式，依賴于計算機語言。問題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、鏈式存儲3、索引存儲4、散列存儲問題1.5數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型的區(qū)別是什么？數(shù)據(jù)結(jié)構(gòu)：所有數(shù)據(jù)元素以及數(shù)據(jù)元素之間的關(guān)系，可以看作是互相之間存在著某種特定關(guān)系的數(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)某個抽象運算。 特性：有窮性、確定性、可行性、有輸入、有輸出。問題1.7如何分析算法的時間復雜度？由其中基本運算的執(zhí)行次數(shù)來計量。記作：T(n)=0(f(n

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

4、表示算法的時間性能。將基本語句執(zhí)行次數(shù)的數(shù)量級放入大0記號中。問題1.8如何分析算法的空間復雜度？空間復雜度是對一個算法在運行過程中臨時占用存儲空間大小的量度。一個算法在計算機存儲器上所占用的存儲空間， 包括存儲算法本身所占用的存儲空間， 算法的 輸入輸出數(shù)據(jù)所占用的存儲空間和算法在運行過程中臨時占用的存儲空間這三個方面。記作：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ǔ) 上，對抽象算法的具體描述。算法是解題的方法， 沒有了算法，

5、程序就成了無源之水， 有了算法，表達程序?qū)⒉?再那么困難，算法在程序設(shè)計、軟件開發(fā)甚至整個計算機科學領(lǐng)域都極其重要。所以：程序=數(shù)據(jù)結(jié)構(gòu)+算法問題1.10數(shù)據(jù)結(jié)構(gòu)和C語言的區(qū)別是什么？C語言是一種編程的語言，編程的語言有很多種。而數(shù)據(jù)結(jié)構(gòu)則是講的是關(guān)于一些 數(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ù)關(guān)系、基本運算、Init_List(&L):線性表初始化，構(gòu)造一個空的線性表L.Destro

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

7、, i,& e):插入數(shù)據(jù)元素，在線性表L中刪除序號第i(1<=i<=n+1)個元 素之前插入新的元素e，L的長度增1.ListDelete(&L,i,&e):刪除數(shù)據(jù)元素，在線性表L中刪除序號第i(1<=i<=n)個元素，并用e返回其值，L的長度減1.問題2.3線性表的順序存儲結(jié)構(gòu)如何實現(xiàn)？線性表的順序存儲結(jié)構(gòu)是利用數(shù)組來實現(xiàn)的，數(shù)組的基本類型就是線性表中元素的類型，數(shù)組的大小要大于等于線性表的長度。問題2.4實現(xiàn)順序表的基本運算有哪些？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線性表的鏈式存儲結(jié)構(gòu)如何實現(xiàn)？利用單鏈表、雙鏈表、循環(huán)鏈表實現(xiàn)。問題2.6什么是單鏈表？單鏈表的操作有哪些？單鏈表：在每個節(jié)點中，除數(shù)據(jù)域外，應(yīng)只設(shè)置一個指針域，用以指向其后繼節(jié)點。插入和刪除節(jié)點操作。其基本運算可實現(xiàn)：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什么是雙鏈表？其操作有哪些？在每個節(jié)點中，除數(shù)據(jù)域外，設(shè)置兩個指針域，分別用以指向其前驅(qū)結(jié)點和后繼節(jié) 點。其基本運算與單鏈表相同，插入與刪除節(jié)點操作方法不同。問題2.8什么是循環(huán)鏈表？其和單鏈表、雙鏈表的區(qū)別是什么？循環(huán)鏈表中尾節(jié)點的指針域不再為空，而是指向頭節(jié)點，整個鏈表形成一個環(huán)。問題2.9有序表的概念及其歸并算法如何實現(xiàn)？有序表：其中所有元素以遞增或遞減的方式有序排列的線性表。

10、第3章棧和隊列 問題3.1什么是棧？其抽象數(shù)據(jù)類型是什么？棧是一種只能在一端進行插入或刪除操作的線性表問題3.2棧的特點是什么？棧的主要特點是“后進先出”，即后進棧的元素先彈出。問題3.3棧的順序存儲結(jié)構(gòu)運算有哪些？如何實現(xiàn)？(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棧的鏈式存儲結(jié)構(gòu)運算有哪些？如何實現(xiàn)？（1 ）初始化棧InitStack（s）。建立一個空棧 s。實際上是創(chuàng)建鏈棧的頭節(jié)點，并 將其next 域置為NULL（2） 銷毀棧DestoryStack（s）。釋放棧s占用的全部存儲空間。（3）判斷棧是否為空 StackEmpty（s）。棧s為空的條件是s->next=NULL,即單鏈 表中沒有數(shù)據(jù)節(jié)點。（4）進棧Push（s,e）。將新數(shù)據(jù)節(jié)點插入到頭節(jié)點之后。（5）出棧Pop

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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