Fundamentals of Algorithms

Question 1

What is Graph Traversal

Answer 1

Graph Traversal is the process of visiting each vertex in a graph.

Question 2

What is an algorithm

Answer 2

A set of instructions which completes a task in a finite time and always terminates

Question 3

Name the two types of graph traversal

Answer 3

Depth-first search and breadth-first search

Question 4

Which type of graph traversal is best for a maze

Answer 4

Depth-first search

Question 5

What is Breadth-first traversal useful for?

Answer 5

Shortest path on an unweighted graph

Question 6

What abstract data type is used for a breadth-first traversal

Answer 6

Queue

Question 7

What abstract data type is used in a depth-first traversal

Answer 7

Stack

Question 8

What requirement must a graph have to be searched

Answer 8

it must be connected.

Question 9

What is tree traversal

Answer 9

The process of visiting/updating/outputting each node in a tree

Question 10

Name the three types of tree traversal

Answer 10

Preorder, inorder and postorder

Question 11

Name a use of postorder tree traversal

Answer 11

Infinix to RPM
Producing a postfix expression from an expression tree

Question 12

Name a use of inorder tree traversal

Answer 12

Outputting the contents of a binary search tree in ascending order

Question 13

Can an inorder traversal be performed on any tree

Answer 13

no, it must be a binary tree, however postorder and preorder can be performed on any tree

Question 14

How do tree traversals work their way around the tree?

Answer 14

anticlockwise

Question 15

Why is reverse polish notation used

Answer 15

RPN eliminates the need for brackets, aswell as being easier to work with in computers.

Question 16

Convert the following infix expression to reverse polish
14 + 6

Answer 16

14 6 +

Question 17

Convert the following infix expression to reverse polish
(12 - 4) x (3 + 5)

Answer 17

12 4 - 3 5 + x

Question 18

Convert the following reverse polish expression to infix
13 6 + 4 -

Answer 18

(13 + 6) - 4

Question 19

Convert the following infix expression to reverse polish
3(4 - 2) + 9

Answer 19

4 2 - 3 x 9 +

Question 20

Convert the following reverse polish expression to infix
4 6 7 + -

Answer 20

4 - (6 + 7)

Question 21

what is the result of this reverse polish expression
2 8 x 2 4 - x

Answer 21

(2 x 8) x (2 - 4) = -32

Question 22

What is the result of this reverse polish expression
4 6 8 - -

Answer 22

4 - (6 - 8) = 6

Question 23

Which searching algorithm requires data to be sorted before starting

Answer 23

Binary search

Question 24

What is the time complexity of a binary search

Answer 24

O(logn)

Question 25

What searching algorithm has a time complexity of O(n)

Answer 25

Linear search

Question 26

Which sorting algorithm is most time efficient: bubble sort or merge sort

Answer 26

merge sort

Question 27

Which sorting algorithm is an example of a divide and conquer algorithm

Answer 27

merge sort

Question 28

What is the time complexity of the bubble sort algorithm

Answer 28

O(n^2)

Question 29

What is the time complexity of the merge sort algorithm

Answer 29

O(nlogn)

Question 30

What is the purpose of an optimisation algorithm

Answer 30

To find the best possible solution to the problem posed.

Question 31

What is the purpose of Dijkstra’s algorithm

Answer 31

To find the shortest path between two nodes in a network