PROGRAMMING & OOP

Complete Exam Preparation Notes

NTRCA College Level (Code: 452) | BCS Preliminary

C Programming • Object-Oriented Concepts • Data Structures • Algorithms

15-Page Master Notes | 50 MCQ Drill | Concept Questions

■ Exam Pattern: MCQ format · 200 questions · NTRCA Written: 2 × 10 = 20 marks for OOP section ·
Topics: C fundamentals, OOP concepts, Data Structures, Algorithms, Software Engineering
 ■ CHAPTER 1: C PROGRAMMING FUNDAMENTALS
1.1 Data Types in C
Data Types define the type and size of data a variable can hold. C has Primary (int, float, char,
double, void), Derived (array, pointer, function), and User-defined (struct, union, enum, typedef)
types.

Type Size Range Format

int 4 bytes -2,147,483,648 to 2,147,483,647 %d

float 4 bytes 3.4E-38 to 3.4E+38 (6 decimal) %f

double 8 bytes 1.7E-308 to 1.7E+308 (15 decimal) %lf

char 1 byte -128 to 127 %c

long int 8 bytes Very large integers %ld

unsigned int 4 bytes 0 to 4,294,967,295 %u

1.2 Operators in C
Type Operators Note

Arithmetic +, -, *, /, % (modulus) a%b gives remainder

Relational ==, !=, <, >, <=, >= Returns 0 or 1

Logical &&, ||, ! AND, OR, NOT

Bitwise &, |, ^, ~, <<, >> Operate on bits

Assignment =, +=, -=, *=, /= Shorthand assignment

Ternary ?: condition ? true : false

sizeof sizeof(type) Returns size in bytes

Increment/Decrement ++, -- Pre: ++a; Post: a++

1.3 Control Statements

Statement Description

if-else Conditional branching based on a boolean expression

switch-case Multi-branch selection based on integer/char value

for loop Count-controlled iteration: for(init; cond; update)

while loop Condition-controlled: checks condition before executing

do-while Executes at least once; checks condition after body

break Exits the nearest enclosing loop or switch

continue Skips rest of loop body; goes to next iteration

goto Unconditional jump (avoid in structured programming)

1.4 Arrays and Strings
Array: Collection of same-type elements stored contiguously in memory. Index starts at 0.
Declaration: int arr[10];
String: Array of characters terminated by null character \0. Key functions: strlen(), strcpy(), strcat(),
strcmp(), strrev()

1.5 Pointers
• A pointer stores the memory address of another variable.
• Declaration: int *p; | Address-of: p = &x; | Dereference: *p
• Pointer arithmetic: p++ moves pointer by sizeof(type) bytes.
• NULL pointer: pointer not pointing to any valid address (int *p = NULL;)
• Void pointer: generic pointer (void *p;) — can hold any data type address.
• Dangling pointer: points to freed/out-of-scope memory → undefined behavior.
• Arrays and pointers: array name is pointer to first element (arr == &arr;[0]).

1.6 Functions
Concept Details

Return Type void (no return), int, float, char, etc.

Parameter Passing Call by Value: copy sent; Call by Reference: address sent via pointer

Recursion Function calls itself. Must have base case to avoid infinite loop.

Storage Classes auto (default), static (persists between calls), extern, register

Prototype Declaration before main(): int add(int, int);

1.7 Structures and Unions

Type Key Feature Memory/Example

Structure (struct) Groups different data types. Each member hassizeof(struct)

OWN memory. = sum of all members (+ padding)

Union All members SHARE the same memory location.

sizeof(union) = size of LARGEST member

Enum Named integer constants. Default starts at 0. enum Color {RED=0, GREEN=1, BLUE=2};

typedef Creates alias for data type. typedef struct Node { int data; } Node;
 ■ CHAPTER 2: OBJECT-ORIENTED PROGRAMMING
(OOP)
OOP is a programming paradigm based on the concept of "objects" — entities that contain data
(attributes) and behavior (methods). The 4 pillars: Encapsulation · Inheritance · Polymorphism ·
Abstraction

2.1 Classes and Objects

Term Definition Example

Class Blueprint/template for creating objects. Defines attributes

class Car
& methods.
{ int speed; void drive(); }

Object Instance of a class. Has its own copy of instance variables.

Car myCar = new Car();

Constructor Special method called when object is created. Same

Car()
name
{ speed
as class.
= 0; }

Destructor Called when object is destroyed (C++: ~ClassName())

Releases allocated memory

this keyword Reference to current object inside a method. [Link] = speed;

static member Shared among ALL instances of the class. static int count = 0;

2.2 The Four Pillars of OOP

■ Encapsulation
Bundling data (attributes) and methods that operate on the data into a single unit (class), and
restricting direct access using access modifiers.
• private: accessible only within the class
• protected: accessible within class and subclasses
• public: accessible from anywhere
• Getters/Setters provide controlled access to private fields.

■■■■■ Inheritance
Type Description Syntax

Single One parent, one child class B extends A

Multiple Multiple parents (C++ supports; Java: via interfaces) class C extends A, B (C++)

Multilevel A → B → C (chain) class C extends B, B extends A

Hierarchical One parent, multiple children class B, C both extend A

Hybrid Combination of multiple + multilevel Complex diamond problem

■ Polymorphism
Polymorphism = "many forms". Same interface, different implementation.
• Compile-time (Static): Method Overloading — same name, different parameters.
• Run-time (Dynamic): Method Overriding — child redefines parent method. Uses virtual (C++) or
@Override (Java).
• Operator Overloading (C++): Redefine behavior of operators for user-defined types.

■ Abstraction
 Abstraction = hiding implementation details, showing only essential features.
• Abstract Class: Cannot be instantiated; may have abstract (no-body) methods.
• Interface: 100% abstract. All methods are abstract. A class can implement multiple interfaces.
• Key difference: Abstract class can have constructor; Interface cannot (Java 7 and below).

2.3 Key OOP Concepts Summary

Concept Explanation

Method Overloading Same name, different parameters (compile-time polymorphism)

Method Overriding Subclass redefines parent method (runtime polymorphism)

Abstract Method Declared without implementation; must be overridden in subclass

Interface Pure abstract type; class implements interface(s)

super keyword Refers to parent class; super() calls parent constructor

final keyword final class: cannot extend; final method: cannot override; final var: constant

Package Namespace for organizing related classes (like folders)

instanceof Checks if object is an instance of a class: obj instanceof ClassName

Garbage Collection Automatic memory management (Java/Python) — frees unused objects

Copy Constructor Creates new object as copy of existing object

 ■ CHAPTER 3: DATA STRUCTURES
3.1 Arrays vs. Linked Lists
Operation Array Linked List

Access O(1) random access O(n) sequential access

Insert/Delete (middle) O(n) — shift elements O(1) — change pointers

Memory Contiguous block required Non-contiguous; extra pointer space

Size Fixed at declaration Dynamic (grows/shrinks)

Cache performance Better (contiguous) Poor (scattered)

3.2 Linked List Types

Type Key Feature

Singly Linked List Each node has data + next pointer. Traversal in one direction only.

Doubly Linked List Each node has data + next + prev pointer. Bidirectional traversal.

Circular Linked List Last node points back to first node. No NULL at end.

Circular Doubly Combines circular and doubly features.

3.3 Stack and Queue

Type Order Operations Applications

Stack LIFO (Last In First Out) Push, Pop, Peek/Top, isEmpty Function calls, Undo, Expression evaluation, Recursio

Queue FIFO (First In First Out) Enqueue, Dequeue, Front, Rear CPU scheduling, Print spooler, BFS

Priority Queue Element with highest priority dequeued

Insert, Extract-Max/Min
first Dijkstra's, Huffman coding

Deque Double-ended queue: insert/delete

InsertFront,
at both InsertRear,
ends etc. Sliding window, LRU cache

Expression Conversion: Infix: A+B | Prefix (Polish): +AB | Postfix (Reverse Polish): AB+
Postfix evaluation uses a STACK. Scan left→right: push operand, pop two on operator, push result.

3.4 Trees
Tree Type Key Properties

Binary Tree Each node has at most 2 children (left, right)

BST (Binary Search Tree) Left < Root < Right. Search: O(log n) avg, O(n) worst.

AVL Tree Self-balancing BST. Height difference (balance factor) ≤ 1. Rotations: LL, RR, LR, RL.

Heap Complete binary tree. Max-Heap: parent ≥ children. Min-Heap: parent ≤ children.

B-Tree Multi-way search tree. Used in databases/file systems. All leaves at same level.

B+ Tree B-tree where all data in leaves, leaves linked. Best for range queries.
 Red-Black Tree Self-balancing BST with color property. O(log n) all operations.

Trie Tree for strings. Each edge = one character. Used in autocomplete, dictionary.

3.5 Graph Fundamentals

Concept Description

Directed (Digraph) Edges have direction. (u→v ≠ v→u)

Undirected Edges have no direction. (u-v = v-u)

Weighted Each edge has a numeric weight/cost

Adjacency Matrix n×n matrix. Space O(V²). Good for dense graphs.

Adjacency List List per vertex. Space O(V+E). Good for sparse graphs.

BFS Breadth-First Search. Uses Queue. Finds shortest path (unweighted). O(V+E).

DFS Depth-First Search. Uses Stack/Recursion. O(V+E).

Topological Sort Linear ordering of vertices in a DAG. DFS-based.

 ■ CHAPTER 4: SORTING & SEARCHING
ALGORITHMS
4.1 Sorting Algorithms — Big-O Complexity
Algorithm Best Worst Space Stable Notes

Bubble Sort O(n²) O(n²) O(1) Yes Simple; worst performer

Selection Sort O(n²) O(n²) O(1) No Minimum swaps: n-1

Insertion Sort O(n) O(n²) O(1) Yes Best for nearly sorted

Merge Sort O(n log n) O(n log n) O(n) Yes Divide & conquer; stable

Quick Sort O(n log n) O(n²) O(log n) No Average best; pivot matters

Heap Sort O(n log n) O(n log n) O(1) No Uses max-heap structure

Radix Sort O(nk) O(nk) O(n+k) Yes Non-comparative; for integers

Counting Sort O(n+k) O(n+k) O(k) Yes k = range of input values

Stability: A sort is stable if equal elements maintain their original order.

In-place: Sorts with O(1) extra space are in-place (Bubble, Selection, Insertion, Heap, Quick).
Exam Tip: Merge Sort = always O(n log n) · Quick Sort worst = O(n²) when pivot is min/max.

4.2 Searching Algorithms

Algorithm Best Worst Average Requirement Notes

Linear Search O(1) O(n) O(n)/2 avg No Works on unsorted array

Binary Search O(1) O(log n) O(log n) Yes (sorted) Divide and conquer; array must be sorted

Hashing O(1) O(n) worst O(1) avg No Best average case; collision handling needed

DFS Search O(V+E) O(V+E) - Graphs Used for graph/tree traversal

BFS Search O(V+E) O(V+E) - Graphs Shortest path in unweighted graph

4.3 Algorithm Design Techniques

Technique Strategy Classic Problems

Greedy Algorithm Makes locally optimal choice at each step hoping

Huffman
for global
Coding,
optimum.
Kruskal's MST, Prim's MST, Activity Selecti

Divide & Conquer Divide into subproblems, solve recursively, combine

Merge Sort,
results.
Quick Sort, Binary Search, Strassen Matrix Multi

Dynamic Programming Solves overlapping subproblems using memoization

LCS, 0/1orKnapsack,
[Link] Chain Multiplication, Floyd-Warsh

Backtracking Tries all possibilities, abandons (backtracks) when

N-Queens,
constraint
Sudoku
violated.
Solver, Maze Problem, Hamiltonian Path

Branch & Bound Like backtracking but uses bounding function TSP,
to prune
0/1 Knapsack
search space.
(optimization)

4.4 Hashing
Concept Description

Hash Function Maps key to index. Simple: h(k) = k mod m

Collision Two keys hash to same index

Chaining (Open Hashing) Each slot is a linked list. Multiple keys stored in list.

Open Addressing Store in next available slot. Types: Linear, Quadratic, Double Hashing.

Linear Probing h(k, i) = (h(k) + i) mod m. Causes primary clustering.

Quadratic Probing h(k, i) = (h(k) + i²) mod m. Reduces primary clustering.

Double Hashing h(k, i) = (h1(k) + i·h2(k)) mod m. Best distribution.

Load Factor (α) α = n/m (n=items, m=slots). Performance degrades as α→1.

 ■ CHAPTER 5: SOFTWARE ENGINEERING
5.1 Software Development Life Cycle (SDLC)
Phase Description

1. Requirement Analysis Gather & document what the system should do (functional & non-functional requirements)

2. System Design High-level (architecture) and low-level (detailed) design

3. Implementation (Coding) Convert design into source code

4. Testing Unit, Integration, System, Acceptance testing

5. Deployment Release to production environment

6. Maintenance Bug fixes, updates, enhancements post-deployment

5.2 Software Development Models

Model Key Features

Waterfall Model Sequential phases; no backtracking. Simple, easy to manage. Problem: inflexible to changes; client s

Agile Model Iterative, incremental development. Customer collaboration. Sprints (2-4 weeks). Frameworks: Scrum

Spiral Model Combines waterfall + prototyping. Risk-driven. Each loop = one phase. Best for large, risk-heavy pro

V-Model Verification & Validation model. Each development phase has a testing phase. Testing planned in pa

Prototype Model Build prototype first, get feedback, refine. Helps clarify unclear requirements.

Incremental Model Deliver product in small increments. First increment = core functionality.

RAD Model Rapid Application Development. Heavy user involvement. Short development cycles.

5.3 Software Quality Attributes

Quality Meaning

Correctness Does the software do what it is supposed to do?

Reliability Performs consistently without failure over time

Usability Easy to learn and use (user-friendly)

Efficiency Good performance with minimal resource usage

Maintainability Easy to modify, update, and fix bugs

Portability Runs on different platforms/environments without modification

Robustness Handles unexpected inputs/errors gracefully

Testability Easy to test (measurable, observable outcomes)

 ■ CHAPTER 6: MCQ EXAM DRILL — 50 QUESTIONS
■ Correct answers are marked with ✔ in green | ■ = Explanation/Tip | Practice these until you can
answer instantly — these patterns repeat in NTRCA & BCS exams.

Section A: C Programming (Q1-Q15)

Q1. Which data type is used to store a single character in C?
(A) int
✔ (B) char
(C) string
(D) byte
■ char stores one character (1 byte). 'string' is not a C data type.

Q2. What is the output of: int x = 5; printf("%d", x++);

✔ (A) 5
(B) 6
(C) 4
(D) Error
■ Post-increment: value used THEN incremented. Prints 5, then x becomes 6.

Q3. Which operator is used to access a struct member through a pointer?

(A) .
✔ (B) ->
(C) ::
(D) *
■ Arrow operator (->) is used for pointer-to-struct. Dot (.) for direct struct access.

Q4. What is the size of int on a 32-bit system?

(A) 2 bytes
✔ (B) 4 bytes
(C) 8 bytes
(D) 1 byte
■ int is typically 4 bytes (32 bits) on 32-bit and 64-bit systems.

Q5. In C, array indices start from:

(A) 1
✔ (B) 0
(C) -1
(D) Depends on compiler
■ C arrays are 0-indexed. arr[0] is the first element.

Q6. Which storage class retains value between function calls?

(A) auto
(B) extern
✔ (C) static
(D) register
■ static local variables persist between function calls; initialized only once.

Q7. What does malloc() return if allocation fails?

(A) 0
✔ (B) NULL
 (C) -1
(D) Garbage value
■ malloc() returns NULL on failure. Always check: if(ptr == NULL) before use.

Q8. A pointer to a pointer is declared as:

(A) *p
✔ (B) **p
(C) &p;
(D) ptr*
■ int **pp is a pointer-to-pointer. **pp dereferences both levels.

Q9. What is the difference between struct and union in C?

(A) No difference
(B) Struct: all share memory; Union: each has own
✔ (C) Struct: each has own memory; Union: all share memory
(D) Only name differs
■ Struct gives each member its own memory. Union: all members share the SAME memory location.

Q10. Which function is used to compare two strings in C?

(A) compare()
✔ (B) strcmp()
(C) strcomp()
(D) equal()
■ strcmp(s1, s2): returns 0 if equal, <0 if s10 if s1>s2.

Q11. In recursion, what prevents infinite loops?

(A) Return statement
✔ (B) Base case
(C) Recursive call
(D) Stack limit
■ Base case: the condition where the function returns without calling itself recursively.

Q12. Which is NOT a valid C data type?

(A) float
(B) double
✔ (C) string
(D) char
■ 'string' is NOT a C primitive. Use char array or char pointer for strings.

Q13. What is Call by Reference in C?

(A) Passing value of variable
✔ (B) Passing address of variable
(C) Passing name of variable
(D) None
■ Call by Reference passes the address using pointers, allowing the function to modify the original.

Q14. The format specifier for float in printf is:

(A) %d
(B) %c
✔ (C) %f
(D) %s
■ %f for float, %lf for double, %d for int, %c for char, %s for string.
Q15. Which is the correct way to declare an array of 10 integers?
(A) int arr{10}
(B) array int[10]
✔ (C) int arr[10]
(D) int[10] arr
■ Syntax: type name[size]; → int arr[10]; is correct.

Section B: OOP Concepts (Q16-Q30)

Q16. Which OOP pillar hides internal implementation details?
(A) Inheritance
(B) Polymorphism
(C) Encapsulation
✔ (D) Abstraction
■ Abstraction hides 'how' and shows 'what'. Encapsulation restricts direct access using access
modifiers.

Q17. Method overloading is an example of:

(A) Runtime polymorphism
✔ (B) Compile-time polymorphism
(C) Inheritance
(D) Abstraction
■ Overloading = same name, different parameters = resolved at compile-time (static binding).

Q18. Which keyword prevents a class from being subclassed in Java?

(A) static
(B) abstract
✔ (C) final
(D) private
■ final class cannot be extended. final method cannot be overridden.

Q19. An interface in Java can have:

(A) Constructor
(B) Instance variables
✔ (C) Abstract methods only (pre-Java 8)
(D) Private methods
■ Before Java 8: interface = only abstract methods + constants. Java 8+: default and static methods
allowed.

Q20. What is the 'super' keyword used for?

(A) Refer to current object
✔ (B) Refer to parent class
(C) Create object
(D) Delete object
■ super() calls parent constructor. [Link]() calls parent's method.

Q21. Which type of inheritance is NOT supported in Java (directly)?

(A) Single
(B) Multilevel
(C) Hierarchical
✔ (D) Multiple (class)
■ Java doesn't support multiple inheritance via classes to avoid diamond problem. Interfaces are
used instead.
Q22. What is an abstract class?
(A) Class with all private methods
✔ (B) Class that cannot be instantiated
(C) Class with no methods
(D) Class with only static members
■ Abstract class cannot be instantiated. May have both abstract and concrete methods.

Q23. Which access modifier is most restrictive?

(A) public
(B) protected
(C) default
✔ (D) private
■ private → default → protected → public (least to most accessible).

Q24. Overriding is associated with:

(A) Same class
✔ (B) Parent-child classes
(C) Interfaces only
(D) Unrelated classes
■ Overriding: subclass redefines a method from its parent class (runtime/dynamic polymorphism).

Q25. In Java, all classes implicitly extend:

(A) String
(B) Class
✔ (C) Object
(D) Base
■ Every Java class implicitly extends [Link] which provides methods like toString(),
equals(), hashCode().

Q26. What is a constructor?

(A) Method to destroy objects
✔ (B) Method called automatically when object is created
(C) Static method
(D) Method with return type
■ Constructor: same name as class, no return type, called automatically on object creation.

Q27. Which OOP concept allows one interface to be used for different data types?
(A) Encapsulation
(B) Inheritance
✔ (C) Polymorphism
(D) Abstraction
■ Polymorphism = 'many forms' — same interface, multiple implementations.

Q28. The 'this' keyword refers to:

(A) Parent class object
✔ (B) Current class object
(C) Static member
(D) Interface
■ 'this' refers to the current instance of the class.

Q29. What is a destructor? (C++)

(A) Creates object
✔ (B) Called before object is destroyed; frees resources
 (C) Returns value from class
(D) Static method
■ Destructor ~ClassName() is automatically called when object goes out of scope.

Q30. Packages in OOP serve as:

(A) Memory allocation units
✔ (B) Namespaces for organizing related classes
(C) Types of inheritance
(D) Abstract data types
■ Package = folder/namespace that organizes related classes and avoids naming conflicts.
Section C: Data Structures & Algorithms (Q31-Q50)
Q31. Which data structure uses LIFO order?
(A) Queue
✔ (B) Stack
(C) Array
(D) Tree
■ Stack = Last In First Out. Push adds to top, Pop removes from top.

Q32. What is the time complexity of binary search?

(A) O(n)
(B) O(n²)
✔ (C) O(log n)
(D) O(1)
■ Binary search divides search space in half each time: T(n) = T(n/2) + O(1) → O(log n).

Q33. Which sorting algorithm has O(n log n) in all cases?

(A) Quick Sort
(B) Bubble Sort
✔ (C) Merge Sort
(D) Insertion Sort
■ Merge Sort is always O(n log n) — unlike Quick Sort which is O(n²) worst case.

Q34. Which tree ensures balance by keeping height difference ≤ 1?

(A) Binary Tree
(B) BST
✔ (C) AVL Tree
(D) B-Tree
■ AVL Tree is a self-balancing BST. Balance factor = height(left) - height(right) ∈ {-1, 0, 1}.

Q35. In a max-heap, the root element is always the:

(A) Smallest
✔ (B) Largest
(C) Middle
(D) Last inserted
■ Max-Heap: root = maximum. Min-Heap: root = minimum.

Q36. BFS (Breadth First Search) uses which data structure?

(A) Stack
✔ (B) Queue
(C) Priority Queue
(D) Tree
■ BFS uses a Queue. DFS uses a Stack (or recursion).

Q37. What is the space complexity of Merge Sort?

(A) O(1)
(B) O(log n)
✔ (C) O(n)
(D) O(n²)
■ Merge Sort needs O(n) auxiliary space to merge subarrays.

Q38. Which collision resolution uses linked lists at each slot?

(A) Open Addressing
(B) Linear Probing
 ✔ (C) Chaining
(D) Quadratic Probing
■ Chaining (Separate Chaining): each hash table slot contains a linked list of all keys with that hash.

Q39. Postfix expression AB+C* means:

✔ (A) (A+B)*C
(B) A+(B*C)
(C) A*B+C
(D) A+(B+C)
■ AB+C*: evaluate AB+ first = (A+B), then (A+B)C* = (A+B)*C.

Q40. Which algorithm finds shortest path in a weighted graph?

(A) DFS
(B) BFS
✔ (C) Dijkstra's
(D) Prim's
■ Dijkstra's algorithm finds shortest paths from source to all vertices in weighted graph (non-negative
weights).

Q41. Quick Sort's worst case occurs when:

✔ (A) Array is sorted (with bad pivot choice)
(B) Array is random
(C) Array is reversed
(D) Array has all equal elements
■ Quick Sort worst = O(n²) when pivot is always min or max (e.g., sorted array with first/last pivot).

Q42. Which data structure is used in implementing undo functionality?

(A) Queue
✔ (B) Stack
(C) Heap
(D) Graph
■ Stack is used for undo: each action pushed; undo pops the last action.

Q43. In a B+ Tree, data pointers exist only in:

(A) Root nodes
(B) Internal nodes
✔ (C) Leaf nodes
(D) All nodes
■ B+ Tree: internal nodes store only keys for routing; ALL data is in leaf nodes (which are also
linked).

Q44. Tower of Hanoi with n disks requires minimum how many moves?
(A) n
(B) 2n-1
✔ (C) 2^n - 1
(D) n²
■ Minimum moves = 2^n - 1. For 3 disks: 2³-1 = 7 moves.

Q45. DFS uses which traversal order for a binary tree (in-order)?
(A) Root-Left-Right
✔ (B) Left-Root-Right
(C) Left-Right-Root
(D) Right-Root-Left
■ In-order: Left → Root → Right (gives sorted output for BST). Pre-order: Root-Left-Right. Post-order:
Left-Right-Root.

Q46. Which sorting is used internally by most programming languages?

(A) Bubble Sort
✔ (B) Quick Sort or TimSort
(C) Insertion Sort
(D) Radix Sort
■ Most use TimSort (Python, Java) or Introsort (C++ STL) which combines Quick, Heap, and Insertion
Sort.

Q47. What does a Trie data structure efficiently support?

(A) Sorting integers
✔ (B) Prefix-based string search
(C) Graph traversal
(D) Matrix operations
■ Trie: tree for strings. Each path from root = prefix. Used in autocomplete, spell-check.

Q48. Kruskal's algorithm is used to find:

(A) Shortest path
✔ (B) Minimum Spanning Tree
(C) Topological order
(D) Maximum flow
■ Kruskal's and Prim's both find MST. Kruskal's: sort edges by weight, add if no cycle (uses
Union-Find).

Q49. What is memoization in Dynamic Programming?

(A) Deleting unused variables
✔ (B) Storing computed results to avoid recomputation
(C) Sorting data
(D) Memory allocation
■ Memoization = top-down DP. Store (cache) results of expensive function calls to avoid
recomputing.

Q50. The height of a complete binary tree with n nodes is:

(A) n
(B) n/2
✔ (C) log■(n)
(D) n-1
■ Height of complete binary tree = ■log■(n)■. Minimum height = maximum efficiency for search.
 ■ QUICK CHEAT SHEET — MUST MEMORIZE
Topic Key Facts

Stack LIFO · Push/Pop/Peek · Applications: Recursion, Undo, Expression eval, DFS

Queue FIFO · Enqueue/Dequeue · Applications: BFS, Scheduling, Printing

Binary Search O(log n) · MUST be sorted · Low=0, High=n-1, Mid=(L+H)/2

Merge Sort O(n log n) all cases · Stable · O(n) space · Divide & Conquer

Quick Sort O(n log n) avg · O(n²) worst · In-place · Not stable

Heap Sort O(n log n) all · In-place · Not stable · Build max-heap then extract

BST Search O(log n) avg · O(n) worst (skewed) · Left < Root < Right

AVL Tree Self-balancing BST · Balance Factor ∈ {-1,0,1} · O(log n) guaranteed

BFS Queue · Level-order traversal · Shortest path (unweighted) · O(V+E)

DFS Stack/Recursion · Pre/In/Post-order · O(V+E) · Used for topological sort

Dijkstra Priority Queue · Shortest path (weighted, non-negative) · O((V+E)log V)

Greedy Local optimal → Global optimal · Huffman, Kruskal, Prim, Activity Selection

DP Overlapping subproblems + Optimal substructure · LCS, Knapsack, Floyd-Warshall

Hashing O(1) avg · Collision: Chaining or Open Addressing (Linear/Quadratic/Double)

OOP Pillars Encapsulation · Inheritance · Polymorphism · Abstraction

Polymorphism Overloading (compile-time) · Overriding (runtime)

Recursion Must have BASE CASE · Uses call stack · T(n) = T(n-1)+O(1)→O(n)

Tower of Hanoi 2^n - 1 moves · Recursive · Classic recursion example

Postfix eval Stack: push operands, pop two on operator, push result

B+ Tree All data in LEAVES · Leaves linked · Best for range queries · Used in DB

■ Exam Strategy: For NTRCA MCQ — eliminate clearly wrong options first. For sorting: always
check stable/in-place/complexity trio. For OOP: Overloading=compile-time, Overriding=runtime. For
trees: BST property + AVL balance factor are the most-tested concepts. For graphs:
BFS=Queue=Shortest path · DFS=Stack=Topological sort.