第一篇：數(shù)據(jù)結(jié)構(gòu)第九章排序習(xí)題及答案[小編推薦]

習(xí)題九

排序

一、單項(xiàng)選擇題

1．下列內(nèi)部排序算法中：

A．快速排序 B.直接插入排序 C.二路歸并排序 D.簡單選擇排序 E.起泡排序 F.堆排序

（1）其比較次數(shù)與序列初態(tài)無關(guān)的算法是（）（2）不穩(wěn)定的排序算法是（）

（3）在初始序列已基本有序（除去n個(gè)元素中的某k個(gè)元素后即呈有序，k<

（4）排序的平均時(shí)間復(fù)雜度為O(n?logn)的算法是（）為O(n?n)的算法是（）2．比較次數(shù)與排序的初始狀態(tài)無關(guān)的排序方法是()。

A．直接插入排序 B．起泡排序 C．快速排序 D．簡單選擇排序 3．對(duì)一組數(shù)據(jù)（84，47，25，15，21）排序，數(shù)據(jù)的排列次序在排序的過程中的變化為（1）84 47 25 15 21（2）15 47 25 84 21（3）15 21 25 84 47（4）15 21 25 47 84 則采用的排序是()。

A.選擇 B.冒泡 C.快速 D.插入

4．下列排序算法中()排序在一趟結(jié)束后不一定能選出一個(gè)元素放在其最終位置上。

A.選擇 B.冒泡 C.歸并 D.堆 5．一組記錄的關(guān)鍵碼為（46，79，56，38，40，84），則利用快速排序的方法，以第一個(gè)記錄為基準(zhǔn)得到的一次劃分結(jié)果為（）。

A．(38,40,46,56,79,84)B.(40,38,46,79,56,84)C．(40,38,46,56,79,84)D.(40,38,46,84,56,79)6．下列排序算法中，在待排序數(shù)據(jù)已有序時(shí)，花費(fèi)時(shí)間反而最多的是()排序。A． 冒泡 B.希爾 C.快速 D.堆

7.就平均性能而言，目前最好的內(nèi)排序方法是()排序法。

A.冒泡 B.希爾插入 C.交換 D.快速 8.下列排序算法中，占用輔助空間最多的是：()A.歸并排序 B.快速排序 C.希爾排序 D.堆排序

9.若用冒泡排序方法對(duì)序列{10,14,26,29,41,52}從大到小排序，需進(jìn)行（）次比較。

A.3 B.10 C.15 D.25 10.快速排序方法在（）情況下最不利于發(fā)揮其長處。

A.要排序的數(shù)據(jù)量太大 B.要排序的數(shù)據(jù)中含有多個(gè)相同值 C.要排序的數(shù)據(jù)個(gè)數(shù)為奇數(shù) D.要排序的數(shù)據(jù)已基本有序 11．下列四個(gè)序列中，哪一個(gè)是堆（）。

A.75,65,30,15,25,45,20,10 B.75,65,45,10,30,25,20,15 C.75,45,65,30,15,25,20,10 D.75,45,65,10,25,30,20,15 12.有一組數(shù)據(jù)（15，9，7，8，20，-1，7，4），用堆排序的篩選方法建立的初始堆為（）

A．-1，4，8，9，20，7，15，7 B．-1，7，15，7，4，8，20，9 C．-1，4，7，8，20，15，7，9 D．A，B，C均不對(duì)。

二、填空題

1.若待排序的序列中存在多個(gè)記錄具有相同的鍵值，經(jīng)過排序，這些記錄的相對(duì)次序仍然保持不變，則稱這種排序方法是________的，否則稱為________的。

2.按照排序過程涉及的存儲(chǔ)設(shè)備的不同，排序可分為________排序和________排序。

3．直接插入排序用監(jiān)視哨的作用是___________________________。

4．對(duì)n個(gè)記錄的表r[1..n]進(jìn)行簡單選擇排序，所需進(jìn)行的關(guān)鍵字間的比較次數(shù)為_______。

5．下面的c函數(shù)實(shí)現(xiàn)對(duì)鏈表head進(jìn)行選擇排序的算法,排序完畢,鏈表中的結(jié)點(diǎn)按結(jié)點(diǎn)值從小到大鏈接。請(qǐng)?jiān)诳湛蛱幪钌线m當(dāng)內(nèi)容,每個(gè)空框只填一個(gè)語句或一個(gè)表達(dá)式： #include typedef struct node {char data;struct node *link;}node;node *select(node *head){node *p,*q,*r,*s;p=(node *)malloc(sizeof(node));p->link=head;head=p;while(p->link!=null){q=p->link;r=p;while((1)____________){ if(q->link->datalink->data)r=q;q=q->link;} if((2)___________){s=r->link;r->link=s->link;

s->link=((3)_________);((4)_________);}((5)________);} p=head;head=head->link;free(p);return(head);}

6．下面的排序算法的思想是：第一趟比較將最小的元素放在r[1]中，最大的元素放在r[n]中，第二趟比較將次小的放在r[2]中，將次大的放在r[n-1]中，…,依次下去，直到待排序列為遞增序。（注：<-->）代表兩個(gè)變量的數(shù)據(jù)交換）。

void sort(SqList &r,int n){ i=1;while((1)______){ min=max=1;for(j=i+1;(2)________;++j){if((3)________)min=j;else if(r[j].key>r[max].key)max=j;} if((4)_________)r[min] <---->r[j];if(max!=n-i+1){if((5)_______)r[min] <----> r[n-i+1];else((6)______);} i++;} }//sort

7．下列算法為奇偶交換排序，思路如下：第一趟對(duì)所有奇數(shù)的i,將a[i]和a[i+1]進(jìn)行比較,第二趟對(duì)所有偶數(shù)的i,將a[i]和a[i+1]進(jìn)行比較,每次比較時(shí)若a[i]>a[i+1],將二者交換;以后重復(fù)上述二趟過程,直至整個(gè)數(shù)組有序。

void oesort(int a[n]){int flag,i,t;do {flag=0;for(i=1;ia[i+1]){flag=(1)______;t=a[i+1];a[i+1]=a[i];(2)________;} for(3)________ if(a[i]>a[i+1]){flag=(4)________;t=a[i+1];a[i+1]=a[i];a[i]=t;} }while(5)_________;}

第九章 排序

一、單項(xiàng)選擇題 1．（1）DC（2）ADF（3）B（4）ACF BDE 2．D 3．A 4．C 5．C 6．C 7.D 8.A 9.C 10.D 11．C 12.C

二、填空題 1.穩(wěn)定、不穩(wěn)定 2.內(nèi)部、外部

3．免去查找過程中每一步都要檢測整個(gè)表是否查找完畢，提高了查找效率。4．n(n-1)/2 5．題中為操作方便，先增加頭結(jié)點(diǎn)（最后刪除），p指向無序區(qū)的前一記錄，r指向最小值結(jié)點(diǎn)的前驅(qū)，一趟排序結(jié)束，無序區(qū)第一個(gè)記錄與r所指結(jié)點(diǎn)的后繼交換指針。

(1)q->link!=NULL(2)r!=p(3)p->link(4)p->link=s(5)p=p->link 6．.(1)ir[n-i+1] 7．(1)1(2)a[i]=t(3)(i=2;i<=n;i+=2)(4)1(5)flag

第二篇：數(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è)輸出，有窮性，確定性，可行性

⑹ 算法的描述方法通常有（）、（）、（）和（）四種，其中，（）被稱為算法語言。【解答】自然語言，程序設(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)；簡單地說，算法是解決問題的方法；數(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 正確性和簡明性

G 可讀性和文檔性 H 數(shù)據(jù)復(fù)雜性和程序復(fù)雜性 【解答】C，E 3.判斷題

⑴ 算法的時(shí)間復(fù)雜度都要通過算法中的基本語句的執(zhí)行次數(shù)來確定。【解答】錯(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è)排序算法?！窘獯稹肯旅媸呛唵芜x擇排序算法的偽代碼描述。

下面是簡單選擇排序算法的C++描述。

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

⑵ 找出整型數(shù)組A[n]中元素的最大值和次最大值?！窘獯稹克惴ǖ膫未a描述如下：

算法的C++描述如下：

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

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

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í)可以作出處理的特性稱為（）。【解答】健壯性

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)。

【解答】表長的一半，表長，該元素在表中的位置

⑵ 順序表中第一個(gè)元素的存儲(chǔ)地址是100，每個(gè)元素的長度為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 所需空間與線性表長度成正比 【解答】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)?！窘獯稹垮e(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)更好些。

⑴ 若線性表的總長度基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快的速度存取線性表中的元素。⑵ 如果n個(gè)線性表同時(shí)并存，并且在處理過程中各表的長度會(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)：① 不必事先知道線性表的長度；② 插入和刪除元素時(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ò)充，適合表的長度動(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è)順序表的長度為length，則將表中第i個(gè)元素與第length-i-1個(gè)元素相交換。具體算法如下：

單鏈表的逆置請(qǐng)參見2.2.4算法2-4和算法2-6。

⑸ 假設(shè)在長度大于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í)自測及答案

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．在長度為n的線性表中查找值為x的數(shù)據(jù)元素的時(shí)間復(fù)雜度為：（）。

A O(0)B O(1)C O(n)D O(n2)【解答】C 3．在一個(gè)長度為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ǔ)位置由（）指示?！窘獯稹科淝摆吔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之間（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。【解答】算法如下：

第 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)是（）；其判定?？盏臈l件分別是（），判定棧滿的條件分別是（）?！窘獯稹宽樞虼鎯?chǔ)結(jié)構(gòu)和鏈接存儲(chǔ)結(jié)構(gòu)（或順序棧和鏈棧），棧頂指針top=-1和top=NULL，棧頂指針top等于數(shù)組的長度和內(nèi)存無可用空間

⑶（）可作為實(shí)現(xiàn)遞歸函數(shù)調(diào)用的一種數(shù)據(jù)結(jié)構(gòu)。【解答】棧

【分析】遞歸函數(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ì)列長度為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è)串相等的充分必要條件是（）?！窘獯稹块L度相同且對(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 【分析】兩棧共享空間首先兩個(gè)棧是相向增長的，棧底應(yīng)該分別指向兩個(gè)棧中的第一個(gè)元素的位置，并注意C++中的數(shù)組下標(biāo)是從0開始的。

⑼ 設(shè)有兩個(gè)串p和q，求q在p中首次出現(xiàn)的位置的運(yùn)算稱作（）。A 連接 B 模式匹配 C 求子串 D 求串長 【解答】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度為零，而空格串的長度不為0，其長度是串中空格的個(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ū)別？串中的空格符有何意義？空串在串處理中有何作用？

【解答】不含任何字符的串稱為空串，其長度為零。僅含空格的串稱為空格串，它的長度為串中空格符的個(gè)數(shù)。串中的空格符可用來分隔一般的字符，便于人們識(shí)別和閱讀，但計(jì)算串長時(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í)自測及答案

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”，其長度為（）?！窘獯稹?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ǔ)方法有兩種，分別是（）和（）。【解答】三元組順序表，十字鏈表

⑸ 廣義表((a),(((b),c)),(d))的長度是（），深度是（），表頭是（），表尾是（）。【解答】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ù)組是一種定長的線性結(jié)構(gòu)

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

⑷ 對(duì)特殊矩陣采用壓縮存儲(chǔ)的目的主要是為了（）A 表達(dá)變得簡單 B 對(duì)矩陣元素的存取變得簡單 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í)自測及答案

1．二維數(shù)組M中每個(gè)元素的長度是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]的起始地址為（）。【解答】d+22，d+141 2．一個(gè)n×n的對(duì)稱矩陣，按行優(yōu)先或列優(yōu)先進(jìn)行壓縮存儲(chǔ)，則其存儲(chǔ)容量為（）。【解答】n(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á)到的最大值是（），最小值是（）?！窘獯稹?h-1，2h-1 【分析】最小結(jié)點(diǎn)個(gè)數(shù)的情況是第1層有1個(gè)結(jié)點(diǎn)，其他層上都只有2個(gè)結(jié)點(diǎn)。

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

⑹ 具有100個(gè)結(jié)點(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)。【解答】12 【分析】根據(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)造出來。

⑼ 在具有n個(gè)結(jié)點(diǎn)的二叉鏈表中，共有（）個(gè)指針域，其中（）個(gè)指針域用于指向其左右孩子，剩下的（）個(gè)指針域則是空的。【解答】2n，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)路徑長度。

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

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

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)路徑長度=2×5+1×5+3×4+5×3+9×2+4×3+4×3+7×2=98，所以，該字符串的編碼長度至少為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í)自測及答案

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)路徑長度為（）。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)的入度的方法是（）?！窘獯稹壳蟮趈列的所有元素之和

⑹ 有向圖G用鄰接矩陣A[n][n]存儲(chǔ)，其第i行的所有元素之和等于頂點(diǎn)i的（）。【解答】出度

⑺ 圖的深度優(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)的連通圖中的任意一條簡單路徑，其長度不可能超過（）。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)?！窘獯稹垮e(cuò)。只有連通圖從某頂點(diǎn)出發(fā)進(jìn)行一次遍歷，可訪問圖的所有頂點(diǎn)。⑹ 在一個(gè)有向圖的拓?fù)湫蛄兄?，若頂點(diǎn)a在頂點(diǎn)b之前，則圖中必有一條弧?！窘獯稹垮e(cuò)。只能說明從頂點(diǎn)a到頂點(diǎn)b有一條路徑。

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

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

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．證明：生成樹中最長路徑的起點(diǎn)和終點(diǎn)的度均為１?！窘獯稹坑梅醋C法證明。

設(shè)v1, v2, …, vk是生成樹的一條最長路徑，其中，v1為起點(diǎn)，vk為終點(diǎn)。若vk的度為2，取vk的另一個(gè)鄰接點(diǎn)v，由于生成樹中無回路，所以，v在最長路徑上，顯然v1, v2, …, vk , v的路徑最長，與假設(shè)矛盾。所以生成樹中最長路徑的終點(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) 最短路徑 最短路徑長度 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) 最短路徑 最短路徑長度 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?！窘獯稹咳我鈔個(gè)結(jié)點(diǎn)的有向無環(huán)圖都可以得到一個(gè)拓?fù)湫蛄小ＴO(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ù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)報(bào)告 排序

實(shí)驗(yàn)題目：

輸入十個(gè)數(shù)，從插入排序，快速排序，選擇排序三類算法中各選一種編程實(shí)現(xiàn)。

實(shí)驗(yàn)所使用的數(shù)據(jù)結(jié)構(gòu)內(nèi)容及編程思路：

1.插入排序：直接插入排序的基本操作是，將一個(gè)記錄到已排好序的有序表中，從而得到一個(gè)新的，記錄增一得有序表。

一般情況下，第i趟直接插入排序的操作為：在含有i-1個(gè)記錄的有序子序列r［1..i-1］中插入一個(gè)記錄r［i］后，變成含有i個(gè)記錄的有序子序列r［1..i］；并且，和順序查找類似，為了在查找插入位置的過程中避免數(shù)組下標(biāo)出界，在 r［0］處設(shè)置哨兵。在自i-1起往前搜索的過程中，可以同時(shí)后移記錄。整個(gè)排序過程為進(jìn)行n-1趟插入，即：先將序列中的第一個(gè)記錄看成是一個(gè)有序的子序列，然后從第2個(gè)記錄起逐個(gè)進(jìn)行插入，直至整個(gè)序列變成按關(guān)鍵字非遞減有序序列為止。

2.快速排序：基本思想是，通過一趟排序?qū)⒋庞涗浄指畛瑟?dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，則可分別對(duì)這兩部分記錄繼續(xù)進(jìn)行排序，以達(dá)到整個(gè)序列有序。

假設(shè)待排序的序列為{L.r[s]，L.r[s+1],?L.r[t]},首先任意選取一個(gè)記錄(通?？蛇x第一個(gè)記錄L.r[s])作為樞軸（或支點(diǎn)）（pivot），然后按下述原則重新排列其余記錄：將所有關(guān)鍵字較它小的記錄都安置在它的位置之前，將所有關(guān)鍵字較大的記錄都安置在它的位置之后。由此可以該“樞軸”記錄最后所羅的位置i作為界線，將序列{L.r[s]，?，L.r[t]}分割成兩個(gè)子序列{L.r[i+1],L.[i+2],?,L.r[t]}。這個(gè)過程稱為一趟快速排序，或一次劃分。

一趟快速排序的具體做法是：附設(shè)兩個(gè)指針low和high，他們的初值分別為low和high，設(shè)樞軸記錄的關(guān)鍵字為pivotkey，則首先從high所指位置起向前搜索找到第一個(gè)關(guān)鍵字小于pivotkey的記錄和樞軸記錄互相交換，然后從low所指位置起向后搜索，找到第一個(gè)關(guān)鍵字大于pivotkey的記錄和樞軸記錄互相 1 交換，重復(fù)這兩不直至low=high為止。

具體實(shí)現(xiàn)上述算法是，每交換一對(duì)記錄需進(jìn)行3次記錄移動(dòng)（賦值）的操作。而實(shí)際上，在排列過程中對(duì)樞軸記錄的賦值是多余的，因?yàn)橹挥性谝惶伺判蚪Y(jié)束時(shí)，即low=high的位置才是樞軸記錄的最后位置。由此可以先將樞軸記錄暫存在r[0]的位置上，排序過程中只作r[low]或r[high]的單向移動(dòng)，直至一趟排序結(jié)束后再將樞軸記錄移至正確位置上。

整個(gè)快速排序的過程可遞歸進(jìn)行。若待排序列中只有一個(gè)記錄，顯然已有序，否則進(jìn)行一趟快速排序后再分別對(duì)分割所得的兩個(gè)子序列進(jìn)行快速排序。

3.簡單選擇排序：其操作為，通過n-i次關(guān)鍵字間的比較，從n-i+1個(gè)記錄中選出關(guān)鍵字最小的記錄，并和第i（1≤i≤n）個(gè)記錄交換之。

顯然，對(duì)L.r[1?n]中的記錄進(jìn)行簡單選擇排序的算法為：令i從1至n-1，進(jìn)行n-1趟選擇操作?？梢钥闯?，簡單選擇排序過程中，所需進(jìn)行記錄移動(dòng)的操作次數(shù)較少，其最小值為“0”，最大值為3（n-1）。然后，無論記錄的初始排列如何，所需進(jìn)行的關(guān)鍵字之間的比較次數(shù)相同，均為n(n-1)/2。

程序清單： 1．插入排序： #include structsqlist {int key[11];int length;} insertsort(structsqlist *l){ inti,j;for(i=2;i<=l->length;i++)if(l->key[i]key[i-1]){l->key[0]=l->key[i];l->key[i]=l->key[i-1];for(j=i-2;l->key[0]key[j];j--)l->key[j+1]=l->key[j];l->key[j+1]=l->key[0];} } main(){ inti,j,k;structsqlistnum;num.length=10;for(i=1;i<=num.length;i++)scanf(“%d”,&(num.key[i]));insertsort(&num);printf（“charu：”）；

for(i=1;i<=num.length;i++)printf(“%d ”,num.key[i]);} 測試用例：

輸入：23 34 12 98 56 45 67 8 9 37 輸出：charu：8 9 12 23 34 37 45 56 67 98 2快速排序： #include structsqlist { int key[11];int length;};int partition(structsqlist *l,intlow,int high){ intpivotkey;l->key[0]=l->key[low];pivotkey=l->key[low];while(lowkey[high]>=pivotkey)high--;l->key[low]=l->key[high];while(lowkey[low]<=pivotkey)low++;l->key[high]=l->key[low];} l->key[low]=l->key[0];return low;} voidqsort(structsqlist *l,intlow,int high){intpivotloc;if(lowlength);} main(){ inti,j;structsqlistnum;num.length=10;for(i=1;i<=num.length;i++)scanf(“%d”,&(num.key[i]));quicksort(&num);printf（“kuaisu：”）；

for(i=1;i<=num.length;i++)printf(“%d ”,num.key[i]);} 測試用例：

輸入：23 34 12 98 56 45 67 8 9 37 輸出：charu：8 9 12 23 34 37 45 56 67 98 3選擇排序： #include structsqlist {int key[11];int length;};

intselectminkey(structsqlist *l,int a){ inti,j=a;for(i=a;i<=l->length;i++)if(l->key[i]key[j])j=i;return j;} voidselectsort(structsqlist *l){inti,j,k;for(i=1;ilength;i++){j=selectminkey(l,i);if(i!=j){k=l->key[i];l->key[i]=l->key[j];l->key[j]=k;} } } main(){ inti,j;structsqlistnum;num.length=10;for(i=1;i<=num.length;i++)scanf(“%d”,&(num.key[i]));selectsort(&num);printf（“xuanze：”）；

for(i=1;i<=num.length;i++)printf(“%d ”,num.key[i]);} 測試用例：

輸入：23 34 12 98 56 45 67 8 9 37 輸出：charu：8 9 12 23 34 37 45 56 67 98

編程感想： 本次編程總共使用了三種排序方法，而這三種編程方法放在一起進(jìn)行編寫時(shí)，很容易就讓我們對(duì)齊難易程度有了更深刻的了解。

首先，三種排序中，我們都像查表那樣，設(shè)置了哨兵，而哨兵的使用可以減少對(duì)整個(gè)表的驗(yàn)空操作，使程序更加節(jié)省空間。

其次，對(duì)于插入排序，每次都要對(duì)一段序列進(jìn)行檢索，每排一次所要檢索的序列長度減一，其時(shí)間發(fā)雜度為O（n^2）。

接著，對(duì)于快速排序，這個(gè)程序是比較復(fù)雜的，總共是3個(gè)函數(shù)，并且使用了遞歸的方法，這是但是，這種算法卻是最優(yōu)越的，平均性能也是最好的，我在編這個(gè)程序時(shí)，對(duì)其排序的思想有了進(jìn)一步的了解，并努力拿他與冒泡排序進(jìn)行比較，看出了些許其優(yōu)越性。

還有，就是選擇排序，簡單選擇排序思路簡單，易于進(jìn)行，但其時(shí)間發(fā)雜度與簡單插入排序方法一樣，都是O（n^2），性能不如快速排序。

最后，本次試驗(yàn)是數(shù)據(jù)結(jié)構(gòu)課的最后一次實(shí)驗(yàn)，經(jīng)過數(shù)據(jù)結(jié)構(gòu)試驗(yàn)課的鍛煉，使我對(duì)數(shù)據(jù)結(jié)構(gòu)有了更深刻的理解，對(duì)我對(duì)其知識(shí)起到了重要的影響，增加了我編程的實(shí)踐活動(dòng)，為我將來進(jìn)一步學(xué)習(xí)打下了基礎(chǔ)。

第四篇：句子排序方法及習(xí)題附答案

句子排序方法及習(xí)題附答案

怎樣排列順序錯(cuò)亂的句子

把排列錯(cuò)亂的句子整理成一段通順連貫的話，能訓(xùn)練對(duì)句子的理解能力、有條理表達(dá)能力和構(gòu)段能力。這樣的練習(xí)一般可按五步進(jìn)行。

第一步，仔細(xì)閱讀每句話或每組句子，理解它們的主要內(nèi)容；第二步，綜合各句的意思，想想這些話主要說的是什么內(nèi)容；第三步，想想全段的內(nèi)容按什么順序排列好，即找出排列順序的依據(jù)，如，是按事情發(fā)展順序，還是時(shí)間順序，或方位，還是“總分”等；第四步，按確定的排列依據(jù)排列順序；第五步，按排好的順序仔細(xì)讀兩遍，看排得對(duì)不對(duì)，如發(fā)現(xiàn)有的句子排得位置不對(duì)，就進(jìn)行調(diào)整，直到這段話排得通順連貫為止。把錯(cuò)亂的句子排列好，這是小學(xué)階段語文練習(xí)中的一個(gè)重要形式，必須好好掌握。學(xué)會(huì)排列句子，不僅能提高我們的思維能力，還能提高我們的寫作能力。那么，如何學(xué)會(huì)排列好句子呢？我們可以按下列方法進(jìn)行。

一、按事情發(fā)展的順序排列

有些錯(cuò)亂的句子，我們?cè)谂帕袝r(shí)，應(yīng)仔細(xì)分析句與句之間的聯(lián)系。常見的錯(cuò)亂句子，往往敘述了一件完整的事，或者活動(dòng)的具體過程。那么，我們就可以按事情發(fā)展的順序來排列。

二、按時(shí)間先后順序排列

對(duì)一些錯(cuò)亂的句子，我們可以找出表示時(shí)間概念的詞語，如，早晨、上午、中午、下午等詞，然后按時(shí)間先后順序進(jìn)行排列句子。

三、按先總述后分述的順序排列

根據(jù)這段話的特點(diǎn)，找出這句話是個(gè)中心句，其他句子都是圍繞著這句話來說的。顯而易見，我們可按先總后分的順序來排列句子。

四、按空間推移的順序排列

所謂空間推移，就是由地點(diǎn)的轉(zhuǎn)移，表達(dá)出不同的內(nèi)容。排列時(shí)，要十分注意，不要與其他的方法相混淆。

對(duì)練習(xí)排列句子有幫助

把錯(cuò)亂的句子排列好，這是小學(xué)階段語文練習(xí)中的一個(gè)重要形式，必須好好掌握。學(xué)會(huì)排列句子，不僅能提高我們的思維能力，還能提高我們的寫作能力。那么，如何學(xué)會(huì)排列好句子呢？我們可以按下列方法進(jìn)行。

試題

一、按事情發(fā)展的順序排列

有些錯(cuò)亂的句子，我們?cè)谂帕袝r(shí)，應(yīng)仔細(xì)分析句與句之間的聯(lián)系。常見的錯(cuò)亂句子，往往敘述了一件完整的事，或者活動(dòng)的具體過程。那么，我們就可以按事情發(fā)展的順序來排列。如：

（）他想，這是誰丟的，真不講衛(wèi)生。（）他看見地上有一團(tuán)白白的東西。

（）忽然，他看見有幾個(gè)小同學(xué)在打掃操場，爭做好事。（）下課了，張良在操場上玩。

（）他連忙回頭，不好意思地拾起剛才看到的那一團(tuán)白紙。（）想著，他就若無其事地走開了。（）走近一看，原來是一團(tuán)廢紙。

從這段話中，我們可以看出，敘述了張良在操場上看到了一團(tuán)廢紙，經(jīng)過思想斗爭，最后拾起了那團(tuán)廢紙的過程，層次清楚。在排列時(shí)，我們可按事情發(fā)展的順序排列排列為4、2、6、1、7、5、3。

把下面順序錯(cuò)亂的句子整理成通順連貫的一段話，在句子前標(biāo)上序號(hào)。（事情發(fā)展順序）

()姐姐看見了，大聲喊：“快把它放了，它是益蟲?！?/p>

()大蜻蜓亮晶晶的兩只眼睛，像小玻璃球，一對(duì)紅翅膀不住地扇動(dòng)，非常漂亮。

()我和姐姐發(fā)現(xiàn)一只大蜻蜓，落在一棵小樹上。

()我悄悄地一捏，把它捉住了。

()我聽了姐姐的話，想到益蟲的好處，馬上把它放了。

解析這五句話分句細(xì)讀后，我們知道它寫了這樣一件事：“我”抓住了一只蜻蜓，姐姐說它是益蟲，“我”馬上把它放了。應(yīng)該按事情的發(fā)展順序來排列：發(fā)現(xiàn)蜻蜓→觀察蜻蜓→抓住蜻蜓→姐姐讓放蜻蜓→放走蜻蜓。

排列順序?yàn)椋?4)(2)(1)(3)(5)。

二、按時(shí)間先后順序排列

對(duì)一些錯(cuò)亂的句子，我們可以找出表示時(shí)間概念的詞語，如，早晨、上午、中午、下午等詞，然后按時(shí)間先后順序進(jìn)行排列句子。例如：

（）華羅庚教授是一位自學(xué)成才的著名的數(shù)學(xué)家。

試題

（）20歲那年，他得了傷寒病，一躺就是半年，病好后，一條腿殘疾，但他毫不泄氣，繼續(xù)向科學(xué)城堡進(jìn)攻。

（）他14歲開始自學(xué)數(shù)學(xué)，每天堅(jiān)持自學(xué)10小時(shí)，從不間斷。

（）1932年，22歲的華羅庚應(yīng)清華大學(xué)數(shù)學(xué)系主任熊慶來的邀請(qǐng)，到清華大學(xué)工作。（）從19歲起，華羅庚開始寫數(shù)學(xué)論文。

（）在清華期間，他看了更多的數(shù)學(xué)書，并開始學(xué)習(xí)外文。由于他肯下苦功，進(jìn)步很快，25歲時(shí)，華羅庚就成了著名的數(shù)學(xué)家。

排列這段話時(shí)，我們可以抓住“14歲”、“19歲”、“20歲”、“22歲”、“25歲”這些表示年齡的詞，也就是以時(shí)間順序來排列句子，那問題就迎刃而解了，正確的排列應(yīng)是：1、4、2、5、3、6。

把下列錯(cuò)亂的句子，按順序排列起來，整理成一段通順的話。（時(shí)間先后順序）

()從那天起，媽媽發(fā)憤讀書了。

()我去問媽媽，她說：“從今天開始，媽媽也要當(dāng)學(xué)生參加學(xué)習(xí)了?！?/p>

()考試的日期快到了，媽媽對(duì)學(xué)習(xí)抓得更緊了，睡得更晚了。

()難道媽媽也要學(xué)習(xí)嗎?我感到很奇怪，心中涌起了一個(gè)問號(hào)。

()一天，我發(fā)現(xiàn)媽媽的桌子上多了一疊課本和作業(yè)本。

()過了些日子，媽媽終于領(lǐng)到了一張畢業(yè)證。

解析認(rèn)真讀了這六句話后，我們了解到寫了這樣一件事：媽媽當(dāng)了學(xué)生發(fā)憤讀書，領(lǐng)到了畢業(yè)證。這六句話是按時(shí)間的先后順序排列的：一天→從那天起一考試的日期快到了→過了些日子。寫“一天”的共有三句話，是按看到(媽媽桌子上多了一疊課本和作業(yè)本)→想到(媽媽也要學(xué)習(xí)嗎)→聽到(媽媽也要當(dāng)學(xué)生參加學(xué)習(xí)了)的順序?qū)懙?，這三句話交代了媽媽要學(xué)習(xí)，接著兩句話寫媽媽發(fā)憤學(xué)習(xí)，最后一句話寫媽媽領(lǐng)到了畢業(yè)證。

排列順序?yàn)椋?、3、5、2、1、6，然后按照排列順序依次抄句，成為一段通順連貫的話。

三、按先總述后分述的順序排列

有這么一個(gè)習(xí)題：

（）有桉樹、椰子樹、橄欖樹、鳳凰樹，還有別的許多亞熱帶樹木。（）初夏，桉樹葉子散發(fā)出來的香味，飄得滿街滿院都是。（）小城里每一個(gè)庭院都栽了很多樹。

試題

（）鳳凰樹開了花，開得那么熱鬧，小城好像籠罩在一片片紅云中。

根據(jù)這段話的特點(diǎn)，“小城里每一個(gè)庭院都栽了很多樹”這句話是個(gè)中心句，其他三句話都是圍繞著這句話來說的。顯而易見，我們可按先總后分的順序來排列句子。排列的順序?yàn)椋?、3、1、4。

四、按空間推移的順序排列

所謂空間推移，就是由地點(diǎn)的轉(zhuǎn)移，表達(dá)出不同的內(nèi)容。排列時(shí)，要十分注意，不要與其他的方法相混淆。譬如:（）一聽到這熟悉的叫聲，我就猜準(zhǔn)它一定生蛋了。（）我高興地把蛋揀在手里，還熱乎乎的呢。

（）跨進(jìn)屋門，果然，一個(gè)鵝蛋似的雙黃蛋躺在雞窩里。

（）一天下午，我參加學(xué)習(xí)小組后回家，老遠(yuǎn)就聽到我家的那只老母雞“咯咯噠”、“咯咯噠”地在房子里叫個(gè)不停。

這段話，我們可以抓住“屋外”和“屋里”兩個(gè)不同地點(diǎn)，對(duì)句子進(jìn)行排列，順序是2、4、3、1。

把下列錯(cuò)亂的句子，按順序排列起來，整理成一段通順的話。（地點(diǎn)轉(zhuǎn)換順序）

（）遠(yuǎn)遠(yuǎn)望去，山谷里有一條小溪，溪水慢慢地流著。

（）這里的空氣多么新鮮！這里的風(fēng)景多么美麗！

（）藍(lán)藍(lán)的天空飄著一片片白云。

（）不遠(yuǎn)處還有一片綠色的竹林，竹林邊開放著一朵朵火紅的野花。

（）這是什么地方？這是我可愛的家鄉(xiāng)。

解析：很明顯，這是描寫家鄉(xiāng)的風(fēng)景，贊美家鄉(xiāng)的美麗的一段文字。通過閱讀，我們可以看到，作者的視角是在不斷變化的：天空白云——遠(yuǎn)望小溪——近處的竹林野花——總寫——揭示描寫的是家鄉(xiāng)。地點(diǎn)視角的轉(zhuǎn)換是排序的基礎(chǔ)。

排列順序?yàn)槭牵? 4 1 3 5

同學(xué)們:下面有道調(diào)整句子順序的題，同學(xué)們可來試著排列一下，并仔細(xì)考慮你那么排的理由：

（）我把它們投插在一個(gè)鐵壺里，掛在壁間。

試題

（）昨晚從山上回來，采回幾串茨實(shí)、幾簇秋楂、幾枝帶有花蕾的山茶。

（）鮮紅的楂子和嫩黃的茨實(shí)襯著濃碧的山茶葉——這是怎么也不能描畫出的一種風(fēng)味。

（）原來鐵壺中投插著的山茶，竟開了四朵白色的鮮花！

（）這是從什么地方吹來的呀？

（）今早剛從熟睡中醒來時(shí)，室內(nèi)漾著一種清清的不知名的花香。

仔細(xì)閱讀下面兩種排法，看語句是否順暢，邏輯是否合理，思考一下為什么？

“昨晚從山上回來，采回幾串茨實(shí)、幾簇秋楂、幾枝帶有花蕾的山茶。我把它們投插在一個(gè)鐵壺里，掛在壁間。鮮紅的楂子和嫩黃的茨實(shí)襯著濃碧的山茶葉——這是怎么也不能描畫出的一種風(fēng)味。今早剛從熟睡中醒來時(shí)，室內(nèi)漾著一種清清的不知名的花香。原來鐵壺中投插著的山茶，竟開了四朵白色的鮮花！”（排法一）

“昨晚從山上回來，采回幾串茨實(shí)、幾簇秋楂、幾枝帶有花蕾的山茶。我把它們投插在一個(gè)鐵壺里，掛在壁間。今早剛從熟睡中醒來時(shí)，室內(nèi)漾著一種清清的不知名的花香。原來鐵壺中投插著的山茶，竟開了四朵白色的鮮花！鮮紅的楂子和嫩黃的茨實(shí)襯著濃碧的山茶葉——這是怎么也不能描畫出的一種風(fēng)味?！保ㄅ欧ǘ?/p>

兩種排法各有道理，不同的是“喜悅的心情”所處時(shí)間，如果你想要兩次驚喜（剛回家時(shí)的“風(fēng)味”和第二天一早的“花香”），那么就用第一種排法；如果想讓喜悅一并在清晨綻放，那就選第二種排法。另外，與排法二相比，排法一在邏輯上更嚴(yán)密一些，這體現(xiàn)在排法二的最后一句：鮮紅的楂子和嫩黃的茨實(shí)襯著濃碧的山茶葉——，而此前講的是山茶花。

怎么樣，同學(xué)們，乍一看沒什么不同，而正是一個(gè)細(xì)微的差別造成了兩種不同的效果。你以后無論是在作文時(shí)，還是在做別的事，都應(yīng)該謹(jǐn)慎行之，不可粗心大意。

練習(xí)一下試一試:

將下面亂句重新編號(hào)，變成一段通順的話。

一、（）它的莖像個(gè)綠色的圓球，仿佛挺著個(gè)圓圓的“大肚子”。

（）這些花有白的，也有黃的。

（）莖上長滿了小刺，還開過幾次花。

（）我外公家有一盆仙人球。

試題

答案4 3 1

二、（）一天，我對(duì)小明說：“咱們明天捉知了，好嗎？”他愉快地答應(yīng)了。

（）開始，我怎么也捉不到。

（）第二天，我們倆準(zhǔn)備好了網(wǎng)罩，向樹下跑去。

（）小明卻一連捉了三、四只，我真羨慕他。

（）夏天一到，我們村口的大樹上，從早到晚總能傳來“知了——知了——”的叫聲，我多么想親手捉一只知了??！

（）最后，在小明的幫助下，我也套住了一只，心里別提多高興了。

答案

4 3 5 1 6

三、（）走近看，陽光透過樹梢，照進(jìn)樹林。

（）松樹的葉子變得蒼翠，楓樹的葉子變得更火紅。

（）遠(yuǎn)遠(yuǎn)望去，樹林間滿是晨霧，像是淡淡的藍(lán)煙。

（）我站在公園門口。

（）一陣風(fēng)吹來，片片紅葉飄落下來，就像飛舞的彩蝶。

（）當(dāng)我邁步走進(jìn)樹林時(shí)，藍(lán)煙不見了。

答案5 2 1 6 4

四、（）我的家在這個(gè)村莊里。

（）湖面上蕩著幾只小小的漁船。

（）我的腳下是一片平坦的田野。

（）小湖那邊的村莊掩隱在濃密的樹林里。

（）小路不遠(yuǎn)處有個(gè)平靜的小湖。

（）一條筆直的小路從田野穿過。

答案4 1 5 3 2

五

試題

（）我有一條四四方方的手帕。

（）細(xì)長的脖子彎曲著，高高的額頭。

（）手帕上的天鵝全身羽毛像雪一樣潔白。

（）手帕上印著“天鵝游泳”的圖樣。

（）這只天鵝靜靜地浮在藍(lán)色的湖面上，顯得格外美麗。

（）又寬又扁的嘴巴顯得特別突出。

答案4 3 2 6 5

六

（）從前一只公雞，自以為很美麗。

（）有一天，它來到樹下和啄木鳥比美，啄木鳥不和它比。

（）它又來到稻田和青蛙比美，青蛙也不比，它只好往回走。

（）它又來到果園和蜜蜂比美，蜜蜂不和它比。

（）它遇到老牛，傷心的說：“老牛伯伯，我和啄木鳥，蜜蜂`青蛙比美，它們都不理。我呢？”

答案2 4 3 5

七

（）老黃鸝說：“這是卷葉蟲?！?/p>

（）小黃鸝都把脖子伸得長長的，張開黃黃的小嘴叫著：“媽媽，給我吃，給我吃！”

（）那只小黃鸝吃得津津有味，問媽媽：“這是什么呀？真好吃！”

（）老黃鸝看見了連忙飛過去，從那片卷著的葉子里，捉出一條黃綠色的小毛蟲，飛了回來。

（）老黃鸝把小蟲塞到一只小黃鸝的嘴里。

（）海棠樹上有一片嫩葉卷了起來。

答案3 5 2 4 1

按順序排列下列句子:

練習(xí)一: 試題

（）還沒釘幾針，手就被扎破了。

（）回到家里，我把書包往墻上一掛，從媽媽的針線盒里拿出針線。

（）放學(xué)路上，我發(fā)現(xiàn)上衣扣子丟了一顆。

（）我說：“不，自己能做的事情，我要自己做。”

（）找了一顆和原來一樣的扣子，然后學(xué)著媽媽的樣子釘了起來。

（）媽媽看見我扎了手，說：“拿來，我給你釘?！?/p>

答案2 1 6 3 5

練習(xí)二:

（）河上還有一座小橋。

（）月亮灣的后面有山，山坡上長著梨樹和蘋果樹。

（）河里，一群群魚兒正歡快地游來游去，清清的河水倒映著青山、綠樹、小橋。

（）我的家鄉(xiāng)在月亮灣。

（）岸上栽著許多桃樹。樹上開滿了桃花，遠(yuǎn)遠(yuǎn)望去，像一片片火紅的朝霞。

（）前面有一條河，河水繞著村子緩緩地流著。

答案6 3 1 5 2

練習(xí)三:

()麥田的盡頭，村辦的工廠一座挨一座，連成一片。

()河水是那么清澈、明凈，水里的小魚兒自由自在地游來游去。

()小河的另一邊是麥田，如今金燦燦的，向人們報(bào)告著豐收的喜訊。

()一條小河從我們的村子里靜靜地流過。

()山腰上的公路，像一條銀灰色的綢帶飄向遠(yuǎn)方。

()小河的一邊是果園，你看那杏兒發(fā)黃，桃兒發(fā)白，散發(fā)著誘人的清香。

答案2 4 1 6 3

練習(xí)四:

（）激光測距機(jī)不用三秒鐘能測出地球距月球?yàn)槿巳f四千千米遠(yuǎn)。

（）激光能瞄得準(zhǔn)，射得遠(yuǎn)。

試題

（）激光雷達(dá)本領(lǐng)更大，它能隨時(shí)測量出敵人目標(biāo)的準(zhǔn)確距離和方位。

（）利用它的這個(gè)特點(diǎn)可以制成激光測距機(jī)和激光雷達(dá)。

（）激光雷達(dá)還能測量和預(yù)報(bào)出大氣層中含有多少極微量的有害氣體。

答案1 4 2 5

練習(xí)五

（）雨停了，太陽出來了，彩虹掛在天空，蟬叫起來了，蜘蛛又坐在網(wǎng)上了。

（）雷聲接著閃電，隆隆直響，嘩嘩下起了大雨。

（）漸漸地，雷聲小了，雨聲也小了。

（）雨越下越大，往外望去，樹啊，房子啊，都看不清了。

（）忽然，一陣大風(fēng)，吹得樹枝亂擺，一只蜘蛛垂落下來逃走了。

（）滿天烏云黑沉沉地壓下來，樹上的葉子一動(dòng)不動(dòng)，蟬一聲也不叫。

（）池塘里水滿了，明晃晃的，像一面鏡子。

答案 6 3 5 4 2 1 7

練習(xí)六

（）開始，海的遠(yuǎn)處是一片云霧。

（）一轉(zhuǎn)眼，鮮紅的太陽跳了出來，射出萬道金光。

（）老師帶著同學(xué)們?cè)诤┥鲜睾蛉粘觥?/p>

（）接著東方越來越亮。

（）同學(xué)們迎著初升的太陽歡呼起來。

（）天邊的云慢慢變紅了，太陽露出了頭。

答案5 1 3 6 4 小學(xué)高年級(jí)排列句子順序方法舉例及練習(xí)答案

排列句子順序練習(xí)

排列順序的根據(jù)：事情發(fā)展的順序，時(shí)間的先后順序，地點(diǎn)的轉(zhuǎn)換順序，總分的順序、方位順序。

1、錯(cuò)亂的句子敘述了一件完整的事，或者活動(dòng)的具體過程，可以按事情發(fā)展的順序來排列；

試題

2、能從錯(cuò)亂的句子中找出表示時(shí)間概念的詞語，如，早晨、上午、中午、下午等詞，可以按時(shí)間先后順序進(jìn)行排列句子；

3、根據(jù)這段話的特點(diǎn)，能找出一句話是個(gè)中心句，其他句子都是圍繞著這句話來說的，可以按先總后分的順序來排列句子；

4、能從錯(cuò)亂的句子中找出表示地點(diǎn)的詞，由地點(diǎn)的轉(zhuǎn)移，表達(dá)出不同的內(nèi)容，可以按地點(diǎn)的轉(zhuǎn)換順序排列句子。

排列順序的方法：

1、粗讀知大意。

2、細(xì)讀找順序。仔細(xì)地尋找句子中相關(guān)的詞語來確定順序。

3、精讀巧排列。就是從句子中間尋找它們之間有聯(lián)系或相同的詞語。

4、朗讀細(xì)審定。句子大意是否通暢、順序是否正確、是否還有其它排列方法？

排列順序的技巧：排列句子，最主要的是找準(zhǔn)第一句話。

1、寫事的文章，第一句往往有事情發(fā)生的時(shí)間、地點(diǎn)、人物；

2、寫人的文章，第一句往往有對(duì)人物特點(diǎn)的概括；

3、寫景、寫物的文章，第一句往往點(diǎn)明這樣景、物所在的地點(diǎn)，或?qū)@景、物特的點(diǎn)來個(gè)總起。

例

1、按事情發(fā)展順序排列。

()姐姐看見了，大聲喊：“快把它放了，它是益蟲?！?/p>

()大蜻蜓亮晶晶的兩只眼睛，像小玻璃球，一對(duì)紅翅膀不住地扇動(dòng)，非常漂亮。()我和姐姐發(fā)現(xiàn)一只大蜻蜓，落在一棵小樹上。()我悄悄地一捏，把它捉住了。

()我聽了姐姐的話，想到益蟲的好處，馬上把它放了。

正確順序：4 2 1 3 5 解析：我們知道它寫了這樣一件事：“我”抓住了一只蜻蜓，姐姐說它是益蟲，“我”馬上把它放了。應(yīng)該按事情的發(fā)展順序來排列：發(fā)現(xiàn)蜻蜓→觀察蜻蜓→抓住蜻蜓→姐姐讓放蜻蜓→放走蜻蜓。

例

2、按時(shí)間先后順序排列。()從那天起，媽媽發(fā)憤讀書了。

()我去問媽媽，她說：“從今天開始，媽媽也要當(dāng)學(xué)生參加學(xué)習(xí)了?！?)考試的日期快到了，媽媽對(duì)學(xué)習(xí)抓得更緊了，睡得更晚了。

試題

()難道媽媽也要學(xué)習(xí)嗎?我感到很奇怪，心中涌起了一個(gè)問號(hào)。()一天，我發(fā)現(xiàn)媽媽的桌子上多了一疊課本和作業(yè)本。()過了些日子，媽媽終于領(lǐng)到了一張畢業(yè)證。

正確順序：4 3 5 2 1 6 解析：寫了這樣一件事：媽媽當(dāng)了學(xué)生發(fā)憤讀書，領(lǐng)到了畢業(yè)證。這六句話是按時(shí)間的先后順序排列的：一天→從那天起一考試的日期快到了→過了些日子。寫“一天”的共有三句話，是按看到(媽媽桌子上多了一疊課本和作業(yè)本)→想到(媽媽也要學(xué)習(xí)嗎)→聽到(媽媽也要當(dāng)學(xué)生參加學(xué)習(xí)了)的順序?qū)懙?，這三句話交代了媽媽要學(xué)習(xí)，接著兩句話寫媽媽發(fā)憤學(xué)習(xí)，最后一句話寫媽媽領(lǐng)到了畢業(yè)證。

例

3、按地點(diǎn)轉(zhuǎn)換順序排列。

（）遠(yuǎn)遠(yuǎn)望去，山谷里有一條小溪，溪水慢慢地流著。（）這里的空氣多么新鮮！這里的風(fēng)景多么美麗！（）藍(lán)藍(lán)的天空飄著一片片白云。

（）不遠(yuǎn)處還有一片綠色的竹林，竹林邊開放著一朵朵火紅的野花。（）這是什么地方？這是我可愛的家鄉(xiāng)。

正確順序：2 4 1 3 5 解析：這是描寫家鄉(xiāng)的風(fēng)景，贊美家鄉(xiāng)的美麗的一段文字。通過閱讀，我們可以看到，作者的視角是在不斷變化的：天空白云——遠(yuǎn)望小溪——近處的竹林野花——總寫——揭示描寫的是家鄉(xiāng)。地點(diǎn)視角的轉(zhuǎn)換是排序的基礎(chǔ)。

例

4、按時(shí)間先后順序排列。

()華羅庚教授是一位自學(xué)成才的著名的數(shù)學(xué)家。

()二十歲那年，他得了傷寒病，一躺就是半年，病好后，一條腿殘廢，但他毫不泄氣，繼續(xù)向科學(xué)城堡進(jìn)攻。()他十四歲開始自學(xué)數(shù)學(xué)，每天堅(jiān)持自學(xué)十小時(shí)，從不間斷。

()1932年二十二歲的華羅庚應(yīng)清華大學(xué)數(shù)學(xué)系主任熊慶來的邀請(qǐng)，到清華大學(xué)工作。()從十九歲起，華羅庚開始寫數(shù)學(xué)論文。

()在清華期間，他看了更多的數(shù)學(xué)書，并開始學(xué)習(xí)外文。由于他肯下苦功，進(jìn)步很快，二十五歲時(shí)，華羅庚就成了著名的數(shù)學(xué)家。

正確順序：1 4 2 5 3 6 解析：圍繞中心句“華羅庚教授是一位自學(xué)成才的著名的數(shù)學(xué)家”，按照14歲至25歲的試題

時(shí)間順序，敘述了華羅庚的成功經(jīng)歷。排列這段話時(shí)，我們可以抓住“14歲”、“19歲”、“20歲”、“22歲”、“25歲”這些表示年齡的詞，也就是以時(shí)間順序來排列句子。

例

5、按地點(diǎn)轉(zhuǎn)換順序排列。

（）小溪的一邊是果園。春天，花香彌漫；秋天，碩果累累。()田野的盡頭，連綿起伏的山峰猶如大海里起伏的波濤。()溪水是那么清澈、明凈，水里的小魚無憂無慮地游來游去。()山腰的公路，像一條銀灰色的帶子飄向遠(yuǎn)方。()一條小溪從我們村里流過。

()小溪的另一邊是田野。如今沉甸甸的麥穗，正點(diǎn)著頭報(bào)告豐收的喜訊。

正確順序：3 5 2 6 1 4

例

6、按事情發(fā)展順序排列。

（）古時(shí)候，有位將軍得到一張射得又遠(yuǎn)又準(zhǔn)的好弓。()那美麗的圖案，看上去非常精美。()將軍高興極了，想試一下弓。

()于是，它請(qǐng)人在弓上雕刻了各式各樣的花紋。()他用力一拉，沒想到，弓斷了。

()他很珍惜這張弓，想把它修飾一下。

正確順序：1 4 5 3 6 2 例

7、按先總后分的順序來排列句子。

（）有桉樹、椰子樹、橄欖樹、鳳凰樹，還有別的許多亞熱帶樹木。（）初夏，桉樹葉子散發(fā)出來的香味，飄得滿街滿院都是。（）小城里每一個(gè)庭院都栽了很多樹。

（）鳳凰樹開了花，開得那么熱鬧，小城好像籠罩在一片片紅云中。

排列順序：2 3 1 4。

試題

根據(jù)這段話的特點(diǎn)，“小城里每一個(gè)庭院都栽了很多樹”這句話是個(gè)中心句，其他三句話都是圍繞著這句話來說的。顯而易見，我們可按先總后分的順序來排列句子。

例

8、（）我們站在海灘上靜靜地等著．（）啊，太陽升起來了．

（）上個(gè)星期五，我們一家人來到海灘看日出．（）過了一會(huì)兒，太陽象個(gè)大火球，一下子跳出了海面．（）漸漸地，東方開始發(fā)白了，還出現(xiàn)了一些紅霞．（）我們來到海灘的時(shí)候，天空還是灰蒙蒙的．

正確順序：3 6 1 5 4 2 例

9、（）如果書是借來的，就把重要的內(nèi)容摘記下來。

（）達(dá)爾文曾風(fēng)趣地說：“這里面的知識(shí)，足夠我一生使用了?！保ǎ┑匀粓?jiān)持每天學(xué)習(xí)，一直到去世。

（）這樣的筆記本，保存了一大柜子，還有三四十個(gè)大紙夾，里面有各種各樣的資料。

（）達(dá)爾文讀書非常認(rèn)真，對(duì)不理解的內(nèi)容，絕不放過一點(diǎn)。（）達(dá)爾文到了晚年，身體很不好，經(jīng)常生病。

正確順序：2 4 6 3 1 5 例

10、（）每當(dāng)春暖花開或果實(shí)累累的季節(jié)，小鳥經(jīng)常飛到村莊里來。（）當(dāng)?shù)氐拇迕窬桶阉Q作禮鳥。

（）投下的東西不是香氣撲鼻的花，就是清甜可口的野果。（）非洲某地，有一種十分討人喜愛的小鳥。

（）將銜著的東西丟到人們的身上或投到屋里。

正確順序：2 5 4 1 3 例

11、試題

（）不管刮風(fēng)下雨，從不間斷。（）當(dāng)時(shí)，他還沒有那么多錢買本子。

（）陳毅5歲就開始練習(xí)毛筆字，上小學(xué)后，每天還要寫一百個(gè)大字，二百個(gè)小字。（）便用毛筆蘸著米湯在黃紙上寫，晾干后，字跡沒有了，第二天再寫。（）后來，連最便宜的黃紙也買不起了，他就到池塘邊沙地上練字。（）他天天寫，天天練，一個(gè)學(xué)期過去了，那盒黃紙比原來重了半斤。（）由于他天天練習(xí)，陳毅元帥的毛筆字寫得又漂亮，又有勁。

正確順序：6 2 1 3 5 4 7 例

12、（）我和小朋友站在棗樹下，抬頭望著這些大紅棗，仿佛已經(jīng)吃到嘴里，那么甜，那么脆，真好吃。

（）春天，棗樹上開滿了淺黃色的棗花。

（）我們?nèi)滩蛔∨郎戏咳ゴ驐?，媽媽不讓我上房，我只好在下面拾棗。（）夏天，棗樹上結(jié)滿了小青棗。

（）到了秋天，小青棗慢慢地變紅了，變成了很大很大的紅棗，樹上好像掛滿了小燈籠似的。

（）我們?cè)豪镉幸豢脳棙?，那是一棵古老而又高大的棗樹?/p>

（）這棗樹不知道是誰種的，我嘴里吃著又天又脆的棗，心里十分感動(dòng)種棗樹的人。（）他們?cè)跇渖蠐u來晃去，棗好像涼雹似的打在我的頭上。（）為了吃棗，我只得抱著頭去拾棗，不一會(huì)兒就拾了一籃子。

正確順序：5 2 6 3 4 1 9 7 8 例

13、（）國王很高興，就叫仆人牽來一匹馬，送給了那個(gè)農(nóng)民。（）國王猜透了財(cái)主的黑心，只送給他一只大南瓜。財(cái)主氣死了。

（）在一個(gè)農(nóng)民的菜園里，長了一個(gè)很大很大的南瓜，農(nóng)民把大南瓜送給了國王。（）這件事被一個(gè)財(cái)主知道了，他很羨慕。

（）財(cái)主也送了一匹好馬給國王，想得到國王更多的禮物。

試題

正確順序：2 5 1 3 4 例

14、（）一早醒來，??！地上，樹上，房子上一片積雪，成了白色的世界。（）漸漸地雨停了，雪花越下越大。

（）傍晚，天氣突然冷起來，天空中布滿烏云。（）當(dāng)人們進(jìn)入夢(mèng)鄉(xiāng)時(shí)，雪花還在紛紛揚(yáng)揚(yáng)地飄著。（）不一會(huì)兒，小雨夾著雪花一同飄落下來。

正確順序：5 3 1 4 2

試題

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

第一章

第1章作業(yè)：1.1,1.2,1.6(1)(3)1.8 1.1 簡述下列概念：數(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 按增長率由小至大的順序排列下列各函數(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ù)以上分析按增長率由小至大的順序可排列如下：(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ǔ)的線性表長度變化不大，易于事先確定其大小時(shí)，為了節(jié)約存儲(chǔ)空間，宜采用順序表；反之，當(dā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)前的表長度 } 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表的表長分別是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ì)前測試入隊(duì)后頭尾指針是否會(huì)重合，如果會(huì)重合就認(rèn)為隊(duì)列已滿。三是設(shè)置一計(jì)數(shù)器記錄隊(duì)列中元素總數(shù)，不僅可判別空或滿，還可以得到隊(duì)列中元素的個(gè)數(shù)。

3.3設(shè)長度為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ǔ)空間。