Data Structure I Practice Test 4

1. What will be the output of the following code?

#include <bits/stdc++.h> 
using namespace std; 
 
int func(int arr[], int s, int e) 
{
   if (s == e) 
	return 0; 
   if (arr[s] == 0) 
	return INT_MAX; 

int min = INT_MAX; 
for (int i = s + 1; i <= e && i <= s + arr[s]; i++) 
{ 
	int jumps = func(arr, i, e); 
	if(jumps != INT_MAX && jumps + 1 < min) 
		min = jumps + 1; 
} 
return min; 
}

int main() 
{ 
	int arr[] = {1, 3, 6, 3, 8, 5}; 
	int n = sizeof(arr)/sizeof(arr[0]); 
	cout << func(arr, 0, n-1); 
	return 0; 
} 

2. Are the below statements true about skiplists?
In a sorted set of elements skip lists can implement the below operations
i.given a element find closest element to the given value in the sorted set in O(logn)
ii.find the number of elements in the set whose values fall a given range in O(logn)

3. Which of the following method performs poorly when elements are accessed in sequential order?

4. What technique is used in Transpose method?

5. When array reversal and rotation is applied to the same array then the output produced will also be the same every time.

6. What is the space complexity of the code that uses merge sort for determining the number of inversions in an array?

7. Predefined function rotate() in C++ is available under which header file?

8. What datastructures can be used in implementing a free list?

9. What will be the output of the following code?

#include <bits/stdc++.h> 
using namespace std; 

void func(int arr[], int n) 
{  
	int count[n]; 
	memset(count, 0, sizeof(count)); 

	for (int i=n-2; i>=0; i--) 
	{ 
		if (arr[i] >= n - i - 1) 
			count[i]++; 

		for (int j=i+1; j < n-1 && j <= arr[i] + i; j++) 

			if (count[j] != -1) 
				count[i] += count[j]; 

		if (count[i] == 0) 
			count[i] = -1; 
	} 

	for (int i=0; i<n; i++) 
		cout << count[i] << " "; 
} 

int main() 
{ 
	int arr[] = {1, 3, 5, 8, 9}; 
	int n = sizeof(arr) / sizeof(arr[0]); 
	func(arr, n); 
	return 0; 
} 

10. The time complexity of the code that determines the number of inversions in an array using merge sort is lesser than that of the code that uses loops for the same purpose.