1.4.2 Data Structures & in Paper 2

Question 1

What is a Graph?

Answer 1

An abstract data structure used to show relationships between items.

Question 2

What is the definition for Node/Vertex?

Answer 2

An item, or piece of data

Question 3

What is an Edge/Arc?

Answer 3

A relationship between nodes.

Question 4

Describe a Weighted Graph

Answer 4

Each edge has a value, or a cost to travel.

Question 5

Describe an unweighted graph

Answer 5

Edges have no values or costs.

Question 6

What is a Directed Graph?

Answer 6

Edges can only be traversed in one direction.

Question 7

What is an Adjacency Matrix?

Answer 7

A table to show the relationships in a graph.

Question 8

What is an Undirected Graph?

Answer 8

Edges can be traversed in any direction.

Question 9

What is an Adjacency List?

Answer 9

A space-efficient way to store the relationships in a graph.

Question 10

What is the definition of Static?

Answer 10

Structures with a fixed length.

Question 11

What is the definition of Dynamic?

Answer 11

Structures with a changeable length.

Question 12

What is the definition of Array?

Answer 12

A static, ordered set of elements of the same type

Question 13

What is the definition of Tuple?

Answer 13

• A static, ordered set of elements of any type.
• Immutable.

Question 14

What is a 2D array?

Answer 14

• An array that contains other arrays.
• Often used to store tables

Question 15

What is a Linked List?

Answer 15

• An abstract, dynamic data structure…
• Which holds ordered data from different locations

Question 16

What are the steps in inserting an item into linked lists?

Answer 16

• Use nextFree to place the item in the next free node
• Follow pointers from start until you find the node with data greater than the item.
• Change the pointer of the previous node to point to your item.
• Change the pointer of your item to point to the next code.

Question 17

What is a List?

Answer 17

An abstract data structure that stores a number of items.

Question 18

What is the general method to adding items to an ordered list?

Answer 18

Is the list full? If so, stop.
REPEAT:
If targetIndex<nextIndex:
move all items along by 1
insert them
ELSE:
Look at next list item.

Question 19

What is Depth-first traversal ?

Answer 19

Read a graph by going as far down each route as
you can before backtracking.

Question 20

What is Breadth-first traversal ?

Answer 20

Read a graph by checking all available routes
from a node before progressing.

Question 21

What is a Binary Search Tree ?

Answer 21

A rooted tree where each node has a maximum of two children.
Makes data easy to search.

Question 22

What are the 3 ways you can be traversing a binary tree ?

Answer 22

• Pre-order (to the left)
• In order (underneath)
• Post-order (to the right)

Question 23

What is abstract data structure?

Answer 23

A data structure made by the
programmer.

Question 24

What is a Queue ?

Answer 24

A static, first-in-first-out structure for
ordering data.

Question 25

What does enQueue(item) do ?

Answer 25

Add an item to the rear of the list.

Question 26

What does deQueue() do ?

Answer 26

Remove the item from the front of the
list.

Question 27

What does isEmpty()/isFull() do ?

Answer 27

Check if the list is empty / is full.

Question 28

What is a Stack ?

Answer 28

A Last In First Out (LIFO) data structure.
Usually used to store instructions.

Question 29

What is the Call Stack ?

Answer 29

A structure to hold the active subroutines
and their data.