Previously Asked GATE Questions on Arrays

Calculate the address of any element in the 3-D Array:

Question 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

Answer: (a)
Explanation: An array of 50 numbers is correct.

Question 2: What will the output of the below code?

C++

#include <iostream> 
using namespace std; 
   
int main() 
{ 
   
    int arr[2] = { 1, 2 }; 
    cout << 0 [arr] << ", " << 1 [arr] << endl; 
    return 0; 
}

Java

public class Main { 
    public static void main(String[] args) { 
        // Declare and initialize an array 
        int[] arr = { 1, 2 }; 
  
        // Access array elements using the index directly in Java 
        System.out.println(arr[0] + ", " + arr[1]); 
    } 
} 

Python3

# Equivalent Python code 
arr = [1, 2] 
print(arr[0], ", ", arr[1]) 

C#

using System; 
  
class Program 
{ 
    static void Main() 
    { 
        // Declare and initialize an array of integers 
        int[] arr = { 1, 2 }; 
  
        // Print the values using array indexing 
        Console.WriteLine(arr[0] + ", " + arr[1]); 
    } 
} 

Javascript

// Declare an array with two elements 
const arr = [1, 2]; 
  
// Access and print the first element using array indexing 
console.log(arr[0]); 
  
// Print a comma separator 
console.log(', '); 
  
// Access and print the second element using array indexing 
console.log(arr[1]); 

(a) 1, 2
(b) Syntax error
(c) Run time error
(d) None

Answer: (a)
Explanation: 0[arr]] is a different way to represent array element, which represents the first element of the array.
similarly, 1[arr] is a different way to represent array element, which represents the second element of the array.

Question 3: The minimum number of comparisons required to determine if an integer appears more than n/2 times in a sorted array of n integers is

(a) O(n)
(b) O(log(n))
(c) O(nlog(n))
(d) O(1)

Answer: (b)
Explanation: If you answered Theta(1), then think of examples {1, 2, 2, 2, 4, 4}, {1, 1, 2, 2, 2, 2, 3, 3} The Best way to find out whether an integer appears more than n/2 times in a sorted array(Ascending Order) of n integers, would be binary search approach.

The First occurrence of an element can be found out in O(log(n)) time using divide and conquer technique,lets say it is i.

The Last occurrence of an element can be found out in O(log(n)) time using divide and conquer technique,lets say it is j.

Now number of occurrence of that element(count) is (j-i+1). Overall time complexity = log n +log n +1 = O(log(n)).

Question 4: Let A be a square matrix of size n x n. Consider the following program. What is the expected output?

C = 100
for i = 1 to n do
    for j = 1 to n do
    {
        Temp = A[i][j] + C
        A[i][j] = A[j][i]
        A[j][i] = Temp - C
    } 
for i = 1 to n do
    for j = 1 to n do
        Output(A[i][j]);

Answer: 1
Explanation: If we take look at the inner statements of first loops, we can notice that the statements swap A[i][j] and A[j][i] for all i and j. Since the loop runs for all elements, every element A[l][m] would be swapped twice, once for i = l and j = m and then for i = m and j = l. Swapping twice means the matrix doesn’t change.

Question 5: An algorithm performs (logN)^1/² find operations, N insert operations, (logN)^1/2 delete operations, and (logN)^1/2 decrease-key operations on a set of data items with keys drawn from a linearly ordered set. For a delete operation, a pointer is provided to the record that must be deleted. For the decrease-key operation, a pointer is provided to the record that has its key decreased. Which one of the following data structures is the most suited for the algorithm to use, if the goal is to achieve the best total asymptotic complexity considering all the operations?

(a) Unsorted array
(b) Min-heap
(c) Sorted array
(d) Sorted doubly linked list

Answer: (a)
Explanation: The time complexity of insert in unsorted array is O(1), O(Logn) in Min-Heap, O(n) in sorted array and sorted DLL.

For unsorted array, we can always insert an element at end and do insert in O(1) time

For Min Heap, insertion takes O(Log n) time. Refer Binary Heap operations for details.

For sorted array, insert takes O(n) time as we may have to move all elements worst case.

For sorted doubly linked list, insert takes O(n) time to find position of element to be inserted.

Question 6: Consider an array consisting of –ve and +ve numbers. What would be the worst case time complexity of an algorithm to segregate the numbers having same sign altogether i.e all +ve on one side and then all -ve on the other ?

(a) O(N)
(b) O(Nlog(N))
(c) O(N*N)
(d) O(Nlog(log(N)))

Answer: (c)
Explanation: Here we can use the partition algorithm of quick sort for segregation and answer will be O(N*N). Choose the first element as pivot whatever may be its sign we don’t care and keep an extra index at pivot position.

Question 7: Let A[1…n] be an array of n distinct numbers. If i < j and A[i] > A[j], then the pair (i, j) is called an inversion of A. What is the expected number of inversions in any permutation on n elements ?

(a) n(n-1)/2
(b) n(n-1)/4
(c) n(n+1)/4
(d) 2nlog(n)

Answer: (b)
Explanation: There are n(n-1)/2 pairs such that i < j. For a pair (a_i, a_j), probability of being inversion is 1/2. Therefore expected value of inversions = 1/2 * (n(n-1)/2) = n(n-1)/4.

Question 8: Consider the following array declaration in the ‘C’ language:

int array 1[] = {2, 3};
int array2[3]={9};
What will be the output of the following print statement?
printf(“%d, %d”, array1 [1], array2 [2]);

(a) 2, 0
(b) 3, 0
(c) 2, 9
(d) 4, 9

Answer: (b)

Question 9: Consider the following C program.

#include < stdio.h >
int main () {
    int a [4] [5] = {{1, 2, 3, 4, 5},
                           {6, 7, 8, 9, 10},
                           {11, 12, 13, 14, 15},
                           {16, 17, 18, 19, 20}};
    printf (“%d\n”, *(*(a+**a+2) +3));
    return (0);
}

The output of the program is _______.

Answer: 19

Question 10: Which operations can not be done in O(1) for an array of sorted data.

(a) Print the nth largest element
(b) Print the nth smallest element
(c) Delete element
(d) None of the above

Answer: (c)
Explanation: If we have to delete x and its index is last, it would take O(n).

Array Notes for GATE Exam [2024]

Arrays are fundamental data structures in computer science, and mastering them is crucial for success in the GATE exam. This article aims to provide concise yet comprehensive notes on arrays, covering essential concepts and strategies to help you tackle array-related questions in the GATE 2024 exam.

Table of Content

Introduction to Arrays
Basic terminologies of the array
Representation of Array
Types of arrays
Finding Adress of an Element in Array
Calculating the address of any element In the 1-D array
Calculate the address of any element in the 2-D array
Calculate the address of any element in the 3-D Array
Previously Asked GATE Questions on Arrays

Previously Asked GATE Questions on Arrays

C++

Java

Python3

C#

Javascript

Array Notes for GATE Exam [2024]

Similar Reads