CSC3171 Quiz 2

Fall 2011
Herbert J. Bernstein ( )

CSC3171 Quiz 2
Fall 2011

 		 

This web page is http://www.bernstein-plus-sons.com/.dowling/CSC3171F11/CSC3171_Quiz_2.html
Copyright © 2007, 2011 Herbert J. Bernstein and other parties. All rights reserved.

This is the second weekly quiz to be taken on of before Thursday, 15 September 2011. You should do it after you read the first half of Chapter Two of Knuth's Fundamental Algorithms. You should expect to spend 30 minutes to 2 hours on this quiz. You may use your text and any other resources to do this quiz, but if you do not know the answers well or are unable to discuss them in class, you will lose credit for the quiz.

  <==== Do this AFTER you've answered all the questions

You probably DON'T want to do this ===>  

Please fill in the following information:

Name:


Email:

Please answer the following questions on this form (or on a paper copy of this form).

  1. Briefly, define a stack and list the operations to be supported (be careful to only list operations appropriate to a stack)

  2. Briefly, define a queue and list the operations to be supported (be careful to only list operations appropriate to a queue)

  3. Briefly, define a dequeue and list the operations to be supported (be careful to only list operations appropriate to a dequeue)

  4. Briefly explain the design decisions in sequential allocation of memory for lists.

  5. Briefly explain the design decisions in linked allocation for lists.

  6. Explain what a topological sort does.

  7. What is a circular list and what is it useful for?

  8. Explain in detail the process of deletion from a doubly linked list.

  9. Explain the design decisions in doing a pivot step on a sparse matrix.

  10. Briefly explain how to represent a balanced binary tree using one-way pointers from each parent to its two children

  11. Briefly explain how to represent a balanced binary tree as an array

  12. Briefly compare the time and space requirements for tree traversal using these two representations.

  <==== Do this AFTER you've answered all the questions

You probably DON'T want to do this ===>  

Revised 13 August 2011