4-8 makers paper2

Describe how a linear search works.[4]

Compare the search item with the first value

…then compare it to the next value

…repeat the above process until either the end of the array has been reached or the search item is found and then stop.

Return the array position.

Describe one feature of an Integrated Development Enviroment (IDE that can be used to help write the program and one feature that canb be used to help test the program.[4]

Write: Auto-complete

• Starts typing an identifier and it fills in the rest.

Test: Breakpoint

• Stop the program running at a set point to check variables.

Describe how a quicksort would sort the data into ascending order.

• Choose a pivot

• Compare each element to the pivot

• put items< pivot to the left sublist.

• Put items> in the right sublist.

• Choose a pivot in each sublist

• If a pointer is larger than end pointer.. then swap data items around

• …And repeat the process until each item becomes a pivot.

Describe the steps the procedure enqueue() will follow when adding new items to the queue.[5]

• check id the queue is full

• If the firstElment pointer (+1) = lastElement if it is true return False.

• Adds element at lastElement (+1) position

• …increments last Element pointer.

• If last Element is greater than last inedx

• … reset to 0

Explain how a bubble sort algorithm sorts data. Use the current contents of processedData in your explanation.[5]

• Compare each pair of data e.g. 0 and 0.5

• If they are in the correct order it moves to the net pair e.g. 0.5 and 0.

• If there are in the wrong order it swaps them e.g. 0.5 and 0 become 0 and 0.5.

• Continues to the end of the array e.g. pass 1 complete.

• If there has been a swap it checks again e.g. Pass 2 complete.

• If there has been no swaps it is sorted.

• If there has been no swaps it is sorted.

Describe what each of these complexities mean.

Best time 0(n)

Average and worst time 0(n²)

Worst space 0(1)

[6]

Best time 0(n): Linear

• Best time grows at the same rate as the number.

• This is the case when the data is already ordered.

Average and worst time 0(n²): Polynomial/quadratic

• Worst and average time is proportional to the square of the number of elements.

Worst space 0(1):

• Constant

• Will always take the same amount of memory.

Explain how backtracking is used in depth-first (post-order) traversal.

Use the tree in Fig2.1 in your explanation [4]

Depth first starts at the root

..and goes all the way down on the branch to the bottom.

It stores which nodes it has visited.

When it cannot go any further.

…It then backtracks/returns to the previous node

And continues to backtrack until a node is reached with unvisited children

…and checks down that branch

in the tree show after visiting ...

the algorithm would backtrack to …and then visit…

Explain how a data item is removed from a linked list. (case)[4]

• traverse the list to the item immediately prior to the item to be removed.

• which is the NextPointer of the item to be removed.

• Find the value of the NextPointer of the item to be removed

• Set the nextPointer value of …. to be removed.

Describe how a merge sort would sort the given array into descending order.[6]

• Splits the list in half repeatedly.. until it its independent arrays.

• Compare the first two items and combine to create a new array in descending order.

• Repeat with the next of the indexed

• Compare the first element in the first two new arrays

• choose the largest element, writing this to the new array first repeat until no two elements left

• Combine the two remaining lists into one list