CS211 - Algorithms and Data Structures II
Tutorial 13

T Naughton, CS NUIM
Back to CS211 home

This tutorial will cover some past lab exam problems and past exam questions.

Part I:

  • Lab Problem 11A.1a Write a method for an ordered binary tree that returns the height of the smallest element in the tree.
  • Lab Problem 11A.1b Write a method for an ordered binary tree that returns the depth of the smallest element in the tree.
  • Lab Problem 11B.1 Write a method for an ordered binary tree that returns the number of leaf nodes in the tree.
  • Lab Problem 11C.1 Write a method for an ordered binary tree that returns the contents of the leaf node with the highest value.

    Part II:

  • Lab Problem 11A.2 A class to implement a hash table of airports and their locations is required. Each airport has the following properties: a name, a three digit serial code, and a grid reference. The airport grid reference (the key) is stored as a floating point number, the airport name is stored as a character string, and the three digit code is stored as an integer. Write a suitable hash() function, countfree() method, and insert() method. You do not have to write the class definition.
  • Lab Problem 11B.2 A class to implement a hash table of airports and their locations is required. Each airport has the following properties: a name, a three digit serial code, and a grid reference. The airport grid reference (the key) is stored as a floating point number, the airport name is stored as a character string, and the three digit code is stored as an integer.
    (a) Write a suitable class definition for this class. Include all necessary data structures and method signatures. You do not have to implement the methods.
    (b) Write a method Ratio() to determine the ratio of deleted locations to free locations in your hash table.
    (c) Write a Contains() method that determines if a given grid reference appears in the hash table.

    Part III: Past exam papers:

  • 1998 Summer Paper 2.1 Sect. B Q3(a,b,c), Q6(a,b,c,d,e)
  • 1998 Autumn Paper 2.1 Sect. B Q3(d,e)
  • 1999 Summer Paper 2.1 Sect. B Q3(a,b,c), Q6(a,b,c,d)
  • 1999 Autumn Paper 2.1 Sect. B Q8(a), Q10(a,b,c), Q12(a,b,c)