Programming and Data Structures
Programming and data structures tests C semantics, recursion, pointers, and the implementation and complexity of linear and nonlinear structures. Expect code snippets that ask for output, memory layout, or the result of traversals.
Core rules and concepts
- An array name decays to a pointer to its first element in most expressions, but sizeof(array) returns the whole array size when the array is in scope.
- A stack is LIFO and supports push/pop; a queue is FIFO with enqueue/dequeue. A circular queue of capacity n stores at most n−1 elements if one slot distinguishes full from empty.
- A binary search tree keeps left keys smaller and right keys larger; inorder traversal yields sorted order. A heap is a complete binary tree stored in an array, with parent i and children 2i+1, 2i+2 for zero-based indexing.
- Hash tables give average O(1) search but degrade with collisions; open addressing needs tombstones or careful deletion.
- In C, malloc returns void* and does not initialize memory; free must be applied once to a valid heap pointer.
Worked example
Insert 50, 30, 70, 20, 40, 60, 80 into an initially empty BST. 50 becomes the root; 30 goes left, 70 right; 20 and 40 attach to 30; 60 and 80 attach to 70. Inorder traversal is 20, 30, 40, 50, 60, 70, 80. Preorder is 50, 30, 20, 40, 70, 60, 80. The height is 2 edges, so search is O(log n) here, but a sorted insertion order would create a chain and O(n) search.
Traps that cost marks
Assuming sizeof(pointer) equals the array length; modifying a string literal; using a pointer after free; and treating post-increment side effects in one expression as well-defined when they are not. For heaps, do not confuse heap order with BST order.