📄 page166.html
字号:
<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="tex2html3111" HREF="page167.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html3109" HREF="page130.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html3103" HREF="page165.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html3113" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H1><A NAME="SECTION006400000000000000000">Exercises</A></H1><P><OL><LI> <A NAME="eqnstacksdouble"> </A> The array-based stack implementation introduced in Program <A HREF="page132.html#progstackAsArraya"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> uses a fixed length array. As a result, it is possible for the stack to become full. <OL><LI> Rewrite the <tt>push</tt> method so that it doubles the length of the array when the array is full.<LI> Rewrite the <tt>pop</tt> method so that it halves the length of the array when the array is less than half full.<LI> Show that the <em>average</em> time for both push and pop operations is <I>O</I>(1). <b>Hint</b>: Consider the running time required to push <IMG WIDTH=45 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline58245" SRC="img168.gif" > items onto an empty stack, where <IMG WIDTH=37 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline60883" SRC="img708.gif" >. </OL><LI> Consider a sequence <I>S</I> of push and pop operations performed on a stack that is initially empty. The sequence <I>S</I> is a valid sequence of operations if at no point is a pop operation attempted on an empty stack and if the stack is empty at the end of the sequence. Design a set of rules for generating a valid sequence.<LI> Devise an implementation of the <em>queue</em> abstract data type <em>using two stacks</em>. Give algorithms for the <tt>enqueue</tt> and <tt>dequeue</tt> operations, and derive tight big-oh expressions for the running times of your implementation.<LI> Write each of the following <em>infix</em> expressions in <em>postfix</em> notation: <OL><LI> <IMG WIDTH=90 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline60889" SRC="img709.gif" >,<LI> <IMG WIDTH=100 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline60891" SRC="img710.gif" >,<LI> <IMG WIDTH=101 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline60893" SRC="img711.gif" >,<LI> <IMG WIDTH=111 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline60895" SRC="img712.gif" >,<LI> <IMG WIDTH=101 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline60897" SRC="img713.gif" >, and<LI> <IMG WIDTH=111 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline60899" SRC="img714.gif" >. </OL><LI> Write each of the following <em>postfix</em> expressions in <em>infix</em> notation: <OL><LI> <IMG WIDTH=90 HEIGHT=20 ALIGN=MIDDLE ALT="tex2html_wrap_inline60901" SRC="img715.gif" >,<LI> <IMG WIDTH=89 HEIGHT=20 ALIGN=MIDDLE ALT="tex2html_wrap_inline60903" SRC="img716.gif" >,<LI> <IMG WIDTH=89 HEIGHT=20 ALIGN=MIDDLE ALT="tex2html_wrap_inline60905" SRC="img717.gif" >,<LI> <IMG WIDTH=89 HEIGHT=20 ALIGN=MIDDLE ALT="tex2html_wrap_inline60907" SRC="img718.gif" >,<LI> <IMG WIDTH=89 HEIGHT=20 ALIGN=MIDDLE ALT="tex2html_wrap_inline60909" SRC="img719.gif" >, and<LI> <IMG WIDTH=89 HEIGHT=20 ALIGN=MIDDLE ALT="tex2html_wrap_inline60911" SRC="img720.gif" >. </OL><LI> <A NAME="exercisestacksreverse"> </A> Devise an algorithm which translates a <em>postfix</em> expression to a <em>prefix</em> expression. <b>Hint</b>: Use a stack of strings.<LI> The array-based queue implementation introduced in Program <A HREF="page148.html#progqueueAsArraya"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> uses a fixed length array. As a result, it is possible for the queue to become full. <OL><LI> Rewrite the <tt>enqueue</tt> method so that it doubles the length of the array when the array is full.<LI> Rewrite the <tt>dequeue</tt> method so that it halves the length of the array when the array is less than half full.<LI> Show that the <em>average</em> time for both enqueue and dequeue operations is <I>O</I>(1). </OL><LI> Stacks and queues can be viewed as special cases of deques. Show how all the operations on stacks and queues can be mapped to operations on a deque. Discuss the merits of using a deque to implement a stack or a queue.<LI> Suppose we add a new operation to the stack ADT called <tt>findMinimum</tt> that returns a reference to the smallest element in the stack. Show that it is possible to provide an implementation for <tt>findMinimum</tt> that has a worst case running time of <I>O</I>(1).<LI> <A NAME="exercisestacksreverse2"> </A> The <em>breadth-first traversal</em> method shown in Program <A HREF="page157.html#progalgorithmsa"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> visits the nodes of a tree in the order of their levels in the tree. Modify the algorithm so that the nodes are visited in reverse. <b>Hint</b>: Use a stack.</OL><HR><A NAME="tex2html3111" HREF="page167.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html3109" HREF="page130.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html3103" HREF="page165.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html3113" 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 + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -