《數據結構(Java版)(第2版)》習題解答_第1頁
《數據結構(Java版)(第2版)》習題解答_第2頁
《數據結構(Java版)(第2版)》習題解答_第3頁
《數據結構(Java版)(第2版)》習題解答_第4頁
《數據結構(Java版)(第2版)》習題解答_第5頁
已閱讀5頁,還剩9頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領

文檔簡介

數據結構(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單鏈表中

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容,請與我們聯系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論