🏫 National Institute of Technology Silchar
Click to view the Question Paper
| S.N. | Questions | Marks |
|---|---|---|
| 1(a) | What is a sparse matrix? | 2 |
| 1(b) | How do we represent the sparse matrixJ to save space? | 4 |
| 1(c) | Write a program to reverse an array. | 4 |
| 2(a) | Given a function roll(), which returns an unpredictable outcome of the rolling a die. It can return 1, 2, 3, 4, 5, or 6. Your task is to roll a die n times. Write a program to determine the frequencies of the outcome : 1, 2, 3, 4, 5, and 6. The example frequencies of the faces for N = 10000 are given below: Face 1: 1667 Face 2: 1660 Face 3: 1732 Face 4: 1697 Face 5: 1586 Face 6: 1658 Note: Assume roll() as a library function, so do not write the roll() function. Moreover, your solution should not take more than O(n) time complexity. | 5 |
| 2(b) | Given a singly linked list with N nodes. Write a program to reverse the given singly linked list. | 5 |
| 3(a) | What is the output of the following recursive function?#include <stdio.h> void foo(int n) { if(n>=1) { foo(n-1); printf("%d\t",n); foo(n-1); } } int main() { foo(4); return 0; } | 5 |
| 3(b) | Derive the time and space complexity of the above program. | 5 |
| 4(a) | Given the functions stack *create(int size), void push(stack *st), int pop(stack *st), int peek(stack *st), int isEmpty(stack *st). Write a program to implement a queue with the help of two stacks. Define the functions of the queue - enQueue() and deQueue() for the int data type using the given functions of stack. | 4 + 4 |
| 4(b) | What is the worst-case time complexity of each enQueue() and deQueue() function? | 5 |
| 5(a) | Write a program to implement inorder and preorder binary tree traversal without using recursion. | 5 |
| 5(b) | Construct a binary tree from inorder and preorder tree traversal where the inorder and preorder traversal are given as follows: Preorder: 20, 15, 10, 18, 17, 30, 25, 40, 35, 38, 50 Inorder: 10, 15, 17, 18, 20, 25, 30, 35, 38, 40, 50 | 5 |
| 6(b) | Solve the following recurrence relation: T(n) = T(9n/10) + T(n/10) + O(n) | 5 |
| 7(a) | Given a circular linked list containing int data type. Write a program to display the data of the circular linked list. | 5 |
| 7(b) | Write a program to insert at Kth position in the doubly linked list. | 5 |
| 8(a) | Write a program to multiply two matrices. | 5 |
| 8(b) | Construct the AVL Tree for the given sequence of nodes: Nodes: 21, 26, 30, 9, 4, 14, 28, 18, 15, 10, 2, 3, 7. Analyze the time and space complexity of AVL Tree operations. | 5 |
| 9(a) | When do we use insertion sort? | 2 |
| 9(b) | What sorting algorithm takes the least number of swaps? | 2 |
| 9(c) | Define a priority queue. | 2 |
| 9(d) | What is the time complexity to re-heapify a heap? | 2 |
| 9(e) | Why should we not use bubble sort? | 2 |
