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_-CDE $ 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)