This document contains instructions for a Data Structures examination consisting of 5 questions worth a total of 50 marks. The questions cover topics like time and space complexity analysis of algorithms, sparse matrices, stacks vs queues, linked lists, binary search trees, graph traversal, sorting techniques, heaps and binary trees. Students are required to attempt all questions demonstrating their understanding of the concepts through explanations, examples and solving problems related to implementing various data structures and analyzing algorithms.
This document contains instructions for a Data Structures examination consisting of 5 questions worth a total of 50 marks. The questions cover topics like time and space complexity analysis of algorithms, sparse matrices, stacks vs queues, linked lists, binary search trees, graph traversal, sorting techniques, heaps and binary trees. Students are required to attempt all questions demonstrating their understanding of the concepts through explanations, examples and solving problems related to implementing various data structures and analyzing algorithms.
This document contains instructions for a Data Structures examination consisting of 5 questions worth a total of 50 marks. The questions cover topics like time and space complexity analysis of algorithms, sparse matrices, stacks vs queues, linked lists, binary search trees, graph traversal, sorting techniques, heaps and binary trees. Students are required to attempt all questions demonstrating their understanding of the concepts through explanations, examples and solving problems related to implementing various data structures and analyzing algorithms.
This document contains instructions for a Data Structures examination consisting of 5 questions worth a total of 50 marks. The questions cover topics like time and space complexity analysis of algorithms, sparse matrices, stacks vs queues, linked lists, binary search trees, graph traversal, sorting techniques, heaps and binary trees. Students are required to attempt all questions demonstrating their understanding of the concepts through explanations, examples and solving problems related to implementing various data structures and analyzing algorithms.
CLASS: B. TECH SEMESTER: V BRANCH: ECE/EEE/BT/CP&P/ME/PIE SESSION: MO/2022
SUBJECT: CS201 DATA STRUCTURES
TIME: 03 Hours FULL MARKS: 50
INSTRUCTIONS: 1. The question paper contains 5 questions each of 10 marks and total 50 marks. 2. Attempt all questions. 3. The missing data, if any, may be assumed suitably. 4. Tables/Data handbook/Graph paper etc., if applicable, will be supplied to the candidates -----------------------------------------------------------------------------------------------------------------------------
Q.1(a) Distinguish between time and space complexity? [CO-4, PO-1, BT-2] [2] Q.1(b) Explain sparse matrix? [CO-1, CO-5, PO-2, BT-3] [3] Q.1(c) Discuss the best case, worst case and average case time complexity of an algorithm with a [5] suitable example? [CO-2, PO-2, BT-4]
Q.2(a) Differentiate between stack and queue? [CO-1, CO-2, PO-2, BT-2] [2] Q.2(b) Given an array A [ ] of size N, write an algorithm to reverse the array using stack? [3] [CO-2, CO-3, PO-3, BT-3] Q.2(c) Discuss the Mazing problem? [CO-3, PO-3, BT-3] [5]
Q.3(a) Give the advantages of a circular linked list? [CO-3, PO-3, BT-3] [2] Q.3(b) Write an algorithm to delete the last node from a singly linked list? [CO-2, CO-3, PO-4, BT-4] [3] Q.3(c) Discuss why is a doubly linked list more useful than a singly linked list? [CO-2, PO-3, BT-3] [5]
Q.4(a) How does the height of a binary search tree effect its performance?[CO-1, CO-4, PO-4, BT-4] [2] Q.4(b) Explain depth first search traversal method of a graph? [CO-5, PO-4, BT-3] [3] Q.4(c) Construct a binary tree from the given in-order and pre-order traversal: in-order traversal: [5] {Q, B, K, C, F, A, G, P, E, D, H, R} pre-order traversal: {G, B, Q, A, C, K, F, P, D, E, R, H} [CO-3, PO-4, BT-4]
Q.5(a) What is the difference between internal sorting and external sorting? [CO-4, PO-1, BT-3] [2] Q.5(b) Differentiate between sequential search and binary search? [CO-1, CO-4, PO-3, BT-4] [3] Q.5(c) Construct a heap (H) from the given set of numbers: 33, 42, 67, 23, 44, 49 and 74. Also, [5] while constructing, draw the memory representation of the heap? [CO-3, CO-4, PO-3, BT-4]
