Data Structures and Algorithms Multiple Choice Questions (MCQs) and Answers

Dijkstra's algorithm

Bellman-Ford algorithm

Kosaraju's algorithm

Floyd-Warshall algorithm

Using Dijkstra's algorithm repeatedly for each vertex

Using the Bellman-Ford algorithm repeatedly for each vertex

Using Floyd-Warshall algorithm

Using Prim's algorithm

By performing a topological sort

By checking if the edge connects vertices in the same strongly connected component

By using a union-find data structure

By calculating the graph's diameter

Because BFS does not account for edge weights

Because BFS only works on unweighted graphs

Because the graph is not properly connected

Because the starting node is chosen incorrectly

The graph contains negative edge weights

The priority queue is not updated correctly

The algorithm stops too early

The graph is not strongly connected

Failing to initialize the distance matrix correctly

Not iterating through all vertex pairs

Incorrectly handling negative cycles

All of the above

A binary tree that is completely filled, except possibly for the bottom level, which is filled from left to right

A binary tree where each node has a value greater than or equal to its children

A binary tree where each node has a value less than or equal to its children

Both A and B

A letter in a string

A complete string

A pointer to another trie

A and C

Faster merge operation

Better space complexity

Fixed time insertion

A and C

Binary search tree

Hash table

Binary heap

Linked list

Tries do not require hash functions and can provide alphabetical ordering

Hash tables are faster for insertion and deletion

Tries take up less space

A and C

It provides the worst-case time complexity for any single operation

It shows the average time complexity over a sequence of operations

It guarantees constant time complexity for all operations

It reduces the space complexity of the data structure

Create a new node for every character of the key and link them

Reuse existing nodes for the key if they match and create new nodes only when necessary

Insert the key at the root

B and C

Finding the maximum value

Insertion

Deletion

Finding the minimum value

By swapping the new element with the root if it's smaller

By placing the new element in the leftmost available position and then "heapifying" up

By sorting the entire heap after each insertion

By replacing the largest element if the new element is smaller

The heapify process is not correctly implemented

The heap is not balanced correctly after operations

Keys are not compared correctly during insertions

All of the above

Nodes for some letters are not correctly linked

The search function does not correctly handle word endings

Case sensitivity issues

A and B

Frequent splaying of the same nodes

Not splaying at every operation

Incorrectly balancing the tree

Overuse of rotations in splay operations

Simplifying a problem by breaking it into smaller, more manageable parts

Increasing the efficiency of sorting algorithms

Optimizing recursive functions

Balancing binary search trees

A technique for finding the shortest path in a graph

A way to conserve memory by deleting unnecessary data

A recursive method for solving combinatorial problems by trying to build a solution incrementally

A data compression method

Dynamic programming requires that the problem has overlapping subproblems, whereas divide and conquer does not

Dynamic programming uses only recursion, while divide and conquer does not

Dynamic programming is used only for optimization problems

Divide and conquer algorithms are not applicable to problems with optimal substructure

Greedy algorithms make a sequence of choices that may not lead to an optimal solution, while dynamic programming ensures an optimal solution by considering all possible solutions

Greedy algorithms are easier to implement than dynamic programming solutions

Greedy algorithms can solve a wider range of problems than dynamic programming

Dynamic programming is only suitable for problems with a linear structure

To provide the exact solution to NP-hard problems

To provide solutions that are close to the best possible answer for NP-hard problems

To reduce the time complexity of algorithms to polynomial time

To convert NP-hard problems into P problems

To guarantee the best solution to problems

To provide a deterministic time complexity for any given problem

To improve the average-case performance of algorithms by introducing randomness

To simplify the implementation of algorithms

By placing queens one by one in different rows and checking for conflicts at each step

By randomly placing queens on the board and rearranging them to resolve conflicts

By using a greedy algorithm to place all queens simultaneously

By calculating the exact positions of all queens before placing them

Memoization

Randomization

Backtracking

Linear search

By selecting activities randomly until no more can be chosen

By choosing the shortest activities first

By selecting the activities that start the earliest, without overlapping

By choosing the activities that leave the most free time after completion

The algorithm does not consider all possible subsets of tasks

The algorithm makes irreversible decisions based on local optima without considering the entire problem

The tasks are not sorted correctly before the algorithm is applied

The algorithm incorrectly calculates the finish times of tasks

The recursive calls are too deep

The memoization table consumes too much memory

There are not enough subproblems

The problem does not exhibit overlapping subproblems

Increasing the available memory

Converting the recursion to iterative form to use less memory

Reducing the problem size

Using a more efficient memoization strategy