Thursday, January 3, 2013

GATE Questions-Data Structure- Arrays

Previous GATE questions with solutions on Data Structures (Arrays) - CS/IT


1. A program P reads in 500 integers in the range [0,100] representing the scores of 500 students. It then prints the frequency of each score above 50. what would be the best way for P to store the frequencies?

(a) An array of 50 numbers 
(b) An array of 100 numbers
(c) An array of 500 numbers
(d) A dynamically allocated array of 550 numbers

Ans: Option (a)
We have to store frequencies of scores above 50. That is number of students having score 51, number of students having score 52 and so on. For that an array of size 50 is the best option.

2. An n*n matrix V is defined as follows
V[i,j]=i-j for all i,j, 1<=i<=n;1<=j<=n; 
The sum of the elements of the array V is
(a) 0        (b) n-1       (c) n2-3n+2           (d) n2(n+1)/2

Ans: option (a)
Explanation: Work out the same with a 2x2 matrix, and sum its elements.

3. Suppose you are given an array s[1...n] and a procedure reverse (s,i,j) which reverse the order of elements in s between positions i and j (both inclusive). What does the following sequence do, where 1 < k <= n:
  reverse (s, 1, k);
  reverse (s, k + 1, n);
  reverse (s, 1, n);
(a) Rotates s left by k positions
(b) Leaves s unchanged
(c) Reverses all elements of s
(d) None of the above

Ans: option (a)
For any value of k, three reversals is equivalent to the left rotation of the array of size n by k. Note, if we rotate an array n times for k = 1 to n, we get the same array back. Try it with an array of 4 elements.

4. A single array A[1..MAXSIZE] is used to implement two stacks. The two stacks grow from opposite ends of the array. Variables top1 and top2 (topl< top 2) point to the location of the topmost element in each of the stacks. If the space is to be used efficiently, the condition for “stack full” is
(a) (top1 = MAXSIZE/2) and (top2 = MAXSIZE/2+1)
(b) top1 + top2 = MAXSIZE
(c) (top1= MAXSIZE/2) or (top2 = MAXSIZE)
(d) top1= top2 -1

Ans: option (d)
Given that both the stacks grows from opposite ends, i.e. if the stack has 1 element each, then top1 =1 and top2 = MAXSIZE. Let MAXSIZE = 10, according to option (a) top1 = 5, and top2=6. Here the stack is full, but it is only one instance where the stack is full. It is not necessary that for the space to be utilized efficiently top1 should be 5 and top2 should be 6. Option (d) satisfies all the instances where the stack is full.

5. Let A be a two-dimensional array declared as follows: 
      A: array [1 …. 10] [1 …… 15] of integer; 
Assuming that each integer takes one memory location, the array is stored in row-major order and the first element of the array is stored at location 100, what is the address of the element A[i][j]?
(a) 15i + j + 84          (b) 15j + i + 84  
(c) 10i + j + 89          (d) 10j + i + 89 

Ans: option(a)
The array is stored in row-major order, that means the elements are stored in the memory row-wise. 
Suppose we have the 2D array
1 2 3
4 5 6
It will be stored in the memory as 1 2 3 4 5 6
If array is stored as column-major order then it will be stored as 1 4 2 5 3 6

Let A be a 2D array, A: array [b1 …. u1] [b2 …… u2], then 
To find the location of A[i][j] for a 2D array stored in Row-major order use the following formula:

Loc A[i][j] = L + [ (i - b1) (u2 - b2 +1) + (j  - b2) ] x M

L - base address of the array, i.e. address of the first element of the array
M - Memory Size, here each integer takes only 1 memory location therefore M = 1

Loc A[i][j] = 100 + [ (i - 1) (15 - 1 +1) + (j  - 1) ] x 1
                = 100 + (i - 1) 15 + j -1 = 15i + j + 84

To find the location of A[i][j] for a 2D array stored in Column-major order use the following formula:

Loc A[i][j] = L + [ (j - b2) (u1 - b1 +1) + (i  - b1) ] x M

6. Two matrices M1 and M2 are to be stored in arrays A and B respectively. Each array can be stored either in row-major or column-major order in contiguous memory locations. The time complexity of an algorithm to compute M1 × M2 will be 
(a) best if A is in row-major, and B is in column major order 
(b) best if both are in row-major order 
(c) best if both are in column-major order 
(d) independent of the storage scheme

Ans: option (d)
Whether the array is stored in row-major order or column-major order, same number of multiplications and additions are required for matrix multiplication. Hence time complexity is independent of the storage scheme. 

7. In a compact single dimensional array representation for lower triangular matrices (i.e all the elements above the diagonal are zero) of size  n x n , non-zero elements (i.e elements of the lower triangle) of each row are stored one after another, starting from the first row, the index of the  (i,j)th element of the lower triangular matrix in this new representation is: 
(a) i + j       (b) i + j -1     (c) j + [i(i-1)/2]    (d)  i + [j(j-1)/2]

Ans: option (c)
An example of lower triangular matrix of size 3 x 3 is given below.
1   0   0
2   3   0
4   5   6
While storing we will store as 1 2 3 4 5 6.
Index of the  (i,j)th element = the number of elements in (i - 1) rows + j
                                          = (1 + 2 + ... + i-1) + j
                                          = [i(i-1)/2] + j
Hence option (c)
* The number of elements in (i - 1) rows  = 1 + 2 + ... + i-1, because first row contains only 1 element, second row contains only 2 elements, third row contains only 3 elements and so on.
* 1 + 2 + ... + n = n(n-1)/2


  1. ty..its really useful explanation..

  2. GATE 2017 CSE Programming and Data Structures Previously asked Questions and Answers

  3. The storage of all of this additional data has really put a strain on some companies that are outgrowing their data storage needs every 6-12 months or are having difficulty organizing stored data.Self Storage