I85PREP
⌘ K
SQU IT Exit study materials
SQU IT Exit study resources

SQU IT Exit: Data Structures and Algorithms

SQU IT Exit · Work through your exam, one topic at a time.

All guide sections

Data Structures and Algorithms

What this domain tests

Data Structures and Algorithms tests selection and analysis: given a problem, choose a structure, state its complexity, and trace an operation. Expect Big-O, arrays, linked lists, stacks, queues, trees, hashing, graphs, and sorting/searching.

Core rules and concepts

  • Big-O describes growth, not seconds. Nested loops over n are usually O(n²); halving the input each step is O(log n).
  • Array indexing is O(1); inserting at the front is O(n). A singly linked list finds the nth node in O(n) but inserts at a known node in O(1).
  • Stack is LIFO; queue is FIFO. BFS uses a queue; DFS uses a stack or recursion.
  • BST search is O(log n) average but O(n) worst when unbalanced. Hash tables average O(1), worst O(n) with collisions.
  • Stable sorts preserve equal-key order; comparison sorts cannot beat O(n log n) in the worst case.

Worked example

Search 23 in sorted [2,5,8,12,16,23,38,56,72,91]. low=0, high=9, mid=(0+9)/2=4, value 16; 23>16, so low=5. mid=(5+9)/2=7, value 56; 23<56, so high=6. mid=(5+6)/2=5, value 23; found in 3 comparisons. The invariant is that the target, if present, stays within [low, high].

Traps that cost marks

Calling hash lookup O(1) in every case. Forgetting the BST worst case. Using a stack for BFS. Confusing average and worst case. Choosing a linked list for binary search, which needs O(1) random access.