Programming and data structures
Programming and data structures tests how data is typed, stored and manipulated: arrays, records, linked lists, stacks, queues, trees and hash tables, plus parameter passing and object-oriented design.
Types and structures
Primitive types include integer, real, Boolean, character, string and date; casting converts between them. An array has fixed size and contiguous elements, so index access is constant time. A two-dimensional array is indexed by row and column. A record groups fields of different types, and an array of records is the standard way to hold a table of data. A linked list stores each item in a node with a pointer to the next node: insertion and deletion are cheap once the position is known, but access is sequential and a head pointer is essential.
Abstract data types
A stack is last in, first out: push adds to the top, pop removes from the top. A queue is first in, first out: enqueue adds at the rear, dequeue removes from the front. A binary tree has at most two children per node; a binary search tree keeps smaller values left and larger values right. A hash table maps a key to a bucket through a hash function, giving near-constant lookup when collisions are handled.
Parameters and OOP
Passing by value copies the argument, so changes are local; passing by reference passes the address, so changes affect the caller. A function returns a value; a procedure does not. A class is a template, an object is an instance; encapsulation keeps attributes private and exposes methods; inheritance reuses a parent class; polymorphism lets the same method call behave differently.
Worked example
PROCEDURE change(BYREF x : INTEGER, BYVAL y : INTEGER) sets x ← x + 1 and y ← y + 1. With a = 5 and b = 5, calling change(a, b) leaves a = 6 and b = 5, because x refers to a while y is a discarded copy.
Traps
Reversing stack and queue order; assuming an array can grow; forgetting a linked list needs a head pointer; mixing by-value and by-reference; saying a class is an object.