| 20134 y RAZZ1]0020 SRM Institute of Science ana ‘Technolo; ” 7 Department of Computer Science and Engineering B® Ss RM Delhi— Meerut Road, Sikri Kalan, Ghaziabad, Uttar Pradesh — 201204 mr nonce EES Academic Year: 2023-24 (ODD) Test + Internal Examination IL Date & Session: 24/09/2023/FN Course Code & Tith '1CSC201J/ Data Structures and Algorithms Duration: 2 Hours Year & Sem 1 IT Year/MI Sem Max. Marks: 60 Part-A (10 x 1=10 Marks) Answer All questions Q.No Question 1 Ina circular linked list, the last node's reference points to: a. The first node b. NULL, ¢. The previous node 4. A random node 2 When would you choose to use an array over a linked list? 14 2 2 a, When you need dynamic sizing b. When you need constant-time insertions and deletions . When you need fast random access to elements 4d. When you want to save memory 3 fan array is declared as arr{} = {1,3,5,7,9); then what is the value ofsizeoffarf32 1 3 2 2 (a)! (b)2 3 (a) 8 In the Josephus problem, ifn=7 and k=3, which person will be the last survivor? = 1 3-23 a) Ist person b) 3rd person ©) 4th person ) 7th person What is the time complexity of the Push and Pop operations in a typical stack implementation? 8) O(n) for Push and O(1) for Pop ') O(n) for both Push and Pop ©) O(1) for Push and O(n) for Pop 4) 0(1) for both Push and Pop 6 In postfix notation, how would you write the expression "3 +4 * 2" a)3424+ by3+42* 3442" a) 34442" If each move takes 2 seconds, the minimum time required to solve tower of hanoi 1 puzzle with 4 disks will be a) 15 seconds b) 30 seconds 6) 16 seconds ) 32 seconds 8 Which of the following is NOT a common application of a queue? Ieee siaits a) Task scheduling ») Breadth-first search in graphs ) Maintaining a history of actions f ) Recursive algorithms Marks BL CO PO 1 2 2 2 w10 ’ % 18 Ina deque, which end is typically referred to as the "front"? 2) The end where elements are added ‘b) The end where elements are removed 5) idepends on the specific implementation 8) A deque dossn't have a front ‘Which operation can be used to remove a node from the middle of a doubly linked list efficiently? 2) Delete )Remove 2) Erase 4)Pop Pat B Answer any Five questions Design algorithms Sor Inserfing and Deleting an element from a specified position nan Array. Consider the following polynomials: = 6x2 St + Da? “Show the addition process of above represented using Linked List. “Desoribe an algorithm 10 solve the Josepbus problem for a given number of people anda specific eliminations. Discuss the concept of 2 Doubly Linked List. What advantages does it offer over a 30+(7-3)+ 102 Draw the Circular Queue structure in each case when the following operations are ‘performed on an empty queue. (2) Add A,B, C,D,E,F () Delete tw leners ()AddG (6) Add (2)Delete four letters () Add I What is fhe significance of the "front" and "rear" pointers in a queue data structure? How are they used 1o manage elements in the queue? PartC Answer All questions (_(A) Explain the Insertion operation in Linked List. How nodes are inserted afier a specified node? (oR) () Design algorithms for Searching and Traversing operation in linked list strate with suitable examples. 319 eae Gmplemented by linked list? Discuss in detail with example. (or) “(B) Explain implementation of Queues using appropriate algorithms. age, ae ..-Bz 2 6M.x 5Q=30 Marks cua) oe 2 eos 2. 2 6.s 2 3 6 2 2 2 ies 6 3 3 3 6 2 2 10M x 2Q=20 Marks io 3 10 w 10 10, 2 3