## Data Structures - Dec 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.

### Short Questions

**1(a)** Define data structure(1 marks)
**1(b)** List operations performed on a stack(1 marks)
**1(c)** Mention variations of the queue data structure.(1 marks)
**1(d)** What is the worst case time complexity of searching an element in a list? How?(1 marks)
**1(e)** Mention one operation for which use of doubly linked list is preferred over the singly linked list.(1 marks)
**1(f)** Write an algorithm/steps to traverse a singly linked list.(1 marks)
**1(g)** Define: Height of a tree.(1 marks)
**1(h)** What is the height of a complete binary with n nodes?(1 marks)
**1(i)** Write two simple hash functions.(1 marks)
**1(j)** What is a header node and what is its use?(1 marks)
**1(k)** Is Queue a priority queue? Justify(1 marks)
**1(l)** What is the complexity of binary search algorithm?(1 marks)
**1(m)** Name two divide and conquer algorithms for sorting(1 marks)
**1(n)** Give two applications of graphs.(1 marks)
**2(a)** Write an algorithm to check if an expression has balanced parenthesis using stack.(3 marks)
**2(b)** What is postfix notation? What are its advantages?
Convert the following infix expression to postfix. A$B-C*D+E$F/G(4 marks)

### Solved any one question from 2(c) & 2(d)

**2(c)** Write a C program to implement a stack with all necessary overflow and underflow checks using array.(7 marks)
**2(d)** Write a C program to implement a circular queue using array with all necessary overflow and underflow checks(7 marks)

### Solved any one question from Q.3 & Q.4

**3(a)** Evaluate the following postfix expression using a stack. Show the stack contents.

AB*CD$-EF/G/+ A=5, B=2, C=3, D=2, E=8, F=2, G=2(3 marks)
**3(b)** Perform following operations in a circular queue of length 4 and give the Front, Rear and Size of the queue
after each operation

1) Insert A, B

2) Insert C

3) Delete

4) Insert D

5) Insert E

6) Insert F

7) Delete(4 marks)
**3(c)** Write a program to insert and delete an element after a given node in a singly linked list.(7 marks)
**4(a)** Explain various applications of queue.(3 marks)
**4(b)** Differentiate between arrays and linked list(4 marks)
**4(c)** Create a doubly circularly linked list and write a function to traverse it(7 marks)

### Solved any one question from Q.5 & Q.6

**5(a)** Define complete binary tree and almost complete binary tree.(3 marks)
**5(b)** Explain deletion in an AVL tree with a suitable
Example(4 marks)
**5(c)** What is binary tree traversal? What are the various traversal methods? Explain any two with suitable example.(7 marks)
**6(a)** Mention the properties of a B-Tree.(3 marks)
**6(b)** Construct a binary tree from the traversals given below:

Inorder: 1, 10, 11, 12, 13, 14, 15, 17, 18, 21

Postorder: 1, 11, 12, 10, 14, 18, 21, 17, 15, 13(4 marks)
**6(c)** What is a binary search tree? Create a binary search tree for inserting the following data.

50, 45, 100, 25, 49, 120, 105, 46, 90, 95

Explain deletion in the above tree.(7 marks)

### Solved any one question from Q.7 & Q.8

**7(a)** Insert the following elements in a B-Tree.
a, g, f, b, k, c, h, n, j(3 marks)
**7(b)** Apply quicksort algorithm to sort the following data.
Justify the steps.

42, 29, 74, 11, 65, 58(4 marks)
**7(c)** What is hashing? What are the qualities of a good hash function? Explain any two hash functions in detail.(7 marks)
**8(a)** List advantages and disadvantages of Breadth First Search and Depth First Search.(3 marks)
**8(b)** What is a minimum spanning tree? Explain Kruskal's algorithm for finding a minimum spanning tree.(5 marks)
**8(c)** Discuss various methods to resolve hash collision with suitable examples.(7 marks)