Data Structure and Algorithms MCQ IT Officer(PSC)

 1. A queue follows

a. LIFO principle
b. FIFO principle
c. Linear tree
d. Ordered array
Correct Answer: b
Explanation: A queue follows the First-In-First-Out (FIFO) principle, where the first element added is the first to be removed, similar to a real-world queue (e.g., a line of people). LIFO (Last-In-First-Out) applies to stacks, not queues.

2. The time complexity used for inserting a node in a priority queue on the basis of key is:
a. O(n)
b. O(n²)
c. O(nlogn)
d. O(log n)
Correct Answer: d
Explanation: In a priority queue implemented using a heap (e.g., binary heap), insertion involves adding an element and performing a heapify-up operation, which takes O(log n) time due to the height of the tree. The given answer "a" is incorrect; the correct answer is "d".

3. Which of these is a postfix expression?
a. a + b - c
b. +ab
c. abc*+de-+
d. ab(c+d)
Correct Answer: c
Explanation: A postfix expression (Reverse Polish Notation) places operators after operands (e.g., abc+de-+ means ((a * b) + c) - (d + e)). Options a and d are infix, and b is not a valid expression. The correct answer is "c".

4. Which data structure do we use for testing a palindrome?
a. Heap
b. Tree
c. Priority queue
d. Stack
Correct Answer: d
Explanation: A stack is used to test a palindrome by pushing characters and popping them to compare with the original sequence in reverse (e.g., "radar" can be checked by comparing halves). The correct answer is "d".

5. Which of these will form an inversion in this given array? arr = {2, 8, 5, 3}
a. (2, 8)
b. (8, 5), (8, 3)
c. (2, 8), (2, 5), (1, 3)
d. (8, 5), (8, 3), (5, 3)
Correct Answer: d
Explanation: An inversion occurs when a larger element appears before a smaller element in an array. In {2, 8, 5, 3}, the pairs (8, 5), (8, 3), and (5, 3) are inversions. Option d lists all valid inversions. The correct answer is "d".

6. Which one isn't the property of the XOR lists?
a. X ⊕ 0 = X
b. X ⊕ X = 0
c. X ⊕ 0 = 1
d. (X ⊕ Y) ⊕ Z = X ⊕ (Y ⊕ Z)
Correct Answer: c
Explanation: XOR (exclusive OR) properties include: X ⊕ 0 = X, X ⊕ X = 0, and (X ⊕ Y) ⊕ Z = X ⊕ (Y ⊕ Z). However, X ⊕ 0 = 1 is incorrect; XOR with 0 returns the original value. The correct answer is "c".

7. The tango tree is a type of:
a. Binary Search Tree
b. K-ary Tree
c. Ternary Tree
d. AVL Tree
Correct Answer: a
Explanation: A tango tree is a type of self-adjusting Binary Search Tree (BST) optimized for dynamic operations. It is not specifically a K-ary, Ternary, or AVL tree. The correct answer is "a".

8. In an AA-tree, we can remove a left horizontal link by:
a. inserting a new element
b. deleting both the elements
c. performing left rotation
d. performing right rotation
Correct Answer: d
Explanation: An AA-tree (a variant of a red-black tree) maintains balance by avoiding left horizontal links. Removing a left horizontal link is done with a right rotation. The correct answer is "d".

9. We can use a self-balancing binary search tree for implementing the:
a. Hash table
b. Priority queue
c. Heap sort and Priority queue
d. Heap sort
Correct Answer: b
Explanation: A self-balancing binary search tree (e.g., AVL or Red-Black tree) can efficiently implement a priority queue with O(log n) operations for insertion and deletion. It’s not ideal for hash tables or heap sort. The correct answer is "b".

10. A splay operation refers to:
a. the removal of leaf node
b. the movement of root to leaf
c. the movement of a node to root
d. the movement of parent node to a child node's down
Correct Answer: c
Explanation: In a splay tree, a splay operation moves the accessed node to the root to optimize future accesses. The correct answer is "c".

11. Out of these, which one is NOT true about a 2-3 tree?
a. it is perfectly balanced
b. the leaves are always at the same level
c. it refers to a B-tree of the order 3
d. postorder traversal would yield the elements in a sorted order
Correct Answer: d
Explanation: A 2-3 tree is perfectly balanced with leaves at the same level and is a B-tree of order 3. However, postorder traversal does not guarantee a sorted order; inorder traversal does. The correct answer is "d".

12. How do we define the Ackermann's function?
a. for i < 1, Λ(i, i) = i + 1
b. for i = j, Λ(i, j) = i + j
c. for i >= j, Λ(i, j) = i + j
d. for i >= 1, Λ(1, i) = i + 1
Correct Answer: d
Explanation: The Ackermann function is a recursive function where Λ(1, i) = i + 1 is a base case. The other options do not correctly define it. The correct answer is "d".

13. A recursive implementation would presumably fail in skew heaps because:
a. lack of stack space
b. time complexity
c. these heaps are self adjusting
d. efficiency gets reduced
Correct Answer: a
Explanation: Skew heaps are self-adjusting, but recursive implementations can fail due to stack overflow with deep recursion, especially with large datasets. The correct answer is "a".

14. Which operation can we NOT perform directly in a dheap?
a. create
b. find
c. delete
d. insert
Correct Answer: b
Explanation: A d-ary heap supports create, insert, and delete operations directly, but finding a specific element (e.g., finding the minimum) requires a search, which is not a direct operation. The correct answer is "b".

15. The time taken for the construction of suffix tree is:
a. Linear to the Length of Tree
b. Exponential to the Length of Tree
c. O(M!)
d. O(log M)
Correct Answer: a
Explanation: Suffix tree construction can be done in linear time (O(n)) with respect to the length of the input string using algorithms like Ukkonen’s. The correct answer is "a".

16. The best technique for handling collision is:
a. Separate chaining
b. Double hashing
c. Linear probing
d. Quadratic probing
Correct Answer: a
Explanation: Separate chaining handles collisions by storing colliding elements in linked lists, offering better performance and avoiding clustering compared to probing methods. The correct answer is "a" (though "d" was given, "a" is more widely accepted as optimal).

17. Which one is the most desirable out of these traits of a hash function?
a. it must cause more collisions
b. it must be easy to implement
c. it must cause less collisions
d. it must occupy less space
Correct Answer: c
Explanation: A hash function should minimize collisions to ensure efficient retrieval. Ease of implementation and space are secondary to collision minimization. The correct answer is "c".

18. What is the time complexity for checking if an undirected graph with E edges and V vertices is Bipartite, given its adjacency matrix?
a. O(E)
b. O(V)
c. O(EE)
d. O(VV)
Correct Answer: d
Explanation: Using an adjacency matrix, checking bipartiteness with BFS or DFS takes O(V²) time, as each vertex is visited and checked against all others. The correct answer is "d".

19. The members of two of the sets are relatively more common when the Jaccard Index is:
a. Closer to 0
b. Closer to 1
c. Farther to 1
d. Closer to -1
Correct Answer: b
Explanation: The Jaccard Index measures similarity between sets, ranging from 0 to 1. A value closer to 1 indicates more common members. The correct answer is "b".

20. The polynomial-time graph manipulation algorithms can't implement which of these logical operations using the Binary Decision Diagrams?
a. Tautology Checking
b. Negation
c. Disjunction
d. Conjunction
Correct Answer: a
Explanation: Binary Decision Diagrams (BDDs) can efficiently handle negation, disjunction, and conjunction in polynomial time, but tautology checking (determining if a formula is always true) is more complex and not guaranteed to be polynomial. The correct answer is "a".

---

MCQs from PAGE2

1. When determining the efficiency of algorithm, the space factor is measured by
a. Counting the maximum memory needed by the algorithm
b. Counting the minimum memory needed by the algorithm
c. Counting the average memory needed by the algorithm
d. Counting the maximum disk space needed by the algorithm
Correct Answer: a
Explanation: The space factor measures the maximum memory required by an algorithm during execution, including variables and data structures. The correct answer is "a".

2. The complexity of Bubble sort algorithm is
a. O(n)
b. O(log n)
c. O(n²)
d. O(n log n)
Correct Answer: c
Explanation: Bubble sort compares adjacent elements and swaps them, resulting in O(n²) time complexity in all cases due to nested loops. The correct answer is "c".

3. Linked lists are best suited
a. for relatively permanent collections of data
b. for the size of the structure and the data in the structure are constantly changing
c. for both of above situation
d. for none of above situation
Correct Answer: b
Explanation: Linked lists are ideal when the size and data change frequently due to dynamic memory allocation, unlike arrays which are better for permanent data. The correct answer is "b".

4. If the values of a variable in one module is indirectly changed by another module, this situation is called
a. internal change
b. inter-module change
c. side effect
d. side-module update
Correct Answer: c
Explanation: A side effect occurs when one module unintentionally alters a variable in another module, often through global variables or pointers. The correct answer is "c".

5. In linear search algorithm the Worst case occurs when
a. The item is somewhere in the middle of the array
b. The item is not in the array at all
c. The item is the last element in the array
d. The item is the last element in the array or is not there at all
Correct Answer: d
Explanation: The worst case in linear search is when the item is at the end or not present, requiring n comparisons. The correct answer is "d".

6. For an algorithm the complexity of the average case is
a. Much more complicated to analyze than that of worst case
b. Much more simpler to analyze than that of worst case
c. Sometimes more complicated and some other times simpler than that of worst case
d. None or above
Correct Answer: a
Explanation: Average case complexity requires probabilistic analysis over all inputs, making it more complicated than the worst case, which considers a single maximum scenario. The correct answer is "a".

7. The complexity of merge sort algorithm is
a. O(n)
b. O(log n)
c. O(n²)
d. O(n log n)
Correct Answer: d
Explanation: Merge sort uses a divide-and-conquer approach, resulting in O(n log n) time complexity due to splitting and merging phases. The correct answer is "d".

8. The complexity of linear search algorithm is
a. O(n)
b. O(log n)
c. O(n²)
d. O(n log n)
Correct Answer: a
Explanation: Linear search checks each element sequentially, leading to O(n) time complexity in the worst and average cases. The correct answer is "a".

9. When determining the efficiency of algorithm the time factor is measured by
a. Counting microseconds
b. Counting the number of key operations
c. Counting the number of statements
d. Counting the kilobytes of algorithm
Correct Answer: b
Explanation: Time efficiency is measured by counting the number of key operations (e.g., comparisons, assignments) rather than raw time or statements. The correct answer is "b".

10. Which of the following data structure is linear data structure?
a. Trees
b. Graphs
c. Arrays
d. None of above
Correct Answer: c
Explanation: A linear data structure has elements arranged sequentially (e.g., arrays), unlike trees and graphs, which are non-linear. The correct answer is "c".

11. The elements of an array are stored successively in memory cells because
a. by this way computer can keep track only the address of the first element and the addresses of other elements can be calculated
b. the architecture of computer memory does not allow arrays to store other than serially
c. both of above
d. none of above
Correct Answer: a
Explanation: Arrays use contiguous memory, allowing the computer to calculate subsequent addresses from the first element’s address using the index. The correct answer is "a".

12. Which of the following data structure is not linear data structure?
a. Arrays
b. Linked lists
c. Both of above
d. None of above
Correct Answer: d
Explanation: Both arrays and linked lists are linear data structures, as they organize data sequentially. The correct answer is "d" (none of the above are non-linear).

13. The Average case occur in linear search algorithm
a. When Item is somewhere in the middle of the array
b. When Item is not in the array at all
c. When Item is the last element in the array
d. When Item is the last element in the array or is not there at all
Correct Answer: a
Explanation: The average case in linear search assumes the item is found midway, requiring n/2 comparisons on average. The correct answer is "a".

14. Two main measures for the efficiency of an algorithm are
a. Processor and memory
b. Complexity and capacity
c. Time and space
d. Data and space
Correct Answer: c
Explanation: Efficiency is measured by time (execution speed) and space (memory usage) complexities. The correct answer is "c".

15. Finding the location of the element with a given value is:
a. Traversal
b. Search
c. Sort
d. None of above
Correct Answer: b
Explanation: Searching involves finding the location of a specific element, unlike traversal (visiting all elements) or sorting (ordering elements). The correct answer is "b".

16. Which of the following case does not exist in complexity theory
a. Best case
b. Worst case
c. Average case
d. Null case
Correct Answer: d
Explanation: Complexity theory considers best, worst, and average cases, but "null case" is not a recognized category. The correct answer is "d".

17. The operation of processing each element in the list is known as
a. Sorting
b. Merging
c. Inserting
d. Traversal
Correct Answer: d
Explanation: Traversal involves visiting and processing each element in a list, unlike sorting, merging, or inserting. The correct answer is "d".

18. Arrays are best data structures
a. for relatively permanent collections of data
b. for the size of the structure and the data in the structure are constantly changing
c. for both of above situation
d. for none of above situation
Correct Answer: a
Explanation: Arrays are ideal for permanent data due to fixed size, unlike linked lists which handle dynamic changes. The correct answer is "a".

19. Each array declaration need not give, implicitly or explicitly, the information about
a. the name of array
b. the data type of array
c. the first data from the set to be store
d. the index set of the array
Correct Answer: c
Explanation: Array declaration requires a name, data type, and index set, but not the first data value, which is assigned later. The correct answer is "c".

20. The complexity of Binary search algorithm is
a. O(n)
b. O(log n)
c. O(n²)
d. O(n log n)
Correct Answer: b
Explanation: Binary search divides the search space in half each step, resulting in O(log n) time complexity for a sorted array. The correct answer is "b".