📄 page384.html
字号:
<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="tex2html5608" HREF="page385.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html5606" HREF="page351.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html5600" HREF="page383.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html5610" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H1><A NAME="SECTION0011600000000000000000">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="page384.html#exercisepqueuesi"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> determine the heap obtained after three consecutive <tt>dequeueMin</tt> operations.<LI> Repeat Exercises <A HREF="page384.html#exercisepqueuesi"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> and <A HREF="page384.html#exercisepqueuesii"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> for a leftist heap.<LI> Show the result obtained by inserting the keys <IMG WIDTH=87 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline66455" SRC="img1528.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="page296.html#exercisetreesfullnode"><IMG ALIGN=BOTTOM ALT="gif" SRC="../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="page354.html#theorempqueuesiii"><IMG ALIGN=BOTTOM ALT="gif" SRC="../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="page500.html#secsortingheap"><IMG ALIGN=BOTTOM ALT="gif" SRC="../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="page384.html#exercisepqueuesheapify"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> and <A HREF="page384.html#exercisepqueuesleftist"><IMG ALIGN=BOTTOM ALT="gif" SRC="../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="page354.html#figtree16"><IMG ALIGN=BOTTOM ALT="gif" SRC="../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="displaymath66451" SRC="img1529.gif" ><P> where <IMG WIDTH=85 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline66475" SRC="img1530.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=119 ALIGN=BOTTOM ALT="displaymath66452" SRC="img1531.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=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline57913" SRC="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_inline59347" SRC="img400.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_inline66485" SRC="img1532.gif" >. <b>Hint</b>: See Exercise <A HREF="page384.html#exercisepqueuespath"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.<LI> <A NAME="exercisepqueuesbinom"> </A> Prove Theorem <A HREF="page369.html#theorempqueuesbinom"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.<LI> Do Exercise <A HREF="page349.html#exercisesrchtreecomplete"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.</OL><HR><A NAME="tex2html5608" HREF="page385.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html5606" HREF="page351.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html5600" HREF="page383.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html5610" 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 + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -