tut3.html
来自「Data Structure Ebook」· HTML 代码 · 共 162 行
HTML
162 行
<HTML><HEAD>
<TITLE>Data Structures and Algorithms: Tutorial Problems 3</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 3</B></FONT>
</TD></TR>
</TABLE>
<HR>
<H3>Tutorial 3</H3>
<OL>
<LI VALUE=4><H3>B+-tree Design</H3>
You are constructing a database for the Tax Office of a
medium-sized Pacific nation.
The primary key for records is a 9-digit tax file number.
(This Tax Office is so pre-occupied with
a new tax scheme that their Prime Minister is touting as
the answer to all their economic woes, that it hasn't learnt
about binary representations for numbers yet and still uses
one byte per decimal digit. They get <I>really</I> uptight
when anyone mentions the year 2000 problem!)
<P>
The records for this database will be stored on discs which have
an average access time of 2.5ms to read a block of 4Kbytes.
Each disc uses a 32-bit integer to address blocks within the disc.
The database spreads over multiple discs, so a 16-bit disc
identifier has to be added to each block address.
It takes 150ns to read a word from the computer's main memory.
<P>
The population is 17x10<SUP>6</SUP> taxpayers and 0.78 x 10<SUP>3</SUP>
politicians (1.8x10<SUP>3</SUP> millionaires have never needed to
submit a tax return.). There are also records for 1.2 x 10<SUP>6</SUP>
foreign residents who pay some tax and 2.8x10<SUP>6</SUP> companies,
trusts and other tax avoidance structures.
<OL TYPE=a>
<LI>How much space will you use to store the indices for this
database?
Work out the minimum and maximum values for the space -
in either disc blocks or bytes.
(Don't worry about the poor taxpayers' records, which
are humungous as they include details such as the cost of
the beer consumed by every travelling salesman in every bar in the
country - in order to calculate FBT.)
<LI>How long will it take to find a taxpayer's record?
<LI>How much disc space has been wasted in the indices?
<LI>Many compilers align fields on to word boundaries for efficiency.
For example, a 9-byte field is padded out to 12-bytes (the next multiple
of the 4-byte word length) so that the next field lies on a word boundary.
Would this be a good thing to do in this case?
Would it be worth going to some effort to prevent the compiler from
padding out short (<4byte) fields?
</OL>
<P>
<LI><H3>Stable Sorting</H3>
A stable sorting algorithm is one which leaves equal keys in the
same order as they appeared in the original collection.
Work out which of the algorithms that you have studied so far
will produce stable sorts.
<P>
<LI><H3>A Numerical Puzzle</H3>
You are given an array containing <B><I>n</I></B> integers.
You are asked to determine if the list contains two numbers
that sum to some arbitrary integer, <B><I>k</I></B>.
For example, if the list is <B>8, 4, 1 </B>and <B>6</B> and
<B><I>k</I> = 10</B>, the answer is "yes", because
<B>4+6 = 10</B>.
<OL TYPE=a>
<LI>Find a way to solve this problem that is <B><I>O(n</I><SUP>2</SUP><I>)</I></B>.
<LI>Can you do better?
What is the time complexity of the better method?
</OL>
<I>Hint:</I> Consider sorting the array first.
<P>
<LI><H3>Dynamically Balanced Trees</H3>
Show that any AVL tree can be coloured as a red-black tree.
<P>
<LI><H3>Dynamic Memory Allocation</H3>
Modern object-oriented software makes extensive use
of the <TT>malloc</TT> and <TT>free</TT> operations.
Unfortunately, they are generally quite expensive (in time) and
thus efficient routines are important.
<P>
<TT>free</TT> places freed blocks into <B>free lists</B>.
In order to re-use memory as much as possible, <TT>malloc</TT> will
generally search the free lists for a block before requesting another
one from the operating system (a very expensive exercise!).
A <B>best-fit</B> algorithm searches for the smallest free block
into which the requested block will fit.
<P>
Suggest a number of ways in which <TT>free</TT> could organise the
free lists and give the time complexities for
<OL TYPE=a><LI> <TT>free</TT> to add a block to the free lists
<LI> <TT>malloc</TT> to find a "best-fit" block from these lists.
</OL>
Describe any drawbacks that any method might have.
<P>
<LI><H3>Equivalence Classes</H3>
You are required to test some sorting routines:
<OL Type="a">
<LI>an insertion sort,
<LI>a heap sort <I>and</I>
<LI>a quick sort.
</OL>
<P>
<OL TYPE="i">
<LI>Propose a simple specification for a general purpose
sorting function.
<LI>Using the specification,
derive a set of tests that you would perform to verify
the function.
<LI>Would your knowledge of the algorithms used by
each sorting method cause you to extend the test set?
</OL>
For the purpose of drawing up examples,
use records whose keys are integers.
<HR>
</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="tut4.html" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/Tutorials/tut4.html">Tutorials: Part 4</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 + -
显示快捷键?