Monash University > CSSE > CSE1303 > Part A > Tutorials > Tutorial A5

CSE1303 Computer Science
Summer Semester, 2003
Part A
Tutorial A5 : Recursion, Binary Search Trees and Complexity

This tute covers material from lectures A10 to A13.

There may not be time in the tutorial to cover all of these questions. Attempt at least the ones marked with an asterisk before the tutorial; these are the ones that will be focussed on during the class. If you have specific questions about unmarked questions, you can ask the tutor about them during the tutorial. If you want further revision questions, suggestions of questions from the textbooks are provided at the end of the tutorial sheet.

---

Note: The purpose of tutorials is not simply to give you the answers to these questions! (Solutions will be released in about a week online, so if all you want is the answers, there are easier ways.)

---

Exercise 1

Assume that the Linked List is defined as it is in the lecture notes to hold items of type float. Write a function void killList(List* listPtr),which deletes all the nodes in the Linked List.

* Exercise 2

Assume that the Binary Search Tree is defined as it is in the lecture notes to hold items of type float. Write a recursive function void killTree(TreeNode* nodePtr),which deletes all the nodes in the Binary Search Tree, where nodePtr contains the address of the root node.

* Exercise 3

Draw an Expression Tree for the following expressions:
1. (a*q - b*p) / (a-b)
2. ((a - b)*(c - d) ) / ((b - c)*(d - a))

* Exercise 4

For the expressions in Exercise 3, write them in following notations:
1. Prefix
2. Infix
3. Postfix

* Exercise 5

Assume the Binary Search Tree stores strings in alphabetical order. Insert the following 14 names into an empty Binary Search Tree in the order they appear and draw the final Binary Search Tree.

Jan, Guy, Jon, Ann, Jim, Eva, Amy, Tim, Ron, Kim, Tom, Roy, Kay, Dot

* Exercise 6

For the Binary Search Tree constructed in Exercise 5, write the names in the order given by the following traversal methods:
1. Preorder
2. Inorder
3. Postorder

Exercise 7

1. Given the following unsorted list:

   5

   7

   8

   1

   6

   • What is the complexity of sorting the list using selection sort? Why?
   • What is the complexity of sorting the list using insertion sort? Why?

2. Given the following sorted list:

   3

   6

   9

   11

   12

   • How many comparisons does the worst case for a linear search of this list take and what does it search for?
   • What is the average number of comparisons for a linear search in this list?
   • How many comparisons does the worst case for a binary search of this list take and what does it search for?
   • What is the average number of comparisons for a binary search in this list?

3. Given the following binary search tree:

   

   • How many comparisons does the worst case for a search of this tree take, and what does it search for?
   • What is the average number of comparisons to search for an item that is in this binary search tree?
   • Give an example of a tree which has O(n) worst case to search for an item which is in the tree.

ADDITIONAL EXERCISES

Kruse et al, 2^nd Edition
    Exercises 3.4: E1, E2
    Exercises 9.1: E1, E2, E3, E4, E5, E6, E7, E13, E14, E15
    Exercises 9.2: E1, E2, E4, E6,
    Review Questions Chapter 3: 3, 4, 5, 13
    Review Questions Chapter 9: 1, 2, 3, 4, 5, 6

Deitel & Deitel 2^nd Edition
    Self Review Exercises: 12.1 k, l, m, n, o, 12.5
    Exercises: 12.20, 12.21, 12.25

[ Top | Home ]

Last modified: Tuesday 02 December 2003 22:29:33