GATE PYQ

Data Structure

Q1.
Let P be an array containing n integers. Let t be the lowest upper bound on the number of comparisons of the array elements, required to find the minimum and maximum values in an arbitrary array of n elements. Which one of the following choices is correct?

Q2.
What is the worst-case number of arithmetic operations performed by recursive binary search on a sorted array of size n?

Q3.
Consider a 2-dimensional array x with 10 rows and 4 columns, with each element storing a value equivalent to the product of row number and column number. The array is stored in row-major format. If the first element x[0][0] occupies the memory location with address 1000 and each element occupies only one memory location, which all locations (in decimal) will be holding a value of 10?

Q4.
If an array A contains the items 10, 4, 7, 23, 67, 12 and 5 in that order, what will be the resultant array A after third pass of insertion sort?

Q5.
An array A consists of n integers in locations A[0],A[1],...A[n-1]. It is required to shift the elements of the array cyclically to the left by k places, where 1 \leq k \leq (n-1). An incomplete algorithm for doing this in linear time, without using another array is given bellow. Complete the algorithm by filling in the blanks. min=n; i=0; while(_____) { temp= A[i]; j=i; while(_) { A[j]= _; j=(j+k) mod n; if(j < min) then min = j; } A[(n+i-k) mod n]=_; i=____; }

Q6.
A frame buffer array is addressed in row major order for a monitor with pixel locations starting from (0,0) and ending with (100,100). What is address of the pixel(6,10)? Assume one bit storage per pixel and starting pixel location is at 0.

Q7.
Suppose there are 11 items in sorted order in an array. How many searches are required on the average, if binary search is employed and all searches are successful in finding the item?

Q8.
Consider the following two C code segments. Y and X are one and two dimensional arrays of size n and nxn respectively, where 2\leq n\leq 10. Assume that in both code segments, elements of Y are initialized to 0 and each element X[i][j] of array X is initialized to i+j. Further assume that when stored in main memory all elements of X are in same main memory page frame. Code segment 1://initialize elements of Y to 0 //initialize elements X[i][j] of X to i+j for(i = 0; i < n; i++) Y[i] += X[0][i]; Code Segment 2: //initialize elements of Y to 0 //initialize elements X[i][j] of X to i+j for(i = 0; i < n; i++) Y[i] += X[i][0]; Which of the following statements is/are correct? S1: Final contents of array Y will be same in both code segments S2: Elements of array X accessed inside the for loop shown in code segment 1 are contiguous in main memory S3: Elements of array X accessed inside the for loop shown in code segment 2 are contiguous in main memory

Q9.
Let A be an array of 31 numbers consisting of sequence of 0's followed by a sequence of 1's. The problem is to find the smallest index i that A[i] is 1 by probing the minimum numbers of locations in A. The worst case number of probes performed by an optimal algorithm is _____________.

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