Data structure (utu) b tech que paper 2nd year

UTTARAKHAND TECHNICAL UNIVERSITY

B.TECH (SEM. 3RD) 

2011-2012

Sub: Data structure

time : 3hr]

Total marks :100

Note: Attempt all questions. Be precise in your answer.

SECTION A

Q1:- Attempt any four of the following :

4x5=20

1. Describe time and space complexity. Discuss best, average and worst case for finding a given number from an array of integers.
2. Explain the difference types of data structure. What data structure will you use to store the information of students of your class? Why?
3. Make a function in C which takes an array of names as input and return the number of palindromes in it.
4. Write a complete program in C to implement stack using liked list.
5. Write an algorithm to evaluate postfix expression. Convert the following infix expression into equivalent postfix expression.
   (a+b)  ͯ  c-d + e / (f-g) 
6. What is recurssion? What is the significance of using recursive function to print Fibonacci number up to the given number.

Q2:- Attempt any four of the following :

4x5=20

SECTION B

1. Write a function in C to reverse a given queue.
2. What is priority queue? How it is implemented? Take an example to show your implementation.
3. Devise function in C which check for Full and Empty for a circular queue. Also find out the number of elements in circular queue.
4. Write a program in C to find the given item in a single linked list. Also analyze the running time of your program.
5. Devise insertion and deletion function for doubly linked list.
6. Explain Garbage Collection and Compaction.

 Q3:- Attempt any two of the following :

10X2=20 

SECTION C

1. (a) Define a tree. Explain the difference type of binary tree. What is predecessor and successor         of node in a binary search tree?
   (b) Prove that the number of nodes n in a perfect binary tree can be found using this formula : n=2^h+1 - 1 where h is the height of the tree.
2. (a) Discuss the usage of threaded binary tree.
   (b) Show the working of Huffman algorithm.
3. Write a pseudo code for insertion and deletion in Binary Search Tree. Find out the running time of insertion and deletion in binary search Tree.

Q4:- Attempt any two of the following :

10X2=20 

SECTION D

1. Can we use Binary search technique everywhere? Justify your answer. Analyze best, average and worst case behavior of binary search. Shoe the steps of binary search for finding 28 in the given list of numbers.
   2, 7, 12, 15, 18, 20, 22, 26, 28, 30, 33, 36, 39, 40, 45, 50
2. What is Hash table? What is the purpose of using hash table is more beneficial as compared to its contemporary techniques.
3. Write pseudo code for heap sort. Analyze its running time. Perform heap sort on following list of integers.
   21, 1, 34, 28, 6, 85, 23, 17, 22, 80, 11, 2, 7, 25

Q5:- Attempt any two of the following :

10x2=20 

 SECTION E

1. How the files are organized on physical storage media? Explain in detail.
2. (a) Explain the organization of sequential file.
   (b) What is B+ tree? Explain its usage.
3. Write short notes on any two:
   (a) Indexing
   (b) Hashing
   (c) Indices.

--------------------utu previous year question papers of B.tech, Bba, B.com, B.sc and Mba old year question papers Uttarakhand technical University (UTU)-----------------------

Good luck !!!