ch19/20

Question 1

State three essential features of recursion.

Answer 1

1- base case
2- general case
3- function calls itself and stops once the base case is reached

Question 2

Explain the reasons why a stack is a suitable Abstract Data Type (ADT) to implement recursion.

Answer 2

• A stack is a LIFO data structure
• Each recursive call is pushed onto the stack
• …. and is then popped as the function ends

Question 3

Describe how to perform a binary search. (4)

Answer 3

Find the middle item / index
MP2 Check the value of middle item in the list to be searched
MP3 If equal item searched for is found
MP4 If this is not equal/greater/less than the item searched for
MP5 … discard the half of the list that does not contain the search item
MP6 Repeat the above steps until the item searched for is found
MP7 … or there is only one item left in the list and it is not the item searched for

Question 4

Compare the performance of the algorithms for a binary search and a linear search using Big O notation for order of time complexity

Answer 4

MP1 Linear search O(n) and Binary search O(log
2n) / O(Log n)
MP2 time to search increases linearly in relation to the number of items in the list for a linear search and logarithmically
for a Binary search
MP3 time to search increases less rapidly for a binary search and time to search increases more rapidly for a linear
search

Question 5

State the reasons for including exception handling routines when writing a program.
Include an example of an exception in your answer

Answer 5

To trap (some) runtime errors
To prevent a program halting unexpectedly To produce meaningful error messages for these errors Example divide by zero // end of file // file not found