Data Structures 2018 Question Paper — Government College of Engineeri…

Instructions

• Attempt five questions in all, selecting at least two questions from each section.

Questions

Section A

• Q1. (a). What do you mean by space complexity and time complexity of an algorithm ? Write and algorithm/pseudo code for linear search and mention the best case and worst case time complexity of Linear Search algorithm. [10 marks]
• Q(b). Compare array and linked list. State where they stand in context of speed, space, reliability, insertion, deletion and access operations. [10 marks]
• Q2. (a). Write algorithm for evaluating postfix expression. Explain the working of the algorithm to evaluate the following expression $623 + - 382/+ * 2 \$ 3 +$ ($is for exponent) [10 marks]
• Q(b). What are circular queues ? What advantage circular queues has over linear queues ? Discuss implementation of circular queues. [10 marks]
• Q3. (a). If you are to maintain the list of numbers in sorted order, which data structure you would prefer and why ? Write down an algorithm to maintain the list of numbers in sorted order using the data structure you preferred. [10 marks]
• Q(b). Distinguish between recursion and iteration. Explain the advantages and disadvantages of using the recursive formulation of the algorithm compared to non-recursive formulation. [5 marks]
• Q(c). What is sparse matrix ? Describe a data structure for the efficient storage of a sparse matrix. [5 marks]
• Q4. (a). Write algorithms for the following : 2×5=10 (i) Split the singly linked list at the middle and make the second half as the first and vice-versa. (ii) Delete all nodes from doubly linked list with value less than the value in the first node of the doubly linked list. [10 marks]
• Q(b). Write a short note on Dynamic Memory management and garbage collection. [10 marks]

Section B

• Q5. (a). What are threaded binary trees ? Write an algorithm for inserting a node in a threaded binary tree. [10 marks]
• Q(b). Define an AVL tree. Obtain an AVL tree by inserting one integer at a time in the following sequence : 150, 155, 160, 115, 110, 140, 120, 145, 130, 147, 170, 180. Show all the steps. [10 marks]
• Q6. (a). Create a binary search tree for the following numbers start from an empty binary search tree : 45, 26, 10, 60, 70, 30, 40. Delete keys 10, 60 and 45 one after the other and show the trees at each stage. [10 marks]
• Q(b). Write algorithm to sort list of numbers using Quick sort. Explain stepwise working of it for the following list of numbers : 15, 4, 3, 10, 8, 7, 13, 6, 12, 89, 40. Also write the time complexity of Quick sort in best and worst case. [10 marks]
• Q7.. Write an algorithm for : 4×5=20 (i) Find and display the largest and smallest value in a Binary Search Tree. (ii) Insert a node with new element in a Binary Search Tree. (iii) Count the number of leaf nodes in a Binary tree. (iv) To create a mirror image of a Binary tree. [20 marks]
• Q8. (a). Write Prim's algorithm to find Minimum Spanning Tree. [8 marks]
• Q(b). Find the Minimum spanning tree using Prim's algorithm for the given graph. Consider vertex V₁ as root. [7 marks]
• Q(c). Explain Dijkstra's single source shortest path algorithm with an example. [5 marks]

Related pages

• Data Structures syllabus
• All Data Structures papers from 2018

Other years

• Data Structures 2018 question paper — end-term
• Data Structures 2018 question paper — end-term