数据结构与算法分析 第13章 答案 Larry Nyhoff 清华大.pdf
《数据结构与算法分析 第13章 答案 Larry Nyhoff 清华大.pdf》由会员分享,可在线阅读,更多相关《数据结构与算法分析 第13章 答案 Larry Nyhoff 清华大.pdf(44页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、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 p
2、ositioned: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(Elem
3、entType 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;
4、/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 ex
5、ecutes,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
6、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
7、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;/Recreat
8、e 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
9、(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 helpe
10、r 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 recBubbl
11、eSort(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./Initial
12、ly,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 le
13、ft: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)
14、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 /po
15、ints 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-ne
16、xtiii.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-fir
17、st 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 6070402050
18、308010Insert 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 elemen
19、ts.(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
20、 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(
21、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 up
22、dated 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(Ele
23、mentType 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-bot
24、tom level is not completely full.2.4712356356124712345671234567(b)3.13245678910132456789102456789101324567891013Chapter 13 235 571246891034.1 712 171231671264517126455417126456524171264567523417Chapter 13 236 5.1 112 1712312712246171224563171254566231712545676243176.1 712 671236571254647125456347125
25、45662347Chapter 13 237 12545676213477.1 112 1212312312243141224543151254564231612645674253178.123456712345671234567124567Heapify2.(a)Chapter 13 238 471256561247731246123461356255324411132531544211325342432111 25 423213211 2 112Chapter 13 239 9.12345671234567234567124567Heapify3(b)4712656124773124612
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构与算法分析 第13章 答案 Larry Nyhoff 清华大 数据结构 算法 分析 13 清华
限制150内