4.2 Data Structures

Question 1

Static vs Dynamic Data Structures
- when size is determined
- storage

Answer 1

• 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

Question 2

Enumerated (definition)

Answer 2

In the form of a list

Question 3

Arrays (2)

Answer 3

• elements must be of the same data type
• objects are mutable

Question 4

Lists (3)

Answer 4

• elements can be of different data types
• objects are mutable
• is a dynamic data structure

Question 5

Tuples (3)

Answer 5

• elements can be of different data types
• objects are immutable
• more efficient than lists since are immutable

Question 6

Text Files can only store

Answer 6

Strings

Question 7

Advantage of Text Files

Answer 7

They can be created, altered or prepared independently from the program

Question 8

Binary Files (3)

Answer 8

• 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

Question 9

CSV Files (4)

Answer 9

• 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

Question 10

Types of Access of Files
- read
- write
- append
- read binary file
- write to binary file

Answer 10

• r = read
• w = write (overwrites entire file)
• a = append
• rb = read binary file
• wb = write to binary file

Question 11

Queues
- Acronym
- Number of Pointers

Answer 11

• FIFO (First In First Out)
• 2 pointers: rear and front

Question 12

Linear Queues
- type of structure
- queue = empty if …
- disadvantage

Answer 12

• static data structure
• queue = empty if front > rear
• dis: limited amount of space

Question 12

Circular Queues
- definition
- what pointers store

Answer 12

• 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

Question 13

Priority Queues (2 + Enqueue)

Answer 13

• 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

Question 14

Enqueue Algorithm

Answer 14

• 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

Question 15

Push Function + Algorithm

Answer 15

• 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

Question 15

Stack
- type of structure
- acronym
- no. pointers

Answer 15

• static data structure
• LIFO (Last In First Out)
• 1 pointer: top

Question 15

Dequeue Algorithm

Answer 15

• 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

Question 16

Pop Function + Algorithm

Answer 16

• 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

Question 17

Peek Function + Algorithm

Answer 17

• returns value at the top of stack without removing it
• return stackarray[top]

Question 18

Test for Empty Stack AKA + Algorithm

Answer 18

• known as stack underflow
• if top == -1
• • return True

Question 19

Test for Full Stack AKA + Algorithm

Answer 19

• known as stack overflow
• if top == max
• • return True

Question 20

Method to Reverse the Order of a List Using a Stack

Answer 20

• 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

Question 21

Method to Reverse the Order of a Queue Using a Stack

Answer 21

• elements of queue are dequeued from queue
• elements are then pushed onto stack
• elements are popped off stack
• elements are enqueued to queue

Question 22

Graph (definition)

Answer 22

Has a set of vertices and edges where each edge joins two vertices

Question 23

Labelled Graph (definition)

Answer 23

One that has its vertices associated with a label

Question 24

Directed Graph (definition)

Answer 24

Graph that consists of arcs and vertices where every arc connects two vertices and has a direction

Question 25

Weighted Graph (definition)

Answer 25

Graphs where every edge is given a weight

Question 26

Adjacency Matrix vs List

Answer 26

- 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

Question 27

Tree (definition)

Answer 27

Connected undirected graph with no cycles

Question 28

A Tree with n vertices has

Answer 28

n-1 edges

Question 29

Rooted Tree (definition)

Answer 29

Tree in which one vertex has been designated as the root - all edges and vertices stem from the root node

Question 30

Binary Tree (definition)

Answer 30

Rooted tree where each node has at most 2 children

Question 31

Rooted Graph (definition)

Answer 31

Graph where one of the nodes has been distinguished as a root

Question 32

Rooted Tree (definition)

Answer 32

Tree where one of the nodes has been distinguished as a root

Question 33

Assigning one of the nodes of a tree as a root allows us to

Answer 33

Talk about parents and children

Question 34

Hashing Algorithm (definition)

Answer 34

A mathematical calculation performed on search criteria to find its location

Question 35

Collision (definition) (aim) (resolution)

Answer 35

- 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

Question 36

Time Complexity of a Hash Table

Answer 36

Instant Time: O(1)

Question 37

Clustering (definition)

Answer 37

Where lots of values are close together in a hash table

Question 38

Process of Adding a Record to a Hash Table

Answer 38

- 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

Question 39

Vectors - type of structure - can be represented as

Answer 39

- dynamic data structures - list of numbers, 1D array, dictionary

Question 40

Stack: Starting Positions of Pointers

Answer 40

top = -1

Question 41

Queue: Starting Positions of Pointers

Answer 41

rear = -1 front = 0

Question 42

Enqueue with Circular Queues

Answer 42

- 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