AQA A Level Computer Science Unit 7
Data Structures Definitions Exam With
Correct Answers
Abstract data type - correct answers ✔✔A logical description of how the data is viewed and the
operations that can be performed upon it.
Queue - correct answers ✔✔A first in first out (FIFO) data structure where elements can only be
added to the end and can only be retrieved from the front. The order of items is determined by
the order they were inserted in.
Operations on a queue - correct answers ✔✔enQueue, deQueue, isEmpty, ifFull
Dynamic data structure - correct answers ✔✔A collection of data in memory that has the ability
to grow or shrink in size with the aid of the heap, a portion of memory from which space is
allocated or de-allocated as required.
Static data structure - correct answers ✔✔A data structure that is fixed in size and cannot
increase in size or free up memory while the program is running. E.g. an array. A disadvantage of
using an array to implement a data structure is that the size has to be decided in advance and
cannot be increased once it is full. Additionally, memory that has been allocated cannot be
deallocated even if it is unused. An advantage is that no pointers or other data about the
structure needs to be stored.
Linear queue - correct answers ✔✔Either
1. As items leave the queue all other items move up one space so that the front of the queue is
always the first element. This may require a lot of processing for long queues.
2. Pointers are used to keep track of the front and rear of the queue. A variable with the size of
the array is needed as well as a variable with the number of items currently in the queue. An
, issue is that as items are removed space is created at the front of the queue which cannot be
filled, and eventually the rear pointer points to the last element of the data structure and no
more items can be added.
Circular queue - correct answers ✔✔Solves the limitations of a linear queue by having the rear
pointer wrap around to 0 when it reaches the end of the array. This requires extra effort from
the programmer and is less flexible than dynamic data structures if the maximum number of
items is not known in advance.
Priority queue - correct answers ✔✔A queue in which the logical order of items is determined
by their priority, with higher priority items at the front and lowest priority items at the back. A
new item is therefore able to join at the front or the middle, not just the rear.
List - correct answers ✔✔An abstract data type consisting of a number of items in which the
same item may occur more than once. The list is sequenced so that we can refer to the first,
second, third... item and wen can also refer to the last element of the list.
Operations on a list - correct answers ✔✔isEmpty(), append(item), remove(item), search(item),
length(), index(item), insert(pos, item), pop(), pop(pos)
List implementation - correct answers ✔✔Using an array - items are shifted forwards and
backwards as elements are inserted and removed, max size must be declared in advance
Using a linked list - each item is stored alongside a pointer to the next item. The pointers are
adjusted when items are inserted and deleted.
Stack - correct answers ✔✔A last in first out (LIFO) data structure where items are added to the
top and removed from the top.
Stack implementation - correct answers ✔✔Using an array - a pointer to the top of the stack
and the size of the array are stored. Items are removed from where the pointer points,
decrementing it, and added in the slot above, incrementing the pointer.
Data Structures Definitions Exam With
Correct Answers
Abstract data type - correct answers ✔✔A logical description of how the data is viewed and the
operations that can be performed upon it.
Queue - correct answers ✔✔A first in first out (FIFO) data structure where elements can only be
added to the end and can only be retrieved from the front. The order of items is determined by
the order they were inserted in.
Operations on a queue - correct answers ✔✔enQueue, deQueue, isEmpty, ifFull
Dynamic data structure - correct answers ✔✔A collection of data in memory that has the ability
to grow or shrink in size with the aid of the heap, a portion of memory from which space is
allocated or de-allocated as required.
Static data structure - correct answers ✔✔A data structure that is fixed in size and cannot
increase in size or free up memory while the program is running. E.g. an array. A disadvantage of
using an array to implement a data structure is that the size has to be decided in advance and
cannot be increased once it is full. Additionally, memory that has been allocated cannot be
deallocated even if it is unused. An advantage is that no pointers or other data about the
structure needs to be stored.
Linear queue - correct answers ✔✔Either
1. As items leave the queue all other items move up one space so that the front of the queue is
always the first element. This may require a lot of processing for long queues.
2. Pointers are used to keep track of the front and rear of the queue. A variable with the size of
the array is needed as well as a variable with the number of items currently in the queue. An
, issue is that as items are removed space is created at the front of the queue which cannot be
filled, and eventually the rear pointer points to the last element of the data structure and no
more items can be added.
Circular queue - correct answers ✔✔Solves the limitations of a linear queue by having the rear
pointer wrap around to 0 when it reaches the end of the array. This requires extra effort from
the programmer and is less flexible than dynamic data structures if the maximum number of
items is not known in advance.
Priority queue - correct answers ✔✔A queue in which the logical order of items is determined
by their priority, with higher priority items at the front and lowest priority items at the back. A
new item is therefore able to join at the front or the middle, not just the rear.
List - correct answers ✔✔An abstract data type consisting of a number of items in which the
same item may occur more than once. The list is sequenced so that we can refer to the first,
second, third... item and wen can also refer to the last element of the list.
Operations on a list - correct answers ✔✔isEmpty(), append(item), remove(item), search(item),
length(), index(item), insert(pos, item), pop(), pop(pos)
List implementation - correct answers ✔✔Using an array - items are shifted forwards and
backwards as elements are inserted and removed, max size must be declared in advance
Using a linked list - each item is stored alongside a pointer to the next item. The pointers are
adjusted when items are inserted and deleted.
Stack - correct answers ✔✔A last in first out (LIFO) data structure where items are added to the
top and removed from the top.
Stack implementation - correct answers ✔✔Using an array - a pointer to the top of the stack
and the size of the array are stored. Items are removed from where the pointer points,
decrementing it, and added in the slot above, incrementing the pointer.
