Quelpr

Searching and Sorting Algorithms · CAPE Computer Science Unit 2

34 past-paper questions on Searching and Sorting Algorithms, part of Data Structures, from every CAPE Computer Science Unit 2 paper on Quelpr.

Practise Searching and Sorting Algorithms
  1. 910 marks· CAPE Computer Science Unit 2 · 2005 · Paper 1A soft-drink manufacturer sells five soft-drink flavours: banana, cherry, mango, orange and pineapple. The company knows that banana and pineapple are the two best-selling flavours and is carrying out a poll to…
  2. 910 marks· CAPE Computer Science Unit 2 · 2006 · Paper 1Trace the execution of the algorithm and draw the exact output produced.
  3. 3(a)(i)11 marks· CAPE Computer Science Unit 2 · 2006 · Paper 2Write a recursive function in pseudocode to search arr for a value named key. Return the index where it was found, or return -1 if key is not present.
  4. 3(a)(ii)5 marks· CAPE Computer Science Unit 2 · 2006 · Paper 2Write a segment of code that prompts the user for key, calls the search function in 3(a)(i), and displays an error message if not found or the location if found.
  5. 2(a)(i)10 marks· CAPE Computer Science Unit 2 · 2009 · Paper 2Write a function, lsearch, which takes an integer array arr, its size n, and a search key, performing a linear search to return the index where key is found, or -1 otherwise.
  6. 2(a)(ii)1 mark· CAPE Computer Science Unit 2 · 2009 · Paper 2Assuming key is not in arr, state how many elements of arr are checked before returning -1.
  7. 2(b)(i)10 marks· CAPE Computer Science Unit 2 · 2009 · Paper 2Describe the steps performed during a binary search of arr using an algorithm or written explanation, taking the same parameters and return values as linear search.
  8. 2(b)(ii)4 marks· CAPE Computer Science Unit 2 · 2009 · Paper 2Given arr containing: 7, 10, 15, 17, 18, 25, 35, 37, 40, 45, 50, 55, 56, 57, 58, 62, 63, 71, 75, 78, 81 and key = 40, show your working to determine how many elements will be checked before returning the correct…
  9. 2(a)(i)10 marks· CAPE Computer Science Unit 2 · 2010 · Paper 2Describe how the selection sort algorithm works to sort a set of 10 integers in ascending order.
  10. 2(a)(ii)3 marks· CAPE Computer Science Unit 2 · 2010 · Paper 2Draw the array after the first, second, and third passes of the selection sort algorithm (three diagrams in all).
  11. 2(b)10 marks· CAPE Computer Science Unit 2 · 2010 · Paper 2A one-dimensional array num contains 20 unsorted integers. Write C code to accept an integer target from the user, search for it in num, print the location if found, or print an appropriate error message if not present.
  12. 2(c)2 marks· CAPE Computer Science Unit 2 · 2010 · Paper 2State when binary search should be used on an array.
  13. 1(d)5 marks· CAPE Computer Science Unit 2 · 2011 · Paper 2Describe how an array of n items is sorted using a bubble sort algorithm.
  14. 2(b)12 marks· CAPE Computer Science Unit 2 · 2011 · Paper 2Write a C program to store and then sort the values in the given array arr using a simple selection sort.
  15. 2(c)(i)3 marks· CAPE Computer Science Unit 2 · 2011 · Paper 2Explain what is involved in linear search.
  16. 2(c)(ii)4 marks· CAPE Computer Science Unit 2 · 2011 · Paper 2Explain what is involved in binary search.
  17. 2(a)10 marks· CAPE Computer Science Unit 2 · 2012 · Paper 2Write C code that takes two integers, lower and upper (where lower < upper), and counts and prints the number of marks in an unsorted array of 100 student marks between lower and upper inclusive, printing an error…
  18. 2(b)(i)6 marks· CAPE Computer Science Unit 2 · 2012 · Paper 2Describe how a binary search algorithm will search arr for key 16, showing the portion of the array searched each iteration.
  19. 2(b)(ii)6 marks· CAPE Computer Science Unit 2 · 2012 · Paper 2Describe how a binary search algorithm will search arr for key 63, showing the portion of the array searched each iteration.
  20. 2(c)3 marks· CAPE Computer Science Unit 2 · 2012 · Paper 2Draw the array after the first, second, and third passes of the selection sort algorithm (three diagrams in all).
  21. 2(a)(i)2 marks· CAPE Computer Science Unit 2 · 2013 · Paper 2Explain the purpose of the outer 'for' loop.
  22. 2(a)(ii)3 marks· CAPE Computer Science Unit 2 · 2013 · Paper 2Explain carefully the process occurring in the inner 'for' loop.
  23. 2(a)(iii)1 mark· CAPE Computer Science Unit 2 · 2013 · Paper 2State why the upper limit for j in the inner 'for' loop is (numItems - i) rather than (numItems).
  24. 2(a)(iv)a)4 marks· CAPE Computer Science Unit 2 · 2013 · Paper 2Given the array a with 5 values: [5, 1, 4, 8, 2], show the contents of the array after each stage during the FIRST pass of the bubble sort.
  25. 2(a)(iv)b)2 marks· CAPE Computer Science Unit 2 · 2013 · Paper 2Show the contents of the array at the end of the SECOND and THIRD passes of the bubble sort.
  26. 2(b)4 marks· CAPE Computer Science Unit 2 · 2013 · Paper 2An array contains 7 integers: [34, 5, 10, 1, 9, 23, 14]. Using the selection sort algorithm, show the array contents after each of the first four passes.
  27. 2(c)6 marks· CAPE Computer Science Unit 2 · 2013 · Paper 2Describe the principles behind binary search when searching for an item in an array.
  28. 2(d)(i)1 mark· CAPE Computer Science Unit 2 · 2013 · Paper 2How many comparisons does a linear search make before determining that 50 is not present in the array?
  29. 2(d)(ii)2 marks· CAPE Computer Science Unit 2 · 2013 · Paper 2How many comparisons does a binary search make before determining that 50 is not present in the array? Show your working.
  30. 2(b)(iii)9 marks· CAPE Computer Science Unit 2 · 2014 · Paper 2Write C code to read an integer 'key' from the user and search the array 'num' for it. If found, display the location of key; otherwise, display 'Key Not found'.
  31. 2(a)6 marks· CAPE Computer Science Unit 2 · 2015 · Paper 2Draw the array after the first, second, and third passes of selection sort (3 diagrams total).
  32. 2(c)(i)2 marks· CAPE Computer Science Unit 2 · 2015 · Paper 2Write code to obtain the value of an integer, target, from the user.
  33. 2(c)(ii)10 marks· CAPE Computer Science Unit 2 · 2015 · Paper 2Write code to search for target in the sorted array numbers using binary search. Print its location if found; otherwise print -1.
  34. 2(b)(iii)9 marks· CAPE Computer Science Unit 2 · 2016 · Paper 2Write C code to prompt the user for an integer `key` and use linear search to find it in `number`. Print the location of `key` if found; otherwise, print 'Key Not found'.

Related topics in Data Structures