[Year 12 SofDev] Sample Exam Questions

Sun May 1 17:47:56 EST 2011

Hi Mike,

Sorry about the wording when I suggested the initial stack was in a full
state. What I meant was it was not possible to infer that the initial stack
represents the "capacity" of the stack data structure. 

Perhaps the question could have been worded:

Consider the following stack displaying the maximum capacity of the stack
data structure. And a stack drawn with 5 totally different values 

Further help would have been to state the initial top of stack pointer was
set to 1 rather than have a box labelled TOP with a separate stack drawn
with only 2 elements in it. 

Actually, apart from stimulating discussion about stack implementations, as
an interesting aside, doesn't it bring  into sharp focus the difficulties in
the different numbering of data structure elements in the traditional C like
languages from 0 to the more modern VB family which use 1 as the starting
element ?? 

Sure the pointer is the key to the TOS value but again in every encounter
with stacks in my university days I never saw stacks with popped elements
that did not display the stack with the element removed. It only adds to the
confusion to show a stack with all elements in place but only with the TOS
value to guide you to the actual Top of Stack position. A detail perhaps,
but more confusion.

Your insight has been very useful Mike but it is clearly from the point of
view of an examiner.  I guess Mark and I have been trying to make sense of
it as a student who may not have the capacity to infer what makes a trivial
and what makes a non trivial component in the question.  

How many people would expect a Stack Full outcome as inevitable in some part
of the answer , just because it was mentioned in the question ?? Should
students connect these clues and try to make the answer fit the question
without any evidence that these assumptions are valid ? 

A very useful discussion Mike. Thanks for your input and insight.

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 Mike Brookes
Sent: Sunday, 1 May 2011 4:56 PM
To: Year 12 Software Development Teachers' Mailing List
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

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.edulists.com.au/pipermail/sofdev/attachments/20110501/4923daa4/attachment-0001.html 