Logout

# Topic 5— Abstract data structures (23 hours)

## 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.

Extra resource: Java, Java, Java by Ralph Morelli & Ralph Walde. (CC BY 4.0)
A great college level open source license textbook to aid you.

START  of  STAGE  F

5.1.0 JSR Notes on Topic 5 and ADTs

For 5.1.1 - 5.1.3, refer to Topic 5 & OOP Recursion main section.

Code-Camp-Day-1: 2D Arrays (YT)

5.1.4 Describe the characteristics of a two-dimensional array.

5.1.5 Construct algorithms using two-dimensional arrays.

5.1.5-Full-Examples

___________________________________________________

Dynamic Data Structures

5.1.18 Define the term dynamic data structure.

5.1.11 Describe the features and characteristics of a dynamic data structure (like linked list)

D.4.5 - Define the term object reference. (JSR added - it helps the understanding of dynamic data structures.)

5.1.12 Describe how linked lists operate logically.

Linked lists will be examined at the level of diagrams and descriptions. Students are not expected to construct linked list algorithms using pseudocode. JSR Note: But for Option D, you are expected to construct and use Java algorithms using the LinkedList ADT.

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

Once again, remember Topic 5, gnerally is to be "examined at the level of diagrams and pseudocode."

Code-Camp-Day-1: Stacks and Queues Implemented (YT)

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.

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.

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.

JSR note: Note that trees are only a Topic 5, not an Option topic.

Code-Camp-Day-1: Trees (YT)

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 (MOVED to Recursion Page) State the result of inorder, postorder and preorder tree traversal.

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

Applications

Code-Camp-Day-1: Applications (YT)

5.1.18 Define the term dynamic data structure. (Already covered above, as general intro after 2d arrays.)

5.1.19 Compare the use of static and dynamic data structures.

5.1.20 Suggest a suitable structure for a given situation.

***Topic 5 (& OOP) Recursion***

END of  STAGE  F