Download DU (University of Delhi) B-Tech (Bachelor of Technology) 2nd Semester 7802 Data Structures Question Paper
.
v
v [This question paper contains 4 printed pages.]
. Sr. No. onuestion Paper : 7802 F?2 Your Roll No ................
' Unique Paper Code : 2341202
v
Name ofthe Course : B.Tech. Computer Science
v
_ Name of the Paper : Data Structures [DC?1.4]
v Semester : II
' Duration : 3 Hours > Maximum Marks : 75
v
v Instructions for Candidates
' 1. Write your Roll No. on the top immediately on receipt of this question paper.
' 2 Question 1 is compulsory.
" 3. Attempt any four questions out of the remaining Q2?Q7.
' 4 Parts of a question must be answered together.
v
'i \
.1: 1 (a) A tridiagonal matrix D of dimension n x n has all non-zero entries on the
_ three central diagonals. Suppose this matrix is mapped to a one dimensional
. array A by diagonals, starting with the lowest diagonal. Obtain the formula
for the location of an element D(i, j) in A. (3)
(b) Differentiate between arrays and linked lists. (3)
(c) How many exchanges will occur during the ?rst pass, if the following array
is sorted using bubble sort ?
23, 43, 56, 12, 87, 14, 86 (3)
(d) Give the pre?x form for the folldwing in?x expression
VL.J_I~J_J_I_1__!_I_!._L
((A+B)*C?(D-E))"(F+G) (3)
P.T.0.
v?vvvvv'v'vv-vv'vvvvpvvvv'v
v
-
v 7802 2
v (6) Draw possible binary trees with three nodes A, B, and C such that their
' post-order traversal is B-A-C. (3)
V (0 Consider the following recursive function :
' int func(int m, int n)
v
{ if (m < n) return 0;
?
_ else
V return 1 + func(m-n, n); }
' What is the value of func(6, 3) based on the code above ? (3)
v
- (g) Take an initially empty hash table with eight slots, with hash function
h(x) = x mod 8, and with collisions resolved by linear probing, put the
' following data into the correct slot :
'1
i 16, 36, 28, 72, 34, 50 (3)
v
w (h) Draw a binary search tree for the following sequence :
'i 50, 20, 30, 60, 65, 55, 80, 15, 8, 35, 70 (3)
v
(i) Write a C++ function for binary search. (3)
v
v (j) What is a B-tree ? How is it different from a B+ tree ? (3)
v
(k) Write a C++ function to reverse a singly linked list of integers in one pass
' of the list. (5)
v
v 2. (a) Write a C++ program to reverse the order of elements in a stack using one
' additional queue. (6)
V (b) Show the contents of the stack while evaluating the following post?x
' expression :?
V B AC + X CAB ? + X where B=5, A=6, C=4. (4)
v.
v
'\
v
v
v
-
_ 7802 3
v 3. (3) Give template class de?nition for a doubly linked list. Write a member function
to delete all odd numbered nodes from this linked list. (2+4)
v
V (b) Give the formula and calculate the address of the element A[3][6] ofthe 2D
v Array de?ned as int A[7][7], ifthe elements are stored in
v (i) row major order
v
(ii) column major order
v
v The beginning address of the array is 200. Every element requires 4 bytes
. of storage. (4)
-,
v 4. (a) What are self-organizing lists ? For a given sequence ABCDBBCADD,
show the list after each step using (1) Move to Front and (ii) Count
v
method. (1+5)
v
v (b) Write a recursive function to calculate the length of a linked list. (4)
v
i 5. (a) Write C++ functions to perform the following on a binary tree (3+3)
' ? Counting the no. of right children
'
- Calculating height of the tree
(b) Draw the tree corresponding to the following traversals
Preorder traversal : J C A E G F M R
Inorder traversal : A C E F G J M R (4)
(a) Write an algorithm that determines whether a binary tree is complete or
not. - (6)
' (b) Brie?y explain any two methods for hash function. (4)
P. I 0.
14444444444al
a
l
v?vvvvvvvvvvvvvvvvvvvvvvvvv
V
v
7802 4
v
v 7. (a) Build a B tree of order 5 by inserting the following keys :?
v 9,14, 3, 16,4,1, 17, 6, 5,28
- Show the B tree diagrammatically after each key insertion. (6)
U
?- (b) Sort the following array using insertion sort :?
" 12,14, 11,16, 7, 8
v
. Show the contents of the array at every step. (4)
v
?
'
v
v,
v
'1
vi
.
'5
'1
'
v
v
w
V
c
v ,
v
v (2000)
u
"1
'1 ,
(r
1
1
1
This post was last modified on 31 January 2020