Data Structures | OCR A-Level Computer Science (H446)

Data Structures

124 questions
9 subtopics
Component 01: Computer systems
Component 01

Data Structures is examined on component 01 of OCR Computer Science, Computer systems.

124 recall questions across 9 subtopics.

Sample questions from Data Structures

Answer each one closed book first, then open the answer.

Arrays and records

How many elements does an array declared as 2 by 3 by 4 hold?

Show the answer
24. The sizes of the dimensions multiply: 2 x 3 x 4 = 24 elements.
Arrays and records

An array of 4-byte integers begins at address 2000 and is indexed from 0. What is the address of element 6?

Show the answer
2024. Address = 2000 + (6 x 4) = 2000 + 24 = 2024. Note that if the array were indexed from 1 instead, you would use (6 - 1) x 4, giving 2020 - always check the base index.
Lists and tuples, and creating, traversing, adding and removing items

What is a list?

Show the answer
An ordered, dynamic collection of items where each item has a position. Unlike an array, a list can grow and shrink at run time, items can be inserted and removed at any position, and in many languages the items do not all have to be the same data type. Underneath it may be implemented with a dynamic array or a linked list.
Linked Lists

How do you create an empty linked list?

Show the answer
Set the head pointer to null, so that it points at no node. In an array-based implementation you also build the free list by linking every slot to the next one and setting the free-list pointer to the first slot, so all space is marked as available.
Linked Lists

How is deleting the first node of a linked list different from deleting one from the middle?

Show the answer
There is no previous node whose pointer can be redirected, so instead you set the head pointer to the first node's next pointer, and then release that node. Deleting the last node is also a special case: you set the previous node's pointer to null so that it becomes the new end of the list.
Stacks

Describe the push operation.

Show the answer
First check whether the stack is full - if the pointer is already at the maximum index, report overflow and do not proceed. Otherwise increment the stack pointer by one and store the new item at that index. The new item is now the top of the stack, and the item previously on top is untouched underneath it.
Stacks

What is stack underflow?

Show the answer
An attempt to pop or peek an item from an empty stack, when the stack pointer shows there is nothing stored. There is no item to return, so the operation must be refused and an error reported rather than reading whatever rubbish is in the memory location.
Queues and Circular Queues

Describe the enqueue operation on a linear queue.

Show the answer
Check first whether the queue is full — if the rear pointer already holds the last index there is no room, so report the error. Otherwise move the rear pointer on by one, store the new item at the index the rear pointer now holds and increase the item count. The front pointer is not affected.

The 9 subtopics

One subtopic is one session. Work down the list.

Subtopic	What it covers	Questions
Arrays and records	Recall questions on one, two and three-dimensional arrays, calculating element addresses, why arrays give direct access, the limitations of arrays, records, and how arrays differ from records and are combined into arrays of records.	11
Lists and tuples, and creating, traversing, adding and removing items	Recall questions on lists and tuples and how they differ from arrays, immutability, when to choose a tuple, and how to create, traverse, add to and remove from arrays, records and lists.	11
Linked Lists	Recall questions on linked lists and how they are stored, the free list, advantages and disadvantages against arrays, creating, traversing and searching a list, adding, inserting and deleting nodes in the right pointer order, and doubly linked lists.	17
Stacks	Recall questions on stacks and their uses, the stack pointer, creating a static stack, push, pop and peek, overflow and underflow, static and dynamic stacks, tracing operations, and why recursion needs a stack rather than a queue.	14
Queues and Circular Queues	Recall questions on queues and their uses, front and rear pointers, enqueue and dequeue, the wasted space of a linear queue, circular queues with modulo arithmetic, telling full from empty, tracing operations, and static and dynamic queues.	15
Graphs	Recall questions on directed, undirected and weighted graphs, adjacency matrices and adjacency lists and when to use each, creating graphs and adding or removing nodes and edges, traversals, visited lists, and how a tree relates to a graph.	15
Trees and binary search trees: structure, insertion and searching	Recall questions on tree terminology, binary trees and the binary search tree rule, how a tree is stored and created, inserting and searching for values with traces, search efficiency, and the effect of inserting sorted data.	11
Deleting from a binary search tree, traversals, uses of trees and general trees	Recall questions on deleting leaf, one-child and two-children nodes from a binary search tree, in-order successors and predecessors, pre-order, in-order, post-order and breadth-first traversals, uses of trees, and adding nodes to a general tree.	12
Hash Tables	Recall questions on hash tables and hash functions, inserting with linear probing, lookup, collisions and why they are unavoidable, separate chaining and other collision strategies, load factor, performance, deletion, and when a hash table fits.	18

Data Structures is 124 of the 1,549 questions in the guide.Get the guide, £9

How the guide is worked

Answering a question from memory stores it far better than reading the answer again. The guide runs that as a fixed procedure on one subtopic at a time, about twenty minutes a session.

Step 1 · Closed book
Cover the answers. Work through one subtopic and write down what you can. Leave blanks where you have nothing.
Step 2 · Open book
Go back to the top. Read each printed answer and write it out in full, including the ones you had right.
Step 3 · Closed book again
Same questions, same order, from memory. The gap between pass one and pass three is the session result.

Read the full method, the return schedule and the research behind it.