The Java programming language provides some standard data structures (such as arrays or files) that are adequate for many standard problems. Other
problems require further data types to represent more complex structures, improve algorithm efficiency, or provide for more sophisticated memory
management.
Although Java implements many different types of container class for the convenience of programmers, students are expected to be able to develop their own
ADTs from first principles.
Higher level students must demonstrate mastery of some of these techniques in the program dossier and should be able to use any of these techniques during
the examination. This topic extends several aspects of topics 1 and 2.
5.1.2 Define stack, queue and binary tree.
5.1.3 Discuss the features and appropriate usage of stacks including: parameter storage, interrupt handling, evaluation of arithmetic expressions and storage of subprogram return addresses.
5.1.4 Discuss the features and appropriate usage of queues including: keyboard queues, print queues and customer queue simulations.
5.1.5 Discuss the features and appropriate usage of binary trees including: storing search keys, decision trees and file systems.
5.2.1 Trace algorithms that perform a quicksort on linear arrays.
5.2.2 Construct algorithms that perform a quicksort on linear arrays.
5.2.3 Construct a hash table including the generation of addresses using modulo arithmetic and the handling of clashes by locating next free space.
5.2.4 Trace algorithms that implement a stack in an array.
5.2.5 Construct algorithms that implement a stack in an array.
5.2.6 Trace algorithms that implement a queue in an array.
5.2.7 Construct algorithms that implement a queue in an array.
5.3.1 Define object reference.
5.3.2 Construct algorithms that use reference mechanisms.
5.3.3 Discuss the features and appropriate usage of single, double and circular linked lists.
5.3.4 Outline and illustrate how links operate logically.
5.3.5 Trace algorithms to implement linked lists.
5.3.6 Construct algorithms to implement linked lists.
5.3.7 Trace algorithms that implement a dynamic stack using references.
5.3.8 Construct algorithms that implement a dynamic stack using references.
5.3.9 Trace algorithms that implement a dynamic queue using references.
5.3.10 Construct algorithms that implement a dynamic queue using references.
5.3.11 Define parent, left-child, right-child and subtree.
5.3.12 Trace algorithms to implement binary trees.
5.3.13 Construct algorithms to implement binary trees.
5.3.14 Outline and illustrate the logical representation of dynamic data structures.
5.4.1 Outline the features of an object.
5.4.2 Explain the basic features and advantages of encapsulation.
5.4.3 Explain the basic features and advantages of information and data hiding.
5.4.4 Explain the basic features and advantages of polymorphism.
5.4.5 Explain the basic features and advantages of inheritance.
5.4.6 Trace an algorithm that includes objects.
5.5.1 Define recursion.
5.5.2 Discuss the advantages and disadvantages of recursion.
5.5.3 Trace recursive algorithms.
5.5.4 Construct recursive algorithms.
5.5.5 Implement the following constructs: self-referential classes and recursion.
5.6.1 State the efficiency of the following algorithms in BigO notation: a linear search is O(n), a bubble sort is O(n2), a quicksort is O(n log n), a binary search is O(log n) and a selection sort is (n2), given a randomly distributed data set.
5.6.2 Analyse the efficiency of algorithms (those in 5.6.1 and those of similar complexity), in terms of BigO notation and in terms of the storage requirements.
5.6.4 Evaluate algorithms that use any of the data structures in this syllabus.