৪৯তম বিসিএস ⎯ কম্পিউটার সায়েন্স (CSE) [৯৭১]

Linked list:
A linked list stores elements in nodes scattered across memory connected by pointers.
Contiguous memory locations:(Answer)
A 1D array is stored in a single continuous block of memory where each element is placed right after the previous one. This allows direct indexing with base_address + index * size_of_element.
Non-contiguous blocks:
If memory blocks are scattered, you’d need pointers to connect them — which is again a linked structure, not an array.
Binary tree:
A binary tree is a hierarchical structure, not a linear storage format like arrays.

Indexing in an array is done by calculating Base_Address + (Index * Size_of_Element), which takes constant time O(1).

Time complexity
O(1) (constant time):
If an operation always takes the same amount of time regardless of array size n.
Examples: array access by index, push/pop on stack, hash-table lookup (average case).
O(n) (linear time):
Have to scan all elements.
Example: searching for a number in an unsorted array that's why  you may check every element.
O(log n) (logarithmic time):
If each step halves the problem size.
Example: binary search in a sorted array.
O(n²) (quadratic time):
If you have nested loops over the array.
Example: bubble sort or comparing every element with every other element.

Answer: A-2024
Address formula: Base + (i * Size) = 2000 + (5 * 4) = 2020. Since array index starts from 0, A[5] means the 6th element → 2000 + (5*4) = 2020.

Searching in an unsorted array
Since the array is unsorted, cannot use tricks like binary search (which requires sorted data).
The only way is to check elements one by one until  find the element or reach the end of the array.
Worst-case
If the element is not present,  have to check all ?
Even if the element is present, in the worst case it could be at the last position (index n−1).
So the number of comparisons = n.
Worst-case time complexity=O(n)

Answer: B 
​ Stack: A stack follows the LIFO principle: the last element inserted is the first one removed. 
​Think of a stack of plates: you place plates on top (push), and you remove from the top (pop). 
​Used in function calls, recursion, expression evaluation, and backtracking.
​
​Queue: Linear data structure that follows FIFO (First In, First Out).
example: A line of people at a ticket counter.
​
​Linked List: A sequence of nodes, where each node stores data + pointer (address of next node).
​
​ Heap: A special binary tree (complete tree) used for fast retrieval of min/max element.

Answer: A 
​Stack underflow occurs when we try to remove an element from an empty stack. 
​Stack overflow happens when we try to push into a full stack (in fixed-size array implementation).

 Answer: D
​Deque (Double Ended Queue) supports Insertion/deletion at front & rear. 
​Input-restricted deque: insertion at one end only. Output-restricted deque: deletion at one end only

Answer: B 
​ Breadth-First Search (BFS) uses a queue to explore level by level. 
How it works:
o Visit the root.
o Visit all nodes at the current level, left to right.
o Then move to the next level

​DFS uses a stack (or recursion) ,it has three main variants Preorder, Inorder, Postorder.

Answer: C
​  Undo/Redo maintains history in two stacks: Undo stack, Redo stack
​  Undo → follows LIFO (Last In, First Out).
The last action you performed is the first one you want to undo.
So each action is pushed onto an Undo stack.
Redo → uses another stack.
When you undo an action, it is moved (popped from Undo, pushed to Redo).
If you choose redo, it pops from the Redo stack and reapplies the action.

Answer: A 
 Stack = LIFO (last element removed first). Queue = FIFO (first element removed first).

Answer: B 
Arrays = contiguous memory, fixed size. 
​Linked lists = nodes linked via pointers, non-contiguous, dynamic size.

 Answer: C 
​Dynamic memory allocation & easy insertions/deletions
Arrays have a fixed size. Once declared, you cannot easily resize them (in languages like C/C++). 
​Expanding means creating a new larger array and copying all elements (O(n)).
Linked Lists can grow or shrink dynamically because each element (node) is allocated separately and connected via pointers.
Insertions and deletions in a linked list are efficient (O(1)) if you already have the pointer to the node, since you only adjust pointers.

Answer: D 
​Time Complexity for Linked List
Best case:
The element is at the head (first node) → only 1 comparison → O(1).
Worst case:
The element is at the last node or not present at all → must traverse all n nodes → O(n).
Average case:
On average, you’ll search through n/2 nodes before finding it → but in Big-O, that’s still O(n).
​Example
Linked list: 10 → 20 → 30 → 40 → 50
Search for 10: found at head → O(1).
Search for 50: must traverse all → O(n).
Search for 60: not present → traverse all → O(n).

Answer B 
 A binary tree is a hierarchical structure where each node has at most two children (left and right).
​ Option C is full binary tree (every node has 0 or 2)

Answer: C
Level numbering starts at 0 for root. At level l, maximum nodes = 2^{L .
Maximum number of nodes at level l in a binary tree
A binary tree is such that each node can have at most 2 children.
At level 0 → only 1 node (the root).
At level 1 → at most 2 nodes.
At level 2 → at most 4 nodes.
​At level L → at most:
​
​}

2^{h + 1} - 1
Answer: A
 A complete binary tree of height h has: 1 + 2 + 4 + ... + 2ʰ = 2ʰ⁺¹ − 1 nodes.
​
​
​Here, h= 3 (level 0-3)
​Number of total nodes = 2ʰ⁺¹ − 1 =2³⁺¹ −1= 15

  Answer: C
​Dense Matrix: Most of the elements are non-zero, Stored in a regular 2D array form.
Efficiency: Simple to access any element using row & column indices → O(1).
Memory: Uses a lot of memory if the matrix is very large.
​Sparse Matrix: Most of the elements are zero.
Storage: Instead of storing all elements, only the non-zero elements with their positions (row, column) are stored 
Efficiency: Saves space but access can be slower since you may need to search through the stored entries.
Memory: Very efficient for large matrices with many zeros

Linear Data Structure
A data structure is linear if its elements are arranged in a sequential (linear) order, and each element has a unique predecessor and successor (except the first and last). ​Example: Array, Linked List, Stack, Queue 
 Non-linear Data Structure
A data structure is non-linear if its elements are not stored sequentially. Each element can connect to multiple elements, forming a hierarchical or network structure. Example: Tree, Graph

Stack
A stack is a linear data structure that follows the LIFO (Last In, First Out) principle.
Operations:
PUSH → Insert an element (on top).
POP → Remove an element (from top).
PEEK / TOP → View the top element without removing.
isEmpty / isFull → Check stack status.

Representation: Can be implemented using Array or Linked List.

Dynamic data structures allocate/deallocate memory at runtime/ dynamically, are flexible in size, and include linked lists, trees, and graphs.
​Where Array, Stack, Queue are Static Data structure.

Answer: C 
​ BST property = Left < Root < Right.
​In a Binary Search Tree (BST):
The left subtree of a node contains only nodes with values less than the node’s key.
The right subtree of a node contains only nodes with values greater than the node’s key.
both left and right subtrees themselves must also be BSTs.
​Following is a pictorial representation of BST −
​

Answer: B) Stack
​ Reason:
Recursion follows LIFO, and Stack is the best structure for LIFO operations.
Every recursive call is pushed onto the call stack, and when the function ends, it is popped.

Answer: C Better memory utilization 
​Explanation: In a linear queue, once rear reaches the end, we can’t insert more elements even if space is free at the beginning. A circular queue reuses empty slots, so memory is used more efficiently.Both

Answer: B) (rear + 1) % N == front 
Circular queue full condition: 
​If advancing rear by one position (circularly) makes it equal to front, then the queue is full.
Because rear cannot move to the front position (that slot is reserved to distinguish full from empty).
Example (size = 5):
​Index: 0 1 2 3 4
Queue: [10][20][30][40][50]
front = 0
rear = 4
Now,
(rear + 1) % size = (4 + 1) % 5 = 0
And since front = 0, condition is true → Queue is Full.

Answer: D
Sparse matrices  are usually represented using Triplet, CSR, or CSC.
​An AVL tree is a data structure for fast searching, not a typical sparse matrix storage method.

Answer: C 
Queue is a linear data structure that follows the First-In-First-Out (FIFO
 Enqueue(insert) → rear (End)
​Dequeue(remove) → front 
​
​

Answer: C 
​A deque (short for double-ended queue) is a data structure that allows insertion and deletion of elements from both ends, making it more flexible than a standard queue. Unlike a regular queue that follows the FIFO (First In First Out) principle, a deque allows operations at both the front and rear ends. That’s why it is called a double-ended queue.

Answer: A 
Input-restricted → Insert only at one end; delete from both ends. 
​Output-restricted → Delete only at one end; insert at both ends.

Answer: B 
​Stack Overflow occurs when we try to push an element into a stack that is already full.

For an array-based stack of size n: Index ranges: 0 to n-1
top points to the current top element.
If top = n-1, the stack is full, and any further push causes overflow.

Stack Underflow occurs when we try to pop from an empty stack (top = -1).

Answer: D Elements are served according to priority
Priority queue is a special type of queue in which each element is associated with a priority.
​Higher priority elements are served before lower priority ones.
If two elements have the same priority, they are served according to FIFO (first-come-first-served) or implementation-specific rules.
In  Priority queue 
Each element has a priority.
Insertion can happen at any position based on priority.
Deletion always removes the highest-priority element.