Unit 7 Data Structures
No description yet. This curated deck is ready for daily study.
Card preview (24)
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