Data Structure


Q21.

Consider the following algorithm for searching for a given number x in an unsorted array A[1.....n] having n distinct values : (1) Choose an i uniformly at random from [1....n] (2) If A[i] = x then stop else Goto 1; Assuming that x is present A, What is the expected number of comparisons made by the algorithm before it terminates?
GateOverflow

Q22.

Consider the following declaration of a two-dimensional array in C : Char a[100][100] Assuming that the main memory is byte-addressable and that array is stored starting form memory address 0, the address of a [40] [50] is
GateOverflow

Q23.

An n \times n array v is defined as follows: v\left[i,j\right] = i - j for all i, j, i \leq n, 1 \leq j \leq n The sum of the elements of the array v is
GateOverflow

Q24.

Suppose you are given an array s[1....n] and a procedure reverse (s, i, j) which reverses the order of elements in s between positions i and j (both inclusive). What does the following sequence do, where 1 \leqslant k \leqslant n: reverse (s, 1, k); reverse (s, k+1, n); reverse (s, 1, n);
GateOverflow

Q25.

Suppose we want to arrange the n numbers stored in any array such that all negative values occur before all positive ones. Minimum number of exchanges required in the worst case is
GateOverflow

Q26.

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]?
GateOverflow

Q27.

In a compact single dimensional array representation for lower triangular matrices (i.e all the elements above the diagonal are zero) of size n \times n, non-zero elements, (i.e elements of 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:
GateOverflow

Q28.

The average number of key comparisons required for a successful search for sequential search on n items is
GateOverflow

Q29.

B+ Trees are considered BALANCED because
GateOverflow

Q30.

With reference to the B+ tree index of order 1 shown below, the minimum number of nodes (including the Root node) that must be fetched in order to satisfy the following query: "Get all records with a search key greater than or equal to 7 and less than 15" is ____________.
GateOverflow