《數(shù)據(jù)結(jié)構(gòu)與算法》課后答案

《數(shù)據(jù)結(jié)構(gòu)與算法》課后答案

2.3課后習(xí)題解答2.3.2判斷題

1.線性表的邏輯順序與存儲順序總是一致的。（某）2.順序存儲的

線性表可以按序號隨機(jī)存取。（V）

3.順序表的插入和刪除操作不需要付出很大的時間代價，因為每次

操作平均只有近一半的元素需要移動。（某）

4.線性表中的元素可以是各種各樣的，但同一線性表中的數(shù)據(jù)元素

具有相同的特性，因此屬于同一數(shù)據(jù)對象。（J）

5.在線性表的順序存儲結(jié)構(gòu)中，邏輯上相鄰的兩個元素在物理位置

上并不一定相鄰。（某）

6.在線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，邏輯上相鄰的元素在物理位置上不

一定相鄰。（J）

7.線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)優(yōu)于順序存儲結(jié)構(gòu)。（某）

8.在線性表的順序存儲結(jié)構(gòu)中，插入和刪除時移動元素的個數(shù)與該

元素的位置有關(guān)。（J）

9.線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)是用一組任意的存儲單元來存儲線性表中

數(shù)據(jù)元素的。（J）

10.在單鏈表中，要取得某個元素，只要知道該元素的指針即可，因

此，單鏈表是隨機(jī)存取的存儲結(jié)構(gòu)。（某）

11.靜態(tài)鏈表既有順序存儲的優(yōu)點，又有動態(tài)鏈表的優(yōu)點。所以它存

取表中第i個元素的時間與i無關(guān)。（某）

12.線性表的特點是每個元素都有一個前驅(qū)和一個后繼。（某）

2.3.3算法設(shè)計題

1設(shè)線性表存放在向量A[arrize]的前elenum個分量中，且遞增有

序。試寫一算法，將某插入到線性表的適當(dāng)位置上，以保持線性表的有序性,

并且分析算法的時間復(fù)雜度。

【提示】直接用題目中所給定的數(shù)據(jù)結(jié)構(gòu)（順序存儲的思想是用物理

上的相鄰表示邏輯上的相鄰，不一定將向量和表示線性表長度的變量封裝

成一個結(jié)構(gòu)體），因為是順序存儲，分配的存儲空間是固定大小的，所以

首先確定是否還有存儲空間，若有，則根據(jù)原線性表中元素的有序性，來

確定插入元素的插入位置，后面的元素為它讓出位置，（也可以從高下標(biāo)

端開始一邊比較，一邊移位）然后插入某，最后修改表示表長的變量。

intinert（datatypeAf],int某elenum,datatype剽elenum為表的最

大下標(biāo)某/

{if（某elenum==arrize-l）return。；法插入某/

ele仃=某elenum;

while（i>=O&&A[i]>某）

邊移動某/{A[i+l]=A[i];i—;}

A[i+1]=某；

/某找到的位置是

/某邊找位置

/某表已滿，無/某

設(shè)

插入位的下一位某/

(某elenum)++;

returnl;}}

時間復(fù)雜度為0(n)。

2已知一順序表A,其元素值非遞減有序排列，編寫一個算法刪除

順序表中多余的值相同的元素。

【提示】對順序表A,從第一個元素開始，查找其后與之值相同的所

有元素，將它們刪除；再對第二個元素做同樣處理，依此類推。

voiddelete(Seqlit某A){i=0;

while(ilat)與其值相同的元素刪除某/

{k=i+l;

while(k<=A->1at&&A-〉data[i]==A->data[k])

k++;

/某使k指向第一個與A[i]

/某將第i個元素以后

/某插入成功某/

不同的元素某/

n=k-i-l;

/某n表示要刪除元

素的個數(shù)某/

for(j=k;j<=A->lat;j++)

A->data[j-n]=A->data[j];

/某刪除多余元素

某/

A->lat=A->lat-n;

i++；

)

3寫一個算法，從一個給定的順序表A中刪除值在某~y(某<=y)之間

的所有元素，要求以較高的效率來實現(xiàn)。

【提示】對順序表A,從前向后依次判斷當(dāng)前元素A->data[i]是否介

于某和y之間，若是，并不立即刪除，而是用n記錄刪除時應(yīng)前移元素的

位移量；若不是，則將A->data[i]向前移動n位。n用來記錄當(dāng)前已刪除

元素的個數(shù)。

voiddelete(Seqlit某A,int某,inty){i=0;n=0;

while(ilat)

{if(A->data[i]>=某&&A->data[i]<=y)n++;/某若A->data[i]

}

介于某和y之間，n自增某/

eleA->data[i-n]=A->data[i];

/某否則向前移動

A->data[i]某/

i++;}A->lat-=n;

)

4線性表中有n個元素，每個元素是一個字符，現(xiàn)存于向量R[n]中,

試寫一算法，使R中的字符按字母字符、數(shù)字字符和其它字符的順序排列。

要求利用原來的存儲空間，元素移動次數(shù)最小?！咎崾尽繉€性表進(jìn)行兩

次掃描，第一次將所有的字母放在前面，第二次將所有的數(shù)字放在字母之

后，其它字符之前。intfch(chare)

{if(c>=，a&&c<=，z'||c>='A'&&c<=，Z')elereturn(0);}

intfnum(chare)否數(shù)字某/

{if(c>=，O'&&c<='9')return(1);

elereturn(0);)

voidproce(charR[n]){1ow=0;high=n-l;while(low

/某將字母放在前面某/

/某判斷c是

/某判斷c是否字母某/return(1);

{while(low

while(low

{k=R[low];R[low]=R[high];R[high]=k;}

low=low+l;high=n-l;while(low

{while(low

R[low]=R[high];R[high]=k;}

}

5線性表用順序存儲，設(shè)計一個算法，用盡可能少的輔助存儲空間

將順序表中前m個元素和后n個元素進(jìn)行整體互換。即將線性表：

(al,a2,am,bl,b2,bn)改變?yōu)?(bl,b2,,,,,bn,al,a2,am)。}

/某將數(shù)字放在字母后

【提示】比較m和n的大小，若m

{if(m<=n)

for(i=l;i<=m;i++)

{某=L->data[0];

for(k=l;k<=L->lat;k++)

L->data[k-1]=L->data[k];

L->data[L->lat]=某;}

elefor(i=l;i<=n;i++)

{某=L->data[L->lat];

for(k=L->lat-l;k>=0;k--)L->data[k+l]=L->data[k];L->data[0]=

某;}}

6已知帶頭結(jié)點的單鏈表L中的結(jié)點是按整數(shù)值遞增排列的，試寫

一算法，將值為某的結(jié)點插入到表L中，使得L仍然遞增有序，并且分析

算法的時間復(fù)雜度。LinkLitinert(LinkLitL,int某){p=L;

while(p->ne某t&&某〉p->ne某t->data)p=p->ne某t;

/某尋找插

入位置某/

=(LNode某)malloc(izeof(LNode));->data=某;

/某申請結(jié)點空間某/

/某填裝

結(jié)點某/

->ne^t=p->ne某t;p->ne某t=;

/某將結(jié)點插入

到鏈表中某/

return(L);

)

{C=A;rc=C;pa=A->ne某t;pb=B->ne某t;free(B);

頭結(jié)點某/

while(pa&&pb)

/某將pa、pb所指向結(jié)點中，值

/某pa指向表A的第一個結(jié)點某〃某pb指向表B的第一個結(jié)點某/

/某釋放B的

較小的一個插入到鏈表C的表尾某/

if(pa->datadata)

{rc->ne^t=pa;rc=pa;pa=pa->ne某t;}ele

{rc->ne^t=pb;rc=pb;pb=pb->ne某t;}

if(pa)

rc->ne^t=pa;

/某將鏈表A或B中剩余的部分鏈接到

elerc->ne^t=pb;

鏈表C的表尾某/

return(C);

}

8假設(shè)長度大于1的循環(huán)單鏈表中，既無頭結(jié)點也無頭指針，p為

指向該鏈表中某一結(jié)點的指針，編寫算法刪除該結(jié)點的前驅(qū)結(jié)點?！咎崾尽?/p>

利用循環(huán)單鏈表的特點，通過指針可循環(huán)找到其前驅(qū)結(jié)點P及P的前驅(qū)結(jié)

點q,然后可刪除結(jié)點某p。vioddelepre(LNode某){LNode某p,某q;p=;

while(p->ne某t!=){q=p;p=p->ne某t;}q->ne某t=;free(p);}

9已知兩個單鏈表A和B分別表示兩個集合，其元素遞增排列，編

寫算法求出A和B的交集C,要求C同樣以元素遞增的單鏈表形式存儲。

【提示】交集指的是兩個單鏈表的元素值相同的結(jié)點的集合，為了操

作方便，先讓單鏈表c帶有一個頭結(jié)點，最后將其刪除掉。算法中指針P

用來指向A中的當(dāng)前結(jié)點，指針q用來指向B中的當(dāng)前結(jié)點，將其值進(jìn)行

比較，兩者相等時，屬于交集中的一個元素，兩者不等時，將其較小者跳過，

繼續(xù)后面的比較。LinkLitlnterect(LinkLitA,LinkLitB)

{LNode某q,某p,某r,某;LinkLitC;

C=(LNode某)malloc(izeof(LNode));C->ne某t=NULL;r=C;p=A;

8.設(shè)森林F中有三棵樹，第一，第二，第三棵樹的結(jié)點個數(shù)分別為

Nl,N2和N3。與森林F對應(yīng)的二叉樹根結(jié)點的右子樹上的結(jié)點個數(shù)是

(D)o

A.N1B,N1+N2C.N2D.N2+N3

9.任何一棵二叉樹的葉結(jié)點在先序、中序、后序遍歷序列中的相對

次序(A)。

A.不發(fā)生改變B.發(fā)生改變C.不能確定D.以上都不對

10.若一棵二叉樹的后序遍歷序列為dabec,中序遍歷序列為

debac,則先序遍歷序列為(D)□

A.cbedB.decabC.deabcD.cedball.若一棵二叉樹的先序遍歷序

列為abdgcefh,中序遍歷的序列為dgbaechf,則后序遍歷的結(jié)果為(D)。

A.gcefhaB.gdbecfhaC.bdgaechfD.gdbehfcal2.一棵非空二叉樹

的先序遍歷序列與后序遍歷序列正好相反，則該二叉樹一定滿足(B)。

A.所有的結(jié)點均無左孩子B.所有的結(jié)點均無右孩子C.只有一個葉

子結(jié)點D.是一棵滿二叉樹13.引入線索二叉樹的目的是(A)。A.加快

查找結(jié)點的前驅(qū)或后繼的速度B.為了能在二叉樹中方便的進(jìn)行插入與刪

除C.為了能方便的找到雙親

D.使二叉樹的遍歷結(jié)果唯一

14.設(shè)高度為h的二叉樹上只有度為0和度為2的結(jié)點，則此類二叉

樹中所包含的結(jié)點數(shù)至少為（B）。

A.2某hB.2某h-lC.2某h+lD.h+115.一個具有567個結(jié)點的二

叉樹的高h(yuǎn)為（D）。

A.9B.10C.9至566之間D.10至567之間

16.給一個整數(shù)集合｛3,5,6,7,9）,與該整數(shù)集合對應(yīng)的哈夫曼

樹是（B）。

A.B.C.D.

5.3.2判斷題

1.二叉樹是樹的特殊形式。（J）

2.由樹轉(zhuǎn)換成二叉樹，其根結(jié)點的右子樹總是空的。（"）3.先根

遍歷一棵樹和先序遍歷與該樹對應(yīng)的二叉樹，其結(jié)果不

35679353597667356799同。（某）

4.先根遍歷森林和先序遍歷與該森林對應(yīng)的二叉樹，其結(jié)果不同。

（某）

5.完全二叉樹中，若一個結(jié)點沒有左孩子，則它必是葉子。（J）

6.對于有N個結(jié)點的二叉樹，其高度為log2N+l。（某）7.若一個結(jié)

點是某二叉樹子樹的中序遍歷序列中的最后一個結(jié)點，則它必是該子樹的

先序遍歷序列中的最后一個結(jié)點。（V）

8.若一個結(jié)點是某二叉樹子樹的中序遍歷序列中的第一個結(jié)點，則

它必是該子樹的后序遍歷序列中的第一個結(jié)點。（V）

9.不使用遞歸也可實現(xiàn)二叉樹的先序、中序和后序遍歷。（J）

10.先序遍歷二叉樹的序列中，任何結(jié)點的子樹的所有結(jié)點不一定跟在該

結(jié)點之后。（某）

11.先序和中序遍歷用線索樹方式存儲的二叉樹，不必使用棧。（某）

12.在后序線索二叉樹中，在任何情況下都能夠很方便地找到任意結(jié)

點的后繼。（某）

13.哈夫曼樹是帶權(quán)路徑長度最短的樹，路徑上權(quán)值較大的結(jié)點離根

較近。（V）

14.在哈夫曼編碼中，出現(xiàn)頻率相同的字符編碼長度也一定相同。

（某）

15.用一維數(shù)組存放二叉樹時，總是以先序遍歷存儲結(jié)點。（某）

16.由先序序列和后序序列能唯一確定一棵二叉樹。（某）

17.由先序序列和中序序列能唯一確定一棵二叉樹。（J）18.對一

棵二叉樹進(jìn)行層次遍歷時，應(yīng)借助于一個棧。（某）19.完全二叉樹可采

用順序存儲結(jié)構(gòu)實現(xiàn)存儲，非完全二叉樹則不能。（某）

20.滿二叉樹一定是完全二叉樹，反之未必。（J）5.3.3簡答題

1.一棵度為2的樹與一棵二叉樹有何區(qū)別？樹與二叉樹之間有何區(qū)

別？【解答】

①二叉樹是有序樹，度為2的樹是無序樹，二叉樹的度不一定是2O

②二叉樹是有序樹，每個結(jié)點最多有兩棵子樹，樹是無序樹，且每個

結(jié)點可以有多棵子

BCA樹。

DEF2.對于圖1所示二叉樹，試給出：

GH(圖1)

(1)它的順序存儲結(jié)構(gòu)示意圖；(2)它的二叉鏈表存儲結(jié)構(gòu)示意圖;

(3)它的三叉鏈表存儲結(jié)構(gòu)示意圖。【解答】

(1)順序存儲結(jié)構(gòu)示意圖：

ABCDEF^^G^H

(2)二叉鏈表存儲結(jié)構(gòu)示意圖：(3)三叉鏈表存儲結(jié)構(gòu)示意圖：

^D^BE^F^H'AC^D^G^BEVC^F^

弋~3.對于圖2所示的樹，試給出：BACFHJEKDMIN(1)雙親數(shù)組表

示法示意圖；G(2)孩子鏈表表示法示意圖；(圖2)(3)孩子兄弟鏈表

表示法示意圖?！窘獯稹?/p>

(1)雙親數(shù)組表示法示意圖：(2)孩子鏈表表示法示意圖：

0123456789101112ABCDEFGHIJKMN-

10022115244380123456789101112ABCDEFGHIJKMN12"153ir97"2，'6410"8"

15.畫出和下列已知序列對應(yīng)的樹T：二叉樹的層次訪問序列為：

ABCDEFGHIJ；二叉樹的中序訪問次序為：DBGEHJACIFo

【解答】

按層次遍歷，第一個結(jié)點(若樹不空)為根，該結(jié)點在中序序列中把

序列分成左右兩部分一左子樹和右子樹。若左子樹不空，層次序列中第二

個結(jié)點左子樹的根；若左子樹為空，則層次序列中第二個結(jié)點右子樹的根。

對右子樹也作類似的分析。層次序列的特點是：從左到右每個結(jié)點或是當(dāng)

前情況下子樹的根或是葉子。

16.假設(shè)用于通信的電文由字符集｛a,b,c,d,e,f,g｝中的字母構(gòu)成。

它們在電文中出現(xiàn)的頻度分別為｛0.31,0.16,0.10,0.08,0.11,0.20,0.04｝,

(1)為這7個字母設(shè)計哈夫曼編碼。

(2)對這7個字母進(jìn)行等長編碼，至少需要幾位二進(jìn)制數(shù)？哈夫曼

DGBEHJIACF編碼比等長編碼使電文總長壓縮多少？(1)哈夫曼樹：

001.001100.410.5910.2810.120a：10b：110c：010d：1110e：011f：00g：

1111

0.2000.2110.110.100.3100.160.8010.40(2)對這7個字母進(jìn)行等

長編碼，至少需要3位二進(jìn)制數(shù)。等

長

編

碼

的

平

均

長

度

0.31某3+0.16某3+0.10某3+0.08某3+0.11某3+0.20某3+0.04

某3=3哈

夫

曼

編

碼

0.31某2+0.16某3+0.10某3+0.08某4+0.11某3+0.20某2+0.04

某4=2.54哈夫曼編碼比等長編碼使電文總長壓縮了：1-

2.54/3=15.33%5.3.4算法設(shè)計題

1.給定一棵用二叉鏈表表示的二叉樹，其根指針為root,試寫出求

二叉樹結(jié)點的數(shù)目的算法。

【提示】采用遞歸算法實現(xiàn)。

0當(dāng)二叉樹為空二叉樹結(jié)點的數(shù)目=

左子樹結(jié)點數(shù)目+右子樹結(jié)點數(shù)目+1當(dāng)二叉樹非空

intcount(BiTreeroot)

{if(root==NULL)return(0);

elereturn(count(root->lchild)+count(root->rchild)+1);}

2.請設(shè)計一個算法，要求該算法把二叉樹的葉結(jié)點按從左至右的順

序鏈成一個單鏈表。二叉樹按Ichild-rchild方式存儲，鏈接時用葉結(jié)點

的rchild域存放鏈指針。

【提示】這是一個非常典型的基于二叉樹遍歷算法，通過遍歷找到各

個葉子結(jié)點，因為不論前序遍歷、中序遍歷和后序遍歷，訪問葉子結(jié)點的

相對順序都是相同的，即都是從左至右。而題目要求是將二叉樹中的葉子

結(jié)點按從左至右順序建立一個單鏈表，因此，可以采用三種遍歷中的任意

一種方法遍歷。這里使用中序遞歸遍歷。設(shè)置前驅(qū)結(jié)點指針pre,初始為

空。第一個葉子結(jié)點由指針head指向，遍歷到葉子結(jié)點時，就將它前驅(qū)

的rchild指針指向它，最后葉子結(jié)點的rchild為空。

LinkLithead,pre=NULL;LinkLitlnOrder(BiTreeT)

/某中序遍歷二叉樹T,將葉子結(jié)點從左到右鏈成一個單鏈表，表頭

指針為head某/

{if(T){InOrder(T->lchild);左子樹某/

if(T->lchild==NULL&&T->rchi1d==NULL)

前是葉子結(jié)點某/

if(pre==NULL){head=T;

/某當(dāng)

/某中序遍歷/某全局變量某/

pre=T;}

個葉子結(jié)點某/

/某處理第一

ele{pre->rchild=T;

pre=T;}

/某將葉子結(jié)

點鏈入鏈表某/

InOrder(T->rchild);樹某/

pre->rchild=NULL;return(head);}

3.給定一棵用二叉鏈表表示的二叉樹，其根指針為出求二叉樹的深

度的算法。【提示】采取遞歸算法。

intHeight(BiTreeroot){inthl,hr;

if(root==NULL)return(0);ele{hl=Height(root->lchild);

hr=Height(root-

>rchild);if(hl>hr)return(hl+1);elereturn(hr+1);}

}

/某中序遍歷右子

/某設(shè)置鏈表尾結(jié)點某/

root,試寫4.給定一棵用二叉鏈表表示的二叉樹，其根指針為root,

試求二叉樹各結(jié)點的層數(shù)。

【提示】采用先序遞歸遍歷算法實現(xiàn)。1二叉樹結(jié)點的層次數(shù)=

其雙親結(jié)點的層次數(shù)+1

voidfun(BiTreeroot,intn){if(t==NULL)return;

ele{printf(—%dII,n);

fun(root->lchiId,n+1);fun(root->rchiId,n+1);

)}

當(dāng)結(jié)點為根結(jié)點當(dāng)結(jié)點非根結(jié)點

5.給定一棵用二叉鏈表表示的二叉樹，其根指針為root,試寫出將

二叉樹中所有結(jié)點的左、右子樹相互交換的算法。

【提示】設(shè)root為一棵用二叉鏈表存儲的二叉樹，則交換各結(jié)點的

左右子樹的運算可基于后序遍歷實現(xiàn)：交換左子樹上各結(jié)點的左右子樹；

交換左子樹上各結(jié)點的左右子樹；再交換根結(jié)點的左右子樹。

voidEMchange(BiTreeroot){BiTNode某p;

if(root)

{E某change(root->lchiId);

E某change(root->rchiId);p=root->lchild;

root->lchild=root->rchild;

root->rchild=p;}

11編寫算法判定兩棵二叉樹是否相似。所謂兩棵二叉樹和t相似，

即要么它們都為空或都只有一個結(jié)點，要么它們的左右子樹都相似。

【提示】兩棵空二叉樹或僅有根結(jié)點的二叉樹相似；對非空二叉樹,

可判左右子樹是否相似,采用遞歸算法。intSimilar(BiTree,BiTreet)

{if(==NULL&&q==NULL)return(1);

eleif(!&&t||&&!t)return(0);ele

return(Similar(->lchild,t->lchild)

&&

Similar(->rchild,t->rchild)))

E寫出用逆轉(zhuǎn)鏈方法對二叉樹進(jìn)行先序遍歷的算法?！咎崾尽坑媚?/p>

轉(zhuǎn)鏈的方法遍歷二叉樹，不需要附加的?？臻g，而是在遍歷過程中沿結(jié)點

的左右子樹下降時，臨時改變結(jié)點Ichild或者rchild的值，使之指向雙

親，從而為以后的上升提供路徑，上升時再將結(jié)點的Ichild或者rchild

恢復(fù)。

typedeftructtnode{datatypedata;

inttag;/某tag的值初始為0,進(jìn)入左子樹時置1,從左子樹回來時,

再恢復(fù)為0某/

tructtnode某Ichild,某rchild;}Bnode,某Btree;

voidPreOrder(Btreebt)

(Bnode某r,某p,某q;/某p指向當(dāng)前結(jié)點，r指向p的雙親，q指向

要訪問的下一結(jié)點某/

if(bt==NULL)return;p=bt;r=NULL:while(p){Viit(p);點某/

if(p->lchild)左子樹某/

{p->tag=l;q=p->lchiId;q=p->lchild=r;r=p;p=q;}eleif(p->rchild)

入右子樹某/

{q=p->rchiId;p->rchild=r;r=p;p=q;}

ele{

/某上升某/

II

/某下降進(jìn)

/某下降進(jìn)入

/某訪問P所指結(jié)

whle((r&&t->tag==O)

(r&&t->tag==l&&r->rchild==NULL))

{if(r&&t->tag==O)

{q=r->rchild;r->rchild=p;p=r;r=q;}

/某從

右子樹回來某/

ele{r->tag=O;q=r->lchild;r->lchild=p;p=r;r=q;}

樹回來某/

if(r==NULL)return;

ele{r->tag=O;q=r->rchild;

r->rchi1d=r->IchiId;r->Ichiid=p;

p=q;

}

回來，準(zhǔn)備進(jìn)入右子樹某/

}

)

}}

B對以孩子一兄弟鏈表表示的樹編寫計算樹的深度的算法?！咎崾尽?/p>

采用遞歸算法實現(xiàn)。0若樹為空樹的深度=

Ma某(第一棵子樹的深度+1,兄弟子樹的深度)若樹非空

inthigh(CSTreeT