GTU Computer Engineering (Semester 3)
Data Structures
December 2016
Total marks: --
Total time: --
INSTRUCTIONS
(1) Assume appropriate data and state your reasons
(2) Marks are given to the right of every question
(3) Draw neat diagrams wherever necessary


1(a) Primitive data structure
1 M
1(b) Non-primitive data structure
1 M
1(c) Linear data structure
1 M
1(d) Non-linear data structure
1 M
1(e) Recursion
1 M
1(f) Time complexity of an algorithm
1 M
1(g) Double-ended queue
1 M
1(h) Priority queue
1 M
1(i) Circular linked list
1 M
1(j) Complete binary tree
1 M

2(a) Write a pseudo-code for PUSH and POP operations of stack.
3 M
2(b) What is prefix notation? Convert the following infix expression into prefix. A+B_-C*D*E $ F $ G
4 M
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 M
2(d) Write differences between simple queue and circular queue. Write an algorithm for insert and delete operations for circular queue.
7 M

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 M
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 M
3(c) Write 'C' program to implement stack using linked list.
7 M

4(a) Enlist and briefly explain various application of stack.
3 M
4(b) Discuss various rehashing techniques.
4 M
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 M

solve any one question Q.5(a,b,c) &Q6(a,b,c)
5(a) Write an algorithm for Binary search method.
3 M
5(b) Write 'C' program for Bubble sort.
4 M
5(c) Sort the following numbers using i) Selection sort ii) Quick sort: 10 50 20 30 10
7 M

6(a) Wrie a 'C function for Selection sort.
3 M
6(b) Write an algorithm for Quick sort.
4 M
6(c) Explain Depth First Search and Breadth First Search in graphs with an exmaple.
7 M

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 M
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 M
7(c) Write 'C' functions for: inserting a node, postorder traversal and counting total number of nodes for binary search tree.
7 M

8(a) ExplainAVL trees.
3 M
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 M
8(c) Write Kruskal's algorithm for minimum spanning tree with an example.
7 M

11(k) 2-3 tree
1 M

12(l) Minimum spanning tree
1 M

13(m) Degree of vertex
1 M

14(n) Hash collision
1 M



More question papers from Data Structures
SPONSORED ADVERTISEMENTS