2.3 Algorithms extra

Question 1

Process of pushing to a stack()

Answer 1

Check if the stack is full (pointer =
array.length/array.length+1)
If it is not ¡V insert the item
If it is ¡V return/error that the stack is
full

Question 2

Process of pushing to a stack()

Answer 2

line 02
Include an OR with variations (e.g.
userAnswer = “PUSH” OR
userAnswer = “Push” etc.)/Convert
input to uppercase/lowercase and just
compare to equivalent

Question 3

Describe how a 1D array can be set up and used to push and pop items as a stack.

Answer 3

Array size defined
A stack pointer is used to point to the
top of the stack
When an item is pushed the stack
pointer is incremented
When an item is popped the stack
pointer is decremented

Question 4

Explain how a linear search would check if the departure station exists in the array.

Answer 4

Start at the first item (Cavalry)
Compare with departure station ‘Bridge
Heights’
If matched, report found
Otherwise continue to the next item in
list (Bridge)
Continue until item found, or end of list
reached…
and then False returned

Question 5

Describe the stages of a binary search on an array of size n.

Answer 5

Repeat
Calculating an array midpoint…
…by adding the array lower bound to
the array upper bound, dividing by 2
and rounding
Compare array midpoint with value to
search for…
…if equal set found flag to true
…if array midpoint < value to search
for, change lowerbound to equal
midpoint + 1
…if array midpoint > value to search
for, change upperbound to equal
midpoint - 1
Until lowerbound is greater than or
equal to upperbound
Return/output found flag

Question 6

Pre condition for tree to be searched

Answer 6

Binary tree and ordered/sorted

Question 7

Describe the disadvantages of using a bubble sort.

Answer 7

Bubble sort is an inefficient algorithm…
Meaning it will take more
time/processing cycles to sort the list.
Generally outperformed by Insertion
sort/quick sort/ merge sort (accept any
other sensible sorting algorithm)
The item to be sorted is at the end of
the list (and so can only move back
one place per pass) which is the worst
case scenario for bubble sort

Question 8

dentify the characteristic of this problem that minimises the disadvantages of a bubble sort.

Answer 8

There are only a small number of data
items

Question 9

Describe how an insertion sort is performed.

Answer 9

One item at a time / serially …
…moved into correct position…
…until all items in list checked