Data Structures 03

21. Merge sort makes two recursive calls. Which statement is true after these two recursive calls finish, but before the merge step ? [Paper II June2014]
(A) The array elements form a heap.

(B) Elements in each half of the array are sorted amongst themselves.

(C) Elements in the first half of the array are less than or equal to elements in second half of the array.
(D) All of the above

22. Searching for an element in the hash table requires O(1) time for the ___ time, whereas for direct addressing it holds for the ___ time. [Paper II June 2014]
(A) worst­ case, average    (B) worst ­case, worst­ case
(C) average, worst­ case    (D) best, average

23. An algorithm is made up of 2 modules M1 and M2. If time complexity of modules M1 and M2 are h(n) and g(n) respectively, the time complexity of the algorithm is [Paper II June 2014]
(A) min (h(n), g(n))      (B) max (h(n), g(n))
(C) h(n) + g(n)            (D) h(n) * g(n)

24. What is the maximum number of parenthesis that will appear on the stack at any one time for parenthesis expression given by (( ) ( ( ) ) ( ( ) ) ) [Paper II June 2014]
(A) 2         (B) 3
(C) 4         (D) 5

25. The reverse polish notation equivalent to the infix expression ((A + B) * C + D)/(E + F + G)   [Paper III June 201 4]
(A) A B + C * D + EF + G + / 

(B) A B + C D * + E F + G + /
(C) A B + C * D + E F G + +/ 

(D) A B + C * D + E + F G + /

26. ___ comparisons are necessary in the worst case to find both the maximum and minimum of n numbers.    [Paper III December 2013 ]
(A) 2n – 2                        (B) n + floor (lg n) – 2
(C) floor (3n/2) – 2            (D) 2 * lg n – 2

27. Let A and B be two n × n matrices. The efficient algorithm to multiply the two matrices has the time complexity [Paper III December 2013 ]
(A) O(n³)                (B) O(n^2.81)
(C) O(n^2.67)            (D) O(n²)

28. Assuming there are n keys and each key is in the range [0, m – 1]. The run time of bucket sort is  [Paper III December 2013 ]

(A) O(n)                 (B) O(n * lg n)
(C) O(n * lg m)       (D) O(n + m)

29.What is the value of the postfix expression ?
a b c d + – ∗ (where a = 8, b = 4, c = 2 and d = 5) [Paper II December2013]
(A) – 3/8                (B) ­ 8/3
(C) 24                   (D) ­24

30. If the queue is implemented with a linked list, keeping track of a front pointer and a rear pointer, which of these pointers will change during an insertion into a non­empty queue ?       [Paper II December 2013]
(A) Neither of the pointers change 
(B) Only front pointer changes
(C) Only rear pointer changes
(D) Both of the pointers changes

SOLUTIONS

21. B

22. C

23. B

24. B

25. A

26. C

27. B
 
28. D

29. D

30. C

Programming (C, C++ ...) 02

11. Assume that we have constructor functions for both base class and derived class. Now consider the declaration in main( ). Base * P = new Derived; in what sequence will the constructor be called? [Paper III June 2012]
(A) Derived class constructor followed by Base class constructor.
(B) Base class constructor followed by derived class constructor.
(C) Base class constructor will not be called.
(D) Derived class constructor will not be called.

12. printf(“%c”, 100); [Paper II June 2012]
(A) prints 100
(B) prints ASCII equivalent of 100
(C) prints garbage
(D) none of the above

13. Which API is used to draw a circle ? [Paper II December 2012]
(A) Circle( )                 (B) Ellipse( )
(C) RoundRect( )         (D) Pie( )

14. Which of the following are two special functions that are meant for handling exception, that occur during exception handling itself? [Paper II December 2012]
(A) void terminate ( ) and void unexpected ( )
(B) Non void terminate ( ) and void unexpected ( )
(C) void terminate ( ) and non void unexpected ( )
(D) Non void terminate ( ) and non void unexpected ( )

15. Match the following with respect to C++ data types: [Paper II December 2012]
a. User defined type 1. Qualifier
b. Built in type 2. Union
c. Derived type 3. Void
d. Long double 4. Pointer
Code :
       a b c d
(A) 2 3 4 1
(B) 3 1 4 2
(C) 4 1 2 3
(D) 3 4 1 2

16. Enumeration is a process of [Paper II December 2012]
(A) Declaring a set of numbers
(B) Sorting a list of strings
(C) Assigning a legal values possible for a variable
(D) Sequencing a list of operators

17. Which of the following mode declaration is used in C++ to open a file for input?
[Paper II December 2012]
(A) ios : : app
(B) in : : ios
(C) ios : : file
(D) ios : : in

18. What is the result of the following expression? [Paper II December 2012]
(1 & 2) + (3 & 4)
(A) 1
(B) 3
(C) 2
(D) 0

SOLUTIONS

11. B
Here A derived class object is created first and then assigned to a base class pointer. Whenever a derived class object is created, the base class constructor gets called first and then the derived class constructor.

12. B

13. B

14. A
The visual C++ Standard requires that unexpected() is called when a function throws an exception that is not on its throw list.
The terminate( ) function is used with visual C++ exception handling and is called in the following cases:

• A matching catch handler cannot be found for a thrown C++ exception.
• An exception is thrown by a destructor function during stack unwind.
• The stack is corrupted after throwing an exception.

Both the functions does not return anything.

15. A

16. C

An enum is a user-defined type consisting of a set of named constants called enumerators. The colors of the rainbow would be mapped like this.:

              enum rainbowcolors { red,  orange, yellow, green,  blue, indigo, violet)  }

Now internally, the compiler will use an int to hold these and if no values are supplied, red will be 0, orange is 1 etc.

17. D
In order to open a file with a stream object we use its member function open():
          open (filename, mode);
Where filename is a null-terminated character sequence of type const char * (the same type that string literals have) representing the name of the file to be opened, and mode is an optional parameter with a combination of the following flags:

• ios::in    Open for input operations.
• ios::out    Open for output operations.
• ios::binary  Open in binary mode.
• ios::ate    Set the initial position at the end of the file. If this flag is not set to any value, the initial position is the beginning of the file.
• ios::app    All output operations are performed at the end of the file, appending the content to the current content of the file. This flag can only be used in streams open for output-only operations.
• ios::trunc    If the file opened for output operations already existed before, its previous content is deleted and replaced by the new one.

18. D
& represents bitwise AND. Converting the given values in the expression to 4 bit binary we have:
(1 & 2) + (3 & 4) = (0001 & 0010) + (0011 & 0100)
                            = (0000) + (0000)
                            = 0 + 0
                            = 0