page249.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 143 行
HTML
143 行
<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="tex2html4065" HREF="page250.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html4063" HREF="page205.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html4057" HREF="page248.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html4067" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H1><A NAME="SECTION008800000000000000000">Exercises</A></H1><P><OL><LI> Suppose we know <em>a priori</em> that a given key is equally likely to be any integer between <I>a</I> and <I>b</I>. <OL><LI> When is the <em>division method of hashing</em> a good choice?<LI> When is the <em>middle square method of hashing</em> a good choice? </OL><LI> Compute (by hand) the hash value obtained by Program <A HREF="page220.html#progstrnga"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> for the strings <tt>"ece.uw.ca"</tt> and <tt>"cs.uw.ca"</tt>. <b>Hint</b>: Refer to Appendix <A HREF="page609.html#appcharcode"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.<LI> Canadian postal codes have the format <code>LDL DLD</code> where <tt>L</tt> is always a letter (<tt>A</tt>-<tt>Z</tt>), <tt>D</tt> is always a digit (<tt>0</tt>-<tt>9</tt>), and <code> </code> is always a single space. For example, the postal code for the University of Waterloo is <code>N2L 3G1</code>. Devise a suitable hash function for Canadian postal codes.<LI> <A NAME="exercisehashingi"> </A> For each type of hash table listed below, show the hash table obtained when we insert the keys <P> <IMG WIDTH=500 HEIGHT=40 ALIGN=BOTTOM ALT="equation13944" SRC="img1030.gif" ><P> in the order given into a table of size <I>M</I>=16 that is initially empty. Use the following table of hash values: <DIV ALIGN=CENTER><P ALIGN=CENTER><TABLE COLS=2 BORDER FRAME=HSIDES RULES=GROUPS><COL ALIGN=LEFT><COL ALIGN=RIGHT><TBODY><TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> <I>x</I> </TD><TD VALIGN=BASELINE ALIGN=RIGHT NOWRAP> <tt>Hash(<I>x</I>)</tt> (octal) </TD></TR></TBODY><TBODY><TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP><tt>"un"</tt> </TD><TD VALIGN=BASELINE ALIGN=RIGHT NOWRAP> <tt>016456</tt> </TD></TR><TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> <tt>"deux"</tt> </TD><TD VALIGN=BASELINE ALIGN=RIGHT NOWRAP> <tt>0145446470</tt> </TD></TR><TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> <tt>"trois"</tt> </TD><TD VALIGN=BASELINE ALIGN=RIGHT NOWRAP> <tt>016563565063</tt> </TD></TR><TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> <tt>"quatre"</tt> </TD><TD VALIGN=BASELINE ALIGN=RIGHT NOWRAP> <tt>010440656345</tt> </TD></TR><TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> <tt>"cinq"</tt> </TD><TD VALIGN=BASELINE ALIGN=RIGHT NOWRAP> <tt>0142505761</tt> </TD></TR><TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> <tt>"six"</tt> </TD><TD VALIGN=BASELINE ALIGN=RIGHT NOWRAP> <tt>01625070</tt> </TD></TR><TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> <tt>"sept"</tt> </TD><TD VALIGN=BASELINE ALIGN=RIGHT NOWRAP> <tt>0162446164</tt> </TD></TR><TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> <tt>"huit"</tt> </TD><TD VALIGN=BASELINE ALIGN=RIGHT NOWRAP> <tt>0151645064</tt> </TD></TR><TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> <tt>"neuf"</tt> </TD><TD VALIGN=BASELINE ALIGN=RIGHT NOWRAP> <tt>0157446446</tt> </TD></TR><TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> <tt>"dix"</tt> </TD><TD VALIGN=BASELINE ALIGN=RIGHT NOWRAP> <tt>01455070</tt> </TD></TR><TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> <tt>"onze"</tt> </TD><TD VALIGN=BASELINE ALIGN=RIGHT NOWRAP> <tt>0156577345</tt> </TD></TR><TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> <tt>"douze"</tt> </TD><TD VALIGN=BASELINE ALIGN=RIGHT NOWRAP> <tt>014556647345</tt> </TD></TR></TBODY></TABLE></P></DIV> <OL><LI> chained hash table,<LI> chained scatter table,<LI> open scatter table using <em>linear probing</em>,<LI> open scatter table using <em>quadratic probing</em>, and<LI> open scatter table using <em>double hashing</em>. (Use Equation <A HREF="page241.html#eqnhashingdouble"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> as the secondary hash function). </OL><LI> For each table obtained in Exercise <A HREF="page249.html#exercisehashingi"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>, show the result when the key <tt>"deux"</tt> is withdrawn.<LI> For each table considered in Exercise <A HREF="page249.html#exercisehashingi"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> derive an expression for the total memory space used to represent a table of size <I>M</I> that contains <I>n</I> items.<LI> Consider a chained hash table of size <I>M</I> that contains <I>n</I> items. The performance of the table decreases as the load factor <IMG WIDTH=64 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline62233" SRC="img935.gif" > increases. In order to keep the load factor below one, we propose to double the size of the array when <I>n</I>=<I>M</I>. However, in order to do so we must <em>rehash</em> all of the elements in the table. Explain why rehashing is necessary.<LI> Give the sequence of <I>M</I> keys that fills a <em>chained scatter table</em> of size <I>M</I> in the <em>shortest</em> possible time. Find a tight, asymptotic bound on the minimum running time taken to fill the table.<LI> Give the sequence of <I>M</I> keys that fills a <em>chained scatter table</em> of size <I>M</I> in the longest possible time. Find a tight, asymptotic bound on the minimum running time taken to fill the table.<LI> Consider the chained hash table introduced shown in Program <A HREF="page225.html#progchainedHashTablea"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>-Program <A HREF="page228.html#progchainedHashTablec"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>. <OL><LI> Rewrite the <tt>insert</tt> method so that it doubles the length of the array when <IMG WIDTH=37 HEIGHT=11 ALIGN=BOTTOM ALT="tex2html_wrap_inline62347" SRC="img969.gif" >.<LI> Rewrite the <tt>withdraw</tt> method so that it halves the length of the array when <IMG WIDTH=39 HEIGHT=29 ALIGN=MIDDLE ALT="tex2html_wrap_inline62723" SRC="img1031.gif" >.<LI> Show that the <em>average</em> time for both insert and withdraw operations is still <I>O</I>(1). </OL><LI> Consider two sets of integers, <IMG WIDTH=137 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline62727" SRC="img1032.gif" > and <IMG WIDTH=131 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline62729" SRC="img1033.gif" >. <OL><LI> Devise an algorithm that uses a hash table to test whether <I>S</I> is a subset of <I>T</I>. What is the average running time of your algorithm?<LI> Two sets are <em>equivalent</em> if and only if both <IMG WIDTH=42 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline62735" SRC="img1034.gif" > and <IMG WIDTH=43 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline62737" SRC="img1035.gif" >. Show that we can test if two sets of integers are equivalent in <I>O</I>(<I>m</I>+<I>n</I>) time (on average). </OL><LI> <A NAME="exercisehashingtree"> </A> (This question should be attempted <em>after</em> reading Chapter <A HREF="page298.html#chapsrchtree"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>). Rather than use an array of linked lists, suppose we implement a hash table with an array of <em>binary search trees</em>. <OL><LI> What are the worst-case running times for <tt>insert</tt>, <tt>find</tt>, and <tt>withdraw</tt>.<LI> What are the average running times for <tt>insert</tt>, <tt>find</tt>, and <tt>withdraw</tt>. </OL><LI> <A NAME="exercisehashingrandom"> </A> (This question should be attempted <em>after</em> reading Section <A HREF="page465.html#secalgsrng"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>). Consider a scatter table with open addressing. Devise a probe sequence of the form <P> <IMG WIDTH=351 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath62354" SRC="img980.gif" ><P> where <I>c</I>(<I>i</I>) is a <em>full-period pseudo random number generator</em>. Why is such a sequence likely to be better than either linear probing or quadratic probing?</OL><HR><A NAME="tex2html4065" HREF="page250.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html4063" HREF="page205.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html4057" HREF="page248.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html4067" 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 + =
减小字号Ctrl + -
显示快捷键?