《数据结构Java版》习题解答.doc 37页

'第0章Java程序设计基础1【习0.1】实验0.1哥德巴赫猜想。1【习0.2】实验0.2杨辉三角形。1【习0.3】实验0.3金额的中文大写形式。1【习0.4】实验0.4下标和相等的数字方阵。1【习0.5】实验0.5找出一个二维数组的鞍点2【习0.6】实验0.6复数类。2【习0.7】实验0.8图形接口与实现图形接口的类2第1章绪论3【习1.1】实验1.1判断数组元素是否已按升序排序。3【习1.2】实验1.3用递归算法求两个整数的最大公因数。3第2章线性表5【习2.1】习2-5图2.19的数据结构声明。5【习2.2】习2-6如果在遍历单链表时，将p=p.next语句写成p.next=p，结果会怎样？5【习2.3】实验2.2由指定数组中的多个对象构造单链表。5【习2.4】实验2.2单链表的查找、包含、删除操作详见8.2.1。5【习2.5】实验2.2单链表的替换操作。6【习2.6】实验2.2首尾相接地连接两条单链表。6【习2.7】实验2.2复制单链表。6【习2.8】实验2.2单链表构造、复制、比较等操作的递归方法。7【习2.9】建立按升序排序的单链表（不带头结点）。8【习2.10】实验2.6带头结点的循环双链表类，实现线性表接口。10【习2.11】实验2.5建立按升序排序的循环双链表。14第3章栈和队列17【习3.1】习3-5栈和队列有何异同？17【习3.2】能否将栈声明为继承线性表，入栈方法是add(0,e)，出栈方法是remove(0)？为什么？17【习3.3】能否用一个线性表作为栈的成员变量，入栈方法是add(0,e)，出栈方法是remove(0)？为什么？17【习3.4】能否将队列声明为继承线性表，入队方法是add(e)，出队方法是remove(0)？为什么？17第4章串18【习4.1】实验4.6找出两个字符串中所有共同的字符。18【习4.2】习4-9(1)已知目标串为"abbaba"、模式串为"aba"，画出其KMP算法的匹配过程，并给出比较次数。18-III- 【习4.3】习4-9(2)已知target="ababaab"、pattern="aab"，求模式串的next数组，画出其KMP算法的匹配过程，并给出比较次数。18第5章数组和广义表20【习5.1】求一个矩阵的转置矩阵。20第6章树和二叉树21【习6.1】画出3个结点的各种形态的树和二叉树。21【习6.2】找出分别满足下面条件的所有二叉树。21【习6.3】输出叶子结点。21【习6.4】求一棵二叉树的叶子结点个数。22【习6.5】判断两棵二叉树是否相等。22【习6.6】复制一棵二叉树。23【习6.7】二叉树的替换操作。23【习6.8】后根次序遍历中序线索二叉树。24第7章图25第8章查找26【习8.1】实验8.1顺序表的查找、删除、替换、比较操作。26【习8.2】实验8.2单链表的全部替换操作。28【习8.3】实验8.2单链表的全部删除操作。28【习8.4】折半查找的递归算法。29【习8.5】二叉排序树查找的递归算法。29【习8.6】二叉排序树插入结点的非递归算法。30【习8.7】判断一棵二叉树是否为二叉排序树。31第9章排序32【习9.1】判断一个数据序列是否为最小堆序列。32【习9.2】归并两条排序的单链表。32【习9.3】说明二叉排序树与堆的差别。34图0.1下标和相等的数字方阵算法描述1图2.1p.next=p将改变结点间的链接关系5图4.1目标串"abbaba"和模式串"aba"的KMP算法模式匹配过程18图4.2目标串"ababaab"和模式串"aab"的KMP算法模式匹配过程19图6.13个结点树和二叉树的形态21图6.2单支二叉树21图9.2归并两条排序的单链表33-III- 表4.1模式串"aab"的next数组19第0章-III- 第0章Java程序设计基础【习0.1】实验0.1哥德巴赫猜想。【习0.2】实验0.2杨辉三角形。【习0.3】实验0.3金额的中文大写形式。【习0.4】实验0.4下标和相等的数字方阵。输出下列方阵（当n=4时）。1267或134103581325911491214681215101115167131416采用二维数组实现。二维数组中，每一条斜线上各元素下标和相等，如图0.1所示。图0.1下标和相等的数字方阵算法描述程序如下。publicclassUpmat{publicstaticvoidmain(Stringargs[]){intn=4;//阶数int[][]mat=newint[n][n];intk=1;//k是自然数，递增变化booleanup=true;//方向向上for(intsum=0;sum=0;i--)mat[i][sum-i]=k++;//k先赋值后自加elsefor(inti=0;i<=sum;i++)mat[i][sum-i]=k++;up=!up;//方向求反}for(intsum=n;sum<2*n-1;sum++)//右下三角{if(up)for(intj=sum-n+1;jsum-n;j--)mat[sum-j][j]=k++;up=!up;}for(inti=0;itable[i+1])returnfalse;returntrue;}publicstaticbooleanisSorted(Comparable[]table)//判断对象数组是否已按升序排序{//若已排序返回true，否则返回falseif(table==null)returnfalse;for(inti=0;i0)returnfalse;returntrue;}【习0.2】实验1.3用递归算法求两个整数的最大公因数。publicclassGcd{publicstaticintgcd(inta,intb)//返回a,b的最大公因数，递归方法{if(b==0)returna;if(a<0)returngcd(-a,b);if(b<0)returngcd(a,-b);returngcd(b,a%b);}publicstaticvoidmain(Stringargs[]){-34- inta=12,b=18,c=24;System.out.println("gcd("+a+","+b+","+c+")="+gcd(gcd(a,b),c));//获得3个整数最大公因数}}-34- 第0章线性表【习0.1】习2-5图2.19的数据结构声明。table数组元素为单链表，声明如下：SinglyLinkedListtable[]【习0.2】习2-6如果在遍历单链表时，将p=p.next语句写成p.next=p，结果会怎样？使p.next指向p结点自己，改变了结点间的链接关系，丢失后继结点，如图2.1所示。图0.1p.next=p将改变结点间的链接关系【习0.3】实验2.2由指定数组中的多个对象构造单链表。在SinglyLinkedList单链表类中，增加构造方法如下。publicSinglyLinkedList(E[]element)//由指定数组中的多个对象构造单链表{this.head=null;if(element!=null&&element.length>0){this.head=newNode(element[0]);Noderear=this.head;inti=1;while(isearch(Eelement,Nodestart)//从单链表结点start开始顺序查找指定对象publicNodesearch(Eelement)//若查找到指定对象，则返回结点，否则返回nullpublicbooleancontain(Eelement)//以查找结果判断单链表是否包含指定对象-34- publicbooleanremove(Eelement)//移去首次出现的指定对象【习0.1】实验2.2单链表的替换操作。在SinglyLinkedList单链表类中，增加替换操作方法如下。publicbooleanreplace(Objectobj,Eelement)//将元素值为obj的结点值替换为element{//若替换成功返回true，否则返回false，O(n)if(obj==null||element==null)returnfalse;Nodep=this.head;while(p!=null){if(obj.equals(p.data)){p.data=element;returntrue;}p=p.next;}returnfalse;}【习0.2】实验2.2首尾相接地连接两条单链表。在SinglyLinkedList单链表类中，增加替换操作方法如下。publicvoidconcat(SinglyLinkedListlist)//将指定单链表list链接在当前单链表之后{if(this.head==null)this.head=list.head;else{Nodep=this.head;while(p.next!=null)p=p.next;p.next=list.head;}}【习0.3】实验2.2复制单链表。在SinglyLinkedList单链表类中，增加构造方法如下。publicSinglyLinkedList(SinglyLinkedListlist)//以单链表list构造新的单链表{//复制单链表-34- this.head=null;if(list!=null&&list.head!=null){this.head=newNode(list.head.data);Nodep=list.head.next;Noderear=this.head;while(p!=null){rear.next=newNode(p.data);rear=rear.next;p=p.next;}}}【习0.1】实验2.2单链表构造、复制、比较等操作的递归方法。由指定数组中的多个对象构造单链表的操作也可设计为以下的递归方法：publicSinglyLinkedList(E[]element)//由指定数组中的多个对象构造单链表{this.head=null;if(element!=null)this.head=create(element,0);}privateNodecreate(E[]element,inti)//由指定数组构造单链表，递归方法{Nodep=null;if(ilist)//以单链表list构造新的单链表{this.head=copy(list.head);}privateNodecopy(Nodep)//复制单链表，递归方法-34- {Nodeq=null;if(p!=null){q=newNode(p.data);q.next=copy(p.next);}returnq;}比较两条单链表是否相等的操作也可设计为以下的递归方法：publicbooleanequals(Objectobj)//比较两条单链表是否相等{if(obj==this)returntrue;if(objinstanceofSinglyLinkedList){SinglyLinkedListlist=(SinglyLinkedList)obj;returnequals(this.head,list.head);}returnfalse;}privatebooleanequals(Nodep,Nodeq)//比较两条单链表是否相等，递归方法{if(p==null&&q==null)returntrue;if(p!=null&&q!=null)returnp.data.equals(q.data)&&equals(p.next,q.next);returnfalse;}【习0.1】建立按升序排序的单链表（不带头结点）。采用直接插入排序算法将一个结点插入到已排序的单链表中。importdataStructure.linearList.Node;importdataStructure.linearList.SinglyLinkedList;//不带头结点的单链表类publicclassSortedSinglyLinkedListextendsSinglyLinkedList{publicSortedSinglyLinkedList(){-34- super();}publicbooleanadd(Eelement)//根据指定对象的大小插入在合适位置{if(element==null||!(elementinstanceofComparable))returnfalse;//不能插入null或非Comparable对象Comparablecmp=(Comparable)element;if(this.head==null||cmp.compareTo(this.head.data)<=0)this.head=newNode(element,this.head);//头插入else{Nodefront=null,p=this.head;while(p!=null&&cmp.compareTo(p.data)>0){front=p;//front是p的前驱结点p=p.next;}front.next=newNode(element,p);//中间/尾插入}returntrue;}publicstaticvoidmain(Stringargs[]){SortedSinglyLinkedListlist=newSortedSinglyLinkedList();intn=10;System.out.print("insert：");for(inti=0;iimplementsLList//带头结点的循环双链表类{protectedDLinkNodehead;//头指针publicCHDoublyLinkedList()//构造空链表{this.head=newDLinkNode();//创建头结点，值为nullthis.head.prev=head;this.head.next=head;}publicbooleanisEmpty()//判断双链表是否为空{returnhead.next==head;}//以下算法同循环单链表，与单链表的差别在于，循环条件不同publicintlength()//返回双链表长度{inti=0;DLinkNodep=this.head.next;//此句与单链表不同while(p!=head)//循环条件与单链表不同{i++;p=p.next;}returni;-34- }publicEget(intindex)//返回序号为index的对象{if(index>=0){intj=0;DLinkNodep=this.head.next;while(p!=head&&j=0&&element!=null){intj=0;DLinkNodep=this.head.next;while(p!=head&&jp=this.head.next;while(p!=head){str+=p.data.toString();p=p.next;if(p!=head)str+=",";}returnstr+")";}//双链表的插入、删除算法与单链表不同publicbooleanadd(intindex,Eelement)//插入element对象，插入后对象序号为index{//若操作成功返回true，O(n)if(element==null)returnfalse;//不能添加空对象（null）intj=0;DLinkNodefront=this.head;while(front.next!=head&&jq=newDLinkNode(element,front,front.next);//插入在front结点之后front.next.prev=q;front.next=q;returntrue;}publicbooleanadd(Eelement)//在单链表最后添加对象，O(1){if(element==null)returnfalse;//不能添加空对象（null）-34- DLinkNodeq=newDLinkNode(element,head.prev,head);head.prev.next=q;//插入在头结点之前，相当于尾插入head.prev=q;returntrue;}publicEremove(intindex)//移除指定位置的对象，O(n){//返回被移除的原对象，指定位置序号错误时返回nullEold=null;intj=0;DLinkNodep=this.head.next;while(p!=head&&jlist=newCHDoublyLinkedList();System.out.println("删除第"+i+"个结点"+list.remove(0));System.out.println(list.toString());-34- for(i=5;i>=0;i--)list.add(0,newString((char)("A"+i)+""));for(i=0;i<6;i++)list.add(newString((char)("A"+i)+""));//list.add(i,newString((char)("A"+i)+""));System.out.println(list.toString());System.out.println("删除第"+i+"个结点"+list.remove(i));System.out.println(list.toString());}}程序运行结果如下：删除第0个结点null()(A,B,C,D,E,F,A,B,C,D,E,F)删除第6个结点A(A,B,C,D,E,F,B,C,D,E,F)【习0.1】实验2.5建立按升序排序的循环双链表。packagedataStructure.linearList;importdataStructure.linearList.DLinkNode;importdataStructure.linearList.CHDoublyLinkedList;//循环双链表类publicclassSortedCHDLinkedListextendsCHDoublyLinkedList{//按升序排序的循环双链表类publicSortedCHDLinkedList(){super();}publicbooleanadd(Eelement)//根据指定对象的大小插入在合适位置{//若操作成功返回true，O(n)if(element==null||!(elementinstanceofComparable))returnfalse;//不能插入null或非Comparable对象Comparablecmp=(Comparable)element;if(this.head.prev!=head&&cmp.compareTo(this.head.prev.data)>0){//非空双链表，插入在最后，O(1)DLinkNodeq=newDLinkNode(element,head.prev,head);head.prev.next=q;//插入在头结点之前，相当于尾插入-34- head.prev=q;returntrue;}DLinkNodep=this.head.next;while(p!=head&&cmp.compareTo(p.data)>0)//寻找插入位置p=p.next;DLinkNodeq=newDLinkNode(element,p.prev,p);//插入在p结点之前p.prev.next=q;p.prev=q;returntrue;}publicbooleanremove(Eelement)//删除指定对象{//若操作成功返回true，O(n)if(element==null||!(elementinstanceofComparable))returnfalse;Comparablecmp=(Comparable)element;DLinkNodep=this.head.next;while(p!=head&&cmp.compareTo(p.data)>0)//定位到待删除的结点p=p.next;if(p!=head){p.prev.next=p.next;//删除p结点自己p.next.prev=p.prev;returntrue;}returnfalse;//未找到指定结点，删除不成功}publicstaticvoidmain(Stringargs[]){SortedCHDLinkedListlist=newSortedCHDLinkedList();intn=10;System.out.print("insert：");for(inti=0;ip)//先根次序遍历，输出叶子结点，3种遍历次序结果一样{if(p!=null){if(p.isLeaf())System.out.print(p.data+"");-34- leaf(p.left);leaf(p.right);}}【习0.1】求一棵二叉树的叶子结点个数。在BinaryTree类中增加以下方法。publicintcountLeaf()//求一棵二叉树中所有叶子结点个数{returncountLeaf(root);}publicintcountLeaf(BinaryNodep)//求以p结点为根的子树的叶子结点个数{if(p==null)return0;if(p.isLeaf())return1;returncountLeaf(p.left)+countLeaf(p.right);}【习0.2】判断两棵二叉树是否相等。publicbooleanequals(Objectobj)//比较两棵二叉树是否相等，BinaryTree类中方法{if(obj==this)returntrue;if(objinstanceofBinaryTree){BinaryTreebitree=(BinaryTree)obj;returnequals(this.root,bitree.root);}returnfalse;}privatebooleanequals(BinaryNodep,BinaryNodeq)//判断两棵子树是否相等，递归方法{if(p==null&&q==null)returntrue;if(p!=null&&q!=null)return(p.data.equals(q.data))&&equals(p.left,q.left)&&equals(p.right,q.right);returnfalse;}【习0.3】复制一棵二叉树。-34- 在BinaryTree类中增加以下构造方法，以已知的bitree构造二叉树构造一棵二叉树。publicBinaryTree(BinaryTreebitree)//以已知的bitree构造二叉树{this.root=copy(bitree.root);}publicBinaryNodecopy(BinaryNodep)//复制以p根的子二叉树{BinaryNodeq=null;if(p!=null){q=newBinaryNode(p.data);q.left=copy(p.left);//复制左子树q.right=copy(p.right);//复制右子树}returnq;//返回建立子树的根结点}【习0.1】二叉树的替换操作。publicbooleanreplace(Eold,Evalue)//将首次出现的值为old结点值替换为value{BinaryNodefind=search(old);//查找值为old的结点if(find!=null)find.data=value;//替换结点元素值returnfind!=null;}publicvoidreplaceAll(Eold,Evalue)//将值为old的结点全部替换为value{replaceAll(root,old,value);}publicvoidreplaceAll(BinaryNodep,Eold,Evalue)//在以p为根的子树中实现全部替换{if(p!=null){if(p.data.equals(old))p.data=value;replaceAll(p.left,old,value);replaceAll(p.right,old,value);}}-34- 【习0.1】后根次序遍历中序线索二叉树。在中序线索二叉树类ThreadBinaryTree中，增加以下方法，实现后根次序遍历。publicThreadBinaryNodepostPrevious(ThreadBinaryNodep)//返回p在后根次序下的前驱{if(p.rtag==0)//若右子树非空p=p.right;//右孩子是p的前驱结点else//否则，前驱是左兄弟或某个中序祖先的左孩子{while(p.ltag==1&&p.left!=null)p=p.left;//寻找其某个中序祖先p=p.left;//左孩子是p的前驱结点}returnp;}publicvoidpostOrder_previous()//后根次序遍历中序线索二叉树{ThreadBinaryNodep=root;if(p!=null){System.out.print("后根次序遍历（反序）：");do{System.out.print(p.data+"");p=postPrevious(p);//返回p在后根次序下的前驱结点}while(p!=null);System.out.println();}}-34- 第0章图-34- 第0章查找【习0.1】实验8.1顺序表的查找、删除、替换、比较操作。程序见顺序表类SeqList.java。publicintlastIndexOf(Eelement)//返回obj对象最后出现位置，若未找到返回-1{if(obj!=null)for(inti=this.n-1;i>=0;i--)if(obj.equals(this.table[i]))returni;return-1;}publicbooleanremove(Eelement)//移去首次出现的obj对象，若操作成功返回true{if(this.n!=0&&obj!=null)returnthis.remove(this.indexOf(obj))!=null;returnfalse;}publicbooleanremoveAll(Eelement)//移去线性表中所有obj对象{booleandone=false;if(this.n!=0&&obj!=null){inti=0;while(ilist=(SeqList)obj;for(inti=0;ip=this.head;while(p!=null){if(obj.equals(p.data)){p.data=element;done=true;}p=p.next;}}returndone;}【习0.2】实验8.2单链表的全部删除操作。在SinglyLinkedList单链表类中，增加删除操作方法如下。publicbooleanremoveAll(Objectobj)//将所有元素值为obj的结点删除{if(this.head==null||obj==null)returnfalse;booleandone=false;while(this.head!=null&&obj.equals(this.head.data)){this.head=this.head.next;//头删除done=true;}Nodefront=this.head,p=front.next;while(p!=null)if(obj.equals(p.data)){-34- front.next=p.next;//删除p结点p=front.next;done=true;}else{front=p;p=p.next;}returndone;}【习0.1】折半查找的递归算法。publicstaticintbinarySearch(int[]table,intvalue)//折半查找算法，数组元素已按升序排列{//若查找成功返回元素下标，否则返回-1if(table!=null)returnbinarySearch(table,value,0,table.length-1);return-1;}privatestaticintbinarySearch(int[]table,intvalue,intlow,inthigh)//折半查找，递归算法{//low、high指定查找范围的下界和上界if(low<=high)//边界有效{intmid=(low+high)/2;//中间位置，当前比较元素位置System.out.print(table[mid]+"?");if(table[mid]==value)returnmid;//查找成功elseif(table[mid]>value)//给定值小returnbinarySearch(table,value,low,mid-1);//查找范围缩小到前半段elsereturnbinarySearch(table,value,mid+1,high);//查找范围缩小到后半段}return-1;}【习0.2】二叉排序树查找的递归算法。将二叉排序树类BinarySortTree中的search(value)方法替换为以下方法。publicBinaryNodesearchNode(Evalue)//查找值为value的结点{//若查找成功返回结点，否则返回null-34- if(value==null||!(valueinstanceofComparable))returnnull;returnsearchNode(value,root);}privateBinaryNodesearchNode(Evalue,BinaryNodep)//查找值为value的结点，递归算法{if(p!=null){Comparablecmpobj=(Comparable)value;if(cmpobj.compareTo(p.data)==0)//若两个对象相等，查找成功returnp;System.out.print(p.data+"?");if(cmpobj.compareTo(p.data)<0)returnsearchNode(value,p.left);//在左子树中查找elsereturnsearchNode(value,p.right);//在右子树中查找}returnnull;}【习0.1】二叉排序树插入结点的非递归算法。将二叉排序树类BinarySortTree中的insert(value)方法替换为以下方法。publicbooleaninsertNode(Evalue)//插入结点，非递归算法{if(value==null||!(valueinstanceofComparable))returnfalse;if(root==null)root=newBinaryNode(value);//建立根结点else{BinaryNodep=this.root,parent=null;Comparablecmpobj=(Comparable)value;while(p!=null){parent=p;if(cmpobj.compareTo(p.data)==0)returnfalse;//不插入重复关键字if(cmpobj.compareTo(p.data)<0)p=p.left;else-34- p=p.right;}p=newBinaryNode(value);//建立叶子结点pif(cmpobj.compareTo(parent.data)<0)parent.left=p;//p作为parent的左孩子elseparent.right=p;//p作为parent的右孩子}returntrue;}【习0.1】判断一棵二叉树是否为二叉排序树。将二叉树类BinaryTree中增加以下方法。publicbooleanisSorted()//判断一棵二叉树是否为二叉排序树{returnisSorted(this.root);}publicbooleanisSorted(BinaryNodep){booleanyes=true;if(p!=null){if(!(p.datainstanceofComparable))returnfalse;Comparablecmpobj=(Comparable)p.data;if((p.left==null||p.left!=null&&cmpobj.compareTo(p.left.data)>0)&&(p.right==null||p.right!=null&&cmpobj.compareTo(p.right.data)<0)){yes=isSorted(p.left);if(yes)yes=isSorted(p.right);}elseyes=false;}returnyes;}-34- 第0章排序【习0.1】判断一个数据序列是否为最小堆序列。publicstaticbooleanisMinHeap(int[]table)//判断一个数据序列是否为最小堆{if(table==null)returnfalse;inti=table.length/2-1;//最深一棵子树的根结点while(i>=0){intj=2*i+1;//左孩子if(jtable[j])returnfalse;elseif(j+1table[j+1])//右孩子returnfalse;i--;}returntrue;}【习0.2】归并两条排序的单链表。使用一趟归并排序算法，将两条排序的单链表合并成一条排序的单链表。算法描述如图9.2所示。-34- 图0.1归并两条排序的单链表在带头结点的单链表类SortedHSLinkedList中，增加merge()方法如下：publicvoidmerge(SortedHSLinkedListlist)//归并两条排序的单链表{if(list==null||list.head==null)return;if(this.head==null){this.head=list.head;return;}Nodefront=this.head,p=front.next;//front是p的前驱，p指向this单链表的第一个结点Nodeq=list.head.next;//q指向list单链表的第一个结点while(p!=null&&q!=null){if(((Comparable)p.data).compareTo((Comparable)q.data)<0)//比较两个链表当前结点值{front=p;p=p.next;}else{//将q结点插入到front结点之后front.next=q;q=q.next;front=front.next;-34- front.next=p;}}if(q!=null)//list链表中剩余结点并入当前链表尾{front.next=q;while(q.next!=null)q=q.next;this.rear=q;}this.n+=list.n;}【习0.1】说明二叉排序树与堆的差别。二叉排序树与堆是不同的。二叉排序树是二叉树结构，通常采用链式存储结构，父母结点的关键字值比左孩子结点值大，而比右孩子结点值小。而堆序列是顺序存储结构的线性表，只看成是完全二叉树结点的层次序列；堆序列的性质强调对应完全二叉树中父母结点值比子女结点值小，而不考虑左右孩子值间的大小。-34-'