Download DU (University of Delhi) B-Tech 2nd Semester 7802 Data Structures Question Paper

A Firstranker's choice FirstRanker.com

[This question paper contains 4 printed pages.]

Sr. No. of Question Paper : 7802

--- Content provided by FirstRanker.com ---

Unique Paper Code : 2341202

Name of the Course : B.Tech. Computer Science

Name of the Paper : Data Structures [DC—1.4]

Semester : 3

Duration : 3 Hours

--- Content provided by FirstRanker.com ---

Maximum Marks : 75

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.

--- Content provided by FirstRanker.com ---

4. Parts of a question must be answered together.

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)
2. (b) Differentiate between arrays and linked lists. (3)
3. (c) How many exchanges will occur during the first pass, if the following array is sorted using bubble sort ? 23, 43, 56, 12, 87, 14, 86 (3)
4. (d) Give the prefix form for the following infix expression (A+B)*C - (D-E)^(F+G) (3)

--- Content provided by FirstRanker.com ---

5. (e) Draw possible binary trees with three nodes A, B, and C such that their post-order traversal is B-A-C. (3)
6. (f) Consider the following recursive function :

   
   int func(int m, int n)
   { if (m < n) return 0;
   else
   --- Content provided by FirstRanker.com ---
   return 1 + func(m-n, n); }
   

   What is the value of func(6, 3) based on the code above ? (3)
7. (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 : 16, 36, 28, 72, 34, 50 (3)
8. (h) Draw a binary search tree for the following sequence : 50, 20, 30, 60, 65, 55, 80, 15, 8, 35, 70 (3)
9. (i) Write a C++ function for binary search. (3)

--- Content provided by FirstRanker.com ---

10. (j) What is a B-tree ? How is it different from a B+ tree ? (3)
11. (k) Write a C++ function to reverse a singly linked list of integers in one pass of the list. (6)
12. (l) Write a C++ program to reverse the order of elements in a stack using one additional queue. (6)
13. (m) Show the contents of the stack while evaluating the following postfix expression : BAC+ * CAB -+ * where B=5, A=6, C=4. (4)

FirstRanker.com

--- Content provided by FirstRanker.com ---

2. (a) Give template class definition for a doubly linked list. Write a member function to delete all odd numbered nodes from this linked list. (2+4)
3. (b) Give the formula and calculate the address of the element A[3][6] of the 2D Array defined as int A[7][7], if the elements are stored in (i) row major order (ii) column major order The beginning address of the array is 200. Every element requires 4 bytes of storage. (6)

FirstRanker.com

3. (a) What are self-organizing lists ? For a given sequence ABCDBBCADD, show the list after each step using (i) Move to Front and (ii) Count method. (1+5)
4. (b) Write a recursive function to calculate the length of a linked list. (6)

--- Content provided by FirstRanker.com ---

4. (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
5. (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 (6)

5. (a) Write an algorithm that determines whether a binary tree is complete or not. (6)

--- Content provided by FirstRanker.com ---

6. (b) Briefly explain any two methods for hash function. (4)

A Firstranker's choice FirstRanker.com

7. (a) Build a B tree of order 5 by inserting the following keys : 9, 14, 3, 16, 4, 1, 19, 96, 5, 28 Show the B tree diagrammatically after each key insertion. (6)
8. (b) Sort the following array using insertion sort : 12, 14, 11, 16, 7, 8 Show the contents of the array at every step. (4)

FirstRanker.com

--- Content provided by FirstRanker.com ---