10 ADTs and Recursion (HL only)

ADTs

Data Structures

Describe the features and characteristics of a dynamic data structure.

Compare the use of static and dynamic data structures.

Suggest a suitable structure for a given situation.

2D Arrays

Construct algorithms using two- dimensional arrays.

Stacks

Describe the characteristics and applications of a stack. Characteristics: Last in, first out (LIFO).

Examples of the applications of stacks may include running recursive processes, return memory addresses.

Construct algorithms using the access methods of a stack. Access methods: push, pop, isEmpty.

Queues

Describe the characteristics and applications of a queue.

Characteristics: First in, first out (FIFO).

Examples of the applications of queues may include print queues and the computer modelling of physical queues (eg supermarket checkouts).

Both linear and circular implementation of a queue are required.

Construct algorithms using the access methods of a queue.

Access methods: enqueue, dequeue, isEmpty.

Dynamic Stacks and Queues, Nodes

Explain the use of arrays as static stacks and queues. Students should be able to explain push and pop operations, and test on empty/full stack. Students should be able to explain enqueue and dequeue operations, and test on empty/full queue.

Students should understand the concepts of nodes and pointer.

Trees

Describe how trees operate logically (both binary and non-binary).

Define the terms: parent, left-child, right-child, subtree, root and leaf. These definitions only apply to a binary tree. These definitions only apply to a binary tree.

Define the terms: parent, left-child, right-child, subtree, root and leaf. These definitions only apply to a binary tree.

State the result of inorder, postorder and preorder tree traversal.

Sketch binary trees. Students should be able to sketch diagrams showing the resulting binary tree after adding a new data item, adding one or more new nodes, and/or removing one or more nodes.

Linked Lists

Describe how linked lists operate logically.

Sketch linked lists (single, double and circular). Students should be able to sketch diagrams illustrating: adding a data item to. Students should be able to sketch diagrams illustrating: adding a data item to linked list, deleting specified data item, modifying the data held in the linked list, searching for a given data item.

Recursion

Identify a situation that requires the use of recursive thinking. Suggested practical activity: snowflakes and fractals, towers of Hanoi.

Identify recursive thinking in a specified problem solution.

Trace a recursive algorithm to express a solution to a problem. Students will be required to state the output of the recursive algorithm. For example, trees.