Now test yourself

Question 1

Explain what data structure should be used in a breadth first search: (2)

Answer 1

A queue as each newly discovered node is added to the rear of the queue and queues are discovered in the order they are found.

Question 2

State one potential use for a breadth first search: (1)

Answer 2

shorted path through an unweighted graph

Question 3

Explain what data structure should be used in a depth first search: (2)

Answer 3

A stack as each newly discovered node is inspected immediately and the route can be stepped through in reverse (popped) to find a new path.

Question 4

State one potentially use for a Depth first search (1)

Answer 4

Navigating a maze

Question 5

Which tree traversal algorithm will print the value of the root node as the last line? (1)

Answer 5

Post order traversal

Question 6

which tree traversal algorithm would be most suitable for copying a tree? (1)

Answer 6

Pre order traversal

Question 7

Describe two possible uses for post order traversal: (2)

Answer 7

Emptying a tree
Converting from infix to post fix notation (RPN)

Question 8

Which tree traversal algorithm can be used to output a list in ascending order? (1)

Answer 8

In order traversal

Question 9

What type of algorithm is a binary search algorithm? (1)

Answer 9

an example of a divide and conquer algorithm

Question 10

Give one disadvantage of using linear search (1)

Answer 10

inefficient for large lists

Question 11

Give two situations where linear search would be an appropriate choice (2)

Answer 11

If a list is unordered or if the list is small

Question 12

Suggest one advantage of using binary search over linear search (1)

Answer 12

Binary search is much quicker than linear search for large sorted lists

Question 13

State one Disadvantage of using a instead of Linear search (1)

Answer 13

List must be sorted for a binary search

Question 14

Why is a binary search more efficient than a linear search? (2)

Answer 14

The list of possible values is halved each time.

Question 15

State the number of comparisons needed to run through one pass of the bubble sort for a lost of 10 items:

Answer 15

10

Question 16

Suggest to methods for improving the efficiency of the standard Bubble sort: (2)

Answer 16

after each pass check if a swap has been made - if no swap has been made then the list can be assumed to be sorted.

reduce the number of comparisons after each pass by one because the highest value is guaranteed to have bubbled to the end each time.

Question 17

Give two situations in which merge sort would be more suitable than bubble sort (2)

Answer 17

Large lists

Question 18

Give one situation in which bubble sort is more suitable than merge sort? (1)

Answer 18

Some lists that are nearly in order since merge sort has a fixed number of steps.