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)

Which of the following operations is not O(1) for an array of sorted data. You may assume that array elements are distinct.

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) (n) (B) (logn) (C) (log*n) (D) (1)

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]);

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?

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 ?