《數據結構(Java版)(第2版)》習題解答

數據結構（Java版）（第2版）

習題解答

葉核亞編著

目錄

第。章Java程序設計基礎..........................................................1

【習0.1】實驗哥德巴赫猜想。................................................1

【習0.2］實驗楊輝三角形。..................................................1

【習0.3］實驗金額的中文大寫形式。..........................................1

【習0.4］實驗下標和相等的數字方陣。........................................I

第6章樹和二叉樹.................................................................3

【習6.1】畫出3個結點的各種形態(tài)的樹和二叉樹。.................................3

【習6.2］找出分別滿足下面條件的所有二叉樹。..................................3

【習6.3】輸出葉子結點。.......................................................3

【習6.4］實驗單鏈表的全部替換操作。........................................4

【習6.5］實驗單鏈表的全部刪除操作。.........................................4

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

【習6.7】二叉排序樹查找的遞歸算法。...........................................6

【習6.8】二叉排序樹插入結點的非遞歸算法。.....................................7

【習6.9】判斷一棵二叉樹是否為二叉排序樹。.....................................8

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

【習7.1】判斷一個數據序列是否為最小堆序列。..................................10

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

【習7.3】說明二叉排序樹與堆的差別。..........................................12

圖0.1下標和相等的數字方陣算法描述.............................................I

圖6.13個結點樹和二叉樹的形態(tài)..................................................3

圖6.2單支二叉樹...............................................................3

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

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

2

pOPlp2P（）PlP2

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

第0章Java程序設計基礎

【習0.1】實驗哥德巴赫猜想。

【習02]實驗楊輝三角形。

【習。3】實驗金額的中文大寫形式。

【習0.4】實驗下標和相等的數字方陣。

輸出下列方陣（當n=4時）。

1267或3410

3581325911

491214681215

101115167131416

采用二維數組實現。二維數組中，每一條斜線上各元素下標和相等，如圖所示。

程序如下。

publicclassUpmat

pubIicstaticvoidmain(Stringargs[])

-1

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

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

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章樹和二叉樹

【習6.1】畫出3個結點的各種形態(tài)的樹和二叉樹。

3個結點的樹有2種形態(tài)，3個結點的二叉樹有5種形態(tài)，如圖所示。

(a)3個結點的樹具有2種基本形態(tài)(b)3個結點的二又朝具有5種基本形態(tài)

圖6.13個結點樹和二叉樹的形態(tài)

【習&2】找出分別滿足下面條件的所有二叉樹。

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

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

③先根遍歷序列和后根遍歷序列相同：空樹，只有一個根結點的二叉樹。

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

圖6.2單支二叉樹

【習6.3】輸出葉子結點。

在BinaryTree類中增加以下方法。

publicvoidIeaf()quals(i))))

returnfalse;

returntrue;

-3-

)

returnfalse;

)

【習6.4]實驗單鏈表的全部替換操作。

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

publicbooleanreplace(Objectobj,EeIement)//詳見實驗

pubIicbooleanreplaceAlI(Objectobj,Eelement)〃將所有元素值為obj的結點值替

換為eIement

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

booleandone二千aIse;

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

(

Node<E>p=;

while(p!=nulI)

(

if)

(

=element;

done=true;

1

p=；

)

)

returndone;

)

【習6.5]實驗單鏈表的全部刪除操作。

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

publicbooleanremoveAlI(Objectobj)〃將所有元素值為obj的結點刪除

(

if==nuII|Iobj=nulI)

-4-

returnfalse;

booleandone=faIse;

while!=nulI&&{

=〃頭刪除

done=true;

)

Node<E>front=,p=;

while(p!=nulI)

if)

(

=；〃刪除P結點

P=；

done=true;

I

else

(

front=p;

P=；

1

returndone;

)

【習6.6】折半查找的遞歸算法。

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

已按升序排列

{//若查找成功返回元素下標，否則返回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;〃中間位置，當前比較元素位置

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;

)

【習6.7]二叉排序樹查找的遞歸算法。

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

publicBinaryNode<E>searchNode(EvaIue)〃查找值為vaIue的結點

(〃若查找成功返回結點，否則返回null

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

returnnull;

returnsearchNode(vaIue,root);

)

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

遞歸算法

(

if(p!=nulI)

-6-

Comparablecmpobj=(Comparable)value;

if==0)〃若兩個對象相等，查找成功

returnp;

一)；

if<0)

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

eIse

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

)

returnnull;

)

[習6.8]二叉排序樹插入結點的非遞歸算法。

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

publicbooleaninsertNode(EvaIue)〃插入結點，非遞歸

算法

(

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

returnfalse;

if(root=nulI)

root二newBinaryNode<E>(vaIue);〃建立根結點

eIse

(

BinaryNode<E>p=,parent=nuII;

ComparabIecmpobj=(ComparabIe)vaIue;

while(p!=nulI)

(

parent=p:

if==0)

returnfalse;〃不插入重復關鍵字

if<0)

-7-

eIse

P=；

)

p=newBinaryNode<E>(vaIue);〃建立葉子結點p

if<0)

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

eIse

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

)

returntrue;

)

【習6.9】判斷一棵二叉樹是否為二叉排序樹。

將二叉樹類BinaryTree中增加以下方法。

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

排序樹

(

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章排序

【習7.1】判斷一個數據序列是否為最小堆序列。

publicstaticbooleanisMinHeap(int[]table)//判斷一個數據序列是否

為最小堆

(

if(table==nulI)

returnfalse;

inti=2-1;〃最深一棵子樹的根結點

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;

)

【習7.2】歸并兩條排序的單鏈表。

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

所示。

-10-

frontP

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