Data Structure Online Test

1. Given only a single array of size 10 and no other memory is available. Which of the following operation is not feasible to implement (Given only push and pop operation)?

2. Construct a binary tree using inorder and level order traversal given below.
Inorder Traversal: 3, 4, 2, 1, 5, 8, 9
Level Order Traversal: 1, 4, 5, 9, 8, 2, 3

3. When executing a sequence of Unions, a node of rank r must have at least 2^r descendants.

4. Consider the following piece of code in C++. What does the following code implement?

#include <iostream>   
using namespace std;
int main()
{
    int *arr_vla;
    int size;
    cout<<"Enter the size of variable length array: ";
    cin>>size;
    arr_vla = new int [size];
    for (int i = 0; i < size; i++)
    {
        cout<<"Enter the integers to be inserted in the variable length array: ";
        cin>>arr_vla[i];
    }
    for(int i = 0; i < size; i++)
    {
        cout<<arr_vla[i]<<"  ";
    }
    cout<<endl;
    return 0;
}

5. Consider the following algorithm to insert an element in a triply linked list.

insertelement(data)
{
    create a node with given data.
    if the linked list is empty
    {
        _____________
        _____________
    }
    if the given node is less than the head
    {
        link the nodes through address and adjust the tail
    }
    if the given node is not less than the head
    {
        if the given node is equal to the head
        {
            new node is inserted on top of the head    
        }
        else
        {
            traverse the linked list to find an element greater than the node and insert in front of the node     
        }   
    } 
}

Which of the following option is best suited to fill the blank?

6. If there are more than 1 topological sorting of a DAG is possible, which of the following is true.

7. Given the Node class implementation, select one of the following that correctly inserts a node at the tail of the list.

public class Node
{
	protected int data;
	protected Node prev;
	protected Node next;
	public Node(int data)
	{
		this.data = data;
		prev = null;
		next = null;
	}
	public Node(int data, Node prev, Node next)
	{
		this.data = data;
		this.prev = prev;
		this.next = next;
	}
	public int getData()
	{
		return data;
	}
	public void setData(int data)
	{
		this.data = data;
	}
	public Node getPrev()
	{
		return prev;
	}
	public void setPrev(Node prev)
	{
		this.prev = prev;
	}
	public Node getNext
	{
		return next;
	}
	public void setNext(Node next)
	{
		this.next = next;
	}
}
public class DLL
{
	protected Node head;
	protected Node tail;
	int length;
	public DLL()
	{
		head = new Node(Integer.MIN_VALUE,null,null);
		tail = new Node(Integer.MIN_VALUE,null,null);
		head.setNext(tail);
		length = 0;
	}
}

8. Which of the following is true for a Hash tree?

9. What is the time complexity of Uttkonen’s algorithm?

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

11. What is the number of words that can be formed from the given Directed Acyclic Word Graph?

12. If a Graph Structured Stack contains {1,2,3,4} {1,5,3,4} {1,6,7,4} and {8,9,7,4}, what would be the source and sink vertices of the DAC?

13. How many extra nodes are there in Full K-ary tree than complete K-ary tree?

14. Pushing an element into stack already having five elements and stack size of 5, then stack becomes ___________

15. Which of the following data clustering algorithm uses suffix tree in search engines?

16. All paths and cyclic graphs are bipartite graphs.

17. What is the space complexity of a linear queue having n elements?

18. What is a memory efficient double linked list?

19. Matrix A when multiplied with Matrix C gives the Identity matrix I, what is C?

20. For the given expression tree, write the correct postfix expression.

21. Which of the following is the correct function definition for quadratic probing?

22. What will be the auxiliary space complexity of the following code?

#include <bits/stdc++.h> 
using namespace std; 
void func1(int arr[], int n) 
{ 
	int k = arr[0], i; 
	for (i = 0; i < n - 1; i++) 
		arr[i] = arr[i + 1]; 

	arr[i] = k; 
} 

void func(int arr[], int d, int n) 
{ 
	for (int i = 0; i < d; i++) 
		func1(arr, n); 
} 

void printArray(int arr[], int n) 
{ 
	for (int i = 0; i < n; i++) 
		cout << arr[i] << " "; 
} 

int main() 
{ 
	int arr[] = { 1, 2, 3, 4, 5}; 
	int n = sizeof(arr) / sizeof(arr[0]); 

    int d = 3;
	func(arr, d, n); 
	printArray(arr, n); 

	return 0; 
} 

23. Which of the following techniques offer better cache performance?

24. Every Directed Acyclic Graph has at least one sink vertex.

25. Which of the following is not a disadvantage to the usage of array?

26. What will be the time complexity of the following code?

#include <bits/stdc++.h> 
using namespace std; 
void func(int arr[], int left, int right) 
{ 
    if (left >= right) 
    return; 
      
    int temp = arr[left];  
    arr[left] = arr[right]; 
    arr[right] = temp; 
      
    func(arr, left + 1, right - 1);  
}      

void printArray(int arr[], int size) 
{ 
    for (int i = 0; i < size; i++) 
    cout << arr[i] << " "; 
} 

int main() 
{ 
	int arr[] = {1,2,3,4}; 
	int n = sizeof(arr) / sizeof(arr[0]); 
	func(arr, 0, n-1); 
	printArray(arr, n); 
	return 0; 
} 

27. What is the time complexity for converting decimal to binary numbers?

28. What is the fundamental operation on leftist heap?

29. Given the pseudo code, state whether the function for merging of two heap is correct or not?

		mergeTree(p,q)
    		if p.root.value <= q.root.value
        	return p.addTree(q)
    		else
        	return q.addTree(p)

30. The roots of the elements of the subtrees are smaller than the root of the heap.

31. What is the condition for priority of a node in a treap?

32. Array is divided into two parts in ____________

33. Which of the following is a self - balancing binary search tree?

34. What is the time complexity for deleting the string to form a new string in the rope data structure?

35. What are different ways of implementing free lists and which is simple among them?

36. How many types of the merge are available in skew heaps?

37. What is the time complexity for finding a maximum and minimum integer in Van Emde Boas data structure?

38. In which of the following self - balancing binary search tree the recently accessed element can be accessed quickly?

39. What is the space complexity of the in-order traversal in the recursive fashion? (d is the tree depth and n is the number of nodes)

40. Is it true that splay trees have O(logn) amortized complexity ?

41. What is the condition for two elements arr[i] and arr[j] to form an inversion?

42. How many top trees are there in a tree with single vertex?

43. Can leaf node be called child node in a K-ary tree?

44. Which of the following are used as an internal operation in Top tree?

45. Can suffix tree be used in bioinformatics problems and solutions.

46. Select the appropriate code which reverses a word.

47. An error is thrown if the character ‘\n’ is pushed in to the character stack.

48. In the given figure, find ‘?’.

49. Suppose X is the starting symbol of the given grammar with the following transition rules. Compute the value of X as the root of the parse tree for the expression: 3 & 4 % 7.
X → X1 & B | B {X.value = X1.value + B.value, X.value = B.value}
B → B1 % D | D {B.value = B1.value * D.value, B.value = D.value}
D → num {D.value = num.value}

50. Elements in an array are accessed _____________