page248.html

来自「wqeqwvrw rkjqhwrjwq jkhrjqwhrwq jkhrwq」· HTML 代码 · 共 142 行 · 第 1/2 页

	For each table obtained in Exercise&nbsp;<A HREF="page248.html#exercisehashingi" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page248.html#exercisehashingi"><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>,
	show the result when the key <tt>&quot;deux&quot;</tt> is withdrawn.<LI>
	For each table considered in Exercise&nbsp;<A HREF="page248.html#exercisehashingi" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page248.html#exercisehashingi"><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>
	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=63 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline62864" SRC="img984.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img984.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 implementation shown in
	Programs&nbsp;<A HREF="page224.html#proghashtbl2h" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page224.html#proghashtbl2h"><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>, <A HREF="page225.html#proghashtbl2c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page225.html#proghashtbl2c"><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>, <A HREF="page226.html#proghashtbl3c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page226.html#proghashtbl3c"><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&nbsp;<A HREF="page227.html#proghashtbl4c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page227.html#proghashtbl4c"><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><LI>
		Rewrite the <tt>Insert</tt> routine so that it doubles
		the length of the array when  <IMG WIDTH=37 HEIGHT=11 ALIGN=BOTTOM ALT="tex2html_wrap_inline62978" SRC="img1016.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1016.gif"  >.<LI>
		Rewrite the <tt>Withdraw</tt> routine so that it halves
		the length of the array when  <IMG WIDTH=39 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline63360" SRC="img1079.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1079.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=139 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline63364" SRC="img1080.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1080.gif"  >
	and  <IMG WIDTH=133 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline63366" SRC="img1081.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1081.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_inline63372" SRC="img1082.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1082.gif"  > and  <IMG WIDTH=43 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline63374" SRC="img1083.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1083.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">&#160;</A>
	(This question should be attempted
	<em>after</em> reading Chapter&nbsp;<A HREF="page299.html#chapsrchtree" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page299.html#chapsrchtree"><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>).
	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">&#160;</A>
	(This question should be attempted
	<em>after</em> reading Section&nbsp;<A HREF="page472.html#secalgsrng" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page472.html#secalgsrng"><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 scatter table with open addressing.
	Devise a probe sequence of the form
	<P> <IMG WIDTH=351 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath62985" SRC="img1027.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1027.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="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> <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 &#169; 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>