Multiple choice questions in Data structures and algorithms with answers set 07

Data structures and algorithms multiple choice questions with answers, important interview questions in data structures, data structures questions for entrance exams

Data Structures and Algorithms Multiple Choice Questions

SET 07

 

1. Which of the following statements is true?

a) Interpreted programs run faster than compiled programs.

b) Compilers translate high-level language into machine language.

c) Interpreter programs use assembly language as input.

d) None of the above.

 

2. What is the worst case tightest bound time complexity for the following case? “Finding the maximum value in a hash table containing N elements where quadratic probing has been used to resolve collisions”

a) O(N)

b) O(N²)

c) O(log N)

d) O(log²N)

 

3. What is the tightest and simple worst case time complexity of printing all elements from a binary search trees consists of N elements from largest to smallest value?

a) O(N)

b) O(N²)

c) O(log N)

d) O(log²N)

 

4. Find the worst case time complexity of the following algorithm

void skiing(int n)

{

for (int i = 0; i < n; i = i + n/2)

{

for (int j = n; j > 0; j = j – n * 2)

{

print("downhill");

}

}

}

a) O(N)

b) O(N²)

c) O(1)

d) O(log N)

 

5. Given a complete binary tree of height h, what are the minimum and maximum numbers of nodes in the right subtree of the root?

a) 0, 2^h

b) 2^h-1 – 1, 2^h-1 – 1

c) 2^h – 1, 2^h-1 – 1

d) 2^h-1 – 1, 2^h – 1

 

6. In a single linked list which operation depends on the length of the list.

a) Delete the last element of the list

b) Add an element before the first element of the list

c) Delete the first element of the list

d) Interchange the first two elements of the list

 

7. What is the worst case time complexity for pushing an element into a stack of N elements that was implemented using singly linked list?

a) O(N)

b) O(N²)

c) O(1)

d) O(log N)

 

8. What is the time complexity of the following code segment?

          sum = 0;

          for (i=1; i<=100; i++)

                   for (j=1; j<=n; j++)

                             sum = sum + i;

a) O(N)

b) O(N²)

c) O(1)

d) O(log N)

 

9. Which of the following statements are NOT CORRECT? Binary search trees (regardless of the order in which the values are inserted into the tree)

a) Always have multiple links per node.

b) Can be sorted efficiently.

c) Always have the same shape for a particular set of data.

d) Are nonlinear data structures.

 

10. What is the worst case time complexity of deleting an element from a binary search tree of N elements?

a) O(N)

b) O(N²)

c) O(1)

d) O(log N)

********************

Answer:

1 – (b) Compilers translate high-level language into machine language.

2 – (a) O(N)

3 – (b) O(N)

Hint: The property of binary search tree is its left children is less than or equal to root and right children is greater than root. You can do the inorder traversal in reverse to arrange the elements in descending order as follows;

print INORDER(right)

print INORDER(root)

print INORDER(left)

 

4 – (c) O(1)

Hint: The given routine will execute a maximum of three times as per the conditions given. Hence, the complexity is constant time.

 

5 – (d) 2^h-1 – 1, 2^h – 1

Hint: Complete binary trees require the nodes to fill ineach level from left-to-right before starting thenext level. A complete binary tree of height h looks like a full binary tree down to level h-1, and the level h is filled from left to right.

 

6 – (a) Delete the last element of the list

Hint: In a singly linked list, if you want to delete the last element, then you have to traverse the entire list to reach the last node. Then only you can delete it.

 

7 – (c) O(1)

Hint: Pushing into a stack which was implemented using singly linked list requires creation of new node and reset the head node to point to the new node. This happens for every insertion. Hence the time complexity is constant time.

 

8 – (a) O(N)

Hint: For any N value, the outer loop executes exactly 100 times and the inner loop executes for N times. The time complexity = O(1) + O(N) + O(1) = O(N). [outer for loop, inner loop and sum calculation]

 

9 – (c) Always have the same shape for a particular set of data.

10 – (a) O(N)

Hint: For deletion of element, we have to traverse all elements to find the element to be deleted. Therefore, deletion in binary tree has worst case complexity of O(n). In general, in the worst case it requires time proportional to the height of the tree.

 

*************************

Related links:

• Go to MCQ Questions and Answers on Data Structures and Algorithms

• Go to TRUE/FALSE Questions and Answers in Data Structures and Algorithms

• Go to Computer Science Engineering - Quiz Questions and Answers - Home page

Interview questions and answers in data structure and algorithms

DSA quiz questions with answers explained

Solved true or false questions in DSA

Practice questions in data structures

Entrance exam questions with answers in Data structures for Tamilnadu engineering entrance

Entrance exam questions with answers in Data structures for IIT-JEE entrance exam

Entrance exam questions with answers in Data structures for JNTU engineering entrance