U3 AOS1: ADTS & Graphs

Question 1

Define ADTS

Answer 1

An abstract data type is a data structure and its allowable operations

Question 2

Define sets

Answer 2

A collection of unordered and unique elements

Question 3

Define arrays

Answer 3

A collection of elements of the same data type and a fixed length

Question 4

Define lists

Answer 4

A collection of elements of any data type and a variable length (able to be appended or removed)

Question 5

What are primitive operations?

Answer 5

Operations that
create, destroy, inspect, observe, or change the data structure

Question 6

What are dictionaries

Answer 6

Unordered collection of {key,value} pairs, where the key is unique

Question 7

What is a linked list?

Answer 7

A sequential access data structure, where each element can be accessed only in particular order.

Question 8

What is a data structure and why are they useful?

Answer 8

A data structure is a particular way of organising the data so that it can be used efficiently. They provide a means to managing large amounts of data efficiently through algorithms.

Question 9

What is an ADT

Answer 9

Combination of a data structure and its allowable operations

Question 10

What does contiguous mean?

Answer 10

Adjacent to, neighbouring, touching

Question 11

What is the role of arrays in data modelling?

Answer 11

They provide efficient access to elements by index, making them suitable for scenarios where fast random access is required.
They are useful for modelling fixed size elements, such as a book with its fixed number of pages. Other examples include coordinates

However, their fixed size is not suitable for situations where the size of the data can be changing/large

Question 12

Role of lists in data modelling

Answer 12

Since arrays are not suitable for when the size of the data may be changing, lists allow for efficient insertion and removal of elements, making them useful for
1) task management
2) scheduling,
3) data processing
They are also used to model collections of similar information (such as friends invited for a party)

Question 13

Roles of Sets in data modelling

Answer 13

They are useful when collecting SIMILAR unique objects, such as {Monday, Tuesday, wednesday} however they don’t allow for duplicate items

Question 14

Roles of Dictionaries in data modelling

Answer 14

• They store key-value pairs, allowing efficient retrieval of values based on keys. They provide operations for insertion, deletion, and retrieval based on keys.
• If you need to quickly retrieve values based on known keys without iterating through the entire collection

Question 15

Roles of Queues & Priority queues in data modelling

Answer 15

As they use the FIFO principle, they are particularly useful when we want the elements in a specific order. They are used largely in scheduling problems and project management.

Priority queues are used in hospitals (based of patient condition), or a airport runway

Question 16

Roles of Graphs in data modelling

Answer 16

Graphs are used for modelling complex relationships, or connections between specific nodes and edges, such as social networks and organisational structures.

Question 17

What is meant by modularising algorithms?

Answer 17

Grouping part of the algorithm into smaller algorithms (modules)

Question 18

Advantages of modularising algorithms

Answer 18

• Re-use modules in other places
• Easier to rewrite the modules
• Use a function before you have defined it

Question 19

What is top-down design?

Answer 19

Breaking the problem down into smaller parts
- Vision → Design → Develop

Question 20

Advantages of Top-down design:

Answer 20

-Breaking down the problem helps clarify the problem
- At each step of refinement, the new parts become easier to figure out
- Reusable parts
- Allows more than one person to work on the solution

Question 21

What principle do stacks use?

Answer 21

LIFO (last in, first out) or (FILO), just think of stack of plates for dishwashing

Question 22

What is morse code?

Answer 22

Morse code is a method that is used to encode letters of the alphabet, numbers, and punctuation marks as arrangements/sequences of 2 different “signals”, known as “dots” and “dashes”

Question 23

For real-world problems, what ADT should you use when the number of items is fixed?

Answer 23

Arrays, and if it isn’t fixed then Lists

Question 24

For real-world problems, what ADT should you use when the order of the items doesn’t matter?

Answer 24

A Set

Question 25

Define Paths

Answer 25

Sequences of vertices that are connected so that we can move from A to B

Question 26

Define forests

Answer 26

A graph that has no cycles but is not necessarily connected

Question 27

What are simple graphs?

Answer 27

Only have a single edge between any pair of vertices and no loops

Question 28

What are circuits?

Answer 28

A graph contains a circuit if there is more than one path that connects two nodes

Question 29

What are walks?

Answer 29

A walk is a sequence of edges, each edge connecting successive nodes

Question 30

What are trails?

Answer 30

A trail is a walk with no repeated edges.

Question 31

What is a cycle

Answer 31

A path that starts and ends on the same node

Question 32

What is a binary search tree?

Answer 32

A binary tree where every node in the left subtree is less than the root, and every node in the right subtree is greater than the root

Question 33

How does insertion work in a binary search tree

Answer 33

The new element is compared with the current node’s value. If the element is less than the node’s value, it is inserted to the left of the subtree, if it is greater, it is inserted to the right

Question 34

Complete Graphs

Answer 34

Every node is adjacent to every other vertex

Degree (No. of edges incident to a vertex) = ∣V∣−1
Number of edges = V(V-1)/2
​