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:
- Write your Roll No. on the top immediately on receipt of this question paper.
- Question 1 is compulsory.
- Attempt any four questions out of the remaining Q2-Q7.
- Parts of a question must be answered together.
--- Content provided by FirstRanker.com ---
- (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 first pass, if the following array is sorted using bubble sort ? 23, 43, 56, 12, 87, 14, 86 (3)
- (d) Give the prefix form for the following infix expression (A+B)*C - (D-E)^(F+G) (3)
- (e) Draw possible binary trees with three nodes A, B, and C such that their post-order traversal is B-A-C. (3)
- (f) Consider the following recursive function :
What is the value of func(6, 3) based on the code above ? (3)
int func(int m, int n)
{ if (m < n) return 0;
else--- Content provided by FirstRanker.com ---
return 1 + func(m-n, n); } - (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)
- (h) Draw a binary search tree for the following sequence : 50, 20, 30, 60, 65, 55, 80, 15, 8, 35, 70 (3)
- (i) Write a C++ function for binary search. (3)
- (j) What is a B-tree ? How is it different from a B+ tree ? (3)
- (k) Write a C++ function to reverse a singly linked list of integers in one pass of the list. (6)
- (l) Write a C++ program to reverse the order of elements in a stack using one additional queue. (6)
- (m) Show the contents of the stack while evaluating the following postfix expression : BAC+ * CAB -+ * where B=5, A=6, C=4. (4)
--- Content provided by FirstRanker.com ---
--- Content provided by FirstRanker.com ---
--- Content provided by FirstRanker.com ---
- (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)
- (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)
- (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)
- (b) Write a recursive function to calculate the length of a linked list. (6)
--- Content provided by FirstRanker.com ---
- (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 (6)
- (a) Write an algorithm that determines whether a binary tree is complete or not. (6)
- (b) Briefly explain any two methods for hash function. (4)
--- Content provided by FirstRanker.com ---
A Firstranker's choice FirstRanker.com
- (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)
- (b) Sort the following array using insertion sort : 12, 14, 11, 16, 7, 8 Show the contents of the array at every step. (4)
--- Content provided by FirstRanker.com ---
This download link is referred from the post: MU-Mumbai University MCA Last 10 Years 2010-2020 Question Papers || University of Mumbai
--- Content provided by FirstRanker.com ---