CMSC--341 Data Structures Section 101 & 201

Fall 1998 Exam 2 Review

Sample questions and things you should know for exam 2



template <class Etype>
class Tree_Node
{
    protected:
        Etype Element;
        Tree_Node *Left;
        Tree_Node *Right;
       Tree_Node( Etype E = 0, Tree_Node *L = NULL, Tree_Node *R = NULL )
            : Element( E ), Left( L ), Right( R ) {  }

 friend class Binary_Search_Tree<Etype>; 
}

template <class Etype>
class Binary_Search_Tree 
{
    protected:
      void Make_Empty(Tree_Node<Etype> * &);
      Tree_Node<Etype> * Find(const Etype &, Tree_Node<Etype> *) const;
      Tree_Node<Etype> * Find_Max(Tree_Node<Etype> *) const;

      Tree_Node<Etype> *Root;
      Tree_Node<Etype> *Last_Find;

    public:
      Binary_Search_Tree( ) : Root( NULL ), Last_Find( NULL ) {  }
      Binary_Search_Tree (Binary_Search_Tree & Value );
      virtual ~ Binary_Search_Tree ( )
         { Make_Empty( Root ); Root = Last_Find = NULL; }
      virtual int Find( const Etype & X )
         { return int( Last_Find = Find( X, Root ) ); }
      virtual int Find_Max()
         { return int (Last_Find = Find_Max(Root)); }

     // iterator functions
     void BSTInit();
    Etype BSTGetNext();
};

1. Prove 2n+1 = O(2n )

2. Write the Binary_Search_Tree member function

int NrOfNodes (Tree_Node *) that counts the number of nodes in a binary search tree. What is the Big-Oh running time of your algorithm? Justify your answer.

3. Write a binary search tree traversal (pseudo-code) that prints the contents of the tree in reverse sorted order. What is the Big-Oh running time of your algorithm? Justify your answer.

4. Let T be a binary search tree, let x be a leaf node in T and let y be x's parent. Show that y's element is either the smallest element in T that is larger than x's element or the largest eleme nt in T that is smaller than x's element.

5. Let T be a binary search tree, and x be any node that has two children. Show that x's successor has no left child and that it's predecessor has no right child.

6. Professor Smith thinks he has discovered a remarkable property of binary search trees. Suppose that the search for element K in a BST ends in a leaf.

Consider 3 sets: A is the set of elements to the left of the search path; B is the set of elements on the search parth; and C is the set of elements to the right of the search path. Professor Smith claims that for any three elements a,b and c contained in A, B and C respectively that a <= b <= c. Give a small counterexample to the professor's claim.

7. How can a BST be used for sorting?

8. State the Binary Search tree property.

9. Why is Binary_Search_Tree declared as a friend class of Tree_Node?

10. Define an ADT for queue

11. Describe an array implementation for the queue ADT (describe the data structure, cursors, etc.).

Show how the operations isEmpty, isFull, dequeue, and enqueue are implemented.

12. Describe a linked­list implementation for the queue ADT (describe the data structure, pointers, etc.). Show how the operations isEmpty, isFull, dequeue, and enqueue are implemented.

13. Describe the advantages and disadvantages of the array and linked­list implementations of the queue ADT. Consider the asymptotic behavior for each of the operations isEmpty, isFull, dequeue, and enqueue. Also consider the storage requirements for e ach implementation.

14. For any tree T , define path in T, length of a path in T , height of a node in T , depth of a node in T, height of T, depth of T, leaf node.

15. Given the diagram of a binary tree, draw the corresponding general first-child, next-sibling tree, and vice versa.

16. Prove: there are n - 1 edges in any tree with n nodes.

17. Define tree, binary tree, full binary tree, complete binary tree, height­balanced binary tree.

 

18. Prove: A full binary tree of height h has 2h leaf nodes.

19. Write C++ function templates for pre­order, post­order, and in­order traversal of binary trees.

20. Write pseudo-code for the function
template <class Etype>
Tree_Node<Etype> *
Binary_Search_Tree::Find(const Etype & value, Tree_Node<Etype> * T) const
that takes a value and a Tree_Node as its arguments and returns a pointer to the node if found, or NULL if the node is not found.

21. State the three rules for deletion of a node in a binary search tree.

22. Show the result of inserting {3,1,4,6,9,2,5,7} (in that order) into an empty binary search tree (show the tree at the end of each insertion). Show the result of deleting the root.

23. Draw the tree that results after deleting a specified node from a binary search tree.

24. Explain why SPLAY, AVL and Red-Black trees provide better worst-case performance for Find and Insert operations on BSTs. Discuss the relative peformance of each tree.

25. Given an existing SPLAY tree, show the resulting splay tree after a FIND operation is done a particular node. The rules for splaying will be provided with the exam.

26. Define AVL tree.

27. Show the AVL tree that results after insertion of the values {4, 3, 12, 7, 6, 5} (in that order). The initial insertion is into an empty AVL tree. Show the AVL tree after each insertion. The rules for re-balancing AVL trees will be provided with the exam.

28. Define the Red-Black tree properties. Which property may be violated when a new node is inserted?

29. Suppose the root of a Red-Black tree is RED. If we make it BLACK, does the
tree remain a Red-Black tree? Justify your answer.

30. Define black-height for a Red-Black tree.

31. Describe how you can use a tree traversal to argue that rotations in a BST do not violate the BST property.

32. Write pseudo-code for pre-order, post-order and in-order traversal functions for binary trees.

33. For a given binary tree, give the pre-order, post-order and in-order traversals of the tree.

34. What is the conceptual relationship between a base class and its derived classes?

35. What is the difference between overloading and overriding a function in C++?

36. Define the following

  1. protected member
  2. Base class
  3. Derived class
  4. virtual function
  5. pure virtual function
  6. polymorphism
  7. dynamic binding

37. What does the key word virtual mean in front of a C++ member function?

38. Write out the class declarations for three classes: A, B, and C, where B and C inherit (publicly) from A. A has a virtual member function, print(), which is overridden in B and C.

39. What is the difference between overloading and overriding a function in C++?

40. If classes B and C inherit from class A, indicate which of the following C++ statements will compile: A *ap = new A; B *bp = new B; C *cp = new C; ap = bp; cp = ap; ap = cp; bp = cp; 40. Consider the following class definitions and code fragment class A { public: int i; A (int k) { i = k; } }; class B { protected: int i; public: B (int k) { i = k; } virtual int f( ) { return i; } virtual int g( ) { return 2 * i; } }; class C : public B { public: A a; int j; C (int k) : B(5), a(10) { j = k; } int f ( ) { return 3 * i; } int g ( ) { return 4 * i; } }; main ( ) { B b(15); B *bp = &b; C c(20); C *cp = &c; cout << bp->f( ) << endl; // line 1 cout << bp->g( ) << endl; // line 2 cout << cp->f( ) << endl; // line 3 cout << cp->g( ) << endl; // line 4 bp = cp; cout << bp->f() << endl; // line 5 cout << bp->g() << endl; // line 6 }

A. What is the output for lines 1 to line 4?

  1. 15, 30, 5, 20
  2. 15, 30, 20, 80
  3. 15, 30, 15, 20
  4. 15, 60, 15, 60
  5. 45, 60, 20, 80

B. What is the output for lines 5 and 6?

  1. 5, 10
  2. 15, 20
  3. 15, 30
  4. 15, 60
  5. 45, 60