This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Sparse Matrix”.
Q1. The matrix contains m rows and n columns. The matrix is called Sparse Matrix if ________
A) Total number of Zero elements > (m*n)/2
B) Total number of Zero elements = m + n
C) Total number of Zero elements = m/n
D) Total number of Zero elements = m-n
Explanation: To be called a Sparse Matrix, a matrix must have more zero elements than non-zero elements. The given matrix has a total of mn components. If the total number of zero elements in the matrix is greater than (mn)/2, it is referred to as a Sparse Matrix.
2. Which of the following is not the method to represent Sparse Matrix?
A) Dictionary of Keys
B) Linked List
Explanation: Although rows and column numbers are used as Keys and values as Matrix entries in Dictionary, Linked List is used with each node having four fields (Row, Column, Value, Next Node) (2D array is used to represent the Sparse Matrix with three fields) (Row, Column, Value).
3. Is Sparse Matrix also known as Dense Matrix?
Explanation: A Sparse Matrix is one in which the majority of the elements are Zero, while a Dense Matrix is one in which the majority of the elements are Non-Zero.
4. Which one of the following is a Special Sparse Matrix?
A) Band Matrix
B) Skew Matrix
C) Null matrix
D) Unit matrix
Explanation: A band matrix is a sparse matrix of non-zero elements that are bounded by a diagonal band that includes the main diagonal and zero or more diagonals on either side.
5. In what way the Symmetry Sparse Matrix can be stored efficiently?
B) Binary tree
C) Hash table
D) Adjacency List
Explanation: Since Symmetry Sparse Matrix is the undirected graph’s adjacency matrix. As a result, it can be effectively stored as an adjacency list.
6. Which matrix has most of the elements (not all) as Zero?
A) Identity Matrix
B) Unit Matrix
C) Sparse Matrix
D) Zero Matrix
Explanation: The term “sparse matrix” refers to a matrix in which the majority of the elements are zero. A matrix in which all of the principal diagonal elements are 1 and the rest of the elements are 0 is known as an Identity Matrix. Identity Matrix is another name for Unit Matrix. A Zero Matrix is one in which all of the elements are equal to zero.
7. What is the relation between Sparsity and Density of a matrix?
A) Sparsity = 1 – Density
B) Sparsity = 1 + Density
C) Sparsity = Density*Total number of elements
D) Sparsity = Density/Total number of elements
Explanation: A matrix’s Sparsity is equal to 1 minus the matrix’s Density. The total number of Zero Valued elements divided by the total number of elements is the Sparsity of a matrix.
8. Who coined the term Sparse Matrix?
A) Harry Markowitz
B) James Sylvester
C) Chris Messina
D) Arthur Cayley
Explanation: The word Sparse Matrix was coined by Harry Markowitz. The word Matrix was invented by James Sylvester. Arthur Cayley introduced the algebraic aspects of a matrix, while Chris Messina coined the word Hashtag.
9. Is O(n) the Worst case Time Complexity for addition of two Sparse Matrix?
Explanation: Furthermore, since the matrix is traversed linearly, it has an O(n) time complexity, where n is the number of non-zero elements in the largest of the two matrices.
A sparse matrix, also known as a sparse array, is a matrix with the majority of its elements being empty. There is no precise specification about how many elements in a matrix must be zero to be considered sparse, but one common criterion is that the number of non-zero elements equals the number of rows or columns. When the majority of the elements are nonzero, the matrix is said to be dense. The sparsity of a matrix is defined as the number of zero-valued elements divided by the total number of elements (e.g., m n for a m n matrix).