Programming and Data Structures
This section mixes C programming semantics with classical data structures. GATE favours short code fragments whose output must be derived by hand, and structural questions about trees, heaps and hashing.
C semantics to know cold
- An array name decays to a pointer to its first element, so a[i] ≡ *(a+i) and i[a] is legal.
- C is strictly pass-by-value; to modify a caller's variable you pass its address.
- && and || short-circuit, so side effects on the right may never execute.
- sizeof(array) is total bytes; sizeof(pointer) is the pointer size, independent of what it points to.
Data structures
- Stack (LIFO), queue (FIFO), circular queue where full and empty must be distinguished by a counter or a sacrificed slot.
- BST: inorder traversal is sorted; search is O(h), degenerating to O(n) for sorted insertions.
- Binary heap: a complete binary tree stored in an array; build-heap is O(n), insert and extract-max are O(log n).
- Hashing: open addressing suffers clustering; chaining degrades to O(n) as the load factor approaches 1.
Worked example
int a[5] = {1,2,3,4,5};
int *p = a + 1;
printf("%d", p[2] + *(p+1));
p points to a[1] = 2. Then p[2] is a[3] = 4, and *(p+1) is a[2] = 3. Output = 7. The common error is treating p[2] as a[2].
Traps that cost marks
- Writing through a string literal, which is undefined behaviour.
- Assuming two different BST insertion orders give different trees - symmetric orders can coincide.
- Forgetting that the number of distinct BSTs on n keys is the Catalan number Cₙ.