数据结构与算法分析 第13章 答案 Larry Nyhoff 清华大.pdf

Chapter 13 226 Chapter 13:SortingExercises 13.11.After first pass,elements of x are:10 50 70 30 40 60.After second pass:10 30 70 50 40 60.2.(a)60 70 50 40 20 1070 60 50 40 20 10 (b)3,since no interchanges occur on the third pass.(c)Worst case is when elements are in reverse order.3.(a)After x 4 is positioned:20 30 40 60 10 50After x 5 is positioned:10 20 30 40 60 50(b)If the list is in increasing order;no interchanges are required.4.(a)After one pass:10 50 60 30 40 70After two passes:10 30 40 50 60 70(b)Function to perform double-ended selection sort:template void doubleEndedSelectionSort(ElementType x,int n)/*-Sort a list into ascending order using double-ended selection sort.Precondition:array x contains n elements.Postcondition:The n elements of array have been sorted into ascending order.-*/int minValue,maxValue,minPos,maxPos;for(int i=1;i=n/2;i+)minValue=maxValue=xi;minPos=maxPos=i;/find min and max values among xi,.,xnChapter 13 227 for(int j=i+1;j=n-i+1;j+)if(xj maxValue)maxValue=xj;maxPos=j;/make sure that positioning min value doesnt overwrite max if(i=maxPos)maxPos=minPos;xminPos=xi;xi=minValue;xmaxPos=xn-i+1;xn-i+1=maxValue;(c)Computing time is O(n2).5.(a)After step 1 executes,xis are:30509010607020100 8040There are 5 passes for step 2.xis are:After first pass:105040206070309080100After second pass:102040306070508090100After third pass:102030406070508090100After fourth pass:102030405060708090100After fifth pass:102030405060708090100(b)The functions below implement Min-Max Sort.template void swap(ElementType x,int a,int b)int temp=xa;xa=xb;xb=temp;Chapter 13 228 template void minMaxSort(ElementType x,int n)/Create rainbow pattern for(int i=1;i xn+1-i)swap(x,i,n+1-i);/Find smallest in first half of list for(int i=1;i=n/2;i+)int minPos=i;int minValue=xi;for(int j=i+1;j=n/2;j+)if(xj minValue)minPos=j;minValue=xj;/Swap smallest with first element xminPos=xi;xi=minValue;/Find largest in last half of list int maxPos=n+1-i;int maxValue=xmaxPos;for(int j=n/2+1;j maxValue)maxPos=j;maxValue=xj;/Swap largest with last element xmaxPos=xn+1-i;xn+1-i=maxValue;/Recreate rainbow pattern if(xminPos xn+1-minPos)swap(x,minPos,n+1-minPos);if(xmaxPos xn+1-maxPos)swap(x,maxPos,n+1-maxPos);Chapter 13 229 6./Recursive helper function for recSelectionSort()so/it has same signature as other sorting functions.template void recSelectionSortAux(ElementType x,int n,int first)if(first n)int minPos=first;int minValue=xfirst;for(int j=first+1;j=n;j+)if(xj minValue)minPos=j;minValue=xj;xminPos=xfirst;xfirst=minValue;recSelectionSortAux(x,n,first+1);/*recursive SelectionSort*/template void recSelectionSort(ElementType x,int size)recSelectionSortAux(x,size,0);7./Recursive helper function for recBubbleSort()so/it has same signature as other sorting functions.template void recBubbleSortAux(ElementType x,int numCompares)if(numCompares 0)int last=1;for(int i=1;i xi+1)int temp=xi;xi=xi+1;xi+1=temp;last=i;recBubbleSortAux(x,last-1);/*recursive BubbleSort*/template void recBubbleSort(ElementType x,int n)recBubbleSortAux(x,n);Chapter 13 230 8.Bubblesort algorithm for a linked list with head node:1.If first-next=0 /empty listterminate this algorithm.Else continue with the following:2.Initialize lastPtr=0,lastSwap=first.3.While(lastSwap-next!=0)lastSwap=lastSwap-next./Initially,put lastSwap at next-to-last node4.While(lastSwap!=first-next)a.ptr=first-nextb.while(ptr!=lastSwap)i.if(ptr-data ptr-next-data)(1)swap(ptr-data,ptr-next-data)(2)lastPtr=ptr ii.ptr=ptr-nextc.lastSwap=lastPtr9.(a)Elements of x after each pass:left to right:30 80 20 60 70 10 90 50 40 100right to left:10 30 80 20 60 70 40 90 50 100left to right:10 30 20 60 70 40 80 50 90 100right to left:10 20 30 40 60 70 50 80 90 100left to right:10 20 30 40 60 50 70 80 90 100right to left:10 20 30 40 50 60 70 80 90 100left to right:10 20 30 40 50 60 70 80 90 100right to left:10 20 30 40 50 60 70 80 90 100(b)Algorithm for two way bubble sort:O(n2).Do the following:1.Set interchanges1 and interchanges2 to false.2.For i=1 to n 1 do the following:If xi xi+1 thena.Interchange xi and xi+1b.Set interchanges1 to true.End for.3.If noInterchanges1 is false thenFor i=n 1 downto 1 do the following:If xi+1 next /points to the predecessor of the next node to be insertednextElPtr=predPtr-next/points to the node of the next element to be inserted 2.While(nextElPtr!=0)a.While(ptr-next!=nextElPtr&ptr-next-data data)ptr=ptr-nextEnd whileb.If(ptr-next!=nextElPtr)i.predPtr-next=nextElPtr-next ii.nextElPtr-next=ptr-nextiii.ptr-next=nextElPtr.iv.nextElPtr=predPtr-next Else i.predPtr=nextElPtrii.nextElPtr=nextElPtr-nextc.ptr=firstEnd while11.(a)Algorithm for binary insertion sort.For index=1 to end of array,do1.If xindex-1 xindex/Adjustment neededa.first=0,last=index,found=falseb.item=xindexc.while(!found&last-first 1)/binary search i.loc=(first+last)/2;ii.if xindex=xlocfound=trueelse if xindex xfirst i.shift array elements xlast.xindex 1 one position to the rightii.set xlast=itemelse i.shift array elements xfirst.xindex 1 one position to the rightii.set xfirst=itemChapter 13 232(b)Insert 90:90100 6070402050308010Insert 60:6090100 70402050308010Insert 70:607090100 402050308010Insert 40:40607090100 2050308010Insert 20:204060709010050308010Insert 50:204050607090100 308010Insert 30:20304050607090100 8010Insert 80:2030405060708090100 10Insert 10:102030405060708090100There were 27 comparisons of list elements.(b)There would be 35 comparisons of list elements.12.(a)40 10 50 30 80 20 60 70 100 9010 20 30 40 50 60 70 80 90 100(b)/*-Incremented Insertion Sort-*/template void incrInsertSort(ElementType x,int numElements,int start,int gap)ElementType nextElement;int j;for(int i=start+gap;i=start&nextElement xj-gap)/Shift element gap positions to right to open a spot xj=xj-gap;j-=gap;/Now drop next Element into the open spot xj=nextElement;Chapter 13 233/*-ShellSort x1,x2,.,xnumElements-*/template void shellSort(ElementType x,int numElements)int gap=1;/Find largest value in incr.seq.=numElements while(gap=1)for(int i=1;i=gap;i+)incrInsertSort(x,numElements,i,gap);gap/=3;13-14.The following are array-based treesort and supporting routines.Array and linked listimplementations are similar.The primary difference is one of traversal:index(for loop)is used foran array.A temporary pointer,continually updated to the contents of the next field(while loop),isused for a linked list.template void treeSort(ElementType x,int size)BST tree;for(int index=0;index size;index+)tree.insert(xindex);tree.inOrder(x);where inOrder()is a function member of BST defined as follows:template inline void BST:inOrder(ElementType x)int index=0;inOrderAux(root,x,index);template void BST:inOrderAux(BST:BinNodePointer root,ElementType x,int&index)if(root!=0)inOrderAux(root-left,x,index);xindex=root-data;index+;inOrderAux(root-right,x,index);Chapter 13 234 Exercises 13.21.The tree is not complete because the next-to-bottom level is not completely full.2.4712356356124712345671234567(b)3.13245678910132456789102456789101324567891013Chapter 13 235 571246891034.1 712 171231671264517126455417126456524171264567523417Chapter 13 236 5.1 112 1712312712246171224563171254566231712545676243176.1 712 67123657125464712545634712545662347Chapter 13 237 12545676213477.1 112 1212312312243141224543151254564231612645674253178.123456712345671234567124567Heapify2.(a)Chapter 13 238 471256561247731246123461356255324411132531544211325342432111 25 423213211 2 112Chapter 13 239 9.12345671234567234567124567Heapify3(b)47126561247731246123465513562553244113151544213231 2534243211321 25 4231321Chapter 13 240 1 2 11210.123456712345671234567124567Heapify1345613456(c)4712565612477312461234634513456135625532441123345132531544212233132534243211123Chapter 13 241 1 25 423213232111 2 11211.12345171234567163456112567Heapify3465754324712565173412636536137245135615532441432253132531544213322Chapter 13 242 1325342432111231 25 423213232111 2 11212.Contents of array x after each of the calls:After first call:20 15 31 49 67 50 3 10 26After second call:20 15 50 49 67 31 3 10 26(The remaining calls produce:After third call:20 67 50 49 15 31 3 10 26After fourth call:67 49 50 26 15 31 3 10 26)13.Contents of array x after each of the calls:After first call:88 77 55 66 22 33 44 99After second call:77 66 55 44 22 33 88 99(The remaining calls produce:After third call:66 44 55 33 22 77 88 99After fourth call:55 44 22 33 66 77 88 99After fifth call:44 33 22 55 66 77 88 99After sixth call:33 22 44 55 66 77 88 99After seventh call:22 33 44 55 66 77 88 99Chapter 13 243 14-15.#include using namespace std;const int HEAP_CAPACITY=127;template class Heap public:/-PUBLIC FUNCTION MEMBERS-Heap();/*-Constructor Precondition:None.Postcondition:An empty heap that can store HEAP_CAPACITY elements has been constructed.-*/bool empty()const;/*-Check if heap is empty.Precondition:None.Postcondition:True is returned if heap is empty,false if not.-*/int getSize()const;/*-Return number of elements in heap.Precondition:None.Postcondition:mySize is returned.-*/ElementType*getArray();/*-Return array used to store elements of heap.Precondition:None.Postcondition:myArray is returned.-*/void insert(ElementType item);/*-Insert operation Precondition:mySize HEAP_CAPACITY.Postcondition:item has been inserted into the heap so the result is still a heap,provided there is room in myArray;otherwise,a heap-full message is displayed and execution is terminated.-*/Chapter 13 244 ElementType getMax()const;/*-Retrieve the largest element in the heap.Precondition:Heap is nonempty.Postcondition:Largest element is returned if heap is nonempty,otherwise a heap-empty message is displayed and a garbage value is returned.-*/void removeMax();/*-Remove the largest element in the heap.Precondition:Heap is nonempty.Postcondition:Largest element is removed if heap is nonempty and result is still a heap;Otherwise a heap-empty message is displayed.-*/void remove(int loc);/*-Remove the element in location loc.Precondition:1=loc=mySize.Postcondition:Element at location loc is removed and result is still a heap;otherwise a bad-location message is displayed.-*/-Extra Functions to help visualize heaps private:/-DATA MEMBERS-int mySize;ElementType myArrayHEAP_CAPACITY;/-PRIVATE FUNCTION MEMBERS-void percolateDown(int r,int n);/*-Percolate-down operation Precondition:myArrayr,.,myArrayn stores a semiheap.Postcondition:The semiheap has been converted into a heap.-*/void heapify();/*-Heapify operation Precondition:myArray1,.,myArraymySize stores a complete binary tree.Postcondition:The complete binary tree has been converted into a heap.-*/;/-Definition of constructortemplate inline Heap:Heap():mySize(0)Chapter 13 245/-Definition of empty()template inline bool Heap:empty()const return mySize=0;/-Definition of getSize()template inline int Heap:getSize()const return mySize;/-Definition of getArray()template inline ElementType*Heap:getArray()return myArray;/-Definition of insert()template void Heap:insert(ElementType item)if(mySize=HEAP_CAPACITY)cerr=1&myArrayloc myArrayparent)/-Swap elements at positions loc and parent ElementType temp=myArrayloc;myArrayloc=myArrayparent;myArrayparent=temp;loc=parent;parent=loc/2;/-Definition of getMax()template ElementType Heap:getMax()const if(!empty()return myArray1;/else cerr Heap is empty-garbage value returnedn;ElementType garbage;return garbage;Chapter 13 246/-Definition of removeMax()template void Heap:removeMax()if(!empty()remove(1);else cerr Heap is empty-no element removed;/-Definition of remove()template void Heap:remove(int loc)if(1=loc and loc=mySize)myArrayloc=myArraymySize;mySize-;percolateDown(loc,mySize);else cerr Illegal location in heap:loc endl;/-Definition of percolateDown()template void Heap:percolateDown(int r,int n)int c;for(c=2*r;c=n;)if(c n&myArrayc myArrayc+1)c+;/Interchange node and largest child,if necessary /move down to the next subtree.if(myArrayr myArrayc)ElementType temp=myArrayr;myArrayr=myArrayc;myArrayc=temp;r=c;c*=2;else break;/-Definition of heapify()template void Heap:heapify()for(int r=mySize/2;r 0;r-)percolateDown(r,mySize);Chapter 13 247 16.#include using namespace std;#include Heap.h /file containing Heap class templateconst int PQ_CAPACITY=HEAP_CAPACITY;template/*is assumed to be defined for type ElementType so that x y if xs priority ys priority.*/class PriorityQueue public:PriorityQueue();/*-Constructor Precondition:None.Postcondition:An empty priority queue that can store PQ_CAPACITY elements has been constructed.-*/bool empty();/*-Check if priority queue is empty.Precondition:None.Postcondition:True is returned if priority queue is empty,false if not.-*/void insert(ElementType item);/*-Insert operation Precondition:mySize PQ_CAPACITY.Postcondition:item has been inserted into the priority queue so the result is still a priority queue,provided there is room in myHeap;otherwise,a priority-queue-full message is displayed and execution is terminated.-*/ElementType getMax();/*-Retrieve the largest(i.e.,with highest priority)element in the priority queue.Precondition:Priority queue is nonempty.Postcondition:Largest element is returned if priority queue is nonempty,otherwise a priority-queue-empty message is displayed and a garbage value is returned.-*/Chapter 13 248 void removeMax();/*-Remove the largest(i.e.,with highest priority)element in the priority queue.Precondition:Priority queue is nonempty.Postcondition:Largest element is removed if priority queue is nonempty and result is still a priority queue;Otherwise a priority-queue-empty message is displayed.-*/void display(ostream&out);/*-Display elements of priority queue.Precondition:ostream out is open.Postcondition:Elements of priority queue have been displayed(from front to back)to out.-*/private:Heap myHeap;/-Definition of constructortemplate inline PriorityQueue:PriorityQueue()/Let Heap constructor do the work/-Definition of empty()template inline bool PriorityQueue:empty()myHeap.empty();/-Definition of insert()template inline void PriorityQueue:insert(ElementType item)if(myHeap.getSize()PQ_CAPACITY)myHeap.insert(item);else cerr No more room in priority queue-increase its capacityn;exit(1);Chapter 13 249/-Definition of getMax()template ElementType PriorityQueue:getMax()return myHeap.getMax();/-Definition of removeMax()template void PriorityQueue:removeMax()myHeap.removeMax();/-Definition of display()template void PriorityQueue:display(ostream&out)for(int i=1;i=myHeap.getSize();i+)out myHeap.getArray()i ;out endl;Exercises 13.31.The array elements are10 20 40 30 45 80 60 70 50 90.2.The following diagram shows the sequence for trees for Exercise 2.Only the final trees forExercises 3,4 and 5 are given.E,A,F,D,C,BE,A,F,D,C,BC,A,B,DFE(a)ABE,A,F,D,C,BC,A,B,DFEB,ACDE,A,F,D,C,BC,A,B,DFEB,ACDChapter 13 250 BE,A,F,D,C,BC,A,B,DFEB,ACDABAE,A,F,D,C,BC,A,B,DFEB,ACDABDE,A,F,D,C,BC,A,B,DFECB,AABBDE,A,F,D,C,BC,A,B,DEB,ACAF3.FFFCEBAFDF,E,DC,F,E,DB,C,F,E,DA,B,C,F,E,D(b)Chapter 13 251 4.5.BFFEBBBE,D,C,B,AF,E,D,C,B,A D,C,B,A C,B,A B,ACEBAFDFFFCBADD,E,FC,D,E,FB,C,D,E