page201.html
来自「wqeqwvrw rkjqhwrjwq jkhrjqwhrwq jkhrwq」· HTML 代码 · 共 82 行
HTML
82 行
<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="tex2html4393" HREF="page202.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page202.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="tex2html4391" HREF="page166.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page166.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="tex2html4385" HREF="page200.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page200.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="tex2html4395" 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="tex2html4396" 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="SECTION008300000000000000000">Exercises</A></H1>
<P>
<OL><LI>
Devise an algorithm to reverse the contents of an ordered list.
Determine the running time of your algorithm.<LI> <A NAME="exerciselistsappend"> </A>
Devise an algorithm to append the contents of one ordered list
to the end of another.
Assume that both lists are represented using arrays.
What is the running time of your algorithm?<LI>
Repeat Exercise <A HREF="page201.html#exerciselistsappend" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page201.html#exerciselistsappend"><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>,
but this time assume that both lists are represented using linked lists.
What is the running time of your algorithm?<LI> <A NAME="exerciselistsmerge"> </A>
Devise an algorithm to merge the contents of two sorted lists.
Assume that both lists are represented using arrays.
What is the running time of your algorithm?<LI>
Repeat Exercise <A HREF="page201.html#exerciselistsmerge" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page201.html#exerciselistsmerge"><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>,
but this time assume that both lists are represented using linked lists.
What is the running time of your algorithm?<LI>
The <tt>Withdraw</tt> function can be used to
remove items from a list one at a time.
Suppose we want to provide an additional a member function,
<tt>WithdrawAll</tt>,
that takes one argument and withdraws all the items in a list
that <em>match</em> the given argument.
<P>
We can provide an abstract implementation of the <tt>WithdrawAll</tt>
function in the <tt>List</tt> class like this:
<PRE>void List::WithdrawAll (Object const& arg)
{
for (;;)
{
Object& object = Find (arg);
if (object.IsNull ())
break;
Withdraw (object);
}
}</PRE>
Determine the worst-case running time of this routine
for each of the following cases:
<OL><LI> an array-based implementation of an ordered list,<LI> a linked-list implementation of an ordered list,<LI> an array-based implementation of a sorted list, and<LI> a linked-list implementation of a sorted list.
</OL><LI> <A NAME="exerciselistswithdrawall"> </A>
Devise an <I>O</I>(<I>n</I>) algorithm,
to remove from an ordered list
all the items that match a given item.
Assume the list is represented using an array.<LI>
Repeat Exercise <A HREF="page201.html#exerciselistswithdrawall" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page201.html#exerciselistswithdrawall"><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>,
but this time assume the ordered list
is represented using a linked list.<LI>
Consider an implementation of the <tt>OrderedList</tt> class that uses
a doubly-linked list such as the one shown in Figure <A HREF="page163.html#figdeque2" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page163.html#figdeque2"><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> (a).
Compare the running times of the operations for this implementation
with those given in Table <A HREF="page186.html#tbllists" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page186.html#tbllists"><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>
Derive an expression for the amount of space used to represent
an ordered list of <I>n</I> elements using
a doubly-linked list such as the one shown in Figure <A HREF="page163.html#figdeque2" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page163.html#figdeque2"><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> (a).
Compare this with the space used by the array-based implementation.
Assume that integers and pointers each occupy four bytes.<LI>
Consider an implementation of the <tt>SortedList</tt> class that uses
a doubly-linked list such as the one shown in Figure <A HREF="page163.html#figdeque2" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page163.html#figdeque2"><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> (a).
Compare the running times of the operations for this implementation
with those given in Table <A HREF="page197.html#tblsortedlists" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page197.html#tblsortedlists"><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 NAME="exerciselistsproof"> </A>
Verify that Program <A HREF="page199.html#progapp04cc" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page199.html#progapp04cc"><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> correctly computes
the sum of two polynomials.<LI>
Write an algorithm to multiply a polynomial by a scalar.
<b>Hint</b>: Use a visitor.
</OL><HR><A NAME="tex2html4393" HREF="page202.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page202.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="tex2html4391" HREF="page166.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page166.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="tex2html4385" HREF="page200.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page200.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="tex2html4395" 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="tex2html4396" 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> <P><ADDRESS>
<img src="bruno.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/bruno.gif" alt="Bruno" align=right>
<a href="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address. \n\nDo you want to open it from the server?'))window.location='http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html">Copyright © 1997</a> by <a href="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address. \n\nDo you want to open it from the server?'))window.location='http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html">Bruno R. Preiss, P.Eng.</a> All rights reserved.
</ADDRESS>
</BODY>
</HTML>
⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?