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

Programming (C, C++ ...) 01

01. When a programming Language has the capacity to produce new datatype, it is called as,

[Paper III December 2012]

(A) Overloaded Language

(B) Extensible Language

(C) Encapsulated Language

(D) Abstraction Language                  

02. The Default Parameter Passing Mechanism is called as       [Paper III December 2012]

(A) Call by Value

(B) Call by Reference

(C) Call by Address

(D) Call by Name

03. Functions defined with class name are called as                   [Paper III December 2012]

(A) Inline function            (B) Friend function

(C) Constructor               (D) Static function

04. 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. 

05. Consider the program below in a hypothetical programming language which allows global variables and a choice of static or dynamic scoping                  [Paper III December 2012]

int i;

program Main( )

{

       i = 10;

       call f ( );

}

procedure f( )

{

        int i = 20;

        call g ( );

}

procedure g( )

{

       print i;

}

Let x be the value printed under static scoping and y be the value printed under dynamic scoping. Then x and y are

(A) x = 10, y = 20

(B) x = 20, y = 10

(C) x = 20, y = 20

(D) x = 10, y = 10

06. printf(“%c”, 100);                                  [Paper II June 2012]

(A) prints 100

(B) prints ASCII equivalent of 100

(C) prints garbage

(D) none of the above

07. X – = Y + 1 means                               [Paper III December 2012]

(A) X = X – Y + 1

(B) X = –X – Y – 1

(C) X = –X + Y + 1

(D) X = X – Y – 1

08. The _______ memory allocation function modifies the previous allocated space. 
[Paper III June 2012]

(A) calloc( )                 (B) free( )

(C) malloc( )                (D) realloc( )

09. The mechanism that binds code and data together and keeps them secure from outside world is known as                  .           [Paper III June 2012]

(A) Abstraction           (B) Inheritance

(C) Encapsulation       (D) Polymorphism

10. Match the following with respect to java.util.* class methods:     [Paper III June 2012]

(a) Bit Set                    (i) Time zone getTimezone( )

(b) Calendar                (ii) int hashcode( )

(c) Time zone              (iii) int nextInt( )

(d) Random                 (iv) void setID(String tzName)

(a)        (b)        (c)        (d)

(A)       (ii)        (i)         (iv)       (iii)

(B)       (iii)       (iv)        (i)         (ii)

(C)       (iv)       (iii)        (ii)        (i)

(D)       (ii)        (i)         (iii)       (iv)

SOLUTIONS

1. B

2. A

3. C

4.

5. D

Whatever be the scoping, the i declared inside the method f() is not accessible outside. So when we say i from g(), it refers to global i. So under both cases, 10 is printed

6. B

7. D

X - = Y + 1    =>     X = X - (Y+1)    =>     X = X - Y - 1

8. D

malloc allocates the specified number of bytes
realloc increases or decrease the size of the specified block of memory. Reallocates it if needed
calloc allocates the specified number of bytes and initializes them to zero

free         releases the specified block of memory back to the system

9. C

10. A

The exact match is

(a) Bit Set                    (ii) int hashcode( )

(b) Calendar                (i) Time zone getTimezone( )

(c) Time zone               (iv) void setID(String tzName)

(d) Random                 (iii) int nextInt( )

Miscellaneous 01

01. ______ is process of extracting previously not known valid and actionable information from large data to make crucial business and strategic decisions.                     [Paper III December 2012]

(A) Data Management

(B) Data base

(C) Data Mining

(D) Meta Data

02. Data Warehouse provides                                             [Paper III June 2012]

(A) Transaction Responsiveness

(B) Storage, Functionality Responsiveness to queries

(C) Demand and Supply Responsiveness

(D) None of the above

03. An example of a dictionary-based coding technique is      [Paper III December 2012]

(A) Run-length coding

(B) Huffman coding

(C) Predictive coding

(D) LZW coding

SOLUTIONS

1. C

2. B

A data warehouse is a database used for reporting and data analysis. It is a central repository of data which is created by integrating data from one or more disparate sources. Data warehouses store current as well as historical data and are used for creating trending reports for senior management reporting such as annual and quarterly comparisons.

The data stored in the warehouse are uploaded from the operational systems (such as marketing, sales etc.,). The data may pass through an operational data store for additional operations before they are used in the DW for reporting.

3. D
Run-length Coding is a very simple form of data compression in which runs of data (that is, sequences in which the same data value occurs in many consecutive data elements) are stored as a single data value and count, rather than as the original run.
Huffman coding is an entropy encoding algorithm used for lossless data compression. The term refers to the use of a variable-length code table for encoding a source symbol.
Predictive coding is a tool used mostly in audio signal processing and speech processing for representing the spectral envelope of a digital signal of speech in compressed form, using the information of a linear predictive model.
Lempel–Ziv–Welch (LZW) is a universal lossless data compression algorithm. A high level view of the encoding algorithm is shown here:

1. Initialize the dictionary to contain all strings of length one.
2. Find the longest string W in the dictionary that matches the current input.
3. Emit the dictionary index for W to output and remove W from the input.
4. Add W followed by the next symbol in the input to the dictionary.
5. Go to Step 2.

A dictionary is initialized to contain the single-character strings corresponding to all the possible input characters (and nothing else except the clear and stop codes if they're being used). The algorithm works by scanning through the input string for successively longer substrings until it finds one that is not in the dictionary

Computer Graphics 01

1. The aspect ratio of an image is defined as         [Paper III December 2012]
(A) The ratio of width to its height measured in unit length.
(B) The ratio of height to width measured in number of pixels.
(C) The ratio of depth to width measured in unit length.
(D) The ratio of width to depth measured in number of pixels.

2. The Mandelbrot set used for the construction of beautiful images is based on the following transformation: x_{n + 1}= x²_n+ z    Here,                        [Paper III December 2012]
(A) Both x & z are real numbers.
(B) Both x & z are complex numbers.
(C) x is real & z is complex.
(D) x is complex & z is real.

3. In an image compression system 16384 bits are used to represent 256 × 256 image with 256 gray levels. What is the compression ratio for this system? [Paper III June 2012]
(A) 1 (B) 2
(C) 4 (D) 8

4. If the pixels of an image are shuffled then the parameter that may change is
[Paper III June 2012]
(A) Histogram (B) Mean
(C) Entropy (D) Covariance

5. The quantiser in an image-compression system is a      [Paper III June 2012]
(A) lossy element which exploits the psychovisual redundancy
(B) lossless element which exploits the psychovisual redundancy
(C) lossy element which exploits the statistical redundancy
(D) lossless element which exploits the statistical redundancy

6. The perspective projection matrix, on the view plane z = d where the centre of projection is the origin (0, 0, 0) shall be [Paper III June 2012]

7. If a and b are the end points of a line, then which one of the following is true?   [Paper III June 2012]
(A) If both end points are left, right, above or below the window, the line is invisible.
(B) If both end points are left, right, above or below the window, the line is completely visible.
(C) If both end points are left, right, above or below the window, the line is trivially visible.
(D) If both end points are left, right, above or below the window, the line is trivially invisible.

8. Halftoning is defined as                      [Paper III June 2012]
(A) a technique to obtain increased visual resolution using multiple intensity levels.
(B) a technique for using minimum number of intensity levels to obtain increased visual resolution.
(C) a technique to obtain increased visual resolution using maximum number of intensity levels.
(D) a technique for using appropriate number intensity levels to obtain increased visual resolution.

SOLUTIONS

1. A

2. B
The Mandelbrot set is the set of values of c in the complex plane for which the orbit of 0 under iteration of the complex quadratic polynomial z_n+1 = z_n² + c remains bounded. That is, a complex number c is part of the Mandelbrot set if, when starting with z0 = 0 and applying the iteration repeatedly, the absolute value of z_n remains bounded however large n gets.

3.

4.

5. A
Quantization, involved in image processing, is a lossy compression technique achieved by compressing a range of values to a single quantum value. When the number of discrete symbols in a given stream is reduced, the stream becomes more compressible. For example, reducing the number of colours required to represent a digital image makes it possible to reduce its file size.

• Color quantization reduces the number of colors used in an image.
• Frequency quantization: The human eye is fairly good at seeing small differences in brightness over a relatively large area, but not so good at distinguishing the exact strength of a high frequency (rapidly varying) brightness variation. This fact allows one to reduce the amount of information required by ignoring the high frequency components. This is done by simply dividing each component in the frequency domain by a constant for that component, and then rounding to the nearest integer.

6.

7. A

8.
Halftone is the reprographic technique that simulates continuous tone imagery through the use of dots, varying either in size, in shape or in spacing. "Halftone" can also be used to refer specifically to the image that is produced by this process.
Most photographs, paintings, or similar pictorial works reproduced in books, magazines and newspapers are printed as halftones. In a halftone, the continuous tones of the picture being reproduced are broken into a series of equally spaced dots of varying size, printed with only one color of ink. The outcome exploits an optical illusion: the tiny halftone dots are blended into smooth tones by the human eye.

Theory of Computation and Compiler Design 02

11. The equivalent grammar corresponding to the grammar  G : S → aA, A → BB, B → aBb | ϵ is                                                                                                 [Paper III June 2012]

(A) S →  aA,     A →  BB,     B →  aBb

(B) S → a | aA,    A → BB,     B → aBb | ab

(C) S → a | aA,    A → BB | B,     B → aBb

(D) S → a | aA,    A → BB | B,     B → aBb | ab

12. Consider the regular expression (a + b) (a + b) … (a + b) (n-times). The minimum number of states in finite automaton that recognizes the language represented by this regular expression contains                                                                      [Paper III June 2012]

(A) n states                  (B) n + 1 states

(C) n + 2 states            (D) 2n states

13. The following CFG S → aB | bA, A → a | as | bAA, B → b | bs | aBB  

generates strings of terminals that have                        [Paper III June 2012]

(A) odd number of a’s and odd number of b’s

(B) even number of a’s and even number of b’s

(C) equal number of a’s and b’s

(D) not equal number of a’s and b’s

14. The regular expression for the following DFA is      [Paper III June 2012]

(A) ab*(b + aa*b)*           (B) a*b(b + aa*b)*

(C) a*b(b* + aa*b)           (D) a*b(b * + aa*b)*

15. Match the following:                      [Paper III June 2012]

(i) Regular Grammar                           (a) Pushdown automaton

(ii) Context free Grammar                   (b) Linear bounded automaton

(iii) Unrestricted Grammar                  (c) Deterministic finite automaton

(iv) Context Sensitive Grammar          (d) Turing machine

(i)         (ii)        (iii)       (iv)

(A)       (c)        (a)        (b)       (d)

(B)       (c)        (a)        (d)       (b)

(C)       (c)        (b)        (a)       (d)

(D)       (c)        (b)        (d)       (a)

16. Consider the following statements:           [Paper II June 2012]
I. Recursive languages are closed under complementation.
II. Recursively enumerable languages are closed under union.
III. Recursively enumerable languages are closed under complementation.
Which of the above statements are true?

(A) I only                    (B) I and II

(C) I and III                (D) II and III

SOLUTIONS

11. D

Strings that are legal according to the given grammar is a, aab, aabab etc

Out of the options the grammar that can produce all these strings is D

Option B seems to be correct in first look, but fails to produce  aab.

12.

13.

14. D

15. B

Grammar Type	Language	machine
Type 0	Recurssively Enumerable/ Un restricted/ Phase structured/ Semithus	Turing Machine
Type 1	Context Sensitive	Linear Bounded Automata
Type 2	Context Free	Pushdown Automata
Type 3	Regular	Finite Automata

16. B

Recursively enumerable languages are closed under the following operations:

• Kleene star L*
• concatenation of L and P
• union of L and P
• intersection L and P.

Recursive languages are closed under the following operations:

• Kleene star L*
• Concatenation L and P
• Union L and P
• Intersection L and P
• Complement of L
• Set difference L - P

So only Statements I and II are true.

Data Structures 02

11. Which one of the following binary search tree is optimal, if probabilities of successful search and unsuccessful search are same?                 [Paper III June 2012]

12. The strategy used to reduce the number of tree branches and the number of static evaluations applied in case of a game tree is                                 [Paper III June 2012]

(A) Minmax strategy

(B) Alpha-beta pruning strategy

(C) Constraint satisfaction strategy

(D) Static max strategy

13. The postfix expression AB + CD – * can be evaluated using a

[Paper II June 2012]

(A) stack                     (B) tree

(C) queue                    (D) linked list

14. The post order traversal of a binary tree is DEBFCA. Find out the preorder traversal.

[Paper II June 2012]

(A) ABFCDE

(B) ADBFEC

(C) ABDECF

(D) None of the above

15. A binary search tree is a binary tree:    [Paper II June 2012]

(A) All items in the left subtree are less than root

(B) All items in the right subtree are greater than or equal to the root

(C) Each subtree is itself a binary search tree

(D) All of the above

16. Leaves of which of the following trees are at the same level?

[Paper II June 2012]

(A) Binary tree                      (B) B-tree

(C) AVL-tree                        (D) Expression tree

17. A / B+ tree index is to be built on the name attribute of the relation STUDENT. Assume that all students names are of length 8 bytes, disk block are of size 512 bytes and index pointers are of size 4 bytes. Given this scenario what would be the best choice of the degree (i.e. the number of pointers per node) of the B+ tree?            [Paper II June 2012]

(A) 16             (B) 42

(C) 43             (D) 44

18. The Inorder traversal of the tree will yield a sorted listing of elements of tree in

[Paper II June 2012]

(A) Binary tree

(B) Binary search tree

(C) Heaps

(D) None of the above

19. Which of the following data structure is linear type?          [Paper II June 2012]

(A) Strings

(B) Lists

(C) Queues

(D) All of the above

20. To represent hierarchical relationship between elements, which data structure is suitable? 
[Paper II June 2012]

(A) Dequeue             (B) Priority

(C) Tree                    (D) All of the above

SOLUTIONS

11. D

This tree is optimal because the distance to the leaf nodes is minimum.

12. B

Minimax is a decision rule used in decision theory, game theory for minimizing the possible loss for a worst case (maximum loss) scenario. Originally formulated for two-player zero-sum game theory, covering both the cases where players take alternate moves and those where they make simultaneous moves, it has also been extended to more complex games and to general decision making in the presence of uncertainty.

Alpha-beta pruning is a procedure to reduce the amount of computation and searching during minimax. It seeks to decrease the number of nodes that are evaluated by the minimax algorithm in its search tree. It is an adversarial search algorithm used commonly for machine playing of two-player games (Tic-tac-toe, Chess, Go, etc.). It stops completely evaluating a move when at least one possibility has been found that proves the move to be worse than a previously examined move. 

13. A

14.

15. D

16. B
A B-tree is a tree data structure that keeps data sorted and allows searches, sequential access, insertions, and deletions in logarithmic time. The B-tree is a generalization of a binary search tree in that a node can have more than two children. A B-tree is kept balanced by requiring that all leaf nodes be at the same depth.
An AVL tree is a self-balancing binary search tree in which the heights of the two child subtrees of any node differ by at most one.
An expression tree is a specific application of a binary tree to evaluate certain expressions. 

17.

18. B

19. D

20. C