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.