Logout

HL extension (45 hours)

Topic 5— Abstract data structures (23 hours)

 

START  of  STAGE  F

5.1 Abstract data structures (23 hours)


This will be examined at the level of diagrams and pseudocode.

Students should be able to describe the most common data structures (arrays, stacks, queues, linked lists, binary trees) and the most common data processing operations on each of the basic data structures (addition, deletion and retrieval of data, traversal, searching for a given data, sorting of data into some order).

This should be taught and connected to flow charts, pseudocode and programming in the SL/HL core.

The basic ideas and their application should be illustrated with non-computer examples. Each basic idea should then be practised in specific algorithmic contexts using concepts drawn from flow charts, pseudocode and programming.

 

Code-Camp-Day-1: Recursion

Code-Camp-Day-1: Recursion Applied


Thinking recursively

5.1.1 Identify a situation that requires the use of recursive thinking.

5.1.2 Identify recursive thinking in a specified problem solution.

5.1.3 Trace a recursive algorithm to express a solution to a problem.


Abstract data structures

Code-Camp-Day-1: 2D Arrays

5.1.4 Describe the characteristics of a two-dimensional array.

5.1.5 Construct algorithms using two-dimensional arrays.

5.1.6 Describe the characteristics and applications of a stack.

5.1.7 Construct algorithms using the access methods of a stack.

5.1.8 Describe the characteristics and applications of a queue.

Code-Camp-Day-1: Stacks and Queues Implemented

5.1.9 Construct algorithms using the access methods of a queue.

5.1.10 Explain the use of arrays as static stacks and queues.


Linked lists

Linked lists will be examined at the level of diagrams and descriptions. Students are not expected to construct linked list algorithms using pseudocode.

Code-Camp-Day-1: Linked Lists

5.1.11 Describe the features and characteristics of a dynamic data structure

5.1.12 Describe how linked lists operate logically.

5.1.13 Sketch linked lists (single, double and circular). Straight-forward, good exam question


Trees

Binary trees will be examined at the level of diagrams and descriptions. Students are not expected to construct tree algorithms using pseudocode.

Tracing and constructing algorithms are not expected.

Code-Camp-Day-1: Trees

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

5.1.15 Define the terms: parent, left-child, right-child, subtree, root and leaf.

5.1.16 State the result of inorder, postorder and preorder tree traversal. Straight-forward, good exam question

5.1.17 Sketch binary trees. Straight-forward, good exam question


Applications

Code-Camp-Day-1: Applications

5.1.18 Define the term dynamic data structure.

5.1.19 Compare the use of static and dynamic data structures.

5.1.20 Suggest a suitable structure for a given situation.

END of  STAGE  F

go to Stage G (Back to Topic OOP Option for HL Extension)