page517.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 140 行
HTML
140 行
<HTML><HEAD><TITLE>Exercises</TITLE></HEAD><BODY bgcolor="#FFFFFF"> <a href="../index.html" target="_top"><img src="../icons/usins.gif" alt="Logo" align=right></a><b>Data Structures and Algorithms with Object-Oriented Design Patterns in Python</b><br><A NAME="tex2html7104" HREF="page518.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html7102" HREF="page478.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html7096" HREF="page516.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html7106" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H1><A NAME="SECTION00151000000000000000000">Exercises</A></H1><P><OL><LI> <A NAME="exercisesortingi"> </A> Consider the sequence of integers <P> <IMG WIDTH=347 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath70431" SRC="img2148.gif" ><P> For each of the following sorting algorithms, draw a sequence of diagrams that traces the execution of the algorithm as it sorts the sequence <I>S</I>: straight insertion sort, binary insertion sort, bubble sort, quick sort, straight selection sort, heapsort, merge sort, and bucket sort.<LI> <A NAME="exercisesortingii"> </A> Draw a sequence of diagrams that traces the execution of a radix-10 sort of the sequence <P> <IMG WIDTH=386 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath70432" SRC="img2149.gif" ><P><LI> For each of the sorting algorithms listed in Exercises <A HREF="page517.html#exercisesortingi"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> and <A HREF="page517.html#exercisesortingii"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> indicate whether the sorting algorithm is <em>stable</em>.<LI> Consider a sequence of three distinct keys <IMG WIDTH=51 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline66503" SRC="img1539.gif" >. Draw the binary decision tree that represents each of the following sorting algorithms: straight insertion sort, straight selection sort, and bubble sort.<LI> <A NAME="exercisesortingsort5"> </A> Devise an algorithm to sort a sequence of exactly five elements. Make your algorithm as efficient as possible.<LI> Prove that the swapping of a pair of adjacent elements removes at most one inversion from a sequence.<LI> Consider the sequence of elements <IMG WIDTH=102 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70443" SRC="img2150.gif" >. What is the maximum number of inversions that can be removed by the swapping of a pair of distinct elements <IMG WIDTH=11 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline68959" SRC="img1985.gif" > and <IMG WIDTH=11 HEIGHT=15 ALIGN=MIDDLE ALT="tex2html_wrap_inline68961" SRC="img1986.gif" >? Express the result in terms of the <em>distance</em> between <IMG WIDTH=11 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline68959" SRC="img1985.gif" > and <IMG WIDTH=11 HEIGHT=15 ALIGN=MIDDLE ALT="tex2html_wrap_inline68961" SRC="img1986.gif" >: <IMG WIDTH=135 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline70453" SRC="img2151.gif" >.<LI> Devise a sequence of keys such that <em>exactly</em> eleven inversions are removed by the swapping of one pair of elements.<LI> Prove that <em>binary insertion sort</em> requires <IMG WIDTH=68 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59353" SRC="img402.gif" > comparisons.<LI> <A NAME="exercisesortingpasses"> </A> Consider an arbitrary sequence <IMG WIDTH=102 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70443" SRC="img2150.gif" >. To sort the sequence, we determine the permutation <IMG WIDTH=104 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67695" SRC="img1715.gif" > such that <P> <IMG WIDTH=324 HEIGHT=14 ALIGN=BOTTOM ALT="displaymath70433" SRC="img2152.gif" ><P> Prove that <em>bubble sort</em> requires at least <I>p</I> passes where <P> <IMG WIDTH=311 HEIGHT=25 ALIGN=BOTTOM ALT="displaymath70434" SRC="img2153.gif" ><P><LI> Modify the bubble sort algorithm (Program <A HREF="page489.html#progbubbleSortera"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>) so that it terminates the outer loop when it detects that the array is sorted. What is the running time of the modified algorithm? <b>Hint</b>: See Exercise <A HREF="page517.html#exercisesortingpasses"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.<LI> A variant of the bubble sorting algorithm is the so-called <em>odd-even transposition sort</em><A NAME=47504> </A>. Like bubble sort, this algorithm a total of <I>n</I>-1 passes through the array. Each pass consists of two phases: The first phase compares <IMG WIDTH=60 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70465" SRC="img2154.gif" > with <IMG WIDTH=88 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70467" SRC="img2155.gif" > and swaps them if necessary for all the odd values of of <I>i</I>. The second phase does the same for the even values of <I>i</I>. <OL><LI> Show that the array is guaranteed to be sorted after <I>n</I>-1 passes.<LI> What is the running time of this algorithm? </OL><LI> Another variant of the bubble sorting algorithm is the so-called <em>cocktail shaker sort</em><A NAME=47510> </A>. Like bubble sort, this algorithm a total of <I>n</I>-1 passes through the array. However, alternating passes go in opposite directions. For example, during the first pass the largest item bubbles to the end of the array and during the second pass the smallest item bubbles to the beginning of the array. <UL><LI> Show that the array is guaranteed to be sorted after <I>n</I>-1 passes.<LI> What is the running time of this algorithm? </UL><LI> <A NAME="exercisesortingselect"> </A> Consider the following algorithm for selecting the <IMG WIDTH=20 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline61477" SRC="img821.gif" > largest element from an unsorted sequence of of <I>n</I> elements, <IMG WIDTH=134 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70483" SRC="img2156.gif" >. <OL><LI> If <IMG WIDTH=38 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70485" SRC="img2157.gif" >, sort <I>S</I> and select directly the <IMG WIDTH=20 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline61477" SRC="img821.gif" > largest element.<LI> Otherwise <I>n</I><I>></I>5: Partition the sequence <I>S</I> into subsequences of length five. In general, there will be <IMG WIDTH=35 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70495" SRC="img2158.gif" > subsequences of length five and one of length <IMG WIDTH=56 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline70497" SRC="img2159.gif" >.<LI> Sort by any means each of the subsequences of length five. (See Exercise <A HREF="page517.html#exercisesortingsort5"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>).<LI> Form the sequence <IMG WIDTH=184 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70499" SRC="img2160.gif" > containing the <IMG WIDTH=35 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70495" SRC="img2158.gif" > median values of each of the subsequences of length five.<LI> Apply the selection method recursively to find the median element of <I>M</I>. Let <I>m</I> be the median of the medians.<LI> Partition <I>S</I> into three subsequences, <IMG WIDTH=97 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70509" SRC="img2161.gif" >. such that all the elements in <I>L</I> are less than <I>m</I>, all the elements in <I>E</I> are equal to <I>m</I>, and all the elements of <I>G</I> are greater than <I>m</I>.<LI> If <IMG WIDTH=47 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70523" SRC="img2162.gif" > then apply the method recursively to select the <IMG WIDTH=20 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline61477" SRC="img821.gif" > largest element of <I>L</I>; if <IMG WIDTH=130 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70529" SRC="img2163.gif" >, the result is <I>m</I>; otherwise apply the method recursively to select the <IMG WIDTH=124 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline70533" SRC="img2164.gif" > largest element of <I>G</I>. </OL> <OL><LI> What is the running time of this algorithm?<LI> Show that if we use this algorithm to select the pivot the worst-case running time of <em>quick sort</em> is <IMG WIDTH=68 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59353" SRC="img402.gif" >. </OL><LI> <A NAME="exercisesortingcomplete"> </A> Show that the sum of the heights of the nodes in a complete binary tree with <I>n</I> nodes altogether is <I>n</I>-<I>b</I>(<I>n</I>), where <I>b</I>(<I>n</I>) is the number of ones in the binary representation of <I>n</I>.</OL><HR><A NAME="tex2html7104" HREF="page518.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html7102" HREF="page478.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html7096" HREF="page516.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html7106" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <P><ADDRESS><img src="../icons/bruno.gif" alt="Bruno" align=right><a href="../copyright.html">Copyright © 2003</a> by <a href="../signature.html">Bruno R. Preiss, P.Eng.</a> All rights reserved.</ADDRESS></BODY></HTML>⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?