page385.html
来自「wqeqwvrw rkjqhwrjwq jkhrjqwhrwq jkhrwq」· HTML 代码 · 共 89 行
HTML
89 行
<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="tex2html6683" HREF="page386.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page386.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="tex2html6681" HREF="page352.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page352.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="tex2html6675" HREF="page384.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page384.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="tex2html6685" 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="tex2html6686" 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="SECTION0012600000000000000000">Exercises</A></H1>
<P>
<OL><LI> <A NAME="exercisepqueuesi"> </A>
For each of the following key sequences
determine the binary heap obtained when the keys
are inserted one-by-one in the order given
into an initially empty heap:
<OL><LI> 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.<LI> 3, 1, 4, 1, 5, 9, 2, 6, 5, 4.<LI> 2, 7, 1, 8, 2, 8, 1, 8, 2, 8.
</OL><LI> <A NAME="exercisepqueuesii"> </A>
For each of the binary heaps
obtained in Exercise <A HREF="page385.html#exercisepqueuesi" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page385.html#exercisepqueuesi"><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>
determine the heap obtained after three consecutive
<tt>DequeueMin</tt> operations.<LI>
Repeat Exercises <A HREF="page385.html#exercisepqueuesi" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page385.html#exercisepqueuesi"><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="page385.html#exercisepqueuesii" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page385.html#exercisepqueuesii"><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> for a leftist heap.<LI>
Show the result obtained by inserting the keys
<IMG WIDTH=89 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline67080" SRC="img1580.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1580.gif" > one-by-one in the order given
into an initially empty binomial queue.<LI>
A <em>full</em> binary tree is a tree in which each node
is either a leaf or its is a <em>full node</em>
(see Exercise <A HREF="page297.html#exercisetreesfullnode" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page297.html#exercisetreesfullnode"><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>).
Consider a <em>complete</em> binary tree with <I>n</I> nodes.
<OL><LI>
For what values of <I>n</I> is a complete binary tree
a <em>full</em> binary tree.<LI>
For what values of <I>n</I> is a complete binary
a <em>perfect</em> binary tree.
</OL><LI> <A NAME="exercisepqueuesipl"> </A>
Prove by induction Theorem <A HREF="page355.html#theorempqueuesiii" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page355.html#theorempqueuesiii"><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>
Devise an algorithm to determine whether a given binary tree is a heap.
What is the running time of your algorithm?<LI>
Devise an algorithm to find the <em>largest</em> item
in a binary <em>min</em> heap.
<b>Hint</b>: First, show that the largest item
must be in one of the leaves.
What is the running time of your algorithm?<LI> <A NAME="exercisepqueuesheapify"> </A>
Suppose we are given an arbitrary array of <I>n</I> keys
to be inserted into a binary heap all at once.
Devise an <I>O</I>(<I>n</I>) algorithm to do this.
<b>Hint</b>: See Section <A HREF="page504.html#secsortingheap" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page504.html#secsortingheap"><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>
Devise an algorithm to determine whether a given binary tree
is a leftist tree.
What is the running time of your algorithm?<LI> <A NAME="exercisepqueuesleftist"> </A>
Prove that a complete binary tree is a leftist tree.<LI>
Suppose we are given an arbitrary array of <I>n</I> keys
to be inserted into a leftist heap all at once.
Devise an <I>O</I>(<I>n</I>) algorithm to do this.
<b>Hint</b>: See Exercises <A HREF="page385.html#exercisepqueuesheapify" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page385.html#exercisepqueuesheapify"><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="page385.html#exercisepqueuesleftist" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page385.html#exercisepqueuesleftist"><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="exercisepqueuespath"> </A>
Consider a complete binary tree
with its nodes numbered as shown in Figure <A HREF="page355.html#figtree16" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page355.html#figtree16"><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>.
Let <I>K</I> be the number of a node in the tree.
The the binary representation of <I>K</I> is
<P> <IMG WIDTH=295 HEIGHT=47 ALIGN=BOTTOM ALT="displaymath67076" SRC="img1581.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1581.gif" ><P>
where <IMG WIDTH=86 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline67100" SRC="img1582.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1582.gif" >.
<OL><LI>
Show that path from the root to a given node <I>K</I>
passes passes through the following nodes:
<P> <IMG WIDTH=322 HEIGHT=120 ALIGN=BOTTOM ALT="displaymath67077" SRC="img1583.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1583.gif" ><P><LI>
Consider a complete binary tree with <I>n</I> nodes.
The nodes on the path from the root to the <IMG WIDTH=21 HEIGHT=13 ALIGN=BOTTOM ALT="tex2html_wrap_inline58453" SRC="img94.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img94.gif" >
are <em>special</em>.
Show that every non-special node
is the root of a perfect tree.
</OL><LI>
The <tt>Enqueue</tt> algorithm for the <tt>BinaryHeap</tt> class
does <IMG WIDTH=56 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59891" SRC="img403.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img403.gif" > object comparisons in the worst case.
In effect, this algorithm does a linear search from a leaf
to the root to find the point at which to insert a new key.
Devise an algorithm that a binary search instead.
Show that the number of comparisons required becomes <IMG WIDTH=79 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67110" SRC="img1584.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1584.gif" >.
<b>Hint</b>: See Exercise <A HREF="page385.html#exercisepqueuespath" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page385.html#exercisepqueuespath"><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="exercisepqueuesbinom"> </A>
Prove Theorem <A HREF="page371.html#theorempqueuesbinom" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page371.html#theorempqueuesbinom"><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>
Do Exercise <A HREF="page350.html#exercisesrchtreecomplete" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page350.html#exercisesrchtreecomplete"><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>.
</OL><HR><A NAME="tex2html6683" HREF="page386.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page386.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="tex2html6681" HREF="page352.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page352.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="tex2html6675" HREF="page384.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page384.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="tex2html6685" 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="tex2html6686" 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 + -
显示快捷键?