## 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)