




版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
數(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)金額的中文大寫形式。..........................................1
【習(xí)0.4]實(shí)驗(yàn)下標(biāo)和相等的數(shù)字方陣。........................................I
第6章樹(shù)和二叉樹(shù).................................................................3
【習(xí)6.1】畫出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)金額的中文大寫形式。
【習(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】畫出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單鏈表中
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025秦皇島職業(yè)技術(shù)學(xué)院?jiǎn)握小墩Z(yǔ)文》考前沖刺練習(xí)題及完整答案詳解(奪冠)
- 四年級(jí)數(shù)學(xué)(上)計(jì)算題專項(xiàng)練習(xí)及答案
- 2024-2025學(xué)年度四川工程職業(yè)技術(shù)學(xué)院?jiǎn)握小段锢怼烦?键c(diǎn)試卷及答案詳解【有一套】
- 2024年福建生物工程職業(yè)技術(shù)學(xué)院?jiǎn)握小段锢怼吠P(guān)題庫(kù)及參考答案詳解(基礎(chǔ)題)
- 福建省2025年設(shè)計(jì)前期場(chǎng)地與建筑設(shè)計(jì):設(shè)備布置要求與方式考試試題
- 義務(wù)教育課程方案和課程標(biāo)準(zhǔn)心得體會(huì)2026版
- 2024年長(zhǎng)治幼兒師范高等??茖W(xué)校輔導(dǎo)員考試真題
- 2024年濟(jì)寧梁山運(yùn)河城市更新有限公司招聘考試真題
- 2024年貴州師范大學(xué)輔導(dǎo)員考試真題
- 2024年臨汾隰縣開(kāi)發(fā)公益性崗位招用就業(yè)困難人員筆試真題
- 臨床急診影像學(xué)檢查與診斷
- 5S車間管理培訓(xùn)
- 希爾頓酒店設(shè)計(jì)和施工標(biāo)準(zhǔn)第12節(jié)套房
- 鋁電解電容器
- GB/T 13912-2020金屬覆蓋層鋼鐵制件熱浸鍍鋅層技術(shù)要求及試驗(yàn)方法
- 結(jié)構(gòu)設(shè)計(jì)總說(shuō)明(帶圖完整版)分解
- 第二外語(yǔ)(日語(yǔ))試卷
- 食品營(yíng)養(yǎng)標(biāo)簽的解讀課件
- 二手新能源汽車充電安全承諾書(shū)
- 品質(zhì)異常8D報(bào)告 (錯(cuò)誤模板及錯(cuò)誤說(shuō)明)指導(dǎo)培訓(xùn)
- 貴陽(yáng)市建設(shè)工程消防整改驗(yàn)收申請(qǐng)表
評(píng)論
0/150
提交評(píng)論