《數(shù)據(jù)結(jié)構(gòu)(Java版)(第2版)》習(xí)題解答

數(shù)據(jù)結(jié)構(gòu)（Java版）（第2版）

習(xí)題解答

葉核亞編著

目錄

第。章Java程序設(shè)計(jì)基礎(chǔ)..........................................................1

【習(xí)0.1】實(shí)驗(yàn)哥德巴赫猜想。................................................1

【習(xí)0.2］實(shí)驗(yàn)楊輝三角形。..................................................1

【習(xí)0.3］實(shí)驗(yàn)金額的中文大寫(xiě)形式。..........................................1

【習(xí)0.4］實(shí)驗(yàn)下標(biāo)和相等的數(shù)字方陣。........................................I

第6章樹(shù)和二叉樹(shù).................................................................3

【習(xí)6.1】畫(huà)出3個(gè)結(jié)點(diǎn)的各種形態(tài)的樹(shù)和二叉樹(shù)。.................................3

【習(xí)6.2］找出分別滿足下面條件的所有二叉樹(shù)。..................................3

【習(xí)6.3】輸出葉子結(jié)點(diǎn)。.......................................................3

【習(xí)6.4］實(shí)驗(yàn)單鏈表的全部替換操作。........................................4

【習(xí)6.5］實(shí)驗(yàn)單鏈表的全部刪除操作。.........................................4

【習(xí)6.6】折半查找的遞歸算法。.................................................5

【習(xí)6.7】二叉排序樹(shù)查找的遞歸算法。...........................................6

【習(xí)6.8】二叉排序樹(shù)插入結(jié)點(diǎn)的非遞歸算法。.....................................7

【習(xí)6.9】判斷一棵二叉樹(shù)是否為二叉排序樹(shù)。.....................................8

第7章排序.......................................................................10

【習(xí)7.1】判斷一個(gè)數(shù)據(jù)序列是否為最小堆序列。..................................10

【習(xí)7.2】歸并兩條排序的單鏈表。..............................................10

【習(xí)7.3】說(shuō)明二叉排序樹(shù)與堆的差別。..........................................12

圖0.1下標(biāo)和相等的數(shù)字方陣算法描述.............................................I

圖6.13個(gè)結(jié)點(diǎn)樹(shù)和二叉樹(shù)的形態(tài)..................................................3

圖6.2單支二叉樹(shù)...............................................................3

圖7.2歸并兩條排序的單鏈表....................................................11

表0.1intn=4;ength;j++)

2

pOPlp2P（）PlP2

(a)第一次匹配，因po=p2，可知t2Kp0(b)第二次匹配，從t3開(kāi)始比較

第0章Java程序設(shè)計(jì)基礎(chǔ)

【習(xí)0.1】實(shí)驗(yàn)哥德巴赫猜想。

【習(xí)02]實(shí)驗(yàn)楊輝三角形。

【習(xí)。3】實(shí)驗(yàn)金額的中文大寫(xiě)形式。

【習(xí)0.4】實(shí)驗(yàn)下標(biāo)和相等的數(shù)字方陣。

輸出下列方陣（當(dāng)n=4時(shí)）。

1267或3410

3581325911

491214681215

101115167131416

采用二維數(shù)組實(shí)現(xiàn)。二維數(shù)組中，每一條斜線上各元素下標(biāo)和相等，如圖所示。

程序如下。

publicclassUpmat

pubIicstaticvoidmain(Stringargs[])

-1

表0.1intn=4;ength;j++)

(a)第一次匹配，因po=P2,可知t2±P。(b)第二次匹配，從t3開(kāi)始比較

target

pattern

(a)to=po?ti^pp比較2次，ncxt[1]=-1(b)t2=p(),ta^pp比較2次，ncxt[1]=-l

ength,;

for(inti=0;i<i++)

for(intj=0;j<[i].length;j++)

[j][i]=[i][j]；

returntrans;

)

-2-

第6章樹(shù)和二叉樹(shù)

【習(xí)6.1】畫(huà)出3個(gè)結(jié)點(diǎn)的各種形態(tài)的樹(shù)和二叉樹(shù)。

3個(gè)結(jié)點(diǎn)的樹(shù)有2種形態(tài)，3個(gè)結(jié)點(diǎn)的二叉樹(shù)有5種形態(tài)，如圖所示。

(a)3個(gè)結(jié)點(diǎn)的樹(shù)具有2種基本形態(tài)(b)3個(gè)結(jié)點(diǎn)的二又朝具有5種基本形態(tài)

圖6.13個(gè)結(jié)點(diǎn)樹(shù)和二叉樹(shù)的形態(tài)

【習(xí)&2】找出分別滿足下面條件的所有二叉樹(shù)。

①先根遍歷序列和中根遍歷序列相同：右單支二叉樹(shù)，如圖(a)所示。

②中根遍歷序列和后根遍歷序列相同：左單支二叉樹(shù)，如圖(b)所示。

③先根遍歷序列和后根遍歷序列相同：空樹(shù)，只有一個(gè)根結(jié)點(diǎn)的二叉樹(shù)。

(a)右單支二叉樹(shù)(b)左單支二叉樹(shù)

圖6.2單支二叉樹(shù)

【習(xí)6.3】輸出葉子結(jié)點(diǎn)。

在BinaryTree類中增加以下方法。

publicvoidIeaf()quals(i))))

returnfalse;

returntrue;

-3-

)

returnfalse;

)

【習(xí)6.4]實(shí)驗(yàn)單鏈表的全部替換操作。

在SinglyLinkedList單鏈表類中，增加替換操作方法如下。

publicbooleanreplace(Objectobj,EeIement)//詳見(jiàn)實(shí)驗(yàn)

pubIicbooleanreplaceAlI(Objectobj,Eelement)〃將所有元素值為obj的結(jié)點(diǎn)值替

換為eIement

(〃若替換成功返回true,否則返回false

booleandone二千aIse;

if(obj!二null&&eIement!=nuII)

(

Node<E>p=;

while(p!=nulI)

(

if)

(

=element;

done=true;

1

p=；

)

)

returndone;

)

【習(xí)6.5]實(shí)驗(yàn)單鏈表的全部刪除操作。

在SinglyLinkedList單鏈表類中，增加刪除操作方法如下。

publicbooleanremoveAlI(Objectobj)〃將所有元素值為obj的結(jié)點(diǎn)刪除

(

if==nuII|Iobj=nulI)

-4-

returnfalse;

booleandone=faIse;

while!=nulI&&{

=〃頭刪除

done=true;

)

Node<E>front=,p=;

while(p!=nulI)

if)

(

=；〃刪除P結(jié)點(diǎn)

P=；

done=true;

I

else

(

front=p;

P=；

1

returndone;

)

【習(xí)6.6】折半查找的遞歸算法。

publicstaticintbinarySearch(int[]table,intvaIue)〃折半查找算法，數(shù)組元素

已按升序排列

{//若查找成功返回元素下標(biāo)，否則返回7

if(table!=nulI)

returnbinarySearch(tabIe,vaIue,0,;

return-1;

)

privatestaticintbinarySearch(int[]table,intvalue,intlow,inthigh)〃折

-5-

半查找，遞歸算法

(//lowvhigh指定查找范圍的下界和上界

if(Iow<=high)〃邊界有效

(

intmid=(low+high)/2;〃中間位置，當(dāng)前比較元素位置

H")；

if(tabIe[mid]==vaIue)

returnmid;〃查找成功

eIse

if(tabIe[mid]>vaIue)〃給定值小

returnbinarySearch(tabIe,value,low,mid-1);〃查找范圍縮

小到前半段

eIse

returnbinarySearch(tabIe,vaIue,mid+1,high);//查找范圍縮

小到后半段

)

return-1;

)

【習(xí)6.7]二叉排序樹(shù)查找的遞歸算法。

將二叉排序樹(shù)類BinarySortTree中的search(vaIue)方法替換為以下方法。

publicBinaryNode<E>searchNode(EvaIue)〃查找值為vaIue的結(jié)點(diǎn)

(〃若查找成功返回結(jié)點(diǎn)，否則返回null

if(vaIue==nuII||!(vaIueinstanceofComparable))

returnnull;

returnsearchNode(vaIue,root);

)

privateBinaryNode<E>searchNode(EvaIue,BinaryNode<E>p)〃查找值為value的結(jié)點(diǎn)，

遞歸算法

(

if(p!=nulI)

-6-

Comparablecmpobj=(Comparable)value;

if==0)〃若兩個(gè)對(duì)象相等，查找成功

returnp;

一)；

if<0)

returnsearchNode(vaIuer;〃在左子樹(shù)中查找

eIse

returnsearchNode(vaIue,;〃在右子樹(shù)中查找

)

returnnull;

)

[習(xí)6.8]二叉排序樹(shù)插入結(jié)點(diǎn)的非遞歸算法。

將二叉排序樹(shù)類BinarySortTree中的insert(vaIue)方法替換為以下方法。

publicbooleaninsertNode(EvaIue)〃插入結(jié)點(diǎn)，非遞歸

算法

(

if(value二二null||!(valueinstanceofComparabIe))

returnfalse;

if(root=nulI)

root二newBinaryNode<E>(vaIue);〃建立根結(jié)點(diǎn)

eIse

(

BinaryNode<E>p=,parent=nuII;

ComparabIecmpobj=(ComparabIe)vaIue;

while(p!=nulI)

(

parent=p:

if==0)

returnfalse;〃不插入重復(fù)關(guān)鍵字

if<0)

-7-

eIse

P=；

)

p=newBinaryNode<E>(vaIue);〃建立葉子結(jié)點(diǎn)p

if<0)

=p；//p作為parent的左孩子

eIse

=P；//p作為parent的右孩子

)

returntrue;

)

【習(xí)6.9】判斷一棵二叉樹(shù)是否為二叉排序樹(shù)。

將二叉樹(shù)類BinaryTree中增加以下方法。

publicbooleanisSorted()〃判斷一棵二叉樹(shù)是否為二叉

排序樹(shù)

(

returnisSorted;

)

publicbooleanisSorted(BinaryNode<E>p)

(

booleanyes=true;

if(p!=nulI)

(

if(!instanceofComparabIe))

returnfalse;

Comparablecmpobj=(Comparable);

if(=nulI||!=nulI&&&&

=nulI||!=nulI&&{

yes=isSorted;

if(yes)

yes=isSorted;

-8-

1

eIse

yes=false;

1

returnyes;

)

-9-

第7章排序

【習(xí)7.1】判斷一個(gè)數(shù)據(jù)序列是否為最小堆序列。

publicstaticbooleanisMinHeap(int[]table)//判斷一個(gè)數(shù)據(jù)序列是否

為最小堆

(

if(table==nulI)

returnfalse;

inti=2-1;〃最深一棵子樹(shù)的根結(jié)點(diǎn)

while(i>=0)

(

intj=2*i+1;//左孩子

if(j<

if(table[i]>table[j])

returnfalse;

eIse

if(j+1<&&table[i]>table[j+1])〃右孩子

returnfalse;

i一；

)

returntrue;

)

【習(xí)7.2】歸并兩條排序的單鏈表。

使用一趟歸并排序算法，將兩條排序的單鏈表合并成一條排序的單鏈表。算法描述如圖

所示。

-10-

frontP

(a)建立兩條排序的單鏈表，將list中結(jié)點(diǎn)依次插入到this單鏈表中