第一篇：數(shù)據(jù)結(jié)構(gòu)查找習(xí)題及答案

第9章查找

一、單選題

1.對(duì)一棵二叉搜索樹按（）遍歷，可得到結(jié)點(diǎn)值從小到大的排列序列。

A.先序 B.中序

C.后序

D.層次

2.從具有n個(gè)結(jié)點(diǎn)的二叉搜索樹中查找一個(gè)元素時(shí)，在平均情況下的時(shí)間復(fù)雜度大致為（）。

A.O(n)

B.O(1)

C.O(logn)

D.O(n2)3.從具有n個(gè)結(jié)點(diǎn)的二叉搜索樹中查找一個(gè)元素時(shí)，在最壞情況下的時(shí)間復(fù)雜度為（）。

A.O(n)

B.O(1)

C.O(logn)

D.O(n2)4.在二叉搜索樹中插入一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度為（）。

A.O(1)B.O(n)

C.O(logn)

D.O(n2)5.分別以下列序列構(gòu)造二叉搜索樹，與用其它三個(gè)序列所構(gòu)造的結(jié)果不同的是（）。

A．（100，80，90，60，120，110，130）B.（100，120，110，130，80，60，90）C.（100，60，80，90，120，110，130）D.（100，80，60，90，120，130，110）

6.在一棵AVL樹中，每個(gè)結(jié)點(diǎn)的平衡因子的取值范圍是（）。

A.-1?1 B.-2?2 C.1?2

D.0?1 7.根據(jù)一組關(guān)鍵字（56，42，50，64，48）依次插入結(jié)點(diǎn)生成一棵AVL樹，當(dāng)插入到值為（）的結(jié)點(diǎn)時(shí)需要進(jìn)行旋轉(zhuǎn)調(diào)整。A.42 B.50

C.64

D.48 8.深度為4的AVL樹至少有（）個(gè)結(jié)點(diǎn)。

A．9 B.8

C.7

D.6 9.一棵深度為k的AVL樹，其每個(gè)分支結(jié)點(diǎn)的平衡因子均為0，則該平衡二叉樹共有（）個(gè)結(jié)點(diǎn)。A.2k-1-1 B.2k-1+1

C.2k-1

D.2k

10.在AVL樹中插入一個(gè)結(jié)點(diǎn)后造成了不平衡，設(shè)最低的不平衡結(jié)點(diǎn)為A，并已知A的左孩子的平衡因子為0，右孩子的平衡因子為1，則應(yīng)作（）型調(diào)整以使其平衡。A.LL

B.LR

C.RL

D.RR

二、判斷題 1.二叉搜索樹的任意一棵子樹中，關(guān)鍵字最小的結(jié)點(diǎn)必?zé)o左孩子，關(guān)鍵字最大的結(jié)點(diǎn)必?zé)o右孩子。

2.二叉搜索樹中每個(gè)結(jié)點(diǎn)的關(guān)鍵字值大于其左非空子樹（若存在的話）所有結(jié)點(diǎn)的關(guān)鍵字值，且小于其右非空子樹（若存在的話）所有結(jié)點(diǎn)的關(guān)鍵字值。

3.二叉搜索樹按照中序遍歷將各結(jié)點(diǎn)打印出將各結(jié)點(diǎn)打印出來，將得到按照由小到大的排列。

4.若二叉搜索樹的根結(jié)點(diǎn)沒有左兒子，則根結(jié)點(diǎn)一定是值最小的結(jié)點(diǎn)。5.二叉搜索樹一定是滿二叉樹。

6.從二叉搜索樹的根結(jié)點(diǎn)一直沿右兒子向下找不一定能找到樹中值最大的結(jié)點(diǎn)。7.二叉搜索樹的充要條件是任一結(jié)點(diǎn)的值均大于其左孩子的值，小于其右孩子的值。8.若二叉搜索樹中關(guān)鍵碼互不相同，則其中最小元素和最大元素一定是葉子結(jié)點(diǎn)。9.在任意一棵非空二叉搜索樹中，刪除某結(jié)點(diǎn)后又將其插入，則所得二叉搜索樹與原二叉搜索樹相同。

10.當(dāng)向二叉搜索樹中插入一個(gè)結(jié)點(diǎn)，則該結(jié)點(diǎn)一定成為葉子結(jié)點(diǎn)。11.AVL樹是指左右子樹的高度差的絕對(duì)值不大于1的二叉樹。12.AVL是一棵二叉樹，其樹上任一結(jié)點(diǎn)的平衡因子的絕對(duì)值不大于1。

13.在AVL樹中，向某個(gè)平衡因子不為零的結(jié)點(diǎn)的樹中插入一新結(jié)點(diǎn)，必引起平衡旋轉(zhuǎn)。

三、填空題

1.在一棵二叉搜索樹上實(shí)施遍歷后，其關(guān)鍵字序列是一個(gè)有序表。

2.一個(gè)無序序列可以通過構(gòu)造一棵_______而變成一個(gè)有序序列，構(gòu)造樹的過程即為對(duì)無序序列進(jìn)行排序的過程。

3.在一棵二叉搜索樹中，每個(gè)分支結(jié)點(diǎn)的左子樹上所有結(jié)點(diǎn)的值一定________該結(jié)點(diǎn)的值，右子樹上所有結(jié)點(diǎn)的值一定________該結(jié)點(diǎn)。

4.從一棵二叉搜索樹中查找一個(gè)元素時(shí)，若元素的值等于根結(jié)點(diǎn)的值，則表明_______，若元素的值小于根結(jié)點(diǎn)的值，則繼續(xù)向_______查找，若元素的值大于根結(jié)點(diǎn)的值，則繼續(xù)向________查找。

5.向一棵二叉搜索樹中插入一個(gè)元素時(shí)，若元素的值小于根結(jié)點(diǎn)的值，則接著向根結(jié)點(diǎn)的________插入，若元素的值大于根結(jié)點(diǎn)的值，則接著向根結(jié)點(diǎn)的________插入。6.根據(jù)n個(gè)元素建立一棵二叉搜索樹的時(shí)間復(fù)雜度大致為________。7.二叉樹中某一結(jié)點(diǎn)左子樹的深度減去右子樹的深度稱為該結(jié)點(diǎn)的_______。8.深度為4的平衡二叉樹中至少有個(gè)結(jié)點(diǎn)，至多有個(gè)結(jié)點(diǎn)。

9.在一棵AVL樹中，每個(gè)結(jié)點(diǎn)的左子樹高度與右子樹高度之差的絕對(duì)值不超過________。

四、應(yīng)用題

1.一棵二叉搜索樹的結(jié)構(gòu)如下圖所示，結(jié)點(diǎn)的值為1～8，請(qǐng)標(biāo)出各結(jié)點(diǎn)的值。

2.若依次輸入序列{62,68,30,61,25,14,53,47,90,84}中的元素，生成一棵二叉搜索樹。畫出生成后的二叉搜索樹（畫出生成過程）。

3.依次讀入給定的整數(shù)序列{7,16,4,8,20,9,6,18,5}，構(gòu)造一棵二叉搜索樹,并計(jì)算在等概率情況下該二叉搜索樹的平均查找長(zhǎng)度ASL。（要求給出構(gòu)造過程）

4.從空二叉樹開始，嚴(yán)格按照二叉搜索樹的插入算法（不進(jìn)行平衡旋轉(zhuǎn)），逐個(gè)插入關(guān)鍵碼{18,73,10,5,68,99,27,41,51,32,25}構(gòu)造出一棵二叉搜索樹，畫出這棵二叉搜索樹并寫出其前序、后序遍歷序列。

5.若一棵二叉搜索樹的關(guān)鍵字輸入序列為{80，6，10，7，8，25，100，90}，請(qǐng)畫出該二叉搜索樹。

6.設(shè)有一組初始記錄關(guān)鍵字為(45，80，48，40，22，78)，要求構(gòu)造一棵二叉搜索樹并給出構(gòu)造過程。

7.假定一個(gè)關(guān)鍵字序列為(38,52,25,74,68,16,30,54,90,72)，畫出按序列中元素的次序生成的一棵二叉搜索樹，求出其平均查找長(zhǎng)度。

8.將數(shù)列（24，15，38，27，121，76，130）的各元素依次插入一棵初始為空的二叉搜索樹中，請(qǐng)畫出最后的結(jié)果并求等概率情況下查找成功的平均查找長(zhǎng)度。

9.輸入一個(gè)正整數(shù)序列{40,28,6,72,100,3,54,1,80,91,38}，建立一棵二叉搜索樹，然后刪除結(jié)點(diǎn)72，分別畫出該二叉樹及刪除結(jié)點(diǎn)72后的二叉樹。

10.根據(jù)元素插入的先后次序不同，可構(gòu)成多種形態(tài)的二叉搜索樹。請(qǐng)畫出4棵含1，2，3，4四個(gè)元素且以1為根、深度為3的二叉搜索樹。11.請(qǐng)畫出從下面的二叉搜索樹中刪除關(guān)鍵碼40后的結(jié)果。

***604050

12.對(duì)關(guān)鍵字序列（25, 16, 34, 39, 28, 56），1）畫出按此序列生成的二叉搜索樹。2）計(jì)算等概率下查找成功時(shí)的平均查找長(zhǎng)度。

13.輸入一個(gè)正整數(shù)序列（53,17,12,66,58,70,87,25,56,60），試完成下列各題。

(1)按次序構(gòu)造一棵二叉搜索樹BS。

(2)依此二叉搜索樹，如何得到一個(gè)從大到小的有序序列？

(3)假定每個(gè)元素的查找概率相等，試計(jì)算該二叉搜索樹的平均查找長(zhǎng)度(4)畫出在此二叉搜索樹中刪除“66”后的樹結(jié)構(gòu)。

14.試推導(dǎo)深度為5的平衡二叉樹最少包含多少個(gè)結(jié)點(diǎn)，并畫出一棵這樣的樹。

15.畫出在一個(gè)初始為空的AVL樹中依次插入3,1,4,6,9,8,5,7時(shí)每一插入后AVL樹的形態(tài)。若做了某種旋轉(zhuǎn)，說明旋轉(zhuǎn)的類型。

16.給定一個(gè)關(guān)鍵字序列4,5,7,2,1,3,6，生成一棵AVL樹，畫出構(gòu)造過程。

17.給定關(guān)鍵字序列4,5,7,2,1,3,6，分別生成二叉搜索樹和AVL樹，并用二叉搜索樹和AVL樹兩種方法查找，給出查找6的查找次數(shù)及查找成功的平均查找長(zhǎng)度。

18.給定關(guān)鍵詞輸入序列{CAP, AQU, PIS, ARI, TAU, GEM, CAN, LIB, VIR, LEO, SCO}，假定關(guān)鍵詞比較按英文字典序，試畫出從一棵空樹開始，依上述順序（從左到右）輸入關(guān)鍵詞，用AVL樹的插入算法生成一棵AVL樹的過程，并說明生成過程中采用了何種轉(zhuǎn)動(dòng)方式進(jìn)行平衡調(diào)整，標(biāo)出樹中各結(jié)點(diǎn)的平衡因子。

參考答案

一、6-10.ABCCC 1-5.BCABC

二、6-10.××××√ 11-13.√√× 1-5.√√√√×

三、1.2.3.4.5.6.7.8.9.四、1.中序

二叉搜索樹 小于，大于

查找成功，左子樹，右子樹 左子樹，右子樹 O(n2)平衡因子 7, 15 1

2.3.ASL=(1+2*2+3*3+4*3)/9 = 26/9 = 2.89 4.前序：18 10 5 73 68 27 25 41 32 51 99 后序：5 10 25 32 51 41 27 68 99 73 18 5.6.7.二叉搜索樹如圖所示，平均查找長(zhǎng)度等于32/10。

8.平均查找長(zhǎng)度=1+2×2+3×2+4×2=19/7。

9.二叉搜索樹

刪除72后的二叉搜索樹

10.11.或12.（1）

（2）(1+2*2+3*2+4*1)/6 = 2.5

13.（1）構(gòu)造的二叉搜索樹為：（4）刪除結(jié)點(diǎn)66后

(2)對(duì)于一個(gè)二叉搜索樹，想得到一個(gè)從大到小的序列只要先讀右子樹再讀根結(jié)點(diǎn)，最后讀左子樹的遍歷這顆二叉樹就可以了。如果是要從小到大的序列，則只需中序遍歷這顆二叉樹即可。

(3)該二叉樹的平均查找長(zhǎng)度為：ASL=（1*1+2*2+3*4+4*3）/10=2.9 14.略 15.16.17.二叉搜索樹

AVL樹

從二叉搜索樹查找6需4次，平均查找長(zhǎng)度ASL=(1+2+2+3+3+3+4)/7=18/7≈2.57。從平衡二叉樹查找6需2次，平均查找長(zhǎng)度ASL=(1+2+2+3+3+3+3)=17/7≈2.43。18.單向左旋 先右旋后左旋

第二篇：數(shù)據(jù)結(jié)構(gòu)習(xí)題與答案

第 1 章 緒 論

課后習(xí)題講解

1.填空

⑴（）是數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理?！窘獯稹繑?shù)據(jù)元素

⑵（）是數(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)系。

⑶ 從邏輯關(guān)系上講，數(shù)據(jù)結(jié)構(gòu)主要分為（）、（）、（）和（）。【解答】集合，線性結(jié)構(gòu)，樹結(jié)構(gòu)，圖結(jié)構(gòu)

⑷ 數(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)系

⑸ 算法具有五個(gè)特性，分別是（）、（）、（）、（）、（）?！窘獯稹坑辛銈€(gè)或多個(gè)輸入，有一個(gè)或多個(gè)輸出，有窮性，確定性，可行性

⑹ 算法的描述方法通常有（）、（）、（）和（）四種，其中，（）被稱為算法語言?！窘獯稹孔匀徽Z言，程序設(shè)計(jì)語言，流程圖，偽代碼，偽代碼

⑺ 在一般情況下，一個(gè)算法的時(shí)間復(fù)雜度是（）的函數(shù)。【解答】問題規(guī)模

⑻ 設(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 指針 【解答】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ù)據(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.判斷題

⑴ 算法的時(shí)間復(fù)雜度都要通過算法中的基本語句的執(zhí)行次數(shù)來確定?！窘獯稹垮e(cuò)。時(shí)間復(fù)雜度要通過算法中基本語句執(zhí)行次數(shù)的數(shù)量級(jí)來確定。⑵ 每種數(shù)據(jù)結(jié)構(gòu)都具備三個(gè)基本操作：插入、刪除和查找。

【解答】錯(cuò)。如數(shù)組就沒有插入和刪除操作。此題注意是每種數(shù)據(jù)結(jié)構(gòu)。

⑶ 所謂數(shù)據(jù)的邏輯結(jié)構(gòu)指的是數(shù)據(jù)之間的邏輯關(guān)系?！窘獯稹垮e(cuò)。是數(shù)據(jù)之間的邏輯關(guān)系的整體。

⑷ 邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無關(guān)。【解答】對(duì)。因此邏輯結(jié)構(gòu)是數(shù)據(jù)組織的主要方面。⑸ 基于某種邏輯結(jié)構(gòu)之上的基本操作，其實(shí)現(xiàn)是唯一的。

【解答】錯(cuò)。基本操作的實(shí)現(xiàn)是基于某種存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)的，因而不是唯一的。4.分析以下各程序段，并用大O記號(hào)表示其執(zhí)行時(shí)間。

【解答】⑴ 基本語句是k=k+10*i，共執(zhí)行了n-2次，所以T(n)=O(n)。

⑵ 基本語句是k=k+10*i，共執(zhí)行了n次，所以T(n)=O(n)。

⑶ 分析條件語句，每循環(huán)一次，i+j 整體加1，共循環(huán)n次，所以T(n)=O(n)。

⑷ 設(shè)循環(huán)體共執(zhí)行T(n)次，每循環(huán)一次，循環(huán)變量y加1，最終T(n)=y，即：

(T(n)+1)2≤n，所以T(n)=O(n1/2)。

⑸ x++是基本語句，所以

5．設(shè)有數(shù)據(jù)結(jié)構(gòu)（D，R），其中D={1, 2, 3, 4, 5, 6}，R={(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)}。試畫出其邏輯結(jié)構(gòu)圖并指出屬于何種結(jié)構(gòu)。

【解答】其邏輯結(jié)構(gòu)圖如圖1-3所示，它是一種圖結(jié)構(gòu)。

6.為整數(shù)定義一個(gè)抽象數(shù)據(jù)類型，包含整數(shù)的常見運(yùn)算，每個(gè)運(yùn)算對(duì)應(yīng)一個(gè)基本操作，每個(gè)基本操作的接口需定義前置條件、輸入、功能、輸出和后置條件?！窘獯稹空麛?shù)的抽象數(shù)據(jù)類型定義如下：

ADT integer Data 整數(shù)a：可以是正整數(shù)(1, 2, 3, …)、負(fù)整數(shù)(-1,-2,-3, …)和零 Operation Constructor

前置條件：整數(shù)a不存在輸入：一個(gè)整數(shù)b

功能：構(gòu)造一個(gè)與輸入值相同的整數(shù) 輸出：無

后置條件：整數(shù)a具有輸入的值

Set 前置條件：存在一個(gè)整數(shù)a 輸入：一個(gè)整數(shù)b

功能：修改整數(shù)a的值，使之與輸入的整數(shù)值相同

輸出：無

后置條件：整數(shù)a的值發(fā)生改變

Add

前置條件：存在一個(gè)整數(shù)a 輸入：一個(gè)整數(shù)b

功能：將整數(shù)a與輸入的整數(shù)b相加

輸出：相加后的結(jié)果

后置條件：整數(shù)a的值發(fā)生改變

Sub

前置條件：存在一個(gè)整數(shù)a 輸入：一個(gè)整數(shù)b

功能：將整數(shù)a與輸入的整數(shù)b相減

輸出：相減的結(jié)果

后置條件：整數(shù)a的值發(fā)生改變

Multi

前置條件：存在一個(gè)整數(shù)a 輸入：一個(gè)整數(shù)b

功能：將整數(shù)a與輸入的整數(shù)b相乘

輸出：相乘的結(jié)果

后置條件：整數(shù)a的值發(fā)生改變 Div

前置條件：存在一個(gè)整數(shù)a 輸入：一個(gè)整數(shù)b

功能：將整數(shù)a與輸入的整數(shù)b相除

輸出：若整數(shù)b為零，則拋出除零異常，否則輸出相除的結(jié)果

后置條件：整數(shù)a的值發(fā)生改變

Mod

前置條件：存在一個(gè)整數(shù)a 輸入：一個(gè)整數(shù)b

功能：求當(dāng)前整數(shù)與輸入整數(shù)的模，即正的余數(shù)

輸出：若整數(shù)b為零，則拋出除零異常，否則輸出取模的結(jié)果

后置條件：整數(shù)a的值發(fā)生改變 Equal

前置條件：存在一個(gè)整數(shù)a 輸入：一個(gè)整數(shù)b

功能：判斷整數(shù)a與輸入的整數(shù)b是否相等

輸出：若相等返回1，否則返回0 后置條件：整數(shù)a的值不發(fā)生改變

endADT

7.求多項(xiàng)式A(x)的算法可根據(jù)下列兩個(gè)公式之一來設(shè)計(jì)：

⑴ A(x)=anxn+an-1xn-1+…+a1x+a0 ⑵ A(x)=(…(anx+an-1)x+…+a1)x)+a0

根據(jù)算法的時(shí)間復(fù)雜度分析比較這兩種算法的優(yōu)劣。

【解答】第二種算法的時(shí)間性能要好些。第一種算法需執(zhí)行大量的乘法運(yùn)算，而第二種算法進(jìn)行了優(yōu)化，減少了不必要的乘法運(yùn)算。

8.算法設(shè)計(jì)（要求：算法用偽代碼和C++描述，并分析最壞情況下的時(shí)間復(fù)雜度）⑴ 對(duì)一個(gè)整型數(shù)組A[n]設(shè)計(jì)一個(gè)排序算法?！窘獯稹肯旅媸呛?jiǎn)單選擇排序算法的偽代碼描述。

下面是簡(jiǎn)單選擇排序算法的C++描述。

分析算法，有兩層嵌套的for循環(huán)，所以。

⑵ 找出整型數(shù)組A[n]中元素的最大值和次最大值。【解答】算法的偽代碼描述如下：

算法的C++描述如下：

分析算法，只有一層循環(huán)，共執(zhí)行n-2次，所以，T(n)=O(n)。

學(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.算法在發(fā)生非法操作時(shí)可以作出處理的特性稱為（）?！窘獯稹拷研?/p>

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)和抽象數(shù)據(jù)類型的概念與程序設(shè)計(jì)語言中數(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ì)語言中的數(shù)據(jù)類型是一個(gè)值的集合和定義在這個(gè)值集上一組操作的總稱。抽象數(shù)據(jù)類型可以看成是對(duì)數(shù)據(jù)類型的一種抽象。

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=(D，R)，其中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 { x*=2;count++;} return count;【解答】Ｏ(log2n)

第 2 章 線性表

課后習(xí)題講解 1.填空

⑴ 在順序表中，等概率情況下，插入和刪除一個(gè)元素平均需移動(dòng)（）個(gè)元素，具體移動(dòng)元素的個(gè)數(shù)與（）和（）有關(guān)。

【解答】表長(zhǎng)的一半，表長(zhǎng)，該元素在表中的位置

⑵ 順序表中第一個(gè)元素的存儲(chǔ)地址是100，每個(gè)元素的長(zhǎng)度為2，則第5個(gè)元素的存儲(chǔ)地址是（）?！窘獯稹?08 【分析】第5個(gè)元素的存儲(chǔ)地址=第1個(gè)元素的存儲(chǔ)地址＋(5－1)×2=108 ⑶ 設(shè)單鏈表中指針p 指向結(jié)點(diǎn)A，若要?jiǎng)h除A的后繼結(jié)點(diǎn)（假設(shè)A存在后繼結(jié)點(diǎn)），則需修改指針的操作為（）。

【解答】p->next=(p->next)->next ⑷ 單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是（）?！窘獯稹繛榱诉\(yùn)算方便

【分析】例如在插入和刪除操作時(shí)不必對(duì)表頭的情況進(jìn)行特殊處理。

⑸ 非空的單循環(huán)鏈表由頭指針head指示，則其尾結(jié)點(diǎn)（由指針p所指）滿足（）?！窘獯稹縫->next=head 【分析】如圖2-8所示。

⑹ 在由尾指針rear指示的單循環(huán)鏈表中，在表尾插入一個(gè)結(jié)點(diǎn)s的操作序列是（）；刪除開始結(jié)點(diǎn)的操作序列為（）。

【解答】s->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ù)雜度為（）。【解答】Ο(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 【分析】線性表的鏈接存儲(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 單鏈表 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)鏈表、雙鏈表都不合適，考慮在帶尾指針的單循環(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 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ǔ)空間的速度是一樣的。由于雙鏈表具有對(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->next=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ǔ)順序總是一致的。

【解答】錯(cuò)。順序表的邏輯順序和存儲(chǔ)順序一致，鏈表的邏輯順序和存儲(chǔ)順序不一定一致。⑵ 線性表的順序存儲(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è)直接后繼。

【解答】錯(cuò)。每個(gè)元素最多只有一個(gè)直接前驅(qū)和一個(gè)直接后繼，第一個(gè)元素沒有前驅(qū)，最后一個(gè)元素沒有后繼。

⑸ 在單鏈表中，要取得某個(gè)元素，只要知道該元素所在結(jié)點(diǎn)的地址即可，因此單鏈表是隨機(jī)存取結(jié)構(gòu)?！窘獯稹垮e(cuò)。要找到該結(jié)點(diǎn)的地址，必須從頭指針開始查找，所以單鏈表是順序存取結(jié)構(gòu)。4．請(qǐng)說明順序表和單鏈表各有何優(yōu)缺點(diǎn)，并分析下列情況下，采用何種存儲(chǔ)結(jié)構(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ǔ)結(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ù)組A[n]中所有元素循環(huán)右移k個(gè)位置?！窘獯稹克惴ㄋ枷胝?qǐng)參見主教材第一章思想火花。下面給出具體算法。

分析算法，第一次調(diào)用Reverse函數(shù)的時(shí)間復(fù)雜度為O(k)，第二次調(diào)用Reverse函數(shù)的時(shí)間復(fù)雜度為O(n-k)，第三次調(diào)用Reverse函數(shù)的時(shí)間復(fù)雜度為O(n)，所以，總的時(shí)間復(fù)雜度為O(n)。

⑵ 已知數(shù)組A[n]中的元素為整型，設(shè)計(jì)算法將其調(diào)整為左右兩部分，左邊所有元素為奇數(shù)，右邊所有元素為偶數(shù)，并要求算法的時(shí)間復(fù)雜度為Ｏ(n)。

【解答】從數(shù)組的兩端向中間比較，設(shè)置兩個(gè)變量i和j，初始時(shí)i=0，j=n-1，若A[i]為偶數(shù)并且A[j]為奇數(shù)，則將A[i]與A[j]交換。具體算法如下：

分析算法，兩層循環(huán)將數(shù)組掃描一遍，所以，時(shí)間復(fù)雜度為Ｏ(n)。

⑶ 試編寫在無頭結(jié)點(diǎn)的單鏈表上實(shí)現(xiàn)線性表的插入操作的算法，并和帶頭結(jié)點(diǎn)的單鏈表上的插入操作的實(shí)現(xiàn)進(jìn)行比較?！窘獯稹繀⒁?.2.3。

⑷ 試分別以順序表和單鏈表作存儲(chǔ)結(jié)構(gòu)，各寫一實(shí)現(xiàn)線性表就地逆置的算法。

【解答】順序表的逆置，即是將對(duì)稱元素交換，設(shè)順序表的長(zhǎng)度為length，則將表中第i個(gè)元素與第length-i-1個(gè)元素相交換。具體算法如下：

單鏈表的逆置請(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)。

【解答】利用單循環(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)鏈表中只含同一類字符。

【解答】在單鏈表A中依次取元素，若取出的元素是字母，把它插入到字母鏈表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ì)稱。

【解答】設(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指向同一結(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 【解答】D 2．在長(zhǎng)度為n的線性表中查找值為x的數(shù)據(jù)元素的時(shí)間復(fù)雜度為：（）。

A O(0)B O(1)C O(n)D O(n2)【解答】C 3．在一個(gè)長(zhǎng)度為n的順序表的第i（1≤i≤n+1）個(gè)元素之前插入一個(gè)元素，需向后移動(dòng)（）個(gè)元素，刪除第i（1≤i≤n）個(gè)元素時(shí)，需向前移動(dòng)（）個(gè)元素?！窘獯稹縩-i+1，n-i

4．在單鏈表中，除了頭結(jié)點(diǎn)以外，任一結(jié)點(diǎn)的存儲(chǔ)位置由（）指示。【解答】其前趨結(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之間（1≤i≤n）的概率為插入一個(gè)元素所要移動(dòng)的元素個(gè)數(shù)又是多少？ 【解答】

，則平均每。

8．線性表存放在整型數(shù)組A[arrsize]的前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)，再將二者間的所有結(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?！窘獯稹克惴ㄈ缦拢?/p>

第 3 章 特殊線性表——棧、隊(duì)列和串

課后習(xí)題講解

1.填空

⑴ 設(shè)有一個(gè)空棧，棧頂指針為1000H，現(xiàn)有輸入序列為1、2、3、4、5，經(jīng)過push，push，pop，push，pop，push，push后，輸出序列是（），棧頂指針為（）?！窘獯稹?3，1003H ⑵ 棧通常采用的兩種存儲(chǔ)結(jié)構(gòu)是（）；其判定棧空的條件分別是（），判定棧滿的條件分別是（）?！窘獯稹宽樞虼鎯?chǔ)結(jié)構(gòu)和鏈接存儲(chǔ)結(jié)構(gòu)（或順序棧和鏈棧），棧頂指針top=-1和top=NULL，棧頂指針top等于數(shù)組的長(zhǎng)度和內(nèi)存無可用空間

⑶（）可作為實(shí)現(xiàn)遞歸函數(shù)調(diào)用的一種數(shù)據(jù)結(jié)構(gòu)?！窘獯稹織?/p>

【分析】遞歸函數(shù)的調(diào)用和返回正好符合后進(jìn)先出性。⑷ 表達(dá)式a*(b+c)-d的后綴表達(dá)式是（）?！窘獯稹縜bc+*d-【分析】將中綴表達(dá)式變?yōu)楹缶Y表達(dá)式有一個(gè)技巧：將操作數(shù)依次寫下來，再將算符插在它的兩個(gè)操作數(shù)的后面。

⑸ 棧和隊(duì)列是兩種特殊的線性表，棧的操作特性是（），隊(duì)列的操作特性是（），棧和隊(duì)列的主要區(qū)別在于（）。

【解答】后進(jìn)先出，先進(jìn)先出，對(duì)插入和刪除操作限定的位置不同 ⑹ 循環(huán)隊(duì)列的引入是為了克服（）?！窘獯稹考僖绯?/p>

⑺ 數(shù)組Q[n]用來表示一個(gè)循環(huán)隊(duì)列，front為隊(duì)頭元素的前一個(gè)位置，rear為隊(duì)尾元素的位置，計(jì)算隊(duì)列中元素個(gè)數(shù)的公式為（）?！窘獯稹浚╮ear-front+n）% n 【分析】也可以是（rear-front）% n，但rear-front的結(jié)果可能是負(fù)整數(shù)，而對(duì)一個(gè)負(fù)整數(shù)求模，其結(jié)果在不同的編譯器環(huán)境下可能會(huì)有所不同。

⑻ 用循環(huán)鏈表表示的隊(duì)列長(zhǎng)度為n，若只設(shè)頭指針，則出隊(duì)和入隊(duì)的時(shí)間復(fù)雜度分別是（）和（）?！窘獯稹浚?1)，Ｏ(n)【分析】在帶頭指針的循環(huán)鏈表中，出隊(duì)即是刪除開始結(jié)點(diǎn)，這只需修改相應(yīng)指針；入隊(duì)即是在終端結(jié)點(diǎn)的后面插入一個(gè)結(jié)點(diǎn)，這需要從頭指針開始查找終端結(jié)點(diǎn)的地址。⑼ 串是一種特殊的線性表，其特殊性體現(xiàn)在（）?！窘獯稹繑?shù)據(jù)元素的類型是一個(gè)字符 ⑽ 兩個(gè)串相等的充分必要條件是（）。【解答】長(zhǎng)度相同且對(duì)應(yīng)位置的字符相等 【分析】例如“abc”≠“abc ”，“abc”≠“bca”。2.選擇題

⑴ 若一個(gè)棧的輸入序列是1，2，3，…，n，輸出序列的第一個(gè)元素是n，則第i個(gè)輸出元素是（）。A 不確定 B n-i C n-i-1 D n-i+1 【解答】D 【分析】此時(shí)，輸出序列一定是輸入序列的逆序。

⑵ 設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素e1、e2、e3、e4、e5、e6依次通過棧S，一個(gè)元素出棧后即進(jìn)入隊(duì)列Q，若6個(gè)元素出隊(duì)的順序是e2、e4、e3、e6、e5、e1，則棧S的容量至少應(yīng)該是（）。A 6

B C D 2 【解答】C 【分析】由于隊(duì)列具有先進(jìn)先出性，所以，此題中隊(duì)列形同虛設(shè)，即出棧的順序也是e2、e4、e3、e6、e5、e1。

⑶ 一個(gè)棧的入棧序列是1，2，3，4，5，則棧的不可能的輸出序列是（）。A 54321 B 45321 C 43512 D 12345 【解答】C 【分析】此題有一個(gè)技巧：在輸出序列中任意元素后面不能出現(xiàn)比該元素小并且是升序（指的是元素的序號(hào)）的兩個(gè)元素。

⑷ 設(shè)計(jì)一個(gè)判別表達(dá)式中左右括號(hào)是否配對(duì)的算法，采用（）數(shù)據(jù)結(jié)構(gòu)最佳 A 順序表 B 棧 C 隊(duì)列 D 鏈表 【解答】B 【分析】每個(gè)右括號(hào)與它前面的最后一個(gè)沒有匹配的左括號(hào)配對(duì)，因此具有后進(jìn)先出性。

⑸ 在解決計(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)先出性。⑹ 一個(gè)隊(duì)列的入隊(duì)順序是1，2，3，4，則隊(duì)列的輸出順序是（）。A 4321 B 1234 C 1432 D 3241 【解答】B 【分析】隊(duì)列的入隊(duì)順序和出隊(duì)順序總是一致的。⑺ 棧和隊(duì)列的主要區(qū)別在于（）。

A 它們的邏輯結(jié)構(gòu)不一樣 B 它們的存儲(chǔ)結(jié)構(gòu)不一樣 C 所包含的運(yùn)算不一樣 D 插入、刪除運(yùn)算的限定不一樣 【解答】D 【分析】棧和隊(duì)列的邏輯結(jié)構(gòu)都是線性的，都有順序存儲(chǔ)和鏈接存儲(chǔ)，有可能包含的運(yùn)算不一樣，但不是主要區(qū)別，任何數(shù)據(jù)結(jié)構(gòu)在針對(duì)具體問題時(shí)包含的運(yùn)算都可能不同。

⑻ 設(shè)數(shù)組S[n]作為兩個(gè)棧S1和S2的存儲(chǔ)空間，對(duì)任何一個(gè)棧只有當(dāng)S[n]全滿時(shí)才不能進(jìn)行進(jìn)棧操作。為這兩個(gè)棧分配空間的最佳方案是（）。A S1的棧底位置為0，S2的棧底位置為n-1 B S1的棧底位置為0，S2的棧底位置為n/2 C S1的棧底位置為0，S2的棧底位置為n D S1的棧底位置為0，S2的棧底位置為1 【解答】A 【分析】?jī)蓷９蚕砜臻g首先兩個(gè)棧是相向增長(zhǎng)的，棧底應(yīng)該分別指向兩個(gè)棧中的第一個(gè)元素的位置，并注意C++中的數(shù)組下標(biāo)是從0開始的。

⑼ 設(shè)有兩個(gè)串p和q，求q在p中首次出現(xiàn)的位置的運(yùn)算稱作（）。A 連接 B 模式匹配 C 求子串 D 求串長(zhǎng) 【解答】B 3.判斷題

⑴ 有n個(gè)元素依次進(jìn)棧，則出棧序列有(n-1)/2種。

【解答】錯(cuò)。應(yīng)該有 種。

⑵ 棧可以作為實(shí)現(xiàn)過程調(diào)用的一種數(shù)據(jù)結(jié)構(gòu)。

【解答】對(duì)。只要操作滿足后進(jìn)先出性，都可以采用棧作為輔助數(shù)據(jù)結(jié)構(gòu)。⑶ 在棧滿的情況下不能做進(jìn)棧操作，否則將產(chǎn)生―上溢‖?！窘獯稹繉?duì)。

⑷ 在循環(huán)隊(duì)列中，front指向隊(duì)頭元素的前一個(gè)位置，rear指向隊(duì)尾元素的位置，則隊(duì)滿的條件是front=rear。

【解答】錯(cuò)。這是隊(duì)空的判定條件，在循環(huán)隊(duì)列中要將隊(duì)空和隊(duì)滿的判定條件區(qū)別開。⑸ 空串與空格串是相同的。

【解答】錯(cuò)?？沾拈L(zhǎng)度為零，而空格串的長(zhǎng)度不為0，其長(zhǎng)度是串中空格的個(gè)數(shù)。

4.設(shè)有一個(gè)棧，元素進(jìn)棧的次序?yàn)锳，B，C，D，E，能否得到如下出棧序列，若能，請(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)象。

【解答】假設(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)、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．空串和空格串有何區(qū)別？串中的空格符有何意義？空串在串處理中有何作用？

【解答】不含任何字符的串稱為空串，其長(zhǎng)度為零。僅含空格的串稱為空格串，它的長(zhǎng)度為串中空格符的個(gè)數(shù)。串中的空格符可用來分隔一般的字符，便于人們識(shí)別和閱讀，但計(jì)算串長(zhǎng)時(shí)應(yīng)包括這些空格符?？沾诖幚碇锌勺鳛槿我獯淖哟?.算法設(shè)計(jì)

⑴ 假設(shè)以不帶頭結(jié)點(diǎn)的循環(huán)鏈表表示隊(duì)列，并且只設(shè)一個(gè)指針指向隊(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ì)算法如下：

⑵ 設(shè)順序棧S中有2n個(gè)元素，從棧頂?shù)綏５椎脑匾来螢閍2n，a2n-1，…，a1，要求通過一個(gè)循環(huán)隊(duì)列重新排列棧中元素，使得從棧頂?shù)綏５椎脑匾来螢閍2n，a2n-2，…，a2，a2n-1，a2n-3，…，a1，請(qǐng)?jiān)O(shè)計(jì)算法實(shí)現(xiàn)該操作，要求空間復(fù)雜度和時(shí)間復(fù)雜度均為O(n)?！窘獯稹坎僮鞑襟E為： ① 將所有元素出棧并入隊(duì)；

② 依次將隊(duì)列元素出隊(duì)，如果是偶數(shù)結(jié)點(diǎn)，則再入隊(duì)，如果是奇數(shù)結(jié)點(diǎn)，則入棧； ③ 將奇數(shù)結(jié)點(diǎn)出棧并入隊(duì)； ④ 將偶數(shù)結(jié)點(diǎn)出隊(duì)并入棧； ⑤ 將所有元素出棧并入隊(duì)； ⑥ 將所有元素出隊(duì)并入棧即為所求。

⑶ 用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)串S，編寫算法刪除S中第 i個(gè)字符開始的連續(xù)j個(gè)字符。

【解答】先判斷串S中要?jiǎng)h除的內(nèi)容是否存在，若存在，則將第i+j-1之后的字符前移j個(gè)位置。算法如下：

⑷ 對(duì)于采用順序存儲(chǔ)結(jié)構(gòu)的串S，編寫一個(gè)函數(shù)刪除其值等于ch的所有字符。

【解答】從后向前刪除值為ch的所有元素，這樣所有移動(dòng)的元素中沒有值為ch的元素，能減少移動(dòng)元素的次數(shù)，提高算法的效率。算法如下：

⑸ 對(duì)串的模式匹配KMP算法設(shè)計(jì)求模式滑動(dòng)位置的next函數(shù)?！窘獯稹繀⒁?.2.5 學(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;【解答】C 2．一個(gè)棧的入棧序列是a, b, c, d, e，則棧的不可能的出棧序列是（）。A edcba B cdeba C debca D abcde 【解答】C 3．從棧頂指針為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;【解答】D 4．設(shè)元素1, 2, 3, P, A依次經(jīng)過一個(gè)棧，進(jìn)棧次序?yàn)?23PA，在棧的輸出序列中，有哪些序列可作為C++程序設(shè)計(jì)語言的變量名。

【解答】PA321, P3A21, P32A1, P321A, AP321 5.設(shè)S=“I_ am_ a_ teacther”，其長(zhǎng)度為（）?！窘獯稹?5 第 4 章 廣義線性表——多維數(shù)組和廣義表

課后習(xí)題講解

1.填空

⑴ 數(shù)組通常只有兩種運(yùn)算：（）和（），這決定了數(shù)組通常采用（）結(jié)構(gòu)來實(shí)現(xiàn)存儲(chǔ)?！窘獯稹看嫒。薷模樞虼鎯?chǔ)

【分析】數(shù)組是一個(gè)具有固定格式和數(shù)量的數(shù)據(jù)集合，在數(shù)組上一般不能做插入、刪除元素的操作。除了初始化和銷毀之外，在數(shù)組中通常只有存取和修改兩種操作。

⑵ 二維數(shù)組A中行下標(biāo)從10到20，列下標(biāo)從5到10，按行優(yōu)先存儲(chǔ)，每個(gè)元素占4個(gè)存儲(chǔ)單元，A[10][5]的存儲(chǔ)地址是1000，則元素A[15][10]的存儲(chǔ)地址是（）?！窘獯稹?140 【分析】數(shù)組A中每行共有6個(gè)元素，元素A[15][10]的前面共存儲(chǔ)了(15-10)×6+5個(gè)元素，每個(gè)元素占4個(gè)存儲(chǔ)單元，所以，其存儲(chǔ)地址是1000+140=1140。

⑶ 設(shè)有一個(gè)10階的對(duì)稱矩陣A采用壓縮存儲(chǔ)，A[0][0]為第一個(gè)元素，其存儲(chǔ)地址為d，每個(gè)元素占1個(gè)存儲(chǔ)單元，則元素A[8][5]的存儲(chǔ)地址為（）?！窘獯稹縟+41 【分析】元素A[8][5]的前面共存儲(chǔ)了(1+2+…+8)+5=41個(gè)元素。⑷ 稀疏矩陣一般壓縮存儲(chǔ)方法有兩種，分別是（）和（）?！窘獯稹咳M順序表，十字鏈表

⑸ 廣義表((a),(((b),c)),(d))的長(zhǎng)度是（），深度是（），表頭是（），表尾是（）。【解答】3，4，(a)，((((b),c)),(d))⑹ 已知廣義表LS=(a，(b，c，d)，e)，用Head和Tail函數(shù)取出LS中原子b的運(yùn)算是（）。【解答】Head(Head(Tail(LS)))2.選擇題

⑴ 二維數(shù)組A的每個(gè)元素是由6個(gè)字符組成的串，行下標(biāo)的范圍從0~8，列下標(biāo)的范圍是從0~9，則存放A至少需要（）個(gè)字節(jié)，A的第8列和第5行共占（）個(gè)字節(jié)，若A按行優(yōu)先方式存儲(chǔ)，元素A[8][5]的起始地址與當(dāng)A按列優(yōu)先方式存儲(chǔ)時(shí)的（）元素的起始地址一致。A 90 B 180 C 240 D 540 E 108 F 114 G 54 H A[8][5] I A[3][10] J A[5][8] K A[4][9] 【解答】D，E，K 【分析】數(shù)組A為9行10列，共有90個(gè)元素，所以，存放A至少需要90×6=540個(gè)存儲(chǔ)單元，第8列和第5行共有18個(gè)元素（注意行列有一個(gè)交叉元素），所以，共占108個(gè)字節(jié)，元素A[8][5]按行優(yōu)先存儲(chǔ)的起始地址為d+8×10+5=d+85，設(shè)元素A[i][j]按列優(yōu)先存儲(chǔ)的起始地址與之相同，則d+j×9+i=d+85，解此方程，得i=4，j=9。

⑵ 將數(shù)組稱為隨機(jī)存取結(jié)構(gòu)是因?yàn)椋ǎ?/p>

A 數(shù)組元素是隨機(jī)的 B 對(duì)數(shù)組任一元素的存取時(shí)間是相等的 C 隨時(shí)可以對(duì)數(shù)組進(jìn)行訪問 D 數(shù)組的存儲(chǔ)結(jié)構(gòu)是不定 【解答】B ⑶ 下面的說法中，不正確的是（）

A 數(shù)組是一種線性結(jié)構(gòu) B 數(shù)組是一種定長(zhǎng)的線性結(jié)構(gòu)

C 除了插入與刪除操作外，數(shù)組的基本操作還有存取、修改、檢索和排序等 D 數(shù)組的基本操作有存取、修改、檢索和排序等，沒有插入與刪除操 【解答】C 【分析】數(shù)組屬于廣義線性表，數(shù)組被創(chuàng)建以后，其維數(shù)和每維中的元素個(gè)數(shù)是確定的，所以，數(shù)組通常沒有插入和刪除操作。

⑷ 對(duì)特殊矩陣采用壓縮存儲(chǔ)的目的主要是為了（）A 表達(dá)變得簡(jiǎn)單 B 對(duì)矩陣元素的存取變得簡(jiǎn)單 C 去掉矩陣中的多余元素 D 減少不必要的存儲(chǔ)空間 【解答】D 【分析】在特殊矩陣中，有很多值相同的元素并且他們的分布有規(guī)律，沒有必要為值相同的元素重復(fù)存儲(chǔ)。⑸ 下面（）不屬于特殊矩陣。

A 對(duì)角矩陣 B 三角矩陣 C 稀疏矩陣 D 對(duì)稱矩陣

【解答】C ⑹ 若廣義表A滿足Head(A)=Tail(A)，則A為（）A()B(())C((),())D((),(),())【解答】B ⑺ 下面的說法中，不正確的是（）

A 廣義表是一種多層次的結(jié)構(gòu) B 廣義表是一種非線性結(jié)構(gòu) C 廣義表是一種共享結(jié)構(gòu) D 廣義表是一種遞歸 【解答】B 【分析】從各層元素各自具有的線性關(guān)系講，廣義表屬于線性結(jié)構(gòu)。⑻ 下面的說法中，不正確的是（）

A 對(duì)稱矩陣只須存放包括主對(duì)角線元素在內(nèi)的下（或上）三角的元素即可。B 對(duì)角矩陣只須存放非零元素即可。

C 稀疏矩陣中值為零的元素較多，因此可以采用三元組表方法存儲(chǔ)。

D 稀疏矩陣中大量值為零的元素分布有規(guī)律，因此可以采用三元組表方法存儲(chǔ) 【解答】D 【分析】稀疏矩陣中大量值為零的元素分布沒有規(guī)律，因此采用三元組表存儲(chǔ)。如果零元素的分布有規(guī)律，就沒有必要存儲(chǔ)非零元素的行號(hào)和列號(hào)，而需要按其壓縮規(guī)律找出相應(yīng)的映象函數(shù)。3.判斷題

⑴ 數(shù)組是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，數(shù)組元素之間的關(guān)系既不是線性的，也不是樹形的?！窘獯稹垮e(cuò)。例如二維數(shù)組可以看成是數(shù)據(jù)元素為線性表的線性表。⑵ 使用三元組表存儲(chǔ)稀疏矩陣的元素，有時(shí)并不能節(jié)省存儲(chǔ)空間。

【解答】對(duì)。因?yàn)槿M表除了存儲(chǔ)非零元素值外，還需要存儲(chǔ)其行號(hào)和列號(hào)。⑶ 稀疏矩陣壓縮存儲(chǔ)后，必會(huì)失去隨機(jī)存取功能。

【解答】對(duì)。因?yàn)閴嚎s存儲(chǔ)后，非零元素的存儲(chǔ)位置和行號(hào)、列號(hào)之間失去了確定的關(guān)系。

⑷ 線性表可以看成是廣義表的特例，如果廣義表中的每個(gè)元素都是單元素，則廣義表便成為線性表?！窘獯稹繉?duì)。

⑸ 若一個(gè)廣義表的表頭為空表，則此廣義表亦為空表。

【解答】錯(cuò)。如廣義表L=(()，(a，b))的表頭為空表，但L不是空表。

4．一個(gè)稀疏矩陣如圖4-4所示，寫出對(duì)應(yīng)的三元組順序表和十字鏈表存儲(chǔ)表示。

【解答】對(duì)應(yīng)的三元組順序表如圖4-5所示，十字鏈表如圖4-6所示。

5．已知A為稀疏矩陣，試從空間和時(shí)間角度比較采用二維數(shù)組和三元組順序表兩種不同的存儲(chǔ)結(jié)構(gòu)完成求 運(yùn)算的優(yōu)缺點(diǎn)。

【解答】設(shè)稀疏矩陣為m行n列，如果采用二維數(shù)組存儲(chǔ)，其空間復(fù)雜度為Ｏ(m×n)；因?yàn)橐獙⑺械木仃囋乩奂悠饋恚?，需要用一個(gè)兩層的嵌套循環(huán)，其時(shí)間復(fù)雜度亦為Ｏ(m×n)。如果采用三元組順序表進(jìn)行壓縮存儲(chǔ)，假設(shè)矩陣中有t個(gè)非零元素，其空間復(fù)雜度為Ｏ(t)，將所有的矩陣元素累加起來只需將三元組順序表掃描一遍，其時(shí)間復(fù)雜度亦為Ｏ(t)。當(dāng)t << m×n時(shí)，采用三元組順序表存儲(chǔ)可獲得較好的時(shí)、空性能。

6．設(shè)某單位職工工資表ST由―工資‖、―扣除‖和―實(shí)發(fā)金額‖三項(xiàng)組成，其中工資項(xiàng)包括―基本工資‖、―津貼‖和―獎(jiǎng)金‖，扣除項(xiàng)包括―水‖、―電‖和―煤氣‖。

⑴ 請(qǐng)用廣義表形式表示所描述的工資表ST，并用表頭和表尾求表中的―獎(jiǎng)金‖項(xiàng)； ⑵ 畫出該工資表ST的存儲(chǔ)結(jié)構(gòu)。

【解答】⑴ ST=((基本工資，津貼，獎(jiǎng)金)，(水，電，煤氣)，實(shí)發(fā)金額)Head(Tail(Tail(Head(ST))))=獎(jiǎng)金

⑵ 工資表ST的頭尾表示法如圖4-7所示。

7．若在矩陣A中存在一個(gè)元素ai,j（0≤i≤n-1，0≤j≤m-1），該元素是第i行元素中最小值且又是第j列元素中最大值，則稱此元素為該矩陣的一個(gè)馬鞍點(diǎn)。假設(shè)以二維數(shù)組存儲(chǔ)矩陣A，試設(shè)計(jì)一個(gè)求該矩陣所有馬鞍點(diǎn)的算法，并分析最壞情況下的時(shí)間復(fù)雜度。

【解答】在矩陣中逐行尋找該行中的最小值，然后對(duì)其所在的列尋找最大值，如果該列上的最大值與該行上的最小值相等，則說明該元素是鞍點(diǎn)，將它所在行號(hào)和列號(hào)輸出。

具體算法如下：

分析算法，外層for循環(huán)共執(zhí)行n次，內(nèi)層第一個(gè)for循環(huán)執(zhí)行m次，第二個(gè)for循環(huán)最壞情況下執(zhí)行n次，所以，最壞情況下的時(shí)間復(fù)雜度為Ｏ(mn+n2)。

學(xué)習(xí)自測(cè)及答案

1．二維數(shù)組M中每個(gè)元素的長(zhǎng)度是3個(gè)字節(jié)，行下標(biāo)從0到7，列下標(biāo)從0到9，從首地址d開始存儲(chǔ)。若按行優(yōu)先方式存儲(chǔ)，元素M[7][5]的起始地址為（），若按列優(yōu)先方式存儲(chǔ)，元素M[7][5]的起始地址為（）?！窘獯稹縟+22，d+141 2．一個(gè)n×n的對(duì)稱矩陣，按行優(yōu)先或列優(yōu)先進(jìn)行壓縮存儲(chǔ)，則其存儲(chǔ)容量為（）?！窘獯稹縩(n+1)/2 3．設(shè)n行n列的下三角矩陣A（行列下標(biāo)均從1開始）已壓縮到一維數(shù)組S[1]~S[n(n+1)/2]中，若按行優(yōu)先存儲(chǔ)，則A[i][j]在數(shù)組S中的存儲(chǔ)位置是（）?！窘獯稹縤×(i-1)/2+j 4．已知廣義表LS=(a,(b, c),(d, e, a))，運(yùn)用Head函數(shù)和Tail函數(shù)取出LS中原子d的運(yùn)算是（）?！窘獯稹縃ead(Head(Tail(Tail(LS))))5．廣義表(a, b,(c,(d)))的表尾是（）。A(d)B(c,(d))C b,(c,(d))D(b,(c,(d)))【解答】D 6．設(shè)有三對(duì)角矩陣An×n（行、列下標(biāo)均從0開始），將其三條對(duì)角線上的元素逐行存于數(shù)組B[3n-2]中，使得B[k]=aij求：

⑴ 用i, j表示k的下標(biāo)變換公式； ⑵ 用k表示i, j的下標(biāo)變換公式。

【解答】⑴ 要求i, j表示k的下標(biāo)變換公式，就是要求在k之前已經(jīng)存儲(chǔ)了多少個(gè)非零元素，這些非零元素的個(gè)數(shù)就是k的值。元素aij求所在的行為i，列為j，則在其前面的非零元素的個(gè)數(shù)是；k=2 + 3(i－1)+(j－i + 1)= 2i+ j。

⑵ 因?yàn)閗和i, j之間是一一對(duì)應(yīng)的關(guān)系，k+1是當(dāng)前非零元素的個(gè)數(shù)，整除即為其所在行號(hào)，取余表示當(dāng)前行中第幾個(gè)非零元素，加上前面零元素所在列數(shù)就是當(dāng)前列號(hào)，即：

7．已知兩個(gè)n×n的對(duì)稱矩陣按壓縮存儲(chǔ)方法存儲(chǔ)在已維數(shù)組A和B中，編寫算法計(jì)算對(duì)稱矩陣的乘積。【解答】對(duì)稱矩陣采用壓縮存儲(chǔ)，乘積矩陣也采用壓縮存儲(chǔ)。注意矩陣元素的表示方法。

第 5 章 樹和二叉樹

課后習(xí)題講解

1.填空題

⑴ 樹是n（n≥0）結(jié)點(diǎn)的有限集合，在一棵非空樹中，有（）個(gè)根結(jié)點(diǎn)，其余的結(jié)點(diǎn)分成m（m＞0）個(gè)（）的集合，每個(gè)集合都是根結(jié)點(diǎn)的子樹?！窘獯稹坑星覂H有一個(gè)，互不相交

⑵ 樹中某結(jié)點(diǎn)的子樹的個(gè)數(shù)稱為該結(jié)點(diǎn)的（），子樹的根結(jié)點(diǎn)稱為該結(jié)點(diǎn)的（），該結(jié)點(diǎn)稱為其子樹根結(jié)點(diǎn)的（）。

【解答】度，孩子，雙親

⑶ 一棵二叉樹的第i（i≥1）層最多有（）個(gè)結(jié)點(diǎn)；一棵有n（n>0）個(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á)到的最大值是（），最小值是（）。【解答】2h-1，2h-1 【分析】最小結(jié)點(diǎn)個(gè)數(shù)的情況是第1層有1個(gè)結(jié)點(diǎn)，其他層上都只有2個(gè)結(jié)點(diǎn)。

⑸ 深度為k的二叉樹中，所含葉子的個(gè)數(shù)最多為（）?！窘獯稹?k-1 【分析】在滿二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù)達(dá)到最多。

⑹ 具有100個(gè)結(jié)點(diǎn)的完全二叉樹的葉子結(jié)點(diǎn)數(shù)為（）?！窘獯稹?0 【分析】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，則其后序遍歷序列是（）?！窘獯稹緾DBGFEA 【分析】根據(jù)前序遍歷序列和后序遍歷序列將該二叉樹構(gòu)造出來。

⑼ 在具有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。

⑶ 二叉樹的前序序列和后序序列正好相反，則該二叉樹一定是（）的二叉樹。A 空或只有一個(gè)結(jié)點(diǎn) B 高度等于其結(jié)點(diǎn)數(shù) C 任一結(jié)點(diǎn)無左孩子 D 任一結(jié)點(diǎn)無右孩子 【解答】B 【分析】此題注意是序列正好相反，則左斜樹和右斜樹均滿足條件。

⑷ 線索二叉樹中某結(jié)點(diǎn)R沒有左孩子的充要條件是（）。A R.lchild=NULL B R.ltag=0 C R.ltag=1 D R.rchild=NULL 【解答】C 【分析】線索二叉樹中某結(jié)點(diǎn)是否有左孩子，不能通過左指針域是否為空來判斷，而要判斷左標(biāo)志是否為1。

⑸ 深度為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 2k–1-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ù)最少的情況下，葉子結(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 【分析】三種遍歷次序均是先左子樹后右子樹。

⑻ 如果T' 是由有序樹T轉(zhuǎn)換而來的二叉樹，那么T中結(jié)點(diǎn)的前序序列就是T' 中結(jié)點(diǎn)的（）序列，T中結(jié)點(diǎn)的后序序列就是 T' 中結(jié)點(diǎn)的（）序列。A 前序 B 中序 C 后序 D 層序 【解答】A，B

⑼ 設(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 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)換來的。

⑽ 討論樹、森林和二叉樹的關(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í)際意義 【解答】B 3.判斷題

⑴ 在線索二叉樹中，任一結(jié)點(diǎn)均有指向其前趨和后繼的線索。

【解答】錯(cuò)。某結(jié)點(diǎn)是否有前驅(qū)或后繼的線索，取決于該結(jié)點(diǎn)的標(biāo)志域是否為1。

⑵ 在二叉樹的前序遍歷序列中，任意一個(gè)結(jié)點(diǎn)均處在其子女的前面?！窘獯稹繉?duì)。由前序遍歷的操作定義可知。

⑶ 二叉樹是度為2的樹。

【解答】錯(cuò)。二叉樹和樹是兩種不同的樹結(jié)構(gòu)，例如，左斜樹是一棵二叉樹，但它的度為1。

⑷ 由樹轉(zhuǎn)換成二叉樹，其根結(jié)點(diǎn)的右子樹總是空的?！窘獯稹繉?duì)。因?yàn)楦Y(jié)點(diǎn)無兄弟結(jié)點(diǎn)。

⑸ 用一維數(shù)組存儲(chǔ)二叉樹時(shí)，總是以前序遍歷存儲(chǔ)結(jié)點(diǎn)。

【解答】錯(cuò)。二叉樹的順序存儲(chǔ)結(jié)構(gòu)是按層序存儲(chǔ)的，一般適合存儲(chǔ)完全二叉樹。

4．證明：對(duì)任一滿二叉樹，其分枝數(shù)B＝2(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．證明：已知一棵二叉樹的前序序列和中序序列，則可唯一確定該二叉樹?！窘獯稹孔C明采用歸納法。

設(shè)二叉樹的前序遍歷序列為a1a2a3… an，中序遍歷序列為b1b2b3… bn。

當(dāng)n=1時(shí)，前序遍歷序列為a1，中序遍歷序列為b1，二叉樹只有一個(gè)根結(jié)點(diǎn)，所以，a1= b1，可以唯一確定該二叉樹；

假設(shè)當(dāng)n<=k時(shí)，前序遍歷序列a1a2a3… ak和中序遍歷序列b1b2b3… bk可唯一確定該二叉樹，下面證明當(dāng)n=k+1時(shí)，前序遍歷序列a1a2a3… akak+1和中序遍歷序列b1b2b3… bk bk+1可唯一確定一棵二叉樹。

在前序遍歷序列中第一個(gè)訪問的一定是根結(jié)點(diǎn)，即二叉樹的根結(jié)點(diǎn)是a1，在中序遍歷序列中查找值為a1的結(jié)點(diǎn)，假設(shè)為bi，則a1=bi且b1b2… bi-1是對(duì)根結(jié)點(diǎn)a1的左子樹進(jìn)行中序遍歷的結(jié)果，前序遍歷序列a2a3… ai是對(duì)根結(jié)點(diǎn)a1的左子樹進(jìn)行前序遍歷的結(jié)果，由歸納假設(shè)，前序遍歷序列a2a3… ai和中序遍歷序列b1b2… bi-1唯一確定了根結(jié)點(diǎn)的左子樹，同樣可證前序遍歷序列ai+1ai+2… ak+1和中序遍歷序列bi+1bi+2… bk+1唯一確定了根結(jié)點(diǎn)的右子樹。

6．已知一棵度為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=0×n0+1×n1+2×n2+……+m×nm+1 由上述兩式可得：

n0= n2+2n3+……+(m-1)nm+1 7．已知二叉樹的中序和后序序列分別為CBEDAFIGH和CEDBIFHGA，試構(gòu)造該二叉樹。【解答】二叉樹的構(gòu)造過程如圖5-12 所示。

8．對(duì)給定的一組權(quán)值W＝（5，2，9，11，8，3，7），試構(gòu)造相應(yīng)的哈夫曼樹，并計(jì)算它的帶權(quán)路徑長(zhǎng)度。

【解答】構(gòu)造的哈夫曼樹如圖5-13所示。

樹的帶權(quán)路徑長(zhǎng)度為：

WPL=2×4+3×4+5×3+7×3+8×3+9×2+11×2 =120 9．已知某字符串S中共有8種字符，各種字符分別出現(xiàn)2次、1次、4次、5次、7次、3次、4次和9次，對(duì)該字符串用[0，1]進(jìn)行前綴編碼，問該字符串的編碼至少有多少位。

【解答】以各字符出現(xiàn)的次數(shù)作為葉子結(jié)點(diǎn)的權(quán)值構(gòu)造的哈夫曼編碼樹如圖5-14所示。其帶權(quán)路徑長(zhǎng)度=2×5+1×5+3×4+5×3+9×2+4×3+4×3+7×2=98，所以，該字符串的編碼長(zhǎng)度至少為98位。

10．算法設(shè)計(jì) ⑴ 設(shè)計(jì)算法求二叉樹的結(jié)點(diǎn)個(gè)數(shù)。

【解答】本算法不是要打印每個(gè)結(jié)點(diǎn)的值，而是求出結(jié)點(diǎn)的個(gè)數(shù)。所以可將遍歷算法中的―訪問‖操作改為―計(jì)數(shù)操作‖，將結(jié)點(diǎn)的數(shù)目累加到一個(gè)全局變量中，每個(gè)結(jié)點(diǎn)累加一次即完成了結(jié)點(diǎn)個(gè)數(shù)的求解。具體算法如下：

⑵ 設(shè)計(jì)算法按前序次序打印二叉樹中的葉子結(jié)點(diǎn)。

【解答】本算法的要求與前序遍歷算法既有相同之處，又有不同之處。相同之處是打印次序均為前序，不同之處是此處不是打印每個(gè)結(jié)點(diǎn)的值，而是打印出其中的葉子結(jié)點(diǎn)，即為有條件打印。為此，將前序遍歷算法中的訪問操作改為條件打印即可。算法如下：

⑶ 設(shè)計(jì)算法求二叉樹的深度。

【解答】當(dāng)二叉樹為空時(shí)，深度為0；若二叉樹不為空，深度應(yīng)是其左右子樹深度的最大值加1，而其左右子樹深度的求解又可通過遞歸調(diào)用本算法來完成。具體算法如下：

⑷ 編寫算法，要求輸出二叉樹后序遍歷序列的逆序。

【解答】要想得到后序的逆序，只要按照后序遍歷相反的順序即可，即先訪問根結(jié)點(diǎn)，再遍歷根結(jié)點(diǎn)的右子樹，最后遍歷根結(jié)點(diǎn)的左子樹。注意和前序遍歷的區(qū)別，具體算法如下：

⑸ 以二叉鏈表為存儲(chǔ)結(jié)構(gòu)，編寫算法求二叉樹中結(jié)點(diǎn)x的雙親。

【解答】對(duì)二叉鏈表進(jìn)行遍歷，在遍歷的過程中查找結(jié)點(diǎn)x并記載其雙親。具體算法如下：

⑹ 以二叉鏈表為存儲(chǔ)結(jié)構(gòu)，在二叉樹中刪除以值x為根結(jié)點(diǎn)的子樹。

【解答】對(duì)二叉鏈表進(jìn)行遍歷，在遍歷的過程中查找結(jié)點(diǎn)x并記載其雙親，然后將結(jié)點(diǎn)x的雙親結(jié)點(diǎn)中指向結(jié)點(diǎn)x的指針置空。具體算法如下：

⑺ 一棵具有n個(gè)結(jié)點(diǎn)的二叉樹采用順序存儲(chǔ)結(jié)構(gòu)，編寫算法對(duì)該二叉樹進(jìn)行前序遍歷?！窘獯稹堪凑疹}目要求，設(shè)置一個(gè)工作棧以完成對(duì)該樹的非遞歸算法，思路如下：

① 每訪問一個(gè)結(jié)點(diǎn)，將此結(jié)點(diǎn)壓棧，查看此結(jié)點(diǎn)是否有左子樹，若有，訪問左子樹，重復(fù)執(zhí)行該過程直到左子樹為空。

② 從棧彈出一個(gè)結(jié)點(diǎn)，如果此結(jié)點(diǎn)有右子樹，訪問右子樹執(zhí)行步驟①，否則重復(fù)執(zhí)行步驟②。具體算法如下：

⑻ 編寫算法交換二叉樹中所有結(jié)點(diǎn)的左右子樹。

【解答】對(duì)二叉樹進(jìn)行后序遍歷，在遍歷過程中訪問某結(jié)點(diǎn)時(shí)交換該結(jié)點(diǎn)的左右子樹。具體算法如下：

⑼ 以孩子兄弟表示法做存儲(chǔ)結(jié)構(gòu)，求樹中結(jié)點(diǎn)x的第i個(gè)孩子。

【解答】先在鏈表中進(jìn)行遍歷，在遍歷過程中查找值等于x的結(jié)點(diǎn)，然后由此結(jié)點(diǎn)的最左孩子域firstchild找到值為x結(jié)點(diǎn)的第一個(gè)孩子，再沿右兄弟域rightsib找到值為x結(jié)點(diǎn)的第i個(gè)孩子并返回指向這個(gè)孩子的指針。

樹的孩子兄弟表示法中的結(jié)點(diǎn)結(jié)構(gòu)定義如下： template struct TNode { T data;TNode *firstchild, *rightsib;};具體算法如下：

學(xué)習(xí)自測(cè)及答案

1．前序遍歷和中序遍歷結(jié)果相同的二叉樹是（）。A 根結(jié)點(diǎn)無左孩子的二叉樹 B 根結(jié)點(diǎn)無右孩子的二叉樹

C 所有結(jié)點(diǎn)只有左子樹的二叉樹 D 所有結(jié)點(diǎn)只有右子樹的二叉樹 【解答】D 1．前序遍歷和中序遍歷結(jié)果相同的二叉樹是（）。A 根結(jié)點(diǎn)無左孩子的二叉樹 B 根結(jié)點(diǎn)無右孩子的二叉樹 C 所有結(jié)點(diǎn)只有左子樹的二叉樹 D 所有結(jié)點(diǎn)只有右子樹的二叉樹【解答】D

2．由權(quán)值為{3, 8, 6, 2, 5}的葉子結(jié)點(diǎn)生成一棵哈夫曼樹，其帶權(quán)路徑長(zhǎng)度為（）。A 24 B 48 C 53 D 72 【解答】C

3．用順序存儲(chǔ)的方法將完全二叉樹中的所有結(jié)點(diǎn)逐層存放在數(shù)組A[1] ~ A[n]中，結(jié)點(diǎn)A[i]若有左子樹，則左子樹的根結(jié)點(diǎn)是（）。

A A[2i-1] B A[2i+1] C A[i/2] D A[2i] 【解答】D

4．對(duì)任何一棵二叉樹T，如果其終端結(jié)點(diǎn)的個(gè)數(shù)為n0，度為2的結(jié)點(diǎn)個(gè)數(shù)為n2，則（）。A n0=n2-1 B n0=n2 C n0=n2+1 D 沒有規(guī)律 【解答】C

5．一棵滿二叉樹中共有n個(gè)結(jié)點(diǎn)，其中有m個(gè)葉子結(jié)點(diǎn)，深度為h，則（）。A n=h+m B h+m=2n C m=h-1 D n=2h-1 【解答】D

6．對(duì)于完全二叉樹中的任一結(jié)點(diǎn)，若其右分支下的子孫的最大層次為h，則其左分支下的子孫的最大層次為（）。

A h B h+1 C h或h+1 D 任意 【解答】C

7．假定一棵度為3的樹中結(jié)點(diǎn)數(shù)為50，則其最小高度應(yīng)為。A 3 B 4 C 5 D 6 【解答】C

8．在線索二叉樹中，一個(gè)結(jié)點(diǎn)是葉子結(jié)點(diǎn)的充要條件為（）。A 左線索標(biāo)志為0，右線索標(biāo)志為1 B 左線索標(biāo)志為1，右線索標(biāo)志為0 C 左、右線索標(biāo)志均為0 D 左、右線索標(biāo)志均為1 【解答】C

9．對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的樹，其所有結(jié)點(diǎn)的度之和為（）。【解答】n-1

10．在順序存儲(chǔ)的二叉樹中，編號(hào)為i和j的兩個(gè)結(jié)點(diǎn)處在同一層的條件是（）?！窘獯稹?/p>

11．現(xiàn)有按前序遍歷二叉樹的結(jié)果ABC，問有哪幾種不同的二叉樹可以得到這一結(jié)果？ 【解答】共有5種二叉樹可以得到這一結(jié)果，如圖5-15所示。

12．試找出分別滿足下列條件的所有二叉樹： ⑴ 前序序列和中序序列相同。⑵ 中序序列和后序序列相同。⑶ 前序序列和后序序列相同。

【解答】 ⑴ 空二叉樹、只有一個(gè)根結(jié)點(diǎn)的二叉樹和右斜樹。⑵ 空二叉樹、只有一個(gè)根結(jié)點(diǎn)的二叉樹和左斜樹。⑶ 空二叉樹、只有一個(gè)根結(jié)點(diǎn)的二叉樹

13．將下面圖5-16所示的樹轉(zhuǎn)換為二叉樹，圖5-17所示的二叉樹轉(zhuǎn)換為樹或森林。

【解答】圖5-16所示樹轉(zhuǎn)換的二叉樹如圖5-18所示，圖5-17所示二叉樹轉(zhuǎn)換的森林如圖5-19所示。

14．以孩子兄弟表示法作為存儲(chǔ)結(jié)構(gòu)，編寫算法求樹的深度。

【解答】采用遞歸算法實(shí)現(xiàn)。若樹為空樹，則其深度為0，否則其深度等于第一棵子樹的深度+1和兄弟子樹的深度中的較大者。具體算法如下：

15．設(shè)計(jì)算法，判斷一棵二叉樹是否為完全二叉樹。

【解答】根據(jù)完全二叉樹的定義可知，對(duì)完全二叉樹按照從上到下、從左到右的次序（即層序）遍歷應(yīng)該滿足： ⑴ 若某結(jié)點(diǎn)沒有左孩子，則其一定沒有右孩子； ⑵ 若某結(jié)點(diǎn)無右孩子，則其所有后繼結(jié)點(diǎn)一定無孩子。

若有一結(jié)點(diǎn)不滿足其中任意一條，則該二叉樹就一定不是完全二叉樹。因此可采用按層次遍歷二叉樹的方法依次對(duì)每個(gè)結(jié)點(diǎn)進(jìn)行判斷是否滿足上述兩個(gè)條件。為此，需設(shè)兩個(gè)標(biāo)志變量BJ和CM，其中BJ表示已掃描過的結(jié)點(diǎn)是否均有左右孩子，CM存放局部判斷結(jié)果及最后的結(jié)果。具體算法如下：

第 6 章 圖

課后習(xí)題講解

1.填空題

⑴ 設(shè)無向圖G中頂點(diǎn)數(shù)為n，則圖G至少有（）條邊，至多有（）條邊；若G為有向圖，則至少有（）條邊，至多有（）條邊?！窘獯稹?，n(n-1)/2，0，n(n-1)【分析】圖的頂點(diǎn)集合是有窮非空的，而邊集可以是空集；邊數(shù)達(dá)到最多的圖稱為完全圖，在完全圖中，任意兩個(gè)頂點(diǎn)之間都存在邊。

⑵ 任何連通圖的連通分量只有一個(gè)，即是（）?！窘獯稹科渥陨?⑶ 圖的存儲(chǔ)結(jié)構(gòu)主要有兩種，分別是（）和（）。【解答】鄰接矩陣，鄰接表

【分析】這是最常用的兩種存儲(chǔ)結(jié)構(gòu)，此外，還有十字鏈表、鄰接多重表、邊集數(shù)組等。⑷ 已知無向圖G的頂點(diǎn)數(shù)為n，邊數(shù)為e，其鄰接表表示的空間復(fù)雜度為（）。【解答】Ｏ(n+e)【分析】在無向圖的鄰接表中，頂點(diǎn)表有n個(gè)結(jié)點(diǎn)，邊表有2e個(gè)結(jié)點(diǎn)，共有n+2e個(gè)結(jié)點(diǎn)，其空間復(fù)雜度為Ｏ(n+2e)=Ｏ(n+e)。

⑸ 已知一個(gè)有向圖的鄰接矩陣表示，計(jì)算第j個(gè)頂點(diǎn)的入度的方法是（）。【解答】求第j列的所有元素之和

⑹ 有向圖G用鄰接矩陣A[n][n]存儲(chǔ)，其第i行的所有元素之和等于頂點(diǎn)i的（）?！窘獯稹砍龆?/p>

⑺ 圖的深度優(yōu)先遍歷類似于樹的（）遍歷，它所用到的數(shù)據(jù)結(jié)構(gòu)是（）；圖的廣度優(yōu)先遍歷類似于樹的（）遍歷，它所用到的數(shù)據(jù)結(jié)構(gòu)是（）?！窘獯稹壳靶?，棧，層序，隊(duì)列

⑻ 對(duì)于含有n個(gè)頂點(diǎn)e條邊的連通圖，利用Prim算法求最小生成樹的時(shí)間復(fù)雜度為（），利用Kruskal算法求最小生成樹的時(shí)間復(fù)雜度為（）?！窘獯稹浚?n2)，Ｏ(elog2e)【分析】Prim算法采用鄰接矩陣做存儲(chǔ)結(jié)構(gòu)，適合于求稠密圖的最小生成樹；Kruskal算法采用邊集數(shù)組做存儲(chǔ)結(jié)構(gòu)，適合于求稀疏圖的最小生成樹。

⑼ 如果一個(gè)有向圖不存在（），則該圖的全部頂點(diǎn)可以排列成一個(gè)拓?fù)湫蛄??！窘獯稹炕芈?/p>

⑽ 在一個(gè)有向圖中，若存在弧、、，則在其拓?fù)湫蛄兄校旤c(diǎn)vi, vj, vk的相對(duì)次序?yàn)椋ǎ??！窘獯稹縱i, vj, vk 【分析】對(duì)由頂點(diǎn)vi, vj, vk組成的圖進(jìn)行拓?fù)渑判颉?.選擇題

⑴ 在一個(gè)無向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的（）倍。A 1/2 B 1 C 2 D 4 【解答】C 【分析】設(shè)無向圖中含有n個(gè)頂點(diǎn)e條邊，則。

⑵ n個(gè)頂點(diǎn)的強(qiáng)連通圖至少有（）條邊，其形狀是（）。A n B n+1 C n-1 D n×(n-1)E 無回路

F 有回路

G 環(huán)狀

H 樹狀 【解答】A，G ⑶ 含n 個(gè)頂點(diǎn)的連通圖中的任意一條簡(jiǎn)單路徑，其長(zhǎng)度不可能超過（）。A 1 B n/2 C n-1 D n 【解答】C 【分析】若超過n-1，則路徑中必存在重復(fù)的頂點(diǎn)。

⑷ 對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的無向圖，若采用鄰接矩陣存儲(chǔ)，則該矩陣的大小是（）。A n B(n-1)2 C n-1 D n2 【解答】D ⑸ 圖的生成樹（），n個(gè)頂點(diǎn)的生成樹有（）條邊。A 唯一

B 不唯一

C 唯一性不能確定 D n E n +1 F n-1 【解答】C，F(xiàn) ⑹ 設(shè)無向圖G=(V, E)和G' =(V', E')，如果G' 是G的生成樹，則下面的說法中錯(cuò)誤的是（）。A G' 為 G的子圖 B G' 為 G的連通分量

C G' 為G的極小連通子圖且V = V' D G' 是G的一個(gè)無環(huán)子圖 【解答】B 【分析】連通分量是無向圖的極大連通子圖，其中極大的含義是將依附于連通分量中頂點(diǎn)的所有邊都加上，所以，連通分量中可能存在回路。

⑺ G是一個(gè)非連通無向圖，共有28條邊，則該圖至少有（）個(gè)頂點(diǎn)。A 6 B 7 C 8 D 9 【解答】D 【分析】n個(gè)頂點(diǎn)的無向圖中，邊數(shù)e≤n(n-1)/2，將e=28代入，有n≥8，現(xiàn)已知無向圖非連通，則n=9。⑻ 最小生成樹指的是（）。A 由連通網(wǎng)所得到的邊數(shù)最少的生成樹 B 由連通網(wǎng)所得到的頂點(diǎn)數(shù)相對(duì)較少的生成樹 C 連通網(wǎng)中所有生成樹中權(quán)值之和為最小的生成樹 D 連通網(wǎng)的極小連通子圖

⑼ 判定一個(gè)有向圖是否存在回路除了可以利用拓?fù)渑判蚍椒ㄍ?，還可以用（）。A 求關(guān)鍵路徑的方法

B 求最短路徑的方法 C 廣度優(yōu)先遍歷算法

D 深度優(yōu)先遍歷算法 【解答】D 【分析】當(dāng)有向圖中無回路時(shí)，從某頂點(diǎn)出發(fā)進(jìn)行深度優(yōu)先遍歷時(shí)，出棧的順序（退出DFSTraverse算法）即為逆向的拓?fù)湫蛄小?/p>

⑽ 下面關(guān)于工程計(jì)劃的AOE網(wǎng)的敘述中，不正確的是（）?br /> A 關(guān)鍵活動(dòng)不按期完成就會(huì)影響整個(gè)工程的完成時(shí)間

B 任何一個(gè)關(guān)鍵活動(dòng)提前完成，那么整個(gè)工程將會(huì)提前完成 C 所有的關(guān)鍵活動(dòng)都提前完成，那么整個(gè)工程將會(huì)提前完成 D 某些關(guān)鍵活動(dòng)若提前完成，那么整個(gè)工程將會(huì)提前完 【解答】B 【分析】AOE網(wǎng)中的關(guān)鍵路徑可能不止一條，如果某一個(gè)關(guān)鍵活動(dòng)提前完成，還不能提前整個(gè)工程，而必須同時(shí)提高在幾條關(guān)鍵路徑上的關(guān)鍵活動(dòng)。3.判斷題

⑴ 一個(gè)有向圖的鄰接表和逆鄰接表中的結(jié)點(diǎn)個(gè)數(shù)一定相等。

【解答】對(duì)。鄰接表和逆鄰接表的區(qū)別僅在于出邊和入邊，邊表中的結(jié)點(diǎn)個(gè)數(shù)都等于有向圖中邊的個(gè)數(shù)。⑵ 用鄰接矩陣存儲(chǔ)圖，所占用的存儲(chǔ)空間大小只與圖中頂點(diǎn)個(gè)數(shù)有關(guān)，而與圖的邊數(shù)無關(guān)?！窘獯稹繉?duì)。鄰接矩陣的空間復(fù)雜度為Ｏ(n2)，與邊的個(gè)數(shù)無關(guān)。⑶ 圖G的生成樹是該圖的一個(gè)極小連通子圖 【解答】錯(cuò)。必須包含全部頂點(diǎn)。

⑷ 無向圖的鄰接矩陣一定是對(duì)稱的，有向圖的鄰接矩陣一定是不對(duì)稱的

【解答】錯(cuò)。有向圖的鄰接矩陣不一定對(duì)稱，例如有向完全圖的鄰接矩陣就是對(duì)稱的。⑸ 對(duì)任意一個(gè)圖，從某頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先或廣度優(yōu)先遍歷，可訪問圖的所有頂點(diǎn)。【解答】錯(cuò)。只有連通圖從某頂點(diǎn)出發(fā)進(jìn)行一次遍歷，可訪問圖的所有頂點(diǎn)。⑹ 在一個(gè)有向圖的拓?fù)湫蛄兄?，若頂點(diǎn)a在頂點(diǎn)b之前，則圖中必有一條弧。【解答】錯(cuò)。只能說明從頂點(diǎn)a到頂點(diǎn)b有一條路徑。

⑺ 若一個(gè)有向圖的鄰接矩陣中對(duì)角線以下元素均為零，則該圖的拓?fù)湫蛄斜囟ù嬖凇！窘獯稹繉?duì)。參見第11題的證明。

⑻ 在AOE網(wǎng)中一定只有一條關(guān)鍵路徑?br />【解答】錯(cuò)。AOE網(wǎng)中可能有不止一條關(guān)鍵路徑，他們的路徑長(zhǎng)度相同。

4．n個(gè)頂點(diǎn)的無向圖，采用鄰接表存儲(chǔ)，回答下列問題?br />⑴ 圖中有多少條邊？ ⑵ 任意兩個(gè)頂點(diǎn)i和j是否有邊相連？ ⑶ 任意一個(gè)頂點(diǎn)的度是多少?br />【解答】 ⑴ 邊表中的結(jié)點(diǎn)個(gè)數(shù)之和除以2。⑵ 第i個(gè)邊表中是否含有結(jié)點(diǎn)j。⑶ 該頂點(diǎn)所對(duì)應(yīng)的邊表中所含結(jié)點(diǎn)個(gè)數(shù)。

5．n個(gè)頂點(diǎn)的無向圖，采用鄰接矩陣存儲(chǔ)，回答下列問題： ⑴ 圖中有多少條邊？

⑵ 任意兩個(gè)頂點(diǎn)i和j是否有邊相連？ ⑶ 任意一個(gè)頂點(diǎn)的度是多少？ 【解答】

⑴ 鄰接矩陣中非零元素個(gè)數(shù)的總和除以2。

⑵ 當(dāng)鄰接矩陣A中A[i][j]=1（或A[j][i]=1）時(shí)，表示兩頂點(diǎn)之間有邊相連。⑶ 計(jì)算鄰接矩陣上該頂點(diǎn)對(duì)應(yīng)的行上非零元素的個(gè)數(shù)。6．證明：生成樹中最長(zhǎng)路徑的起點(diǎn)和終點(diǎn)的度均為１?！窘獯稹坑梅醋C法證明。

設(shè)v1, v2, …, vk是生成樹的一條最長(zhǎng)路徑，其中，v1為起點(diǎn)，vk為終點(diǎn)。若vk的度為2，取vk的另一個(gè)鄰接點(diǎn)v，由于生成樹中無回路，所以，v在最長(zhǎng)路徑上，顯然v1, v2, …, vk , v的路徑最長(zhǎng)，與假設(shè)矛盾。所以生成樹中最長(zhǎng)路徑的終點(diǎn)的度為1。同理可證起點(diǎn)v1的度不能大于1，只能為1。

7．已知一個(gè)連通圖如圖6-6所示，試給出圖的鄰接矩陣和鄰接表存儲(chǔ)示意圖，若從頂點(diǎn)v1出發(fā)對(duì)該圖進(jìn)行遍歷，分別給出一個(gè)按深度優(yōu)先遍歷和廣度優(yōu)先遍歷的頂點(diǎn)序列。

【解答】鄰接矩陣表示如下：

深度優(yōu)先遍歷序列為：v1 v2 v3 v5 v4 v6 廣度優(yōu)先遍歷序列為：v1 v2 v4 v6 v3 v5 鄰接表表示如下：

8．圖6-7所示是一個(gè)無向帶權(quán)圖，請(qǐng)分別按Prim算法和Kruskal算法求最小生成樹。

【解答】按Prim算法求最小生成樹的過程如下：

按Kruskal算法求最小生成樹的過程如下：

9．對(duì)于圖6-8所示的帶權(quán)有向圖，求從源點(diǎn)v1到其他各頂點(diǎn)的最短路徑。

【解答】從源點(diǎn)v1到其他各頂點(diǎn)的最短路徑如下表所示。源點(diǎn) 終點(diǎn) 最短路徑 最短路徑長(zhǎng)度 v1 v7 v1 v7 7 v1 v5 v1 v5 11 v1 v4 v1 v7 v4 13 v1 v6 v1 v7 v4 v6 16 v1 v2 v1 v7 v2 22 v1 v3 v1 v7 v4 v6 v3 25 10．如圖6-9所示的有向網(wǎng)圖，利用Dijkstra算法求從頂點(diǎn)v1到其他各頂點(diǎn)的最短路徑。

【解答】從源點(diǎn)v1到其他各頂點(diǎn)的最短路徑如下表所示。源點(diǎn) 終點(diǎn) 最短路徑 最短路徑長(zhǎng)度 v1 v3 v1 v3 15 v1 v5 v1 v5 15 v1 v2 v1 v3 v2 25 v1 v6 v1 v3 v2 v6 40 v1 v4 v1 v3 v2 v4 45 11．證明：只要適當(dāng)?shù)嘏帕许旤c(diǎn)的次序，就能使有向無環(huán)圖的鄰接矩陣中主對(duì)角線以下的元素全部為0。【解答】任意n個(gè)結(jié)點(diǎn)的有向無環(huán)圖都可以得到一個(gè)拓?fù)湫蛄?。設(shè)拓?fù)湫蛄袨関0v1v2…vn-1，我們來證明此時(shí)的鄰接矩陣A為上三角矩陣。證明采用反證法。

假設(shè)此時(shí)的鄰接矩陣不是上三角矩陣，那么，存在下標(biāo)i和j（i>j），使得A[i][j]不等于零，即圖中存在從vi到vj的一條有向邊。由拓?fù)湫蛄械亩x可知，在任意拓?fù)湫蛄兄?，vi的位置一定在vj之前，而在上述拓?fù)湫蛄衯0v1v2…vn-1中，由于i>j，即vi的位置在vj之后，導(dǎo)致矛盾。因此命題正確。12.算法設(shè)計(jì)

⑴ 設(shè)計(jì)算法，將一個(gè)無向圖的鄰接矩陣轉(zhuǎn)換為鄰接表。

【解答】先設(shè)置一個(gè)空的鄰接表，然后在鄰接矩陣上查找值不為零的元素，找到后在鄰接表的對(duì)應(yīng)單鏈表中插入相應(yīng)的邊表結(jié)點(diǎn)。鄰接矩陣存儲(chǔ)結(jié)構(gòu)定義如下： const int MaxSize=10;template struct AdjMatrix {

T vertex[MaxSize];//存放圖中頂點(diǎn)的數(shù)組 int arc[MaxSize][MaxSize];//存放圖中邊的數(shù)組 int vertexNum, arcNum;//圖的頂點(diǎn)數(shù)和邊數(shù) };鄰接表存儲(chǔ)結(jié)構(gòu)定義如下： const int MaxSize=10;struct ArcNode //定義邊表結(jié)點(diǎn) { int adjvex;//鄰接點(diǎn)域 ArcNode *next;};template

struct VertexNode //定義頂點(diǎn)表結(jié)點(diǎn) { T vertex;ArcNode *firstedge;};struct AdjList { VertexNode adjlist[MaxSize];int vertexNum, arcNum;//圖的頂點(diǎn)數(shù)和邊數(shù) };具體算法如下：

第三篇：數(shù)據(jù)結(jié)構(gòu)查找實(shí)驗(yàn)報(bào)告

實(shí)驗(yàn)題9.1 設(shè)計(jì)一個(gè)程序exp9-1.cpp，輸出在順序表{3，6，2，10，1，8，5，7，4，9}中采用順序方法找關(guān)鍵字5的過程。程序如下：

//文件名:exp9-1.cpp #include #define MAXL 100 typedef int KeyType;typedef char InfoType[10];typedef struct {

KeyType key;

//KeyType為關(guān)鍵字的數(shù)據(jù)類型 //其他數(shù)據(jù)

//定義表中最多記錄個(gè)數(shù)

InfoType data;

} NodeType;typedef NodeType SeqList[MAXL];

//順序表類型

int SeqSearch(SeqList R,int n,KeyType k)//順序查找算法

{

int i=0;

while(i

{

} printf(“%d ”,R[i].key);i++;

//從表頭往后找

if(i>=n)return-1;

else

} void main(){ SeqList R;{

} printf(“%d”,R[i].key);return i;

} int n=10,i;KeyType k=5;int a[]={3,6,2,10,1,8,5,7,4,9};for(i=0;i

//建立順序表

printf(“關(guān)鍵字序列:”);for(i=0;i

截圖如下：

實(shí)驗(yàn)題9.2 設(shè)計(jì)一個(gè)程序exp9-2.cpp，輸出在順序表{1，2，3，4，5，6，7，8，9，10}中采用折半查找法查找關(guān)鍵字9的過程。

程序如下：

//文件名:exp9-2.cpp #include #define MAXL 100 typedef int KeyType;typedef char InfoType[10];typedef struct {

//定義表中最多記錄個(gè)數(shù) KeyType key;

//KeyType為關(guān)鍵字的數(shù)據(jù)類型

InfoType data;

//其他數(shù)據(jù) } NodeType;typedef NodeType SeqList[MAXL];

//順序表類型

int BinSearch(SeqList R,int n,KeyType k)//二分查找算法 { int low=0,high=n-1,mid,count=0;while(low<=high)

{

mid=(low+high)/2;printf(“ 第%d

次

比

較

:在[%d,%d]R[%d]:%dn”,++count,low,high,mid,R[mid].key);

if(R[mid].key==k)

//查找成功返回

return mid;

if(R[mid].key>k)

//繼續(xù)在R[low..mid-1]中查找

high=mid-1;

else

low=mid+1;

//繼續(xù)在R[mid+1..high]中查找 } return-1;} void main(){ SeqList R;KeyType k=9;int a[]={1,2,3,4,5,6,7,8,9,10},i,n=10;for(i=0;i

//建立順序表

R[i].key=a[i];printf(“關(guān)鍵字序列:”);for(i=0;i

比

較

元

素

中

} else printf(“元素%d的位置是%dn”,k,i);printf(“元素%d不在表中n”,k);

截圖如下：

實(shí)驗(yàn)題9.3 設(shè)計(jì)一個(gè)程序exp9-3.cpp，輸出在順序表{8，14，6，9，10,22,34,18,19,31,40,38,54,66,46,71,78,68,80,85,100,94,88,96,87}中采用分塊查找法查找（每塊的塊長(zhǎng)為5，共5塊）關(guān)鍵字46的過程。

程序如下：

//文件名:exp9-3.cpp #include #define MAXL 100 #define MAXI 20 typedef int KeyType;typedef char InfoType[10];typedef struct {

KeyType key;

//KeyType為關(guān)鍵字的數(shù)據(jù)類型

//定義表中最多記錄個(gè)數(shù)

//定義索引表的最大長(zhǎng)度

InfoType data;

//其他數(shù)據(jù) } NodeType;typedef NodeType SeqList[MAXL];typedef struct {

KeyType key;int link;

//KeyType為關(guān)鍵字的類型 //指向分塊的起始下標(biāo)

//順序表類型

} IdxType;typedef IdxType IDX[MAXI];

//索引表類型

int IdxSearch(IDX I,int m,SeqList R,int n,KeyType k)//分塊查找算法 { int low=0,high=m-1,mid,i,count1=0,count2=0;int b=n/m;

//b為每塊的記錄個(gè)數(shù)

printf(“二分查找n”);while(low<=high)

//在索引表中進(jìn)行二分查找,找到的位置存放在low中

{

mid=(low+high)/2;printf(“ 第%d

次

比

較

:在[%d,%d]

中

比

較

元R[%d]:%dn”,count1+1,low,high,mid,R[mid].key);

if(I[mid].key>=k)

high=mid-1;

else

low=mid+1;

count1++;

//累計(jì)在索引表中的比較次數(shù)

} if(low

//在索引表中查找成功后,再在線性表中進(jìn)行順序查找

{

printf(“比較%d次,在第%d塊中查找元素%dn”,count1,low,k);

i=I[low].link;

printf(“順序查找:n

”);

while(i<=I[low].link+b-1 && R[i].key!=k)

{

i++;count2++;

printf(“%d ”,R[i].key);} //count2累計(jì)在順序表對(duì)應(yīng)塊中的比較次數(shù)

printf(“n”);

printf(“比較%d次,在順序表中查找元素%dn”,count2,k);

if(i<=I[low].link+b-1)

return i;

else

return-1;}

素 } return-1;void main(){

} SeqList R;KeyType k=46;IDX I;int a[]={8,14,6,9,10,22,34,18,19,31,40,38,54,66,46,71,78,68,80,85,100,94,88,96,87},i;for(i=0;i<25;i++)R[i].key=a[i];

//建立順序表

I[0].key=14;I[0].link=0;I[1].key=34;I[1].link=4;I[2].key=66;I[2].link=10;I[3].key=85;I[3].link=15;I[4].key=100;I[4].link=20;if((i=IdxSearch(I,5,R,25,k))!=-1)else printf(“元素%d不在表中n”,k);printf(“元素%d的位置是%dn”,k,i);printf(“n”);

截圖如下：

第四篇：數(shù)據(jù)結(jié)構(gòu)課后習(xí)題答案總結(jié)

第一章

第1章作業(yè)：1.1,1.2,1.6(1)(3)1.8 1.1 簡(jiǎn)述下列概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)類型、數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、線性結(jié)構(gòu)、非線性結(jié)構(gòu)?！?數(shù)據(jù)：指能夠被計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理的信息載體。

● 數(shù)據(jù)元素：就是數(shù)據(jù)的基本單位，在某些情況下，數(shù)據(jù)元素也稱為元素、結(jié)點(diǎn)、頂點(diǎn)、記錄。數(shù)據(jù)元素有時(shí)可以由若干數(shù)據(jù)項(xiàng)組成。

● 數(shù)據(jù)類型：是一個(gè)值的集合以及在這些值上定義的一組操作的總稱。通常數(shù)據(jù)類型可以看作是程序設(shè)計(jì)語言中已實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)。

● 數(shù)據(jù)結(jié)構(gòu)：指的是數(shù)據(jù)之間的相互關(guān)系，即數(shù)據(jù)的組織形式。一般包括三個(gè)方面的內(nèi)容:數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算。

● 邏輯結(jié)構(gòu)：指數(shù)據(jù)元素之間的邏輯關(guān)系。

● 存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲(chǔ)器內(nèi)的表示，稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu).● 線性結(jié)構(gòu)：數(shù)據(jù)邏輯結(jié)構(gòu)中的一類。它的特征是若結(jié)構(gòu)為非空集，則該結(jié)構(gòu)有且只有一個(gè)開始結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)，并且所有結(jié)點(diǎn)都有且只有一個(gè)直接前趨和一個(gè)直接后繼。線性表就是一個(gè)典型的線性結(jié)構(gòu)。棧、隊(duì)列、串等都是線性結(jié)構(gòu)?！?非線性結(jié)構(gòu)：數(shù)據(jù)邏輯結(jié)構(gòu)中的另一大類，它的邏輯特征是一個(gè)結(jié)點(diǎn)可能有多個(gè)直接前趨和直接后繼。數(shù)組、廣義表、樹和圖等數(shù)據(jù)結(jié)構(gòu)都是非線性結(jié)構(gòu)。

1.2 試舉一個(gè)數(shù)據(jù)結(jié)構(gòu)的例子、敘述其邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、運(yùn)算三個(gè)方面的內(nèi)容。

答：例如有一張學(xué)生體檢情況登記表，記錄了一個(gè)班的學(xué)生的身高、體重等各項(xiàng)體檢信息。這張登記表中，每個(gè)學(xué)生的各項(xiàng)體檢信息排在一行上。這個(gè)表就是一個(gè)數(shù)據(jù)結(jié)構(gòu)。每個(gè)記錄(有姓名，學(xué)號(hào)，身高和體重等字段)就是一個(gè)結(jié)點(diǎn)，對(duì)于整個(gè)表來說，只有一個(gè)開始結(jié)點(diǎn)(它的前面無記錄)和一個(gè)終端結(jié)點(diǎn)(它的后面無記錄)，其他的結(jié)點(diǎn)則各有一個(gè)也只有一個(gè)直接前趨和直接后繼(它的前面和后面均有且只有一個(gè)記錄)。這幾個(gè)關(guān)系就確定了這個(gè)表的邏輯結(jié)構(gòu)是線性結(jié)構(gòu)。

這個(gè)表中的數(shù)據(jù)如何存儲(chǔ)到計(jì)算機(jī)里，并且如何表示數(shù)據(jù)元素之間的關(guān)系呢? 即用一片連續(xù)的內(nèi)存單元來存放這些記錄(如用數(shù)組表示)還是隨機(jī)存放各結(jié)點(diǎn)數(shù)據(jù)再用指針進(jìn)行鏈接呢? 這就是存儲(chǔ)結(jié)構(gòu)的問題。

在這個(gè)表的某種存儲(chǔ)結(jié)構(gòu)基礎(chǔ)上，可實(shí)現(xiàn)對(duì)這張表中的記錄進(jìn)行查詢，修改，刪除等操作。對(duì)這個(gè)表可以進(jìn)行哪些操作以及如何實(shí)現(xiàn)這些操作就是數(shù)據(jù)的運(yùn)算問題了。

1.6 設(shè)n為正整數(shù)，利用大“O”記號(hào)，將下列程序段的執(zhí)行時(shí)間表示為n的函數(shù)。

(1)i=1;k=0;while(ij)j++;else i++;} 分析：

通過分析以上程序段，可將i+j看成一個(gè)控制循環(huán)次數(shù)的變量，且每執(zhí)行一次循環(huán)，i+j的值加1。該程序段的主要時(shí)間消耗是while循環(huán)，而while循環(huán)共做了n次，所以該程序段的執(zhí)行時(shí)間為：

T(n)=O(n)

1.8 按增長(zhǎng)率由小至大的順序排列下列各函數(shù)：2100,(3/2)n，(2/3)n，nn ,n0.5 , n!，2n，lgn ,nlgn, n(3/2)

答：常見的時(shí)間復(fù)雜度按數(shù)量級(jí)遞增排列,依次為:常數(shù)階0(1)、對(duì)數(shù)階0(log2n)、線性階0(n)、線性對(duì)數(shù)階0(nlog2n)、平方階0(n2)、立方階0(n3)、k次方階0(nk)、指數(shù)階0(2n)。先將題中的函數(shù)分成如下幾類：

常數(shù)階：2 對(duì)數(shù)階：lgn K次方階：n、n0.5(3/2)100

指數(shù)階(按指數(shù)由小到大排)：nlgn、(3/2)n、2n、n!、nn

注意：(2/3)^n由于底數(shù)小于1，所以是一個(gè)遞減函數(shù)，其數(shù)量級(jí)應(yīng)小于常數(shù)階。

根據(jù)以上分析按增長(zhǎng)率由小至大的順序可排列如下：(2/3)n < 2100 < lgn < n0.5 < n(3/2)< nlgn <(3/2)n < 2n < n!< nn

第二章

第二章作業(yè)：2.2，2.6,2.9,2.13 2.2 何時(shí)選用順序表、何時(shí)選用鏈表作為線性表的存儲(chǔ)結(jié)構(gòu)為宜? 答：在實(shí)際應(yīng)用中，應(yīng)根據(jù)具體問題的要求和性質(zhì)來選擇順序表或鏈表作為線性表的存儲(chǔ)結(jié)構(gòu)，通常有以下幾方面的考慮： 1.基于空間的考慮。當(dāng)要求存儲(chǔ)的線性表長(zhǎng)度變化不大，易于事先確定其大小時(shí)，為了節(jié)約存儲(chǔ)空間，宜采用順序表；反之，當(dāng)線性表長(zhǎng)度變化大，難以估計(jì)其存儲(chǔ)規(guī)模時(shí)，采用動(dòng)態(tài)鏈表作為存儲(chǔ)結(jié)構(gòu)為好。

2.基于時(shí)間的考慮。若線性表的操作主要是進(jìn)行查找，很少做插入和刪除操作時(shí)，采用順序表做存儲(chǔ)結(jié)構(gòu)為宜；反之，若需要對(duì)線性表進(jìn)行頻繁地插入或刪除等的操作時(shí)，宜采用鏈表做存儲(chǔ)結(jié)構(gòu)。并且，若鏈表的插入和刪除主要發(fā)生在表的首尾兩端，則采用尾指針表示的單循環(huán)鏈表為宜。2.6 下述算法的功能是什么? LinkList Demo(LinkList L){ // L 是無頭結(jié)點(diǎn)單鏈表 ListNode *Q,*P;if(L&&L->next){ Q=L;L=L->next;P=L;while(P->next)P=P->next;P->next=Q;Q->next=NULL;} return L;}// Demo 答：該算法的功能是：將開始結(jié)點(diǎn)摘下鏈接到終端結(jié)點(diǎn)之后成為新的終端結(jié)點(diǎn)，而原來的第二個(gè)結(jié)點(diǎn)成為新的開始結(jié)點(diǎn)，返回新鏈表的頭指針。

2.7 設(shè)線性表的n個(gè)結(jié)點(diǎn)定義為(a0,a1,...an-1)，重寫順序表上實(shí)現(xiàn)的插入和刪除算法：InsertList 和DeleteList.解：算法如下: #define ListSize 100 // 假定表空間大小為100 typedef int DataType;//假定DataType的類型為int型 typedef struct{ DataType data[ListSize];// 向量data用于存放表結(jié)點(diǎn) int length;// 當(dāng)前的表長(zhǎng)度 } Seqlist;//以上為定義表結(jié)構(gòu)

void InsertList(Seqlist *L, Datatype x, int i){ //將新結(jié)點(diǎn)x插入L所指的順序表的第i個(gè)結(jié)點(diǎn)ai的位置上，即插入的合法位置為：0<=i<=L->length int j;if(i < 0 || i > L-> length)Error(“position error”);// 非法位置，退出，if(L->length>=ListSize)Error(“overflow“);

for(j=L->length-1;j >= i;j--)L->data[ j+1]=L->data [ j ];L->data[ i ]=x;L->length++;} 2.9 設(shè)順序表L是一個(gè)遞增有序表，試寫一算法，將x插入L中，并使L仍是一個(gè)有序表。

答：因已知順序表L是遞增有序表，所以只要從順序表終端結(jié)點(diǎn)（設(shè)為i位置元素）開始向前尋找到第一個(gè)小于或等于x的元素位置i后插入該位置即可。在尋找過程中，由于大于x的元素都應(yīng)放在x之后，所以可邊尋找，邊后移元素，當(dāng)找到第一個(gè)小于或等于x的元素位置i時(shí)，該位置也空出來了。

算法如下：

//順序表存儲(chǔ)結(jié)構(gòu)如題2.7 void InsertIncreaseList(Seqlist *L , Datatype x){ int i;if(L->length>=ListSize)Error(“overflow”);

for(i=L-> length;i>0 && L->data[ i-1 ] > x;i--)L->data[ i ]=L->data[ i ];// 比較并移動(dòng)元素 L->data[ i ] =x;L-> length++;} 2.13 設(shè) A和B是兩個(gè)單鏈表，其表中元素遞增有序。試寫一算法將A和B歸并成一個(gè)按元素值遞減有序的單鏈表C，并要求輔助空間為O(1)，請(qǐng)分析算法的時(shí)間復(fù)雜度。

解：根據(jù)已知條件，A和B是兩個(gè)遞增有序表，所以可以先取A表的表頭建立空的C表。然后同時(shí)掃描A表和B表，將兩表中最大的結(jié)點(diǎn)從對(duì)應(yīng)表中摘下，并作為開始結(jié)點(diǎn)插入C表中。如此反復(fù)，直到A表或B表為空。最后將不為空的A表或B表中的結(jié)點(diǎn)依次摘下并作為開始結(jié)點(diǎn)插入C表中。這時(shí)，得到的C表就是由A表和B表歸并成的一個(gè)按元素值遞減有序的單鏈表C。并且輔助空間為O(1)。

算法如下：

LinkList MergeSort(LinkList A , LinkList B){// 歸并兩個(gè)帶頭結(jié)點(diǎn)的遞增有序表為一個(gè)帶頭結(jié)點(diǎn)遞減有序表 ListNode *pa , *pb , *q , *C;pa=A->next;//pa指向A表開始結(jié)點(diǎn)

C=A;C->next=NULL;//取A表的表頭建立空的C表 pb=B->next;//pb指向B表開始結(jié)點(diǎn) free(B);//回收B表的頭結(jié)點(diǎn)空間 while(pa && pb){ if(pb->data <= pa->data){ // 當(dāng)B中的元素小于等于A中當(dāng)前元素時(shí)，將pa表的開始結(jié)點(diǎn)摘下 q=pa;pa=pa->next;} else {// 當(dāng)B中的元素大于A中當(dāng)前元素時(shí)，將pb表的開始結(jié)點(diǎn)摘下 q=pb;pb=pb->next;} q->next=C->next;C->next=q;//將摘下的結(jié)點(diǎn)q作為開始結(jié)點(diǎn)插入C表 } //若pa表非空，則處理pa表 while(pa){ q=pa;pa=pa->next;q->next=C->next;C->next=q;} //若pb表非空，則處理pb表 while(pb){ q=pb;pa=pb->next;q->next=C->next;C->next=q;} return(C);} 該算法的時(shí)間復(fù)雜度分析如下：

算法中有三個(gè)while 循環(huán)，其中第二個(gè)和第三個(gè)循環(huán)只執(zhí)行一個(gè)。每個(gè)循環(huán)做的工作都是對(duì)鏈表中結(jié)點(diǎn)掃描處理。整個(gè)算法完成后，A表和B表中的每個(gè)結(jié)點(diǎn)都被處理了一遍。所以若A表和B表的表長(zhǎng)分別是m和n，則該算法的時(shí)間復(fù)雜度O(m+n)

●練習(xí)2.1：寫出在線性表中的查找運(yùn)算算法。

即查找數(shù)據(jù)元素x在表中的位置，也就是數(shù)據(jù)元素下標(biāo)值加1。

例如：若L.data[i]=x,則返回i+1;若不存在，則返回n+1 練習(xí)2.2：編寫尾插法建立鏈表的算法。

練習(xí)2.3：若是帶頭指針的單鏈表，算法又是怎樣？

若是兩個(gè)鏈表，既知道頭結(jié)點(diǎn)，又知道尾結(jié)點(diǎn)，算法又是怎樣？

●練習(xí)2：按升序打印帶頭結(jié)點(diǎn)h的單鏈表中各節(jié)點(diǎn)的數(shù)據(jù)域值，并將打印完的節(jié)點(diǎn)從表中刪除。

第三章

第三章作業(yè)：3.2, 3.3，3.4（2），3.6，3.11 3.2 循環(huán)隊(duì)列的優(yōu)點(diǎn)是什么? 如何判別它的空和滿? 答：循環(huán)隊(duì)列的優(yōu)點(diǎn)是：它可以克服順序隊(duì)列的“假上溢”現(xiàn)象，能夠使存儲(chǔ)隊(duì)列的向量空間得到充分的利用。判別循環(huán)隊(duì)列的“空”或“滿”不能以頭尾指針是否相等來確定，一般是通過以下幾種方法：一是另設(shè)一布爾變量來區(qū)別隊(duì)列的空和滿。二是少用一個(gè)元素的空間,每次入隊(duì)前測(cè)試入隊(duì)后頭尾指針是否會(huì)重合，如果會(huì)重合就認(rèn)為隊(duì)列已滿。三是設(shè)置一計(jì)數(shù)器記錄隊(duì)列中元素總數(shù)，不僅可判別空或滿，還可以得到隊(duì)列中元素的個(gè)數(shù)。

3.3設(shè)長(zhǎng)度為n的鏈隊(duì)用單循環(huán)鏈表表示，若設(shè)頭指針，則入隊(duì)出隊(duì)操作的時(shí)間為何? 若只設(shè)尾指針呢? 答：當(dāng)只設(shè)頭指針時(shí)，出隊(duì)的時(shí)間為1，而入隊(duì)的時(shí)間需要n，因?yàn)槊看稳腙?duì)均需從頭指針開始查找，找到最后一個(gè)元素時(shí)方可進(jìn)行入隊(duì)操作。若只設(shè)尾指針，則出入隊(duì)時(shí)間均為1。因?yàn)槭茄h(huán)鏈表，尾指針?biāo)傅南乱粋€(gè)元素就是頭指針?biāo)冈?，所以出?duì)時(shí)不需要遍歷整個(gè)隊(duì)列。3.4 指出下述程序段的功能是什么?(2)SeqStack S1, S2, tmp;

DataType x;

...//假設(shè)棧tmp和S2已做過初始化

while(!StackEmpty(&S1))

{

x=Pop(&S1);

Push(&tmp,x);

}

while(!StackEmpty(&tmp))

{

x=Pop(&tmp);

Push(&S1,x);

Push(&S2, x);

}(2)程序段的功能是利用tmp棧將一個(gè)非空棧s1的所有元素按原樣復(fù)制到一個(gè)棧s2當(dāng)中去。

3.6 利用棧的基本操作，寫一個(gè)將棧S中所有結(jié)點(diǎn)均刪去的算法void ClearStack(SeqStack *S)，并說明S為何要作為指針參數(shù)

解：算法如下

void ClearStack(SeqStack *S)

{ // 刪除棧中所有結(jié)點(diǎn)

S->Top =-1;//其實(shí)只是將棧置空

}

因?yàn)橐每盏氖菞，如果不用指針來做參數(shù)傳遞，那么函數(shù)進(jìn)行的操作不能對(duì)原來的棧產(chǎn)生影響，系統(tǒng)將會(huì)在內(nèi)存中開辟另外的單元來對(duì)形參進(jìn)行函數(shù)操作。結(jié)果等于什么也沒有做。所以想要把函數(shù)操作的結(jié)果返回給實(shí)參的話，就只能用指針來做參數(shù)傳遞了。

3.8 設(shè)計(jì)算法判斷一個(gè)算術(shù)表達(dá)式的圓括號(hào)是否正確配對(duì)。(提示： 對(duì)表達(dá)式進(jìn)行掃描，凡遇到‘(’就進(jìn)棧，遇‘)’就退掉棧頂?shù)摹?’，表達(dá)式被掃描完畢，棧應(yīng)為空。解：

根據(jù)提示，可以設(shè)計(jì)算法如下：

int PairBracket(char *SR)

{//檢查表達(dá)式SR中括號(hào)是否配對(duì)

int i;

SeqStack S;//定義一個(gè)棧

InitStack(&s);

for(i=0;i

{

if(SR[i]==‘(’)Push(&S, SR[i]);//遇‘(’時(shí)進(jìn)棧

if(SR[i]==‘)’)//遇‘)’

if(!StackEmpty(S))//棧不為空時(shí)，將棧頂元素出棧

Pop(&s);

else return 0;//不匹配，返回0

}

if（EmptyStack(&s)）return 1;// 匹配，返回1

else return 0;//不匹配，返回0

} 6.12 若二叉樹中各結(jié)點(diǎn)的值均不相同，則由二叉樹的前序序列和中序序列，或由其后序序列和中序序列均能唯一地確定一棵二叉樹，但由前序序列和后序序列卻不一定能唯一地確定一棵二叉樹。

(1)已知一棵二叉樹的前序序列和中序序列分別為ABDGHCEFI和GDHBAECIF，請(qǐng)畫出此二叉樹。(2)已知一棵二叉樹的中序序列和后序序列分別為BDCEAFHG和DECBHGFA，請(qǐng)畫出此二叉樹。(3)已知一棵二叉樹的前序序列和后序序列分別為AB和BA，請(qǐng)畫出這兩棵不同的二叉樹。解：

(1)已知二叉樹的前序序列為ABDGHCEFI和中序序列GDHBAECIF，則可以根據(jù)前序序列找到根結(jié)點(diǎn)為A，由此，通過中序序列可知它的兩棵子樹包分別含有GDHB和ECIF結(jié)點(diǎn)，又由前序序列可知B和C分別為兩棵子樹的根結(jié)點(diǎn)...以此類推可畫出所有結(jié)點(diǎn)：

○A / ○B(yǎng) ○C / / ○D ○E○F / / ○G ○H ○I

(2)以同樣的方法可畫出該二叉樹：

○A / ○B(yǎng) ○F ○C ○G / ○D ○E ○H

(3)這兩棵不同的二叉樹為：

○A ○A / ○B(yǎng) ○B(yǎng) 6.21 以二叉鏈表為存儲(chǔ)結(jié)構(gòu)，寫一算法交換各結(jié)點(diǎn)的左右子樹。

答：要交換各結(jié)點(diǎn)的左右子樹，最方便的辦法是用后序遍歷算法，每訪問一個(gè)結(jié)點(diǎn)時(shí)把兩棵子樹的指針進(jìn)行交換，最后一次訪問是交換根結(jié)點(diǎn)的子樹。

void ChangeBinTree(BinTree *T)

{ //交換子樹

if(*T)

{ //這里以指針為參數(shù)使得交換在實(shí)參的結(jié)點(diǎn)上進(jìn)行后序遍歷

BinTree temp;

ChangeBinTree(&(*T)->lchild);

ChangeBinTree(&(*T)->rchild);

temp=(*T)->lchild;

(*T)->lchild=(*T)->rchild;

(*T)->rchild=temp;

}

} 9.11試寫出二分查找的遞歸算法。解：

int BinSearch(SeqList R，KeyType K，int low，int high)

{ //在有序表R[low..high]中進(jìn)行二分查找，成功時(shí)返回結(jié)點(diǎn)的位置，失敗時(shí)返回零

int mid； //置當(dāng)前查找區(qū)間上、下界的初值

if(low<=high){ //當(dāng)前查找區(qū)間R[low..high]非空

mid=(low+high)/2；

if(R[mid].key==K)return mid； //查找成功返回

if(R[mid].key>K)

return BinSearch(R，K,low，mid-1)//在R[low..mid-1]中查找

else

return BinSearch(R，K,mid+1，high)； //在R[mid+1..high]中查找

}

return 0； //當(dāng)low>high時(shí)表示查找區(qū)間為空，查找失敗

} //BinSeareh 10.7.將哨兵放在R[n]中，被排序的記錄放在R[0..n-1]中，重寫直接插入排序算法。解：

重寫的算法如下：

void InsertSort(SeqList R)

{//對(duì)順序表中記錄R[0..n-1]按遞增序進(jìn)行插入排序

int i,j;

for(i=n-2;i>=0;i--)//在有序區(qū)中依次插入R[n-2]..R[0]

if(R[i].key>R[i+1].key)//若不是這樣則R[i]原位不動(dòng)

{

R[n]=R[i];j=i+1;//R[n]是哨兵

do{ //從左向右在有序區(qū)中查找插入位置

R[j-1]=R[j];//將關(guān)鍵字小于R[i].key的記錄向右移

j++;

}while(R[j].key

R[j-1]=R[n];//將R[i]插入到正確位置上

}//endif

}//InsertSort.12.1 常見的文件組織方式有哪幾種?各有何特點(diǎn)? 文件上的操作有哪幾種? 如何評(píng)價(jià)文件組織的效率? 答：

常用的文件組織方式有：順序文件、索引文件、散列文件和多關(guān)鍵字文件。

●順序文件的特點(diǎn)是，它是按記錄進(jìn)入文件的先后順序存放，其邏輯結(jié)構(gòu)和物理順序是一致的。

●索引文件的特點(diǎn)是，在主文件之外還另外建立了一張表，由這張表來指明邏輯記錄和物理記錄之間的一一對(duì)應(yīng)關(guān)系。索引文件在存儲(chǔ)器上分為兩個(gè)區(qū)：索引區(qū)和數(shù)據(jù)區(qū)，前者存放索引表，后者存放主文件?！裆⒘形募抢蒙⒘写鎯?chǔ)方式組織的，它類似于散列表，即根據(jù)文件中關(guān)鍵字的特點(diǎn)，設(shè)計(jì)一個(gè)散列函數(shù)和處理沖突的方法，將記錄散列到存儲(chǔ)設(shè)備上，對(duì)于散列文件，磁盤上的文件記錄通常是成組存放的。

●多關(guān)鍵字文件則包含有多個(gè)次關(guān)鍵索引的，不同于前述幾種文件，只含有一個(gè)主關(guān)鍵字。

文件的操作有兩種：檢索和維護(hù)。

評(píng)價(jià)一個(gè)文件組織的效率，是執(zhí)行文件操作(如查找、刪除等)所花費(fèi)的時(shí)間和文件組織所需的存儲(chǔ)空間。

第五篇：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)-查找排序

查找及排序算法實(shí)現(xiàn)

一、實(shí)驗(yàn)?zāi)康?/p>

1、熟練掌握二叉排序樹查找算法及C語言描述。

2、熟練掌握折半查找算法及C語言描述。

3、熟練掌握簡(jiǎn)單選擇排序算法及C語言描述。

4、熟練掌握簡(jiǎn)單插入排序算法及C語言描述。

5、熟練掌握冒泡（起泡）排序算法及C語言描述。

6、了解各種查找及排序算法的優(yōu)缺點(diǎn)、實(shí)用性及應(yīng)用。

7、將理論與實(shí)際相結(jié)合，切實(shí)提高自己的邏輯能力和動(dòng)手能力。

二、設(shè)計(jì)內(nèi)容

1.折半查找算法

折半查找算法的思路：

初始狀態(tài)：假設(shè)表長(zhǎng)為n，low、high和mid分別指向待查元素所在區(qū)間的下界、上界和中點(diǎn),key為給定值，初始時(shí)，令low=0,high=n-1,mid=(low+high)/2 讓key與mid指向的記錄比較

若key==r[mid].key，查找成功,算法結(jié)束；若keyr[mid].key，則low=mid+1；重復(fù)上述操作，直至low>high時(shí)，查找失敗。2.起泡排序算法

起泡排序的思路：

首先將第一個(gè)記錄的關(guān)鍵字和第二個(gè)記錄的關(guān)鍵字進(jìn)行比較，若為逆序（即L.r[1].key>L.r[2].key），則將兩個(gè)記錄交換之，然后比較【第二個(gè)記錄和第三個(gè)記錄】的關(guān)鍵字。以此類推，直至第n-1個(gè)記錄和第n個(gè)記錄的關(guān)鍵字進(jìn)行過比較為止。上述過程稱做第一趟起泡排序，其結(jié)果使得關(guān)鍵字最大的記錄被安置到最后一個(gè)記錄的位置上，然后進(jìn)行第二趟起泡排序，對(duì)前n-1個(gè)記錄進(jìn)行同樣操作，其結(jié)果是使關(guān)鍵字次大的記錄被安置到第n-1個(gè)記錄的位置上。一般地，第i躺起泡排序是從L.r[1]到L.r[n-i+1]以此比較相鄰兩個(gè)記錄的關(guān)鍵字，并在“逆序”時(shí)交換相鄰記錄，其結(jié)果是這n-i+1個(gè)記錄中關(guān)鍵字最大的記錄被交換到第n-i+1的位置上。整個(gè)排序過程需進(jìn)行k(1<=k

首先以一個(gè)元素為基準(zhǔn)，從一個(gè)方向開始掃描，比如從左至右掃描，以a[0]為基準(zhǔn)，接下來從a[0]...a[9] 中找出最小的元素，將其與a[0]交換，然后將基準(zhǔn)位置右

移一位，重復(fù)上面的動(dòng)作，比如，以a[1]為基準(zhǔn)，找出a[1]至a[9]中最小的，將其與a[1]交換，一直進(jìn)行到基準(zhǔn)位置移到數(shù)組最后一個(gè)元素時(shí)排序結(jié)束（此時(shí)基準(zhǔn)左邊所有元素均遞增有序，而基準(zhǔn)為最后一個(gè)元素，故完成排序）。4.直接插入排序算法

直接插入排序是一種最簡(jiǎn)單的排序方法，它的基本操作是將一個(gè)記錄插入到已排好序的有序表中，從而得到一個(gè)新的，記錄數(shù)增1的有序表。

一般情況下，第i趟直接插入排序的操作為：在含有i-1個(gè)記錄的有序子序列r[1...i-1]中插入一個(gè)記錄r[i]后，變成含有i個(gè)記錄的有序子序列r[1....i].在自i-1起往前搜索的過程中，可以同時(shí)后移記錄。

整個(gè)排序過程為進(jìn)行n-1躺插入，即：先將序列中的第一個(gè)記錄看成是一個(gè)有序的子序列，然后從第二個(gè)記錄起逐個(gè)進(jìn)行插入，直至整個(gè)序列變成按關(guān)鍵字非遞減有序序列為止

三、程序源代碼

1.二叉排序樹的創(chuàng)建、遍歷和查找刪除算法

#include #include typedef int KeyType;typedef struct node { KeyType data;struct node *lchild,*rchild;}LNode,*Tree;

void Insert(Tree &T,KeyType key){

if(!T){ T=new LNode;T->data=key;T->lchild=T->rchild=NULL;} else

} {

} if(keydata)Insert(T->lchild,key);else Insert(T->rchild,key);void CreatTree(Tree &T)//二叉排序樹的創(chuàng)建 {

} int num;char c;while(scanf(“%d”,&num)){

} Insert(T,num);c=getchar();if(c=='n')return;void In_Order(Tree T)//中序遍歷 {

if(T){ In_Order(T->lchild);printf(“%d ”,T->data);} In_Order(T->rchild);} void Delete(Tree &p){

Tree q,s;if(!p->rchild){

q = p;p=p->lchild;free(q);} else if(!p->lchild){

} q = p;p=p->rchild;free(q);

else {

} q = p;s = p->lchild;while(s->rchild){

} q = s;s = s->rchild;p->data = s->data;if(q!=p)q->rchild = s->lchild;else q->lchild = s->lchild;free(s);} void DelNode(Tree &T,KeyType key){

} if(!T){ printf(“n該結(jié)點(diǎn)不存在n”);return;} else {

} if(key == T->data)Delete(T);else if(key < T->data)DelNode(T->lchild, key);else DelNode(T->rchild,key);Tree Search(Tree T,KeyType key)//二叉排序樹查找

{

if(!T){

} printf(“該結(jié)點(diǎn)不存在”);return 0;else if(key == T->data)return T;else if(key < T->data)

return(Search(T->lchild, key));else return(Search(T->rchild, key));} int main()//主函數(shù) { Tree T,p;T=NULL;KeyType x;

printf(“請(qǐng)輸入二叉樹各結(jié)點(diǎn)：n”);

CreatTree(T);

printf(“中序遍歷為：n”);In_Order(T);printf(“n請(qǐng)輸入要查找和刪除的結(jié)點(diǎn)：n”);scanf(“%d”,&x);p=Search(T, x);if(p){

} DelNode(T, x);printf(“中序遍歷為：n”);In_Order(T);

}

2、冒泡排序和折半查找算法

#include #include #define M 10 //冒泡排序

int BubbleSort(int c[]){

int i,t,j;for(i=0;i<9;i++){

} for(j=0;j<9-i;j++){

} if(c[j]>c[j+1]){

} t=c[j];c[j]=c[j+1];c[j+1]=t;

printf(“n您所輸入的數(shù)字的升序排列是:nn”);for(i=0;i<10;i++){ printf(“%d”,c[i]);printf(“ ”);} return 1;} //折半查找

int BinarySearch(int b[]){

} int t,mid;int i=0;int j=9;printf(“nn請(qǐng)輸入您要查找的數(shù)字：”);scanf(“%d”, &t);while(i<=j){ mid=i+(j-i)/2;

} return 1;if(t==b[mid]){ printf(“n您要查找的數(shù)字的排列位置是：%dn”,mid+1);break;} else if(t

int main(int argc,char *argv[]){

int a[10];printf(“請(qǐng)您輸入數(shù)據(jù):nn”);for(int i=0;i<10;i++){ scanf(“%d”,&a[i]);

} } BubbleSort(a);BinarySearch(a);return 0;

3、簡(jiǎn)單選擇排序和簡(jiǎn)單插入排序算法

#include int SelectionSort(int*a,int n){

int i,j,min,p,key,k;

for(i=0;i

{

key=0;

min=a[i];

} for(j=i;j

if(a[j]

if(key==1){a[p]=a[i];

a[i]=min;}

for(k=0;k

printf(“%d ”,a[k]);printf(“n”);

return 1;} int InserSort(int*a,int n){

int i,j,k;for(i=2;i<=n;i++){

a[0]=a[i];for(j=1;j

{

if(a[j]>a[i]){for(k=i;k>j;k--)

a[k]=a[k-1];

a[k]=a[0];

}

}

break;} } for(j=1;j<=n;j++){ } printf(“%d ”,a[j]);printf(“n”);return 1;int main(){

int a[80],i,n,b;printf(“請(qǐng)輸入關(guān)鍵字的個(gè)數(shù)：”);scanf(“%d”,&n);printf(“排序類型：n”);printf(“1.選擇排序n”);printf(“2.插入排序n”);printf(“請(qǐng)選擇：”);scanf(“%d”,&b);switch(b){

case 1:

printf(“請(qǐng)輸入關(guān)鍵字：n”);for(i=0;i

SelectionSort(a,n);

return 1;

break;

case 2:

printf(“請(qǐng)輸入關(guān)鍵字：n”);

for(i=1;i<=n;i++){

scanf(“%d”,&a[i]);} printf(“插入排序的流程以及結(jié)果：n”);

InserSort(a,n);return 1;

} break;}while(a!=0);

四、實(shí)驗(yàn)運(yùn)行結(jié)果

1.二叉排序樹的創(chuàng)建、遍歷和查找刪除算法

2、冒泡排序和折半查找算法

3、簡(jiǎn)單選擇排序和簡(jiǎn)單插入排序算法

七、心得體會(huì)

通過本次的數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告，掌握了查找和排序的幾種基本排序算法，了解了他們各自的特點(diǎn)和優(yōu)缺點(diǎn)，完成了對(duì)于他們C語言的描述和實(shí)際應(yīng)用，對(duì)他們有了一個(gè)更加具體、深刻的認(rèn)識(shí)，同時(shí)也鍛煉了我們的邏輯思維能力和動(dòng)手實(shí)踐能力，使我們受益匪淺，給我們今后的計(jì)算機(jī)專業(yè)課程學(xué)習(xí)帶來很大的幫助。