page521.html
来自「wqeqwvrw rkjqhwrjwq jkhrjqwhrwq jkhrwq」· HTML 代码 · 共 140 行 · 第 1/2 页
HTML
140 行
<HTML>
<HEAD>
<TITLE>Exercises</TITLE>
</HEAD>
<BODY bgcolor="#FFFFFF">
<img src="cover75.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cover75.gif" alt="Logo" align=right>
<b>Data Structures and Algorithms
with Object-Oriented Design Patterns in C++</b><br>
<A NAME="tex2html8345" HREF="page522.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page522.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="next_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/next_motif.gif"></A> <A NAME="tex2html8343" HREF="page483.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page483.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="up_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/up_motif.gif"></A> <A NAME="tex2html8337" HREF="page520.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page520.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="previous_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/previous_motif.gif"></A> <A NAME="tex2html8347" HREF="page9.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page9.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="contents_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/contents_motif.gif"></A> <A NAME="tex2html8348" HREF="page620.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page620.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="index_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/index_motif.gif"></A> <BR><HR>
<H1><A NAME="SECTION00161000000000000000000">Exercises</A></H1>
<P>
<OL><LI> <A NAME="exercisesortingi"> </A>
Consider the sequence of integers
<P> <IMG WIDTH=347 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath71237" SRC="img2264.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2264.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=387 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath71238" SRC="img2265.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2265.gif" ><P><LI>
For each of the sorting algorithms listed
in Exercises <A HREF="page521.html#exercisesortingi" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page521.html#exercisesortingi"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> and <A HREF="page521.html#exercisesortingii" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page521.html#exercisesortingii"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/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=49 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67128" SRC="img1591.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1591.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 three 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=103 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline71249" SRC="img2266.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2266.gif" >.
What is the maximum number of inversions that can be removed
by the swapping of a pair of distinct elements <IMG WIDTH=9 HEIGHT=15 ALIGN=MIDDLE ALT="tex2html_wrap_inline69747" SRC="img2098.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2098.gif" > and <IMG WIDTH=12 HEIGHT=16 ALIGN=MIDDLE ALT="tex2html_wrap_inline69749" SRC="img2099.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2099.gif" >?
Express the result in terms of the <em>distance</em>
between <IMG WIDTH=9 HEIGHT=15 ALIGN=MIDDLE ALT="tex2html_wrap_inline69747" SRC="img2098.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2098.gif" > and <IMG WIDTH=12 HEIGHT=16 ALIGN=MIDDLE ALT="tex2html_wrap_inline69749" SRC="img2099.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2099.gif" >: <IMG WIDTH=135 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline71259" SRC="img2267.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2267.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_inline59897" SRC="img405.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img405.gif" > comparisons.<LI> <A NAME="exercisesortingpasses"> </A>
Consider an arbitrary sequence <IMG WIDTH=103 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline71249" SRC="img2266.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2266.gif" >.
To sort the sequence, we determine the permutation
<IMG WIDTH=105 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline68485" SRC="img1821.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1821.gif" > such that
<P> <IMG WIDTH=324 HEIGHT=15 ALIGN=BOTTOM ALT="displaymath71239" SRC="img2268.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2268.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="displaymath71240" SRC="img2269.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2269.gif" ><P><LI>
Modify the bubble sort algorithm (Program <A HREF="page493.html#progsorter3c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page493.html#progsorter3c"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/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="page521.html#exercisesortingpasses" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page521.html#exercisesortingpasses"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/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=47737> </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=54 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline71271" SRC="img2270.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2270.gif" > with <IMG WIDTH=82 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline71273" SRC="img2271.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2271.gif" >
⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?