43 June 2022 307/3¢N) DATA STRUCTURES Time Allowed: 3 Hours Full Marks: 60 Answer the following questions from Group-A, B & Cas directed. GROUP-A 1, Choose the correct altemative (Any 10) 1x 10-10 i) Which data structure is defined as a collection of similar data elements? a) Arrays b) Structs c) Trees 4) Graphs. if) Which function places an element on the stack? a) Pop b)Push c) Peek d) isEmpty. iii) How do you initialize an amay in C? a) im anf3]_ = (12,3); by) int arr(3) = {1,2,3}; ¢) int arr[3] = {1,2,3};d) int arr(3) = (1,2,3); iv) Reverse polish notation is the other namé of a) Infix expression) Prefix Expression ¢) Postfix expression d) None of these. ¥) A normal queue, if implemented using an array of size MAX SIZE, gets full when- a) Rear = MAX_SIZE ~ 1 b) Front = (rear + I)mod MAX_ SIZE c) Front = rear+ | d) Rear = front vi) What is the value of the postfix expression 6 3 24 +~*? a) 1 b) 40 ¢) 74 d)-18, vii) What is the maximum number of swaps that can be performed in the Selection Sort algorithm for “n’ number of elements? a) n-1b)n c) 1 d) n° viii). If TOP=MAX-1, then the stack is a) full b) empty c) contains some data d) none of these ix) Which of the following traversal outputs the data in sorted order in a BST? A) Preorder b) Inorder ©) Postorder d) Level order x) An array consists of n elements. We want to create a heap using the elements. The time complexity of building a heap will be in order of_a) O(n*n*logn)b) O(n*logn) c) O(n*n) d) O(n *logn *logn) xi) Pushing an element into a stack already having five elements and a stack size of 5, then the stack becomes a) Overflow, b) Crash, ¢) Underflow, d) User flow xii) In the given connected graph G, what is the value of rad(G) and diam(G)? a) 3, 2b) 2, 2.¢) 3, 3d) 2,3 2. Fill in the blanks (any ten): 1x 10=10 i) A tree is data structure, ii) The clrscr() function is kept in header file. iii) A tree node that has no children is called a node iv) Breaking a program into several functions is called v) The #define pi 3.14 is a statement. vvi) Adding an element in a queue is called __ operation, vi) The pointer without a data type is viii) A loop inside another loop is called ix) stores the non-homogeneous data elements 1x) Process of removing an element from stack is called xi) Circular Queue is also known as . xii) In the stack, if a user tries to remove an element from the empty stack, then it called : xiii) The complexity to delete a node from the end of the linked list is --— xiv) is the logical container of a data item. xv) The height of a binary tree is the maximum number of edges in any root to leaf path. The maximum ‘number of nodes in a binary tree of height h is é xvi) The malloc function returns ‘when the allocation fails. 3. Answer the following questions (any ten) : 1x 10-10 i) What is FIFO? i) What is a leaf node? What is BST? iv) Memory space for an array is allocated in compile-time or in run time? v) Define De-Queue? vi) What is Backtracking? vii) Explain about dummy header. viii) Write the method of Bubble sort ix) What is the difference between a PUSH and a POP? x) What is a degree of a node of a tree? xxi) Write the full form of MST. xii) What are the disadvantages of linked list? xiii) Define queue full condition. xiv) What is rear of a queue?. GROUP -B 4, Answer the questions (any six) 2x6=12, i) What is complete binary tree? i) Write prefix form of the expression: (A+B*C)-(D/E) ‘What do you understand by radix sort? iv) Write two applications of queue. ¥) 10, 5, 1, 7, 40, 50 is given preorder traversal of a binary search tree. Find out the post-order traversal of the same tree? vi) What is doubly linked list? vi) What is hasing? viii) What is quick sort? ix) What sparx matrix? x) Give infix notation with an example. xi) What do you understand by stack underflow and stack overflow? xii) What is collision resolution technique? GROUP -C 5, Answer the question (any one): 6x1 a) What is Data Structure? Write down the differences between linear and nonlinear Data Structures? b) What is ADT? Explain with a suitable example. ©) Define a graph. Explain different representation of graph. 6. Answer the question (any one): xl 1) Explain Priority queue and its types. What will be the value of A (1,5) by using Ackerman function. b) Write an algorithm to insert a node in an AVL tree. 2©) Given the Pre-order and In-order traversal of binary tree. Draw the tree representation and write its Post-order traversal- Preorder: A Bo DI 2 0 1 '@s FE .- Gumy & In-order: apo By. Bead A ok. eG. OR: AG oxi 7. Answer the question (any one): ) Write pseudocode to implement a circular queue using an array }b) Explain the Polynomial equation of linked list: 3x'+ 2x*- 5x +2=0 ©) Write a recursive algorithm for binary tree traversal with an example.