Parallel and Distributed Computing Unit - 4 mcq

1. The serial algorithm requires ___, for matrix multiplications and additions for n*n matrix.
(A) W = n²
(B) W = n³
(C) W = n log n
(D) None of these

Correct option is A

2. Is Sparse Matrix also known as Dense Matrix?
(A) True
(B) False

Correct option is B

3. ____ is the simplest sorting algorithm that works by repeatedly swapping the adjacent element if they are in wrong order.
(A) Bubble Sort
(B) Quick Sort
(C) Merge Sort
(D) None of these

Correct option is A

4. Complexity of bubble sort in best case, worst case, and Average case respectively.
(A) O(n²), O(n³), O(n³)
(B) O(n), O(n²), O(n²)
(C) O(logn), O(n), O(n)
(D) None of these

Correct option is B

5. What is an external sorting algorithm?
(A) Algorithm that uses tape or disk during the sort.
(B) Algorithm that uses main memory during the sort.
(C) Algorithm that involves swapping
(D) Algorithm that are considered ‘in place’

Correct option is A

6. What is an internal sorting algorithm?
(A) Algorithm that uses tape or disk during the sort
(B) Algorithm that uses main memory during the sort.
(C) Algorithm that are considered ‘in place’.
(D) Algorithm that involves swapping

Correct option is B

7. Statement: Kruskal’s algorithm is best suited for the sparse graphs than the prim’s algorithm.
(A) True
(B) False

Correct option is A

8. The given array is arr = {5, 6, 7, 8}. Bubble sort is used to sort the array elements. How many iterations will be done to sort the array?
(A) 4
(B) 2
(C) 0
(D) 1

Correct option is A

9. The given array is arr = {1,2,4,3}. Bubble sort is used to sort the array elements. How many iterations will be done to sort the array with improvised version?
(A) 4
(B) 2
(C) 0
(D) 1

Correct option is B

10. Which of the following sorting algorithms is the fastest?
(A) Merge Sort
(B) Quick Sort
(C) Shell sort
(D) Insertion Sort

Correct option is B

11. Statement: Quick sort follows Divide-and-Conquer strategy.
(A) True
(B) False

Correct option is A

12 Which of the following methods is the most effective for picking the pivot element?
(A) First element
(B) Second element
(C) Random element
(D) Median-of-three partitioning

Correct option is D

13. Which of the following statements for a simple graph is correct?
(A) Every trail is a path as well as every path is a trail
(B) Every path is a trail
(C) Path and trail have no relation
(D) Every trail is a path

Correct option is B

14. Statement: In a simple graph, the number of edges is equal to twice the sum of the degrees of the vertices.
(A) True
(B) False

Correct option is B

15. A connected planar graph having 6 vertices, 7 edges contains _____ regions.
(A) 11
(B) 1
(C) 3
(D) 15

Correct option is C

16. If a simple graph G, contains n vertices and m edges, the number of edges in the Graph G'(Complement of G) is _____
(A) (n*n-n-2*m)/2
(B) (n*n+n+2*m)/2
(C) (n*n-n-2*m)/2
(D) (n*n-n+2*m)/2

Correct option is A

17. Which of the following properties does a simple graph not hold?
(A) Must be connected
(B) Must have no loops or multiple edges
(C) Must be unweighted
(D) Must have no multiple edges

Correct option is A

18. Which of the following is true?
(A) A graph may contain no edges and many vertices
(B) A graph may contain no edges and no vertices
(C) A graph may contain many edges and no vertices
(D) A graph may contain no vertices and many edges

Correct option is C

19. Which of the following is false in the case of a spanning tree of a graph G?
(A) It is a subgraph of the G
(B) It is tree that spans G
(C) It includes every vertex of the G
(D) It can be either cyclic or acyclic

Correct option is D

20. Consider a complete graph G with 4 vertices. The graph G has __ spanning trees.
(A) 13
(B) 16
(C) 8
(D) 15

Correct option is B

21. Which of the following is not the algorithm to find the minimum spanning tree of the given graph?

(A) Boruvka’s algorithm
(B) Kruskal’s algorithm
(C) Prim’s algorithm
(D) Bellman–Ford algorithm

Correct option is D

22. Dijkstra’s Algorithm is used to solve _____ problems.
(A) All pair shortest path
(B) Network flow
(C) Single source shortest path
(D) Sorting

Correct option is C

23. Which of the following is the most commonly used data structure for implementing Dijkstra’s Algorithm?
(A) Min priority queue
(B) Circular queue
(C) Stack
(D) Max priority queue

Correct option is D

24. The maximum number of times the decrease key operation performed in Dijkstra’s algorithm will be equal to _____
(A) Number of vertices – 1
(B) Number of edges – 1
(C) Total number of vertices
(D) Total number of edges

Correct option is D