GCSE Computing Flash Quiz

What is a merge sort?

Show the stages in the merge sort for the following:

{38, 27, 43, 3, 9, 82, 10}

• 
• Divide and Conquer method suitable for large lists, or lists that are more unordered

Show how an insertion sort works

• 
• You have a sorted and unsorted list, with the sorted list usually on the left. Each new item from the unsorted list is then inserted into the sorted list. Like sorting out a hand of playing cards

What is abstraction?

• Getting rid of unnecessary detail and concentrating on the important parts.

  You must use the word "unnecessary"

  It makes things less complicated, which means its quicker and simpler to program.

• .

What is Decomposition?

• Breaking a problem down into smaller parts the are easier to understand.

  Problem >> Sub-problem >> smaller parts until each problem can be solved

• .

How does Binary Search work?

• The list must be sorted for this search method to work.

  
  

  Split the list into two equal lists (find the midpoint)

  Compare search term (target value) with midpoint.

  If target value greater than midpoint, discard the first half. If lesser, discard the second half.

  Repeat until item is found

  
  

  NB if the list has an even number of items N, then the mid point is the N / 2 item. For odd numbers of items, the mid point is the item in the middle (N/2 rounded up)

  
  

  If a question asks you to compare to Linear Search, use the word "whereas" in your answer. E.g., a binary search requires a sorted list, whereas a linear list does not

• .

How does Linear Search work?

• Linear search can work on unsorted lists

  
  

  Each item on the list is taken in turn and compared to the target value, until it is found! Or until the entire list is checked and the item is not included

  
  

  If a question asks you to compare to Binary Search, use the word "whereas" in your answer. E.g., a binary search requires a sorted list, whereas a linear list does not

• .

How does bubble sort work?

• Takes a list and compares the first 2 values. If the second is less than the first, do a swap.

  Then continue and compare each "pair" of adjacent items along the list, and swap where needed. Continue until the end of the list is reached.

  Then repeat from the start

  Keep repeating until the order of the list doesn't change

  
  

  Low values "bubble" to the top of the list, and large values "sink" to the bottom of the list.

  
  

  The bubble sort is simple to understand, but inefficient in most cases compared to e.g., insertion sort

• .

What is an array?

• An array is a group of data items usually of the same data type, stored under one name, in memory locations one after another (contiguous)

• .

When would you use a 2D array? How would you access the 2nd row 5th column?

• A 2D array can be used to store a table of data, e.g., 10 test scores for 30 students.

  
  

  Arrays start at Row 0 Column 0.

  
  

  So the 2nd row 5th column of array "ClassScores" is ClassScores[1][4]

• .

What is the pseudo code for reading from a file?

• my_file = openRead("sample.txt")

  x = my_file.readline()

  my_file.close()

• .