page248.html
来自「wqeqwvrw rkjqhwrjwq jkhrjqwhrwq jkhrwq」· HTML 代码 · 共 142 行 · 第 1/2 页
HTML
142 行
<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="tex2html4979" HREF="page249.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page249.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="tex2html4977" HREF="page203.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page203.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="tex2html4971" HREF="page247.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page247.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="tex2html4981" 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="tex2html4982" 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="SECTION009800000000000000000">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="page218.html#proghash3c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page218.html#proghash3c"><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 strings <tt>"ece.uw.ca"</tt> and <tt>"cs.uw.ca"</tt>.
<b>Hint</b>: Refer to Appendix <A HREF="page618.html#appcharcode" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page618.html#appcharcode"><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>
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.
E.g., 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="equation14577" SRC="img1078.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1078.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="page240.html#eqnhashingdouble" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page240.html#eqnhashingdouble"><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> as the secondary hash function).
</OL><LI>
⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?