數(shù)據(jù)結(jié)構(gòu)期末考試復(fù)習(xí)題及參考答案

1、第1章 緒論1. 填空（1）（ ）是數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理?！窘獯稹繑?shù)據(jù)元素 （2）（ ）是數(shù)據(jù)的最小單位，（ ）是討論數(shù)據(jù)結(jié)構(gòu)時(shí)涉及的最小數(shù)據(jù)單位?！窘獯稹繑?shù)據(jù)項(xiàng)，數(shù)據(jù)元素【分析】數(shù)據(jù)結(jié)構(gòu)指的是數(shù)據(jù)元素以及數(shù)據(jù)元素之間的關(guān)系。 （3）從邏輯關(guān)系上講，數(shù)據(jù)結(jié)構(gòu)主要分為（ ）、（ ）、（ ）和（ ）。【解答】集合，線性結(jié)構(gòu)，樹結(jié)構(gòu)，圖結(jié)構(gòu) （4）數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)主要有（ ）和（ ）兩種基本方法，不論哪種存儲(chǔ)結(jié)構(gòu)，都要存儲(chǔ)兩方面的內(nèi)容：（ ）和（ ）?！窘獯稹宽樞虼鎯?chǔ)結(jié)構(gòu)，鏈接存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素，數(shù)據(jù)元素之間的關(guān)系 （5）算法具有五個(gè)特性，分別是（ ）、（ ）、

2、（ ）、（ ）、（ ）?！窘獯稹坑辛銈€(gè)或多個(gè)輸入，有一個(gè)或多個(gè)輸出，有窮性，確定性，可行性（6）在一般情況下，一個(gè)算法的時(shí)間復(fù)雜度是（ ）的函數(shù)?！窘獯稹繂栴}規(guī)模 （7）設(shè)待處理問題的規(guī)模為n，若一個(gè)算法的時(shí)間復(fù)雜度為一個(gè)常數(shù)，則表示成數(shù)量級(jí)的形式為（ ），若為n*log25n，則表示成數(shù)量級(jí)的形式為（ ）?！窘獯稹?1)，(nlog2n) 【分析】用大o記號(hào)表示算法的時(shí)間復(fù)雜度，需要將低次冪去掉，將最高次冪的系數(shù)去掉。2. 選擇題 順序存儲(chǔ)結(jié)構(gòu)中數(shù)據(jù)元素之間的邏輯關(guān)系是由（ ）表示的，鏈接存儲(chǔ)結(jié)構(gòu)中的數(shù)據(jù)元素之間的邏輯關(guān)系是由（ ）表示的。a 線性結(jié)構(gòu) b 非線性結(jié)構(gòu) c 存儲(chǔ)位置 d 指針

3、【解答】c，d 【分析】順序存儲(chǔ)結(jié)構(gòu)就是用一維數(shù)組存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素，其邏輯關(guān)系由存儲(chǔ)位置（即元素在數(shù)組中的下標(biāo)）表示；鏈接存儲(chǔ)結(jié)構(gòu)中一個(gè)數(shù)據(jù)元素對(duì)應(yīng)鏈表中的一個(gè)結(jié)點(diǎn)，元素之間的邏輯關(guān)系由結(jié)點(diǎn)中的指針表示。 假設(shè)有如下遺產(chǎn)繼承規(guī)則：丈夫和妻子可以相互繼承遺產(chǎn)；子女可以繼承父親或母親的遺產(chǎn)；子女間不能相互繼承。則表示該遺產(chǎn)繼承關(guān)系的最合適的數(shù)據(jù)結(jié)構(gòu)應(yīng)該是（ ）。a 樹 b 圖 c 線性表 d 集合【解答】b【分析】將丈夫、妻子和子女分別作為數(shù)據(jù)元素，根據(jù)題意畫出邏輯結(jié)構(gòu)圖。 算法指的是（ ）。a 對(duì)特定問題求解步驟的一種描述，是指令的有限序列。b 計(jì)算機(jī)程序 c 解決問題的計(jì)算方法 d 數(shù)

4、據(jù)處理【解答】a【分析】計(jì)算機(jī)程序是對(duì)算法的具體實(shí)現(xiàn)；簡(jiǎn)單地說，算法是解決問題的方法；數(shù)據(jù)處理是通過算法完成的。所以，只有a是算法的準(zhǔn)確定義。 下面（ ）不是算法所必須具備的特性。a 有窮性 b 確切性 c 高效性 d 可行性【解答】c 【分析】高效性是好算法應(yīng)具備的特性。 算法分析的目的是（ ），算法分析的兩個(gè)主要方面是（ ）。a 找出數(shù)據(jù)結(jié)構(gòu)的合理性 b 研究算法中輸入和輸出的關(guān)系c 分析算法的效率以求改進(jìn) d 分析算法的易讀性和文檔性 e 空間性能和時(shí)間性能 f 正確性和簡(jiǎn)明性 g 可讀性和文檔性 h 數(shù)據(jù)復(fù)雜性和程序復(fù)雜性【解答】c，e 3. 判斷題（1） 算法的時(shí)間復(fù)雜度都要通過算法

5、中的基本語(yǔ)句的執(zhí)行次數(shù)來確定?！窘獯稹垮e(cuò)。時(shí)間復(fù)雜度要通過算法中基本語(yǔ)句執(zhí)行次數(shù)的數(shù)量級(jí)來確定。（2）每種數(shù)據(jù)結(jié)構(gòu)都具備三個(gè)基本操作：插入、刪除和查找?！窘獯稹垮e(cuò)。如數(shù)組就沒有插入和刪除操作。此題注意是每種數(shù)據(jù)結(jié)構(gòu)。 （3）邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無關(guān)?！窘獯稹繉?duì)。因此邏輯結(jié)構(gòu)是數(shù)據(jù)組織的主要方面。（4）基于某種邏輯結(jié)構(gòu)之上的基本操作，其實(shí)現(xiàn)是唯一的?！窘獯稹垮e(cuò)?；静僮鞯膶?shí)現(xiàn)是基于某種存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)的，因而不是唯一的。4. 分析以下各程序段，并用大o記號(hào)表示其執(zhí)行時(shí)間。 【解答】 基本語(yǔ)句是k=k+10*i，共執(zhí)行了n-2次，所以t(n)=o(n)。 基本語(yǔ)句是k=k+10*i，共執(zhí)

6、行了n次，所以t(n)=o(n)。 分析條件語(yǔ)句，每循環(huán)一次，i+j 整體加1，共循環(huán)n次，所以t(n)=o(n)。 每循環(huán)一次，循環(huán)變量y加1，最后一次y= t(n)，即： (t(n)+1)2n，t(n)= n1/2-1，y=0t(n)循環(huán)體都執(zhí)行，共t(n)+1次，即n1/2次，所以t(n)=o(n1/2)。 x+是基本語(yǔ)句，所以 5設(shè)有數(shù)據(jù)結(jié)構(gòu)（d，r），其中d=1, 2, 3, 4, 5, 6，r=,。試畫出其邏輯結(jié)構(gòu)圖并指出屬于何種結(jié)構(gòu)?！窘獯稹科溥壿嫿Y(jié)構(gòu)圖如圖1-3所示，它是一種圖結(jié)構(gòu)。6. 求多項(xiàng)式a(x)的算法可根據(jù)下列兩個(gè)公式之一來設(shè)計(jì)： a(x)=anxn+an-1xn-1

7、+a1x+a0 a(x)=(0*x+an)x+an-1)x+a1)x)+a0 根據(jù)算法的時(shí)間復(fù)雜度分析比較這兩種算法的優(yōu)劣?！窘獯稹康诙N算法的時(shí)間性能要好些。第一種算法需執(zhí)行大量的乘法運(yùn)算，而第二種算法進(jìn)行了優(yōu)化，減少了不必要的乘法運(yùn)算。8. 算法設(shè)計(jì)（要求：算法用偽代碼和c+描述，并分析最壞情況下的時(shí)間復(fù)雜度） 對(duì)一個(gè)整型數(shù)組an設(shè)計(jì)一個(gè)排序算法。 找出整型數(shù)組an中元素的最大值和次最大值。學(xué)習(xí)自測(cè)及答案1順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)是（ ），鏈接存儲(chǔ)結(jié)構(gòu)的特點(diǎn)是（ ）?！窘獯稹坑迷卦诖鎯?chǔ)器中的相對(duì)位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系，用指示元素存儲(chǔ)地址的指針表示數(shù)據(jù)元素之間的邏輯關(guān)系。 2. 算法在

8、發(fā)生非法操作時(shí)可以作出處理的特性稱為（ ）?！窘獯稹拷研?3. 常見的算法時(shí)間復(fù)雜度用大記號(hào)表示為：常數(shù)階( )、對(duì)數(shù)階( )、線性階 ( )、平方階( )和指數(shù)階( )?！窘獯稹?1)，(log2n)，(n)，(n2)，(2n) 4將下列函數(shù)按它們?cè)趎 時(shí)的無窮大階數(shù)，從小到大排列。n, n-n3+7n5, nlogn, 2n/2, n3, log2n, n1/2+log2n, (3/2)n, n!, n2+log2n 【解答】log2n, n1/2+log2n, n, nlog2n, n2+log2n, n3, n-n3+7n5, 2n/2, (3/2)n, n! 5試描述數(shù)據(jù)結(jié)構(gòu)和抽象

9、數(shù)據(jù)類型的概念與程序設(shè)計(jì)語(yǔ)言中數(shù)據(jù)類型概念的區(qū)別?！窘獯稹繑?shù)據(jù)結(jié)構(gòu)是指相互之間存在一定關(guān)系的數(shù)據(jù)元素的集合。而抽象數(shù)據(jù)類型是指一個(gè)數(shù)據(jù)結(jié)構(gòu)以及定義在該結(jié)構(gòu)上的一組操作。程序設(shè)計(jì)語(yǔ)言中的數(shù)據(jù)類型是一個(gè)值的集合和定義在這個(gè)值集上一組操作的總稱。6. 對(duì)下列用二元組表示的數(shù)據(jù)結(jié)構(gòu),試分別畫出對(duì)應(yīng)的邏輯結(jié)構(gòu)圖，并指出屬于何種結(jié)構(gòu)。 a=(d，r)， 其中d=a1, a2, a3, a4，r= b=(d，r)， 其中d=a, b, c, d, e, f，r=, c=( d，r)，其中d=a，b，c，d，e，f，r=(d,b),(e,g),(a,b),(b,c),(e,g),(g,h) d=(d，r)，

10、其中d=1, 2, 3, 4, 5, 6，r=(1, 2)，(1, 4)，(2, 3)，(2, 4)，(3, 4)，(3, 5)，(3, 6)，(4, 6) 【解答】 屬于集合，其邏輯結(jié)構(gòu)圖如圖1-4(a)所示； 屬于線性結(jié)構(gòu)，其邏輯結(jié)構(gòu)圖如圖1-4(b)所示； 屬于樹結(jié)構(gòu)，其邏輯結(jié)構(gòu)圖如圖1-4(c)所示； 屬于圖結(jié)構(gòu)，其邏輯結(jié)構(gòu)圖如圖1-4(d)所示。 7. 求下列算法的時(shí)間復(fù)雜度。count=0; x=1;while (x next=(p-next)-next 單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是（ ）?！窘獯稹繛榱诉\(yùn)算方便【分析】例如在插入和刪除操作時(shí)不必對(duì)表頭的情況進(jìn)行特殊處理。 非空的單循環(huán)

11、鏈表由頭指針head指示，則其尾結(jié)點(diǎn)（由指針p所指）滿足（ ）?！窘獯稹縫-next=head【分析】如圖2-8所示。 在由尾指針rear指示的單循環(huán)鏈表中，在表尾插入一個(gè)結(jié)點(diǎn)s的操作序列是（ ）；刪除開始結(jié)點(diǎn)的操作序列為（ ）?！窘獯稹縮-next =rear-next; rear-next =s; rear =s;q=rear-next-next; rear-next-next=q-next; delete q;【分析】操作示意圖如圖2-9所示： 一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表，在指針p所指結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為（ ）；在給定值為x的結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為（ ）?！窘獯稹?/p>

12、(1)，(n)【分析】在p所指結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)只需修改指針，所以時(shí)間復(fù)雜度為(1)；而在給定值為x的結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)需要先查找值為x的結(jié)點(diǎn)，所以時(shí)間復(fù)雜度為(n)。 可由一個(gè)尾指針唯一確定的鏈表有（ ）、（ ）、（ ）?！窘獯稹垦h(huán)鏈表，循環(huán)雙向鏈表，雙向鏈表2. 選擇題 線性表的順序存儲(chǔ)結(jié)構(gòu)是一種（ ）的存儲(chǔ)結(jié)構(gòu)，線性表的鏈接存儲(chǔ)結(jié)構(gòu)是一種（ ）的存儲(chǔ)結(jié)構(gòu)。 a 隨機(jī)存取 b 順序存取 c 索引存取 d 散列存取【解答】a，b【分析】參見2.2.1。 線性表采用鏈接存儲(chǔ)時(shí)，其地址（ ）。a 必須是連續(xù)的 b 部分地址必須是連續(xù)的c 一定是不連續(xù)的 d 連續(xù)與否均可以【解答】d【分析】

13、線性表的鏈接存儲(chǔ)是用一組任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素，這組存儲(chǔ)單元可以連續(xù)，也可以不連續(xù)，甚至可以零散分布在內(nèi)存中任意位置。 單循環(huán)鏈表的主要優(yōu)點(diǎn)是（ ）。a 不再需要頭指針了 b 從表中任一結(jié)點(diǎn)出發(fā)都能掃描到整個(gè)鏈表；c 已知某個(gè)結(jié)點(diǎn)的位置后，能夠容易找到它的直接前趨；d 在進(jìn)行插入、刪除操作時(shí)，能更好地保證鏈表不斷開?！窘獯稹縝 鏈表不具有的特點(diǎn)是（ ）。a 可隨機(jī)訪問任一元素 b 插入、刪除不需要移動(dòng)元素c 不必事先估計(jì)存儲(chǔ)空間 d 所需空間與線性表長(zhǎng)度成正比【解答】a 若某線性表中最常用的操作是取第i 個(gè)元素和找第i個(gè)元素的前趨，則采用（ ）存儲(chǔ)方法最節(jié)省時(shí)間。a 順序表 b 單

14、鏈表 c 雙向鏈表 d 單循環(huán)鏈表【解答】a【分析】線性表中最常用的操作是取第i 個(gè)元素，所以，應(yīng)選擇隨機(jī)存取結(jié)構(gòu)即順序表，同時(shí)在順序表中查找第i個(gè)元素的前趨也很方便。單鏈表和單循環(huán)鏈表既不能實(shí)現(xiàn)隨機(jī)存取，查找第i個(gè)元素的前趨也不方便，雙向鏈表雖然能快速查找第i個(gè)元素的前趨，但不能實(shí)現(xiàn)隨機(jī)存取。 若鏈表中最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)和刪除第一個(gè)結(jié)點(diǎn)，則采用（ ）存儲(chǔ)方法最節(jié)省時(shí)間。a 單鏈表 b 帶頭指針的單循環(huán)鏈表 c 雙向鏈表 d 帶尾指針的單循環(huán)鏈表【解答】d【分析】在鏈表中的最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)需要知道終端結(jié)點(diǎn)的地址，所以，單鏈表、帶頭指針的單循環(huán)鏈表、雙向鏈表

15、都不合適，考慮在帶尾指針的單循環(huán)鏈表中刪除第一個(gè)結(jié)點(diǎn)，其時(shí)間性能是o(1)，所以，答案是d 。 若鏈表中最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)和刪除最后一個(gè)結(jié)點(diǎn)，則采用（ ）存儲(chǔ)方法最節(jié)省運(yùn)算時(shí)間。a 單鏈表 b 循環(huán)雙向鏈表 c單循環(huán)鏈表 d 帶尾指針的單循環(huán)鏈表【解答】b【分析】在鏈表中的最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)需要知道終端結(jié)點(diǎn)的地址，所以，單鏈表、單循環(huán)鏈表都不合適，刪除最后一個(gè)結(jié)點(diǎn)需要知道終端結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)的地址，所以，帶尾指針的單循環(huán)鏈表不合適，而循環(huán)雙向鏈表滿足條件。 在具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并仍然有序的時(shí)間復(fù)雜度是（ ）。a o(1) b o(n) c

16、 o(n2) d o(nlog2n)【解答】b【分析】首先應(yīng)順序查找新結(jié)點(diǎn)在單鏈表中的位置。 對(duì)于n個(gè)元素組成的線性表，建立一個(gè)有序單鏈表的時(shí)間復(fù)雜度是（ ）。a o(1) b o(n) c o(n2) d o(nlog2n)【解答】c【分析】該算法需要將n個(gè)元素依次插入到有序單鏈表中，而插入每個(gè)元素需o(n)。 使用雙向鏈表存儲(chǔ)線性表，其優(yōu)點(diǎn)是可以（ ）。a 提高查找速度 b 更方便數(shù)據(jù)的插入和刪除c 節(jié)約存儲(chǔ)空間 d 很快回收存儲(chǔ)空間【解答】b【分析】在鏈表中一般只能進(jìn)行順序查找，所以，雙向鏈表并不能提高查找速度，因?yàn)殡p向鏈表中有兩個(gè)指針域，顯然不能節(jié)約存儲(chǔ)空間，對(duì)于動(dòng)態(tài)存儲(chǔ)分配，回收存儲(chǔ)

17、空間的速度是一樣的。由于雙向鏈表具有對(duì)稱性，所以，其插入和刪除操作更加方便。 在一個(gè)單鏈表中，已知q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的直接前驅(qū)，若在q和p之間插入s所指結(jié)點(diǎn)，則執(zhí)行（ ）操作。a s-next=p-next; p-next=s; b q-next=s; s-next=p; c p-next=s-next; s-next=p; d p-next=s; s-next=q;【解答】b【分析】注意此題是在q和p之間插入新結(jié)點(diǎn)，所以，不用考慮修改指針的順序。 在循環(huán)雙向鏈表的p所指結(jié)點(diǎn)后插入s所指結(jié)點(diǎn)的操作是（ ）。a p-next=s; s-prior=p; p-next-prior=s; s-n

18、ext=p-next; b p-next=s; p-next-prior=s; s-prior=p; s-next=p-next;c s-prior=p; s-next=p-next; p-next=s; p-next-prior=s;d s-prior=p; s-next=p-next; p-next-prior=s; p-next=s【解答】d【分析】在鏈表中，對(duì)指針的修改必須保持線性表的邏輯關(guān)系，否則，將違背線性表的邏輯特征，圖2-10給出備選答案c和d的圖解。3. 判斷題 線性表的邏輯順序和存儲(chǔ)順序總是一致的?！窘獯稹垮e(cuò)。順序表的邏輯順序和存儲(chǔ)順序一致，鏈表的邏輯順序和存儲(chǔ)順序不一定一

19、致。 線性表的順序存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈接存儲(chǔ)結(jié)構(gòu)。【解答】錯(cuò)。兩種存儲(chǔ)結(jié)構(gòu)各有優(yōu)缺點(diǎn)。 設(shè)p，q是指針，若p=q，則*p=*q。【解答】錯(cuò)。p=q只能表示p和q指向同一起始地址，而所指類型則不一定相同。 線性結(jié)構(gòu)的基本特征是：每個(gè)元素有且僅有一個(gè)直接前驅(qū)和一個(gè)直接后繼?！窘獯稹垮e(cuò)。每個(gè)元素最多只有一個(gè)直接前驅(qū)和一個(gè)直接后繼，第一個(gè)元素沒有前驅(qū)，最后一個(gè)元素沒有后繼。 在單鏈表中，要取得某個(gè)元素，只要知道該元素所在結(jié)點(diǎn)的地址即可，因此單鏈表是隨機(jī)存取結(jié)構(gòu)。【解答】錯(cuò)。要找到該結(jié)點(diǎn)的地址，必須從頭指針開始查找，所以單鏈表是順序存取結(jié)構(gòu)。4請(qǐng)說明順序表和單鏈表各有何優(yōu)缺點(diǎn)，并分析下列情況下，采用何種存儲(chǔ)結(jié)

20、構(gòu)更好些。 若線性表的總長(zhǎng)度基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快的速度存取線性表中的元素。 如果n個(gè)線性表同時(shí)并存，并且在處理過程中各表的長(zhǎng)度會(huì)動(dòng)態(tài)發(fā)生變化。 描述一個(gè)城市的設(shè)計(jì)和規(guī)劃?！窘獯稹宽樞虮淼膬?yōu)點(diǎn)： 無需為表示表中元素之間的邏輯關(guān)系而增加額外的存儲(chǔ)空間； 可以快速地存取表中任一位置的元素（即隨機(jī)存?。?。順序表的缺點(diǎn)： 插入和刪除操作需移動(dòng)大量元素； 表的容量難以確定； 造成存儲(chǔ)空間的“碎片”。單鏈表的優(yōu)點(diǎn)： 不必事先知道線性表的長(zhǎng)度； 插入和刪除元素時(shí)只需修改指針，不用移動(dòng)元素。單鏈表的缺點(diǎn)： 指針的結(jié)構(gòu)性開銷； 存取表中任意元素不方便，只能進(jìn)行順序存取。 應(yīng)選用順序存儲(chǔ)

21、結(jié)構(gòu)。因?yàn)轫樞虮硎请S機(jī)存取結(jié)構(gòu)，單鏈表是順序存取結(jié)構(gòu)。本題很少進(jìn)行插入和刪除操作，所以空間變化不大，且需要快速存取，所以應(yīng)選用順序存儲(chǔ)結(jié)構(gòu)。 應(yīng)選用鏈接存儲(chǔ)結(jié)構(gòu)。鏈表容易實(shí)現(xiàn)表容量的擴(kuò)充，適合表的長(zhǎng)度動(dòng)態(tài)發(fā)生變化。 應(yīng)選用鏈接存儲(chǔ)結(jié)構(gòu)。因?yàn)橐粋€(gè)城市的設(shè)計(jì)和規(guī)劃涉及活動(dòng)很多，需要經(jīng)常修改、擴(kuò)充和刪除各種信息，才能適應(yīng)不斷發(fā)展的需要。而順序表的插入、刪除的效率低，故不合適。5算法設(shè)計(jì)欣賞 設(shè)計(jì)一個(gè)時(shí)間復(fù)雜度為(n)的算法，實(shí)現(xiàn)將數(shù)組an中所有元素循環(huán)左移k個(gè)位置?！窘獯稹克惴ㄋ枷胝?qǐng)參見主教材第一章思想火花。下面給出具體算法。分析算法，第一次調(diào)用reverse函數(shù)的時(shí)間復(fù)雜度為o(k)，第二次調(diào)用r

22、everse函數(shù)的時(shí)間復(fù)雜度為o(n-k)，第三次調(diào)用reverse函數(shù)的時(shí)間復(fù)雜度為o(n)，所以，總的時(shí)間復(fù)雜度為o(n)。 已知數(shù)組an中的元素為整型，設(shè)計(jì)算法將其調(diào)整為左右兩部分，左邊所有元素為奇數(shù)，右邊所有元素為偶數(shù)，并要求算法的時(shí)間復(fù)雜度為(n)?！窘獯稹繌臄?shù)組的兩端向中間比較，設(shè)置兩個(gè)變量i和j，初始時(shí)i=0，j=n-1，若ai為偶數(shù)并且aj為奇數(shù)，則將ai與aj交換。具體算法如下：分析算法，兩層循環(huán)將數(shù)組掃描一遍，所以，時(shí)間復(fù)雜度為(n)。 試編寫在無頭結(jié)點(diǎn)的單鏈表上實(shí)現(xiàn)線性表的插入操作的算法，并和帶頭結(jié)點(diǎn)的單鏈表上的插入操作的實(shí)現(xiàn)進(jìn)行比較?！窘獯稹繀⒁?.2.3。 試分別以順

23、序表和單鏈表作存儲(chǔ)結(jié)構(gòu)，各寫一實(shí)現(xiàn)線性表就地逆置的算法?！窘獯稹宽樞虮淼哪嬷?，即是將對(duì)稱元素交換，設(shè)順序表的長(zhǎng)度為length，則將表中第i個(gè)元素與第length-i-1個(gè)元素相交換。具體算法如下：?jiǎn)捂湵淼哪嬷谜?qǐng)參見2.2.4算法2-4和算法2-6。 假設(shè)在長(zhǎng)度大于1的循環(huán)鏈表中，即無頭結(jié)點(diǎn)也無頭指針，s為指向鏈表中某個(gè)結(jié)點(diǎn)的指針，試編寫算法刪除結(jié)點(diǎn)s的前趨結(jié)點(diǎn)?！窘獯稹坷脝窝h(huán)鏈表的特點(diǎn)，通過指針s可找到其前驅(qū)結(jié)點(diǎn)r以及r的前驅(qū)結(jié)點(diǎn)p，然后將結(jié)點(diǎn)r刪除，如圖2-11所示，具體算法如下： 已知一單鏈表中的數(shù)據(jù)元素含有三類字符：字母、數(shù)字和其他字符。試編寫算法，構(gòu)造三個(gè)循環(huán)鏈表，使每個(gè)循環(huán)鏈表

24、中只含同一類字符?！窘獯稹吭趩捂湵韆中依次取元素，若取出的元素是字母，把它插入到字母鏈表b 中，若取出的元素是數(shù)字，則把它插入到數(shù)字鏈表d中，直到鏈表的尾部，這樣表b，d，a中分別存放字母、數(shù)字和其他字符。具體算法如下： 設(shè)單鏈表以非遞減有序排列，設(shè)計(jì)算法實(shí)現(xiàn)在單鏈表中刪去值相同的多余結(jié)點(diǎn)?！窘獯稹繌念^到尾掃描單鏈表，若當(dāng)前結(jié)點(diǎn)的元素值與后繼結(jié)點(diǎn)的元素值不相等，則指針后移；否則刪除該后繼結(jié)點(diǎn)。具體算法如下： 判斷帶頭結(jié)點(diǎn)的雙循環(huán)鏈表是否對(duì)稱?！窘獯稹吭O(shè)工作指針p和q分別指向循環(huán)雙向鏈表的開始結(jié)點(diǎn)和終端結(jié)點(diǎn)，若結(jié)點(diǎn)p和結(jié)點(diǎn)q的數(shù)據(jù)域相等，則工作指針p后移，工作指針q前移，直到指針p和指針q指向同

25、一結(jié)點(diǎn)（循環(huán)雙向鏈表中結(jié)點(diǎn)個(gè)數(shù)為奇數(shù)），或結(jié)點(diǎn)q成為結(jié)點(diǎn)p的前驅(qū)（循環(huán)雙向鏈表中結(jié)點(diǎn)個(gè)數(shù)為偶數(shù)）。如圖2-12所示。學(xué)習(xí)自測(cè)及答案 1. 已知一維數(shù)組a采用順序存儲(chǔ)結(jié)構(gòu)，每個(gè)元素占用4個(gè)存儲(chǔ)單元，第9個(gè)元素的地址為144，則第一個(gè)元素的地址是（ ）。a 108 b 180 c 176 d 112【解答】d2在長(zhǎng)度為n的線性表中查找值為x的數(shù)據(jù)元素的時(shí)間復(fù)雜度為： （ ）。 a o(0) b o(1) c o(n) d o(n2)【解答】c3在一個(gè)長(zhǎng)度為n的順序表的第i（1in+1）個(gè)元素之前插入一個(gè)元素，需向后移動(dòng)（ ）個(gè)元素，刪除第i（1in）個(gè)元素時(shí)，需向前移動(dòng)（ ）個(gè)元素?！窘獯稹縩-i

26、+1，n-i 4在單鏈表中，除了頭結(jié)點(diǎn)以外，任一結(jié)點(diǎn)的存儲(chǔ)位置由（ ）指示?！窘獯稹科淝摆吔Y(jié)點(diǎn)的指針域 5當(dāng)線性表采用順序存儲(chǔ)結(jié)構(gòu)時(shí)，其主要特點(diǎn)是（ ）?！窘獯稹窟壿嫿Y(jié)構(gòu)中相鄰的結(jié)點(diǎn)在存儲(chǔ)結(jié)構(gòu)中仍相鄰6在雙向鏈表中，每個(gè)結(jié)點(diǎn)設(shè)置了兩個(gè)指針域，其中一個(gè)指向（ ）結(jié)點(diǎn)，另一個(gè)指向（ ）結(jié)點(diǎn)?！窘獯稹壳膀?qū)，后繼7設(shè)a是一個(gè)線性表（a1, a2, , an），采用順序存儲(chǔ)結(jié)構(gòu)，則在等概率的前提下，平均每插入一個(gè)元素需要移動(dòng)的元素個(gè)數(shù)為多少？若元素插在ai與ai+1之間（1in）的概率為 ，則平均每插入一個(gè)元素所要移動(dòng)的元素個(gè)數(shù)又是多少？【解答】 ，。算法設(shè)計(jì)欣賞8線性表存放在整型數(shù)組aarrsize的

27、前elenum 個(gè)單元中，且遞增有序。編寫算法，將元素x插入到線性表的適當(dāng)位置上，以保持線性表的有序性，并且分析算法的時(shí)間復(fù)雜度?！窘獯稹勘绢}是在一個(gè)遞增有序表中插入元素x，基本思路是從有序表的尾部開始依次取元素與x比較，若大于x，此元素后移一位，再取它前面一個(gè)元素重復(fù)上述步驟；否則，找到插入位置，將x插入。具體算法如下：9. 已知單鏈表中各結(jié)點(diǎn)的元素值為整型且遞增有序，設(shè)計(jì)算法刪除鏈表中所有大于mink且小于maxk的所有元素，并釋放被刪結(jié)點(diǎn)的存儲(chǔ)空間?！窘獯稹恳?yàn)槭窃谟行騿捂湵砩系牟僮?，所以，要充分利用其有序性。在單鏈表中查找第一個(gè)大于mink的結(jié)點(diǎn)和第一個(gè)小于maxk的結(jié)點(diǎn)，再將二者間的

28、所有結(jié)點(diǎn)刪除。10設(shè)單循環(huán)鏈表l1，對(duì)其遍歷的結(jié)果是：x1, x2, x3, xn-1, xn。請(qǐng)將該循環(huán)鏈表拆成兩個(gè)單循環(huán)鏈表l1和l2，使得l1中含有原l1表中序號(hào)為奇數(shù)的結(jié)點(diǎn)且遍歷結(jié)果為：x1, x3, ；l2中含有原l1表中序號(hào)為偶數(shù)的結(jié)點(diǎn)且遍歷結(jié)果為： , x4, x2?！窘獯稹克惴ㄈ缦拢旱?章 棧、隊(duì)列1. 填空 （1） 設(shè)有一個(gè)空棧，棧頂指針為1000h，現(xiàn)有輸入序列為1、2、3、4、5， 經(jīng)過push，push，pop，push，pop，push，push后，輸出序列是（ ），棧頂指針為（ ）?！窘獯稹?3，1006h（2）棧通常采用的兩種存儲(chǔ)結(jié)構(gòu)是（ ）；其判定?？盏臈l件分別

29、是（ ），判定棧滿的條件分別是（ ）?！窘獯稹宽樞虼鎯?chǔ)結(jié)構(gòu)和鏈接存儲(chǔ)結(jié)構(gòu)（或順序棧和鏈棧），棧頂指針top= -1和top=null，棧頂指針top等于數(shù)組的長(zhǎng)度和內(nèi)存無可用空間（3）（ ）可作為實(shí)現(xiàn)遞歸函數(shù)調(diào)用的一種數(shù)據(jù)結(jié)構(gòu)?！窘獯稹織！痉治觥窟f歸函數(shù)的調(diào)用和返回正好符合后進(jìn)先出性。（4） 棧和隊(duì)列是兩種特殊的線性表，棧的操作特性是（ ），隊(duì)列的操作特性是（ ），棧和隊(duì)列的主要區(qū)別在于（ ）?！窘獯稹亢筮M(jìn)先出，先進(jìn)先出，對(duì)插入和刪除操作限定的位置不同（5）循環(huán)隊(duì)列的引入是為了克服（ ）?！窘獯稹考僖绯觯?） 數(shù)組qn用來表示一個(gè)循環(huán)隊(duì)列，front為隊(duì)頭元素的前一個(gè)位置，rear為隊(duì)尾元素的

30、位置，計(jì)算隊(duì)列中元素個(gè)數(shù)的公式為（ ）?！窘獯稹浚╮ear-front+n）% n【分析】也可以是（rear-front）% n，但rear-front的結(jié)果可能是負(fù)整數(shù)，而對(duì)一個(gè)負(fù)整數(shù)求模，其結(jié)果在不同的編譯器環(huán)境下可能會(huì)有所不同。2. 選擇題（1）若一個(gè)棧的輸入序列是1，2，3，n，輸出序列的第一個(gè)元素是n，則第i個(gè)輸出元素是（ ）。a 不確定 b n-i c n-i-1 d n-i+1【解答】d【分析】此時(shí)，輸出序列一定是輸入序列的逆序。（2） 設(shè)棧s和隊(duì)列q的初始狀態(tài)為空，元素e1、e2、e3、e4、e5、e6依次通過棧s，一個(gè)元素出棧后即進(jìn)入隊(duì)列q，若6個(gè)元素出隊(duì)的順序是e2、e4、

31、e3、e6、e5、e1，則棧s的容量至少應(yīng)該是（ ）。a 6 b 4 c 3 d 2【解答】c【分析】由于隊(duì)列具有先進(jìn)先出性，所以，此題中隊(duì)列形同虛設(shè)，即出棧的順序也是e2、e4、e3、e6、e5、e1。（3）一個(gè)棧的入棧序列是1，2，3，4，5，則棧的不可能的輸出序列是（ ）。a 54321 b 45321 c 43512 d 12345 【解答】c【分析】此題有一個(gè)技巧：在輸出序列中任意元素后面不能出現(xiàn)比該元素小并且是升序（指的是元素的序號(hào)）的兩個(gè)元素。（4）設(shè)計(jì)一個(gè)判別表達(dá)式中左右括號(hào)是否配對(duì)的算法，采用（ ）數(shù)據(jù)結(jié)構(gòu)最佳a(bǔ) 順序表 b 棧 c 隊(duì)列 d 鏈表【解答】b【分析】每個(gè)右括號(hào)

32、與它前面的最后一個(gè)沒有匹配的左括號(hào)配對(duì)，因此具有后進(jìn)先出性。（5）在解決計(jì)算機(jī)主機(jī)與打印機(jī)之間速度不匹配問題時(shí)通常設(shè)置一個(gè)打印緩沖區(qū)，該緩沖區(qū)應(yīng)該是一個(gè)（ ）結(jié)構(gòu)。a 棧 b隊(duì)列 c 數(shù)組 d線性表【解答】b【分析】先進(jìn)入打印緩沖區(qū)的文件先被打印，因此具有先進(jìn)先出性。（6）一個(gè)隊(duì)列的入隊(duì)順序是1，2，3，4，則隊(duì)列的輸出順序是（ ）。a 4321 b 1234 c 1432 d 3241【解答】b【分析】隊(duì)列的入隊(duì)順序和出隊(duì)順序總是一致的。（7） 棧和隊(duì)列的主要區(qū)別在于（ ）。a 它們的邏輯結(jié)構(gòu)不一樣 b 它們的存儲(chǔ)結(jié)構(gòu)不一樣c 所包含的運(yùn)算不一樣 d 插入、刪除運(yùn)算的限定不一樣【解答】d【分

33、析】棧和隊(duì)列的邏輯結(jié)構(gòu)都是線性的，都有順序存儲(chǔ)和鏈接存儲(chǔ)，有可能包含的運(yùn)算不一樣，但不是主要區(qū)別，任何數(shù)據(jù)結(jié)構(gòu)在針對(duì)具體問題時(shí)包含的運(yùn)算都可能不同。3. 判斷題（1）棧可以作為實(shí)現(xiàn)過程調(diào)用的一種數(shù)據(jù)結(jié)構(gòu)?！窘獯稹繉?duì)。只要操作滿足后進(jìn)先出性，都可以采用棧作為輔助數(shù)據(jù)結(jié)構(gòu)。（2） 在棧滿的情況下不能做進(jìn)棧操作，否則將產(chǎn)生“上溢”。【解答】對(duì)。（3）在循環(huán)隊(duì)列中，front指向隊(duì)頭元素的前一個(gè)位置，rear指向隊(duì)尾元素的位置，則隊(duì)滿的條件是front=rear?！窘獯稹垮e(cuò)。這是隊(duì)空的判定條件，在循環(huán)隊(duì)列中要將隊(duì)空和隊(duì)滿的判定條件區(qū)別開。4. 設(shè)有一個(gè)棧，元素進(jìn)棧的次序?yàn)閍，b，c，d，e，能否得到如

34、下出棧序列，若能，請(qǐng)寫出操作序列，若不能，請(qǐng)說明原因。 c，e，a，b，d c，b，a，d，e【解答】不能，因?yàn)樵赾、e出棧的情況下，a一定在棧中，而且在b的下面，不可能先于b出棧。可以，設(shè)為進(jìn)棧操作，為入棧操作，則其操作序列為iiioooioio。5. 舉例說明順序隊(duì)列的“假溢出”現(xiàn)象?！窘獯稹考僭O(shè)有一個(gè)順序隊(duì)列，如圖3-6所示，隊(duì)尾指針rear=4，隊(duì)頭指針front=1，如果再有元素入隊(duì)，就會(huì)產(chǎn)生“上溢”，此時(shí)的“上溢”又稱為“假溢出”，因?yàn)殛?duì)列并不是真的溢出了，存儲(chǔ)隊(duì)列的數(shù)組中還有2個(gè)存儲(chǔ)單元空閑，其下標(biāo)分別為0和1。6. 在操作序列push(1)、push(2)、pop、push(5

35、)、push(7)、pop、push(6)之后，棧頂元素和棧底元素分別是什么？（push(k)表示整數(shù)k入棧，pop表示棧頂元素出棧。）【解答】棧頂元素為6，棧底元素為1。其執(zhí)行過程如圖3-7所示。7 在操作序列enqueue(1)、 enqueue(3)、 dequeue、enqueue(5)、enqueue(7)、dequeue、enqueue(9)之后，隊(duì)頭元素和隊(duì)尾元素分別是什么？（enqueue(k)表示整數(shù)k入隊(duì)，dequeue表示隊(duì)頭元素出隊(duì)）?！窘獯稹筷?duì)頭元素為5，隊(duì)尾元素為9。其執(zhí)行過程如圖3-8所示。8. 算法設(shè)計(jì)（1） 假設(shè)以不帶頭結(jié)點(diǎn)的循環(huán)鏈表表示隊(duì)列，并且只設(shè)一個(gè)指針

36、指向隊(duì)尾結(jié)點(diǎn)，但不設(shè)頭指針。試設(shè)計(jì)相應(yīng)的入隊(duì)和出隊(duì)的算法?！窘獯稹砍鲫?duì)操作是在循環(huán)鏈表的頭部進(jìn)行，相當(dāng)于刪除開始結(jié)點(diǎn)，而入隊(duì)操作是在循環(huán)鏈表的尾部進(jìn)行，相當(dāng)于在終端結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)。由于循環(huán)鏈表不帶頭結(jié)點(diǎn)，需要處理空表的特殊情況。入隊(duì)算法如下：出隊(duì)算法如下：學(xué)習(xí)自測(cè)及答案 1在一個(gè)具有n個(gè)單元的順序棧中，假定以地址低端（即下標(biāo)為0的單元）作為棧底，以top作為棧頂指針，當(dāng)出棧時(shí)，top的變化為（ ）。a 不變 b top=0; c top=top-1; d top=top+1;【解答】c2一個(gè)棧的入棧序列是a, b, c, d, e，則棧的不可能的出棧序列是（ ）。a edcba b cd

37、eba c debca d abcde 【解答】c3從棧頂指針為top的鏈棧中刪除一個(gè)結(jié)點(diǎn)，用x保存被刪除結(jié)點(diǎn)的值，則執(zhí)行（ ）。a x=top; top=top-next; b x=top-data;c top=top-next; x=top-data; d x=top-data; top=top-next;【解答】d4對(duì)于棧和隊(duì)列，無論它們采用順序存儲(chǔ)結(jié)構(gòu)還是鏈接存儲(chǔ)結(jié)構(gòu)，進(jìn)行插入和刪除操作的時(shí)間復(fù)雜度都是（ ）?！窘獯稹?1)5如果進(jìn)棧序列為a、b、c、d，則可能的出棧序列是什么？答：共14種，分別是：abcd，abdc，acbd，acdb，adcb，bacd，badc，bcad，bcd

38、a，bdca，cbad，cbda，cdba，dcba6簡(jiǎn)述隊(duì)列和棧這兩種數(shù)據(jù)結(jié)構(gòu)的相同點(diǎn)和不同點(diǎn)?！窘獯稹肯嗤c(diǎn)：它們都是插入和刪除操作的位置受限制的線性表。不同點(diǎn)：棧是限定僅在表尾進(jìn)行插入和刪除的線性表，是后進(jìn)先出的線性表，而隊(duì)列是限定在表的一端進(jìn)行插入，在另一端進(jìn)行刪除的線性表，是先進(jìn)先出的線性表。7. 設(shè)計(jì)算法把一個(gè)十進(jìn)制整數(shù)轉(zhuǎn)換為二至九進(jìn)制之間的任一進(jìn)制數(shù)輸出?！窘獯稹克惴ɑ谠恚簄=(n div d)d + n mod d （div為整除運(yùn)算，mod為求余運(yùn)算）。8假設(shè)一個(gè)算術(shù)表達(dá)式中可以包含三種括號(hào)：圓括號(hào)“（”和“）”，方括號(hào)“”和“”以及花括號(hào)“”和“”，且這三種括號(hào)可按任意

39、的次序嵌套使用。編寫算法判斷給定表達(dá)式中所含括號(hào)是否配對(duì)出現(xiàn)?！窘獯稹考僭O(shè)表達(dá)式已存入字符數(shù)組an中，具體算法如下： 第4章 串 1. 填空 (1)串是一種特殊的線性表，其特殊性體現(xiàn)在（數(shù)據(jù)元素的類型是一個(gè)字符）。(2)兩個(gè)串相等的充分必要條件是（長(zhǎng)度相同且對(duì)應(yīng)位置的字符相等）。(3)空格串是指_(1)_，其長(zhǎng)度等于_(2)_。 (4)一個(gè)字符串中_稱為該串的子串 。 (5)index（datastructure， str）=_5_。(6)設(shè)正文串長(zhǎng)度為n，模式串長(zhǎng)度為m，則串匹配的kmp算法的時(shí)間復(fù)雜度為_o(n+m)_。 (7)設(shè)t和p是兩個(gè)給定的串，在t中尋找等于p的子串的過程稱為_，又

40、稱p為_。(8)已知u=xyxyxyxxyxy；t=xxy；assign（s，u）；assign（v，substr（s，index（s，t），len（t）+1）；assign（m，ww）求replace（s，v，m）= _xyxyxywwy_。 (9)實(shí)現(xiàn)字符串拷貝的函數(shù) strcpy為： void strcpy(char *s , char *t) /*copy t to s*/ while (_*s+=*t+_); (10)下列程序判斷字符串s 是否對(duì)稱，對(duì)稱則返回1，否則返回0；如 f(abba)返回1，f(abab)返回0； int f(1)_char s_) int i=0,j=0;

41、 while (sj)(2)_j+_; for(j-; i=j_) (11)設(shè)s=i_ am_ a_ teacther，其長(zhǎng)度為（ 15）。2. 選擇題(1) 設(shè)有兩個(gè)串p和q，求q在p中首次出現(xiàn)的位置的運(yùn)算稱作（b ）。a 連接 b 模式匹配 c 求子串 d 求串長(zhǎng)(2)下面關(guān)于串的的敘述中，哪一個(gè)是不正確的？（b ）a串是字符的有限序列 b空串是由空格構(gòu)成的串c模式匹配是串的一種重要運(yùn)算 d串既可以采用順序存儲(chǔ)，也可以采用鏈?zhǔn)酱鎯?chǔ) (3)若串s1=abcdefg, s2=9898 ,s3=#,s4=012345,執(zhí)行concat(replace(s1,substr(s1,length(s2

42、),length(s3),s3),substr(s4,index(s2,8),length(s2)其結(jié)果為（ e ）aabc#g0123 babcd#2345 cabc#g2345 dabc#2345eabc#g1234 fabcd#1234 gabc#01234 (4)設(shè)有兩個(gè)串p和q，其中q是p的子串，求q在p中首次出現(xiàn)的位置的算法稱為（ c ）a求子串 b聯(lián)接 c匹配 d求串長(zhǎng) (5)若串s=software,其子串的數(shù)目是（ b ）。a8 b37 c36 d9 (6)設(shè)s為一個(gè)長(zhǎng)度為n的字符串，其中的字符各不相同，則s中的互異的非平凡子串（非空且不同于s本身）的個(gè)數(shù)為（ d ）。a2n

43、-1 bn2 c(n2/2)+(n/2) d(n2/2)+(n/2)-1 e. (n2/2)-(n/2)-1 f.其他情況 (7)串的長(zhǎng)度是指（ b ）a串中所含不同字母的個(gè)數(shù) b串中所含字符的個(gè)數(shù)c串中所含不同字符的個(gè)數(shù) d串中所含非空格字符的個(gè)數(shù)3. 判斷題(1) 空串與空格串是相同的。【解答】錯(cuò)?？沾拈L(zhǎng)度為零，而空格串的長(zhǎng)度不為0，其長(zhǎng)度是串中空格的個(gè)數(shù)。4空串和空格串有何區(qū)別？串中的空格符有何意義？空串在串處理中有何作用？【解答】不含任何字符的串稱為空串，其長(zhǎng)度為零。僅含空格的串稱為空格串，它的長(zhǎng)度為串中空格符的個(gè)數(shù)。串中的空格符可用來分隔一般的字符，便于人們識(shí)別和閱讀，但計(jì)算串長(zhǎng)時(shí)

44、應(yīng)包括這些空格符?？沾诖幚碇锌勺鳛槿我獯淖哟?。5. 算法設(shè)計(jì)：（1）用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)串s，編寫算法刪除s中第 i個(gè)字符開始的連續(xù)j個(gè)字符?！窘獯稹肯扰袛啻畇中要?jiǎng)h除的內(nèi)容是否存在，若存在，則將第i+j-1之后的字符前移j個(gè)位置。算法如下：void del(char s,int i,int j)if (i+js0) for(k=i;k+j=s0;k+)sk=ss+j;s0=s0-1（2）對(duì)于采用順序存儲(chǔ)結(jié)構(gòu)的串s，編寫一個(gè)函數(shù)刪除其值等于ch的所有字符?！窘獯稹繌暮笙蚯皠h除值為ch的所有元素，這樣所有移動(dòng)的元素中沒有值為ch的元素，能減少移動(dòng)元素的次數(shù)，提高算法的效率。算法如下：void

45、 del(char s,char ch) for(i=1,j=1;j0）個(gè)結(jié)點(diǎn)的滿二叉樹共有（ ）個(gè)葉子結(jié)點(diǎn)和（ ）個(gè)非終端結(jié)點(diǎn)?！窘獯稹?i-1，(n+1)/2，(n-1)/2【分析】設(shè)滿二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù)為n0，度為2的結(jié)點(diǎn)個(gè)數(shù)為n2，由于滿二叉樹中不存在度為1的結(jié)點(diǎn)，所以n=n0+n2；由二叉樹的性質(zhì)n0=n2+1，得n0=(n+1)/2，n2=(n-1)/2。 設(shè)高度為h的二叉樹上只有度為0和度為2的結(jié)點(diǎn)，該二叉樹的結(jié)點(diǎn)數(shù)可能達(dá)到的最大值是（ ），最小值是（ ）?！窘獯稹?h -1，2h-1【分析】最小結(jié)點(diǎn)個(gè)數(shù)的情況是第1層有1個(gè)結(jié)點(diǎn)，其他層上都只有2個(gè)結(jié)點(diǎn)。(5) 具有100個(gè)結(jié)

46、點(diǎn)的完全二叉樹的葉子結(jié)點(diǎn)數(shù)為（ ）。【解答】50【分析】100個(gè)結(jié)點(diǎn)的完全二叉樹中最后一個(gè)結(jié)點(diǎn)的編號(hào)為100，其雙親即最后一個(gè)分支結(jié)點(diǎn)的編號(hào)為50，也就是說，從編號(hào)51開始均為葉子。已知一棵度為3的樹有2個(gè)度為1的結(jié)點(diǎn)，3個(gè)度為2的結(jié)點(diǎn)，4個(gè)度為3的結(jié)點(diǎn)。則該樹中有（ ）個(gè)葉子結(jié)點(diǎn)?！窘獯稹?2【分析】根據(jù)二叉樹性質(zhì)3的證明過程，有n0=n2+2n3+1（n0、n2、n3分別為葉子結(jié)點(diǎn)、度為2的結(jié)點(diǎn)和度為3的結(jié)點(diǎn)的個(gè)數(shù)）。某二叉樹的前序遍歷序列是abcdefg，中序遍歷序列是cbdafge，則其后序遍歷序列是（ ）。【解答】cdbgfea【分析】根據(jù)前序遍歷序列和后序遍歷序列將該二叉樹構(gòu)造出來

47、。 在具有n個(gè)結(jié)點(diǎn)的二叉鏈表中，共有（ ）個(gè)指針域，其中（ ）個(gè)指針域用于指向其左右孩子，剩下的（ ）個(gè)指針域則是空的?！窘獯稹?n，n-1，n+1在有n個(gè)葉子的哈夫曼樹中，葉子結(jié)點(diǎn)總數(shù)為（ ），分支結(jié)點(diǎn)總數(shù)為（ ）?！窘獯稹縩，n-1【分析】n-1個(gè)分支結(jié)點(diǎn)是經(jīng)過n-1次合并后得到的。2. 選擇題 如果結(jié)點(diǎn)a有3個(gè)兄弟，b是a的雙親，則結(jié)點(diǎn)b的度是（）。a 1 b 2 c 3 d 4【解答】d 設(shè)二叉樹有n個(gè)結(jié)點(diǎn)，則其深度為（ ）。a n-1 b n c +1 d 不能確定【解答】d【分析】此題并沒有指明是完全二叉樹，則其深度最多是n，最少是 +1。 二叉樹的前序序列和后序序列正好相反，則該

48、二叉樹一定是（ ）的二叉樹。a 空或只有一個(gè)結(jié)點(diǎn) b 高度等于其結(jié)點(diǎn)數(shù)c 任一結(jié)點(diǎn)無左孩子 d 任一結(jié)點(diǎn)無右孩子【解答】b【分析】此題注意是序列正好相反，則左斜樹和右斜樹均滿足條件。(4) 深度為k的完全二叉樹至少有（ ）個(gè)結(jié)點(diǎn)，至多有（ ）個(gè)結(jié)點(diǎn)，具有n個(gè)結(jié)點(diǎn)的完全二叉樹按層序從1開始編號(hào)，則編號(hào)最小的葉子的序號(hào)是（ ）。a 2k-2+1 b 2k-1 c 2k -1 d 2k1 -1 e 2k+1 f 2k+1 -1 g 2k -1+1 h 2k【解答】b，c，a【分析】深度為k的完全二叉樹最少結(jié)點(diǎn)數(shù)的情況應(yīng)是第k層上只有1個(gè)結(jié)點(diǎn)，最多的情況是滿二叉樹，編號(hào)最小的葉子應(yīng)該是在結(jié)點(diǎn)數(shù)最少的情

49、況下，葉子結(jié)點(diǎn)的編號(hào)。 一個(gè)高度為h的滿二叉樹共有n個(gè)結(jié)點(diǎn)，其中有m個(gè)葉子結(jié)點(diǎn)，則有（ ）成立。a n=h+m b h+m=2n c m=h-1 d n=2m-1【解答】d【分析】滿二叉樹中沒有度為1的結(jié)點(diǎn)，所以有m個(gè)葉子結(jié)點(diǎn)，則度為2的結(jié)點(diǎn)個(gè)數(shù)為m-1。任何一棵二叉樹的葉子結(jié)點(diǎn)在前序、中序、后序遍歷序列中的相對(duì)次序（ ）。a 肯定不發(fā)生改變 b 肯定發(fā)生改變 c 不能確定 d 有時(shí)發(fā)生變化【解答】a【分析】三種遍歷次序均是先左子樹后右子樹。設(shè)森林中有4棵樹，樹中結(jié)點(diǎn)的個(gè)數(shù)依次為n1、n2、n3、n4，則把森林轉(zhuǎn)換成二叉樹后，其根結(jié)點(diǎn)的右子樹上有（ ）個(gè)結(jié)點(diǎn)，根結(jié)點(diǎn)的左子樹上有（ ）個(gè)結(jié)點(diǎn)。a

50、 n1-1 b n1 c n1+n2+n3 d n2+n3+n4【解答】d，a【分析】由森林轉(zhuǎn)換的二叉樹中，根結(jié)點(diǎn)即為第一棵樹的根結(jié)點(diǎn)，根結(jié)點(diǎn)的左子樹是由第一棵樹中除了根結(jié)點(diǎn)以外其余結(jié)點(diǎn)組成的，根結(jié)點(diǎn)的右子樹是由森林中除第一棵樹外其他樹轉(zhuǎn)換來的。(8) 討論樹、森林和二叉樹的關(guān)系，目的是為了（ ）。a 借助二叉樹上的運(yùn)算方法去實(shí)現(xiàn)對(duì)樹的一些運(yùn)算b 將樹、森林按二叉樹的存儲(chǔ)方式進(jìn)行存儲(chǔ)并利用二叉樹的算法解決樹的有關(guān)問題c 將樹、森林轉(zhuǎn)換成二叉樹d 體現(xiàn)一種技巧，沒有什么實(shí)際意義【解答】b3. 判斷題(1) 在二叉樹的前序遍歷序列中，任意一個(gè)結(jié)點(diǎn)均處在其子女的前面?！窘獯稹繉?duì)。由前序遍歷的操作定義

51、可知。(2) 二叉樹是度為2的樹。【解答】錯(cuò)。二叉樹和樹是兩種不同的樹結(jié)構(gòu)，例如，左斜樹是一棵二叉樹，但它的度為1。(3) 由樹轉(zhuǎn)換成二叉樹，其根結(jié)點(diǎn)的右子樹總是空的?！窘獯稹繉?duì)。因?yàn)楦Y(jié)點(diǎn)無兄弟結(jié)點(diǎn)。(4) 用一維數(shù)組存儲(chǔ)二叉樹時(shí)，總是以前序遍歷存儲(chǔ)結(jié)點(diǎn)?！窘獯稹垮e(cuò)。二叉樹的順序存儲(chǔ)結(jié)構(gòu)是按層序存儲(chǔ)的，一般適合存儲(chǔ)完全二叉樹。4證明：對(duì)任一滿二叉樹，其分枝數(shù)b2(n0-1) 。（其中，n0為終端結(jié)點(diǎn)數(shù)）【解答】因?yàn)樵跐M二叉樹中沒有度為1的結(jié)點(diǎn)，所以有：n=n0+n2 設(shè)b為樹中分枝數(shù)，則n=b+1所以b=n0 +n2-1再由二叉樹性質(zhì)：n0=n2+1代入上式有：b=n0+n0-1-1=2(n0-1)5已知一棵度為m的樹中有：n1個(gè)度為1的結(jié)點(diǎn)，n2個(gè)度為2的結(jié)點(diǎn)，nm個(gè)度為m的結(jié)點(diǎn)，問該樹中共有多少個(gè)葉子結(jié)點(diǎn)？ 【解答】設(shè)該樹的總結(jié)點(diǎn)數(shù)為n，則n=n0+n1+n2+nm 又：n=分枝數(shù)+1=0n0+1n1+2n2+mnm+1由上述兩式可得：n0= n2+2n3+(m-1)nm+16已知二叉樹的中序和后序序列分別為cbedafigh和cedbifhga，試構(gòu)造該二叉樹?！窘獯稹慷鏄涞臉?gòu)造過程如圖5-12 所示。7對(duì)給定的一組權(quán)值w（5，2，