Topic 5: Abstract data structures

Command Term	Level	Definition
Define	1	Give the precise meaning of a word, phrase, concept or physical quantity.
State	1	Give a specific name, value or other brief answer without explanation or calculation
Describe	2	Give a detailed account.
Identify	2	Provide an answer from a number of possibilities.
Trace	2	Follow and record the action of an algorithm.
Compare	3	Give an account of the similarities between two (or more) items or situations, referring to both (all) of them throughout.
Construct	3	Display information in a diagrammatic or logical form.
Explain	3	Give a detailed account including reasons or causes.
Sketch	3	Represent by means of a diagram or graph (labeled as appropriate). The sketch should give a general idea of the required shape or relationship, and should include relevant features.
Suggest	3	Propose a solution, hypothesis or other possible answer.

5.1 Abstract Data Structures

Thinking Recursively

5.1.1 Identify a situation that requires the use of recursive thinking.
IB HL2 to Unit-6.1 Recursion (bwagner.org)

5.1.2 Identify recursive thinking in a specified problem solution.
IB HL2 to Unit-6.1 Recursion (bwagner.org)

5.1.3 Trace a recursive algorithm to express a solution to a problem.
IB HL2 to Unit-6.1 Recursion (bwagner.org)
Practice Problems Recursion-questions-bw.pdf

Abstract Data Structures

5.1.4 Describe the characteristics of a two-dimensional array.

IB HL2 to Unit-5 2-Dimensional Arrays (bwagner.org)

5.1.5 Construct algorithms using a two-dimensional array.

IB HL2 to Unit-5 2-Dimesional Arrays (bwagner.org)

5.1.6 Describe the characteristics and applications of a stack.

Presentations
Stacks.notebook SmartNotebook file
Stacks.pdf pdf version of the SmartNotebook

Java programs
StateNode.java node for linked-list
StatesStack.java uses StateNode to implement a stack using a linked list.
States.java Main Program to test stack operations

Activitities
See agenda items 10/26 - 10/27
Warm-up Tracing Stacks solution is in the Stacks.notebook file, at the end.

5.1.7 Construct algorithms using the access methods of a stack. See 5.1.6 resources

IB HL2 to Unit-7 to Notes 7.3 Stacks (bwagner.org)
IB HL2 to Unit-9 Stackes (bwagner.org)

5.1.8 Describe the characteristics and applications of a queue.

IB HL2 to Unit-7 to Notes 7.4 Queues (bwagner.org)
IB HL2 to Unit-10 Queues (bwagner.org)

5.1.9 Construct algorithms using the access methods of a queue.

IB HL2 to Unit-7 to Notes 7.4 Queues (bwagner.org)

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

Linked Lists

5.1.11 Describe the features and characteristics of a dynamic data structure.

5.1.12 Describe how linked lists operate logically.
Activities
File: Linked Lists
Present Linked Lists Exampe 1 and Example 2
Complete handout Exercise 1 and Exercise 2
Complete handout Exercise 3 and Exercise 4

Java programs (sorted linked lists)
WordNode.java node for linked-list
WordList.java uses WordNode to implement a sorted linked list.
Words.java Main Program to test sorted-list operations

5.1.13 Sketch linked lists (single, double and circular).
Activities
File: Singularly Linked Lists (from 5.1.12)

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.
See activities list below

parent
A node within a tree that has nodes that branch off from it (children)

child
A node within a tree that branches off from another (parent)

subtree
The grouping of a parent and a child in a tree.

root
The top node in a tree.

leaf
A node with no children within a tree.

5.1.16 State the result of inorder, postorder and preorder tree traversal.
See activities list below

5.1.17 Sketch binary trees.
See activities list below

Tree
References

Lecture notes from Carnegie Mellon School of Computer Science

Activities Covering the Content

Introduction to Recursion and Binary Trees

IB HL2 to Unit-7 to Notes 7.5 Trees (bwagner.org)

Binary Tree Vocabulary

Powerpoint: Binary Trees class activity
Warm-up: Matching Game (Version 1) Version 1 Key
Additional Practice: Matching Game (Version 2) Version 2 Key
IB HL2 to Unit-7 to Notes 7.5 Trees (bwagner.org)
Word Tag review and practice
Additional copies of the matching game are available for end of the year practice and review, as well as for quizzes.

Traversing Binary Trees inorder

Java program
Powerpoint
In-class demo
Warm-up practice
Homework practice
Quiz version 1 version 1 key
Quiz version 2 version 2 key
Quiz version 3 version 3 key

Traversing Binary Trees preorder

Java program
Powerpoint
In-class demo
Warm-up practice
Homework practice
Quiz version 1 version 1 key
Quiz version 2 version 2 key
Quiz version 3 version 3 key

Traversing Binary Trees postorder

Java program
Powerpoint
In-class demo
Warm-up practice
Homework practice
Quiz version 1 version 1 key
Quiz version 2 version 2 key
Quiz version 3 version 3 key

Creating Binary Trees

Java program
PowerPoint Demo
Interactive Demo - try it yourself
Warm-up practice
Homework practice
Quiz version 1 version 1 key
Quiz version 2 version 2 key
Quiz version 3 version 3 key

Applications

5.1.18 Define the term dynamic data structure.
Dynamic Data-Structure
A data structure in which the number of elements can change during program execution

5.1.19 Compare the use of static and dynamic data structures.

5.1.20 Suggest a suitable structure for a given situation.