Exercise: Questions on Array


Questions on Array : Question 1 :
A program P reads in 500 integers in the range [0..100] exepresenting 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? (GATE CS 2005)

An array of 50 numbers
An array of 100 numbers
An array of 500 numbers
A dynamically allocated array of 550 numbers
Show Answer
Questions on Array : Question 2 :
Which of the following operations is not O(1) for an array of sorted data. You may assume that array elements are distinct.

Find the ith largest element
Delete an element
Find the ith smallest element
All of the above
Show Answer
Questions on 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) \theta(n)
(B) \theta(logn)
(C) \theta(log*n)
(D) \theta(1)

A
B
C
D
Show Answer
Questions on Array : 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]);

The matrix A itself
Transpose of matrix A
Adding 100 to the upper diagonal elements and subtracting 100 from diagonal elements of A
None of the above
Show Answer
Questions on Array : Question 5 :
An algorithm performs (logN)1/2 find operations, N insert operations, (logN)1/2 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?

Unsorted array
Min-heap
Sorted array
Sorted doubly linked list
Show Answer
Questions on Array : Question 6 :
Consider an array consisting of –ve and +ve numbers. What would be the worst time comparisons an algorithm can take in order to segregate the numbers having same sign altogether i.e all +ve on one side and then all -ve on the other ?

N-1
N
N+1
(N*(N-1))/2
Show Answer