# Data Structure Questions and Answers updated daily – Computer Knowledge

Data Structure Questions: Solved 242 Data Structure Questions and answers section with explanation for various online exam preparation, various interviews, Computer Knowledge Category online test. Category Questions section with detailed description, explanation will help you to master the topic.

## Data Structure Questions

221. Consider the following C function in which size is the number of elements in the array E:

The value returned by the function MyX is the

int MyX(int *E, unsigned int size)

{

int Y = 0;

int Z;

int i, j, k;

for (i = 0; i < size; i++)

Y = Y + E[i];

for (i = 0; i < size; i++)

for (j = i; j < size; j++)

{

Z = 0;

for (k = i; k <= j; k++)

Z = Z + E[k];

if (Z > Y)

Y = Z;

}

return Y;

}

The value returned by the function MyX is the

int MyX(int *E, unsigned int size)

{

int Y = 0;

int Z;

int i, j, k;

for (i = 0; i < size; i++)

Y = Y + E[i];

for (i = 0; i < size; i++)

for (j = i; j < size; j++)

{

Z = 0;

for (k = i; k <= j; k++)

Z = Z + E[k];

if (Z > Y)

Y = Z;

}

return Y;

}

SHOW ANSWER

Correct Ans:maximum possible sum of elements in any sub-array of array E.

Explanation:

The function does following

Y is used to store maximum sum seen so far and Z is used to store current sum

1) Initialize Y as sum of all elements

2) For every element, calculate sum of all subarrays starting with arr[i]. Store the current sum in Z. If Z is greater than Y, then update Y.

Y is used to store maximum sum seen so far and Z is used to store current sum

1) Initialize Y as sum of all elements

2) For every element, calculate sum of all subarrays starting with arr[i]. Store the current sum in Z. If Z is greater than Y, then update Y.

Workspace

222. Let P be a QuickSort Program to sort numbers in ascending order using the first element as pivot. Let t1 and t2 be the number of comparisons made by P for the inputs {1, 2, 3, 4, 5} and {4, 1, 5, 3, 2} respectively. Which one of the following holds?

SHOW ANSWER

Correct Ans:t1 > t2

Explanation:

When first element or last element is chosen as pivot, Quicksort's worst case occurs for the sorted arrays.

In every step of quick sort, numbers are divided as per the following recurrence.

T(n) = T(n-1) + O(n)

In every step of quick sort, numbers are divided as per the following recurrence.

T(n) = T(n-1) + O(n)

Workspace

223. Consider the directed graph given below. Which one of the following is TRUE?

SHOW ANSWER

Correct Ans:Both PSRQ and SPRQ are topological ordering

Explanation:

The graph doesn't contain any cycle, so there exist topological ordering.

P and S must appear before R and Q because there are edges from P to R and Q, and from S to R and Q.

P and S must appear before R and Q because there are edges from P to R and Q, and from S to R and Q.

Workspace

224. Consider a rooted Binary tree represented using pointers. The best upper bound on the time required to determine the number of subtrees having having exactly 4 nodes O(n^a Logn^b). Then the value of a + 10b is ________

SHOW ANSWER

Correct Ans:1

Explanation:

We can find the subtree with 4 nodes in O(n) time. Following can be a simple approach.

1) Traverse the tree in bottom up manner and find size of subtree rooted with current node

2) If size becomes 4, then print the current node.

int print4Subtree(struct Node *root)

{

if (root == NULL)

return 0;

int l = print4Subtree(root->left);

int r = print4Subtree(root->right);

if ((l + r + 1) == 4)

printf("%d ", root->data);

return (l + r + 1);

}

1) Traverse the tree in bottom up manner and find size of subtree rooted with current node

2) If size becomes 4, then print the current node.

int print4Subtree(struct Node *root)

{

if (root == NULL)

return 0;

int l = print4Subtree(root->left);

int r = print4Subtree(root->right);

if ((l + r + 1) == 4)

printf("%d ", root->data);

return (l + r + 1);

}

Workspace

225. Let G be a graph with n vertices and m edges. What is the tightest upper bound on the running time on Depth First Search of G? Assume that the graph is represented using adjacency matrix.

SHOW ANSWER

Correct Ans:O(n^2)

Explanation:

Depth First Search of a graph takes O(m+n) time when the graph is represented using adjacency list.

In adjacency matrix representation, graph is represented as an 'n x n' matrix. To do DFS, for every vertex, we traverse the row corresponding to that vertex to find all adjacent vertices (In adjacency list representation we traverse only the adjacent vertices of the vertex). Therefore time complexity becomes O(n^2)

In adjacency matrix representation, graph is represented as an 'n x n' matrix. To do DFS, for every vertex, we traverse the row corresponding to that vertex to find all adjacent vertices (In adjacency list representation we traverse only the adjacent vertices of the vertex). Therefore time complexity becomes O(n^2)

Workspace

226. Suppose implementation supports an instruction REVERSE, which reverses the order of elements on the stack, in addition to the PUSH and POP instructions. Which one of the following statements is TRUE with respect to this modified stack?

SHOW ANSWER

Correct Ans:A queue can be implemented where ENQUEUE takes a sequence of three instructions and DEQUEUE takes a single instruction

Explanation:

To DEQUEUE an item, simply POP.

To ENQUEUE an item, we can do following 3 operations

1) REVERSE

2) PUSH

3) REVERSE

To ENQUEUE an item, we can do following 3 operations

1) REVERSE

2) PUSH

3) REVERSE

Workspace

227. Which one of the following correctly determines the solution of the recurrence relation with T(1) = 1?

T(n) = 2T(n/2) + Logn

T(n) = 2T(n/2) + Logn

SHOW ANSWER

Correct Ans:O(n)

Explanation:

Workspace

228. A priority queue is implemented as a Max-Heap. Initially, it has 5 elements. The level-order traversal of the heap is: 10, 8, 5, 3, 2. Two new elements 1 and 7 are inserted into the heap in that order. The level-order traversal of the heap after the insertion of the elements is:

SHOW ANSWER

Correct Ans:10, 8, 7, 3, 2, 1, 5

Explanation:

Workspace

229. Consider a hash table with 9 slots. The hash function is h(k) = k mod 9. The collisions are resolved by chaining. The following 9 keys are inserted in the order: 5, 28, 19, 15, 20, 33, 12, 17, 10. The maximum, minimum, and average chain lengths in the hash table, respectively, are

SHOW ANSWER

Correct Ans:3, 0, and 1

Explanation:

Following are values of hash function for all keys

5 --> 5

28 --> 1

19 --> 1 [Chained with 28]

15 --> 6

20 --> 2

33 --> 6 [Chained with 15]

12 --> 3

17 --> 8

10 --> 1 [Chained with 28 and 19]

The maximum chain length is 3. The keys 28, 19 and 10 go to same slot 1, and form a chain of length 3.

The minimum chain length 0, there are empty slots (0, 4 and 7).

Average chain length is (0 + 3 + 1 + 1 + 0 + 1 + 2 + 0 + 1)/9 = 1

5 --> 5

28 --> 1

19 --> 1 [Chained with 28]

15 --> 6

20 --> 2

33 --> 6 [Chained with 15]

12 --> 3

17 --> 8

10 --> 1 [Chained with 28 and 19]

The maximum chain length is 3. The keys 28, 19 and 10 go to same slot 1, and form a chain of length 3.

The minimum chain length 0, there are empty slots (0, 4 and 7).

Average chain length is (0 + 3 + 1 + 1 + 0 + 1 + 2 + 0 + 1)/9 = 1

Workspace

230. Consider the following pseudo code. What is the total number of multiplications to be performed?

D = 2

for i = 1 to n do

for j = i to n do

for k = j + 1 to n do

D = D * 3

D = 2

for i = 1 to n do

for j = i to n do

for k = j + 1 to n do

D = D * 3

SHOW ANSWER

Correct Ans:One-sixth of the product of the 3 consecutive integers.

Explanation:

Workspace

231. Consider the tree arcs of a BFS traversal from a source node W in an unweighted, connected, undirected graph. The tree T formed by the tree arcs is a data structure for computing.

SHOW ANSWER

Correct Ans:the shortest path from W to every vertex in the graph.

Explanation:

BFS always produces shortest paths from source to all other vertices in an unweighted graph. The reason is simple, in BFS, we first explore all vertices which are 1 edge away from source, then we explore all vertices which are 2 edges away from the source and so on. This property of BFS makes it useful in many algorithms like Edmonds–Karp algorithm.

Workspace

232. Suppose P, Q, R, S, T are sorted sequences having lengths 20, 24, 30, 35, 50 respectively. They are to be merged into a single sequence by merging together two sequences at a time. The number of comparisons that will be needed in the worst case by the optimal algorithm for doing this is ____.

SHOW ANSWER

Correct Ans:358

Explanation:

To merge two lists of size m and n, we need to do m+n-1 comparisons in worst case. Since we need to merge 2 at a time, the optimal strategy would be to take smallest size lists first. The reason for picking smallest two items is to carry minimum items for repetition in merging.

We first merge 20 and 24 and get a list of 44 using 43 worst case comparisons. Then we merge 30 and 35 into a list of 65 using 64 worst case comparisons. Then we merge 50 and 44 into a list of 94 using 93 comparisons. Finally we merge 94 and 65 using 158 comparisons. So total number of comparisons is 43 + 64 + 93 + 158 which is 358.

We first merge 20 and 24 and get a list of 44 using 43 worst case comparisons. Then we merge 30 and 35 into a list of 65 using 64 worst case comparisons. Then we merge 50 and 44 into a list of 94 using 93 comparisons. Finally we merge 94 and 65 using 158 comparisons. So total number of comparisons is 43 + 64 + 93 + 158 which is 358.

Workspace

233. Consider the pseudocode given below. The function DoSomething() takes as argument a pointer to the root of an arbitrary tree represented by the leftMostChild-rightSibling representation. Each node of the tree is of type treeNode.

typedef struct treeNode* treeptr;

struct treeNode {

treeptr leftMostChild, rightSibling;

};

int DoSomething (treeptr tree) {

int value = 0;

if (tree != NULL) {

if (tree->leftMostChild == NULL)

value = 1;

else

value = DoSomething(tree->leftMostChild);

value = value + DoSomething(tree->rightSibling);

}

return(value);

}

When the pointer to the root of a tree is passed as the argument to DoSomething, the value returned by the function corresponds to the

typedef struct treeNode* treeptr;

struct treeNode {

treeptr leftMostChild, rightSibling;

};

int DoSomething (treeptr tree) {

int value = 0;

if (tree != NULL) {

if (tree->leftMostChild == NULL)

value = 1;

else

value = DoSomething(tree->leftMostChild);

value = value + DoSomething(tree->rightSibling);

}

return(value);

}

When the pointer to the root of a tree is passed as the argument to DoSomething, the value returned by the function corresponds to the

SHOW ANSWER

Correct Ans:number of leaf nodes in the tree.

Explanation:

The important thing to note in this question is tree’s representation. Tree is represented as leftmost child and right sibling form. So if the leftmost child is NULL for a node, then there is no child of this node. If we take a look at the function, we can notice that the function increments the “value” by 1 only for a leaf node.

Workspace

234. You have an array of n elements. Suppose you implement quicksort by always choosing the central element of the array as the pivot. Then the tightest upper bound for the worst case performance is

SHOW ANSWER

Correct Ans:O(n^2)

Explanation:

The middle element may always be an extreme element (minimum or maximum) in sorted order, therefore time complexity in worst case becomes O(n^2)

Workspace

235. The minimum number of arithmetic operations required to evaluate the polynomial P(X) = X^5 + 4X^3 + 6X + 5 for a given value of X using only one temporary variable.

SHOW ANSWER

Correct Ans:7

Explanation:

We can parenthesize the polynomial to minimize the number of operations.

We get X(X2(X2 + 4) + 6) + 5 after parenthesization.

Following is sequence of operations to be used.

Note that we are allowed to use only one variable.

res = X*X

res = res + 4

res = X*res

res = X*res

res = res + 6

res = X*res

res = res + 5

**Horner’s Method:**We get X(X2(X2 + 4) + 6) + 5 after parenthesization.

Following is sequence of operations to be used.

Note that we are allowed to use only one variable.

res = X*X

res = res + 4

res = X*res

res = X*res

res = res + 6

res = X*res

res = res + 5

Workspace

236. Let A be a square matrix of size n x n. Consider the following program. What is the expected output?

C = 100

for i = 1 to n do

for j = 1 to n do

{

Temp = A[i][j] + C

A[i][j] = A[j][i]

A[j][i] = Temp - C

}

for i = 1 to n do

for j = 1 to n do

Output(A[i][j]);

C = 100

for i = 1 to n do

for j = 1 to n do

{

Temp = A[i][j] + C

A[i][j] = A[j][i]

A[j][i] = Temp - C

}

for i = 1 to n do

for j = 1 to n do

Output(A[i][j]);

SHOW ANSWER

Correct Ans:The matrix A itself

Explanation:

If we take look at the inner statements of first loops, we can notice that the statements swap A[i][j] and A[j][i] for all i and j.

Since the loop runs for all elements, every element A[l][m] would be swapped twice, once for i = l and j = m and then for i = m and j = l. Swapping twice means the matrix does not change.

Since the loop runs for all elements, every element A[l][m] would be swapped twice, once for i = l and j = m and then for i = m and j = l. Swapping twice means the matrix does not change.

Workspace

237. Consider the following rooted tree with the vertex P labeled as root

The order in which the nodes are visited during in-order traversal is

The order in which the nodes are visited during in-order traversal is

SHOW ANSWER

Correct Ans:SQPTRWUV

Explanation:

Workspace

238. Consider a weighted complete graph G on the vertex set {v1, v2, ..vn} such that the weight of the edge (vi, vj) is 2|i-j|. The weight of a minimum spanning tree of G is

SHOW ANSWER

Correct Ans:2n - 2

Explanation:

Workspace

239. An element in an array X is called a leader if it is greater than all elements to the right of it in X. The best algorithm to find all leaders in an array

SHOW ANSWER

Correct Ans:Solves it in linear time using a right to left pass of the array

Explanation:

Workspace

240. Which one of the following in place sorting algorithms needs the minimum number of swaps?

SHOW ANSWER

Correct Ans:Selection sort

Explanation:

Workspace

Are you seeking for good platform for practicing Data Structure questions in online. This is the right place. The time you spent in Fresherslive will be the most beneficial one for you.

## Online Test on Data Structure @ Fresherslive

This page provides important questions on Data Structure along with correct answers and clear explanation, which will be very useful for various Interviews, Competitive examinations and Entrance tests. Here, Most of the Data Structure questions are framed with Latest concepts, so that you may get updated through these Data Structure Online tests. Data Structure Online Test questions are granted from basic level to complex level.

## Why To Practice Data Structure Test questions Online @ Fresherslive?

Data Structure questions are delivered with accurate answer. For solving each and every question, very lucid explanations are provided with diagrams wherever necessary.

Practice in advance of similar questions on Data Structure may improve your performance in the real Exams and Interview.

Time Management for answering the Data Structure questions quickly is foremost important for success in Competitive Exams and Placement Interviews.

Through Fresherslive Data Structure questions and answers, you can acquire all the essential idea to solve any difficult questions on Data Structure in short time and also in short cut method.

Winners are those who can use the simplest method for solving a question. So that they have enough time for solving all the questions in examination, correctly without any tense. Fresherslive provides most simplest methods to answer any tough questions. Practise through Fresherslive test series to ensure success in all competitive exams, entrance exams and placement tests.

## Why Fresherslive For Data Structure Online Test Preparation?

Most of the job seekers finding it hard to clear Data Structure test or get stuck on any particular question, our Data Structure test sections will help you to success in Exams as well as Interviews. To acquire clear understanding of Data Structure, exercise these advanced Data Structure questions with answers.

You're Welcome to use the Fresherslive Online Test at any time you want. Start your beginning, of anything you want by using our sample Data Structure Online Test and create yourself a successful one. Fresherslive provides you a new opportunity to improve yourself. Take it and make use of it to the fullest. GOODLUCK for Your Bright Future.