0 votes 0 votes How many real links are required to store a sparse matrix of 10 rows , 10 columns ,and 15 non zeros entries.(pick up the closest answer) DS data-structures sparse-matrix matrix + – neha singh asked Mar 11, 2016 • recategorized Jun 21, 2022 by Arjun neha singh 2.7k views answer comment Share Follow See all 7 Comments See all 7 7 Comments reply monanshi commented Mar 12, 2016 reply Follow Share I think we can have 2 links per non-zero element one for next row and one for next column. So, total of 15*2 = 30 links. 0 votes 0 votes neha singh commented Mar 13, 2016 reply Follow Share no its ans is 50 0 votes 0 votes Arjun commented Mar 14, 2016 reply Follow Share @monanshi how can that work? We can do with 15 links by storing the row id and column id. http://financelab.nctu.edu.tw/DataStructure/lec05.pdf 1 votes 1 votes abhilashpanicker29 commented Mar 14, 2016 reply Follow Share @Arjun sir, I have seen another type of data structure, where we keep linked lists for each row and column.. (this can be efficient in searching for a particular row/column, rather than having to search in the single list) So, the answer would depend on which data structure one uses I think.. There are various other methods too.. check the second last slide here.. http://www.staff.science.uu.nl/~bisse101/Book/PSC/psc4_2.pdf 1 votes 1 votes Arjun commented Mar 14, 2016 reply Follow Share @Abhilash that would make 30 rt? Question should have mentioned that. 0 votes 0 votes abhilashpanicker29 commented Mar 14, 2016 i edited by abhilashpanicker29 Mar 14, 2016 reply Follow Share @Arjun Sir, 30 for those 15 entries + some more links for the heads of the lists(But this also depends on how you define the data structures, whether you use head nodes or not, etc).. The pic below is an example taken from Data Structures in C by horowitz and sahani. But then, the same book also gives the data structure you talked about with the row id and column id.. So, the question should have clearly mentioned it. Otherwise its ambiguous which data structure should one use. PS: I dont think such a question would come in GATE unless the code for the data structure is explicitly mentioned. 1 votes 1 votes monanshi commented Mar 15, 2016 reply Follow Share Yes sir, nothing more is mentioned in question. In best case 15 should be correct. 1 votes 1 votes Please log in or register to add a comment.
0 votes 0 votes Full matrix = 10 * 10 = 100 Sparse matrix = 100/2 = 50 because in most of the cases sparse matrix take half the size of full matrix as in triangular matrix. vamsi2376 answered Mar 14, 2016 vamsi2376 comment Share Follow See 1 comment See all 1 1 comment reply Arjun commented Mar 14, 2016 reply Follow Share how can we assume a special sparse matrix? 0 votes 0 votes Please log in or register to add a comment.