Data Structures

Question 1

What is a 1 dimensional array defined as?

Answer 1

a finite set of elements of the same data type

Question 2

What is a tuple?

Answer 2

A set of values which can be of any data type, but can not be changed.

Question 3

What makes up a record?

Answer 3

several fields that each contain one item of data

Question 4

What is an abstract data type?

Answer 4

A data type that has been created by the programmer.

Question 5

How does a queue work?

Answer 5

Data can only be added to the end and Data can only be retrieved from the front.

Question 6

Give some common examples of abstract data types? (4 things)

Answer 6

Queues, stacks, graphs and lists

Question 7

What is a dynamic data structure?

Answer 7

A data structure that is able to increase or decrease the amount of space in memory it takes up.

Question 8

What is the heap?

Answer 8

A portion of memory of which space is automatically allocated or de-allocated as required. This allows for dynamic data structures.

Question 9

What is the main drawback of using dynamic data structures?

Answer 9

They can cause an overflow if they exceed the maximum memory limit which will cause data to be lost and the program to crash.

Question 10

What are examples of dynamic data structures? (2 things)

Answer 10

queues, stacks

Question 11

What is a static data structure?

Answer 11

A data structure that is fixed in size

Question 12

What is an example of a static data structure?

Answer 12

array

Question 13

What is the difference between a priority queue and a normal queue

Answer 13

In a priority queue the items are removed from the queue based on their priority, with the item with the highest priority being removed first, rather than being removed in the order they were added to the queue.

Question 14

What is a list?

Answer 14

An abstract data type made up of items, in which the same item may occur more than once.

Question 15

What does each node in a linked list contain?

Answer 15

The data field and a pointer field that points to the next item in the list

Question 16

How does a stack work?

Answer 16

If you want to remove an item, you have to remove the item that was added most recently.

Question 17

How does a hash table work?

Answer 17

The data being stored is passed into a hashing algorithm that generates an address, the data is then stored at that address in the hash table.

Question 18

What is a graph?

Answer 18

A graph is a set of nodes connected by edges. An edge can have a weight to show the cost to traverse it and a direction in which it must be traversed.

Question 19

What is a depth first traversal of a graph?

Answer 19

You go as far down one route as you can before backtracking until you can take a new route.

Question 20

What is a breadth first traversal of a graph?

Answer 20

We visit all the neighbours of the root node, and then all the neighbours of the first node visited, and then all the neighbours of the second node and so on.

Question 21

What is a binary tree?

Answer 21

A graph where each node, apart from the root node, has one parent and a maximum of two children.

Question 22

What is a pre-order traversal of a binary tree?

Answer 22

Draw an outline around the tree starting with at the root node and moving left. Output the data in each node as you pass to the left of it.

Question 23

What is an in-order traversal of a binary tree?

Answer 23

Draw an outline around the tree starting with at the root node and moving left. Output the data in each node as you pass under it.

Question 24

What is a post-order traversal of a binary tree?

Answer 24

Draw an outline around the tree starting with at the root node and moving left. Output the data in each node as you pass to the right of it.