Assignment 2 Data Structures (BCA3B) PDF

Assignment-2 Data Structures Department of UGCA-1915 Computer Application BCA-3rd Sem Max. Marks = 24...

Assignment-2 Data Structures Department of UGCA-1915 Computer Application BCA-3rd Sem Max. Marks = 24 Questions to be attempted Set 1: Attempt Q.No. 1,2,11,13,21,22,31,38, 44 Q. No. Roll No.: 2333747, 2333749, 2333750, 2333753, 2333759, CO 2333760, 2333761,2333762, 2333763, 2333765, 2333766, 2333769, 2333771, 2333772, 2333773,2333777, 2333779, 2333780, 2333782, 2333785, 2333791, 2333792, 2333799, 2333800, 2333809, 2333810, 2333816, 2333820, 2333821, 2333822, 2333823,2333825, 2333826, 2333828, 2333831, 2333834, 2333835, 2333840, 2333842,2333844, 2333848, 2333849, 2333850, 2333852, 2333853, 2333856, 2333857, 2333860, 2333861, 2333863, 2333864, 2342030 Set 2: Attempt Q.No. 4,6,15,16,24,25,34,39,45 Roll No.: 2333751, 2333754, 2333757, 2333758, 2333767, 2333781, 2333788,2333790, 2333797, 2333802, 2333803, 2333807, 2333819, 2333837, 2333839,2333843, 2333851, 2333854, 2342031 Set 3: Attempt Q.No.. 8,9,18,19,29,30,36,41,47 Roll No.: 2333778, 2333789, 2333814, 2333832 Section A (2 marks each) 1 Describe AVL tree and name its rotations. 2 Enumerate operations of Doubly linked list. 3 Why Balanced tree is used? 4 Draw double linked list of array A= [22,3,4,6,1,88,12]. 5 CO4 Delineate process of in-order traversing in Tree. 6 How parent node is different from root node? 7 What do we call a node if it has no children? Also explain connections between a node and a root. 8 Draw circular linked list of an array = [12,21,24,32,62,52,7]. 9 Draw binary search tree of elements 15,3,8,22,13,34,96,83. 10 Is tree a linear or nonlinear data structure? Write various operations performed on tree. 11 Differentiate complete and simple graph. 12 Enumerate various graphs in data structures? 13 Write various operations performed on Graph. 14 Define Adjacent Vertices. CO5 15 Write characteristics of an adjacent matrix. 16 Draw “Null Graph” and “Labeled Graph”. 17 Draw and define “Trivial Graph” and “Directed Graph”. 18 Why Dijkstra’s algorithm is used? 19 Define the term “Backtracking” used in Graphs. 20 Vertices (5): {A,B,C,D,E} Write order, edges and size of graph  21 What is Hashing? 22 Write best and worst time complexity of Linear search. 23 Explain Searching. How is it different from sorting? 24 Name the various algorithms used to find an element in an array. CO6 25 Highlight the term Collision in Hashing. 26 Why we use Hash Function? 27 Write down time complexity of Binary search algorithm. 28 How “Divide and Conquer” is helpful in Sorting. 29 Scrutinize Collision Resolution Techniques in Hashing. 30 What is sorting? Name sorting algorithms. Section B (4 marks each) 31 Explain AVL rotations in detail? Draw an AVL tree for the numbers 11, 18,12,8,4,17,5 Highlight the properties of Binary Search Tree. Step by step, draw a 32 binary search tree of elements from an array 45, 10, 7, 90, 12, 50, 13, 39, 57 Draw the B-tree of order t=3 and insert the following data as per 33 sequence. 92, 24, 6, 7, 11, 8, 22, 4, 5, 16, 19, 20, 78 Is linked list a linear or non-linear data structure? Write an algorithm 34 to insert an element “item” at position “pos” in a Linked List Draw a circular linked list of size 6. Add five elements 35 (22,33,44,55,66) to linked list. Delete two elements. Add three elements (77,88,99) elements to it. Highlight it front and rear value CO4 Using the following Tree, Traverse the tree in all various traversing ways 36  Write an algorithm of BFS. Using BFS algorithm, traverse all nodes of Graph from starting node “A” from following diagram: 37 Define term Traversing in Graphs? Name the various traversing 38 algorithms are used to traverse the graph. Explain any one traversing technique. Write an algorithm of DFS. Using DFS algorithm, traverse the Graph from starting node “A” from following diagram: 39 CO5 Write an algorithm of Dijkstra algorithm. Find the shortest path using the diagram from source node” A” to destination node” G”. 40 41 What do you mean by a Graph? Explain different types of graphs with diagram. 42 Explain Threaded Binary tree and its types. Define the term searching. Write an algorithm of linear search. Using 43 linear search algorithm, search an element “32” from an array a[]=[65,15,27,45,25,32,49,88]. How binary search differ from linear search? Using binary search 44 algorithm find the element “42” from an array a[]=[11, 20, 14, 42, 26, 27, 36, 47, 43, 32]. 45 Define the term sorting. Write an algorithm of Bubble sort. Sort an CO6 array a[]=[42,71,52,37,10] using Bubble sort algorithm. Using the Hashing technique, arrange the following four students 46 { “Raman”, “Namar”, “Manar”, “Ranam” }in an order, that there should be no collision between two or more students.  How merge sort is different selection sort ? sort an array 47 a[]=[38, 19, 15, 31, 26, 28, 35, 52, 64, 32] using Merge sort Algorithm. Find the collision state of following list 48 [ 1,2,8,11,15,22,28,35,36,42,47,51]. If collision occurs, resolve the collision.