Interview questions related to data structures

CS 201 DATA STRUCTURES         Interview Related objectives                   

                            

                                                                                                GOOD LUCK

1. You are given the following time complexity functions.

f(n) =    2*n! + n/(log n)

g(n) =    5ⁿ + 5

h(n)=   n + nⁿ

When arranged in ascending order (slowest execution time to fastest) we get the following order:

a.       f(n) g(n) h(n)

b.       h(n) g(n) f(n)

c.        h(n) f(n) g(n)[MS1] 

d.       f(n) h(n) g(n)

e.        noneof the above

2. Consider the following circular list (next indicates the forward/right link, previndicates the previous/left link):

What is outputfor the following lines of code:

list->next->next         = list->prev;

list->prev->prev->prev = list;

cout<< list->next->next->prev->data;

1. 2
2. 7
3. 5[a2] 
4. 15
5. runtimeerror

3. Which of the following bits of code would successfully remove the first element from a doubly-linked circular list, in which the list pointer L points to the first element in the list? Assume that the list has at least five elements to begin with.

a.    

L->prev->next = L->next;

L->next->prev=L->prev;

L=L->next;

b.

L->next->prev->

prev->next = L->next;

L->next->prev= L->prev;

L = L->next;

c.

L->prev->next = L->

prev->next->next;

L->next->prev=L->

next->prev->prev;

L=L->next;

d.        None of the above

e.        All of the above[a3] 

4. For the following tree, post-order traversal prints the values:

1. A E H I L K J G[a4] 
2. G E A J I H K L
3. A E G H I J K L
4. G E A J H I K L
5. none of the above

5. If a binary tree has a total of 15 nodes, it can have how many total levels:

1. Any number between 1 and 15 (inclusive)
2. Any number between 3 and 15 (inclusive)
3. Any number between 4 and 15 (inclusive)[a5] 
4. Only 4 levels
5. Only 3 levels
6. none of the above

6. The (i,j)th index of a 2D array of dimension MxN is mapped to which position, when stored internally as a single dimensional array in column major order:

a.       j+M*i

b.       i+N*j

c.        i+M*j[a6] 

d.       j+N*i

e.        none of the above

7. What is the time complexity of the following piece of code?

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

{               for (j=n;j>=1;j=j-2)

                {              

                                cout << ‘*’;

                }

}

a.       O(n)

b.       O(n²)[a7] 

c.        O(n² log n)

d.       O(n log n)

e.        O(log n)

8. What is the worst case time complexity for deleting from a max heap?

a.       O(n)

b.       O(1)

c.        O(n²)

d.       O(log n)[a8] 

e.        none of the above

9. We have three keys, i.e., {9, 15, 20} to be stored in a binary search tree.  How many possible BST’s can we have?

a.       6

b.        7

c.         3

d.        4

e.         5[a9] 

10. Suppose we have 5 keys {90,20,3,7,2} and a hash function: (key mod 5).  How many collisions do we have?

a.        1

b.        2[a10] 

c.         3

d.        4

e.         5

SOLUTION

---

 [MS1]correct

 [a2]correct

 [a3]I hope this is the correct choice!

 [a4]correct

 [a5]correct

 [a6]correct

 [a7]correct

 [a8]correct

 [a9]correct

 [a10]correct