Unit 7 Data Structures Flashcards
What are the properties of a Tuple? (3)
- It is an ordered set of values
- It may have elements of mixed types
- It is immutable
What does Immutable mean?
Elements cannot change
What is a Dynamic Data Structure?
It can change size when required
What is a Static Data Structure?
It cannot change size
What are Integer, Real, Boolean and Char all examples of?
Elementary data types
What are String and Array both examples of?
Composite data types
What are List, Stack and Queue all examples of?
Abstract data types
What is an ADT?
Abstract Data Type
A logical description of how we view the data and possible operations
What does the Queue Function enQueue(item) do?
Adds an item to the rear
What does the Queue Function deQueue do?
Removes and returns an item from the front
What does the Queue Function isEmpty do?
Indicates if a queue is empty
What does the Queue Function isFull do?
Indicates if a queue is full
What happens in a Priority Queue?
Some items are allowed to ‘jump’ the queue
What is Overflow?
Attempting to push onto a stack that is full
What is Underflow?
Attempting to pop from a stack that is empty
How does a Stack operate?
First On Last Off
What is a Hash Function?
Large data sets can be organised so each record is assigned a unique address. This unique address is calculated using a hashing algorithm or hash function. The algorithm uses some part of the record to map the record to a unique destination address
When does a Collision happen?
When an algorithm generates the same address for different primary keys
A collision is sometimes referred to as a synonym
What is a Graph?
A set of vertices or nodes connected by edges or arcs. Edges may be weighted, indicating a cost of traversal
What distinguishes an Undirected Graph?
All edges are bidirectional
What is an advantage of a Matrix?
Convenient to work with, and adding an edge is simple
What is a disadvantage of a Matrix?
A sparse graph with not many connections (edges) will leave most of the cells empty, wasting a lot of memory space
What are advantages of an Adjacency List? (2)
- It only uses storage for the connections that exist, so it is more space-efficient
- It is a good way of representing a large, sparsely connected graph
What are some applications of Graphs? (3)
- Computer networks, with nodes representing computers and weighted edges representing bandwidth between them
- Web pages and links
- Project management, with nodes as tasks, edges representing sequence and weights, time or cost
What is a Tree?
A connected, undirected graph with no cycles
What is an Edge?
A line joining 2 nodes of a tree
What is a Root?
The start node of a tree that all others are connected off of
What is a Subtree?
A smaller segment of a tree
What is a Leaf?
A node on a tree with no children
What is a Binary Tree?
A rooted tree in which each node has a maximum of two children
On a Binary Tree, what does each Node consist of? (3)
- The data (which may be a primitive or more complex object)
- A left pointer to a child
- A right pointer to a child
What is Pre-order Traversal?
Visiting the root, then traversing the left sub-tree, then the right sub-tree. (Left dot)
What is In-order Traversal?
Traversing the left sub-tree, then visiting the root, then traversing the right sub-tree. (Bottom dot)
What is Post-order Traversal?
Traversing the left sub-tree, then traversing the right sub-tree, then visiting the root. (Right dot)
What is a Balanced Binary Tree?
One where the nodes are distributed in such a way that the height is kept to a minimum
