Guru Nanak Dev University Data Structures 2011 Question Paper

Guru Nanak Dev University
B.Sc Information Technology
Data Structures
2011 Question Paper
Time:3 Hrs
Minimum Marks: 100.
Note:-Attempt any FIVE questions carry equal marks.
1. Differentiate binary search from linear search along with the discussion on time complexities of both the algorithms in best, average and worst cases. Write an algorithm for searching an element using binary search. Also discuss the procedure of binary search by taking suitable example. 20
2. Write advantages and disadvantages(if any) of priority queues Discuss the memory representation of priority queues. Write' an algorithm to insert and delete an element from a priority queue. 20
3. (a) List out any three applications of linked list and any three advantages of double Ended linked list over singled linked list. 12
(b) Define recursion and explain it using suitable example.
Give at least three differences between iteration and recursion. 8
4. (a) Discuss the representation of 3-dimensional array in memory with the help of suitable example. 6
(b) Construct a binary tree for: ((6+(3-2)*5)^2+3). 6
(c) Briefly discuss various types of linked lists. 8
5. (a) Given a Postfix Expression :12,7,3,-,/,2,1,5,+,*,+.
Discuss the procedure to translate this post-fix expression using STACK. 10
(b) Write an algorithm for deletion of a node in the stored linked list. 10
6. (a) Discuss the memory representation of graphs. 10
(b) Write an algorithm for finding the shortest path between two nodes of a graph. 10
7. What is binary search tree? Write an algorithm for deletion of a node from binary search tree. 20
8. Write short notes on the following:
(a) Bubble Sort
(b) Time and Space complexity
(c) Depth-first search. 20 

Share This