Question:
Which is the best data structure to represent a sparse matrix?
Which is the best data structure to represent a sparse matrix?
Show Hint
You want to store only the non zero entries. Which structure grows with the count of non zeros, not the full grid?
Updated On: Jul 2, 2026
- Linear array
- Linked list
- Binary tree
- Graph
Show Solution
Verified By Collegedunia
The Correct Option is B
Solution and Explanation
Step 1: A sparse matrix is a matrix where most elements are zero and only a few are non zero. The goal is to store only the non zero entries so we do not waste memory on zeros.
Step 2: A linear array would store every cell including all the zeros, which defeats the purpose. For a matrix of order \( m \times n \) that is \( m \cdot n \) slots regardless of how few non zeros exist.
Step 3: A linked list stores one node per non zero element, each node holding the row index, column index, and value. Memory used is proportional to the number of non zero entries, not the full grid.
Step 4: A binary tree and a graph are not the natural choice for this row, column, value triple storage. The standard and most efficient representation among the options is the linked list.
Answer: option B.
Step 2: A linear array would store every cell including all the zeros, which defeats the purpose. For a matrix of order \( m \times n \) that is \( m \cdot n \) slots regardless of how few non zeros exist.
Step 3: A linked list stores one node per non zero element, each node holding the row index, column index, and value. Memory used is proportional to the number of non zero entries, not the full grid.
Step 4: A binary tree and a graph are not the natural choice for this row, column, value triple storage. The standard and most efficient representation among the options is the linked list.
Answer: option B.
Was this answer helpful?
0
0
Top CPET Computer Science Questions
- Which of the following is a key reason for choosing DRAM over SRAM for main memory?
- Which of the following components in an FPGA is responsible for implementing combinational and sequential logic?
- What is the main purpose of declaring a base class as virtual in multiple inheritance?
- What happens if a class contains at least one pure virtual function?
- What happens if a derived class defines a function with the same name as a base class function, but with a different parameter list?
View More Questions
Top CPET Data Structures - Binary Search Tree Questions
- An M-way search tree is a generalization of which data structure?
- The time complexity to perform an Enqueue operation on a Queue data structure is:
- The Postorder traversal of a Binary Search tree which is created by presenting the values in the order 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 will be:
- Which one of the following is the correct way to increment the rear end of a circular queue represented as an array of size M?
Top CPET Questions
- Which of the following is a key reason for choosing DRAM over SRAM for main memory?
- Which of the following components in an FPGA is responsible for implementing combinational and sequential logic?
- What is the main purpose of declaring a base class as virtual in multiple inheritance?
- What happens if a class contains at least one pure virtual function?
- What happens if a derived class defines a function with the same name as a base class function, but with a different parameter list?
View More Questions