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

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

Data Structures and Algorithms Multiple Choice Questions

SET 08

 

1. What is the minimum number of nodes in an AVL tree of height 5?

a) 20

b) 21

c) 63

d) 12

Answer: (a) 20 Minimum number of nodes in an AVL tree can be recursively calculated as follows; Min. number of nodes of height h, N(h) = N(h-1) + N(h-2) + 1 Here, 1 is added to include the root node. N(0) = 1, N(1) = 2, N(2) = N(1) + N(0) + 1 = 2+1+1 = 4, N(3) = N(2) + N(1) + 1 = 4 + 2 + 1 = 7, N(4) = 12, N(5) = 20. AVL tree An AVL tree is a binary search tree with a self-balancing condition stating that the difference between the height of the left and right subtrees cannot be no more than one. An AVL tree has the following properties: 1. The sub-trees of every node differ in height by at most one. 2. Every sub-tree is an AVL tree.

 

2. What is the minimum number of nodes that must be examined in order to find the minimum value in an AVL tree of height 5?

a) 20

b) 3

c) 12

d) 5

Answer: (b) 3 Minimum value in an AVL tree can be found at the left most node that has left pointer NULL. Such a node can be found at a height of 3 for an AVL tree of height 5.

 

3. Consider a perfect binary tree of height h. Which of the following options represents the minimum and maximum number of nodes in the right sub-tree of the root?

a) 2^h, 2^h

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

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

d) 2h-1, 2h-1

Answer: (b) 2h-1, 2h-1 A perfect binary tree is a binary tree in which all interior nodes have two children and all leaves have the same depth or same level. In this tree each level contains the maximum number of nodes, ie., every level is completely full of nodes. The number of nodes in a perfect binary tree = 2h+1-1 As per the question, we need to find the number of nodes in the right sub-tree alone. Also, the right sub-tree is at height less than that of original tree. Hence, the number of nodes = 2h-1.  For a perfect binary tree, the minimum and maximum number of nodes will be 2h+1-1. Hence, for the right sub-tree alone, they are 2h-1.

 

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

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

Data structures and algorithms GATE exam questions 

What is perfect binary tree and how many nodes it can contain in maximum?

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

 

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

 

 

 

Multiple choice questions in Data structures and algorithms set 06

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 06

1. If you have just executed the command “delete myPtr”, which of the following conclusions will be TRUE?

(a) The memory referenced by myPtr is released only if it is needed by the system.

(b) The pointer myPtr is of type void *.

(c) The pointer myPtr only exists if there was an error freeing the memory.

(d) The pointer myPtr still exists

 

2. What kind of linked list begins with a pointer to the first node, and each node contains a pointer to the next node, and the pointer in the last node points back to the first node?

(a) Circular, singly-linked list.

(b) Circular, doubly-linked list.

(c) Singly-linked list.

(d) Doubly-linked list.

 

3. How many pointers are contained as data members in the nodes of a circular, doubly linked list of integers with five nodes?

(a) 5

(b) 8

(c) 10

(d) 15

 

4. Which of the following statements about stacks is incorrect?

(a) Stacks can be implemented using linked lists.

(b) Stacks are first-in, first-out (FIFO) data structures.

(c) New nodes can only be added to the top of the stack.

(d) The last node (at the bottom) of a stack has a null (0) link

 

5. Given the function definition

void Twist(int &a, int b)

{

int c;

c = a + 2;

a = a * 3;

b = c + a;

}

What is the output of the following code fragment?

r =1;

s =2;

t =3;

Twist(t, s);

cout « r « ‘’ « S « ‘’ « t « endl;

(a) 1, 2, 3

(b) 1 10 3

(c) 1 2 14

(d) 1 2 9

 

6. T(n) = 2n2 + 2n + 3. Which of the following is true about T(n)?

(a) T(n) is O(n²)

(b) T(n) is Ω(n²)

(c) T(n) is Θ(n²)

(d) All of the above

 

7. What is the minimum number of data items in a B tree of height 4 with M = 4 and L = 4?

(a) 4

(b) 8

(c) 16

(d) 32

 

8. A company has a huge amount of data stored on external servers. They have even more data to add and will be performing many insert operations, which they want to be fast. Which of the following data structures will be most suitable (in terms of run time) for this case?

(a) Heap

(b) Queue

(c) B-tree

(d) AVL tree

 

9. What is the worst case time complexity of creating a binary min heap from the elements in a binary search tree containing N elements?

(a) O(1)

(b) O(N)

(c) O(log N)

(d) None of the above

 

10. What is the tight bound worst case time complexity of popping an element from a stack of N elements which was implemented using array data structure?

(a) O(1)

(b) O(N)

(c) O(log N)

(d) None of the above

 

Click here for the answers

Answer:

1 – (d), 2 – (a), 3 – (c), 4 – (b), 5 – (d), 6 – (d), 7 – (d), 8 – (c), 9 – (b), 10 – (a)

 

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

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