Data Structures 2018 Question Paper — Government College of Engineeri…

The 2018 Data Structures previous year question paper (Government College of Engineering and Technology, Jammu), with every question and its marks.

Instructions

Attempt five questions in all selecting at least two questions from each Section.
Each question carries 20 marks.

Q1. (a) Define Big O notation and what is its utility in analysis of algorithms? What is worst case and average case analysis? (b) Compare and contrast Recursion with Iteration. Giving an example discuss the implementation of recursion. (c) What is Sparse Matrices? How are they represented in memory? (d) Write a short note on Garbage Collection. [20 marks]
Q2. (a) Explain stack data structure along with various operations that can be applied on it. Also discuss various applications of stacks. (b) Write an algorithm to check the parenthesis validity in mathematical expression. [20 marks]
Q3. (a) Write algorithms to implement Queues using Linked list. What are the advantages of implementing queues using linked list in comparison to its implementation using arrays. (b) Write algorithms for: (i) Reverse the liner linked list (ii) Delete all nodes in a doubly linked list having odd number in its information part. [20 marks]
Q4. (a) Given pointers L 1 and L 2 of two sorted singly linked lists of integers. The lists may have some common elements. Write an algorithm to create a new sorted singly linked list 1, consisting the elements of L1 U L2 ( L1 union L2 ). (b) What are the problems of a circular link list? Specify the appropriate data structure which can overcome the above problems. Using the above data structure, write a routine which inserts a node with information field x to the right of node p. [20 marks]

Q5. (a) How a node can be added and deleted from a Binary Search tree? Explain the methods. (b) Write an algorithm for Inorder traversal of a Binary tree using stacks. [20 marks]
Q6. Write algorithms for following: (i) Count the number of leaf nodes in a Binary tree. (ii) Set a node as right child of a Threaded Binary tree. (iii) Depth first traversal of a Graph. (iv) Search an element in a Binary search tree. [20 marks]
Q7. (a) Write an algorithm to sort a list of numbers using Shell Sort. How it is different from Insertion sort? Also explain the algorithm to sort the following list of numbers: 25, 57, 48, 37, 12, 92, 86, 33, 100, 7, 66 (b) Explain Radix Sort with an example. [20 marks]
Q8. (a) Define following and give examples: (i) AVL Trees (ii) Minimum Cost Spanning Tree (iii) Threaded Binary trees (iv) Complete Binary tree (v) Binary Search tree. (b) Explain the Linked representation of graph with example. [20 marks]