West Bengal Institute of Technology (WBIT) 2009-3rd Sem B.C.A Computer Application - 302 Data Structure with C ( ) - Question Paper
V\
Name :.....................................................................
Roll No. :................................................................. 7
Invigilators Signature :...............................................
CS / BCA/ SEM-3 / BCA-302/2009-10 2009
Time Allotted : 3 Hours Pull Marks : 70
The figures in the margin indicatefull marks.
Candidates are required to give their answers in their own words
as far as practicable.
GROUP.-A ( Multiple Choice Type Questions )
iv) Complexity of binary searching is
a) O ( n )
b) O (log n ) d) 0(1).
c) O(nlogn)
v) Complexity expressed in O-notation is
a) lower bound
b) upper bound
c) middle between (a) & (b)
d) none of these.
vi) The height difference of any node in an AVL tree is
b) -2,0,1
a) -1,0,1
d) -1,0,2.
c) - 2, 0, 2
vii) Post:order traversal is used for traversing
a) Graph
b) Doubly-circular linked list .
c) D-queue
d) Tree.
viii) Using DFS we can traverse
a) tree b) graph
c) none of these d) both (a) & (b).
ix) When the malloc () function returns null value it means
a) memory is not allocated
b) memory is allocated but no data entered
c) both (a) & (b)
d) none of these.
x) When an element is inserted in queue, the position of font
a) increments b) decrements
c) unchanged d) none of these.
GROUP -B (Short Answer Type Questions )
Answer, any three of the following. 3x5= 15
2. What are B tree and B+ tree ? Give the difference between them.
3. Convert the following into postfix : a + b x c $ d ( e -/ x g ) / h.
4. Write an algorithm to add two polynomials.
5. What is hashing ? Briefly explain different commonly used hash functions.
6. Write a short note on AVL tree.
GROUP-C (Long Answer Type Questions)
Answer any three of the following. 3 x 15 = 45
7. Write short notes on any three of the following : 3x5
a) ADT
b) DEQUE
c) Threaded binary tree
d) Circular queue. /
8. a) Write a function to delete any node from a binary search
tree. 10
b) Give the advantages of using linked list over array. 5
9. a) Explain with an example the heap sort algorithm. 5
b) Write an algorithm for this heap sort. 5
c) Find the time complexity of the above algorithm. 5
10. Write the functions for the following : 3x5
a) Insert a node after a particular node in single linked list.
b) Reverse display of the list in doubly linked list.
c) Physically reverse the single linked list.
j
11. a) What is an adjacency matrix representation of a
graph ? 5
b) Prove that maximum number of nodes on level I of a binary tree is 2~l,lsi. 3
c) What is the difference between recursion and iteration ?
2
d) What will be the complexity for the following operations ?
Quick sort, Binary search, selection sort. 5
33525 4
|
Attachment: |
| Earning: Approval pending. |
