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

1、第一章 概論1. 單項(xiàng)選擇題1.1 B 1.2 C 1.3 A 1.4 D 1.5 A1.6 D 1.7 D 1.8 A 1.9 D 1.10 B2. 填空題2.1 邏輯結(jié)構(gòu) 2.2 查找 2.3 讀取2.4 插入 2.5 刪除 2.6 更新2.7 索引存儲(chǔ) 2.8 執(zhí)行算法所需要的時(shí)間2.9 邏輯運(yùn)算 2.10 存儲(chǔ)結(jié)構(gòu)3. 簡(jiǎn)答題3.1答：凡是能被計(jì)算機(jī)存儲(chǔ)、加工的對(duì)象統(tǒng)稱為數(shù)據(jù)，數(shù)據(jù)是一個(gè)集合。數(shù)據(jù)元素是數(shù)據(jù)的基本單位，是數(shù)據(jù)的一個(gè)元素。數(shù)據(jù)元素與數(shù)據(jù)之間的關(guān)系是元素與集合之間的關(guān)系。3.2答：數(shù)據(jù)：數(shù)據(jù)是信息的載體，它能夠被計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理數(shù)據(jù)元素：是數(shù)據(jù)的基本單位。有時(shí)一個(gè)

2、數(shù)據(jù)元素包含幾個(gè)數(shù)據(jù)項(xiàng)數(shù)據(jù)類型：是一個(gè)值的集合以及在這些值上定義的一組操作的總稱數(shù)據(jù)結(jié)構(gòu)：指的是數(shù)據(jù)之間的邏輯關(guān)系也稱數(shù)據(jù)的邏輯結(jié)構(gòu)。它包括線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩大類。存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲(chǔ)器內(nèi)的表示，稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。線性結(jié)構(gòu)：如果結(jié)構(gòu)非空，則有且僅有一個(gè)開(kāi)始結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)，并且所有的結(jié)點(diǎn)都最多只有一個(gè)直接前驅(qū)和一個(gè)直接后繼非線性結(jié)構(gòu)：該結(jié)構(gòu)的邏輯特征是一個(gè)結(jié)點(diǎn)可能有多個(gè)直接前驅(qū)和直接后繼3.3答：順序存儲(chǔ)結(jié)構(gòu)是將各數(shù)據(jù)元素的存儲(chǔ)位置按其之間的邏輯關(guān)系存放在一塊連續(xù)的存儲(chǔ)空間內(nèi)，由數(shù)據(jù)元素的存儲(chǔ)位置體現(xiàn)數(shù)據(jù)元素之間的邏輯關(guān)系。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)各數(shù)據(jù)元素不一定是存儲(chǔ)在連續(xù)的一

3、塊存儲(chǔ)空間內(nèi)，數(shù)據(jù)元素之間的邏輯關(guān)系與存儲(chǔ)位置沒(méi)有一一對(duì)應(yīng)的關(guān)系，數(shù)據(jù)元素之間的邏輯關(guān)系，是依靠附加在存儲(chǔ)數(shù)據(jù)元素的結(jié)點(diǎn)中的指針表示3.4答：a.算法必須是正確的b.執(zhí)行算法所耗費(fèi)的時(shí)間c.執(zhí)行算法所耗費(fèi)的空間，其中主要考慮輔助存儲(chǔ)空間d.算法應(yīng)易于理解、易于編碼、易于調(diào)試等等。4. 應(yīng)用題4.1其中語(yǔ)句y=y+1的頻度是n-1，語(yǔ)句x=x+1的頻度是（n-1）（2n+1）。所以該程序的算法時(shí)間復(fù)雜度是：T（n）=O（n-1）（2n+1）=O（n2）4.2由于嵌套最深的語(yǔ)句的頻度為n，所以其算法的時(shí)間復(fù)雜度為O（n）。第二章 線性表1 單項(xiàng)選擇題1.1 A 1.2 C 1.3 D 1.4 A

4、1.5 C1.6 A 1.7 C 1.8 A2 填空題2.1 n-i+1 2.2 n-I 2.3 相鄰 2.4 p！=NULL 2.5 L*（i-1） 2.6 直接前驅(qū)2.7 表頭指針 2.8 s-next=s2.9 s-next=s-prior=s3 簡(jiǎn)答題3.1答：a.線性表的順序存儲(chǔ)表示結(jié)構(gòu)簡(jiǎn)單，不需要額外的存儲(chǔ)空間，數(shù)據(jù)記錄在邏輯上相鄰，在存儲(chǔ)位置上亦相鄰，可隨機(jī)存取，有些運(yùn)算容易實(shí)現(xiàn)；但在做插入和刪除運(yùn)算時(shí)要移動(dòng)大量的元素，表長(zhǎng)是固定的，不易擴(kuò)展。b.鏈?zhǔn)酱鎯?chǔ)表示是動(dòng)態(tài)結(jié)構(gòu)，表長(zhǎng)可任意擴(kuò)充，插入和刪除不需要移動(dòng)大量的元素；但不能隨機(jī)存取，需要增加相應(yīng)的存儲(chǔ)空間。3.2答： 在開(kāi)始結(jié)點(diǎn)

5、之前附設(shè)的一個(gè)結(jié)點(diǎn)稱為頭結(jié)點(diǎn)，它的數(shù)據(jù)域值是無(wú)意義的，而開(kāi)始結(jié)點(diǎn)是鏈表中存儲(chǔ)線性表中第一個(gè)元素的結(jié)點(diǎn)。3.3答：循環(huán)鏈表和雙向鏈表4 算法設(shè)計(jì)4.1在順序表中第i個(gè)位置上插入元素x j=L-length-1 L-dataj4.2將順序表中位置為i的元素刪除 jlength-1 L-dataj; 4.3頭插法建立單鏈表(ListNode *)malloc(sizeof(ListNode) head 4.4尾插法建立單鏈表head=s; r-next=s; 4.5在鏈表中查找序號(hào)為i的結(jié)點(diǎn)p-next&jnext;4.6將值為x的結(jié)點(diǎn)插入到單鏈表的第i個(gè)位置上GetNode(head,i-1);p

6、-next;4.7刪除單鏈表中的第i個(gè)結(jié)點(diǎn)p-next;r-next;第三章 棧和隊(duì)列1. 單項(xiàng)選擇題1.1 B 1.2 B 1.3 D 1.4 C 1.5 D1.6 B 1.7 A 1.8 C 1.9 B 1.10 A1.11 A 1.12 B 1.13 A 1.14 A 1.15 B1.16 A 1.17 B 1.18 D 1.19 B 1.20 D2. 填空題2.1 先進(jìn)先出2.2 S.top=-12.3 S.top=maxsize-12.4 棧滿2.5 空棧2.6 n-12.7 s.topnext2.11 ls-next=NULL2.12 首2.13 b2.14隊(duì)空否1.15 sq.d

7、atai2.16 sq.datamax2.17 max+12.18 尾2.19 02.20 03.簡(jiǎn)答題3.1答：進(jìn)棧操作是先將棧頂指針加1后，再將待插入元素入棧，退棧操作則是先取出棧頂元素，在使棧頂指針減1。3.2答：入隊(duì)操作的指針移動(dòng)語(yǔ)句為：cq.rear=(cq.rear+1)%QueueSize；出隊(duì)操作的指針移動(dòng)語(yǔ)句為：cq.front=(cq.front+1)%QueueSize；3.3答：所有可能的出站順序有：123，132，213，231，321，不可能是312，因?yàn)楫?dāng)3號(hào)車進(jìn)站并出站后，站臺(tái)上有1號(hào)車和2號(hào)車，不可能先出1號(hào)而后出2號(hào)。3.4答：出隊(duì)操作是刪除隊(duì)頭元素（修改頭

8、指針）之后，再返回該刪除元素值，而取隊(duì)頭操作僅僅是取出隊(duì)頭元素值返回，不修改隊(duì)頭指針。3.5答：簡(jiǎn)述下面給出的算法的功能是什么？（假設(shè)棧元素為整數(shù)類型）此算法的功能是通過(guò)一個(gè)數(shù)組將一個(gè)棧中的所有元素逆置存放。 3.6答：該算法的功能是通過(guò)一個(gè)中間棧T，達(dá)到刪除棧S中所有與變量C相同的元素。3.7答：只設(shè)頭指針的入隊(duì)操作時(shí)間復(fù)雜度為O（n）；只設(shè)尾指針的入隊(duì)操作時(shí)間復(fù)雜度為O（1）3.8答：棧叫先進(jìn)后出表或叫后進(jìn)先出表。棧的插入和刪除都從稱為棧頂?shù)囊欢诉M(jìn)行，一般線性表可以在線性表的中間及兩端進(jìn)行插入和刪除操作。3.9答：隊(duì)列叫先進(jìn)先出表（FIFO）或叫后進(jìn)后出表，隊(duì)列的插入只能在隊(duì)列的一端進(jìn)行，

9、該端稱為隊(duì)尾。隊(duì)列的刪除只能從另一端進(jìn)行，該端稱為隊(duì)頭。一般線性表可以在線性表的中間及兩端進(jìn)行插入和刪除操作。3. 10答：棧和隊(duì)列都是加了限制的線性表，棧叫后進(jìn)先出表，隊(duì)列叫先進(jìn)先出表。棧和隊(duì)列的插入和刪除運(yùn)算都在端點(diǎn)進(jìn)行，棧的插入與刪除在同一端點(diǎn)，隊(duì)列的插入與刪除在不同的端點(diǎn)進(jìn)行。棧與隊(duì)列的元素個(gè)數(shù)都是可變的，同一個(gè)棧或同一個(gè)隊(duì)列中的元素類型是一致的。3.11寫(xiě)出下列程序段的輸出結(jié)果 輸出結(jié)果：stack3.12 簡(jiǎn)述下列算法的功能 借助數(shù)組將S棧內(nèi)的元素倒置3.13 簡(jiǎn)述下列算法的功能借助T棧將S棧內(nèi)的元素倒置4.算法設(shè)計(jì)4.1順序棧的六種基本操作 S-data+S-top=x; S-d

10、ataS-top4.2循環(huán)隊(duì)列基本算法 Q-rear=(Q-rear+1)%QueueSize; return Q-dataQ-front第四章 串1.單項(xiàng)選擇題1.1 A 1.2 B 1.3 D 1.4 A 1.5 B1.6 C 1.7 B 1.8 B2.填空題2.1 122.2 abcdefg3.簡(jiǎn)答題3.1答：串長(zhǎng)度為零的串稱為空串，它不包含任何字符；而空格串是有若干個(gè)空格字符構(gòu)成的串，它的長(zhǎng)度取決于空格的個(gè)數(shù)。3.2答：串的特殊性就在于它的每個(gè)元素僅由一個(gè)字符組成。3.3答：子串的定位運(yùn)算又稱為串的模式匹配，子串定位就是要在主串中找出一個(gè)與給定子串相同的子串，把這個(gè)主串稱為目標(biāo)串，而給

11、定的子串稱為模式串。3.4答：兩個(gè)串相等的充分必要條件是兩串的長(zhǎng)度相等且對(duì)應(yīng)位置的字符相同。第五章 多維數(shù)組和廣義表1.單項(xiàng)選擇題1.1 D 1.2 C 1.3 B 1.4 D 1.5 C 1.6 B2.填空2.1 LOC（A00）+（n*i+j）*k2.2 3322.3 42第六章 樹(shù)1.單項(xiàng)選擇題1.1C 1.2A 1.3D 1.4B 1.5B 1.6C 1.7B 1.8D 1.9B 1.10D1.11A 1.12A 1.13B 1.14A 1.15A1.16A 1.17C 1.18A 1.19B 1.20B2.填空2.1 2k-1 2.2 2k-1 2.3 n0-12.4 2i-1 2.

12、5 5 2.6 02.7 n+1 2.8 2n-1 2.9 中序2.10 雙親鏈表表示法 2.11 孩子鏈表表示法2.12 2k-1 2.13 7 2.14 183.簡(jiǎn)答3.1 樹(shù)：是n(n0)個(gè)結(jié)點(diǎn)的有限集T，T為空時(shí)稱空樹(shù)，否則它滿足如下兩個(gè)條件：有且僅有一個(gè)特定的稱為根的結(jié)點(diǎn)；其余的結(jié)點(diǎn)可分為m（m0）個(gè)互不相交的子集T1，T2，Tm，其中每個(gè)子集本身又是一棵樹(shù)，并稱其為根的子樹(shù)。3.2 二叉樹(shù)：是n(n0)個(gè)結(jié)點(diǎn)的有限集，它或者是空集（n=0）,或者由一個(gè)根結(jié)點(diǎn)及兩個(gè)互不相交的、分別稱作這個(gè)根的左子樹(shù)和右子樹(shù)的二叉樹(shù)組成。3.3 樹(shù)的遍歷：是指沿著某條搜索路線，依次對(duì)樹(shù)中的每個(gè)結(jié)點(diǎn)均做

13、一次且僅做一次訪問(wèn)。3.4 哈夫曼樹(shù)：在權(quán)為w1,w2,，wn的n個(gè)結(jié)點(diǎn)所構(gòu)成的所有二叉樹(shù)中，帶權(quán)路徑長(zhǎng)度最小的二叉樹(shù)稱為最優(yōu)二叉樹(shù)，又稱哈夫曼樹(shù)。4.應(yīng)用bdgacehf4.1 后序遍歷序列：gdbehfcabchadefg4.2 先序遍歷序列：abcdefgh4.3 BCHADEFGJI4.4 data firstchild12 3 4 5 6 78 9 ABCDE F G H I J root 0 1 2 3 4 5 6 7 8 94.5 下標(biāo)0123456789 MaxTreeSize-1 dataABCDEFGHIJparent-10001123334.6 D H F I C G J

14、 A B E T4.7 假設(shè)7個(gè)結(jié)點(diǎn)分別為a、b、c、d、e、f、g，它們對(duì)應(yīng)的權(quán)值為8、11、13、5、17、25、21，構(gòu)造的哈夫曼樹(shù)如下：該哈夫曼樹(shù)的帶權(quán)路徑長(zhǎng)度為：WPL=84+54+173+113+133+252+212 =287gfedbca 100 45 5521 24 25 30 11 13 17 13 8 5 5.算法5.1i=n;im;i+Tp1.parent= Tp2.parent=i第七章 圖1.單項(xiàng)選擇題1.1A 1.2C 1.3B 1.4B 1.5D 1.6C 1.7A 1.8B 1.9C 1.10B1.11A 1.12C 1.13B 1.14B 1.15C1.16

15、C 1.17 D 1.18C 1.19C 1.20A1.21C 1.22A 1.23D 1.24A 1.21B2.填空2.1 n-1 2.2 1 2.3 O(n+e)2.4 O(n+e) 2.5 求矩陣第i列非零元素之和2.6 將矩陣第i行全部元素置為0 2.7 最小2.8 n-1 2.9 1 2.10 2(n-1)2.11 n(n-1) 2.12 28 2.13 先序2.14 按層次 2.15 鄰接表 2.16 逆鄰接表3.簡(jiǎn)答3.1圖的深度優(yōu)先遍歷：假設(shè)給定圖的初態(tài)是所有頂點(diǎn)均未曾訪問(wèn)過(guò)，在G上任選一頂點(diǎn)v作為源點(diǎn)，則深度優(yōu)先遍歷定義如下：首先訪問(wèn)出發(fā)點(diǎn)v，并將其標(biāo)記為已訪問(wèn)過(guò)；然后依次從

16、v出發(fā)搜索v的每個(gè)鄰接點(diǎn)w，若w未曾訪問(wèn)過(guò)，則以w為新的出發(fā)點(diǎn)繼續(xù)進(jìn)行深度優(yōu)先遍歷，直到圖中所有和源點(diǎn)v有路徑相通的頂點(diǎn)均被訪問(wèn)過(guò)；若此時(shí)圖中仍有未訪問(wèn)有頂點(diǎn)，則另選一個(gè)尚未被訪問(wèn)過(guò)的頂點(diǎn)作為新的源點(diǎn)重復(fù)上述過(guò)程，直到所有頂點(diǎn)均已訪問(wèn)過(guò)。3.2 圖的廣度優(yōu)先遍歷：假設(shè)給定圖的初態(tài)是所有頂點(diǎn)均未曾訪問(wèn)過(guò)，在G上任選一頂點(diǎn)v作為初始出發(fā)點(diǎn)，則廣度優(yōu)先遍歷定義如下：首先訪問(wèn)出發(fā)點(diǎn)v，接著依次訪問(wèn)v的所有鄰接點(diǎn)w1,w2,wt,然后再依次訪問(wèn)與w1,w2,wt鄰接的所有未曾訪問(wèn)過(guò)的頂點(diǎn)。直到圖中所有和源點(diǎn)v有路徑相通的頂點(diǎn)均被訪問(wèn)過(guò)；若此時(shí)圖中仍有未訪問(wèn)有頂點(diǎn)，則另選一個(gè)尚未被訪問(wèn)過(guò)的頂點(diǎn)作為新的源點(diǎn)

17、重復(fù)上述過(guò)程，直到所有頂點(diǎn)均已訪問(wèn)過(guò)。3.3 拓?fù)渑判颍簩?duì)于一個(gè)有向無(wú)環(huán)圖進(jìn)行拓?fù)渑判颍菍中所有頂點(diǎn)排成一個(gè)線性序列，使得對(duì)圖中任意一個(gè)頂點(diǎn)u和v，若E(G)，則u在線性序列中出現(xiàn)在v之前。3.4 連通圖：在無(wú)向圖G中，若從頂點(diǎn)vi到頂點(diǎn)vj有路徑，則稱vi和vj是連通的，若V（G）上任意兩個(gè)不同的頂點(diǎn)vi和vj都連通，則稱G為連通圖。3.5 強(qiáng)連通圖：在有向圖中，若對(duì)于V（G）中任意兩個(gè)不同的頂點(diǎn)vi和vj，都存在從vi到vj以及vj到vi的路徑，則稱G是強(qiáng)連通圖。3.6 最小生成樹(shù)：對(duì)于連通的帶權(quán)圖G，其生成樹(shù)也是帶權(quán)的，我們把生成樹(shù)T的各邊的權(quán)值總和稱為該樹(shù)的權(quán)，將權(quán)值最小的生成樹(shù)稱

18、為G的最小生成樹(shù)，簡(jiǎn)記MST。4.應(yīng)用4.1存拓?fù)渑判蛐蛄校?23654123546231424.2最小生成樹(shù)：4.3 鄰接矩陣：廣度優(yōu)先遍歷結(jié)果：124536深度優(yōu)先遍歷結(jié)果：1234564.4 圖G的鄰接表：01234 3 4 4 2 2 1 2 3 0 1 0 1 V1 V2 V3 V4 V54.5 圖G的逆鄰接表： 3 0 0 2 V1 V2 V3 V4E F G H I J 0123頂點(diǎn)入度出度V112V210V311V4115.算法5.1 i=0;in;i+ k=0;ke;k+5.2 !QueueEmpty(&Q) j=0;jn;j+5.3 k=0;kn-1;k+ e=Tm;Tmt

19、k;Tk=e;5.4 !StackEmpty(&S)p=G.adjlisti.firstedge第八章 排序1 單項(xiàng)選擇1.01 B 1.02 D 1.03 C 1.04 B 1.05 A 1.06 A 1.07 A 1.08 C 1.09 A 1.10 A1.11 B 1.12 D 1.13 D 1.14 A 1.15 C1.16 A 1.17 D 1.18 A 2 填空1.01分配排序 1.02靜態(tài)查找 1.03動(dòng)態(tài)查找 1.04沖突 1.05排序 1.06哈希函數(shù)（散列函數(shù)）1.07 n-1 1.08 0 1.09多關(guān)鍵字文件3 簡(jiǎn)答3.01簡(jiǎn)述穩(wěn)定排序和非穩(wěn)定排序。若待排序的文件中，存

20、在有多個(gè)關(guān)鍵字相同的記錄，經(jīng)過(guò)排序后這些具有相同關(guān)鍵字的記錄之間的相對(duì)次序保持不變，則稱這種排序方法是穩(wěn)定的；反之若具有相同關(guān)鍵字的記錄之間的相對(duì)次序發(fā)生變化，則稱這種排序方法是不穩(wěn)定的。3.02簡(jiǎn)述插入排序算法中的哨兵作用 在插入排序算法中，將要前插的記錄ri保存在r0稱作為哨兵。它的主要作用是用來(lái)在查找循環(huán)中“監(jiān)視”下標(biāo)變量j是否越界，因?yàn)閞0就是ri本身，所以一旦越界（即j=0）則循環(huán)條件r0.key=high為止。3.04如何選擇合適的排序方法？若n較小時(shí)，可以采用直接插入、直接選擇或冒泡排序方法；若文件初始狀態(tài)基本有序，則可以選擇直接插入、冒泡排序方法；若n較大時(shí)，則應(yīng)選擇快速排序、

21、堆排序或歸并排序方法。4 應(yīng)用4.01給定數(shù)據(jù)35，27，86，39，58，19，46，74；請(qǐng)寫(xiě)出按插入排序的每一趟結(jié)果。3527 86 39 58 19 46 7427 3586 39 58 19 46 7427 35 8639 58 19 46 7427 35 39 8658 19 46 7427 35 39 58 8619 46 7419 27 35 39 58 8646 7419 27 35 39 46 58 867419 27 35 39 46 58 74 864.02給定數(shù)據(jù)49，33，61，82，75，12，25，58，29；請(qǐng)寫(xiě)出按快速排序的每一趟結(jié)果。49 33 61 82

22、 75 12 25 58 2929 33 25 124975 82 58 6112 2529334961 587582122529 33 49 5861 75 82 12 25 29 33 49 58 61 75 824.03給定數(shù)據(jù)35，27，86，39，58，19，46，74；請(qǐng)寫(xiě)出按選擇排序的每一趟結(jié)果。1927 86 39 58 35 46 7419 2786 39 58 35 46 7419 27 3539 58 86 46 7419 27 35 3958 86 46 7419 27 35 39 4686 58 7419 27 35 39 46 5886 7419 27 35 39

23、46 58 748619 27 35 39 46 58 74 864.04給定數(shù)據(jù)48，32，61，82，75，19，25，58；請(qǐng)寫(xiě)出按冒泡排序的每一趟結(jié)果。48 32 61 82 75 19 25 581948 32 61 82 75 25 5819 2548 32 61 82 75 5819 25 3248 58 61 82 7519 25 32 4858 61 75 8219 25 32 4858 61 75 8219 25 32 48 58 61 75 824.05給定數(shù)據(jù)38，29，81，34，58，19，46，76；請(qǐng)寫(xiě)出按冒泡排序的每一趟結(jié)果。38 29 81 34 58 19

24、 46 761938 29 81 34 58 46 7619 2938 34 81 46 58 7619 2938 34 81 46 58 7619 29 3438 46 81 58 7619 29 34 3846 58 81 7619 29 34 38 46 58 81 764.06給定數(shù)據(jù)52，33，61，82，75，18，45，58，26；請(qǐng)寫(xiě)出按快速排序的每一趟結(jié)果。52 33 61 82 75 18 45 58 2626 33 45 185275 82 58 61182645 335261 58758218 263345 525861 75 8218 26 33 45 52 58 6

25、1 75 825 算法5.01直接插入排序算法（遞增）Ri.key Ri-1.keyj = i-15.02冒泡排序算法（遞增）i nRj+1.key Rj.key5.03歸并排序算法i=m & j=high P+, i+第九章 查找1 單項(xiàng)選擇1.01 B 1.02 D 1.03 B 1.04 A 1.05 D1.06 B 1.07 C 1.08 D 1.09 A 1.10A1.11 C 1.12 C 1.13 D 1.14 C 1.15 B1.16 B 1.17 C 1.18 C 1.19 A 2 填空2.01 動(dòng)態(tài)查找表 2.02 散列函數(shù)（哈希函數(shù)） 2.03 散列表的長(zhǎng)度2.04 28

26、 2.05 60 2.06 32.07 5 2.08 35 2.09 272.10 (n+1)/2 2.11 log2(n+1)-1 2.12 (s2+2s+n)/(2s)2.13 散列查找方法 2.14 按關(guān)鍵字有序 3 簡(jiǎn)答3.01簡(jiǎn)述靜態(tài)查找和動(dòng)態(tài)查找。若在查找的同時(shí)對(duì)查找表進(jìn)行修改操作（插入或刪除操作），則相應(yīng)的查找表稱之為動(dòng)態(tài)查找表；否則稱之為靜態(tài)查找表。3.02什么是平均查找路徑長(zhǎng)度ASL。通常把查找過(guò)程當(dāng)中對(duì)關(guān)鍵字比較的平均次數(shù)作為平均查找路徑長(zhǎng)度。若n是查找表的結(jié)點(diǎn)數(shù)，pi是查找第i個(gè)結(jié)點(diǎn)的概率，ci是找到第i個(gè)結(jié)點(diǎn)的比較次數(shù)，則平均查找路徑長(zhǎng)度 ASL= pici。3.03簡(jiǎn)

27、述二分查找的基本思想。設(shè)rlowhigh為當(dāng)前的查找區(qū)間，首先確定區(qū)間的中點(diǎn)位置m=(low+high)/2；然后將待查關(guān)鍵字K與rm.key進(jìn)行比較，若相等則查找成功并返回位置m；若Krm.key，則令low=m+1；確定新的查找區(qū)間再次進(jìn)行查找，直到查找成功或查找區(qū)間為零時(shí)（查找失?。┙Y(jié)束。3.04簡(jiǎn)述二叉排序樹(shù)的性質(zhì)。若它的左子樹(shù)非空，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；若它的右子樹(shù)非空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值；左、右子樹(shù)本身仍是一棵二叉排序樹(shù)。3.05簡(jiǎn)述散列表中的沖突（碰橦）概念。有兩個(gè)不同的關(guān)鍵字k1和k2，通過(guò)散列函數(shù)計(jì)算映射到表的同一個(gè)位置空間時(shí)，即：H(k

28、1)=H(k2)，則稱之為發(fā)生沖突（碰橦），而發(fā)生沖突的兩個(gè)關(guān)鍵字稱為該散列函數(shù)的同義詞。3.06散列函數(shù)的選擇標(biāo)準(zhǔn)是什么？散列函數(shù)選擇有兩條標(biāo)準(zhǔn)：簡(jiǎn)單和均勻。簡(jiǎn)單是指散列函數(shù)的計(jì)算簡(jiǎn)單快捷；均勻是指散列函數(shù)能將集合中的關(guān)鍵字以等概率映射到查找表的任何一個(gè)位置空間。3.07簡(jiǎn)述在散列表中拉鏈法解決沖突的基本思想。拉鏈法解決沖突的做法是，將所有關(guān)鍵字為同義詞的結(jié)點(diǎn)鏈接在同一個(gè)單鏈表中。首先選定散列表的長(zhǎng)度m，然后構(gòu)造由m個(gè)頭指針組成的指針數(shù)組T0m-1，凡是映射地址為i的結(jié)點(diǎn)，均插入以Ti為頭指針的鏈表中。4 應(yīng)用4.01按拉鏈法構(gòu)造構(gòu)造散列函數(shù)表 0123456515635154662374126181030在等