29.0. 30. 3ha 3a Pe tott strate the bubble sort technique forthe given data and write the pseudo code and mention its worst case time complexity ‘3 S4 8 57 12 27 73 ‘Waite an pseudo code to insert a node *74” atthe beginning, at any position and atthe end of the single linked list. Give 2 pictorial representation of single linked lst before and aftr insertion. 2 1% 33 47 2 (or) ‘Write the pseudo code for inserting an element in the beginning of an array and for traversing an array with examples, Convert the following expression from infix to postix. @ (a-b)*(e-d)-(ave) GD a-Gler(d%erfig)eh (oR) Write the pseudo code to insert and delete an element in @ circular queue with example ‘Construct a AVI tree and explain all the rotations with the given data 49 13-9 52 6 73 54 16 23 44 39 (oR) ). Construct the binary search ree using the following elements, 4539 56 12 35 78 32 10 89 82 Find in-order, pre-order and post-order traversal ofthe same tree ‘Describe the implementation of Dijikistra’s algorithm with an example. (oR) What is hashing? Explain in detail about mid-quare method and modulo- division method with example. EEE [rene | B.Tech, DEGREE EXAMINATION, JUNE 2023 ‘Third & Fourth Semester ISCSC2013- DATA STRUCTURES AND ALGORITHMS (Por the candidates admited ering he academic year 2018-2019 to 2021-2022) PART A (@20x1=20 Marks) ‘Answer ALL Questions 1, Whats te best case time complexity ofthe insertion sort algorithm? ) 0@) ®) O(alogn) © oO ®) 0@) 2. In bubble sort, how many passes are required to sort ‘n’ elements in the ‘worst case? (a) nd Ba © mt ©) ae 3. In linear search algorithm, what is the input data structure? (A) Array B) Linked list (©) Tre ©) Groph 4. Which ofthe following notations represents a lower bound on the running time of an algorithm? (A). Onnotation ®) Onnotation (©) y-notation 5. What isthe index ofthe first element in an aray in C? wo @1 ©- 2 6. What is a node in a linked list? (A) A pointer to the next node in (B) A pointer to the previous node the lst inthe list (C) A data structure that contains (D) A data structure that contains data and a pointer to the next data only rode in the ist 7. What isthe time complexity of searching for a node in linked list? @ 00) B) O(a) (©) O(ogn) (0) Of) Note: (Part A should be answered in OMR shot within fst 40 minutes and OMR shect should be handed ‘over thal iavigiatr at the end of 40® minute Part -B & Part-C should be answered it enswer booklet. ‘Time: 3 hours ‘Max. Marks: 100,12, 13 Patote ‘The sparse matrix triplet method is most efficient when ed (A) The matrix has very few non- (B) The matrix is symmetric zero elements (©) The mati is diagonal (D) The matrix is dense ‘What s the term used to describe the insertion operation on a queue? ia eae (A) Push (B) Engueve (©) Pop (D) Dequeve What happens when we try fo pop an element from an empty stack? Lagi aie (A) New value is retuned (B) A default values returned (©) The sack remains empty (D) The program crashes, ‘Which ofthe following is true about a priority queue? Mo bt sa (A) Itoperates on 8 FIFO principle (B) It operates on a LIFO principle (C) It stores element in a random (D) It orders clements based on onder their priority In. stack, if a user ties to remove an element from an empty stack itis 1 3 2 called (&) Under flow (B) Overftow (©) Empty collection (D) Garbage ‘The number of edges ftom the node tothe deepest leaf sealed of tz ad the tee, (A) Height (8) Depth (©) Length () Width each node has exactly zero or two children, called as road (A) Full binary tee (B) Halfbinary ree (©) Zero binary tree (D) Quarter binary tree Ina fall binary tee, ifthe number of internal nodes is I, then the number of! 2 4 2 nodes N are? (a) N-2L, @ N-L+1 (© NL (D) N-2L-1 ‘What is the salient feature about the inorder traversal of a binary search 12 4 2 tree? (A) Ie traverses in 2 non-increasing (B) It traverses in an increasing order order (©) It traverses ina random (D) It traverses based on priority of | fashion the node ‘A path that beigns and ends a the same node is bors (A) Cycle (@) Path (©) Degree () Link 18. 20, 21 2, 2 25, 26, 2, 28a. reesett ash tableis__. (A) A structure that maps values to (B) A structure that maps Keys to keys values (©) Astructure used for storage (D) A structure used to implement stack Load factors. (A). Average aay size (B) Average key size (©) Average chain length (D) Average hash table length Difikistra’s algorithm is used for which type of problems? (A) Shortest path problem in (B) Shortest path problem in ‘weighted graph. ‘unweighted graph (©) Longest path problem in (D) Longest path problem in ‘unweighted graph ‘weighted graph PART-B (x 4=20 Marks) Answer ANY FIVE Questions Distinguish the characteristics of Big Ob, Big Omega and theta notations. Analyze the time complexity of insertion sort Write an algorithm for deletion of an node atthe beginning of the single linked ls. For the given matrix, find the sparse triplet matrix and transpose it 0002 0100 0003 3000, Define dequeue. How its represented? What are the types of dequeue? Construct the binary search tree with following elements 47, 36,57, 10, 34, 73, 30, 9, 91, 96, 68, 82 Consider dhe graph given below and find the degree of each node, PART-C (Sx 12= 60 Marks) ‘Answer ALL Questions Ina given aray of 10 numbers the data 35 need tobe Found using near search algorithm. 48 10 17 28 33 45 35 91 97 Write the C program for the same. (oR)