# 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^{2})

c) O(log N)

d) O(log^{2}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^{2})

c) O(log N)

d) O(log^{2}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^{2})

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^{2})

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^{2})

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^{2})

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:**

**Related links:**

#### 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

## No comments:

## Post a Comment