Data Structures And Algorithm Beginner Level Theory Question Paper – 1

Q1.

1. Define different types of Asymptotic notation with brief description. (3 marks)
2. Find the time complexity of the following codes (2 marks)

i.

void func(int n)
{
  int sum = 0;
  int product = 1;
  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < n; j++)
    {
      printf("%d , %d\n", i, j);
    }
  }
}

ii.

int function(int n)
{
  int i = 0;
  if (n <= 0)
  {
    return 0;
  }
  else
  {
    i = random(n - 1);
    printf("this\n");
    return function(i) + function(n - 1 - i);
  }
}

Q2.

1. Convert the following infix expression to postfix using stack. A+(BC-(D/E^F)G)*H (5 marks)
2. What is recursion? Write the algorithm to calculate n factorial. (5 marks)
3. “Tracking of local variables at run time” is the application of Stack or Queue? Justify your answer. (5 marks)

Q3.

1. What is the difference between direct and indirect recursion? (5 marks)
2. Why Stack Overflow error occurs in recursion? (5 marks)
3. In a circular queue, how do you increment the rear and front of the queue? Write the algorithm. (5 marks)

Q4.

1. Write the pseudo code to implement a queue using stack. (5 marks)
2. How are linked lists more efficient than arrays? Also mention the drawbacks of linked list (5 marks)
3. What would be the asymptotic time complexity to add a node at the end of singly linked list, if the pointer is initially pointing to the head of the list? Analyze your answer. (5 marks)

Q5.

1. Write a pseudo code for inserting an element in a doubly linked list at the random position. (6 marks)
2. What are the advantages of Circular Queue over normal Queue. (4 marks)
3. Write the algorithm that gives recursive solution to Tower of Hanoi problem. What is the number of moves required to solve Tower of Hanoi problem for k disks? (5 marks)