page350.html
来自「wqeqwvrw rkjqhwrjwq jkhrjqwhrwq jkhrwq」· HTML 代码 · 共 103 行
HTML
103 行
<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="tex2html6247" HREF="page351.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page351.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="tex2html6245" HREF="page299.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page299.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="tex2html6239" HREF="page349.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page349.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="tex2html6249" 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="tex2html6250" 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="SECTION0011900000000000000000">Exercises</A></H1>
<P>
<OL><LI> <A NAME="exercisesrchtreei"> </A>
For each of the following key sequences
determine the binary search tree obtained when the keys
are inserted one-by-one in the order given
into an initially empty tree:
<OL><LI> 1, 2, 3, 4, 5, 6, 7.<LI> 4, 2, 1, 3, 6, 5, 7.<LI> 1, 6, 7, 2, 4, 3, 5.
</OL><LI> <A NAME="exercisesrchtreeii"> </A>
For each of the binary search trees
obtained in Exercise <A HREF="page350.html#exercisesrchtreei" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page350.html#exercisesrchtreei"><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 tree obtained when the root is withdrawn.<LI>
Repeat Exercises <A HREF="page350.html#exercisesrchtreei" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page350.html#exercisesrchtreei"><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="page350.html#exercisesrchtreeii" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page350.html#exercisesrchtreeii"><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 AVL trees.<LI>
Derive an expression for the total space needed to
represent a tree of <I>n</I> internal nodes
using each of the following classes:
<OL><LI> <tt>BST</tt> defined in Program <A HREF="page312.html#progbst1h" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page312.html#progbst1h"><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> <tt>AVLTree</tt> defined in Program <A HREF="page321.html#progavl1h" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page321.html#progavl1h"><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> <tt>MWayTree</tt> defined in Program <A HREF="page332.html#progmwaytree1h" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page332.html#progmwaytree1h"><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<LI> <tt>BTree</tt> defined in Program <A HREF="page341.html#progbtree1h" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page341.html#progbtree1h"><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>
<b>Hint</b>: For the <tt>MWayTree</tt> and <tt>BTree</tt> assume
that the tree contains are <I>k</I> keys, where <IMG WIDTH=38 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline66064" SRC="img1420.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1420.gif" >.<LI>
To delete a non-leaf node from a binary search tree,
we swap it either with the smallest key its right subtree
or with the largest key in its left subtree
and then recursively delete it from the subtree.
In a tree of <I>n</I> nodes,
what its the maximum number of swaps needed to delete a key?<LI>
Devise an algorithm to compute the internal path length of a tree.
What is the running time of your algorithm?<LI>
Devise an algorithm to compute the external path length of a tree.
What is the running time of your algorithm?<LI>
Suppose that you are given a sorted sequence of <I>n</I> keys,
<IMG WIDTH=145 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline66070" SRC="img1421.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1421.gif" >,
to be inserted into a binary search tree.
<OL><LI>
What is the minimum height of a binary tree
that contains <I>n</I> nodes.<LI>
Devise an algorithm to insert the given keys
into a binary search tree so that the height
of the resulting tree is minimized.<LI>
What is the running time of your algorithm?
</OL><LI>
Devise an algorithm to construct an AVL tree of a given height <I>h</I>
that contains the minimum number of nodes.
The tree should contain the keys
<IMG WIDTH=94 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline66076" SRC="img1422.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1422.gif" >,
where <IMG WIDTH=19 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline64930" SRC="img1315.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1315.gif" > is given by Equation <A HREF="page320.html#eqnsrchtreeavl" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page320.html#eqnsrchtreeavl"><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>
Consider what happens when we insert the keys
<IMG WIDTH=134 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline66080" SRC="img1423.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1423.gif" > one-by-one in the order given
into an initially empty AVL tree for <IMG WIDTH=36 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline63700" SRC="img1122.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1122.gif" >.
Prove that the result is always a perfect tree of height <I>h</I>.<LI> <A NAME="exercisesrchtreefind"> </A>
The <tt>Find</tt> routine defined in Program <A HREF="page314.html#progbst2c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page314.html#progbst2c"><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> is recursive.
Write a non-recursive routine to find a given item
in a binary search tree.<LI>
Repeat Exercise <A HREF="page350.html#exercisesrchtreefind" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page350.html#exercisesrchtreefind"><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 the <tt>FindMin</tt> function
defined in Program <A HREF="page314.html#progbst2c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page314.html#progbst2c"><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 select the <IMG WIDTH=20 HEIGHT=13 ALIGN=BOTTOM ALT="tex2html_wrap_inline61700" SRC="img803.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img803.gif" > key
in a binary search tree.
E.g., given a tree with <I>n</I> nodes,
<I>k</I>=0 selects the smallest key,
<I>k</I>=<I>n</I>-1 selects the largest key,
and <IMG WIDTH=95 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline66094" SRC="img1424.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1424.gif" > selects the median key.<LI>
Devise an algorithm to test whether a given binary search tree
is AVL balanced.
What is the running time of your algorithm?<LI>
Devise an algorithm that takes two values,
<I>a</I> and <I>b</I> such that <IMG WIDTH=37 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline66100" SRC="img1425.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1425.gif" >,
and which visits all the keys <I>x</I> in a binary search tree
such that <IMG WIDTH=67 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline66104" SRC="img1426.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1426.gif" >.
The running time of your algorithm should be <IMG WIDTH=90 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline66106" SRC="img1427.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1427.gif" >,
where <I>N</I> is the number of keys visited
and <I>n</I> is the number of keys in the tree.<LI>
Devise an algorithm to merge the contents of two binary search
trees into one.
What is the running time of your algorithm?<LI> <A NAME="exercisesrchtreecomplete"> </A>
(This question should be attempted
<em>after</em> reading Chapter <A HREF="page352.html#chappqueues" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page352.html#chappqueues"><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>).
Prove that a <em>complete binary tree</em> (Definition <A HREF="page355.html#defncompletebt" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page355.html#defncompletebt"><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>)
is AVL balanced.<LI>
Do Exercise <A HREF="page248.html#exercisehashingtree" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page248.html#exercisehashingtree"><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="exercisesrchtreeiii"> </A>
For each of the following key sequences
determine the 3-way search tree obtained when the keys
are inserted one-by-one in the order given
into an initially empty tree:
<OL><LI> 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.<LI> 3, 1, 4, 5, 9, 2, 6, 8, 7, 0.<LI> 2, 7, 1, 8, 4, 5, 9, 0, 3, 6.
</OL><LI>
Repeat Exercise <A HREF="page350.html#exercisesrchtreeiii" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page350.html#exercisesrchtreeiii"><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 B-trees of order 3.
</OL><HR><A NAME="tex2html6247" HREF="page351.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page351.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="tex2html6245" HREF="page299.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page299.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="tex2html6239" HREF="page349.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page349.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="tex2html6249" 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="tex2html6250" 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 + -
显示快捷键?