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.

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.