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

v1.0可編輯可修改v1.0可編輯可修改PAGEPAGEII-PAGEII-v1.0可編輯可修改PAGE數(shù)據(jù)結(jié)（Java版）（第2版）習(xí)題解答葉核亞編著目錄TOC\h\z\t"標(biāo)題1,1,例題,4"第0章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ù)字方陣。 1第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ù)與堆的差別。 12TOC\h\z\t"圖題,4"圖0.1下標(biāo)和相等的數(shù)字方陣算法描述 1圖6.13個(gè)結(jié)點(diǎn)樹(shù)和二叉樹(shù)的形態(tài) 3圖6.2單支二叉樹(shù) 3圖7.2歸并兩條排序的單鏈表 11TOC\h\z\t"表題,4"表0.1intn=4; ength;j++)8.2.18.2.1 2-PAGE12-Java程序設(shè)計(jì)基礎(chǔ)實(shí)驗(yàn)哥德巴赫猜想。實(shí)驗(yàn)楊輝三角形。實(shí)驗(yàn)金額的中文大寫形式。實(shí)驗(yàn)下標(biāo)和相等的數(shù)字方陣。輸出下列方陣（當(dāng)n=4時(shí)）。1 2 6 7或 1 3 4 103 5 8 13 2 5 9 114 9 12 14 6 8 12 1510 11 15 16 7 13 14 16采用二維數(shù)組實(shí)現(xiàn)。二維數(shù)組中，每一條斜線上各元素下標(biāo)和相等，如圖所示。下標(biāo)和相等的數(shù)字方陣算法描述程序如下。publicclassUpmat{publicstaticvoidmain(Stringargs[]){intn=4; ength;j++) 8.2.18.2.1ength,;for(inti=0;i<i++)for(intj=0;j<[i].length;j++)[j][i]=[i][j];returntrans;}樹(shù)和二叉樹(shù)畫(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)，如圖所示。3個(gè)結(jié)點(diǎn)樹(shù)和二叉樹(shù)的形態(tài)找出分別滿足下面條件的所有二叉樹(shù)。先根遍歷序列和中根遍歷序列相同：右單支二叉樹(shù)，如圖（a）所示。中根遍歷序列和后根遍歷序列相同：左單支二叉樹(shù)，如圖（b）所示。先根遍歷序列和后根遍歷序列相同：空樹(shù)，只有一個(gè)根結(jié)點(diǎn)的二叉樹(shù)。單支二叉樹(shù)輸出葉子結(jié)點(diǎn)。在BinaryTree類中增加以下方法。publicvoidleaf() quals(i))))returnfalse;returntrue;}returnfalse;}實(shí)驗(yàn)單鏈表的全部替換操作。在SinglyLinkedList單鏈表類中，增加替換操作方法如下。publicbooleanreplace(Objectobj,Eelement) //詳見(jiàn)實(shí)驗(yàn)publicbooleanreplaceAll(Objectobj,Eelement)//將所有元素值為obj的結(jié)點(diǎn)值替換為element{ //若替換成功返回true，否則返回falsebooleandone=false;if(obj!=null&&element!=null){Node<E>p=;while(p!=null){if){=element;done=true;}p=;}}returndone;}實(shí)驗(yàn)單鏈表的全部刪除操作。在SinglyLinkedList單鏈表類中，增加刪除操作方法如下。publicbooleanremoveAll(Objectobj) //將所有元素值為obj的結(jié)點(diǎn)刪除{if==null||obj==null)returnfalse;booleandone=false;while!=null&&{= //頭刪除done=true;}Node<E>front=,p=;while(p!=null)if){=; //刪除p結(jié)點(diǎn)p=;done=true;}else{front=p;p=;}returndone;}折半查找的遞歸算法。publicstaticintbinarySearch(int[]table,intvalue) //折半查找算法，數(shù)組元素已按升序排列{ //若查找成功返回元素下標(biāo)，否則返回-1if(table!=null)returnbinarySearch(table,value,0,;return-1;}privatestaticintbinarySearch(int[]table,intvalue,intlow,inthigh) //折半查找，遞歸算法{ //low、high指定查找范圍的下界和上界if(low<=high) //邊界有效{intmid=(low+high)/2; //中間位置，當(dāng)前比較元素位置"");if(table[mid]==value)returnmid; //查找成功elseif(table[mid]>value) //給定值小returnbinarySearch(table,value,low,mid-1); //查找范圍縮小到前半段elsereturnbinarySearch(table,value,mid+1,high); //查找范圍縮小到后半段}return-1;}二叉排序樹(shù)查找的遞歸算法。將二叉排序樹(shù)類BinarySortTree中的search(value)方法替換為以下方法。publicBinaryNode<E>searchNode(Evalue) //查找值為value的結(jié)點(diǎn){ //若查找成功返回結(jié)點(diǎn)，否則返回nullif(value==null||!(valueinstanceofComparable))returnnull;returnsearchNode(value,root);}privateBinaryNode<E>searchNode(Evalue,BinaryNode<E>p)//查找值為value的結(jié)點(diǎn)，遞歸算法{if(p!=null){Comparablecmpobj=(Comparable)value;if==0) //若兩個(gè)對(duì)象相等，查找成功returnp;"");if<0)returnsearchNode(value,; //在左子樹(shù)中查找elsereturnsearchNode(value,; //在右子樹(shù)中查找}returnnull;}二叉排序樹(shù)插入結(jié)點(diǎn)的非遞歸算法。將二叉排序樹(shù)類BinarySortTree中的insert(value)方法替換為以下方法。publicbooleaninsertNode(Evalue) //插入結(jié)點(diǎn)，非遞歸算法{if(value==null||!(valueinstanceofComparable))returnfalse;if(root==null)root=newBinaryNode<E>(value); //建立根結(jié)點(diǎn)else{BinaryNode<E>p=,parent=null;Comparablecmpobj=(Comparable)value;while(p!=null){parent=p;if==0)returnfalse; //不插入重復(fù)關(guān)鍵字if<0)p=;elsep=;}p=newBinaryNode<E>(value); //建立葉子結(jié)點(diǎn)pif<0)=p; //p作為parent的左孩子else=p; //p作為parent的右孩子}returntrue;}判斷一棵二叉樹(shù)是否為二叉排序樹(shù)。將二叉樹(shù)類BinaryTree中增加以下方法。publicbooleanisSorted() //判斷一棵二叉樹(shù)是否為二叉排序樹(shù){returnisSorted;}publicbooleanisSorted(BinaryNode<E>p){booleanyes=true;if(p!=null){if(!instanceofComparable))returnfalse;Comparablecmpobj=(Comparable);if(==null||!=null&&&&==null||!=null&&{yes=isSorted;if(yes)yes=isSorted;}elseyes=false;}returnyes;}排序判斷一個(gè)數(shù)據(jù)序列是否為最小堆序列。publicstaticbooleanisMinHeap(int[]table) //判斷一個(gè)數(shù)據(jù)序列是否為最小堆{if(table==null)returnfalse;inti=2-1; //最深一棵子樹(shù)的根結(jié)點(diǎn)while(i>=0){intj=2*i+1; //左孩子if(j<if(table[i]>table[j])returnfalse;elseif(j+1<&&table[i]>table[j+1]) //右孩子returnfalse;i--;}returntrue;}歸并兩條排序的單鏈表。使用一趟歸并排序算法，將兩條排序的單鏈表合并成一條排序的單鏈表。算法描述如圖所示。歸并兩條排序的單鏈表在帶頭結(jié)點(diǎn)的單鏈表類SortedHSLinkedList中，增加merge()方法如下：publicvoidmerge(SortedHSLinkedList<E