Guru Nanak Dev University 2011 B.Sc Information Technology Data structures - Question Paper

2411


B.Sc.(Information Technology) Part-2

DATA STRUCTURES

Paper-6

[Time allowed:Three hours] [Maximum Marks:100]

Note:-Attempt any 5 ques. carry equal marks.

1. Differentiate binary search from linear search along with the
discussion on time complexities of both the algorithms in best,
avg. and worst cases. Write an algorithm for searching an
element using binary search. Also explain the procedure of
binary search by taking suitable example. 20


2. Write advantages and disadvantages(if any) of priority queues.
explain the memory representation of priority queues. Write'
an algorithm to insert and delete an alement from a priority
queue.20


3. (a) List out any 3 applications of linked list and any
3 advantages of double Ended linked list over singled
linked list.12

(b) describe recursion and discuss it using suitable example.
provide at lowest 3 differences ranging from iteration
and recursion.8


4. (a) explain 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 explain different kinds of linked lists. 8


5. (a) provided a Postfix Expression :12,7,3,-,/,2,1,5,+,*,+.
explain the procedure to translate this postfix expression
using STACK.10

(b) Write an algorithm for deletion of a node in the stored
linked list.10


6. (a) explain the memory representation of graphs. 10

(b) Write an algorithm for finding the shortest path ranging from
2 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

Earning:   Approval pending.