## Data Structures - Dec 2016

### 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)** Primitive data structure(1 marks)
**1(b)** Non-primitive data structure(1 marks)
**1(c)** Linear data structure(1 marks)
**1(d)** Non-linear data structure(1 marks)
**1(e)** Recursion(1 marks)
**1(f)** Time complexity of an algorithm(1 marks)
**1(g)** Double-ended queue(1 marks)
**1(h)** Priority queue(1 marks)
**1(i)** Circular linked list(1 marks)
**1(j)** Complete binary tree(1 marks)
**11(k)** 2-3 tree(1 marks)
**12(l)** Minimum spanning tree(1 marks)
**13(m)** Degree of vertex(1 marks)
**14(n)** Hash collision(1 marks)
**2(a)** Write a pseudo-code for PUSH and POP operations of stack.(3 marks)
**2(b)** What is prefix notation? Convert the following infix expression into prefix. A+B_-C*D*E $ F $ G(4 marks)

### Solve any one question.Q2(c) &Q2(d)

**2(c)** Write an algorithm to perform various operations(insert, delete and display) for simple queue.(7 marks)
**2(d)** Write differences between simple queue and circular queue. Write an algorithm for insert and delete operations for circular queue.(7 marks)

### solve any one question Q.3(a,b,c) &Q4(a,b,c)

**3(a)** Convert the following infix expression into postfix. A + B -C * D * E $ F $ G(3 marks)
**3(b)** Write algorithm (s) to perform INSERT_FIRST ( to insert a node at the first position) and REVERSE_TRAVERSE ( to display the data in nodes in reverse order) operations in doubly linked list.(4 marks)
**3(c)** Write 'C' program to implement stack using linked list.(7 marks)
**4(a)** Enlist and briefly explain various application of stack.(3 marks)
**4(b)** Discuss various rehashing techniques.(4 marks)
**4(c)** Write 'C' functions to implement INSERT_FIRST(to insert a node at the fiirst position), DELETE_FIRST (to delete a node from the first position), DELETE_LAST( delete a node from the last position) and TRAVERSE(to display the data in nodes) operations in circular linked list(7 marks)

### solve any one question Q.5(a,b,c) &Q6(a,b,c)

**5(a)** Write an algorithm for Binary search method.(3 marks)
**5(b)** Write 'C' program for Bubble sort.(4 marks)
**5(c)** Sort the following numbers using i) Selection sort ii) Quick sort: 10 50 20 30 10(7 marks)
**6(a)** Wrie a 'C function for Selection sort.(3 marks)
**6(b)** Write an algorithm for Quick sort.(4 marks)
**6(c)** Explain Depth First Search and Breadth First Search in graphs with an exmaple.(7 marks)

### solve any one question Q.7(a,b,c) &Q8(a,b,c)

**7(a)** Draw a binary expression tree for the following and perform preorder traversal for the same: (A + B $ C) + (D + E * F)(3 marks)
**7(b)** Construct a binary search tree for the following and perform inorder and postorder traversals: 5 9 4 8 2 1 3 7 6(4 marks)
**7(c)** Write 'C' functions for: inserting a node, postorder traversal and counting total number of nodes for binary search tree.(7 marks)
**8(a)** ExplainAVL trees.(3 marks)
**8(b)** Consturct a binary search tree from the following traversals: Inorder: 3 4 5 6 7 9 17 20 22

Preorder: 9 4 3 6 5 7 17 22 20(4 marks)
**8(c)** Write Kruskal's algorithm for minimum spanning tree with an example.(7 marks)