PDA

View Full Version : Data Structure exam help



ExCoder01
10-23-2003, 10:57 AM
Here are a few questions I'm trying to figure out. I have an exam for my Data Structure class soon. These are selected sample exam questions which I'm having a little troubling figuring out. Can anyone help?

1a) Explain how to implement a stack using linked list or array?
How would I implement it using a linked list? Can someone explain this? I'm not looking for the code, but explaination. Example: what accessors/methods do I need? What private/public parts in a class do I need? The same goes for array?

1b) What is the cost of the stack operations in space(memory) and time(CPU) for this implementation?

1c) If I were to implement a binary tree using array or linked list, which would be more efficient? Advantages/disadvantages?

2) Given a in-fix expression: 8-7*(6-5/4)-3, how would I put it in pre-fix and post-fix expression?

3) Can someone explain to me why the average depth of a BST is O(log N)?

Thanks.

axon
10-23-2003, 11:26 AM
Have you ever considered opening your book? :D

All the data structures books I have looked at answer most of your questions. If the book is too intimidating, try google or search on this board. Then combac with whatever else you don't understand.