Algorithms

Question 1

What is an algorithm?

Answer 1

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

Question 2

What is graph traversal?

Answer 2

The process of visiting each vertex in a graph

Question 3

Name the two types of graph traversal

Answer 3

Depth-first search and breadth-first search

Question 4

Which traversal is best for navigating 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 type of graphs can be traversed?

Answer 8

Connected graphs

Question 9

Can a tree undergo depth-first traversal?

Answer 9

Yes- although it might be more appropriate to use a tree-traversal

Question 10

Can a graph traversal start from any node?

Answer 10

Yes

Question 11

What is tree-traversal?

Answer 11

The process of visiting updating or outputting each node in a tree- it is an algorithm

Question 12

Name the three types of tree-traversal

Answer 12

Preorder- inorder and postorder

Question 13

Name a use of postorder traversal

Answer 13

Emptying a tree, Infix to RPN (reverse polish notation) conversions, Producing a postfix expression from an expression tree

Question 14

Which traversal would be used for copying a tree?

Answer 14

Preorder traversal

Question 15

Name a use of inorder traversal

Answer 15

Outputting the contents of a binary search tree in ascending order

Question 16

Can inorder traversal be performed on any tree?

Answer 16

No- only binary trees (including binary search trees)

Question 17

Can preorder traversal be performed on any tree?

Answer 17

Yes

Question 18

Can postorder traversal be performed on any tree?

Answer 18

Yes

Question 19

Where does tree traversal start?

Answer 19

At the root

Question 20

How do traversals work their way around the tree?

Answer 20

Anticlockwise

Question 21

How would In-Order traversal work

Answer 21

Left, Root, Right. Start from furthest left and go to right

Question 22

How would Post-Order traversal work

Answer 22

Left, Right, Root. Start from furthest left and check each leaf node, go up the last one until one before root, switch to other leaf node on other side and repeat.

Question 23

How would Pre-Order traversal work

Answer 23

Root, Left sub-tree, Right sub-tree. Start from top and work down each sub-node

Question 24

What is the benefit of reverse Polish notation?

Answer 24

It eliminates the need for brackets

Question 25

Convert the infix expression 14 + 6 to reverse Polish

Answer 25

14 6 +

Question 26

Convert the infix expression (12 - 4) × (3 + 5) to reverse Polish

Answer 26

12 4 - 3 5 + ×

Question 27

Convert the reverse Polish expression 13 6 + 4 - to infix

Answer 27

(13 + 6) - 4

Question 28

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

Answer 28

4 2 - 3 × 9 +

Question 29

Convert the reverse Polish expression 4 6 7 + - to infix

Answer 29

4 - (6 + 7)

Question 30

Which is not an example of where reverse Polish is used?

Answer 30

PreScript

Question 31

What is the result of the reverse Polish expression 2 8 × 2 4 - × ?

Answer 31

-32

Question 32

What is the result of the reverse Polish expression 4 6 8 - - ?

Answer 32

6

Question 33

What is a searching algorithm used for?

Answer 33

A searching algorithm is used to find a specified data item within a set of data

Question 34

Time complexity of linear search

Answer 34

O(N)

Question 35

What must be true about a set of data if it is to be searched using the binary search algorithm?

Answer 35

The set of data must be sorted

Question 36

Which is most efficient- binary search or linear search?

Answer 36

Binary search

Question 37

Time complexity of binary search

Answer 37

O(LogN)

Question 38

Calculation used to find the midpoint of a set of data

Answer 38

Add the first and last positions of the data and divide by two

Question 39

Time complexity of binary tree search

Answer 39

O(LogN)

Question 40

What is a binary tree?

Answer 40

A rooted- ordered tree in which each node has no more than 2 children

Question 41

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

Answer 41

Merge sort

Question 42

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

Answer 42

Merge sort

Question 43

What is the time complexity of the bubble sort algorithm?

Answer 43

O(n^2)

Question 44

What is the time complexity of the merge sort algorithm?

Answer 44

O(nlogn)

Question 45

What is the purpose of an optimisation algorithm?

Answer 45

To find the best possible solution to the problem posed

Question 46

What is the purpose of Dijkstra’s algorithm?

Answer 46

To find the shortest path between two nodes in a network

Question 47

Which is not an example of where Dijkstra’s algorithm is used?

Answer 47

Binary tree search