4.2 Data Structures Flashcards
1
Q
Static vs Dynamic Data Structures
- when size is determined
- storage
A
- static: storage size determined before program is run (fixed size)
- dynamic: can change size during run time
- static: can waste storage space is number of data items is small compared to size
- dynamic: only take up amount of storage space required
- dynamic: need memory to store pointer to next items
2
Q
Enumerated (definition)
A
In the form of a list
3
Q
Arrays (2)
A
- elements must be of the same data type
- objects are mutable
4
Q
Lists (3)
A
- elements can be of different data types
- objects are mutable
- is a dynamic data structure
5
Q
Tuples (3)
A
- elements can be of different data types
- objects are immutable
- more efficient than lists since are immutable
6
Q
Text Files can only store
A
Strings
7
Q
Advantage of Text Files
A
They can be created, altered or prepared independently from the program
8
Q
Binary Files (3)
A
- hard for human to understand
- are directly compatible with the computer
- tend to be more secure as without correct definitions would be difficult to convert data into meaningful information
9
Q
CSV Files (4)
A
- comma separated files
- type of text file used to store a set of records
- each record is stored on a single line
- each field in the record is separated by a comma
10
Q
Types of Access of Files
- read
- write
- append
- read binary file
- write to binary file
A
- r = read
- w = write (overwrites entire file)
- a = append
- rb = read binary file
- wb = write to binary file
11
Q
Queues
- Acronym
- Number of Pointers
A
- FIFO (First In First Out)
- 2 pointers: rear and front
12
Q
Linear Queues
- type of structure
- queue = empty if …
- disadvantage
A
- static data structure
- queue = empty if front > rear
- dis: limited amount of space
12
Q
Circular Queues
- definition
- what pointers store
A
- queue which has a fixed amount of space but where the end of the queue is connected to the front
- front points to element of array which should be removed next
- rear points to last element added
13
Q
Priority Queues (2 + Enqueue)
A
- when elements are assigned they are ordered according to some rule
- each item is assigned a priority as it is added to the queue
- enqueue: same as linear queue, except value is inserted into correct position according to a given priority
14
Q
Enqueue Algorithm
A
- check if full (if rear + 1 = front)
- if not full
- increment rear by 1
- add item at the location indicated by the value of rear pointer
15
Q
Push Function + Algorithm
A
- adds data pushed to top of stack
- check isFull()
- if not full
- increment top pointer by 1
- insert data at location indicated by the value of the top pointer
15
Q
Stack
- type of structure
- acronym
- no. pointers
A
- static data structure
- LIFO (Last In First Out)
- 1 pointer: top
15
Q
Dequeue Algorithm
A
- check if empty (if front > rear)
- if not empty
- get item at location indicated by front pointer
- increment value of front pointer by 1
- return item
16
Q
Pop Function + Algorithm
A
- removes data at top of stack and returns it
- check isEmpty()
- if not empty
- get value at location indicated by the value of top pointer
- reduce top pointer by 1
- return value
17
Q
Peek Function + Algorithm
A
- returns value at the top of stack without removing it
- return stackarray[top]
18
Q
Test for Empty Stack AKA + Algorithm
A
- known as stack underflow
- if top == -1
- return True
19
Q
Test for Full Stack AKA + Algorithm
A
- known as stack overflow
- if top == max
- return True
20
Q
Method to Reverse the Order of a List Using a Stack
A
- push all elements in list onto stack
- for each element in stack:
- perform pop function
- store value returned in next available space in a list
21
Q
Method to Reverse the Order of a Queue Using a Stack
A
- elements of queue are dequeued from queue
- elements are then pushed onto stack
- elements are popped off stack
- elements are enqueued to queue
22
Graph (definition)
Has a set of vertices and edges where each edge joins two vertices
23
Labelled Graph (definition)
One that has its vertices associated with a label
24
Directed Graph (definition)
Graph that consists of arcs and vertices where every arc connects two vertices and has a direction
25
Weighted Graph (definition)
Graphs where every edge is given a weight
26
Adjacency Matrix vs List
- Use an adjacency matrix with dense graphs (many edges) to avoid searching through long lists to check for adjacency
- Use an adjacency list with sparse graphs as it takes up less storage and lists are short so don’t take a long time to search for adjacency
27
Tree (definition)
Connected undirected graph with no cycles
28
A Tree with n vertices has
n-1 edges
29
Rooted Tree (definition)
Tree in which one vertex has been designated as the root
- all edges and vertices stem from the root node
30
Binary Tree (definition)
Rooted tree where each node has at most 2 children
31
Rooted Graph (definition)
Graph where one of the nodes has been distinguished as a root
32
Rooted Tree (definition)
Tree where one of the nodes has been distinguished as a root
33
Assigning one of the nodes of a tree as a root allows us to
Talk about parents and children
34
Hashing Algorithm (definition)
A mathematical calculation performed on search criteria to find its location
35
Collision (definition) (aim) (resolution)
- When the same index is produced for different values in a hash table
- aim of a good hashing algorithm is to cut down collisions while optimising space needed
- one collision resolution strategy is to use the next free space available
36
Time Complexity of a Hash Table
Instant Time: O(1)
37
Clustering (definition)
Where lots of values are close together in a hash table
38
Process of Adding a Record to a Hash Table
- a unique attribute from the record is used to position record into table
- hash algorithm is applied to the unique attribute
- record is inserted at the location indicated by the hash value of unique attribute
- if an item is already at the location (i.e. a collision), the item is inserted into the next available location
39
Vectors
- type of structure
- can be represented as
- dynamic data structures
- list of numbers, 1D array, dictionary
40
Stack: Starting Positions of Pointers
top = -1
41
Queue: Starting Positions of Pointers
rear = -1
front = 0
42
Enqueue with Circular Queues
- check if full (if rear + 1 = front)
- if not full
- - increment rear by (rear+1) % MAX_SIZE
- - add item at the location indicated by the value of rear pointer
