tut4.html
来自「Data Structure Ebook」· HTML 代码 · 共 121 行
HTML
121 行
<HTML><HEAD>
<TITLE>Data Structures and Algorithms: Tutorial Problems 4</TITLE>
<META name="description" content="Data Structures and Algorithms Course Notes,
PLDS210 University of Western Australia">
<META name="keywords" content="data structures,algorithms,abstract data types ">
</HEAD>
<BODY BGCOLOR="#ffffff">
<TABLE BGCOLOR="#00c0f0" WIDTH="100%" CELLSPACING=0 CELLPADDING=0>
<TR BGCOLOR="#00f0f0"><TD ALIGN=right>
<FONT FACE=helvetica SIZE=+1><I>Data Structures and Algorithms</I></FONT>
</TD></TR>
<TR><TD><FONT FACE=helvetica SIZE=+2><B>Tutorial Problems: Part 4</B></FONT>
</TD></TR>
</TABLE>
<HR>
<H3>Tutorial 4</H3>
<H4>Heap Sort</H4>
<OL>
<LI>What would be the
<OL TYPE=a><LI>minimum,
<LI>maximum
</OL>
number of elements in a heap of height <B><I>h</I></B>?
<LI>Where in a heap would I find the smallest element?
<LI>Is an array that is sorted in reverse order a heap?
<LI>Is { 23, 17, 14, 6, 13, 10, 1, 5, 7, 12 } a heap?
<LI>Convert the <TT>Heapify</TT> function to an iterative form.
<LI>How could I make a FIFO queue with a heap? Is this likely to be a practical thing to do?
<LI>I have <B><I>k</I></B> sorted lists containing a total of <B><I>n</I></B>
elements. Give an <B><I>O(n</I>log<I>k)</I></B> algorithm to merge these lists into a
single sorted list.<BR>
<I>Hint:</I> Use a heap for the merge.
<LI>A <B><I>d</I></B>-ary heap has <B><I>d</I></B> children for each node. (An
ordinary heap is a binary heap.) Show how to store a <B><I>d</I></B>-ary heap in an
array.
</OL>
<H4>Quick Sort</H4>
<OL>
<LI>What is the <B>space complexity</B> of the "standard" recursive quicksort?<BR>
<I>Hint:</I> Consider the stack frames used.
<LI>Convert a recursive quicksort to an iterative one.
<LI>Suggest a simple strategy that can be used to turn <B>any</B> sort into a stable sort.</OL>
<H4>Radix Sort</H4>
<B>In-place</B> sorting algorithms do not require any more space than that occupied by
the records themselves.
<OL>
<LI>I wish to sort a collection of items whose keys can only take the values <B>0</B> or <B>1</B>.
Devise an <B><I>O(n)</I></B> algorithm for sorting these items in place.
You may use auxillary storage of constant (<B><I>O(</I>n<I>)</I></B>) size.
<LI>Can this approach be used to sort <B><I>n</I></B> records with
<B><I>b</I></B>-bit keys in <B><I>O(bn)</I></B> time? Explain your answer.
</OL>
<H4>A sort?</H4>
An integer array of <B><I>n</I></B> elements has a <B><I>majority element</I></B>
if there is an element that occurs more than <B><I>n</I>/2</B> times in the array.
For example, the array:
<CENTER><PRE>[ 2,2,5,1,5,5,2,5,5 ]
</PRE></CENTER>
has a majority element, but the array
<CENTER><PRE>[ 2,2,5,1,5,5,1,5 ]
</PRE></CENTER>
does not have a majority element.
Design an alghorithm to determine whether or not an
array contains a majority element and to return that element if it
exists.
<H4>Hash Tables</H4>
<OL>
<LI>Collisions in linked lists
<OL TYPE=a><LI>What is the worst case performance of a hash table in which collisions
are stored in linked lists attached to the primary table?
<LI>Could I improve this by keeping the items in the linked lists in sorted order?
<LI>Could I use any other auxillary structure to improve the worst case performance?
</OL>
<LI>I have a linked list of items with very long keys, <B><I>k</I></B>.
The hash value of each key, <B><I>h(k)</I></B> is stored with each item.
How might I make use of the hash value to speed up a search?
Will this strategy work with a search tree?
If yes, under what conditions?
</OL>
<H4>Search Trees</H4>
<OL>
<LI>How many binary search trees can I make from the list A B C D E?
<LI>When inserting a new node into a red-black tree, we set its colour to red. We could
have set its colour to be black without violating the
"if a node is red, its children are black" property. Why was it set to red?
</OL>
<P>
<TABLE WIDTH="100%" BGCOLOR="#00c0f0">
<TR><TD><H3>Key terms</H3></TD></TR></TABLE>
<DL>
<DT><FONT COLOR="#fa0000"><B>stable sort</B></FONT>
<DD>A <B></B>In a stable sort, the order of equal keys
in the original is retained in the output.
</DL>
<P>
<TABLE CELLPADDING=5 WIDTH="100%" BGCOLOR="#00f0f0" CELLSPACING=4>
<TR><TD WIDTH=50%>
Continue on to <A HREF="tut5.html" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/Tutorials/tut5.html">Tutorials: Part 5</A></TD>
<TD>Back to the <A HREF="ds_ToC.html" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/ds_ToC.html">Table of Contents</A>
</TD></TR></TABLE>
<SMALL>
© <A HREF=mailto:morris@ee.uwa.edu.au>John Morris</A>, 1998
</SMALL>
</BODY>
</HTML>
⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?