Data Structures - Jun 2015

Computer Engineering (Semester 3)

TOTAL MARKS: 100
TOTAL TIME: 3 HOURS (1) Question 1 is compulsory.
(2) Attempt any four from the remaining questions.
(3) Assume data wherever required.
(4) Figures to the right indicate full marks. 1 (a) Write a "C" program for insertion sort and discuss its efficiency.(7 marks) 1 (b) Briefly explain various linear and non-linear data structures along with their applications.(7 marks) 2 (a) Write "C" functions to: (1) insert a node at the end (2) delete a node from the beginning of a doubly linked list.(7 marks)

Answer any one question from Q2 (b) & Q2 (c)

2 (b) Write an algorithm to reverse a string of characters using stack.(7 marks) 2 (c) Compare: (1) Linked-list and Array (2) Circular queue and Simple Queue.(7 marks)

Answer any two question from Q3 (a), (b) & Q3 (c), (d)

3 (a) Convert (A + B) * C - D ^ E ^ (F * G) infix expression into prefix format showing stack status after every step in tabular form.(7 marks) 3 (b) Write an algorithm to implement insert and delete operations in a simple queue.(7 marks) 3 (c) Describe: (1) Recursion (2) Priority Queue (3) Tower of Hanoi(7 marks) 3 (d) Write "C" functions to: (1) insert a node at beginning in singly linked list (2) insert an element in circular queue.(7 marks)

Answer any two question from Q4 (a), (b) & Q4 (c), (b)

4 (a) With figure, explain the following terms: (1) Depth of a tree (2) Sibling nodes (3) Strictly binary tree (4) Ancestor nodes (5) Graph (6) Minimum spanning tree (7) Degree of a vertex(7 marks) 4 (b) Generate a binary search tree for following numbers and perform in-order and post-order traversals: 50, 40, 80, 20, 0, 30, 10, 90, 60, 70.(7 marks) 4 (c) Explain Right-in-threaded, left-in-threaded and full-in-threaded binary trees.(7 marks) 4 (d) Write Kruskal's algorithm for minimum spanning tree and explain with an example.(7 marks)

Answer any two question from Q5(a), (b) & Q5 (c), (d)

5 (a) Describe various collision resolution techniques in hashing.(7 marks) 5 (b) Write an algorithm for binary search method and discuss its efficiency.(7 marks) 5 (c) Explain Sequential, Indexed Sequential and Random file organizations.(7 marks) 5 (d) Write recursive "C" functions for (1) in-order (2) pre-order and (3) post-order traversals of binary search tree.(7 marks)