Problem Set 3

  1. Given a complete binary tree, what is the index of the node, (8 pts)

    a. found by taking the path: root -> right child -> left child -> right child?

    b. that is the parent of the parent of the node at index 15?

  2. In what order would the nodes in the tree depicted below be traversed, (9 pts)

    a. in a pre-order traversal?

    b. in a in-order traversal?

    c. in a post-order traversal?

  3. What is the average number of table elements examined in a table with capacity 950 and 727 elements, (9 pts)

    a. with linear probing?

    b. with double hashing?

    c. with chained hashing?

3_tree.png

Org version 7.7 with Emacs version 23

Validate XHTML 1.0