SLST data structures topic

Section 1 — Data Types & Data Structures (In-depth theory)

1.1 What is a Data Type?

A data type describes the kind of value a variable can hold, the operations allowed on those values, and how values are represented in
memory.

Categories

• Primitive (built-in) types: Simple atomic values provided by the language (examples: int, char, float, double, boolean).

• Derived / Compound types: Built from primitives, e.g., arrays, pointers, references.

• Aggregate types / Records / Structs: Fixed set of fields possibly of different types (e.g., struct in C, class/record in other
languages).

• Abstract Data Types (ADT): Logical description of data and operations (e.g., Stack, Queue, List, Map). An ADT does not prescribe
a specific memory layout — it defines behavior.

• User-defined types: Types created by programmer (typedef, class, enum, union, struct).

• Dynamic types: Languages with dynamic typing (Python, JavaScript) where variable types are known at runtime.

• Static types: Languages with static typing (C, Java) where variable types are known at compile time.

Properties of a type

• Size and range: e.g., 32-bit signed int typically stores −2^31 .. 2^31−1.

• Representation: Binary layout, signed/unsigned, IEEE754 for floats.

• Operations: Arithmetic, logical, comparison, indexing, field access.

• Type checking rules: Strong vs weak typing, implicit conversions (coercion).

1.2 What is a Data Structure?

A data structure is a particular way of organizing and storing data so that it can be accessed and modified efficiently for particular
operations (insert, delete, search, traverse, update). It combines data representation with algorithms that operate on the data.

Why data structures matter

• Impact on time (how fast) and space (how much memory).

• Choice of structure depends on operations required (random access, frequent insert/delete, ordered traversal).

• Appropriate data structure makes algorithms simpler and more efficient.

1.3 Relationship: Data Type vs Data Structure

• Data type is a classification (e.g., integer, string).

• Data structure is an arrangement/organization that stores values of certain types (e.g., array of ints).

• An ADT is a type-level abstraction (specifies operations). A data structure is the implementation of an ADT.

Example: Stack = ADT (push/pop/peek). Implementation options: array-based or linked-list-based.

1.4 Primitive Types — Detailed notes

• Integer types: signed/unsigned; size depends on architecture (16/32/64 bit).

• Character types: hold character codes (ASCII/Unicode). In C char size is 1 byte; in higher-level languages strings are sequences
of Unicode code points.

• Floating point: float (single), double (double) — IEEE 754 standard, precision & rounding issues.

• Boolean: true/false often stored as 1 byte or single bit in bitfields.

 • Pointer/reference: stores memory address (C pointers) or abstract reference (Java).

1.5 Composite / Derived / Aggregate types

• Array: contiguous block of elements same type; constant-time random access by index.

• Struct / Record: fixed collection of fields, possibly heterogeneous.

• Union: overlaps storage for multiple fields (C union); useful for memory saving but risky.

• Enum: named constants.

• String: typically array of chars with conventions (null-terminated in C).

1.6 Abstract Data Types (ADT) — Key idea

An ADT defines:

• A set of values (domain).

• A set of operations on those values, and the behavior of those operations.

Common ADTs: List, Stack, Queue, Set, Map (Dictionary), Priority Queue, Graph, Tree.

1.7 Implementation vs Interface

• Interface / ADT: Specifies what operations do (e.g., push() adds to top).

• Implementation: How operations are achieved (array/linked list). Different implementations have different time/space
tradeoffs.

1.8 Memory Representation & Layout

• Stack (call stack) vs heap (dynamic allocation).

• Endianness: Big-endian vs little-endian affects byte order in memory.

• Alignment & padding: CPUs may require aligned access; structs may contain padding bytes to meet alignment.

• Contiguous vs linked layout: Arrays are contiguous; linked lists store elements scattered in heap with pointers.

1.9 Type Systems (static/dynamic, strong/weak)

• Static typing: type checks at compile time → fewer runtime errors; often faster.

• Dynamic typing: types checked at runtime → more flexibility.

• Strong typing: prevents implicit conversions that can cause errors.

• Weak typing: allows implicit conversions (C/JS have many implicit casts).

1.10 Language-level constructs affecting data types & structures

• Generics / Templates: allow type-generic structures (Java generics, C++ templates).

• Garbage collection: memory management affects how you implement data structures (no manual free needed).

• Pointers vs references: pointer arithmetic available in C/C++ → powerful but error-prone.

1.11 Choosing a Data Structure — practical tips

• Need fast indexed access → choose array or dynamic array (vector/ArrayList).

• Need frequent insert/delete at ends → stack/queue or deque.

• Need fast insert/delete in middle with known node → linked list (but random access slow).

• Need associative lookup → hash table (average O(1)), balanced BST (O(log n)).

• Need ordered traversal with logarithmic ops → balanced BST (AVL/Red-Black).

 • Need priority extraction → heap (priority queue).

1.12 Example: struct vs class

• struct (C) = aggregate data with no methods. In C++/C#, struct differs in default access and allocation semantics.

• class bundles data + methods; encapsulation and possibly inheritance.

50 Important MCQs — Data Types & Data Structures (each with answer + brief explanation)

Q1. Which of the following is a primitive data type in C?

a) struct b) int c) array d) enum
Answer: b. int is a primitive numeric type; struct and array are composite; enum is user-defined.

Q2. A language with static typing performs type checks at:

a) runtime only b) compile time only c) both d) never
Answer: b. Static typing is compile-time.

Q3. Which storage layout guarantees O(1) time to access the i-th element?
a) Singly linked list b) Array c) Binary tree d) Hash table (worst-case)
Answer: b. Arrays provide direct indexing.

Q4. In C, what does sizeof(char) typically return?

a) 2 b) 1 c) 4 d) depends on machine
Answer: b. sizeof(char) is defined as 1 (one byte) by the C standard.

Q5. The main difference between an ADT and a data structure is:
a) ADT describes memory layout b) ADT specifies behavior only c) Data structure is abstract d) ADT is always implemented with array
Answer: b. ADT defines behavior (operations), not layout.

Q6. Which data structure uses FIFO order?

a) Stack b) Queue c) Tree d) Graph
Answer: b. Queue is first-in-first-out.

Q7. Which of the following is not an aggregate type?

a) Array b) Pointer c) Struct d) Union
Answer: b. Pointer is a derived type referencing another type; arrays/structs/unions aggregate multiple values.

Q8. Which is true about a union in C?

a) Each member has separate memory b) Members share the same memory c) Union cannot contain structs d) Size is sum of members
sizes
Answer: b. Union members overlap in the same memory area.

Q9. Which of the following best describes little-endian?

a) Most-significant byte stored first b) Least-significant byte stored first c) Bytes stored randomly d) Only used in RISC processors
Answer: b. Little-endian stores least-significant byte at lowest address.

Q10. char in C may be signed or unsigned depending on implementation. This is an example of:
a) Static typing b) Implementation-defined behavior c) Undefined behavior d) Platform-independent feature
Answer: b. Whether char is signed or unsigned is implementation-defined.

Q11. Which type of collection is best for associative lookup by key with average O(1) operations?
a) Array b) Linked list c) Hash table d) Binary heap
Answer: c. Hash table gives average O(1) lookup.

Q12. In a record/struct, fields are normally:

a) Homogeneous b) Heterogeneous c) All floats d) None of the above
Answer: b. A struct can contain fields of different types.

Q13. Which ADT supports push, pop, peek operations?

a) Queue b) Set c) Stack d) Map
Answer: c. Stack supports push/pop/peek.

Q14. Which of the following is true about arrays and linked lists?
a) Arrays are dynamic by default b) Linked lists give O(1) random access c) Arrays have contiguous memory d) Linked lists are contiguous
Answer: c. Arrays occupy contiguous memory.

Q15. In dynamically-typed language, type errors are typically detected:

a) At compile time b) At link time c) At runtime d) Never
Answer: c. Dynamic languages check types at runtime.
Q16. A pointer in C stores:
a) A copy of the data b) Memory address c) Type information d) Size of data
Answer: b. Pointers store addresses.

Q17. Which of these is NOT an ADT?

a) Stack b) Queue c) Array d) Map
Answer: c. Array is a concrete data structure; Stack/Queue/Map are ADTs (though arrays are also an abstract concept in some contexts).

Q18. Which data type would you choose to store a large list of integers where you need frequent insertion in the middle?
a) Static array b) Linked list c) Hash table d) Binary search tree
Answer: b. Linked lists allow O(1) insertion once you have the node pointer (but O(n) to find position).

Q19. Which of the following is true about enum in C?

a) It holds only string constants b) It assigns integer constants to symbolic names c) It is same as struct d) It is dynamically sized
Answer: b. enum maps names to integer constants.

Q20. Which is the correct description of a reference in Java?

a) Contains actual object data b) Contains memory address that refers to object c) Can do pointer arithmetic d) Stored on stack always
Answer: b. Java references point to heap objects; pointer arithmetic is not allowed.

Q21. Which of these language features helps write type-safe generic data structures?
a) Templates (C++) b) Macros (C) c) #define d) Goto
Answer: a. Templates provide compile-time generic types; Java generics do similar.

Q22. Which is most memory-efficient to represent a dense fixed-size table of integers?

a) Linked list of nodes b) Array c) Binary tree d) Hash table
Answer: b. Arrays have minimal per-element overhead.

Q23. The difference between struct and class in C++ is:

a) Nothing functionally except default access specifier (struct=public, class=private). b) struct can't have functions. c) class can't have public
fields. d) struct is not supported in C++
Answer: a. In C++ only default access differs.

Q24. Which is an advantage of typed languages with strong typing?

a) Faster development always b) Prevent certain classes of errors at compile-time c) Always better performance than untyped languages d)
Eliminates need for testing
Answer: b. Strong typing catches many type errors early.

Q25. Which of the following is a mutable data type in Python?

a) tuple b) string c) list d) int
Answer: c. list is mutable; tuple, string, and int are immutable.

Q26. Which storage allocation strategy gives variable-sized objects lifetime controlled by programmer (malloc/free)?
a) Automatic (stack) allocation b) Static allocation c) Dynamic (heap) allocation d) Register allocation
Answer: c. Dynamic heap allocation managed by malloc/free.

Q27. Which of these is NOT typically a property of an ADT?

a) It defines operations b) It defines implementation c) It defines behavior d) It hides implementation details
Answer: b. ADT specifies behavior, not implementation.

Q28. In memory alignment, padding is introduced to:

a) Save memory b) Make struct smaller c) Satisfy CPU alignment requirements d) Allow duplicate fields
Answer: c. Padding ensures fields are aligned for efficient CPU access.

Q29. Which representation of a graph is better when the graph is sparse (few edges)?
a) Adjacency matrix b) Edge list c) Adjacency list d) Incidence matrix
Answer: c. Adjacency list uses memory proportional to vertices + edges and is good for sparse graphs.

Q30. What does typedef do in C?

a) Creates a new data type with different runtime behavior b) Creates an alias for an existing type c) Changes the size of type d) Adds
methods to type
Answer: b. typedef creates an alias (no runtime change).

Q31. Which of the following is false about arrays?

a) Arrays store homogeneous elements. b) Array size fixed at compile time in static arrays. c) Arrays support efficient insertion at arbitrary
positions. d) Memory is contiguous.
Answer: c. Arbitrary insertions in arrays require shifting elements (O(n)).

Q32. A data type that allows values which are not defined by language (e.g., user created) is called:
a) Primitive type b) Built-in type c) User-defined type d) None of the above
Answer: c. User-defined types (struct, class, enum).
Q33. What is the advantage of using a linked list over an array?
a) Faster random access b) Less memory per element c) Dynamic size and efficient insertion/deletion (given node) d) No pointers needed
Answer: c. Linked lists allow dynamic growth and easy insert/delete.

Q34. The term “boxing” in programming languages refers to:

a) Moving data into a container b) Converting a value type to a reference type c) Encryption d) Memory allocation on stack
Answer: b. Boxing wraps a primitive/value into an object/reference.

Q35. Which is correct about immutable objects?

a) Their internal state can change after creation b) They cannot be used as keys in hash tables c) Once created, their state cannot change d)
Always faster than mutable objects
Answer: c. Immutable objects cannot change state once created.

Q36. Which data structure organizes data in paired key→value fashion?

a) Set b) Map/Dictionary c) Queue d) Stack
Answer: b. Map/Dictionary stores key-value pairs.

Q37. If int is 4 bytes and double is 8 bytes, what is minimal size of struct { char c; double d; } on typical aligned system?
a) 9 bytes b) 12 bytes c) 16 bytes d) 24 bytes
Answer: c. Likely 16 bytes: 1 byte char + 7 bytes padding + 8 byte double (alignment makes struct size 16).

Q38. The term “aliasing” in pointers refers to:

a) Two variables have same type name b) Two pointers/reference refer to same memory location c) Changing type names via typedef d)
None of the above
Answer: b. Aliasing occurs when multiple references/pointers refer to same memory.

Q39. Which data type would be best to implement a dictionary where ordered traversal by key is required and operations remain O(log n)?
a) Hash table b) Balanced binary search tree (AVL/Red-Black) c) Array d) Unsorted linked list
Answer: b. Balanced BST provides ordered traversal and O(log n) ops.

Q40. Endianness affects:

a) Logical operations only b) Order of bytes in multi-byte values c) Size of data types d) Number of bits in a byte
Answer: b. Endianness determines byte order.

Q41. Which is true: In Java arrays are:

a) Immutable in length b) Dynamic and auto-resizable c) Always stored on stack d) Equivalent to linked lists
Answer: a. Java arrays have fixed length once created.

Q42. Which of these is a correct reason to use a bit-field in C struct?

a) To pack multiple boolean flags into fewer bits (save space) b) To allow pointer arithmetic c) To store floating point numbers d) To make
code portable across platforms
Answer: a. Bit-fields are used to pack small fields into fewer bits.

Q43. Which of the following best describes a sparse array?

a) An array with mostly zero/empty values b) An array implemented as contiguous memory c) Only used for strings d) Same as dense array
Answer: a. Sparse array has many empty or zero elements; often stored via maps or special structures.

Q44. Which of the following languages is strongly typed?

a) Python b) JavaScript c) C (weakly typed) d) Java (strongly typed)
Answer: d. Java is strongly typed; Python is dynamically but strongly typed too—(note: for exam, Java is canonical strong typed). (If asked,
explain Python is dynamically typed but enforces type rules at runtime — still considered strongly typed in many contexts.)

Q45. Which of the following is true about garbage-collected languages?

a) Programmers never need to worry about memory b) They may still have memory leaks (e.g., via lingering references) c) No runtime cost
d) Prevent all bugs
Answer: b. GC exists but leaks can happen if references persist.

Q46. What is the time complexity of accessing a value by key in a balanced binary search tree?
a) O(1) b) O(log n) c) O(n) d) O(n log n)
Answer: b. Balanced BST search is O(log n).

Q47. Which of these accurately describes union vs struct in C?

a) union fields share same memory, struct fields occupy separate memory b) union has methods, struct does not c) union is always bigger
than struct d) Both are identical
Answer: a. Unions overlap storage; structs allocate separate space for each member.

Q48. Which data structure is best to implement LIFO undo feature?

a) Queue b) Stack c) Hash table d) Heap
Answer: b. Stack is LIFO — perfect for undo.

Q49. Which of these operations is NOT commonly associated with the ADT Map (dictionary)?
a) insert(key, value) b) delete(key) c) get(key) d) pop_front()
Answer: d. pop_front() is typical for deque/list, not map.
Q50. If a programming language allows implicit conversion from float to int by truncation without error, this is called:
a) Strong typing b) Weak typing / implicit coercion c) Static typing d) Type erasure
Answer: b. Implicit coercion indicates weaker typing rules.

Section 2 — Concept of Linear and Nonlinear Data Structures

2.1 Introduction

Data structures are classified into two broad categories based on how data elements are organized and accessed:

1. Linear Data Structures

2. Nonlinear Data Structures

The classification depends on the logical arrangement of elements and the relationship between them.

2.2 Linear Data Structures

Definition
A data structure is linear if:
• All elements are arranged sequentially (one after another).
• Each element has a unique predecessor and a unique successor (except the first and last elements).
• Traversal is done in a single run from start to end.
Examples
• Arrays
• Linked Lists
• Stacks
• Queues
Properties
• Single level of data.
• Traversal is sequential.
• Can be implemented using arrays or linked lists.
Advantages
• Easy to implement and traverse.
• Memory allocation can be static (arrays) or dynamic (linked lists).
Disadvantages
• Searching in an unsorted linear structure is O(n).
• For arrays, insertion and deletion are costly.

2.3 Nonlinear Data Structures

Definition
A data structure is nonlinear if:
• Data elements are not arranged sequentially.
• Each element can be connected to multiple elements.
• Traversal may require visiting nodes in a hierarchy or network.
Examples

• Trees

• Graphs

Properties

• Multiple paths for traversal.

• Used to represent hierarchical relationships (tree) or network connections (graph).

Advantages

• More efficient for representing complex relationships.

• Suitable for operations like searching in hierarchical data.

Disadvantages

• More complex to implement and traverse.

 • Requires more memory for storing connections (pointers/edges).

2.4 Differences Between Linear & Nonlinear Data Structures

Aspect Linear Nonlinear

Arrangement Sequential Hierarchical / Network

Traversal One level, sequential Multiple levels, non-sequential

Examples Array, Linked List, Stack, Queue Tree, Graph

Each element has a single predecessor and successor (except Elements may have multiple predecessors or
Predecessor/Successor
ends) successors

Implementation Easier More complex

Memory Usage Usually less (simple pointers or indexes) More (multiple references/edges)

2.5 Real-Life Examples

• Linear: Train coaches (one after another), queue in a ticket counter.

• Nonlinear: Family tree (parent-child relationships), road maps (graph).

50 MCQs — Concept of Linear and Nonlinear Data Structures

Q1. Which of the following is NOT a linear data structure?

a) Stack
b) Queue
c) Tree
d) Array
Answer: c — Tree is nonlinear.

Q2. In a linear data structure, each element has:

a) Multiple predecessors and successors
b) No connection to other elements
c) Only one predecessor and one successor (except ends)
d) Only one successor
Answer: c — That’s the definition.

Q3. Which of the following is a nonlinear data structure?

a) Linked list
b) Stack
c) Graph
d) Queue
Answer: c — Graph is nonlinear.

Q4. Arrays and linked lists are:

a) Nonlinear
b) Linear
c) Both
d) None
Answer: b — Both are linear.
Q5. Which of the following best describes nonlinear structures?
a) Sequential storage
b) Hierarchical/network storage
c) Data stored only in arrays
d) One-to-one connections
Answer: b — Nonlinear = hierarchy/network.

Q6. In a linear structure, traversal is:

a) Random
b) Sequential
c) Parallel
d) None
Answer: b — Sequential.

Q7. Example of a linear structure used for LIFO is:

a) Stack
b) Queue
c) Tree
d) Graph
Answer: a — Stack is LIFO linear.

Q8. Example of nonlinear structure used for routing:

a) Queue
b) Array
c) Graph
d) Stack
Answer: c — Graphs are used in routing.

Q9. Which is easier to implement?

a) Linear structure
b) Nonlinear structure
c) Both are same
d) Depends on programming language
Answer: a — Linear is simpler.

Q10. Which structure is suitable for representing parent-child relationships?

a) Array
b) Queue
c) Tree
d) Stack
Answer: c — Tree shows hierarchy.

Q11. In a graph, a node can be connected to:

a) One other node
b) Multiple nodes
c) No node
d) Only itself
Answer: b — Multiple connections possible.

Q12. Which structure is ideal for hierarchical searching?

a) Stack
b) Tree
c) Array
d) Queue
Answer: b — Trees enable fast hierarchical searches.

Q13. Which structure has exactly one path between two nodes?
a) Tree
b) Graph
c) Circular linked list
d) Queue
Answer: a — Tree property.

Q14. Which linear structure uses both ends for insertion and deletion?
a) Deque
b) Queue
c) Stack
d) Array
Answer: a — Double-ended queue.

Q15. Which nonlinear structure can have cycles?

a) Tree
b) Graph
c) Array
d) Stack
Answer: b — Graph may have cycles.

Q16. Which is NOT a feature of linear structures?

a) Single level of data
b) Simple traversal
c) Complex connections
d) Sequential storage
Answer: c — Complex connections = nonlinear.

Q17. Which is true about linear vs nonlinear?

a) Linear needs more memory than nonlinear
b) Nonlinear needs more memory for connections
c) Both need same memory
d) Memory usage depends only on elements count
Answer: b — More pointers in nonlinear.

Q18. Which is an application of a nonlinear structure?

a) Expression evaluation
b) CPU scheduling
c) File system hierarchy
d) Function call stack
Answer: c — File systems are tree-based.

Q19. Which is an application of a linear structure?

a) Social network
b) Train compartment arrangement
c) Road map
d) File system
Answer: b — Train coaches = linear.

Q20. The main difference between linear and nonlinear is:

a) Linear stores numbers, nonlinear stores strings
b) Linear has sequential arrangement, nonlinear is hierarchical/network
c) Linear is faster than nonlinear
d) Nonlinear cannot store integers
Answer: b — True definition.

Q21. Which structure would be best for breadth-first search (BFS)?

a) Stack
b) Queue
c) Tree
d) Graph
Answer: b — BFS uses queue.

Q22. Linked lists are considered linear because:

a) Data is in contiguous memory
b) Traversal is sequential through pointers
c) They have multiple paths
d) They store hierarchical data
Answer: b — Sequential traversal.

Q23. Which nonlinear structure is suitable for Dijkstra's shortest path?

a) Stack
b) Graph
c) Array
d) Queue
Answer: b — Graph algorithms.

Q24. Which is NOT a nonlinear data structure?

a) Tree
b) Heap
c) Queue
d) Graph
Answer: c — Queue is linear.

Q25. Which linear data structure can be static or dynamic?

a) Array only
b) Linked list only
c) Both array and linked list
d) None
Answer: c — Arrays (static/dynamic) and linked lists (dynamic).

Q26. Linear structure in which insertion and deletion happen at the same end:
a) Stack
b) Queue
c) Deque
d) Linked list
Answer: a — Stack (LIFO).

Q27. In nonlinear data structures, traversal order is:

a) Always fixed
b) Multiple possible orders
c) Always sequential
d) Always random
Answer: b — DFS, BFS, etc.

Q28. Which is an example of converting nonlinear to linear form?

a) Tree traversal
b) Array initialization
c) Stack pop
d) Queue enqueue
Answer: a — Traversing tree yields linear sequence.

Q29. In a complete binary tree, number of nodes in level l is:

a) l
b) 2^l
c) l^2
d) 2*l
Answer: b — Property of complete binary tree.
Q30. Graph edges can represent:
a) Relationships
b) Costs/distances
c) Directions
d) All of the above
Answer: d — Edges may carry weights, direction, relationship.

Q31. Which is used to implement function calls in programming languages?

a) Queue
b) Stack
c) Graph
d) Tree
Answer: b — Stack stores return addresses.

Q32. Which traversal uses queue in trees?

a) Preorder
b) Postorder
c) Level-order
d) Inorder
Answer: c — Level-order uses queue.

Q33. For representing a railway network, you would use:

a) Stack
b) Array
c) Graph
d) Queue
Answer: c — Graph for routes.

Q34. In an array, elements are stored:

a) Sequentially in memory
b) Random locations
c) With multiple references
d) Non-contiguously
Answer: a — Arrays use contiguous memory.

Q35. Which is better for constant-time insertion at known position if memory is not a concern?
a) Array
b) Linked list
c) Tree
d) Graph
Answer: b — Linked list.

Q36. In nonlinear structures like trees, insertion depends on:

a) Level and position rules
b) Array index
c) Random generation
d) Stack order
Answer: a — Insert rules depend on type of tree.

Q37. Which traversal is depth-first?

a) BFS
b) DFS
c) Level-order
d) Breadth traversal
Answer: b — DFS is depth-first.
Q38. Which has O(1) complexity for random access?
a) Array
b) Linked list
c) Tree
d) Graph
Answer: a — Array indexing.

Q39. Which is a disadvantage of linear structures?

a) Complex implementation
b) Cannot represent hierarchical data efficiently
c) Requires pointers
d) High memory usage
Answer: b — Not suited for hierarchy.

Q40. Which is an advantage of nonlinear structures?

a) Suitable for complex data relationships
b) Easier to implement
c) Less memory
d) Fixed traversal order
Answer: a — More expressive for relationships.

Q41. Stack and Queue differ in:

a) Number of elements
b) Insertion/deletion rules
c) Data type stored
d) None
Answer: b — LIFO vs FIFO.

Q42. Graph traversal where each edge is visited once is:

a) BFS
b) DFS
c) Euler tour
d) Inorder
Answer: c — Euler tour.

Q43. In a tree, a node without children is called:

a) Root
b) Leaf
c) Parent
d) Internal node
Answer: b — Leaf node.

Q44. Which is an example of both linear and nonlinear?

a) Adjacency list
b) Binary search tree
c) Linked list of queues
d) None
Answer: c — Combination possible.

Q45. A binary heap is considered:

a) Linear
b) Nonlinear
c) Neither
d) Sequential
Answer: b — Heap is tree-based nonlinear.

Q46. Which nonlinear structure is used for parsing expressions?

a) Tree
b) Stack
c) Queue
d) Array
Answer: a — Expression trees.

Q47. Which linear structure is used for printer job scheduling?

a) Stack
b) Queue
c) Tree
d) Graph
Answer: b — Queue for FIFO jobs.

Q48. Which nonlinear structure is best for shortest path problems?

a) Stack
b) Queue
c) Graph
d) Array
Answer: c — Graph.

Q49. Which is true for both linear and nonlinear structures?

a) Can be implemented using pointers
b) Always use arrays
c) Cannot store different data types
d) Always sorted
Answer: a — Both can use pointers.

Q50. In a tree, number of edges = number of nodes −:

a) 1
b) 2
c) Level count
d) None
Answer: a — Tree property.

Arrays – Full Depth Theory

1. Definition

An array is a finite collection of elements of the same data type, stored in contiguous memory locations, and accessed using indices.

2. Key Features

• Homogeneous elements – All elements have the same type (e.g., all integers).

• Fixed size – Size is decided at the time of declaration (in static arrays).

• Index-based access – Access time for an element is constant, O(1).

• Contiguous memory – Stored sequentially in RAM.

3. Representation

If an array is declared as:

int A[5] = {10, 20, 30, 40, 50}

• Index: 0 to 4

• Memory: Stored in continuous locations

• Base address: Address of A[0]

4. Types of Arrays

(a) One-Dimensional Array (1D)

• Stores elements in a single row.

• Accessed using one index: A[i].

(b) Two-Dimensional Array (2D)

• Stored in row-major or column-major order.

• Accessed using two indices: A[i][j].

(c) Multi-Dimensional Array

• More than two dimensions (e.g., 3D arrays A[i][j][k]).

(d) Static Array

• Fixed size; declared at compile time.

(e) Dynamic Array

• Can grow or shrink at runtime (e.g., Python lists, C++ vector).

5. Common Array Operations & Time Complexities

Operation Time Complexity

Access element O(1)

Insertion (end) O(1)

Insertion (middle) O(n)

Deletion (end) O(1)

Deletion (middle) O(n)

Search (linear) O(n)

Search (binary) O(log n)

6. Advantages

• Fast random access.

• Easy to implement.

• Can represent simple linear data.

7. Disadvantages

• Fixed size in static arrays.

• Insertion/deletion is costly (shifting elements).

• Wasted memory if array is under-utilized.

8. Real-life Examples

• Storing student marks.

 • Representing a chessboard (2D array).

• Image pixel storage.

50 MCQs on Arrays

Basic Level (1–15)

1. Which of the following best defines an array?

a) A collection of similar data elements stored at non-contiguous memory locations
b) A collection of similar data elements stored at contiguous memory locations
c) A collection of dissimilar data elements stored at contiguous memory locations
d) None of these
Ans: b

2. Index of first element in an array is:

a) 0
b) 1
c) -1
d) None
Ans: a

3. If an array has n elements, the last index is:

a) n
b) n+1
c) n-1
d) n-2
Ans: c

4. Accessing any element in an array takes:

a) O(1) time
b) O(n) time
c) O(log n) time
d) O(n²) time
Ans: a

5. What is the size of an array int A[10] in bytes if int is 4 bytes?

a) 10
b) 40
c) 14
d) 20
Ans: b

6. Two-dimensional arrays are stored in memory in:

a) Row-major order
b) Column-major order
c) Either (a) or (b) depending on language
d) None of these
Ans: c

7. Which of the following languages uses column-major order for 2D arrays?

a) C
b) Java
c) Fortran
d) Python
Ans: c

8. An array can be used to implement:

a) Stack
b) Queue
c) Matrix
d) All of the above
Ans: d

9. Which operation is fastest in an array?

a) Insertion at end
b) Deletion from middle
c) Searching a value
d) Insertion at beginning
Ans: a
 10. Wasted memory in an array occurs due to:
a) Fragmentation
b) Fixed size
c) Contiguous allocation
d) All of these
Ans: b

11. The array index must be:

a) A floating value
b) An integer or integer expression
c) A string
d) None of these
Ans: b

12. If array A[5] starts at address 200, each integer is 4 bytes, address of A[3] is:
a) 200
b) 208
c) 212
d) 216
Ans: c

13. The main disadvantage of arrays is:

a) Random access
b) Fixed size
c) Easy implementation
d) Homogeneous elements
Ans: b

14. In a 2D array, number of elements is given by:

a) rows × columns
b) rows + columns
c) rows – columns
d) None of these
Ans: a

15. Which of these can be multi-dimensional?

a) Arrays
b) Linked Lists
c) Stacks
d) All of these
Ans: a

Conceptual Level (16–30)

16. Which searching method works only on sorted arrays?

a) Linear search
b) Binary search
c) Hashing
d) BFS
Ans: b

17. If insertion is always at the end in an array, the complexity is:

a) O(1)
b) O(n)
c) O(log n)
d) O(n²)
Ans: a

18. Which of the following does not apply to arrays?

a) Dynamic resizing (in static arrays)
b) Fixed data type
c) Contiguous memory
d) Indexed access
Ans: a

19. If an array contains n elements, linear search worst case time is:
a) O(1)
b) O(n)
c) O(log n)
d) O(n log n)
Ans: b
 20. The term “row-major order” means:
a) Consecutive elements of the rows are stored next to each other
b) Consecutive elements of the columns are stored next to each other
c) Memory is allocated column by column
d) None
Ans: a

21. What is the time complexity to insert an element at the beginning of an array?
a) O(1)
b) O(log n)
c) O(n)
d) O(n²)
Answer: c) O(n)

22. Which of the following is NOT a type of array?

a) Single-dimensional array
b) Two-dimensional array
c) Multi-dimensional array
d) Associative array in C
Answer: d) Associative array in C

23. If an array starts at memory address 1000 and each element takes 4 bytes, what is the address of the 5th element?
a) 1004
b) 1016
c) 1020
d) 1024
Answer: c) 1020

24. Which of these statements is true about arrays?

a) They are always dynamic in size
b) They have fixed size once declared
c) They can shrink and grow automatically
d) They store elements in random order
Answer: b) They have fixed size once declared

25. Accessing an element in an array using its index takes:

a) O(1) time
b) O(n) time
c) O(log n) time
d) O(n²) time
Answer: a) O(1) time

26. What will happen if you access an array index out of bounds in C?
a) Program will terminate with error
b) It will cause undefined behavior
c) It will print garbage value
d) Both b and c are possible
Answer: d) Both b and c are possible

27. Which of the following is the correct formula to calculate the location of an element in a 1D array?
a) Base address + (index × element size)
b) Base address × (index × element size)
c) Base address + index + element size
d) Base address × index + element size
Answer: a) Base address + (index × element size)

28. If an array is stored row-wise in memory, it is known as:

a) Row-major order
b) Column-major order
c) Indexed order
d) None of these
Answer: a) Row-major order

29. Which of these is a drawback of arrays?

a) Random access
b) Fixed size
c) Contiguous memory
d) Storing similar data types
Answer: b) Fixed size

30. Which operation is costly for arrays compared to linked lists?

a) Traversal
b) Insertion at the end
c) Deletion at the beginning
d) Access by index
Answer: c) Deletion at the beginning

31. Which of these algorithms often use arrays as a base structure?

a) Binary search
b) Breadth First Search
c) Depth First Search
d) Dijkstra’s Algorithm
Answer: a) Binary search

32. The time complexity for merging two sorted arrays is:
a) O(n)
b) O(n log n)
c) O(n²)
d) O(log n)
Answer: a) O(n)

33. Which array indexing is default in most programming languages?

a) 0-based indexing
b) 1-based indexing
c) -1 based indexing
d) Any of the above
Answer: a) 0-based indexing

34. If an array contains n elements, what is the last valid index?

a) n
b) n-1
c) n+1
d) 0
Answer: b) n-1

35. Which array representation requires less memory?

a) Sparse array stored as normal array
b) Sparse array stored as linked list of non-zero values
c) Dense array stored as normal array
d) None of these
Answer: b) Sparse array stored as linked list of non-zero values

36. Which of the following is true about multidimensional arrays?

a) They are stored in contiguous memory
b) They require nested loops for traversal
c) They can be of any dimension
d) All of the above
Answer: d) All of the above

37. Which searching technique works best with sorted arrays?

a) Linear Search
b) Binary Search
c) Jump Search
d) Both b and c
Answer: d) Both b and c

38. The process of rearranging elements in an array is called:

a) Sorting
b) Searching
c) Hashing
d) Traversing
Answer: a) Sorting

39. Which type of array allows different row sizes?

a) Regular array
b) Jagged array
c) Multi-dimensional array
d) Circular array
Answer: b) Jagged array

40. Which of these is an advantage of arrays over linked lists?

a) Faster random access
b) Dynamic size
c) Easy insertion at the beginning
d) Less memory wastage in small data
Answer: a) Faster random access
41. Which is the correct representation of a 2D array element in row-major form?
a) Base address + (row_index × number_of_columns + col_index) × element_size
b) Base address + (col_index × number_of_rows + row_index) × element_size
c) Base address + row_index + col_index × element_size
d) None of these
Answer: a) Base address + (row_index × number_of_columns + col_index) × element_size

42. The time complexity for deleting an element at a specific index in an array is:
a) O(1)
b) O(n)
c) O(log n)
d) O(n²)
Answer: b) O(n)

43. Which one is a limitation of arrays in C?

a) Cannot store elements of different types
b) Cannot store negative numbers
c) Cannot store in sorted order
d) Cannot access elements by index
Answer: a) Cannot store elements of different types

44. The address of arr[0] is called:

a) Base address
b) First address
c) Initial address
d) Starting point
Answer: a) Base address

45. Which of these operations is not directly supported by arrays?

a) Insertion
b) Deletion
c) Searching
d) Dynamic resizing
Answer: d) Dynamic resizing

46. Which of these is an example of a fixed-size data structure?

a) Array
b) Linked list
c) Stack implemented using linked list
d) Binary tree
Answer: a) Array

47. When an array is declared but not initialized, what values does it hold in C?
a) All zeros
b) Garbage values
c) Null values
d) Compiler error
Answer: b) Garbage values

48. Which of these is true about arrays in memory?

a) Elements are stored in continuous blocks
b) Elements may be scattered in memory
c) Each element can be stored anywhere
d) Each element has separate memory allocation request
Answer: a) Elements are stored in continuous blocks

49. Which of the following is a dynamic array implementation in C++?

a) Vector
b) ArrayList
c) Linked list
d) Stack
Answer: a) Vector

50. Which operation takes the least time in an array?

a) Insertion at the beginning
b) Deletion at the beginning
c) Access by index
d) Insertion at middle
Answer: c) Access by index

Linked List – In-Depth Theory

Definition
A linked list is a linear data structure in which elements (called nodes) are connected using pointers (references).
Each node contains:

1. Data – the actual information to store.

2. Pointer/Link – address of the next node (or previous node in doubly linked list).

Unlike arrays, linked lists do not store elements in contiguous memory locations. They allow dynamic memory allocation.

Why Linked List?

• Dynamic Size – Can grow or shrink at runtime without reallocation.

• Efficient Insert/Delete – No shifting required as in arrays.

• Memory Utilization – Uses only required memory (no need to reserve large blocks).

Drawbacks

• No Direct Access – Access is sequential (O(n) time complexity).

• Extra Memory for Pointers.

• More complex implementation compared to arrays.

Types of Linked Lists

1. Singly Linked List

o Each node points to the next node.

o Last node’s pointer is NULL.

o Traversal only in one direction.

o Example: Head -> 10 -> 20 -> 30 -> NULL

2. Doubly Linked List

o Each node has two pointers:

▪ One to the next node.

▪ One to the previous node.

o Traversal possible both ways.

o Example: NULL <- 10 <-> 20 <-> 30 -> NULL

3. Circular Linked List

o Last node points back to the head node.

o Can be singly or doubly circular.

o Example: 10 -> 20 -> 30 -> back to 10

4. Circular Doubly Linked List

o Each node has previous and next pointers.

o Last node points back to head, and head’s previous pointer points to last.

Basic Operations

• Traversal – Visit each node from head to end (or circularly).

 • Insertion

o At beginning

o At end

o After a given node

• Deletion

o At beginning

o At end

o After a given node

• Searching – Sequential search from head to find a value.

Time Complexity

Operation Singly Linked List Doubly Linked List

Traversal O(n) O(n)

Search O(n) O(n)

Insertion at head O(1) O(1)

Insertion at end O(n) O(1) if tail kept

Deletion at head O(1) O(1)

Deletion at end O(n) O(1) if tail kept

Applications

• Music/Video Playlist (next & previous track)

• Undo/Redo in text editors

• Dynamic memory allocation

• Hash tables with chaining

• Navigation systems

50 MCQs on Linked List (With Answers)

Basic (1–15)

1. In a linked list, data elements are stored in:

o a) Contiguous memory

o b) Non-contiguous memory

o c) Random memory

o d) Cache memory

2. Which is NOT a type of linked list?

o a) Singly linked

o b) Doubly linked
 o c) Triply linked

o d) Circular linked

3. In a singly linked list, the last node contains:

o a) NULL

o b) Head

o c) Random data

o d) None

4. Which linked list supports traversal in both directions?

o a) Singly

o b) Doubly

o c) Circular

o d) None

5. The extra memory in linked lists is used for:

o a) Data

o b) Pointer

o c) Index

o d) None

6. Linked lists are best for:

o a) Random access

o b) Insertion/deletion

o c) Searching

o d) None

7. Which pointer in doubly linked list points to the previous node?

o a) next

o b) prev

o c) head

o d) link

8. The head pointer points to:

o a) Last node

o b) First node

o c) Middle node

o d) NULL

9. In circular linked list, last node’s pointer points to:

o a) NULL

o b) Head

o c) Middle node

o d) None

10. Which is the most time-consuming operation in singly linked list?

 o a) Insert at head

o b) Insert at end

o c) Delete at head

o d) Delete at head

11. A doubly linked list node has:

o a) 1 pointer

o b) 2 pointers

o c) 3 pointers

o d) None

12. The process of visiting each node once is:

o a) Traversal

o b) Searching

o c) Deletion

o d) Insertion

13. Which linked list type is best for implementing a playlist?

o a) Singly

o b) Doubly

o c) Circular

o d) Array

14. A pointer to a pointer is often used for:

o a) Deletion

o b) Insertion

o c) Managing head pointer

o d) Traversal

15. What is needed to reverse a linked list?

o a) Recursion or Iteration

o b) Random access

o c) Indexing

o d) Binary tree

Conceptual (16–30)

16. In linked lists, time complexity of accessing nth element is:

o a) O(1)

o b) O(n)

o c) O(log n)

o d) O(n log n)

17. The major advantage of linked list over arrays is:

o a) Faster random access

 o b) Dynamic size

o c) Cache optimization

o d) Sorting speed

18. Deletion at end in singly linked list requires:

o a) Only head

o b) Traversal to last node

o c) Indexing

o d) None

19. Which pointer changes in insertion at head?

o a) Tail pointer

o b) Head pointer

o c) Middle pointer

o d) None

20. In circular linked list, traversal can:

o a) End after one loop

o b) Continue infinitely

o c) Stop at NULL

o d) None

31. Which operation in a linked list requires updating only the head pointer?
a) Insertion at end
b) Deletion at end
c) Insertion at beginning
d) Searching
Answer: c) Insertion at beginning

32. In a circular linked list, which node’s next pointer points to the head?
a) First node
b) Last node
c) Middle node
d) None
Answer: b) Last node

33. In a singly linked list, deletion at the end requires:

a) Access to previous node
b) Access to head only
c) Access to tail only
d) No pointer change
Answer: a) Access to previous node

34. What is a self-referential structure?

a) A structure that points to itself
b) A structure that has no members
c) A structure that stores only integers
d) None
Answer: a) A structure that points to itself

35. What is the time complexity of inserting at the end of a singly linked list (without tail pointer)?
a) O(1)
b) O(n)
c) O(log n)
d) O(n²)
Answer: b) O(n)

36. Which linked list allows traversal in both directions?

a) Singly linked list
b) Doubly linked list
c) Circular singly linked list
d) None
Answer: b) Doubly linked list

37. Which linked list is best for implementing an undo operation in text editors?
a) Circular linked list
b) Doubly linked list
c) Singly linked list
d) None
Answer: b) Doubly linked list

38. In a circular doubly linked list, the head’s previous pointer points to:
a) NULL
b) Tail node
c) Middle node
d) None
Answer: b) Tail node

39. What is the main advantage of circular linked list over singly linked list?
a) Easy backward traversal
b) No NULL at the end
c) Easy to implement stacks
d) None
Answer: b) No NULL at the end

40. Which data structure is more memory-efficient when frequent insertions and deletions occur?
a) Array
b) Linked list
c) Stack
d) Queue
Answer: b) Linked list

41. Which linked list uses two links per node?

a) Singly linked list
b) Doubly linked list
c) Circular singly linked list
d) None
Answer: b) Doubly linked list

42. Which is NOT a type of linked list?

a) Singly
b) Doubly
c) Triple
d) Circular
Answer: c) Triple

43. The last node in a singly linked list contains:

a) Garbage value in pointer
b) Pointer to head
c) NULL pointer
d) None
Answer: c) NULL pointer

44. The last node in a circular singly linked list contains:

a) NULL
b) Pointer to head
c) Pointer to tail
d) None
Answer: b) Pointer to head

45. What is the drawback of doubly linked list compared to singly linked list?
a) Slower traversal
b) Requires more memory per node
c) Cannot store strings
d) None
Answer: b) Requires more memory per node

46. Which traversal is possible in singly linked list?

a) Forward
b) Backward
c) Both forward and backward
d) None
Answer: a) Forward
47. To find the length of a linked list, complexity is:
a) O(1)
b) O(n)
c) O(log n)
d) O(n²)
Answer: b) O(n)

48. Inserting after a given node in a singly linked list requires:

a) Updating one pointer
b) Updating two pointers
c) No pointer update
d) None
Answer: b) Updating two pointers

49. Which data structure is preferred for constant-time insertions/deletions from the middle?
a) Array
b) Linked list
c) Queue
d) Stack
Answer: b) Linked list

50. Which of the following is TRUE for linked lists compared to arrays?
a) Random access is faster
b) Better cache locality
c) Easier memory allocation/deallocation
d) All of the above
Answer: c) Easier memory allocation/deallocation

Stack – In-depth Theory

Definition

A stack is a linear data structure that follows the LIFO principle – Last In, First Out.
This means the last element inserted into the stack is the first one to be removed.

Key Characteristics

• LIFO operation order.

• Only one end (called top) is used for insertion (push) and deletion (pop).

• Stack operations are usually done in O(1) time.

Basic Stack Operations

1. Push(x) → Insert an element x onto the top of the stack.

2. Pop() → Remove and return the element from the top of the stack.

3. Peek()/Top() → View the top element without removing it.

4. isEmpty() → Checks if stack is empty.

5. isFull() → Checks if stack is full (array-based stack).

Types of Stacks

1. Static Stack – Implemented using arrays (fixed size).

2. Dynamic Stack – Implemented using linked list (can grow dynamically).

Stack Overflow & Underflow

• Overflow – Trying to push into a full stack (common in static stack).

• Underflow – Trying to pop from an empty stack.

Applications of Stack

1. Expression Conversion – Infix ↔ Postfix ↔ Prefix.

2. Expression Evaluation – Evaluate postfix/prefix expressions.

3. Function Calls – Call stack in programming languages.

4. Undo/Redo Operations in editors.

5. Balanced Parentheses Checking.

Expression Types

• Infix: Operator between operands (e.g., A + B).

• Prefix: Operator before operands (e.g., + A B).

• Postfix: Operator after operands (e.g., A B +).

Why use postfix/prefix?

• No need for parentheses.

• Easy to evaluate using stacks.

Time & Space Complexity

Operation Complexity

Push O(1)

Pop O(1)

Peek O(1)

Search O(n)

50 MCQs on Stack (with answers)

Basic Level

1. A stack works on the principle of:

a) FIFO
b) LIFO
c) LILO
d) FILO
Ans: b

2. Which operation removes the top element from the stack?

a) Pop
b) Push
c) Peek
d) Insert
Ans: a

3. In an array-based stack, overflow occurs when:

a) Top = -1
b) Top = n - 1
c) Top = 0
d) None
Ans: b

4. In a linked list-based stack, overflow occurs when:

a) List is empty
 b) Memory is exhausted
c) Top = n - 1
d) None
Ans: b

5. What is the initial value of top in an empty stack (array implementation)?

a) 0
b) -1
c) 1
d) None
Ans: b

6. Which operation is not possible in stack?

a) Push
b) Pop
c) Deletion from middle
d) Peek
Ans: c

7. The “call stack” in C language is mainly used for:

a) Variable storage
b) Function call management
c) File handling
d) None
Ans: b

8. If we push 1, 2, 3 into a stack and pop one, what is popped?

a) 1
b) 2
c) 3
d) None
Ans: c

9. Which of the following uses stack?

a) Depth First Search
b) Breadth First Search
c) Both
d) None
Ans: a

10. Stack is best represented using:

a) Queue
b) Linked List or Array
c) Graph
d) Tree
Ans: b

Conceptual Level

11. In postfix evaluation, the stack is used to:

a) Store operators only
b) Store operands only
c) Store both operands and intermediate results
d) None
Ans: c

12. What will be the output if postfix 2 3 * 5 + is evaluated?

a) 11
b) 15
c) 10
d) None
Ans: a

13. Which traversal of a binary tree uses a stack implicitly in recursion?

a) Preorder
b) Inorder
c) Postorder
d) All
Ans: d
 14. In an array-based stack of size n, the maximum number of elements it can hold is:
a) n
b) n+1
c) n-1
d) Infinite
Ans: a

15. Which one is NOT an application of stack?

a) Backtracking
b) Undo operation in editor
c) Implementing recursion
d) Storing queues
Ans: d

16. Conversion from infix to postfix is done using:

a) Queue
b) Stack
c) Array
d) None
Ans: b

17. Which notation is free from operator precedence rules?

a) Infix
b) Postfix
c) Both
d) None
Ans: b

18. Pop from an empty stack is called:

a) Overflow
b) Underflow
c) Exception
d) None
Ans: b

19. Which memory structure is used for recursion?

a) Heap
b) Stack
c) Queue
d) Tree
Ans: b

20. Which of these is an example of a bounded stack?

a) Array stack with fixed size
b) Linked list stack
c) Both
d) None
Ans: a

Moderate Level

21. If elements 1, 2, 3, 4 are pushed and popped alternately, the sequence is:
a) 4 3 2 1
b) 1 2 3 4
c) 1 2 4 3
d) None
Ans: c

22. Which data structure is used in function call/return mechanism?

a) Queue
b) Stack
c) Heap
d) Array
Ans: b

23. The reverse of a string can be implemented using:

a) Stack
b) Queue
c) Linked List
d) Graph
Ans: a
 24. In postfix evaluation, each operator:
a) Pops two operands
b) Pops one operand
c) Pops three operands
d) None
Ans: a

25. Time complexity of push/pop is:

a) O(1)
b) O(n)
c) O(log n)
d) None
Ans: a

26. Which statement is true?

a) Stack allows random access
b) Stack does not allow random access
Ans: b

27. A stack implemented using linked list has no overflow unless:

a) Stack is empty
b) Memory is full
c) Linked list is full
d) None
Ans: b

28. Which operation can cause underflow?

a) Push
b) Pop
c) Peek
d) None
Ans: b

29. The output of infix (2 + 3) * 4 in postfix is:

a) 2 3 4 * +
b) 2 3 + 4 *
c) 2 3 + * 4
d) None
Ans: b

30. Infix to prefix conversion of (A+B)*C is:

a) +ABC
b) +ABC
c) AB+C*
d) None
Ans: a

Tricky Level

31. Which stack representation avoids overflow?

a) Fixed array
b) Linked list
Ans: b

32. For a stack of size 5, after pushing 5 elements and popping 2, how many are left?
a) 2
b) 3
c) 5
d) None
Ans: b

33. Which stack operation does NOT change the number of elements?
a) Push
b) Pop
c) Peek
Ans: c

34. Parenthesis matching uses:

a) Queue
b) Stack
Ans: b
35. If postfix is 6 2 / 3 - 4 2 * +, result is:
a) 8
b) 6
c) 7
d) None
Ans: b

36. Which of these is NOT true?

a) Push increases top by 1
b) Pop decreases top by 1
c) Peek increases top by 1
Ans: c

37. The space complexity of a stack storing n elements is:

a) O(n)
b) O(1)
Ans: a

38. A stack with min and max retrieval in O(1) needs:

a) Two stacks
b) One stack
c) Queue
Ans: a

39. Which of the following is not a postfix expression?

a) AB+
b) ABC+
c) ABC++
Ans: b

40. Which algorithm uses stack internally?

a) Quicksort
b) Merge sort
Ans: a

41. What is the reverse of prefix *+ABC in infix?

a) (A + B) * C
b) A * (B + C)
Ans: a

42. Which structure helps in implementing undo operation?

a) Stack
b) Queue
Ans: a

43. Which stack is used in browsers for back button?

a) Forward stack
b) Backward stack
Ans: b

44. The pop operation on empty stack returns:

a) Error
b) Null
Ans: a

45. In two-stack implementation in one array, overflow happens when:

a) top1 + 1 = top2
b) top1 = top2
Ans: a

46. Stack overflow in array happens when:

a) top >= size
b) top = size - 1
Ans: b

47. Which one is correct about recursion and stack?

a) Recursion always uses stack memory
b) Recursion sometimes uses heap
Ans: a

48. The evaluation of (3 + 4) * 5 in postfix is:

a) 3 4 + 5 *
 b) 3 4 * 5 +
Ans: a

49. Infix to postfix of (A + B) / (C - D) is:

a) AB+CD-/
b) ABCD-+/
Ans: a

50. Which operation is O(1) in stack?

a) Push and Pop
b) Search
Ans: a

Queue – Theory (In-Depth)

1. Definition

A Queue is a linear data structure that stores elements in a sequential manner, following the FIFO (First In, First Out) principle.

• The element added first is removed first.

• It is analogous to a queue of people waiting for a service.

2. Characteristics

• FIFO Order: First element inserted is the first to be removed.

• Two Ends:

o Front → position from which elements are removed.

o Rear → position where new elements are added.

• Dynamic or Static: Can be implemented using arrays (static) or linked lists (dynamic).

3. Basic Operations

1. Enqueue (Insertion): Add an element at the rear end.

2. Dequeue (Deletion): Remove an element from the front end.

3. Peek/Front: Get the element at the front without removing it.

4. isEmpty: Check if the queue is empty.

5. isFull: Check if the queue is full (in case of array implementation).

4. Types of Queues

1. Simple Queue

o Standard FIFO structure.

o Insertion at rear, deletion from front.

2. Circular Queue

o Last position is connected back to the first position to form a circle.

o Efficient use of space because when the rear reaches the end, it wraps to the front if space is available.

3. Priority Queue

o Each element has a priority.

o Higher priority elements are dequeued before lower priority elements.

 4. Double-Ended Queue (Deque)

o Insertion and deletion possible from both ends.

o Two types: Input Restricted Deque (insertion at one end only) and Output Restricted Deque (deletion at one end
only).

5. Time Complexity of Operations

Operation Array Implementation Linked List Implementation

Enqueue O(1) O(1)

Dequeue O(1) O(1)

Peek O(1) O(1)

isEmpty O(1) O(1)

isFull O(1) O(1)

6. Applications

• CPU scheduling in operating systems.

• Printer job management.

• Call center systems.

• Simulation of real-world queues (traffic systems, customer service).

• Breadth-First Search (BFS) in graph algorithms.

Queue – 50 MCQs with Answers

Basic Level (1–15)

1. A queue follows which principle?

a) LIFO
b) FIFO
c) FILO
d) LILO
Answer: b) FIFO

2. In a simple queue, insertion is done at the:

a) Front
b) Rear
c) Both ends
d) Middle
Answer: b) Rear

3. Deletion from a queue is done at the:

a) Front
b) Rear
c) Middle
d) Both ends
Answer: a) Front

4. Which of the following is not a type of queue?

a) Circular queue
b) Priority queue
c) Double-ended queue
d) Binary queue
Answer: d) Binary queue
5. What is the time complexity of dequeue operation in an array-based queue?
a) O(1)
b) O(n)
c) O(log n)
d) O(n log n)
Answer: a) O(1)

6. A priority queue always removes:

a) Oldest element
b) Element with lowest priority
c) Element with highest priority
d) Random element
Answer: c) Element with highest priority

7. The maximum number of elements a circular queue of size N can hold is:
a) N
b) N–1
c) N+1
d) Unlimited
Answer: b) N–1

8. In a double-ended queue, insertion and deletion are allowed from:

a) One end only
b) Rear only
c) Both ends
d) Front only
Answer: c) Both ends

9. The front pointer in a queue:

a) Always points to the last element
b) Always points to the first element
c) Points to the next free space
d) Is always zero
Answer: b) Always points to the first element

10. Which of the following is not an application of queues?

a) BFS in graphs
b) CPU scheduling
c) Undo operation in text editor
d) Call center simulations
Answer: c) Undo operation in text editor

11. In an array-based queue, what happens when the rear reaches the end of the array and there is still space at the front?
a) Overflow
b) Underflow
c) Wasted space
d) Use circular queue
Answer: d) Use circular queue

12. Underflow in a queue occurs when:

a) Queue is full
b) Queue is empty and dequeue is attempted
c) Queue has only one element
d) None of the above
Answer: b) Queue is empty and dequeue is attempted

13. Overflow in a queue occurs when:

a) Queue is empty
b) Queue is full and enqueue is attempted
c) Queue has only one element
d) None of the above
Answer: b) Queue is full and enqueue is attempted

14. The default priority in a priority queue is based on:

a) Time
b) Priority value
c) Random selection
d) Memory location
Answer: b) Priority value

15. Which data structure can be used to implement a queue?

a) Array
b) Linked list
 c) Both a and b
d) Tree
Answer: c) Both a and b

Conceptual Level (16–30)

16. In an array-based linear queue, which condition indicates overflow (without circular wrap)?
a) front == rear
b) rear == size - 1
c) front == -1
d) front == size - 1
Answer: b

17. In a circular queue, the next position of rear is computed as:

a) rear + 1
b) (rear + 1) / size
c) (rear + 1) % size
d) (rear - 1) % size
Answer: c

18. In a queue implemented with a singly linked list, where should enqueues happen for O(1) time?
a) At head only
b) At tail only
c) At both ends
d) In the middle
Answer: b

19. Which operation causes underflow in a queue?

a) Enqueue on full queue
b) Dequeue on empty queue
c) Peek on non-empty queue
d) Enqueue on empty queue
Answer: b

20. The time complexity of enqueue and dequeue in a properly implemented queue is:
a) O(log n) each
b) O(n) each
c) O(1) each
d) O(n log n) each
Answer: c

21. Which of the following is not a valid queue variant?

a) Circular queue
b) Double-ended queue (Deque)
c) Priority queue
d) Ternary queue
Answer: d

22. In a priority queue, deletion by default removes:

a) The oldest element
b) The most recently inserted element
c) The element with highest priority (or lowest key)
d) A random element
Answer: c

23. For a circular queue of size k, the queue is empty when:

a) front == rear and flag == empty
b) front == -1
c) (rear + 1) % k == front
d) rear == -1
Answer: a (one common approach; alternative conventions use front == -1)

24. In a linear array queue (without wrap), after many enqueues and dequeues, there can be unused cells at the front. This issue is called:
a) Overflow
b) Fragmentation (or Slack at front)
c) Underflow
d) Starvation
Answer: b

25. Which of the following is a typical application of queues?

a) Function call stack
b) Level-order traversal in trees
c) Infix to postfix conversion
d) Backtracking
Answer: b

26. In an array-based circular queue, the number of elements is computed as:

a) rear - front
b) (rear - front + size) % size
c) (front - rear + size) % size
d) size - (rear - front)
Answer: b

27. In an amortized O(1) queue built from two stacks (in and out), which sequence triggers moving elements from in to out?
a) On every enqueue
b) When out is empty and a dequeue/peek occurs
c) On every dequeue
d) When sizes of stacks are equal
Answer: b

28. A deque supports which operation that a standard queue does not?
a) Insert at rear
b) Delete from front
c) Insert at front
d) Peek
Answer: c

29. In a bounded circular queue of capacity n, a common full condition (without extra flag) is:
a) front == rear
b) (rear + 1) % n == front
c) rear == n - 1
d) front == -1
Answer: b

30. To avoid the “full vs empty” ambiguity in circular queues using only front and rear, a standard technique is to:
a) Keep one slot always unused
b) Use a min-heap
c) Reverse the queue when half full
d) Double the array every time
Answer: a

32. In a queue, what happens when we attempt to delete an element from an empty queue?
a) Underflow
b) Overflow
c) Garbage value returned
d) Undefined behavior
Answer: a) Underflow

33. Which data structure is best suited for job scheduling?

a) Stack
b) Queue
c) Linked List
d) Tree
Answer: b) Queue

34. Which queue is used for handling multiple priorities in scheduling?

a) Circular Queue
b) Priority Queue
c) Deque
d) Simple Queue
Answer: b) Priority Queue

35. In a circular queue implemented with an array of size N, the condition for a full queue is:
a) front == rear
b) (rear + 1) % N == front
c) rear == N - 1
d) front == 0
Answer: b) (rear + 1) % N == front

36. The process of inserting into a priority queue involves:

a) Adding to the end only
b) Adding in order of priority
c) Adding to the front always
d) None of the above
Answer: b) Adding in order of priority

37. Which of these queues can be implemented using two stacks?

a) Simple Queue
b) Circular Queue
c) Priority Queue
d) All of the above
Answer: a) Simple Queue

38. What is the worst-case time complexity for enqueuing in a linked-list-based queue?
a) O(1)
b) O(n)
c) O(log n)
d) O(n²)
Answer: a) O(1)

39. Which operation is not possible in a simple queue?

a) Insertion at rear
b) Deletion at front
c) Insertion at front
d) Displaying elements
Answer: c) Insertion at front

40. In which queue type do the elements leave in order of highest importance rather than arrival time?
a) Simple Queue
b) Deque
c) Priority Queue
d) Circular Queue
Answer: c) Priority Queue

41. In BFS (Breadth-First Search) traversal of a graph, which data structure is used?
a) Stack
b) Queue
c) Heap
d) Deque
Answer: b) Queue

42. If a queue is implemented using an array without circular logic, what happens after multiple deletions?
a) Overflow occurs quickly
b) Memory is reused
c) Memory is wasted
d) Elements rearrange automatically
Answer: c) Memory is wasted

43. The condition for an empty queue in a circular queue is:

a) rear == front
b) rear == front - 1
c) rear == 0
d) rear + 1 == front
Answer: a) rear == front

44. Which of the following statements about a double-ended queue is false?

a) Elements can be inserted at both ends
b) Elements can be deleted from both ends
c) It is the same as a circular queue
d) It can be used for both stack and queue operations
Answer: c) It is the same as a circular queue

45. Which real-world example fits a circular queue?

a) Undo operations in a text editor
b) CPU process scheduling
c) Function call stack
d) Binary search tree traversal
Answer: b) CPU process scheduling

46. Which queue allows insertion at one end and deletion from the same end?
a) Simple Queue
b) Circular Queue
c) Stack
d) None of the above
Answer: c) Stack
47. In a queue implemented with linked lists, the rear pointer should point to:
a) First element
b) Last element
c) Middle element
d) Null
Answer: b) Last element

48. The maximum number of elements in a circular queue of size 10 is:

a) 9
b) 10
c) 8
d) Infinite
Answer: a) 9

49. If we use two stacks to implement a queue, the dequeue operation’s worst-case complexity is:
a) O(1)
b) O(n)
c) O(log n)
d) O(n²)
Answer: b) O(n)

50. Which data structure is most suitable for printer job scheduling?
a) Stack
b) Queue
c) Deque
d) Priority Queue
Answer: b) Queue

TREE – Full Theory for SLST

1. Introduction to Trees

• Definition:
A tree is a nonlinear hierarchical data structure consisting of nodes connected by edges.

• Structure:

o Node → Basic unit (stores data + pointers to child nodes).

o Root → Topmost node (only one root).

o Parent → Node that has branches to child nodes.

o Child → Node directly connected to a parent.

o Leaf (Terminal Node) → Node with no children.

o Edge → Connection between two nodes.

o Height → Length of the longest path from root to a leaf.

o Depth → Distance of a node from the root.

2. Properties of a Tree

1. A tree with n nodes has exactly n-1 edges.

2. Height of a tree with one node is 0.

3. Maximum number of nodes at level l is 2^l.

4. Maximum nodes in a tree of height h is 2^(h+1) - 1.

3. Binary Trees

1. Full Binary Tree

Definition:
A binary tree in which every node has either 0 or 2 children. No node can have only one child.
Properties:

1. If there are n internal (non-leaf) nodes, there will be exactly n + 1 leaf nodes.

2. The total number of nodes in a full binary tree = 2n + 1, where n is the number of internal nodes.

3. Minimum height for n nodes: ⌈log₂(n+1)⌉ - 1

4. Every level has nodes in pairs except the last.

Example:

10

/ \

20 30

/\ /\

40 50 60 70

Use Cases:

• Expression trees (where every operator has two operands)

• Decision trees with fixed branching

2. Complete Binary Tree

Definition:
A binary tree in which all levels are completely filled, except possibly the last, and the last level is filled from left to right without gaps.

Properties:

1. Number of nodes n lies between 2^(h) and 2^(h+1) - 1 where h is the height.

2. Can be efficiently stored in an array without wasting space.

3. In an array representation:

o Left child index = 2i + 1

o Right child index = 2i + 2

o Parent index = (i - 1) / 2

Example:

/\

2 3

/\ /

4 56

Use Cases:

• Heap structures (min heap, max heap)

• Priority queues

3. Perfect Binary Tree

Definition:
A binary tree in which all internal nodes have exactly 2 children and all leaves are at the same level.

Properties:
 1. A perfect binary tree with height h has exactly 2^(h+1) - 1 nodes.

2. Number of leaf nodes = 2^h (where h is the height starting at 0).

3. Total nodes = Leaf nodes + Internal nodes.

Example:

/\

2 3

/\/\

4 56 7

Use Cases:

• Networking (balanced routing)

• Full tournament bracket trees

4. Degenerate (Skewed) Binary Tree

Definition:
A binary tree where every parent node has only one child, making it essentially behave like a linked list.

Types:

• Left-skewed – All nodes have only left children.

• Right-skewed – All nodes have only right children.

Properties:

1. Height of a degenerate tree with n nodes is n - 1 (worst case).

2. Searching in such a tree is O(n).

Example (Right-Skewed):

Use Cases:

• Rarely useful in practice (usually a sign of unbalanced insertions in BST).

• Appears in sorted data without balancing.

5. Balanced Binary Tree

Definition:
A binary tree where the height difference between left and right subtrees of every node is at most 1.

Properties:

1. Ensures O(log n) search, insertion, and deletion.

 2. Examples: AVL Tree, Red-Black Tree.

3. Height of a balanced binary tree with n nodes is O(log n).

Example:

10

/ \

5 20

/\ /\

3 7 15 25

Use Cases:

• Databases (balanced indexing)

• Filesystems (directory trees)

Comparison Table

Type Children per Node Last Level Filling Height Efficiency Example Usage

Full 0 or 2 only Not required Medium Expression Trees

Complete 0, 1, or 2 Filled left to right High Heaps, Priority Queue

Perfect Exactly 2 Completely filled Highest Balanced networks

Degenerate/Skewed Only 1 child N/A Worst Rare, unbalanced BST

Balanced ≤1 height diff N/A High AVL, Red-Black Tree

5. Binary Tree Traversals

Traversal = Visiting each node exactly once.

1. Preorder (Root → Left → Right)

2. Inorder (Left → Root → Right) – Used for BST to get sorted order.

3. Postorder (Left → Right → Root)

4. Level Order (BFS) – Visit level by level.

6. Binary Search Tree (BST)

• A binary tree with a property:

o Left child < Root < Right child

• Supports fast search, insert, delete in O(log n) (average case).

7. Applications of Trees

• File system structure

• Expression evaluation (Expression Trees)

• Databases (B-trees, B+ trees)

• Huffman encoding (data compression)

• Network routing
 • AI decision-making

8. Complexity of Binary Tree Operations

Operation Average Case Worst Case (Skewed)

Search O(log n) O(n)

Insert O(log n) O(n)

Delete O(log n) O(n)

Traversal O(n) O(n)

4. Binary Search Tree (BST)

• Definition: A binary tree where:

o Left child’s value < Parent’s value.

o Right child’s value > Parent’s value.

• Operations: Search, Insert, Delete — all in O(h) time.

• Applications: Fast searching, range queries.

5. Tree Traversals

Traversal = Visiting all nodes in a specific order.

Depth-First Search (DFS):

1. Inorder (L, Root, R) → Sorted order for BST.

2. Preorder (Root, L, R) → Used for copying trees.

3. Postorder (L, R, Root) → Used for deleting trees.

Breadth-First Search (BFS):

• Level Order → Visit level by level.

6. Special Trees

• AVL Tree → Self-balancing BST (Height diff ≤ 1).

• Red-Black Tree → Balanced BST with color properties.

• Heap → Complete binary tree (Min-Heap, Max-Heap).

• B-Tree / B+ Tree → Used in databases and file systems.

• Trie → Prefix tree for string searching.

7. Time Complexity of Tree Operations

Operation BST (Avg) BST (Worst in skewed) Balanced BST

Search O(log n) O(n) O(log n)

Insert O(log n) O(n) O(log n)

Operation BST (Avg) BST (Worst in skewed) Balanced BST

Delete O(log n) O(n) O(log n)

8. Applications of Trees

• Expression parsing (infix, prefix, postfix).

• Hierarchical file system representation.

• Database indexing (B-Tree, B+ Tree).

• Huffman coding (data compression).

• Network routing algorithms.

A. BASIC LEVEL (1–25)

1. A tree with n nodes has how many edges?

a) n
b) n+1
c) n-1
d) 2n
Answer: c

2. In a binary tree, each node can have at most:

a) 1 child
b) 2 children
c) 3 children
d) 4 children
Answer: b

3. The topmost node in a tree is called:

a) Parent node
b) Root node
c) Leaf node
d) Head node
Answer: b

4. In a binary tree, the maximum number of nodes at level l is:

a) 2l
b) l²
c) 2^l
d) 2^(l-1)
Answer: c

5. The height of a single-node tree is:

a) -1
b) 0
c) 1
d) Undefined
Answer: b

6. A node with no children is called:

a) Root node
b) Leaf node
c) Internal node
d) Null node
Answer: b

7. In a perfect binary tree of height h, number of nodes =

a) 2^h - 1
b) 2^(h+1) - 1
c) h²
d) 2h
Answer: b
8. The property “left < root < right” is satisfied by:
a) Heap
b) Binary Search Tree
c) Complete Binary Tree
d) AVL Tree only
Answer: b

9. A complete binary tree is:

a) All levels completely filled except possibly the last, filled from left to right
b) Every node has 2 children
c) All leaves at same level
d) Skewed tree
Answer: a

10. Which traversal of BST gives sorted order?

a) Preorder
b) Postorder
c) Inorder
d) Level order
Answer: c

11. In a skewed binary tree with n nodes, height is:

a) log₂ n
b) n-1
c) n/2
d) √n
Answer: b

12. The number of edges in an empty tree is:

a) 0
b) -1
c) Undefined
d) 1
Answer: a

13. Which data structure is used in BFS traversal?

a) Stack
b) Queue
c) Linked list
d) Priority queue
Answer: b

14. Which data structure is used in DFS traversal?

a) Queue
b) Stack
c) Heap
d) Array
Answer: b

15. The depth of the root node is always:

a) 1
b) 0
c) -1
d) Depends on tree
Answer: b

16. Which of the following is NOT a binary tree type?

a) Complete
b) Full
c) Perfect
d) Circular
Answer: d

17. Which of the following is NOT a tree application?

a) Compiler syntax analysis
b) Hierarchical database
c) File system
d) Stack implementation
Answer: d

18. In a BST, searching takes O(log n) in:

a) Balanced tree
b) Skewed tree
c) Empty tree
d) None
Answer: a

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

a) log₂ n
b) n/2
c) n
d) √n
Answer: a

20. Which tree structure is used in heaps?

a) Complete binary tree
b) Full binary tree
c) Perfect binary tree
d) Skewed binary tree
Answer: a

21. The leaf nodes of a complete binary tree appear in which order?
a) Random
b) Left to right
c) Right to left
d) None
Answer: b

22. Which special tree is used in dictionaries?

a) Heap
b) Trie
c) AVL Tree
d) Red-Black Tree
Answer: b

23. Which tree structure is used in Huffman coding?

a) Full binary tree
b) Complete binary tree
c) Prefix tree
d) Binary Search Tree
Answer: a

24. In a perfect binary tree, all leaf nodes are:

a) At same level
b) Different levels
c) Random
d) None
Answer: a

25. Which traversal visits all nodes level by level?

a) Inorder
b) Postorder
c) Level order
d) Preorder
Answer: c

B. CONCEPTUAL LEVEL (26–50)

(Questions test understanding of properties and structures)

26. In a binary tree with n leaf nodes, the number of nodes of degree 2 is:
a) n-1
b) n
c) n+1
d) n/2
Answer: a

27. If a binary tree has height h, maximum nodes possible =

a) 2^(h+1) - 1
b) 2^h - 1
c) h²
d) log₂ h
Answer: a
28. For a complete binary tree, height is:
a) O(n)
b) O(log n)
c) O(n log n)
d) O(1)
Answer: b

29. Inorder traversal of BST gives elements in:

a) Ascending order
b) Descending order
c) Random order
d) Depends on insertion
Answer: a

30. Which is faster for search — Balanced BST or Hash Table?

a) Balanced BST
b) Hash Table
c) Both same
d) Depends on keys
Answer: b

31. A degenerate tree behaves like:

a) Queue
b) Stack
c) Linked list
d) Array
Answer: c

32. Which tree type minimizes height?

a) Skewed
b) Balanced
c) Degenerate
d) None
Answer: b

33. Which traversal is used for expression tree evaluation?

a) Inorder
b) Postorder
c) Preorder
d) Level order
Answer: b

34. In a binary tree, number of NULL links =

a) n
b) n+1
c) n-1
d) 2n
Answer: d

35. If a binary tree has 15 nodes, minimum height is:

a) 3
b) 4
c) 5
d) 6
Answer: b

36. Which property is violated in an AVL tree after insertion?

a) Height balance property
b) BST property
c) Heap property
d) Degree property
Answer: a

37. Which rotation is used to fix AVL imbalance in Left-Right case?

a) Single left
b) Single right
c) Left-Right
d) Right-Left
Answer: c

38. Which tree is used for external memory indexing?

a) B-Tree
b) Trie
c) AVL Tree
d) Heap
Answer: a

39. Red-Black Tree is:

a) Strictly balanced
b) Height balanced with coloring rules
c) Heap
d) Prefix tree
Answer: b

40. Which traversal of tree is recursive in nature?

a) DFS
b) BFS
c) Level Order
d) All
Answer: a

41. Which tree has all leaves at depth log₂ n?

a) Perfect binary tree
b) Complete binary tree
c) Skewed tree
d) AVL tree
Answer: a

42. In a max-heap, the largest element is at:

a) Any leaf
b) Root
c) Last node
d) None
Answer: b

43. Which operation is O(log n) in AVL tree?

a) Search
b) Insert
c) Delete
d) All of these
Answer: d

44. The parent of node at index i in heap array is at:

a) i/2
b) (i-1)/2
c) 2i
d) 2i+1
Answer: b

45. Number of binary trees with n nodes is given by:

a) n!
b) Catalan number
c) Fibonacci number
d) None
Answer: b

46. A prefix tree is also called:

a) Heap
b) Trie
c) AVL
d) Red-Black
Answer: b

47. In a min-heap, which child is smaller?

a) Left
b) Right
c) Either
d) Both equal
Answer: c

48. Height-balanced tree ensures:

a) Short height for fast operations
b) Only search improvement
c) Only insert improvement
d) Only delete improvement
Answer: a
49. Which tree can have degree > 2?
a) Binary tree
b) General tree
c) AVL tree
d) Heap
Answer: b

50. The degree of a tree is:

a) Number of edges
b) Max children of any node
c) Height of tree
d) Total nodes
Answer: b

If you want, I can continue with Moderate (51–75) and Tricky (76–100) so you get the full 100 MCQs in one place.
Do you want me to proceed with the remaining 50 questions?

You said:

Moderate (51–75) and Tricky (76–100)

ChatGPT said:

Alright
Here’s the continuation of the Tree MCQs set:

Moderate MCQs (51–75)

51. Which traversal is used in a Binary Search Tree to retrieve data in sorted order?
a) Preorder
b) Postorder
c) Inorder
d) Level order
Answer: c) Inorder

52. In a complete binary tree, if there are n nodes, what is the maximum height?
a) log₂(n)
b) n
c) n/2
d) n – 1
Answer: a) log₂(n)

53. Which property is true for a perfect binary tree?

a) All leaves are at different levels
b) Each non-leaf has exactly 2 children
c) It has only one leaf
d) Height is greater than log₂(n)
Answer: b) Each non-leaf has exactly 2 children

54. The height of a binary tree with a single node is:

a) 0
b) 1
c) 2
d) Undefined
Answer: a) 0

55. Which of the following traversal sequences can uniquely identify a binary tree?
a) Inorder + Preorder
b) Inorder + Postorder
c) Preorder + Postorder
d) Both a and b
Answer: d) Both a and b

56. In an AVL tree, what is the balance factor range for all nodes?
a) 0
b) -1 to 1
c) 1 to 2
d) -2 to 2
Answer: b) -1 to 1
57. Which tree structure is ideal for priority queue implementation?
a) Binary Search Tree
b) AVL Tree
c) Heap
d) B-Tree
Answer: c) Heap

58. A binary tree can be uniquely constructed from:

a) Preorder traversal only
b) Postorder traversal only
c) Inorder + any one of Preorder/Postorder
d) Level order only
Answer: c) Inorder + any one of Preorder/Postorder

59. Which traversal visits nodes level by level?

a) Preorder
b) Level order
c) Postorder
d) Reverse inorder
Answer: b) Level order

60. The minimum number of nodes in an AVL tree of height h is given by:
a) h
b) h + 1
c) Fibonacci(h+2) - 1
d) 2ʰ - 1
Answer: c) Fibonacci(h+2) - 1

61. In a binary tree, the number of null pointers is always:

a) n + 1
b) n - 1
c) n
d) 2n
Answer: a) n + 1

62. Which of the following is not a self-balancing BST?

a) AVL tree
b) Red-Black tree
c) Splay tree
d) Complete binary tree
Answer: d) Complete binary tree

63. In a binary search tree, the complexity for searching a node in the worst case is:
a) O(1)
b) O(log n)
c) O(n)
d) O(n log n)
Answer: c) O(n)

64. Which statement about degenerate (skewed) trees is correct?

a) They are always balanced
b) Their height equals number of nodes - 1
c) They store duplicate keys only
d) They require a heap structure
Answer: b) Their height equals number of nodes - 1

65. Which traversal is used in depth-first search (DFS) of trees?

a) Inorder only
b) Preorder, Postorder, or Inorder
c) Level order only
d) Reverse level order
Answer: b) Preorder, Postorder, or Inorder

66. Which data structure is used to implement recursion in tree traversal?

a) Queue
b) Stack
c) Heap
d) Linked list
Answer: b) Stack

67. In a full binary tree with 15 nodes, how many leaf nodes exist?
a) 7
b) 8
 c) 9
d) 15
Answer: b) 8

68. If a binary tree has height h, the maximum possible number of nodes is:
a) 2ʰ - 1
b) 2^(h+1) - 1
c) h²
d) 2h
Answer: b) 2^(h+1) - 1

69. Which property is specific to a binary search tree (BST)?

a) Left subtree nodes are smaller than root
b) Right subtree nodes are smaller than root
c) No duplicate values allowed
d) Tree is always complete
Answer: a) Left subtree nodes are smaller than root

70. In a heap, which node property holds true?

a) Parent is smaller than child (Min-Heap)
b) Parent is greater than child (Max-Heap)
c) Both a and b depending on heap type
d) None of the above
Answer: c) Both a and b depending on heap type

71. In a complete binary tree, the array index of the left child of node i is:
a) i + 1
b) 2i
c) 2i + 1
d) i - 1
Answer: b) 2i

72. In a BST, deleting a node with two children involves:

a) Replacing with in-order successor/predecessor
b) Removing left child
c) Removing right child
d) Deleting both subtrees
Answer: a) Replacing with in-order successor/predecessor

73. Which type of tree has all levels filled except possibly the last, filled from left to right?
a) Full binary tree
b) Complete binary tree
c) Perfect binary tree
d) AVL tree
Answer: b) Complete binary tree

74. Which traversal of a BST produces descending order output?

a) Inorder
b) Reverse inorder
c) Preorder
d) Level order
Answer: b) Reverse inorder

75. The minimum height of a binary tree with n nodes is:

a) log₂(n+1) - 1
b) log₂n
c) n
d) √n
Answer: a) log₂(n+1) - 1

Tricky MCQs (76–100)

76. If a binary tree has n leaf nodes, how many nodes have degree 2 in a full binary tree?
a) n - 1
b) n
c) 2n
d) n + 1
Answer: a) n - 1

77. Which statement about red-black trees is false?

a) Root is always black
 b) No two consecutive red nodes exist
c) All paths have the same number of red nodes
d) Every leaf is black
Answer: c) All paths have the same number of red nodes

78. Which type of binary tree ensures minimum height for given n nodes?
a) Full binary tree
b) Balanced binary tree
c) Degenerate tree
d) Heap
Answer: b) Balanced binary tree

79. If a complete binary tree is represented in an array, index of right child of node i is:
a) i+1
b) 2i+1
c) 2i+2
d) i-1
Answer: c) 2i+2

80. Which traversal is best suited to create a copy of the tree?

a) Inorder
b) Preorder
c) Postorder
d) Level order
Answer: b) Preorder

81. In a BST, if all keys are inserted in increasing order, the height becomes:
a) log₂n
b) n-1
c) n/2
d) √n
Answer: b) n-1

82. Which is true for a min-heap?

a) Parent is always smaller than children
b) Root is the smallest element
c) Level order traversal gives sorted order
d) Both a and b
Answer: d) Both a and b

83. The maximum number of leaf nodes in a binary tree of height h is:
a) h
b) 2ʰ
c) 2^(h+1)
d) h²
Answer: b) 2ʰ

84. A degenerate tree with n nodes has a height of:

a) n-1
b) log₂n
c) n/2
d) √n
Answer: a) n-1

85. Which of the following trees is used in database indexing?

a) Binary search tree
b) AVL tree
c) B-tree
d) Heap
Answer: c) B-tree

86. Which traversal visits root last?

a) Preorder
b) Inorder
c) Postorder
d) Level order
Answer: c) Postorder

87. For a complete binary tree, if root index = 0, left child of node i is at:
a) 2i+1
b) 2i
c) i+1
 d) i-1
Answer: a) 2i+1

88. In an AVL tree, insertion may require:

a) No rotations
b) Single rotation
c) Double rotation
d) All of the above
Answer: d) All of the above

89. Which is the worst case time complexity for deleting a node in a BST?
a) O(1)
b) O(log n)
c) O(n)
d) O(n log n)
Answer: c) O(n)

90. Which property is true for complete binary trees but not necessarily for full binary trees?
a) All leaves at same level
b) All levels filled except last
c) Each node has 0 or 2 children
d) Tree height = log₂n
Answer: b) All levels filled except last

91. Which tree is used in Huffman coding?

a) Binary search tree
b) Full binary tree
c) Min-heap based binary tree
d) Red-black tree
Answer: c) Min-heap based binary tree

92. Which order traversal is suitable for expression tree evaluation?

a) Preorder
b) Postorder
c) Inorder
d) Level order
Answer: b) Postorder

93. Which is not a property of binary search tree?

a) Inorder traversal yields sorted keys
b) Left child key < root key
c) Right child key > root key
d) Duplicate keys allowed without restriction
Answer: d) Duplicate keys allowed without restriction

94. If a binary tree has L leaves, then total number of nodes N in a full binary tree is:
a) 2L - 1
b) L²
c) L log L
d) L + 1
Answer: a) 2L - 1

95. In a BST, searching for a non-existent key requires:

a) O(1) time
b) O(log n) average, O(n) worst
c) O(n log n)
d) O(√n)
Answer: b) O(log n) average, O(n) worst

96. In a complete binary tree, the parent of node i is:

a) floor(i/2)
b) floor((i-1)/2)
c) i-1
d) 2i
Answer: b) floor((i-1)/2)

97. Which tree structure is most efficient for implementing a priority queue?
a) Red-black tree
b) Min-heap
c) AVL tree
d) B-tree
Answer: b) Min-heap
 98. The maximum number of internal nodes in a binary tree with n nodes is:
a) n
b) n-1
c) n/2
d) log₂n
Answer: c) n/2

99. The number of edges in a tree with n nodes is:

a) n
b) n-1
c) n+1
d) log₂n
Answer: b) n-1

100. In a perfect binary tree of height h, number of leaf nodes =

a) 2ʰ
b) 2^(h+1)
c) h²
d) h+1
Answer: a) 2ʰ

Graph Theory – Complete Notes

1. Definition of a Graph

A graph is a collection of:

• Vertices (Nodes) – Represent entities.

• Edges (Links) – Represent connections between vertices.

Formally, a graph G is defined as:

G=(V,E)G = (V, E)G=(V,E)

Where:

• V = set of vertices

• E = set of edges

2. Types of Graphs

a) Based on Edge Direction

• Undirected Graph – Edges have no direction.

• Directed Graph (Digraph) – Edges have a direction from one vertex to another.

b) Based on Weights

• Weighted Graph – Edges have weights/costs.

• Unweighted Graph – All edges have equal cost.

c) Based on Connectivity

• Connected Graph – There is a path between every pair of vertices.

• Disconnected Graph – Some vertices are not reachable from others.

d) Special Graph Types

• Complete Graph (Kn) – Every vertex is connected to every other vertex.

• Bipartite Graph – Vertices can be divided into two disjoint sets such that no two vertices within the same set are connected.

• Tree – A connected acyclic graph.

• Subgraph – A part of a graph formed from a subset of vertices and edges.

3. Graph Representation

a) Adjacency Matrix

• 2D matrix where cell [i][j] is 1 (or weight) if there is an edge from vertex i to j.

• Space complexity: O(V²)

b) Adjacency List

• An array/list of linked lists.

• Each vertex stores a list of connected vertices.

• Space complexity: O(V + E)

4. Graph Traversals

a) Breadth-First Search (BFS)

• Level-order traversal using a queue.

• Time complexity: O(V + E)

b) Depth-First Search (DFS)

• Traverses deep before backtracking using recursion or a stack.

• Time complexity: O(V + E)

5. Graph Properties

• Degree of a vertex – Number of edges incident on it.

o In-degree – Number of incoming edges (in directed graph).

o Out-degree – Number of outgoing edges.

• Path – Sequence of vertices connected by edges.

• Cycle – Path that starts and ends at the same vertex.

• Acyclic Graph – No cycles present.

6. Graph Algorithms

• Dijkstra’s Algorithm – Shortest path from a source vertex (non-negative weights).

• Bellman-Ford Algorithm – Handles negative weights.

• Floyd-Warshall Algorithm – All-pairs shortest path.

• Kruskal’s Algorithm – Minimum Spanning Tree (MST) using edge sorting.

• Prim’s Algorithm – MST starting from a vertex.

• Topological Sorting – Ordering vertices in a directed acyclic graph (DAG).

7. Complexity Analysis
Representation Space Complexity BFS/DFS Complexity

Adjacency Matrix O(V²) O(V²)

Adjacency List O(V+E) O(V+E)

100 MCQs on Graph Theory

I’ll divide them as:

• Easy (1–30) – Basic definitions & types

• Moderate (31–70) – Properties & algorithms

• Tricky (71–100) – Conceptual & application-based

Easy Level (1–30)

1. In a graph, a vertex is also called:

a) Node
b) Edge
c) Path
d) Weight
Ans: a

2. A graph with no edges is called:

a) Null Graph
b) Complete Graph
c) Bipartite Graph
d) Weighted Graph
Ans: a

3. In an undirected graph, the sum of degrees of all vertices is:

a) E
b) 2E
c) V
d) V²
Ans: b

Graph Theory – MCQs (4–100)

4. In a simple undirected graph with nnn vertices, the maximum number of edges is:
a) n(n+1)/2n(n+1)/2n(n+1)/2
b) n(n−1)/2n(n-1)/2n(n−1)/2
c) n2n^2n2
d) (n−1)2(n-1)^2(n−1)2
Answer: b

5. The degree sum formula in an undirected graph states:

a) Sum of degrees = 2 × number of edges
b) Sum of degrees = number of vertices × number of edges
c) Sum of degrees = number of vertices + number of edges
d) None of these
Answer: a

6. A complete graph with nnn vertices is denoted by:

a) CnC_nCn
b) PnP_nPn
c) KnK_nKn
d) GnG_nGn
Answer: c

7. A tree is a connected graph with:

a) Cycles
b) n−1n-1n−1 edges
c) nnn edges
d) No vertices
Answer: b
8. Which of the following is NOT a type of graph representation?
a) Adjacency list
b) Adjacency matrix
c) Incidence matrix
d) Path matrix
Answer: d

9. The time complexity of DFS using adjacency list is:

a) O(V2)O(V^2)O(V2)
b) O(V+E)O(V+E)O(V+E)
c) O(VE)O(VE)O(VE)
d) O(E2)O(E^2)O(E2)
Answer: b

10. In BFS, the data structure used is:

a) Stack
b) Queue
c) Array
d) Linked list only
Answer: b

11. The number of edges in a complete bipartite graph Km,nK_{m,n}Km,n is:

a) m+nm+nm+n
b) m×nm \times nm×n
c) m+n−1m+n-1m+n−1
d) m×(n−1)m \times (n-1)m×(n−1)
Answer: b

12. Dijkstra’s algorithm is used for:

a) Minimum spanning tree
b) Shortest path from a single source
c) Detecting cycle in graph
d) Topological sorting
Answer: b

13. Kruskal’s algorithm is used for:

a) Minimum spanning tree
b) Single-source shortest path
c) Maximum flow
d) Strongly connected components
Answer: a

14. Prim’s algorithm starts from:

a) Any random vertex
b) The vertex with the smallest degree
c) The vertex with smallest edge weight
d) The vertex with the highest degree
Answer: a

15. In a directed graph, the sum of in-degrees equals:

a) The sum of out-degrees
b) Twice the number of edges
c) Number of vertices
d) None of these
Answer: a

16. Which traversal is used in topological sorting?

a) BFS
b) DFS
c) Inorder
d) Level order
Answer: b

17. Which algorithm can detect negative weight cycles?

a) Dijkstra’s
b) Bellman-Ford
c) Prim’s
d) Kruskal’s
Answer: b

18. Floyd–Warshall algorithm complexity is:

a) O(V2)O(V^2)O(V2)
b) O(V3)O(V^3)O(V3)
c) O(VE)O(VE)O(VE)
d) O(E2)O(E^2)O(E2)
Answer: b

19. Which of the following is true for a planar graph?

a) It can be drawn without edge crossing
b) It has no cycles
c) It has no loops
d) It is complete
Answer: a

20. Euler’s formula for planar graph is:

a) V−E+F=2V - E + F = 2V−E+F=2
b) V+E−F=2V + E - F = 2V+E−F=2
c) E−V+F=0E - V + F = 0E−V+F=0
d) V+F−E=1V + F - E = 1V+F−E=1
Answer: a

21. A Hamiltonian cycle visits:

a) All vertices exactly once and returns to start
b) All edges exactly once
c) Only leaf nodes
d) Only even degree vertices
Answer: a

22. An Eulerian path visits:

a) All edges exactly once
b) All vertices exactly once
c) All cycles exactly once
d) None of these
Answer: a

23. The graph coloring problem involves assigning:

a) Numbers to vertices
b) Colors to vertices such that adjacent vertices have different colors
c) Colors to edges only
d) None of these
Answer: b

24. Chromatic number is:

a) Minimum colors required to color vertices of a graph
b) Maximum colors needed
c) Number of edges
d) Degree of graph
Answer: a

25. Which of the following graphs has a chromatic number 2?

a) Bipartite graph
b) Complete graph with odd vertices
c) Star graph
d) Tree with more than one vertex
Answer: a

26. A dense graph is one in which:

a) EEE is close to V2V^2V2
b) EEE is much less than VVV
c) EEE equals VVV
d) EEE equals V−1V-1V−1
Answer: a

27. Which algorithm is used for finding bridges in a graph?

a) Tarjan’s algorithm
b) Bellman-Ford
c) Kruskal’s
d) Warshall’s
Answer: a

28. In adjacency matrix, space complexity is:

a) O(V2)O(V^2)O(V2)
b) O(E)O(E)O(E)
c) O(V+E)O(V+E)O(V+E)
d) O(E2)O(E^2)O(E2)
Answer: a
29. Which is more space efficient for sparse graphs?
a) Adjacency matrix
b) Adjacency list
c) Incidence matrix
d) None
Answer: b

30. A graph without cycles is called:

a) Tree
b) DAG
c) Bipartite
d) Null graph
Answer: b

Moderate Level (Q31–Q60)

31. In a connected undirected graph with VVV vertices and EEE edges, what is the minimum value of EEE for the graph to remain
connected?
a) VVV
b) V−1V-1V−1
c) V+1V+1V+1
d) 2V2V2V
Answer: b) V−1V-1V−1

32. Which traversal uses a queue?

a) Depth First Search
b) Breadth First Search
c) Prim’s Algorithm
d) Kruskal’s Algorithm
Answer: b) Breadth First Search

33. The adjacency list representation of a graph is more efficient than the adjacency matrix for:
a) Dense graphs
b) Sparse graphs
c) Complete graphs
d) Graphs with self-loops only
Answer: b) Sparse graphs

34. In a directed acyclic graph (DAG), the maximum number of edges possible is:
a) V(V−1)V(V-1)V(V−1)
b) V(V−1)/2V(V-1)/2V(V−1)/2
c) (V−1)!(V-1)!(V−1)!
d) None of these
Answer: b) V(V−1)/2V(V-1)/2V(V−1)/2

35. Which algorithm can be used to detect a cycle in a directed graph?

a) Dijkstra’s algorithm
b) Depth First Search
c) Kruskal’s algorithm
d) Prim’s algorithm
Answer: b) Depth First Search

36. In an undirected connected graph, removing a bridge:

a) Reduces the number of edges but keeps graph connected
b) Disconnects the graph
c) Always reduces the degree of all vertices
d) Has no effect
Answer: b) Disconnects the graph

37. The chromatic number of a bipartite graph is always:

a) 1
b) 2
c) V/2V/2V/2
d) Depends on edges
Answer: b) 2

38. An Euler circuit exists in an undirected graph if and only if:

a) All vertices have odd degree
b) All vertices have even degree
c) Graph is complete
d) Graph is tree
Answer: b) All vertices have even degree
39. Which of the following algorithms can be used to find the shortest path in a weighted graph with negative edges but no
negative cycles?
a) Dijkstra’s
b) Bellman-Ford
c) Floyd-Warshall
d) Both b and c
Answer: d) Both b and c

40. Which data structure is most suitable for DFS?

a) Queue
b) Stack
c) Priority Queue
d) Hash Table
Answer: b) Stack

41. The time complexity of BFS using adjacency list is:

a) O(V+E)
b) O(V²)
c) O(E log V)
d) O(V log V)
Answer: a) O(V+E)

42. The incidence matrix of a graph shows:

a) Vertex-vertex relationships
b) Edge-vertex relationships
c) Edge-edge relationships
d) None of the above
Answer: b) Edge-vertex relationships

43. Which of the following is NOT a spanning tree property?

a) It contains all vertices of the graph
b) It contains no cycles
c) It contains exactly V edges
d) It has exactly V-1 edges
Answer: c) It contains exactly V edges

44. In Prim’s algorithm, the priority queue is used to:

a) Keep track of visited vertices
b) Select the next vertex with minimum weight edge
c) Store DFS order
d) Track degree of vertices
Answer: b) Select the next vertex with minimum weight edge

45. Which type of graph has E=V(V−1)/2E = V(V-1)/2E=V(V−1)/2 edges?

a) Sparse graph
b) Complete graph
c) Bipartite graph
d) Weighted graph
Answer: b) Complete graph

46. The adjacency matrix of an undirected graph is always:

a) Upper triangular
b) Lower triangular
c) Symmetric
d) Skew-symmetric
Answer: c) Symmetric

47. What is the chromatic number of a cycle graph with odd number of vertices?
a) 2
b) 3
c) Depends on V
d) 1
Answer: b) 3

48. The diameter of a graph is:

a) Maximum distance between any two vertices
b) Minimum distance between any two vertices
c) Average distance between vertices
d) Number of connected components
Answer: a) Maximum distance between any two vertices

49. Which of the following is true for a tree with VVV vertices?
a) E = V-2
 b) E = V-1
c) E = 2V
d) E = V²
Answer: b) E = V-1

50. Which algorithm is greedy?

a) Kruskal’s
b) Prim’s
c) Dijkstra’s
d) All of the above
Answer: d) All of the above

Moderate–Tricky (Q51–80)

51. A planar graph can be drawn on a plane without:

a) Loops
b) Parallel edges
c) Edge crossings
d) Isolated vertices
Answer: c) Edge crossings

52. Which graph traversal is used in topological sorting?

a) BFS
b) DFS
c) Dijkstra
d) Kruskal
Answer: b) DFS

53. The handshaking lemma states:

a) Sum of degrees = 2 × number of edges
b) Sum of degrees = number of edges
c) Sum of degrees = V × E
d) None of the above
Answer: a) Sum of degrees = 2 × number of edges

54. In a graph, a vertex of degree 1 is called:

a) Root
b) Leaf
c) Cut vertex
d) Isolated vertex
Answer: b) Leaf

55. Which algorithm can detect negative weight cycles?

a) Dijkstra
b) Bellman-Ford
c) Prim
d) Kruskal
Answer: b) Bellman-Ford

56. The girth of a graph is:

a) Length of shortest cycle
b) Length of longest cycle
c) Number of edges
d) Number of vertices
Answer: a) Length of shortest cycle

57. A Hamiltonian path visits:

a) Every vertex exactly once
b) Every edge exactly once
c) Every vertex and returns to start
d) Only leaf vertices
Answer: a) Every vertex exactly once

58. In BFS, each vertex is enqueued:

a) Once
b) Twice
c) As many times as its degree
d) None of the above
Answer: a) Once
59. An adjacency list for a graph with V vertices and E edges takes space:
a) O(V²)
b) O(V+E)
c) O(E log V)
d) O(VE)
Answer: b) O(V+E)

60. A disconnected graph can have a spanning tree.

a) True
b) False
Answer: b) False

61. In a connected weighted graph, which algorithm will produce the same result as Kruskal’s?
a) Dijkstra’s
b) Prim’s
c) DFS
d) Bellman-Ford
Answer: b) Prim’s

62. If a connected graph has 10 vertices and 15 edges, the number of cycles is:
a) 6
b) 5
c) 4
d) 7
Answer: a) 6

63. In a bipartite graph, the length of every cycle is:

a) Odd
b) Even
c) 0
d) Depends on edges
Answer: b) Even

64. Which algorithm uses union-find data structure?

a) Kruskal’s
b) Prim’s
c) BFS
d) DFS
Answer: a) Kruskal’s

65. In DFS, if we replace stack with queue, it becomes:

a) BFS
b) Topological sort
c) Dijkstra
d) Bellman-Ford
Answer: a) BFS

66. The complement of a complete graph is:

a) Null graph
b) Complete graph
c) Bipartite graph
d) Cyclic graph
Answer: a) Null graph

67. In a DAG, the number of topological orderings possible can be:

a) 1 only
b) More than 1
c) Infinite
d) 0
Answer: b) More than 1

68. Which of the following is NOT true for Dijkstra’s algorithm?

a) Works for negative weights
b) Uses priority queue
c) Finds shortest paths
d) Greedy approach
Answer: a) Works for negative weights

69. For a connected planar graph, Euler’s formula is:

a) V + E = F + 2
b) V - E + F = 2
c) V + E + F = 2
 d) V × E × F = 2
Answer: b) V - E + F = 2

70. A graph with no cycles is called:

a) Tree
b) Forest
c) Acyclic graph
d) All of the above
Answer: d) All of the above

Tricky (Q71–100)

71. Which property is common for all trees?

a) Unique path between any two vertices
b) Multiple paths between vertices
c) Contains cycles
d) Disconnected
Answer: a) Unique path between any two vertices

72. The cut property is used in:

a) Dijkstra’s
b) Bellman-Ford
c) Prim’s and Kruskal’s
d) DFS
Answer: c) Prim’s and Kruskal’s

73. If a graph has all vertices of degree ≥ 2, it must contain:

a) A cycle
b) No cycle
c) A Hamiltonian path
d) Be planar
Answer: a) A cycle

74. Which traversal can detect articulation points?

a) BFS
b) DFS
c) Prim’s
d) Kruskal’s
Answer: b) DFS

75. In adjacency matrix representation, space complexity is:

a) O(V²)
b) O(V+E)
c) O(E log V)
d) O(VE)
Answer: a) O(V²)

76. A dense graph has:

a) E close to V2V^2V2
b) E close to V
c) E much less than V
d) No edges
Answer: a) E close to V2V^2V2

77. The maximum number of edges in a simple directed graph with V vertices is:
a) V(V−1)V(V-1)V(V−1)
b) V(V+1)V(V+1)V(V+1)
c) V2V^2V2
d) V(V−1)/2V(V-1)/2V(V−1)/2
Answer: a) V(V−1)V(V-1)V(V−1)

78. Which of the following cannot have an Euler circuit?

a) A connected graph with exactly two vertices of odd degree
b) A connected graph with all vertices of even degree
c) A disconnected graph with all vertices even degree
d) Both a and c
Answer: d) Both a and c

79. The radius of a graph is:

a) Minimum eccentricity among vertices
b) Maximum eccentricity
 c) Diameter / 2
d) Always 1
Answer: a) Minimum eccentricity among vertices

80. A simple cycle of length 3 in a graph is called:

a) Triangle
b) Triplet
c) Tricycle
d) Complete subgraph
Answer: a) Triangle

81. Which algorithm finds all pairs shortest paths?

a) Bellman-Ford
b) Floyd-Warshall
c) Prim’s
d) Kruskal’s
Answer: b) Floyd-Warshall

82. If a graph has V=5V = 5V=5 and E=10E = 10E=10, it is:

a) Complete
b) Sparse
c) Forest
d) Planar
Answer: a) Complete

83. In BFS, the distance from source to any vertex is:

a) Number of edges in shortest path
b) Weight of shortest path
c) Always constant
d) None of the above
Answer: a) Number of edges in shortest path

84. Which is true for a forest with T trees and V vertices?

a) E = V - T
b) E = V - 1
c) E = T - V
d) E = T + V
Answer: a) E = V - T

85. The Petersen graph is:

a) Planar
b) Non-planar
c) Bipartite
d) Null
Answer: b) Non-planar

86. Which graph property is used in Kahn’s algorithm?

a) Indegree of vertices
b) Outdegree of vertices
c) BFS traversal
d) DFS traversal
Answer: a) Indegree of vertices

87. A graph is Eulerian if:

a) Connected and all vertices have even degree
b) Connected and has exactly two odd degree vertices
c) Complete
d) Planar
Answer: a) Connected and all vertices have even degree

88. Which of the following has time complexity O(VE)?

a) Bellman-Ford
b) Dijkstra (with adjacency list)
c) Prim’s (with adjacency list)
d) Floyd-Warshall
Answer: a) Bellman-Ford

89. The maximum number of edges in a simple undirected graph without loops is:
a) V(V−1)/2V(V-1)/2V(V−1)/2
b) V2V^2V2
c) V(V+1)/2V(V+1)/2V(V+1)/2
d) 2V2V2V
Answer: a) V(V−1)/2V(V-1)/2V(V−1)/2
90. Which traversal is used in bipartite graph checking?
a) BFS
b) DFS
c) Dijkstra
d) Kruskal
Answer: a) BFS

91. If a planar graph has 8 vertices and 12 edges, how many faces does it have?
a) 6
b) 8
c) 4
d) 10
Answer: a) 6

92. In DFS tree, a back edge indicates:

a) Cycle in the graph
b) Graph is disconnected
c) Graph is complete
d) No cycles
Answer: a) Cycle in the graph

93. In a connected undirected graph, removing an articulation point will:

a) Increase connected components
b) Reduce connected components
c) Have no effect
d) Create Euler path
Answer: a) Increase connected components

94. The clique of a graph is:

a) Complete subgraph
b) Path
c) Cycle
d) Tree
Answer: a) Complete subgraph

95. A graph is strongly connected if:

a) Each vertex is reachable from every other vertex (directed)
b) It is connected and undirected
c) It has no cycles
d) It is complete
Answer: a) Each vertex is reachable from every other vertex (directed)

96. In an undirected graph, sum of degrees is always:

a) Even
b) Odd
c) Prime
d) Multiple of 3
Answer: a) Even

97. Which is true for a tree’s adjacency matrix?

a) Always symmetric and sparse
b) Symmetric and dense
c) Not symmetric
d) Skew-symmetric
Answer: a) Always symmetric and sparse

98. Which of the following is a weighted complete graph?

a) Graph with edge weights and V(V−1)/2V(V-1)/2V(V−1)/2 edges
b) Graph with equal weights only
c) Graph with self-loops
d) Graph with 0 edges
Answer: a) Graph with edge weights and V(V−1)/2V(V-1)/2V(V−1)/2 edges

99. The center of a tree is:

a) Vertex with minimum eccentricity
b) Vertex with maximum degree
c) Root
d) Any leaf
Answer: a) Vertex with minimum eccentricity

100. Which algorithm is best for finding Minimum Spanning Tree in dense graphs?
a) Prim’s with adjacency matrix
b) Kruskal’s with adjacency list
 c) Bellman-Ford
d) Floyd-Warshall
Answer: a) Prim’s with adjacency matrix

Theory – Brief Study of Algorithm

1. Definition

An algorithm is a well-defined sequence of unambiguous steps designed to solve a specific problem or perform a computation.
It takes some input, processes it, and produces the desired output in a finite amount of time.

2. Characteristics of a Good Algorithm

1. Finiteness – Must terminate after a finite number of steps.

2. Definiteness – Each step must be clearly defined and unambiguous.

3. Input – Zero or more inputs provided externally.

4. Output – One or more outputs produced.

5. Effectiveness – Each step must be basic enough to be executed exactly.

6. Generality – Should solve a class of problems, not just one instance.

3. Steps in Algorithm Development

1. Understanding the Problem – Identify inputs, outputs, and constraints.

2. Designing the Algorithm – Choose a logical sequence of operations.

3. Representing the Algorithm – Use pseudocode or flowchart.

4. Analysis of the Algorithm – Evaluate efficiency (time and space).

5. Implementation – Convert into a programming language.

6. Testing and Debugging – Verify correctness.

4. Representation of Algorithms

• Pseudocode – A language-independent way of writing algorithms.

• Flowcharts – Diagrammatic representation using symbols.

• Structured English – Combining natural language with programming-like structure.

5. Types of Algorithms

1. Brute Force Algorithm – Try all possible solutions (e.g., linear search).

2. Divide and Conquer – Break into subproblems, solve recursively (e.g., merge sort).

3. Greedy Algorithm – Take the best choice at each step (e.g., Dijkstra's).

4. Dynamic Programming – Break problems into overlapping subproblems (e.g., Fibonacci using memoization).

5. Backtracking – Try all solutions, abandon when constraints fail (e.g., N-Queens problem).

6. Randomized Algorithms – Use random numbers to influence decisions.

7. Recursive Algorithms – Call itself until base case is reached.

8. Iterative Algorithms – Use loops instead of recursion.

6. Importance of Algorithm

• Provides a clear plan for solving problems.

• Helps in optimization for speed and memory.

• Forms the foundation for programming.

• Improves problem-solving skills.

7. Example Algorithm

Problem – Find the sum of the first n natural numbers.

Pseudocode:

Algorithm Sum_Natural(n)

Input: n

Output: sum

sum ← 0

for i ← 1 to n

sum ← sum + i

return sum

End Algorithm

50 MCQs – Brief Study of Algorithm

Basic (1–20)

1. Which of the following is NOT a characteristic of an algorithm?

a) Finiteness
b) Ambiguity
c) Definiteness
d) Output
Ans: b

2. Which representation of an algorithm uses diagrams?

a) Flowchart
b) Pseudocode
c) Code
d) Syntax Tree
Ans: a

3. The output of an algorithm must be:

a) Always numerical
b) Well-defined
c) Same as input
d) Infinite
Ans: b

4. A good algorithm should terminate:

a) Never
b) After infinite steps
c) After finite steps
d) After compilation
Ans: c

5. Which of these is NOT a step in algorithm development?

a) Problem understanding
b) Algorithm design
c) Code optimization
d) Cooking the result
Ans: d
6. Flowchart symbol for decision-making is:
a) Oval
b) Rectangle
c) Diamond
d) Parallelogram
Ans: c

7. Pseudocode is:
a) Language-specific
b) Language-independent
c) Executable directly
d) Binary code
Ans: b

8. Which type of algorithm solves subproblems independently?

a) Greedy
b) Divide and Conquer
c) Backtracking
d) Randomized
Ans: b

9. In which type of algorithm does each step choose the best option without reconsidering?
a) Greedy
b) Recursive
c) Backtracking
d) Brute Force
Ans: a

10. The process of finding an algorithm’s efficiency is called:

a) Compilation
b) Analysis
c) Debugging
d) Optimization
Ans: b

11. Which is NOT a type of algorithm?

a) Brute Force
b) Dynamic Programming
c) Sorting Algorithm
d) Greedy Algorithm
Ans: c

12. Recursive algorithms always require:

a) Loops
b) A base case
c) Random numbers
d) Decision tables
Ans: b

13. Which algorithmic strategy is used in QuickSort?

a) Brute Force
b) Divide and Conquer
c) Dynamic Programming
d) Greedy
Ans: b

14. Which of these is best for shortest path problems?

a) Greedy
b) Recursive
c) Brute Force
d) Randomized
Ans: a

15. Which of these is an example of a divide and conquer algorithm?

a) Bubble Sort
b) Merge Sort
c) Linear Search
d) Counting Sort
Ans: b

16. Which representation is best for debugging?

a) Flowchart
b) Pseudocode
 c) Binary
d) Hexadecimal
Ans: a

17. Which characteristic ensures an algorithm solves all instances of a problem?

a) Effectiveness
b) Definiteness
c) Generality
d) Finiteness
Ans: c

18. Which is the first step in algorithm design?

a) Testing
b) Implementation
c) Understanding the problem
d) Code writing
Ans: c

19. Which algorithm strategy uses overlapping subproblems?

a) Greedy
b) Dynamic Programming
c) Divide and Conquer
d) Backtracking
Ans: b

20. Which algorithm strategy abandons a path when it is not feasible?

a) Brute Force
b) Backtracking
c) Recursive
d) Iterative
Ans: b

21. Which of the following is NOT a characteristic of a good algorithm?

a) Unambiguity
b) Finiteness
c) Efficiency
d) Randomness
Answer: d) Randomness

22. The step-by-step procedure to solve a problem is called:

a) Flowchart
b) Algorithm
c) Pseudocode
d) Program
Answer: b) Algorithm

23. An algorithm must terminate after a:

a) Finite number of steps

b) Variable number of steps
c) Infinite number of steps
d) Conditional number of steps
Answer: a) Finite number of steps

24. Which algorithm design strategy breaks a problem into smaller subproblems?

a) Greedy method
b) Divide and conquer
c) Dynamic programming
d) Both b and c
Answer: d) Both b and c

25. Which of these is NOT a way to represent an algorithm?

a) Flowchart
b) Pseudocode
c) Decision tree
d) Syntax tree
Answer: d) Syntax tree
26. The set of rules defining how to solve a problem step-by-step is known as:

a) Flowchart
b) Syntax
c) Algorithm
d) Code
Answer: c) Algorithm

27. What is the first step in developing an algorithm?

a) Writing code
b) Understanding the problem
c) Debugging
d) Drawing a flowchart
Answer: b) Understanding the problem

28. Which type of algorithm tries all possible solutions and selects the best?

a) Greedy
b) Brute force
c) Divide and conquer
d) Randomized
Answer: b) Brute force

29. In algorithm design, the "greedy" approach means:

a) Trying every possibility

b) Making the best local choice at each step
c) Dividing the problem into halves
d) Using recursion
Answer: b) Making the best local choice at each step

30. Which of these is NOT a benefit of using algorithms?

a) Reusability
b) Easy debugging
c) Language dependency
d) Improved efficiency
Answer: c) Language dependency

31. A recursive algorithm must have:

a) Base case
b) Infinite calls
c) No return statement
d) Randomization
Answer: a) Base case

32. Which representation is most visual for an algorithm?

a) Flowchart
b) Pseudocode
c) Program code
d) Equation
Answer: a) Flowchart

33. What is the main difference between pseudocode and code?

a) Syntax rules
b) Logic
c) Variables
d) Execution
Answer: a) Syntax rules

34. Which algorithm type guarantees the optimal solution if it exists?

a) Greedy
b) Dynamic programming
c) Brute force
d) Randomized
Answer: b) Dynamic programming

35. Which of the following is an example of a divide-and-conquer algorithm?

a) Quick sort
b) Bubble sort
c) Linear search
d) BFS
Answer: a) Quick sort

36. Which algorithm type can adapt its behavior based on random choices?

a) Greedy
b) Brute force
c) Randomized
d) Recursive
Answer: c) Randomized

37. Which step comes after writing an algorithm?

a) Debugging
b) Testing
c) Implementation in code
d) Flowchart drawing
Answer: c) Implementation in code

38. In algorithms, what does “correctness” mean?

a) Program runs fast

b) Output matches the expected result for all inputs
c) Memory usage is low
d) It never crashes
Answer: b) Output matches the expected result for all inputs

39. An algorithm’s efficiency is measured in terms of:

a) CPU speed
b) Execution time and memory usage
c) Programming language
d) Input device
Answer: b) Execution time and memory usage

40. Which of these algorithms is based on recursion?

a) Merge sort
b) Bubble sort
c) Selection sort
d) Linear search
Answer: a) Merge sort

41. Which of these is NOT part of algorithm analysis?

a) Space complexity
b) Time complexity
c) Execution correctness
d) Variable naming style
Answer: d) Variable naming style

42. What is the purpose of dry running an algorithm?

a) Test its correctness without actual execution

b) Improve its efficiency
c) Translate to pseudocode
d) Write flowchart
Answer: a) Test its correctness without actual execution

43. Which algorithm type solves a problem by building up a solution using previously found results?

a) Dynamic programming
b) Greedy
c) Divide and conquer
d) Randomized
Answer: a) Dynamic programming

44. Which property ensures that an algorithm is clear and not open to multiple interpretations?

a) Finiteness
b) Unambiguity
c) Correctness
d) Efficiency
Answer: b) Unambiguity

45. Which design strategy is used by binary search?

a) Greedy
b) Divide and conquer
c) Dynamic programming
d) Brute force
Answer: b) Divide and conquer

46. Which of these is NOT a valid algorithmic strategy?

a) Randomized
b) Backtracking
c) Greedy
d) Guess and check without verification
Answer: d) Guess and check without verification

47. Which statement is true about pseudocode?

a) It must be written in English only

b) It is language-independent
c) It requires compiler
d) It is executed directly
Answer: b) It is language-independent

48. Which step is done before coding the algorithm?

a) Dry run and testing

b) Flowchart or pseudocode creation
c) Debugging
d) Compilation
Answer: b) Flowchart or pseudocode creation

49. Which type of algorithm works well for optimization problems like shortest path?

a) Greedy
b) Backtracking
c) Dynamic programming
d) All of the above
Answer: d) All of the above

50. Which of these algorithms is an example of the greedy approach?

a) Dijkstra’s algorithm
b) Merge sort
c) Binary search
d) Depth-first search
Answer: a) Dijkstra’s algorithm

Complexity of an Algorithm — Complete Theory

1. What is Algorithm Complexity?

Algorithm complexity is a measure of the resources an algorithm needs to run — usually time (execution speed) and space (memory
usage).

• Time Complexity → How much time (steps) it takes.

• Space Complexity → How much memory it requires.

2. Why Analyze Complexity?

• Predict performance before implementing.

• Compare algorithms without actual execution.

 • Identify bottlenecks and inefficiencies.

• Optimize for large-scale data.

3. Time Complexity

Time complexity measures how the execution time grows with the size of input n.
We use asymptotic analysis for this — it focuses on growth rate rather than exact time.

4. Cases in Time Complexity

• Best Case (Ω) → Minimum time taken (optimistic).

• Average Case (Θ) → Expected time taken (most realistic).

• Worst Case (O) → Maximum time taken (pessimistic).

5. Asymptotic Notations

Notation Meaning Use Case

Big-O (O) Upper bound Worst-case analysis

Big-Omega (Ω) Lower bound Best-case analysis

Big-Theta (Θ) Tight bound Average-case or exact growth

Example:

If an algorithm takes 3n² + 5n + 2 steps:

• O(n²) → Growth won’t exceed a constant multiple of n².

• Ω(n²) → It will take at least proportional to n².

• Θ(n²) → Growth is exactly proportional to n².

6. Common Time Complexities

Complexity Example

O(1) Constant Accessing array element by index

O(log n) Logarithmic Binary search

O(n) Linear Linear search

O(n log n) Merge sort, quicksort (average)

O(n²) Quadratic Bubble sort, selection sort

O(2ⁿ) Exponential Recursive Fibonacci

O(n!) Factorial Traveling Salesman (brute force)

7. Space Complexity

Measures total memory needed, including:

• Fixed part → Constants, program code, fixed variables.

 • Variable part → Dynamic memory allocations, data structures.

• Recursion space → Memory used by function calls in recursion.

Formula:

Space Complexity = Fixed Part + Variable Part + Recursion Space

8. Trade-off Between Time and Space

• Less space → More time (e.g., recomputing instead of storing results).

• More space → Less time (e.g., caching results in memory).

• Optimization often involves finding a balance.

9. Examples

Example 1: Linear Search

• Time complexity: O(n) (worst), Ω(1) (best if found at first index).

• Space complexity: O(1) (no extra memory).

Example 2: Binary Search

• Time complexity: O(log n).

• Space complexity: O(1) (iterative) or O(log n) (recursive due to call stack).

10. Summary Table

Algorithm Type Best Case Average Case Worst Case

Linear Search Ω(1) Θ(n) O(n)

Binary Search Ω(1) Θ(log n) O(log n)

Bubble Sort Ω(n) Θ(n²) O(n²)

Merge Sort Ω(n log n) Θ(n log n) O(n log n)

50 MCQs — Complexity of Algorithms

Section A — Basics of Complexity (1–10)

1. Which of the following measures the performance of an algorithm?

o a) Code size

o b) Complexity

o c) Compilation speed

o d) Machine type
Answer: b

2. Time complexity of an algorithm depends on:

o a) Size of the input

o b) Programming language

o c) Compiler used
 o d) Both b and c
Answer: a

3. Space complexity includes:

o a) Fixed part only

o b) Variable part only

o c) Both fixed and variable parts

o d) Execution time
Answer: c

4. Which complexity notation gives the upper bound?

o a) Θ

o b) O

o c) Ω

o d) None
Answer: b

5. What is the best case time complexity of Linear Search?

o a) O(n)

o b) Ω(1)

o c) Θ(n)

o d) O(log n)
Answer: b

6. Which of these is not an asymptotic notation?

o a) Big-O

o b) Little-o

o c) Sigma notation

o d) Big-Omega
Answer: c

7. Time complexity of accessing an element in an array by index is:

o a) O(n)

o b) O(log n)

o c) O(1)

o d) O(n²)
Answer: c

8. Space complexity of a recursive binary search is:

o a) O(1)

o b) O(log n)

o c) O(n)

o d) O(n log n)
Answer: b

9. Which algorithm has O(n²) worst-case time complexity?

o a) Merge sort

o b) Quick sort
 o c) Bubble sort

o d) Binary search
Answer: c

10. The formula for space complexity includes:

o a) Fixed + Variable + Recursion space

o b) Variable only

o c) Recursion only

o d) Execution time
Answer: a

Section B — Asymptotic Notations & Analysis (11–25)

11. Big-O notation describes:

o a) Best case

o b) Worst case

o c) Average case

o d) Space complexity only

Answer: b

12. Big-Omega notation describes:

o a) Best case

o b) Worst case

o c) Tight bound

o d) Memory usage
Answer: a

13. Θ notation describes:

o a) Lower bound only

o b) Upper bound only

o c) Exact/tight bound

o d) None
Answer: c

14. Which complexity grows fastest?

o a) O(n log n)

o b) O(2ⁿ)

o c) O(n²)

o d) O(1)
Answer: b

15. If f(n) = 3n³ + 2n² + n, then complexity is:

o a) O(n³)

o b) O(n²)

o c) O(n)

o d) O(3n³)
Answer: a
16. Which is faster for large n?

o a) O(n)

o b) O(n²)

o c) O(n³)

o d) O(2ⁿ)
Answer: a

17. Which notation is used for tight bound analysis?

o a) O

o b) Ω

o c) Θ

o d) None
Answer: c

18. If f(n) = 5n² + 3n + 7, and g(n) = n², then:

o a) f(n) ∈ O(g(n))

o b) f(n) ∈ Ω(g(n))

o c) f(n) ∈ Θ(g(n))

o d) All of the above

Answer: d

19. Which of these is not true about O(n log n)?

o a) Faster than O(n²) for large n

o b) Slower than O(n) for large n

o c) Slower than O(log n) for large n

o d) Faster than O(1)

Answer: d

20. Best case of binary search is:

o a) O(n)

o b) O(log n)

o c) O(1)

o d) Θ(log n)
Answer: c

21. Insertion sort's best case occurs when:

o a) Data is sorted

o b) Data is reverse sorted

o c) Data is random

o d) None
Answer: a

22. Insertion sort best case complexity:

o a) O(n)

o b) O(n²)

o c) O(log n)
 o d) O(1)
Answer: a

23. Merge sort's time complexity:

o a) O(n²)

o b) O(n log n)

o c) O(log n)

o d) O(n)
Answer: b

24. Which is not correct?

o a) O(1) is constant

o b) O(log n) grows faster than O(n)

o c) O(n!) grows faster than O(2ⁿ)

o d) O(n²) grows faster than O(n log n)

Answer: b

25. In Big-O, constants are:

o a) Considered

o b) Ignored

o c) Sometimes considered

o d) Multiplied
Answer: b

Section C — Advanced & Trick Questions (26–50)

26. The term asymptotic means:

o a) Exact time measurement

o b) Behavior for large inputs

o c) Best case only

o d) Space usage
Answer: b

27. O(n³) algorithm is better than O(2ⁿ) when:

o a) For small n

o b) For large n

o c) Always

o d) Never
Answer: a

28. If an algorithm runs in 5 ms for n=1000, doubling n may roughly take:

o a) 10 ms (if O(n))

o b) 20 ms (if O(n²))

o c) 40 ms (if O(n²))

o d) Same time (O(1))

Answer: a

29. Which complexity is smallest for large n?

 o a) O(n log n)

o b) O(n²)

o c) O(log n)

o d) O(1)
Answer: d

30. If recursion depth is proportional to n, recursion space is:

o a) O(1)

o b) O(n)

o c) O(log n)

o d) O(n²)
Answer: b

31. Which is correct for Quick sort?

o a) Best: O(n log n), Worst: O(n²)

o b) Best: O(n²), Worst: O(n log n)

o c) Both O(n²)

o d) Both O(n log n)

Answer: a

32. Binary search works only if:

o a) Array is sorted

o b) Array is unsorted

o c) Array is small

o d) Array is large
Answer: a

33. Which complexity represents polynomial time?

o a) O(n²)

o b) O(2ⁿ)

o c) O(n!)

o d) O(n log n)
Answer: a, d

34. Which is not polynomial?

o a) O(n³)

o b) O(2ⁿ)

o c) O(n log n)

o d) O(n⁵)
Answer: b

35. Amortized analysis is used when:

o a) Operation cost varies

o b) Operation cost is constant

o c) Space is constant

o d) Input is sorted
Answer: a
36. Which has worst growth rate?

o a) O(1)

o b) O(log n)

o c) O(n)

o d) O(n!)
Answer: d

37. O(log n) complexity is common in:

o a) Binary search

o b) Linear search

o c) Bubble sort

o d) Selection sort
Answer: a

38. If T(n) = 2T(n/2) + n, complexity is:

o a) O(n log n)

o b) O(n²)

o c) O(n)

o d) O(log n)
Answer: a

39. Binary tree traversal complexity:

o a) O(n)

o b) O(log n)

o c) O(n²)

o d) O(1)
Answer: a

40. Which is divide-and-conquer?

o a) Merge sort

o b) Quick sort

o c) Binary search

o d) All of these
Answer: d

41. For a fixed input size, complexity:

o a) Changes

o b) Remains constant

o c) Grows exponentially

o d) None
Answer: b

42. Which operation has O(1) complexity in a hash table (average)?

o a) Search

o b) Insert

o c) Delete
 o d) All of these
Answer: d

43. Best case for bubble sort:

o a) O(n)

o b) O(n²)

o c) O(log n)

o d) O(1)
Answer: a

44. Which algorithm has same best, average, and worst case?

o a) Merge sort

o b) Quick sort

o c) Insertion sort

o d) Heap sort
Answer: a, d

45. Which notation ignores lower-order terms?

o a) Big-O

o b) Big-Theta

o c) Big-Omega

o d) All
Answer: d

46. O(n³) is:

o a) Polynomial

o b) Exponential

o c) Factorial

o d) Constant
Answer: a

47. Which is tightest bound for n² + 5n?

o a) O(n²)

o b) Θ(n²)

o c) Ω(n²)

o d) O(n)
Answer: b

48. Which grows faster than O(n!)?

o a) O(2ⁿ)

o b) O(n²)

o c) O(nⁿ)

o d) O(log n)
Answer: c

49. Logarithmic time is most efficient when:

o a) Data size is huge

o b) Data is small
 o c) Time is unlimited

o d) None
Answer: a

50. Algorithm efficiency depends mainly on:

o a) Input size

o b) Hardware

o c) Programming style

o d) Output format
Answer: a

Full Theory — Searching and Sorting Algorithms

1. Searching Algorithms

Definition

Searching is the process of finding the location of an element (key) within a collection of data (array, list, database, etc.).

1.1 Linear Search

• Idea: Check each element one by one until you find the target or reach the end.

• Steps:

1. Start from the first element.

2. Compare each element with the key.

3. If found, return the index.

4. If not found after traversing all, return “not found”.

• Time Complexity:

o Best Case: O(1) (if the first element matches)

o Worst Case: O(n)

o Average Case: O(n)

• Space Complexity: O(1)

• Pros: Works on unsorted data, very simple.

• Cons: Very slow for large datasets.

1.2 Binary Search

• Idea: Repeatedly divide the sorted array in half until you find the key.

• Precondition: Data must be sorted.

• Steps:

1. Find the middle element.

2. If it matches the key → success.

3. If key < middle → search in left half.

 4. If key > middle → search in right half.

5. Repeat until found or range is empty.

• Time Complexity:

o Best Case: O(1)

o Worst Case: O(log₂ n)

o Average Case: O(log₂ n)

• Space Complexity:

o Iterative: O(1)

o Recursive: O(log n) (due to recursion stack)

• Pros: Very efficient for large datasets.

• Cons: Only works on sorted data.

1.3 Jump Search

• Idea: Jump ahead by fixed steps (√n) and then do a linear search in the block.

• Time Complexity: O(√n)

• When to use: Sorted data with random access.

1.4 Interpolation Search

• Idea: Improved binary search that estimates the position of the key using linear interpolation.

• Best Case: O(1)

• Average: O(log log n)

• Worst: O(n) (when distribution is non-uniform)

• Precondition: Sorted and uniformly distributed data.

1.5 Exponential Search

• Idea: Find range by doubling the index, then perform binary search in the range.

• Time Complexity: O(log n)

2. Sorting Algorithms

Definition

Sorting is the process of arranging elements in a particular order (ascending or descending).

2.1 Bubble Sort

• Process: Compare adjacent elements and swap if out of order; repeat until no swaps needed.

• Time Complexity:

o Best: O(n) (already sorted, optimized version)

o Worst: O(n²)
 o Avg: O(n²)

• Space: O(1)

• Stable: Yes.

2.2 Selection Sort

• Process: Find the smallest element and place it in the first position, then repeat for the rest.

• Time Complexity: O(n²) in all cases.

• Space: O(1)

• Stable: No.

2.3 Insertion Sort

• Process: Build sorted list by inserting each element into the correct position in already sorted part.

• Time Complexity:

o Best: O(n) (already sorted)

o Worst: O(n²)

o Avg: O(n²)

• Space: O(1)

• Stable: Yes.

2.4 Merge Sort

• Approach: Divide and Conquer.

• Process:

1. Divide the array into halves until size = 1.

2. Merge sorted halves.

• Time Complexity: O(n log n) (all cases)

• Space: O(n) (extra array)

• Stable: Yes.

2.5 Quick Sort

• Approach: Divide and Conquer.

• Process:

1. Choose a pivot.

2. Partition elements (smaller on left, larger on right).

3. Recursively apply to partitions.

• Time Complexity:

o Best/Avg: O(n log n)

o Worst: O(n²) (bad pivot choice)

 • Space: O(log n) (recursion)

• Stable: No.

2.6 Heap Sort

• Process:

1. Build max heap.

2. Swap root with last element.

3. Reduce heap size and heapify.

• Time Complexity: O(n log n)

• Space: O(1)

• Stable: No.

2.7 Counting Sort

• Non-comparison based.

• Works by counting occurrences of elements.

• Time Complexity: O(n + k) (k = range of input)

• Space: O(k)

• Stable: Yes.

2.8 Radix Sort

• Sorts by processing digits from least significant to most significant.

• Time Complexity: O(nk)

• Stable: Yes.

2.9 Bucket Sort

• Distributes elements into buckets, sorts each bucket, and merges.

• Time Complexity: O(n + k) average.

• Stable: Yes.

Comparison Table — Searching & Sorting

Algorithm Best Average Worst Space Stable

Linear Search O(1) O(n) O(n) O(1) Yes

Binary Search O(1) O(log n) O(log n) O(1) Yes

Bubble Sort O(n) O(n²) O(n²) O(1) Yes

Selection Sort O(n²) O(n²) O(n²) O(1) No

Algorithm Best Average Worst Space Stable

Insertion Sort O(n) O(n²) O(n²) O(1) Yes

Merge Sort O(n log n) O(n log n) O(n log n) O(n) Yes

Quick Sort O(n log n) O(n log n) O(n²) O(log n) No

Heap Sort O(n log n) O(n log n) O(n log n) O(1) No

SEARCHING ALGORITHMS

1. Linear Search (Sequential Search)

Definition:
Checks each element of the list sequentially until the desired element is found or the list ends.
Steps:

1. Start from the first element.

2. Compare target element with the current element.

3. If match found → return position.

4. If list ends → return not found.

Best Case: Target is the first element (1 comparison).

Worst Case: Target is last element or absent (n comparisons).
Time Complexity:

• Best Case: O(1)

• Worst Case: O(n)

• Average Case: O(n)

Space Complexity: O(1) (in-place)

2. Binary Search

Definition:
Efficient search method for sorted arrays. Repeatedly divides the search interval in half.

Steps:

1. Set low = 0, high = n-1.

2. Find mid = (low + high) / 2.

3. If arr[mid] == target → found.

4. If target < arr[mid] → search left half (high = mid - 1).

5. Else → search right half (low = mid + 1).

6. Repeat until low > high (not found).

Important: Works only on sorted arrays.

Passes: Not applicable — works via halving.

Time Complexity:

• Best Case: O(1)

• Worst Case: O(log n)

• Average Case: O(log n)

Space Complexity:

• Iterative: O(1)
 • Recursive: O(log n) (stack space)

SORTING ALGORITHMS

1. Bubble Sort

Definition:
Repeatedly compares adjacent elements and swaps them if they are in the wrong order.

Passes:

• After 1st pass → largest element is at the end.

• After 2nd pass → 2nd largest is fixed.

• And so on.

• Total passes in worst case: n-1.

When Array is Sorted:

If in a pass no swaps are made → array is sorted early (best case O(n)).

Time Complexity:

• Best Case: O(n) (already sorted, with optimization)

• Worst Case: O(n²) (reverse sorted)

• Average Case: O(n²)

Space Complexity: O(1) (in-place)
Stable: Yes.

2. Selection Sort

Definition:
Finds the smallest element and places it at the beginning; repeats for remaining elements.

Passes:

• Pass 1: Find min in 1..n, place at index 0.

• Pass 2: Find min in 2..n, place at index 1.

• Always needs n-1 passes, even if already sorted.

When Array is Sorted: Only after the final pass.

Time Complexity:

• Best Case: O(n²)

• Worst Case: O(n²)

• Average Case: O(n²)

Space Complexity: O(1)
Stable: No (unless modified).

3. Insertion Sort

Definition:
Builds sorted list one element at a time by inserting each element into its proper place.

Passes:

• Pass 1: First 2 elements sorted.

 • Pass 2: First 3 elements sorted.

• Pass k: First k+1 elements sorted.

• Needs n-1 passes worst case.

When Array is Sorted:

Best case is when array is already sorted (O(n)).

Time Complexity:

• Best Case: O(n)

• Worst Case: O(n²)

• Average Case: O(n²)

Space Complexity: O(1)
Stable: Yes.

4. Merge Sort

Definition:
Divide and Conquer — divides array into halves, sorts them recursively, and merges.

Steps:

• Divide array until single elements remain.

• Merge sorted subarrays.

Passes:
Each pass merges subarrays → log₂n passes.

Time Complexity:

• Best/Worst/Average: O(n log n)

Space Complexity: O(n) (needs extra space for merging)
Stable: Yes.

5. Quick Sort

Definition:
Select pivot → partition elements into left (< pivot) and right (> pivot) → sort recursively.

Passes:
Number of passes depends on pivot placement.

• Best: log₂n passes

• Worst: n passes (if bad pivot always chosen)

Time Complexity:

• Best/Average: O(n log n)

• Worst: O(n²)
Space Complexity: O(log n) (recursive stack)
Stable: No (by default).

6. Counting Sort

Definition:
Counts number of occurrences of each value → reconstructs sorted array. Works for integers in small range.

Time Complexity: O(n + k)

Space Complexity: O(n + k)
Stable: Yes.
MCQs – Searching & Sorting (50 Questions)

Searching (Q1–Q15)

Q1. Which searching technique requires the data to be sorted?

a) Linear Search
b) Binary Search
c) Jump Search
d) Both b & c
Ans: d

Q2. Binary search has a time complexity of:

a) O(n)
b) O(log n)
c) O(n log n)
d) O(1)
Ans: b

Q3. In linear search, best case occurs when:

a) Key is last element
b) Key is middle element
c) Key is first element
d) Key is not found
Ans: c

Q4. How many comparisons in worst-case binary search for 100 elements?
a) 6
b) 7
c) 8
d) 10
Ans: c (log₂100 ≈ 6.64 → round up to 7 comparisons)

Q5. In binary search, if the element is not found, the algorithm returns:
a) -1
b) 0
c) NULL
d) Depends on implementation
Ans: d

Q6. Which search is efficient for a small dataset?

a) Linear Search
b) Binary Search
c) Hashing
d) Tree Search
Ans: a

Q7. Which search is not suitable for linked lists?

a) Linear Search
b) Binary Search
c) Jump Search
d) Exponential Search
Ans: b

Q8. The average case complexity of linear search is:

a) O(n)
b) O(log n)
c) O(n/2)
d) O(1)
Ans: a

Q9. Jump Search jumps by how many steps for optimal performance?
a) √n
b) log n
c) n/2
d) 2√n
Ans: a

Q10. Interpolation Search works best for:

a) Sorted and uniformly distributed data
b) Random unsorted data
c) Sparse data
d) None
Ans: a

Q11. Linear search complexity for n elements:

a) O(log n)
b) O(n)
c) O(n²)
d) O(1)
Ans: b

Q12. Binary search complexity for sorted array of size 1024:

a) 5 comparisons max
b) 8 comparisons max
c) 10 comparisons max
d) 20 comparisons max
Ans: c (log₂1024 = 10)

Q13. In binary search, which condition ends recursion?

a) start > end
b) mid > end
c) start = 0
d) key found at mid
Ans: a

Q14. Which searching technique uses divide-and-conquer?

a) Linear Search
b) Binary Search
c) Sequential Search
d) None
Ans: b

Q15. How many comparisons in worst-case linear search for n elements?

a) 1
b) n
c) log n
d) n/2
Ans: b

Sorting (Q16–Q50)

Q16. Bubble sort works by:

a) Comparing and swapping adjacent elements
b) Dividing into halves
c) Choosing a pivot
d) Using heap property
Ans: a

Q17. Worst-case complexity of bubble sort:

a) O(n log n)
b) O(n²)
c) O(log n)
d) O(n)
Ans: b

Q18. Number of passes required to bubble sort 5 elements:

a) 3
b) 4
c) 5
d) 2
Ans: b (n-1 passes)

Q19. Which sorting algorithm is stable?

a) Quick Sort
b) Merge Sort
c) Heap Sort
d) Selection Sort
Ans: b
Q20. Best-case complexity of bubble sort (already sorted array):
a) O(n)
b) O(n²)
c) O(log n)
d) O(1)
Ans: a

Q21. In selection sort, after k passes:

a) k largest elements are in correct position
b) k smallest elements are in correct position
c) Array is sorted
d) None
Ans: b

Q22. Worst-case complexity of selection sort:

a) O(n log n)
b) O(n²)
c) O(n)
d) O(1)
Ans: b

Q23. How many passes in insertion sort for 6 elements?

a) 5
b) 4
c) 6
d) n/2
Ans: a (n-1 passes)

Q24. Merge sort uses which approach?

a) Greedy
b) Divide-and-Conquer
c) Dynamic Programming
d) Brute force
Ans: b

Q25. Worst-case complexity of merge sort:

a) O(n²)
b) O(n log n)
c) O(log n)
d) O(n)
Ans: b

Q26. Which sorting algorithm can be done in-place?

a) Merge Sort
b) Quick Sort
c) Counting Sort
d) Radix Sort
Ans: b

Q27. Quick sort worst-case occurs when:

a) Pivot divides array equally
b) Pivot is always smallest/largest element
c) Random pivot chosen
d) None
Ans: b

Q28. How many passes for bubble sort to sort [5,4,3,2,1]?

a) 3
b) 4
c) 5
d) 2
Ans: b (n-1 = 4)

Q29. Which sort is best for small arrays and nearly sorted data?
a) Quick Sort
b) Merge Sort
c) Insertion Sort
d) Heap Sort
Ans: c

Q30. Heap sort builds:

a) Binary Search Tree
b) Heap Tree
c) AVL Tree
d) Red-Black Tree
Ans: b

Q31. In selection sort, number of swaps in worst case for n elements:

a) O(n²)
b) O(n)
c) O(1)
d) O(log n)
Ans: b (exactly n-1 swaps)

Q32. Which sorting is NOT comparison-based?

a) Quick Sort
b) Counting Sort
c) Merge Sort
d) Heap Sort
Ans: b

Q33. If bubble sort stops early when no swap in pass, complexity becomes:
a) O(n)
b) O(n²)
c) O(log n)
d) O(1)
Ans: a

Q34. Radix sort works best for:

a) Floating-point numbers
b) Integers with known digit length
c) Random real numbers
d) Strings only
Ans: b

Q35. How many comparisons in worst-case selection sort for n=4?

a) 6
b) 8
c) 10
d) 4
Ans: b (n(n-1)/2 = 6)

Q36. Quick sort average complexity:

a) O(n²)
b) O(n log n)
c) O(log n)
d) O(n)
Ans: b

Q37. Which sorting algorithm is used in merge sort for small subarrays?
a) Bubble Sort
b) Insertion Sort
c) Quick Sort
d) Selection Sort
Ans: b (Hybrid approach in practice)

Q38. Shell sort is an improved version of:

a) Selection Sort
b) Insertion Sort
c) Merge Sort
d) Heap Sort
Ans: b

Q39. Best pivot choice in quick sort for worst-case avoidance:

a) First element
b) Last element
c) Median
d) Random element
Ans: c

Q40. Which sorting has best worst-case complexity?

a) Merge Sort
b) Quick Sort
c) Heap Sort
d) Insertion Sort
Ans: a
Q41. Number of passes in insertion sort for 8 elements:
a) 6
b) 7
c) 8
d) n/2
Ans: b

Q42. Heap sort worst-case complexity:

a) O(n²)
b) O(n log n)
c) O(log n)
d) O(n)
Ans: b

Q43. Stable sorting algorithms include:

a) Merge Sort, Insertion Sort
b) Quick Sort, Heap Sort
c) Selection Sort, Shell Sort
d) None
Ans: a

Q44. Which algorithm is fastest for large datasets in practice?

a) Quick Sort
b) Merge Sort
c) Bubble Sort
d) Selection Sort
Ans: a (average case)

Q45. Bucket sort works by:

a) Splitting into buckets, sorting each, then merging
b) Dividing into halves
c) Choosing pivot
d) None
Ans: a

Q46. Time complexity of counting sort:

a) O(n²)
b) O(n)
c) O(n log n)
d) O(log n)
Ans: b

Q47. Which sort adapts if the list is already partially sorted?

a) Merge Sort
b) Quick Sort
c) Insertion Sort
d) Heap Sort
Ans: c

Q48. For bubble sort of n elements, total comparisons in worst case:

a) n²/2
b) n(n-1)/2
c) n²
d) log n
Ans: b

Q49. In quick sort, partition step complexity:

a) O(n²)
b) O(n)
c) O(log n)
d) O(1)
Ans: b

Q50. Which sorting algorithm is NOT in-place?

a) Merge Sort
b) Quick Sort
c) Heap Sort
d) Insertion Sort
Ans: a