CHP 1

1. Fundamentals (Data, Data Types, ADT, Algorithm, Program Analysis)

Q1: What does Abstract Data Type (ADT) define?

a) Physical data structures
b) Logical behavior and operations
c) Storage allocation
d) Programming language syntax
Answer: b) Logical behavior and operations

Q2: Which characteristic is not of a good algorithm?

a) Finiteness
b) Definiteness
c) Randomness
d) Output
Answer: c) Randomness

2. Arrays, Sparse Matrices, Transpose

Q3: What is a sparse matrix?

a) Most elements non-zero
b) Most elements zero
c) Equal zero and non-zero
d) Only diagonal non-zero
Answer: b) Most elements zero (dbatu.ac.in, sanfoundry.com, scribd.com)

Q4: Which is true: sparsity + density = ____?

a) 0
b) 1
c) m × n
d) m/n
Answer: b) 1 (sanfoundry.com)

Q5: For transpose of a sparse matrix, what's the efficient representation?

a) 2D array
b) Dictionary of keys
c) Linked list of non-zero triples
d) Heap
Answer: c) Linked list of triples (sanfoundry.com)

3. Linear vs Non-Linear Structures, Storage Representation

Q6: Which is linear?

a) Binary tree
b) Graph
c) Array
d) Hash table
Answer: c) Array

Q7: Which is non-linear?

a) Stack
b) Array
c) Binary tree
d) Queue
Answer: c) Binary tree

4. Hashing – Core Concepts

Q8: What is direct addressing?

a) Keys < slots
b) Slots < keys
c) 1:1 key-slot mapping
d) Chaining
Answer: c) 1:1 mapping (scribd.com, sanfoundry.com)

Q9: What is the time complexity of direct addressing search?

a) O(n)
b) O(log n)
c) O(n log n)
d) O(1)
Answer: d) O(1) (sanfoundry.com)

Q10: Collision in hashing means?

a) Randomness
b) Duplication
c) Two keys map to same slot
d) Deletion
Answer: c) Two keys map to same slot (sanfoundry.com)

Q11: What is the load factor α in chaining?

a) #slots/#elements
b) #elements/#slots
c) Average chain length
d) Slots × keys
Answer: c) Average chain length (= #elements/#slots) (sanfoundry.com, dbatu.ac.in,
geeksforgeeks.org)

Q12: Which does not reduce collisions?

a) Uniform hashing
b) Randomized hash function
c) Chaining
d) Only increasing table size
Answer: d) Only increasing table size (sanfoundry.com)
5. Open Addressing & Perfect Hashing

Q13: In open addressing, collisions are resolved using:

a) Linked lists
b) Probing sequences (linear/quadratic)
c) Trees
d) External storage
Answer: b) Probing sequences

Q14: Perfect hashing is used when:

a) Infinite keys
b) Random keys
c) Fixed key set — no collisions
d) External memory
Answer: c) Fixed key set — no collisions

CHP 2

🔹 1. Stack & Queue as ADT

Q1. A stack ADT supports which primary operations?

a) enqueue/dequeue
b) push/pop
c) insert/delete at random
d) find/merge
Answer: b) push/pop (server.cwipedia.in, geeksforgeeks.org, en.wikipedia.org)

Q2. Queue follows the ___ principle.

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

🔹 2. Representation & Implementation

Q3. Which data structures can implement stacks and queues?

a) Arrays only
b) Linked lists only
c) Both arrays & linked lists
d) Trees
Answer: c) Both arrays & linked lists (scribd.com, server.cwipedia.in)
Q4. In linked-list stack implementation, what points to the current top?
a) Rear pointer
b) Front pointer
c) Top pointer
d) Null
Answer: c) Top pointer (server.cwipedia.in)

🔹 3. Circular Queue

Q5. Circular queues are also known as:

a) Ring buffers
b) Square buffers
c) Linear buffers
d) Curve buffers
Answer: a) Ring buffers (sanfoundry.com, srinix.org)

Q6. A circular queue implemented with array size n is full if:

a) (rear +1) mod n == front
b) rear == front
c) front = (rear +1) mod n
d) front +1 = rear
Answer: a) (rear +1) mod n == front (server.cwipedia.in)

🔹 4. Expression Evaluation & Conversion using Stack

Q7. Which data structure is used for converting infix to postfix expressions?
a) Queue
b) Stack
c) Array
d) Tree
Answer: b) Stack

Q8. Given sequence: push(5), push(8), pop, push(2), push(5), pop, pop, pop, push(1), pop —
popped output is:
a) 8 5 2 5 1
b) 8 5 5 2 1
c) 8 2 5 5 1
d) 8 1 2 5 5
Answer: a) 8 5 2 5 1 (server.cwipedia.in)

🔹 5. Recursion
Q9. Recursion is typically implemented using which data structure internally?
a) Queue
b) Stack
c) Linked list
d) Heap
Answer: b) Stack (scribd.com)

🔹 6. Priority Queue

Q10. The most efficient implementation of a priority queue uses:

a) Array
b) Heap
c) Linked list
d) Tree
Answer: b) Heap (scribd.com)

Q11. What operation removes the highest-priority element?

a) enqueue
b) extract_max / extract_min
c) peek
d) search
Answer: b) extract_max (or extract_min) (en.wikipedia.org)

Q12. Which is not an application of priority queues?

a) Huffman coding
b) OS interrupt handling
c) Undo functionality in editors
d) Scheduling algorithms
Answer: c) Undo functionality (sanfoundry.com)

CHP 3

📘 1. Linked List Fundamentals & Memory Management

Q1. Linked lists exemplify what kind of memory allocation?

a) Static
b) Dynamic
c) Compile-time
d) Heap
Answer: b) Dynamic (nktdegreecollege.org)

Q2. Why are linked lists space-efficient compared to arrays?

a) Contiguous memory
b) Dynamic growth
c) Better cache locality
d) Fixed size
Answer: b) Dynamic growth (en.wikipedia.org)

📌 2. Singly vs. Doubly vs. Circular Linked Lists

Q3. In a doubly linked list, each node has:

a) One pointer
b) Two pointers
c) Three pointers
d) No pointers
Answer: b) Two pointers (server.cwipedia.in, en.wikipedia.org)

Q4. A circular linked list differs from a singly linked list because:
a) Last node points to null
b) Last node points to first
c) Only head pointer exists
d) No pointers at all
Answer: b) Last node points to first (nktdegreecollege.org, dbatu.ac.in, dacc.edu.in)

Q5. Which variant allows concatenation of two lists in O(1) time?

a) Singly linked
b) Doubly linked
c) Circular doubly linked
d) Array list
Answer: c) Circular doubly linked (server.cwipedia.in)

🛠️ 3. Operations: Insertion, Deletion, Traversal, Concatenation

Q6. What’s the time to count elements in a linked list of size n?

a) O(1)
b) O(log n)
c) O(n)
d) O(n²)
Answer: c) O(n) (nktdegreecollege.org, t.me)

Q7. In singly linked list, inserting at head takes:

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

Q8. In linked queue, if only front pointer exists, insertion is:

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

🔄 4. Dynamic Storage Management & Garbage Collection

Q9. Garbage collection recovers memory occupied by objects that are:

a) In use
b) Never allocated
c) No longer used
d) Fragmented
Answer: c) No longer used (dacc.edu.in)

CHP 4

🌲 1. Binary Trees – Terminology & Representation

Q1. The number of edges from the root to a node is called its:
a) Height
b) Depth
c) Length
d) Width
Answer: b) Depth (sanfoundry.com)

Q2. A full binary tree is one where:

a) Every node has either 0 or 2 children
b) All leaves are at the same level
c) Every node has exactly two children
d) No children
Answer: a) Every node has 0 or 2 children (sanfoundry.com)

🔧 2. Insertion & Deletion in Binary Trees

Q3. In a general binary tree, deleting a node with two children typically requires replacement
by:
a) Its leftmost leaf
b) Its inorder successor
c) A random node
d) Its parent
Answer: b) Its inorder successor (en.wikipedia.org)

Q4. Node insertion in a binary tree uses array representation where children positions are:
a) 2i and 2i+1
b) i+1, i+2
c) i^2, i^2+1
d) Undefined
Answer: a) 2i and 2i+1 (sist.sathyabama.ac.in, scribd.com)

️ 3. BSTs & Traversal

Q5. A binary search tree (BST) has the property that left subtree keys are ___ and right
subtree keys are ___.
a) Greater, smaller
b) Random
c) Smaller, greater
d) Equal
Answer: c) Smaller, greater (ggn.dronacharya.info)

Q6. Inorder traversal of a BST yields:

a) Pre-sorted order
b) Random order
c) Post-sorted order
d) Reversed order
Answer: a) Sorted order (sanfoundry.com, en.wikipedia.org)

️ 4. Threaded Binary Trees

Q7. Threaded binary trees use otherwise-null pointers to link to:

a) Next inorder predecessor or successor
b) Random memory
c) Root only
d) Parent only
Answer: a) Inorder predecessor/successor (en.wikipedia.org, ggn.dronacharya.info)

️ 5. Heaps & Balanced Trees

Q8. In a max-heap, every child node must be:

a) ≥ parent
b) ≤ parent
c) Random
d) Distinct
Answer: b) ≤ parent (so parent is maximum)

Q9. A red-black tree ensures:

a) Heap order only
b) Height-balanced BST with O(log n) operations
c) Linear time inserts
d) No balancing
Answer: b) Height-balanced BST with O(log n) complexity (scribd.com, quizlet.com)

🌐 6. Graphs – Adjacency Matrix & Warshall’s Algorithm

Q10. In adjacency matrix, entry A[i][j] = 1 means:

a) No edge
b) Edge from i to j
c) Node exists but no edge
d) Matrix empty
Answer: b) Edge from i to j (coursehero.com, geeksforgeeks.org)

Q11. Warshall's algorithm computes:

a) Minimum spanning tree
b) Shortest path between all nodes
c) Adjacency list
d) Graph coloring
Answer: b) All-pairs shortest paths (transitive closure)

CHP 5

Here are DBATU-style remedial MCQs covering your specified topics — sequential &
binary search, skip lists, sorting algorithms (insertion, selection, radix), and file handling:

🔍 1. Searching: Sequential & Binary

Q1. In sequential (linear) search, average-case time complexity is:

a) O(1)
b) O(log n)
c) O(n)
d) O(n log n)
Answer: c) O(n)
Q2. Binary search requires the array to be:
a) Unsorted
b) Sorted
c) In linked list form
d) Duplicated
Answer: b) Sorted

🌐 2. Skip Lists – Dictionaries

Q3. A skip list achieves average search time of:

a) O(n)
b) O(log n)
c) O(1)
d) O(n log n)
Answer: b) O(log n) (geeksforgeeks.org, en.wikipedia.org, sanfoundry.com)

Q4. Skip list insertion height uses:

a) Fixed height
b) Random (coin flips)
c) Deterministic promotion
d) Balanced tree logic
Answer: b) Random via coin flips (ics.uci.edu, geeksforgeeks.org, aaronclauset.github.io)

Q5. Worst-case skip list deletion can take:

a) O(log n)
b) O(n)
c) O(1)
d) O(n log n)
Answer: b) O(n) (rare, but possible) (en.wikipedia.org, coursehero.com)

⚙️ 3. Sorting: Insertion, Selection, Radix

Insertion Sort

Q6. Insertion sort uses ___ passes for n elements:

a) n-1
b) n
c) log n
d) n²
Answer: a) n−1

Q7. Best-case time complexity (already sorted):

a) O(n)
b) O(n log n)
c) O(n²)
d) O(1)
Answer: a) O(n) (sanfoundry.com)

Selection Sort

Q8. Selection sort is unstable because:

a) It swaps equal elements randomly
b) Always maintains order
c) It's stable
d) It uses extra memory
Answer: a) It can change the order of equal elements (testbook.com, sanfoundry.com,
scribd.com)

Radix Sort

Q9. Radix sort is classified as:

a) Comparison-based
b) Non-comparison-based
c) Heapsort variant
d) In-place sorting
Answer: b) Non-comparison-based (testbook.com, sanfoundry.com)

🗂️ 4. File Handling

Q10. Which mode in C opens files for appending in text mode?

a) "r"
b) "w"
c) "a"
d) "r+"
Answer: c) "a"

Q11. To read binary data, which mode is correct?

a) "rb"
b) "wb"
c) "ab"
d) "rt"
Answer: a) "rb"