Question Booklet Series : a Sr. No.

OCET-2012

Question Booklet Series : A Sr. No. :

Important :Please consult your Admit Card / Roll No. Slip before filling your Roll Number on the Test Booklet and Answer Sheet.

Roll No.

Answer Sheet Serial No.

Signature of the Candidate :

Subject : M.E. (Computer Science and Engineering/Information Technology)

Time : 90 minutes Number of Questions : 75 Maximum Marks : 75

DO NOT OPEN THE SEAL ON THE BOOKLET UNTIL ASKED TO DO SO

INSTRUCTIONS

1. Write your Roll No. on the Question Booklet and also on the OMR Answer Sheet in the space provided and nowhere else.

2. Enter the Subject and Series Code of Question Booklet on the OMR Answer Sheet. Darken the corresponding bubble with Black Ball Point /Black Gel pen.

3. Do not make any identification mark on the Answer Sheet or Question Booklet.

4. To open the Question Booklet remove the paper seal (s) gently when asked to do so.

5. Please check that this Question Booklet contains 75 questions. In case of any discrepancy, inform the Assistant Superintendent within 10 minutes of the start of test.

6. Each question has four alternative answers (A, B, C, D) of which only one is correct. For each question,

darken only one bubble (A or B or C or D), whichever you think is the correct answer, on the Answer Sheet

withBlack Ball Point / Black Gel pen.

7. If you do not want to answer a question, leave all the bubbles corresponding to that question blank in the

Answer Sheet. No marks will be deducted in such cases.

8. Darken the bubbles in the OMR Answer Sheet according to the Serial No. of the questions given in the

Question Booklet.

9. Negative marking will be adopted for evaluation i.e., 1/4th of the marks of the question will be deducted for each

wrong answer. A wrong answer means incorrect answer or wrong filling of bubble.

10. For calculations, use of simple log tables is permitted. Borrowing of log tables and any other material is not allowed.

11. For rough work only the sheets marked “Rough Work” at the end of the Question Booklet be used.

12. The Answer Sheet is designed for computer evaluation. Therefore, if you do not follow the instructions

given on the Answer Sheet, it may make evaluation by the computer difficult. Any resultant loss to the

candidate on the above account, i.e., not following the instructions completely, shall be of the

candidate only.

13. After the test, hand over the Question Booklet and the Answer Sheet to the Assistant Superintendent on duty.

14. In no case the Answer Sheet, the Question Booklet, or its part or any material copied/noted from this

Booklet is to be taken out of the examination hall. Any candidate found doing so, would be expelled from

the examination.

15. A candidate who creates disturbance of any kind or changes his/her seat or is found in possession of any

paper possibly of any assistance or found giving or receiving assistance or found using any other unfair

means during the examination will be expelled from the examination by the Centre Superintendent /

Observer whose decision shall be final.

16. Telecommunication equipment such as pager, cellular phone, wireless, scanner, etc., is not

permitted inside the examination hall. Use of calculators is not allowed.

M.E.(Comp. Sc. and Engg./Inf. Tech.)FRH-41350-A 2

M.E.(Comp. Sc. and Engg./Inf. Tech.)FRH-41350-A 3 [Turn over

M.E.(Computer Science and Engineering / Information Technology)/A

1. To implement Dijkastra's shortest path algorithm on unweighted graphs so that it runs

in linear time, the data structure to be used is :

(A) Queue (B) Stack

2. The following numbers are inserted into an empty binary search tree in the given order :

10, 1, 3, 5, 15, 12, 16. What is the height of the binary search tree (the height is the

maximum distance of a leaf node from the root) ?

(A) 2 (B) 3

3. How many distinct binary search trees can be created out of 4 distinct keys ?

(A) 5 (B) 14

4. A Priority-Queue is implemented as a Max-Heap. Initially, it has 5 elements. The levelorder

traversal of the heap is given below : 10, 8, 5, 3, 2. Two new elements 1 and 7 are

inserted in the heap in that order. The level-order traversal of the heap after the

insertion of the elements is :

(A) 10,8,7,5,3,2,1, (B) 10,8,7,2,3,1,5

5. Give a 16 bit value 1001101011001101. What operation must be applied in order to

complement middle 8 bits ?

(A) XOR 0000111111110000 (B) AND 1111000000001111

6. Number of swaps required to sort n elements using selection sort in the worst case :

(A) (n2) (B) (n log n)

7. Suppose an unpipelined processor with 25ns cycle time is divided into 5 pipeline stages

with latencies of 5,7,3,6 and 4 ns. If pipeline latch latency is 1 ns, what is cycle time of

resulting processor ?

(A) 8 ns (B) 9 ns

M.E.(Comp. Sc. and Engg./Inf. Tech.)FRH-41350-A 4

8. Consider the following C function :

int f(int n)

{ staticinti = 1;

if (n > = 5) return n;

n = n + i;

i ++;

return f(n);

}

The value returned by f(1) is

(A) 5 (B) 6

9. If the following program is executed and user entered number 4 as input, then output is :

#include <stdio.h

void main( )

{ int a, b = 8 ;

scanf("%d", & a);

if (a = 0) b*=2; else b/=2;

printf("%d",b++);

}

(A) 16 (B) 8

10. If in a program it is required that a local variable must retain its value during various

function calls to it, its storage must be :

(A) Static (B) Register

11. The output of the following program will be :

#include<stdio.h

void main ( )

{ char *ptr;ptr="OCET";putchar(*ptr);}

(A) T (B) O

M.E.(Comp. Sc. and Engg./Inf. Tech.)FRH-41350-A 5 [Turn over

12. Consider the following C program :

main ( )

{ int x, y, m, n ;

scanf ("%d %d", &x, &y); / * Assume x > 0 and y > 0* /

m = x; n = y ;

while (m ! = n)

{ if (m >n)

m = m — n;

else n = n - m ;

}

printf("%d",n); }

The program computes

(A) x + y, using repeated subtraction (B) x mod y using repeated subtraction

13. A computer has 32 bit instructions and 12 bit address. If there are 250 two address

instructions how many maximum one address instructions can be formulated ?

(A) 26576 (B) 27456

14. Booth's coding in 8 bits for (-57)10 is :

(A) 0-100+1000 (B) 0-100+100-1

15. If (73)x(in base-x number system) is equal to (54)y (in base-y number system), the possible

values of x and y are :

(A) 8,16 (B) 10,12

16. A machine stores floating point numbers in 7-bit word. The first bit is stored for sign of

the number, the next three for the biased exponent and the next three for the magnitude

of the mantissa. In order to represent 35.35 in the above representation, the error would

be :

(A) underflow (B) overflow

M.E.(Comp. Sc. and Engg./Inf. Tech.)FRH-41350-A 6

17. The probability that two friends share the same birth month is :

(A) 1/6 (B) 1/12

18. Suppose A is a finite set with n elements. The number of elements in the largest

equivalence relation of A is :

(A) 1 (B) n

19. The number of distinct relations on a set of 3 elements is :

(A) 8 (B) 9

20. In a population of N families, 50% of the families have three children, 30% of the

families have two children and the remaining families have one child. What is the

probability that a randomly picked child belongs to a family with two children ?

(A) 3/23 (B) 6/23

21. Two 16:1 and one 2:1 multiplexers can be connected to form a :

(A) 8:1 multiplexer (B) 16:1 multiplexer

22. If P1 is NP complete and there is polynomial time reduction of P1 to P2, then P2 is :

(A) NP complete (B) Not necessarily NP complete

23. A PDM behaves like a TM when the number of auxiliary memory it has, is :

(A) 0 (B) 1 or more

24. A grammar that is both left and right recursive for a non-terminal, is :

(A) Ambiguous

(B) Unambiguous

(D) None of the above

25. Which one of the following regular expressions is NOT equivalent to the regular

expression (a + b + c)* ?

(A) (a* + b* + c*)* (B) (a* b* c*)*

M.E.(Comp. Sc. and Engg./Inf. Tech.)FRH-41350-A 7 [Turn over

26. A subnet has been assigned a subnet mask of 255.255.255.192. What is the maximum

number of hosts that can belong to this subnet ?

(A) 14 (B) 30

27. The address resolution protocol (ARP) is used for :

(A) Finding the IP address from the DNS

(B) Finding the IP address of the default gateway

(D) Finding the MAC address that corresponds to an IP address

28. One of the header fields in an IP datagram is the time to live(TTL) field. Which of the

following best explains the need for the field ?

(A) It can be used to prioritize the packets

(B) It can be used to reduce delays

(D) It can be used to prevent packet looping

29. Suppose the round trip propagation delay for a 10 Mbps Ethernet having 48-bit jamming

signal is 46.4 ms. The minimum frame size is :

(A) 94 (B) 416

30. In a network of LANs connected by bridges, packets are sent from one LAN to another

through intermediate bridges. Since more than one path may exist between two LANs,

packets may have to be routed through multiple bridges. Why is the spanning tree algorithm

used for bridge-routing ?

(A) For shortest path routing between LANs (B) For avoiding loops in the routing paths

31. Which one of the following statements is FALSE ?

(A) Any relation with two attributes is in BCNF

(B) A relation in which every key has only one attribute is in 2NF

(D) A prime attribute can be transitively dependent on a key in a BCNF relation

32. Assume transaction A holds a shared lock R. If transaction B also requests for a shared

lock on R, it will :

(A) result in a deadlock situation (B) immediately be granted

M.E.(Comp. Sc. and Engg./Inf. Tech.)FRH-41350-A 8

33. The fourth normal form (4NF) is concerned with dependencies between the elements of

compound keys composed of :

(A) one attribute (B) two attributes

34. If a table has Functional dependency from A to B and A is not the candidate key, then

which of the following is true ?

(A) Table is not in 2NF (B) Table involves some redundancy

35. Let E1 and E2 be the two entities in an ER diagram with simple single valued attributes.

R1 and R2 are the relationships between E1 and E2, where R1 is one-to-many and R2 is

many-to-many. R1 and R2 do not have any attributes of their own. What is the maximum

number of tables required to represent this situation in the relational model ?

(A) 2 (B) 3

36. Consider the following where clause

WHERE A.no=B.no(+)

The above outer join lists :

(A) All matching & non-matching rows of table B

(B) All matching & non-matching rows of table A

(D) All non-matching rows of table A

37. After executing an UPDATE statement, the developer codes a PL/SQL block to perform

an operation based on SQL%ROWCOUNT. What data is returned by the

SQL%ROWCOUNT operation ?

(A) A numeric value representing the number of rows updated

(B) A Boolean value representing the success or failure of the update

(D) A LONG value containing all data from the table

38. Which of the following concurrency control protocols ensure both conflict serializability

and freedom from deadlock ?

(i) 2-phase locking

(ii) Time Stamp ordering

(A) (i) only (B) (ii) only

M.E.(Comp. Sc. and Engg./Inf. Tech.)FRH-41350-A 9 [Turn over

39. The physical location of a record is determined by a mathematical formula that transforms

a file key into a record location is :

(A) a B-tree file (B) an indexed file

40. Which of the following is true concerning open-source DBMS ?

(A) Is not competitive against PC-oriented packages and is fully SQL compliant

(B) Is competitive against PC-oriented packages and is not fully SQL compliant

(D) Is free or nearly free database software whose source code is publicly available

41. Which of the following types of maintenance takes the maximum chunk of total

maintenance effort in typical commercial application ?

(A) Adaptive maintenance (B) Corrective maintenance

42. What is the output of the following program :

#include<stdio.h

main( )

{

enum status {low, medium, high};

enum status rain; rain = 1 ;

if(rain = = low)

printf("Rain =%d", rain);

}

(A) 0 (B) 1

43. What is the availability of a software with the following reliability figures ? Mean Time

Between Failure (MTBF) = 25 days, Mean Time To Repair (MTTR) = 6 hours :

(A) 1% (B) 24%

44. Which of the following statements are valid in C, if p is a pointer ?

(A) p = &x (B) &x++

45. An abstract data type is :

(A) Same as abstract class

(B) A data type which can not be instantiated

(D) All of the above

M.E.(Comp. Sc. and Engg./Inf. Tech.)FRH-41350-A 10

46. C++ encourages structuring a software as a collection of components that are :

(A) Highly cohesive and loosely coupled

(B) Not highly cohesive but loosely coupled

(D) Not highly cohesive but tightly coupled

47. Disk scheduling is used to decide :

(A) Which disk should be accessed next

(B) The order in which disk access requests must be serviced

(D) None of these

48. A system has 6 tape drives, with N processes competing for them. Each process may

need 3 tape drives. The maximum value of N for which the system is guaranteed to be

deadlock free is :

(A) 4 (B) 3

49. The size of the decoder to select all memory devices of capacity 256 × 4 each to make a

memory of 4K × 8-bit memory is :

(A) 3:8 (B) 4:16

50. Which of the following keyword is used to achieve run time polymorphism ?

(A) const (B) explicit

51. Which one of these will be handled at the HIGHEST priority ?

(A) Interrupt from Hard Disk (B) Interrupt from Mouse

52. Which languages need heap allocation in the run-time environment ?

(A) Those that support recursion (B) Those that use dynamic scoping

53. HTML has language elements which permit certain actions other than describing the

structure of the web document. Which one of the following actions is NOT supported by

pure HTML (without any server or client side scripting) pages ?

(A) Embedding web objects from different sites into the same page

(B) Refresh the page automatically after a specified interval

(D) Display the client time as part of the page

M.E.(Comp. Sc. and Engg./Inf. Tech.)FRH-41350-A 11 [Turn over

54. How much time would it take to transmit a 1024*1024 image with 256 gray levels using a

56K baud modem ? Transmission is accomplished in packets consisting of a start bit, a

byte (8 bits) of information, and a stop bit :

(A) 157.25 sec (B) 167.25 sec

55. A pure ALOHA network transmits 200 bit frames on a shared channel of 200 kbps. What

is throughput of a system (all stations together) produces 250 frames per second ?

(A) 80% (B) 70.4%

56. Which one of the following is NOT shared by the threads of the same process ?

(A) Stack (B) Address Space

57. A software organization has been assessed at SEI CMM Level 4. Which of the following

does the organization need to practice beside Process Change Management and

Technology Change Management in order to achieve Level 5 ?

(A) Defect Detection (B) Defect Prevention

58. Suppose that two parties A and B wish to setup a common secret key (D-H key) between

themselves using the Diffle-Hellman key exchange technique. They agree on 7 as the

modulus and 3 as the primitive root. Party A chooses 2 and party B chooses 5 as their

respective secrets. Their D-H key is :

(A) 3 (B) 4

59. Consider the following message M = 1010001101. The cyclic redundancy check (CRC)

for this message using the divisor polynomial x5 + x4 +x2 + 1 is :

(A) 01110 (B) 01011

60. Which of the following statements is FALSE regarding a bridge ?

(A) Bridge is a layer 2 device

(B) Bridge reduces collision domain

(D) Bridge reduces broadcast domain

M.E.(Comp. Sc. and Engg./Inf. Tech.)FRH-41350-A 12

61. A host is transmitting a video over the network. How does the transport layer allow this

host to use multiple applications to transmit other data at the same time as the video

transmission ?

(A) It uses error control mechanisms

(B) It uses a connectionless protocol only for multiple simultaneous transmissions

(D) It uses multiple port numbers

62. Which of the following statements is TRUE about CSMA/CD ?

(A) IEEE 802.11 wireless LAN runs CSMA/CD protocol

(B) Ethernet is not based on CSMA/CD protocol

(D) There is no contention in a CSMA/CD network

63. A system uses FIFO policy for page replacement. It has 4 page frames with no pages

loaded to begin with. The system first accesses 100 distinct pages in some order and

then accesses the same 100 pages but now in the reverse order. How many page faults

will occur ?

(A) 196 (B) 192

64. Which of the following is the programmable internal timer ?

(A) 8250 (B) 8251

65. The clock interrupt handle on computer requires 2 msec per clock tick. The clock runs at

60hz. What percent of CPU time is devoted to the clock ?

(A) 1.2 (B) 7.5

66. Memory access in RISC architecture is limited to instructions :

(A) CALL and RET (B) PUSH and POP

67. When a subroutine is called, the address of the instruction following the CALL instructions

stored in/on the :

(A) stack pointer (B) accumulator

68. The main memory of a computer has 2m blocks while the cache has 2c blocks. If the

cache uses set associative mapping scheme with two blocks per set, then block k of the

main memory maps to the set :

(A) (k mod m) of cache (B) (k mode c) of cache

M.E.(Comp. Sc. and Engg./Inf. Tech.)FRH-41350-A 13 [Turn over

69. Registers which are partially visible to users and used to hold conditional codes are

known as :

(A) PC (B) Memory address registers

70. The access time of a cache memory is 100 ns and that of main memory is 1000 ns. It is