CS 311 Fall 2007  >  Final Exam Review Problems, Part 2

CS 311 Fall 2007
Final Exam Review Problems, Part 2

This is the second of four sets of review problems for the Final Exam. A complete review for the final includes the material of the Midterm Exam as well, which is covered in three problem sets posted earlier in the semester. For all seven sets, see the the class web page, or the following links:

Problems

Review problems are given below. Answers are in the Answers section of this document. Do not turn these in.

  1. What is almost certainly the order of the destructor for a generic container? Why?
     
    1. Compare & contrast Singly Linked Lists and Doubly Linked Lists, from the point of view of efficiency and order of operations.
    2. What does all this mean for the design of generic container types?

     
    1. What is a “Circular Linked List”?
    2. How do Circular Linked Lists complicate ownership and releasing of resources?

     
  4. List the three primary STL sequence types, and very briefly indicate how each is typically implemented.
     
    1. Briefly explain how an STL std::deque is generally implemented.
    2. What are the major advantages of a std::deque over other sequence types?
    3. The C++ standard says that insert at either end of a std::deque is “constant time”. However, by our standards this is not true. Explain.

     
    1. What is mean by iterator (and reference) “validity”?
    2. Briefly summarize the iterator validity rules for std::vector and std::list.

     
  7. “An iterator is often a wrapper around a pointer.”
    1. What does this statement mean?
    2. Why a “wrapper”, and not just a pointer?

     
  8. Suppose the following operations are performed, in the order given, beginning with an empty structure:
    1. push(2)
    2. push(1)
    3. getTop
    4. push(3)
    5. getTop
    6. pop
    7. push(4)
    8. getTop
    9. pop
    10. getTop
    11. pop
    12. getTop
    13. pop
    Answer the following questions:
    1. If these operations are performed on a Stack, what values are returned by the five getTop operations (give them in order)? Remember that getTop does not alter the Stack.
    2. Suppose we replace “push” with “enqueue”, “pop” with “dequeue”, and “getTop” with “getFront”. We perform the operations on a Queue. What values are returned by the five getFront operations (give them in order)?
    3. Do a similar replacement, and answer the same question for a Priority Queue. The priority of an item is given by its value, so that higher values come out first.

     
    1. List three applications of Stacks.
    2. List two applications of Queues.

     
  10. Suppose we implement a Queue (not using a circular buffer), based on each of the data structures below. For each, indicate the order of the three main queue operations (enqueue, dequeue, getFront).
    1. A Doubly Linked List.
    2. A smart array (front of the queue at the beginning of the array).
    3. std::deque.

     
    1. Explain the “circular buffer” method of implementing a queue.
    2. Suppose we have a circular buffer stored in a 10-element array (with indices 0..9). The first item in the buffer is at index 7. If later items are stored at increasing indices, where is the 5th item?

     
    1. What is meant by a “rooted tree”?
    2. Is there such a thing as an “unrooted tree”?

     
  13. A tree is shown below.
    Tree for rooted tree terminology questions
    The following questions concern the bold vertex. One of these questions is nonsensical.
    1. How many children does this vertex have?
    2. How many parents does this vertex have?
    3. How many descendants does this vertex have?
    4. How many ancestors does this vertex have?
    5. How many leaves does this vertex have?
    6. How many siblings does this vertex have?

     
    1. What is a “Binary Tree”?
    2. We can define this concept using a “recursive definition”. What does that mean?
    3. A Binary Tree is not a special kind of general tree. Explain.

     
    1. What is a “full Binary Tree”?
    2. What is a “complete Binary Tree”? Why are they important?
    3. What is a “balanced Binary Tree”? Why are they important?

     
    1. We covered three ways of implementing a Binary Tree. Briefly explain each.
    2. One of the methods from the previous part is only good for Binary Trees with certain properties. What ADTs/data structures is this method typically used as the basis of?

     
  17. A Binary Tree is shown below.
    Binary Tree for traversal questions
    1. Give a preorder traversal of this tree.
    2. Give an inorder traversal of this tree.
    3. Give a postorder traversal of this tree.
    4. This is not balanced Binary Search Tree. What two properties of a balanced Binary Search Tree does it not have?

     
    1. Why do Binary-Tree ADTs typically not have an operation that returns the tree’s size (that is, the number of nodes in it)?
    2. Suppose we want to determine the size of a Binary Tree from “outside”, that is, using only the ADT operations. How can we do this as efficiently as possible?

     
    1. Explain how to use a Binary Tree to implement an arbitrary (“general”) tree.
    2. Give advantages/disadvantages of representing a general tree as a Binary Tree.

     
    1. What is a “Binary Search Tree”?
    2. Which of the three standard traversals of a Binary Search Tree is most important? Why?

     

Answers

  1. The destructor of a generic container is almost certainly linear-time, because it must destroy each data item.
    1. Singly-linked lists cannot do efficient insert/remove at end, insert before a given node, remove a given node, or backwards iteration. (Note: Efficient insert at end is possible if removal only happens at the beginning. However, in that case, we really have a queue, not a list.) Doubly linked lists can do all these efficiently at the expense of a little more memory and time usage.
    2. Singly linked lists are generally not considered appropriate for generic containers in all-purpose languages like C++. Thus, linked-list-style containers (like the STL’s std::list) are implemented using a doubly linked list.
    1. A circular linked list is a data structure that is much like a linked list, except that the last node’s next-node pointer points to the first node. The “list” is thus arranged in a circle.
    2. The usual methods of resource releasing based on ownership and reference counting, do not work with a circular linked list. Suppose that each node owns the node pointed to by its next-node pointer. If the head of the list is destroyed, then the first node is still owned by the last node. In fact every node is still owned, and we have a resource leak. The usual solution to this is weak references, that is, non-owning pointers. In particular, the last node would not own the first node, even though it has a pointer to it.
    1. A std::deque is implemented as an array of pointers to arrays. Thinking of this as a giant list, we try to keep the data in the middle, so that we can efficiently insert at either end. When the master array fills up, we reallocate and copy, but we do not need to copy the data items themselves, only the array of pointers.
    2. A std::deque has amortized constant time insert/remove at both ends, as well as constant-time look-up by index. Neither std::vector nor std::list has both of these properties.
    3. In determining the order of operations, the C++ standard counts only value-type operations. Insert at either end of a deque is constant time when you count only value-type operations, and amortized constant time when you count all operations.
    1. Iterator validity refers to when iterators can be safely used (dereferenced, etc.). Reference validity is the same thing for pointers and references. Iterators, pointers, and references can become invalid when the internal workings of data structures are shuffled around (for example, reallocate-and-copy of a smart array).
    2. Essentially, a vector iterator remains valid as long as no item at or before the one it references is inserted or removed, no reallocate-and-copy happens, and the item itself is not destroyed. A list iterator remains valid until the item it references is destroyed. (Note that destroying a container destroys all the items in it.)
    1. An iterator class often has a single data member: a pointer to a data item or to a node. Iterators differ from pointers in the operations they allow, and how these operations are implemented.
    2. Sometimes we can use a pointer as an iterator. However, for node-based data structures, raw pointers are not appropriate, because the built-in operators do not do what we want them to. In particular, operator++ takes a pointer to the next spot in memory. We want it to take our iterator to the next item in our sequence, which may not be immediately after the current item in memory.
    1. 1, 3, 4, 1, 2.
    2. 2, 2, 1, 3, 4.
    3. 2, 3, 4, 2, 1.
    1. Here are four applications of Stacks:
      • Eliminating recursion.
      • Parsing expressions (or programs or ...).
      • Storing “state” in a program in which temporary state changes are made, which need to be undone later.
      • Executing a program (put return addresses and local variables on the Stack).
    2. Here are four applications of Queues:
      • Storing jobs waiting for an I/O device (e.g., a printer).
      • Storing user-input events for a GUI-based application.
      • Storing requests for a lock on shared data, in a multi-threaded application.
      • Doing a breadth-first search of a graph.
    1. Doubly linked list. enqueue: constant. dequeue: constant. getFront: constant.
    2. Smart array. enqueue: amortized constant. dequeue: linear. getFront: constant.
    3. std::deque. enqueue: amortized constant (constant, by Standard Library defintions). dequeue: constant. getFront: constant.
    1. In a circular buffer, we use an array, and we imagine the beginning and end being joined, so that it forms a circle. Then we can insert and delete at either end of the data without moving any items around, as long as the size of the queue does not exceed the size of the array.
    2. The 5th item is at index 1.
    1. A rooted tree is a tree in which a vertex is designated as the root. All other vertices hang from it, or from previously specified vertices (which hang from vertices, which hang from vertices ... and it all eventually gets back to the root).
    2. Yes, there are trees with no root and no parent-child relationships. However, they are much less important in the study of data structures, and we did not use them in this class.
    1. 3 children.
    2. 1 parent.
    3. 7 descendants.
    4. 2 ancestors.
    5. This is nonsense. A vertex does not have leaves.
    6. 1 sibling.
    1. A Binary Tree consists of a set T of nodes so that either:
      • T is empty (no nodes), or
      • T consists of a node r, the root, and two subtrees of r, each of which is a Binary Tree:
        • the left subtree, and
        • the right subtree.
    2. To define a term recursively is to write the definition in terms of itself. For example, the above is a recursive definition, since the term “Binary Tree” is used in the statement of the definition.
    3. A Binary Tree is not a general tree primarily because the order of its children matters. Note: Another difference, when we use the text’s definitions, is that a Binary Tree can be empty (have no nodes), while a general tree cannot. However, this is a minor point. In any case, many people use different definitions.
    1. A full Binary Tree is a Binary Tree in which every node either has two children or no children, and every leaf is at the same level. That is, every level is filled, up to the highest level.
    2. A complete Binary Tree is a Binary Tree in which every level except the highest is filled, and the highest level is full from the left side to somewhere in the middle (or the far right side). Complete Binary Trees are important because they have a nice array representation, since elements are always added in a specific order. A Heap is a special kind of complete Binary Tree.
    3. A balanced Binary Tree is a Binary Tree in which, for each node, the heights of its two subtrees differ by at most 1. Balanced Binary Trees are important because they allow for efficient algorithms (generally O(log n), when combined with the search-tree idea).
    1. Here are the three implementations:
      • Node/pointer-based. Each node in the tree is a separate block of memory. Nodes refer to their children (and maybe their parents) via pointers. The main data structure includes a pointer to the root node.
      • Nodes in an array. As above, but the nodes are stored in an array, and pointers are replaced by array indices.
      • Complete Binary Tree in an array. We can implement complete Binary Trees by putting their nodes into an array, in order by level, and then left-to-right within each level. We store the array of nodes and the number of nodes. Locations of children and parents are computed via simple formulae. No pointers of any sort (including array indices) need to be stored in the data structure.
    2. The array implementation of a complete Binary Tree is used to implement a Heap (Maxheap or Minheap), which is used to implement a Priority Queue (and also to do Heap Sort, etc.).
    1. Preorder: 1, 2, 4, 7, 5, 3, 6, 8.
    2. Inorder: 4, 7, 2, 5, 1, 3, 8, 6.
    3. Postorder: 7, 4, 5, 2, 8, 6, 3, 1.
    4. This is not a balanced Binary Search Tree, since:
      • It is not balanced. The two subtrees of the “3” node have heights 0 and 2, respectively, and these differ by more than 1.
      • While it is a Binary Tree, it is not a Binary Search Tree. An inorder traversal (see above) does not give the items in sorted order.
    1. Most Binary-Tree ADTs will include an operation to delete a subtree (the one we looked at in class did). This operation changes the size of the tree by an amount that is difficult to determine efficiently. Thus, we cannot efficiently keep track of a tree’s size, nor can we determine it in less than linear time. Since we cannot implement a size operation efficiently, we often do not include such an operation. Note: This is similar to the reason a linked list might not have a size operation if it can do splicing.
    2. Here are two methods.
      • We traverse the tree. We have a counter variable that is initialized to zero and incremented each time we visit a node. After the traversal, the counter holds the size of the tree.
      • We use recursion. The size of a tree is zero if it is empty (base case). Otherwise, it is the size of the root’s left subtree plus the size of the root’s right subtree plus one (for the root). The sizes of the two subtrees are computed recursively.
    1. We represent a general tree using a Binary Tree by giving the left & right child pointers special meanings. The left-child pointer points to a node’s first child in the general tree. The right-child pointer points to a node’s next sibling in the general tree.
    2. Representing a general tree as a Binary Tree is very simple and avoids the data structures that may be required to hold pointers to an arbitrary number of children. Further, it is no less efficient than any other implementation for things like tree traversals. However, if random access to large numbers of children is required, this method is poor, since it requires linear time (in the number of children) to access a child pointer. Also, some trees with a fixed limit on the number of children (quadtrees, etc.) need very fast access to child pointers, making this possibly an inappropriate implementation in those situations as well.
    1. A Binary Search Tree is a Binary Tree in which, for each node, the items in its left subtree are all less than its item, and the items in its right subtree are all greater than its item. Note: Sometimes we substitute “less than or equal to” and “greater than or equal to”. We do this in order to allow multiple equivalent items in the tree.
    2. The inorder traversal is by far the most important, since it gives the items in sorted order.

CS 311 Fall 2007: Final Exam Review Problems, Part 2 / Updated: 12 Dec 2007 / Glenn G. Chappell / ffggc@uaf.edu Valid HTML 4.01!