[Year 12 SofDev] Sample Exam Questions

Robert Hind robert at yinnar.com
Sun May 1 17:57:31 EST 2011


Hi all!

I have never taught SD. Stopped with CS way back. This has sent me way back to old texts - 70s and 80s

How about we ignore the bold entries in the original question and read it to mean that the stack is

92
75
23
83
52

and the Top-of-stack pointer = 1, ie the value 52.

This is what the question seems to say.

We then proceed through the steps as given in the question

Start    Push (23)    Push (18)    Pop    Push (75)    Push (92) Push (47)

92            92               92            92          92            92            *47
75            75               75            75          75            *92            92
23            23               *18           18         *75            75             75    
83            *23               23           *23         23             23            23
*52            52               52            52         52             52            52

Where * indicates the top-of-stack pointer

So where is the problem? Except perhaps in the way the question has been written.

Robert Hind (Semi-retired) OOF, GOM
Ashwood and Traralgon
robert at yinnar.com


  ----- Original Message ----- 
  From: Mike Brookes 
  To: Year 12 Software Development Teachers' Mailing List 
  Sent: Sunday, May 01, 2011 4:56 PM
  Subject: Re: [Year 12 SofDev] Sample Exam Questions


  G'Day again

  Whilst 'tis true that this question on the end of year exam would unduly stress the little dears, to play devil's advocate, it does have a useful function as a sample to provoke discussion about what assumptions must be made. i.e. for the question to have a non trivial answer, what assumptions are necessary? 

  Firstly the memory locations used for the stack do not have to be initialised to 0 or any other value when the stack is created. The pointer is the only thing that must be initialised.

  If you assume the stack starts at 1 instead of 0, then the stack will not be full after step 6 reducing the value of the question.

  I also assumed that the bottom two values were in bold for a purpose, the most obvious (at least to me) being that they were valid existing members of the stack. 
  At the start of the question the stack is not full, the TOS pointer is 1, the stack would be full when it reaches 4, so the non-bold values were from previous uses of the stack. NB. a pop does not delete the value from the stack, it just changes the TOS pointer.

  It may well be that a different set of assumptions will produce a meaningful answer, these were the first consistent set I thought of.

  If you assume an empty stack at the start then, given that the pointer is 1 at the start of the question, the TOS pointer must point to the next available location (closer to convention) and the numbering must start at 1 instead of 0.  In this case the stack is not full after step 6 so another push step would be needed in the question.



       
       
       
       
       
       
       
       
       
       
       
       
       
       

       
       
       
       
       
       
       Stack at start and after each step
       
        Step
       Function
       Top
       Output
       
       
       
       Start
       Step 1
       Step 2
       Step 3
       Step 4
       Step 5
       Step 6
       
        1
       Push (23)
       2
       Item added (23)
       
       Stack position
       5
       92
       92
       92
       92
       92
       92
       92
       
        2
       Push (18)
        3
       Item added (18)
       
       4
       75
       75
       18
       18
       75
       75
       47
       
        3
       Pop
       2
       Item removed (18)
       
       3
       23
       23
       23
       23
       23
       92
       92
       
        4
       Push (75)
        3
       Item added (75)
       
       2
       83
       83
       18
       18
       75
       75
       75
       
        5
       Push (92)
       4
       Item added (92)
       
       1
       52
       23
       23
       23
       23
       23
       23
       
        6
       Push (47)
       5 

       Item added (47)

       
       
       
       
       
       
       
       
       
       
       

       
       
       
       
       
       Top
       1
       2
       3
       2
       3
       4
       5
       

  One would hope that a "real" question would at least have numbered the stack positions and provided a key to explain what the bold signified. A question to sort sheep from goats????????????

  Mike

  1

  On 1/05/2011 12:12 AM, Kevork Krozian wrote: 
    Hi Mark and Mike,


      I am a little late on the scene but have to support Mark here.

    The question on stacks is more a puzzle than a reasonable problem for a student to solve in limited time.

    The question begins with a picture of a stack to consider....... which suggests the starting position of the problem. Apparently it is in a full state .... and that can be determined from ?????

    Then, a push (23) is introduced. Hang on, I thought we had a stack to consider with 5 elements. Are we adding another 23 or picking up half way through the introduced stack ? 

    Where is it suggested that the introduced stack is in a "stack full" state ? 

    The push and pop operations are not the problem, just the starting position of the problem. When is the beginning is what got me first.  The bold items were no help as I didn't consider them to be significant.

    Also, the item Top (1) might mean top of stack to the writer, but only adds to the confusion as it is not obvious it means the top of the stack when we start with a stack with 5 elements. 


    I have gone through my 2nd year Data Structures textbooks and have a strong recollection of the 1982 exams I did ( why wouldn't I ?? ) on stacks and data structures and there was always a pointer or arrow (with a value in a variable ) showing the top of a stack at the beginning of a question and the requirement was to draw the stack through the various states after push and pop functions. Apart from that we either have empty or full states. 


    I can't see how  this question would have helped in any way to show student's understanding of a stack and its functions.


    Kind Regards


    Kevork Krozian

    Edulists Creator Administrator

    www.edulists.com.au

    tel: 0419 356 034


    From: sofdev-bounces at edulists.com.au [mailto:sofdev-bounces at edulists.com.au] On Behalf Of Mark KELLY
    Sent: Wednesday, 27 April 2011 2:36 PM
    To: Year 12 Software Development Teachers' Mailing List
    Subject: Re: [Year 12 SofDev] Sample Exam Questions


    Thanks for the bone, Mike.  Woof!  It finally let me work out the many assumptions underlying the question: and after all that, I'm not wagging my tail.

    I think the question is far from clear, and I doubt students would make much of it in a real exam.
     
    - It does not, for example, say that the stack is zero-based.  If one assumes (as I did) that the stack indexing starts at 1, the whole thing changes and nothing makes sense.
    - It does not indicate what the mysterious bolding of the bottom 2 items is meant to represent.  If the examiners invent their own conventions, they should explain them to us.
    - It does not tell us that the stack pointer in updated before a push/pop instead of being changed afterwards, as often happens.  Again, this changes everything.
    - One has to realise that the stack is expanding from the bottom and not from the top. Stacks are often represented growing in either direction.

    When it comes to real-world stack implementation, there are so many different options such as these that I found the question mind-boggling while I went through the permutations of possible readings.

    Grrr.

    On 21 April 2011 14:45, Mike Brookes <mikebr at tpg.com.au> wrote:

    Hi Mark et Al

    For the question to make sense one has to make the assumption that the stack positions start at the bottom with position zero and go up to position 4 which is the top of the stack. At the start the bottom two (in bold on the PDF) are valid, hence the top of stack pointer showing 1. 

    Below is the completed table and the stack at the start and after each step:


         
         
         
         
         
         
         
         
         
         
         
         
         
         

         
         
         
         
         
         
         Stack at start and after each step
         
          Step
         Function
         Top
         Output
         
         
         
         Start
         Step 1
         Step 2
         Step 3
         Step 4
         Step 5
         Step 6
         
          1
         Push (23)
         2
         Item added (23)
         
         Stack position
         4
         92
         92
         92
         92
         92
         92
         92
         
          2
         Push (18)
         
         Item added (18)
         
         3
         75
         75
         18
         18
         75
         75
         75
         
          3
         Pop
         2
         Item removed (18)
         
         2
         23
         23
         23
         23
         23
         23
         23
         
          4
         Push (75)
         
         Item added (75)
         
         1
         83
         83
         83
         83
         83
         83
         83
         
          5
         Push (92)
         4
         Item added (92)
         
         0
         52
         52
         52
         52
         52
         52
         52
         
          6
         Push (47)
         
         Stack full
         
         
         
         
         
         
         
         
         
         
         

         
         
         
         
         
         Top
         1
         2
         3
         2
         3
         4
         4
         


    Mike Brookes 
    Semi retired gentleman from Copperfield College



    On 21/04/2011 1:35 PM, Mark KELLY wrote: 

    Would someone be kind enough to throw me a bone about the stack question - Q3?

    I thought I knew stack implementation from my assembly language days with Z80... this question feels like walking into someone's half-finished thought process.  I'm really confused about this.After half an hour of conjecture, I've tried four times to ask a series of sensible questions to make sense of it, and have failed every time. 


    The only apparent answer involves time travel, reversed arrays, irrelevant stack pointers and bogus bolding of stack items.  The relationship between the stack and the table is only the beginning of the problem...


    I'd be delighted if anyone could walk me through this...


    Regards

    Mark




    _______________________________________________
    http://www.edulists.com.au - FAQ, Subscribe, Unsubscribe
    IT Software Development Mailing List kindly supported by
    http://www.vcaa.vic.edu.au - Victorian Curriculum and Assessment Authority and
    http://www.vcaa.vic.edu.au/vce/studies/infotech/softwaredevel3-4.html
    http://www.vitta.org.au  - VITTA Victorian Information Technology Teachers Association Inc




    -- 
    Mark Kelly
    Manager of ICT, Reporting, IT Learning Area
    McKinnon Secondary College
    McKinnon Rd McKinnon 3204, Victoria, Australia
    Direct line / Voicemail: +613 8520 9085, Fax +613 9578 9253
    kel at mckinnonsc.vic.edu.au
    VCE IT Lecture Notes: http://vceit.com
    Moderator: IT Applications Edulist

    All generalisations are false, except this one.


_______________________________________________
http://www.edulists.com.au - FAQ, Subscribe, Unsubscribe
IT Software Development Mailing List kindly supported by
http://www.vcaa.vic.edu.au - Victorian Curriculum and Assessment Authority and
http://www.vcaa.vic.edu.au/vce/studies/infotech/softwaredevel3-4.html 
http://www.vitta.org.au  - VITTA Victorian Information Technology Teachers Association Inc



------------------------------------------------------------------------------


  _______________________________________________
  http://www.edulists.com.au - FAQ, Subscribe, Unsubscribe
  IT Software Development Mailing List kindly supported by
  http://www.vcaa.vic.edu.au - Victorian Curriculum and Assessment Authority and
  http://www.vcaa.vic.edu.au/vce/studies/infotech/softwaredevel3-4.html 
  http://www.vitta.org.au  - VITTA Victorian Information Technology Teachers Association Inc


--------------------------------------------------------------------------------


_______________________________________________
http://www.edulists.com.au - FAQ, Subscribe, Unsubscribe
IT Software Development Mailing List kindly supported by
http://www.vcaa.vic.edu.au - Victorian Curriculum and Assessment Authority and
http://www.vcaa.vic.edu.au/vce/studies/infotech/softwaredevel3-4.html 
http://www.vitta.org.au  - VITTA Victorian Information Technology Teachers Association Inc
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.edulists.com.au/pipermail/sofdev/attachments/20110501/011186b0/attachment-0001.html 


More information about the sofdev mailing list