Topical Information

The purpose of this quiz is to give you a chance to focus your knowledge of simple tree data structures in C++.

Quiz Information

Questions

1. A tree data structure has a root, branches, and leaves — just like in the real world. But the data structure also has nodes and is represented upside down from their real-world cousins.

   Such a structure also uses lingo from our inheritance days with terms like _____ and _____.

   1. dowry, shares NO
   2. virtual, override NO
   3. abstract, concrete NO
   4. parent, child YES
   5. "is-a", "has-a" NO

2. The invariant (property that is the same for EVERY node) for a binary search tree is:

   1. all items left are blue, all items right are green NO
   2. all items left are negative, all items right are positive NO
   3. all items left are more important, all items right are less important OKAY
   4. all items left are less than, all items right are more than YES
   5. all items left are circles, all items right are squares NO

3. The invariant (property that is the same for EVERY node) for a heap is:

   1. all items below are red NO
   2. all items less than YES (max heap)
   3. all items below are greater than YES (min heap)
   4. all items below are squares NO
   5. all items below are opaque NO

4. Show recursive code for an in-order traversal of a binary tree. Make it a template with a function parameter to act on each node.

   
       template <typename TreeT, typename FuncF>
       void in_order(TreeT & pN, FuncF & f)
       {
           if (notNull(pN))
           {
               in_order(pN->Left(), f);
               f(pN->Data());
               in_order(pN->Right(), f);
           }
           return;
       }
   
   

5. Given the following tree data structure:

   
                  H
                  |
           +------+------+
           |             |
           V             D
           |             |
        +--+          +--+--+
        |             |     |
        Y             F     B
   
   

   Label each of the following as an IN-order traversal, a PRE-order traversal, a POST-order traversal, or NOT one of these standard traversal patterns.

   1. Y V H F D B IN
   2. F D H V Y B NOT
   3. Y V F B D H POST
   4. H V Y D F B PRE
   5. B Y F D V H NOT

6. Traversing a binary search tree in order will process the data involved in sorted order.

7. Although not quite as simple, a heap data structure can also be used to effect a sorting technique on the contained data.

8.  

   TRUE ✓		FALSE ✗		An expression tree is a way to represent a mathematical expression in tree form.
   TRUE ✓		FALSE ✗		The relative levels of operators tell the precedence of them in the expression's evaluation.
   TRUE ✗		FALSE ✓		Lower operators are evaluated later than higher operators.

9. Evaluation of an expression tree can be effected with a simple post-order traversal of the tree. Or we could transform the expression into post-fix order with a similar traversal and evaluate that instead. Such an evaluation would require a helper stack to accomplish.