Unit 7 - Data Structures

Be familiar with the concept of a data structure

Understand how data is represented and stored within different structures including

• arrays up to three dimensions

• tuples

• records 

Use 1- 2- and 3-dimensional arrays in the design of solutions to simple problems 

Understand the concept of an abstract data type

Be familiar with the concept and uses of a queue

Describe the creation and maintenance of data within a queue (linear, circular, priority)

Describe and apply the following to a linear, circular and priority queue

• add an item

• remove an item

• test for an empty queue

• test for a full queue

Explain how a list may be implemented as a static or dynamic data structure

Describe the linked list data structure

Show how to create, traverse, add data to and remove data from a linked list

Be familiar with the concept and uses of a stack

Be able to describe the creation and maintenance of data within a stack

Be able to describe and apply the following operations: push, pop, peek (or top), test for empty stack, test for full stack 

Be able to explain how a stack frame is used with subroutine calls to store return addresses, parameters and local variables

Be familiar with a hash table and its different uses

Be able to apply simple hashing algorithms

Know what is meant by a collision and how collisions are handled using rehashing

Add data to and remove data from a hash table

Be familiar with the concept of a dictionary

Be familiar with simple applications of a dictionary

Be aware of a graph as a data structure used to represent complex relationships

Be familiar with typical uses for graphs

Be able to explain the terms: graph, weighted graph, vertex/node, edge/arc, undirected graph, directed graph

Know how an adjacency matrix and an adjacency list may be used to represent a graph

Be able to compare the use of adjacency matrices and adjacency lists

Know that a tree is a connected, undirected graph with no cycles

Know that a binary tree is a rooted tree in which each node has at most two children

Be familiar with typical uses for rooted trees

Be able to trace recursive tree-traversal algorithms: pre-order, post-order, in-order 

Understand uses of different traversal outputs