Sample Data Structures Questions

Sample Data Structures Questions
Chapter 9
Trees

Data Structures and Other Objects Using Java (Third Edition)
by Michael Main
ISBN 0-321-37525-4

The Purpose of These Questions

These are typical exam questions from Chapter 9 of the textbook. These exact questions might not be on your exam, but if you research and find the right answers to these questions, that should be good preparation for a real exam. (It's also possible that some of this material was not covered in your class.) At the moment there are 23 short answer questions and 19 multiple choice questions in this file.

Short Answers

Short Answers
Section 9.1
Introduction
to Trees

Here is a small binary tree:
```
       14
      /  \
     2    11
    / \   / \
   1  3  10  30
         /  /            
        7  40
```
Circle all the leaves. Put a square box around the root. Draw a star around each ancestor of the node that contains 10. Put a big X through every descendant of the node the contains 10.
Draw a full binary tree with at least 6 nodes.

Short Answers
Section 9.2
Tree
Representations
Draw a complete binary tree with exactly six nodes. Put a different value in each node. Then draw an array with six components and show where each of the six node values would be placed in the array (using the usual array representation of a complete binary tree).
Write the instance variables for a new class that could be used for a node in a tree where: (1) Each node contains int data, (2) Each node has up to four children, and (3) Each node also has a reference to its parent. Store the references to the children in an array of four components.

Short Answers
Section 9.3
A Toolkit for
Binary Tree Nodes
Draw a binary taxonomy tree that can be used for these four animals: Rabbit, Horse, Whale, Snake.

Using the BTNode class from Chapter 9, write a new static method of the BTNode class to meet the following specification. No recursion is needed.

public static void subswap(BTNode root)
// Precondition: Root is the root reference of a binary tree.
// Postcondition: If root is non-null, then the original left subtree below
// this root has been moved and is now the right subtree, and the original 
// right subtree is now the left  subtree.
// Example original tree:            Example new tree:
//          1                                 1
//         / \                               / \
//        2   3                             3   2
//       / \                                   / \
//      4   5                                 4   5

Redo the previous problem as a new non-static BTNode method.

Using the BTNode class from Chapter 9, write a new static method of the BTNode class to meet the following specification.

public static void flip(BTNode root)
// Precondition: Root is the root reference of a binary tree.
// Postcondition: If the root is non-null, then the tree below this node is 
// now the mirror image of its original value.
// Example original tree:            Example new tree:
//          1                                 1
//         / \                               / \
//        2   3                             3   2
//       / \                                   / \
//      4   5                                 5   4

Redo the previous problem as a new non-static BTNode method.

Short Answers
Section 9.4
Tree
Traversals
Here is a small binary tree:
```
       14
      /  \
     2    11
    / \   / \
   1  3  10  30
         /  /            
        7  40
```
Write the order of the nodes visited in:
A. An in-order traversal:
B. A pre-order traversal:
C. A post-order traversal:

Suppose IntBTNode is a BTNode (from Chapter 9) with integer data. Write a new static method of the IntBTNode class to meet the following specification.

public static void increase(IntBTNode root)
// Precondition: root is the root reference of a binary tree.
// Postcondition: Every node of the tree has had its data
// increased by one.

Redo the previous problem as a new non-static BTNode method.

Using the BTNode class from Chapter 9, write a new static method of the BTNode class to meet the following specification.

public static int manyNodes(BTNode root)
// Precondition: root_ptr is the root reference of a binary tree.
// Postcondition: The return value is the number of nodes in the tree.
// NOTES: The empty tree has 0 nodes, and a tree with just a root has
// 1 node.

Using the BTNode class from Chapter 9, write a new static method of the BTNode class to meet the following specification.

public static int treeDepth(BTNode root)
// Precondition: root_ptr is the root reference of a binary tree.
// Postcondition: The return value is the depth of the binary tree.
// NOTES: The empty tree has a depth of -1 and a tree with just a root
// has a depth of 0.

Suppose IntBTNode is a BTNode (from Chapter 9) with integer data. Write a new static method of the IntBTNode class to meet the following specification.

public static int count42(IntBTNode root)
// Precondition: root is the root reference of a binary tree (but
// NOT NECESSARILY a search tree).
// Postcondition: The return value indicates how many times 42 appears
// in the tree. NOTE: If the tree is empty, the method returns zero.

Suppose IntBTNode is a BTNode (from Chapter 9) with integer data. Write a new static method of the IntBTNode class to meet the following specification.

public static boolean has42(IntBTNode root)
// Precondition: root is the root reference of a binary tree (but
// NOT NECESSARILY a search tree).
// Postcondition: The return value indicates whether 42 appears somewhere
// in the tree. NOTE: If the tree is empty, the method returns false.

Suppose IntBTNode is a BTNode (from Chapter 9) with integer data. Write a new static method of the IntBTNode class to meet the following specification.

public static boolean all42(IntBTNode root)
// Precondition: root is the root reference of a binary tree (but
// NOT NECESSARILY a search tree).
// Postcondition: The return value is true if every node in the tree
// contains 42. NOTE: If the tree is empty, the method returns true.

Suppose IntBTNode is a BTNode (from Chapter 9) with integer data. Write a new static method of the IntBTNode class to meet the following specification.

public static int sum(IntBTNode root)
// Precondition: root is the root reference of a binary tree.
// Postcondition: The return value is the sum of all the data in all the nodes.
// NOTES: The return value for the empty tree is zero.

Short Answers
Section 9.5
Binary Search
Trees

Suppose that we want to create a binary search tree where each node contains information of some data type. What additional factor is required for the data type?
Suppose that a binary search tree contains the number 42 at a node with two children. Write two or three clear sentences to describe the process required to delete the 42 from the tree.
Suppose IntBTNode is a BTNode (from Chapter 9) with integer data. Write a new static method of the IntBTNode class to meet the following specification. Make the method as efficient as possible (do not visit nodes unnecessarily).
```
public static int count42(BTNode root)
// Precondition: root is the root reference of a binary SEARCH tree.
// Postcondition: The return value indicates how many times 42 appears
// in the tree.
```
Suppose IntBTNode is a BTNode (from Chapter 9) with integer data. Write a new static method of the IntBTNode class to meet the following specification. Make the method as efficient as possible (do not visit nodes unnecessarily).
```
public static int max(BTNode root)
// Precondition: root is the root reference of a nonempty binary SEARCH
// tree.
// Postcondition: The return value is the largest value in the tree.
```
Suppose IntBTNode is a BTNode (from Chapter 9) with integer data. Write a new static method of the IntBTNode class to meet the following specification. Make the method as efficient as possible (do not visit nodes unnecessarily).
```
void insert42(BTNode root)
// Precondition: root is the root reference of a binary SEARCH tree.
// Postcondition: One copy of the number 42 has been added to the binary
// search tree.
```

Multiple Choice

Multiple Choice
Section 9.1
Introduction
to Trees

       14
      /  \
     2    11
    / \   / \
   1  3  10  30
         /  /            
        7  40

There is a tree in the box at the top of this section. How many leaves does it have?

A. 2
B. 4
C. 6
D. 8
E. 9

There is a tree in the box at the top of this section. How many of the nodes have at least one sibling?

A. 5
B. 6
C. 7
D. 8
E. 9

There is a tree in the box at the top of this section. What is the value stored in the parent node of the node containing 30?

A. 10
B. 11
C. 14
D. 40
E. None of the above

There is a tree in the box at the top of this section. How many descendants does the root have?

A. 0
B. 2
C. 4
D. 8

There is a tree in the box at the top of this section. What is the depth of the tree?

A. 2
B. 3
C. 4
D. 8
E. 9

There is a tree in the box at the top of this section. How many children does the root have?

A. 2
B. 4
C. 6
D. 8
E. 9

Consider the binary tree in the box at the top of this section. Which statement is correct?

A. The tree is neither complete nor full.
B. The tree is complete but not full.
C. The tree is full but not complete.
D. The tree is both full and complete.

What is the minimum number of nodes in a full binary tree with depth 3?

A. 3
B. 4
C. 8
D. 11
E. 15

What is the minimum number of nodes in a complete binary tree with depth 3?

A. 3
B. 4
C. 8
D. 11
E. 15

Select the one true statement.

A. Every binary tree is either complete or full.
B. Every complete binary tree is also a full binary tree.
C. Every full binary tree is also a complete binary tree.
D. No binary tree is both complete and full.

Suppose T is a binary tree with 14 nodes. What is the minimum possible depth of T?

A. 0
B. 3
C. 4
D. 5

Select the one FALSE statement about binary trees:

A. Every binary tree has at least one node.
B. Every non-empty tree has exactly one root node.
C. Every node has at most two children.
D. Every non-root node has exactly one parent.

Multiple Choice
Section 9.2
Tree
Representations

Suppose t is a BTNode variable from Chapter 9, which expression indicates that t represents an empty tree?

A. (t == null)
B. (t->data == 0)
C. (t->data == null)
D. ((t->left == null) && (t->right == null))

Consider the node of a complete binary tree whose value is stored in data[i] for an array implementation. If this node has a right child, where will the right child's value be stored?

A. data[i+1]
B. data[i+2]
C. data[2*i + 1]
D. data[2*i + 2]

Multiple Choice
Section 9.3
A Toolkit for
Binary Tree Nodes

Suppose that a binary taxonomy tree includes 8 animals. What is the minimum number of NONLEAF nodes in the tree?

A. 1
B. 3
C. 5
D. 7
E. 8

Multiple Choice
Section 9.4
Tree
Traversals

14 / \ 2 11 / \ / \ 1 3 10 30 / / 7 40

There is a tree in the box at the top of this section. What is the order of nodes visited using a pre-order traversal?

A. 1 2 3 7 10 11 14 30 40
B. 1 2 3 14 7 10 11 40 30
C. 1 3 2 7 10 40 30 11 14
D. 14 2 1 3 11 10 7 30 40

There is a tree in the box at the top of this section. What is the order of nodes visited using an in-order traversal?

A. 1 2 3 7 10 11 14 30 40
B. 1 2 3 14 7 10 11 40 30
C. 1 3 2 7 10 40 30 11 14
D. 14 2 1 3 11 10 7 30 40

There is a tree in the box at the top of this section. What is the order of nodes visited using a post-order traversal?

A. 1 2 3 7 10 11 14 30 40
B. 1 2 3 14 7 10 11 40 30
C. 1 3 2 7 10 40 30 11 14
D. 14 2 1 3 11 10 7 30 40

Multiple Choice
Section 9.5
Binary Search
Trees

Consider this binary search tree:

Suppose we remove the root, replacing it with something from the left subtree. What will be the new root?

A. 1
B. 2
C. 4
D. 5
E. 16

Michael Main (main@colorado.edu)