Logout

Home

HL extension (45 hours)

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.


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.18 Define the term dynamic data structure.

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

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.JSR Note: But for Option D, you are expected to construct and use Java algorithms using the LinkedList ADT.

- D.4.5 - Define the term object reference. (JSR added, as it will help set up the understanding of lists.)


Code-Camp-Day-1: Linked Lists     (YT)

5.1.12 Describe how linked lists operate logically.

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


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

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