Quelpr

Abstract Data Types (ADTs) · CAPE Computer Science Unit 2

69 past-paper questions on Abstract Data Types (ADTs), part of Data Structures, from every CAPE Computer Science Unit 2 paper on Quelpr.

Practise Abstract Data Types (ADTs)
  1. 12(a)(i)3 marks· CAPE Computer Science Unit 2 · 2005 · Paper 1By showing each step in the processing of the input string, determine the output that the Mystery algorithm will generate given the input string: ( ) )
  2. 12(a)(ii)4 marks· CAPE Computer Science Unit 2 · 2005 · Paper 1By showing each step in the processing of the input string, determine the output that the Mystery algorithm will generate given the input string: ( ( ) )
  3. 12(a)(iii)2 marks· CAPE Computer Science Unit 2 · 2005 · Paper 1By showing each step in the processing of the input string, determine the output that the Mystery algorithm will generate given the input string: ( ( )
  4. 12(b)1 mark· CAPE Computer Science Unit 2 · 2005 · Paper 1Deduce the purpose of the Mystery algorithm.
  5. 12(a)1 mark· CAPE Computer Science Unit 2 · 2006 · Paper 1Identify the first number inserted into Q1.
  6. 12(b)2 marks· CAPE Computer Science Unit 2 · 2006 · Paper 1State TWO ADT operations of a queue.
  7. 12(c)5 marks· CAPE Computer Science Unit 2 · 2006 · Paper 1Write an algorithm using only queue ADT operations to remove all elements from Q1 and insert them into an initially empty queue Q2.
  8. 12(d)2 marks· CAPE Computer Science Unit 2 · 2006 · Paper 1Draw a diagram showing the elements of Q2 after three elements have been transferred from Q1 to Q2.
  9. 1510 marks· CAPE Computer Science Unit 2 · 2006 · Paper 1Using only stack ADT operations, write an algorithm to calculate the sum of every other element in S.
  10. 4(a)9 marks· CAPE Computer Science Unit 2 · 2006 · Paper 2A list L1 contains 100 elements, and a list L2 of size 150 has 20 elements stored in its first 20 locations (indices 0 to 19). Write an algorithm to move all elements of L1 to L2 starting at the first location of L2,…
  11. 4(b)7 marks· CAPE Computer Science Unit 2 · 2006 · Paper 2Given that L1 contains 100 integer elements, write an algorithm to reverse the elements of L1.
  12. 6(b)(ii)3 marks· CAPE Computer Science Unit 2 · 2006 · Paper 2Write a code fragment to create/instantiate a named data structure to store all Product objects and add the two Product objects from 6(b)(i) to it.
  13. 6(b)(iii)5 marks· CAPE Computer Science Unit 2 · 2006 · Paper 2Write code to print the names of all Product objects in the data structure that need to be reordered.
  14. 1(a)(i)4 marks· CAPE Computer Science Unit 2 · 2009 · Paper 2Describe how to implement the pop, push, and isEmpty stack operations for storing integers using static computer storage.
  15. 1(a)(ii)5 marks· CAPE Computer Science Unit 2 · 2009 · Paper 2Write C code for a function implementing the push(Stack, data) operation for integer data, properly handling stack overflow conditions.
  16. 1(b)10 marks· CAPE Computer Science Unit 2 · 2009 · Paper 2Assuming stk is initially empty, determine the output of the provided algorithm when n is 9 and expr is '923*-82/+', and draw the stack on each iteration of the for loop.
  17. 1(c)6 marks· CAPE Computer Science Unit 2 · 2009 · Paper 2Explain how a stack can be used to determine if a string is a palindrome (e.g. 'madam').
  18. 1(a)2 marks· CAPE Computer Science Unit 2 · 2010 · Paper 2Define the term abstract data type (ADT).
  19. 1(b)(i)1 mark· CAPE Computer Science Unit 2 · 2010 · Paper 2Give an ADT operation that can be used to store an element in a singly linked list.
  20. 1(b)(ii)3 marks· CAPE Computer Science Unit 2 · 2010 · Paper 2A singly linked list is created and elements 25, 50, 75 are placed in that order. Draw the list after all three elements have been placed using the operation from (b)(i), clearly indicating the beginning and end of the…
  21. 1(c)(i)4 marks· CAPE Computer Science Unit 2 · 2010 · Paper 2The Queue ADT provides enqueue(Queue, data) and dequeue(Queue) operations. Suppose a Queue must be implemented for storing integers. Describe the computer storage used for implementing the queue operations.
  22. 1(c)(ii)5 marks· CAPE Computer Science Unit 2 · 2010 · Paper 2Write C code for a function that implements enqueue(Queue, data) assuming data is an integer, handling queue overflow conditions.
  23. 1(d)6 marks· CAPE Computer Science Unit 2 · 2010 · Paper 2Given a queue q with elements, and stack stk with operations pop, push, and isEmpty, write an algorithm to reverse the order of all elements in q using only Stack and Queue ADT operations.
  24. 1(e)4 marks· CAPE Computer Science Unit 2 · 2010 · Paper 2Explain how Stack ADT operations are implemented if a singly linked list is used.
  25. 1(a)(i)2 marks· CAPE Computer Science Unit 2 · 2011 · Paper 2Define the term 'Abstract Data Type' (ADT).
  26. 1(a)(ii)3 marks· CAPE Computer Science Unit 2 · 2011 · Paper 2Explain how a stack ADT is implemented.
  27. 1(b)8 marks· CAPE Computer Science Unit 2 · 2011 · Paper 2Write an algorithm to remove an element that is at the bottom of a stack, maintaining the relative positions of the remaining elements. (An appropriate auxiliary structure may be used.)
  28. 1(c)7 marks· CAPE Computer Science Unit 2 · 2011 · Paper 2Given the circular queue shown in the diagram, draw a diagram illustrating the queue after inserting letters L and Y, removing three letters, and then inserting letters E and Z.
  29. 2(a)6 marks· CAPE Computer Science Unit 2 · 2011 · Paper 2Using a labelled diagram, explain what a linked list is.
  30. 1(a)(i)3 marks· CAPE Computer Science Unit 2 · 2012 · Paper 2Explain the difference between the Stack ADT and the C implementation of the stack.
  31. 1(a)(ii)4 marks· CAPE Computer Science Unit 2 · 2012 · Paper 2Declare the variables needed for implementing the stack in C and describe the purpose of each, assuming it stores at most 100 integer elements.
  32. 1(a)(iii)8 marks· CAPE Computer Science Unit 2 · 2012 · Paper 2Write C code for push(element) and pop() operations, accounting for overflow and underflow conditions.
  33. 1(b)4 marks· CAPE Computer Science Unit 2 · 2012 · Paper 2Given an initially empty linked list with an insert operation at the beginning, draw the linked list after inserting 43, 38, 25 in order, clearly indicating the beginning and ending of the list.
  34. 1(c)6 marks· CAPE Computer Science Unit 2 · 2012 · Paper 2Given a queue q with an unknown number of elements and a stack stk, write an algorithm using only Stack and Queue ADT operations to reverse the order of elements in q.
  35. 1(a)(i)2 marks· CAPE Computer Science Unit 2 · 2013 · Paper 2Write code to declare the variables required for the stack.
  36. 1(a)(ii)4 marks· CAPE Computer Science Unit 2 · 2013 · Paper 2Write a function to push a character, c, onto the stack, accounting for stack overflow.
  37. 1(a)(iii)6 marks· CAPE Computer Science Unit 2 · 2013 · Paper 2Write a function to pop a character from the stack, accounting for stack underflow.
  38. 1(b)(i)7 marks· CAPE Computer Science Unit 2 · 2013 · Paper 2Explain what a 'linked list' is using a labelled diagram.
  39. 1(b)(ii)a)3 marks· CAPE Computer Science Unit 2 · 2013 · Paper 2With the aid of a diagram, explain how a new node can be inserted at the top of the linked list.
  40. 1(b)(ii)b)3 marks· CAPE Computer Science Unit 2 · 2013 · Paper 2With the aid of a diagram, explain how a new node can be inserted at the bottom of the linked list.
  41. 1(a)(i)1 mark· CAPE Computer Science Unit 2 · 2014 · Paper 2State whether a stack must exist prior to executing CreateStack.
  42. 1(a)(ii)1 mark· CAPE Computer Science Unit 2 · 2014 · Paper 2State whether a stack must exist prior to executing DestroyStack.
  43. 1(b)(i)7 marks· CAPE Computer Science Unit 2 · 2014 · Paper 2Determine the contents of the stack following the given sequence of procedure calls, showing all steps involved: Push(Stack, X), Push(Stack, Y), Add(Stack), Push(Stack, Z), Push(Stack, W), Mult(Stack), Add(Stack).
  44. 1(b)(ii)1 mark· CAPE Computer Science Unit 2 · 2014 · Paper 2State ONE condition that must exist for the Add and Mult procedures to work effectively.
  45. 1(b)(iii)2 marks· CAPE Computer Science Unit 2 · 2014 · Paper 2Explain what will happen to the stack if the ADD operation is continuously applied to it.
  46. 1(c)(i)5 marks· CAPE Computer Science Unit 2 · 2014 · Paper 2Explain the purpose of Enqueue() and Dequeue() in a FIFO queue.
  47. 1(c)(ii)8 marks· CAPE Computer Science Unit 2 · 2014 · Paper 2Write an algorithm CountQueue using only the standard queue Abstract Data Type (ADT) operations that returns an integer count of the elements in the queue.
  48. 2(a)10 marks· CAPE Computer Science Unit 2 · 2014 · Paper 2Explain how the numbers 5 and 15 would be inserted into the singly linked list and draw the final linked list.
  49. 2(b)(i)2 marks· CAPE Computer Science Unit 2 · 2014 · Paper 2Write C code to declare an array 'num' that can store 100 integers.
  50. 2(b)(ii)4 marks· CAPE Computer Science Unit 2 · 2014 · Paper 2Write C code to fill the array 'num' with integers entered by the user.
  51. 1(a)2 marks· CAPE Computer Science Unit 2 · 2015 · Paper 2Explain why stacks and queues are classified as ADTs.
  52. 1(b)6 marks· CAPE Computer Science Unit 2 · 2015 · Paper 2Describe the primary differences between stacks and queues, providing a real-life example to illustrate how each ADT can be used.
  53. 1(c)(i)7 marks· CAPE Computer Science Unit 2 · 2015 · Paper 2Write a C function to add an integer to a stack, with the stack and the integer value as arguments.
  54. 1(c)(ii)7 marks· CAPE Computer Science Unit 2 · 2015 · Paper 2Write a C function to add an integer to a queue, taking the queue and the integer to be added as arguments.
  55. 1(d)3 marks· CAPE Computer Science Unit 2 · 2015 · Paper 2Letters A, C, X, and E have been added to a stack in that order. Draw a diagram showing how letter C can be removed from the stack, showing the stack's contents at each stage.
  56. 2(b)(i)3 marks· CAPE Computer Science Unit 2 · 2015 · Paper 2Draw a diagram to show the linked list.
  57. 2(b)(ii)4 marks· CAPE Computer Science Unit 2 · 2015 · Paper 2Explain how to delete the integer 3 from the linked list.
  58. 1(a)(i)1 mark· CAPE Computer Science Unit 2 · 2016 · Paper 2Identify which data structure would be most appropriate for a call centre to ensure calls are answered in first-in, first-out order.
  59. 1(a)(ii)1 mark· CAPE Computer Science Unit 2 · 2016 · Paper 2Identify which data structure would be most appropriate to allow the 'Undo' button to operate correctly in a word processing application.
  60. 1(a)(iii)1 mark· CAPE Computer Science Unit 2 · 2016 · Paper 2Identify which data structure would be most appropriate to store an unknown number of data items and subsequently search for different keys.
  61. 1(b)3 marks· CAPE Computer Science Unit 2 · 2016 · Paper 2Write code to implement the function `public void insertToFront(String s)` which accepts a string `s`, stores it in a new node, and inserts it at the front of an existing linked list where `top` points to the first node.
  62. 1(c)3 marks· CAPE Computer Science Unit 2 · 2016 · Paper 2Draw diagrams showing the contents of the queue Q after executing Line 3, Line 4, and Line 5, showing all elements in the queue for each illustration.
  63. 1(d)6 marks· CAPE Computer Science Unit 2 · 2016 · Paper 2Describe three operations that can be executed on a stack.
  64. 1(e)10 marks· CAPE Computer Science Unit 2 · 2016 · Paper 2Write C code to reverse the order of items in a queue (e.g. from x1, x2, x3 ... xN to xN ... x3, x2, x1 where xN is at the front).
  65. 2(a)(i)3 marks· CAPE Computer Science Unit 2 · 2016 · Paper 2Explain how the first node can be deleted.
  66. 2(a)(ii)3 marks· CAPE Computer Science Unit 2 · 2016 · Paper 2Explain how the last node can be deleted.
  67. 2(a)(iii)4 marks· CAPE Computer Science Unit 2 · 2016 · Paper 2Explain how any node between the first and last can be deleted.
  68. 2(b)(i)2 marks· CAPE Computer Science Unit 2 · 2016 · Paper 2Write C code to declare an array `number` capable of storing 10 integers.
  69. 2(b)(ii)4 marks· CAPE Computer Science Unit 2 · 2016 · Paper 2Write C code to populate the array `number` with integers entered by the user.

Related topics in Data Structures