Appearance

šŸ« National Institute of Technology Silchar

Click to view the Question Paper
Question Paper
All questions are compulsory.
QuestionDetailsMarksCO
1(a)Define Abstract Data Type (ADT) with an example.2CO1
1(b)Solve the following recurrence relation using the Master Theorem:
T(n) = 16T(n/4) + nĀ³		2CO1
1(c)Is 4Ā²āæ = O(2Ā²āæ)? Justify your answer.2CO1
1(d)Consider a row-major array A[15ā€¦40, 20ā€¦45], where one array element occupies one byte of storage in memory. If the starting address of array A is 1600, then what is the address of the element A[30][25]?2CO2
2(a)The following infix expression Q is converted to its equivalent postfix expression using a stack data structure.
Q: A + (B * C - (D / E ^ F) * G) * H
What are the elements of the stack after operand F is scanned during the conversion process?		3CO2
2(b)What is a well-defined recursive function?
Write a tail-recursive function to find the factorial of a given positive number.		1 + 2CO1
2(c) What is the output of the following function for a singly linked list with values 1 -> 2 -> 3 -> 4 -> 5 -> 6?
start is pointing to the first node.

void fun(struct node *start) {
    if (start->next == NULL) return;
    if (start->next->next != NULL)
        fun(start->next->next);
    printf("%d", start->data);
}
2CO2
3(a)Write an algorithm to insert an element in a single-headed Doubly Linked List (DLL) after a given node X.
What is the time complexity of this insertion?
Assume that the start (head) pointer points to the beginning of the DLL.		4 + 1CO3
3(b)What is a min-priority queue data structure?
Consider an array representation of a circular queue where FRONT and REAR are the usual terms used in queue data structure.
Write an algorithm to insert an element into the circular queue.		1 + 4CO3
3(c) Let a space-efficient data structure called twoStack is created by using only one linear array, which supports the following operations:
push1(int x) -> pushes x to the first stack.,
push2(int x) -> pushes x to the second stack.,
pop1() -> pops and element from first stack and return the popped element.,
pop2() -> pops and element from second stack and return the popped element..
Write an algorithm to implement the push() and pop() operations for twoStack. 		4CO3