2021 p1

Question 1

358164
bubble sort this into first second and 3rd pass

Answer 1

first: 351648
second: 315468
third: 134568

Question 2

define binary tree

Answer 2

a rooted tree where each node has at most two child nodes

Question 3

state the output for in-order transversal for E, H, I, Y, Q, B, C.

Answer 3

EIHCYBQ

Question 4

recursive subroutine

Answer 4

s subroutine that calls itself

Question 5

two components of a stack frame

Answer 5

local variables and parameters

Question 6

procedural decomposition

Answer 6

breaking a problem into smaller sub-problems

Question 7

steps in adding a record to a hash table

Answer 7

1. apply hash function to calculate the hash value for the key .
2. use the hash value to find the index in the hash table so that the new record could be stored.
3. check if there is a record at the index. if yes, use a collision resolution technique.
4. insert the new record at the index in the hash table and update the number of records in the hash table.

Question 8

two advantages of RPN

Answer 8

easier for a computer to analyse

don’t need brackets so you don’t have to keep track of parentheses

Question 9

how can a single stack be used to evaluate an RPN expression

Answer 9

1. initialize an empty stack
2. push values onto a stack from left hand side.
   3.for each number in the expression; push it onto a stack. for each operator; pop the top two numbers off the stack.
3. after both have been processed, the stack should contain only one value, which is the result of the expression.

Question 10

base case for a recursive sub routine

Answer 10

a scenario where a recursive subroutine does’nt call itself