B.Tech III (Third) Semester Examination 2015-16
Course Code: ECS305 Paper ID: 0963204
Data Structure Using C
Time: 3 Hours Max. Marks: 70 Max Marks: 75
Note: Attempt six questions in all. Q. No. 1 is compulsory.
1. Answer any five of the following (limit your answer in 50 words). (4x5=20)
a) What do you understand by big ‘O’ notation in a data structure?
b) A complete, undirected, weighted graph G is given on the vertex set {0,1, … , n-1} for any fixed ‘n’. Draw the minimum spanning tree of G if the weight of the edge (u, v) is |u-v|.
c) What is the complexity of extracting maximum element from heap?
d) What is difference between AVL tree and B tree?
e) Explain the memory addressing scheme for two dimensional array with suitable example.
f) What is difference between spanning trees and minimal cost spanning trees?
g) What are different operations done on strings? Explain with examples.
h) Write a ‘c’ code that will split a linked list into two linked lists so that successive nodes go to different lists.
2. Write the Dijikstra’s algorithm for finding shortest path with the help of suitable example. (10)
3. Write ‘C’ programme to create a queue as a linked representation. (10)
4. Explain circular queue and priority queue data structure in detail. Write a program to insert an element in circular queue. (10)
5. What do you understand by linked representation of a binary tree. Also define a ‘C’ structure of a such tree. (10)
6. Write a program to implement quick sort. Give comparative study of Insertion Sort, Bubble Sort and Quick Sort in terms of complexities for best, average and worst cases. (10)
7. The order of nodes of a Binary Tree in preorder and inorder traversal are as follows:
Preorder :3,5,7,10,9,4,17,16,20,18,15,14
Inorder: 3,4,5,7,9,10,14,15,16,17,18,20
Draw the corresponding Binary tree and write its postorder traversal. (10)
8. Write short notes on any two of the following: (5+5)
a) Minimum Cost Spanning Tree
b) Binary Search Tree (BST)
c) Garbage collection and compaction