** Complete Solved Paper with Explanations** ( UGC NET January 2017 Computer Science & Application- Paper-II)

Here I provide the complete solutions and explanations of Paper-II of UGC NET January 2017 in Computer Science & Applications. Due care has been taken while solving the questions, if some mistake is found, we are always ready for discussion.

1. Consider a sequence F₀₀ defined as:

Then what shall be the set of values of the sequence F₀₀?

(a) (1, 110, 1200)

(b) (1, 110, 600, 1200)

(c) (1, 2, 55, 110, 600, 1200)

(d) (1, 55, 110, 600, 1200)

Solution: F00(2) = (10*F00(1) + 100)/ F00(0)
                        = 110
              F00(3) = (10*F00(2) + 100)/F00(1)
                        = 1200
              F00(4) = (10*F00(3) + 100)/F00(2)
                        = 110
Since the values keep on repeating after these three values, the set of values for F00 will be {1, 110, 1200}
Ans: (A)


2. Match the following:

List-I                  List-II

a. Absurd          i. Clearly impossible being

contrary to some evident truth.

b. Ambiguous   ii. Capable of more than one

interpretation or meaning.

c. Axiom            iii. An assertion that is accepted

and used without a proof.

d. Conjecture    iv. An opinion Preferably based

on some experience or wisdom.

Codes:

     a   b   c    d

(A) i    ii   iii   iv

(B) i    iii  iv   ii

(C) ii   iii  iv   i

(D) ii   i    iii   iv

This is the simple word-meaning problem. Answer is Option (A).

3. The functions mapping R into R are defined as:

f(x) = x³-4x, g(x)=1/(x²+1) and h(x)=x⁴

Then find the value of the following composite functions:

hog(x) and hogof(x)

(A) (x²+1)⁴ and [(x³-4x)²+1]⁴

(B) (x²+1)⁴ and [(x³-4x)²+1]^{- 4}

(C) (x²+1)^{- 4} and [(x³-4x)²+1]⁴

(D) (x²+1)^{‑ 4} and [(x³-4x)²+1]^{- 4}

Solution: h0g(x)= h(1/(x²+1) ) = (x²+1)^{‑ 4} 

h0g0f(x) = h0g(x³-4x) = h( (x³-4x)²+1)) = [(x³-4x)²+1]^{- 4}

^{Correct option is (D)}

4. How many multiples of 6 are there between the following pairs of numbers?
0 and 100 and -6 and 34
(A) 16 and 6
(B) 17 and 6
(C) 17 and 7
(D) 16 and 7

Solution: To find out the number of multiples from 1 to 100, we need to divide 100 by 6. We get 16.3, we need to take lower bound of this. Since the range starts from 0, we need to add this too. Total numbers will be 17.


From 0 to 34, there will be (5+1) multiples. Since -6 is also a multiple, total number of multiples will be 7.
Correct option is (C).

5. Consider a Hamiltonian Graph G with no loops or parallel edges and with |V(G)|=n≥3. Then which of the following is true?
(A) deg(v) ≥ n/2 for each vertex v.
(B) |E(G)| ≥ 1/2(n-1)(n-2)+2
(C) deg(v)+deg(w) ≥ n whenever v and w are not connected by an edge.
(D) All of the above

Solution: Wikipedia says: In the mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a Hamiltonian path that is a cycle.
Since, Hamiltonian cycle satisfies all the properties given in the options. Correct option is (D)

6. In propositional logic if (P→Q)˄(R→S) and (P˅R) are two premises such that

Y is the premise:

(A) P˅R

(B) P˅S

(C) Q˅R

(D) Q˅S

Solution: (P→Q)˄(R→S)  means if P is true, then Q has to be true, and if R is true then S has to be true.

In the second statement, it says that P or Q is true, it means either Q or S will be true. 

Correct option is (D).

7. ECL is the fastest of all logic families. High Speed in ECL is possible because transistors are used in difference amplifier configuration, in which they are never driven into ...............

(A) Race condition

(B) Saturation

(C) Delay

(D) High impedance

Solution: ECL is fastest logic family among all and this is due to avoidance of saturation region for application.

Ans: (B)

8. A binary 3-bit down counter uses J-K flip-flops, FFi with inputs Ji, Ki and outputs Qi, i=0,1,2 respectively. The minimized expression for the input from following, is

I. J₀=K₀=0

II. J₀=K₀=1

III. J₁=K₁=Q₀

IV. J₁=K₁=Q'₀

V. J₂=K₂=Q₁Q₀

Vl. J₂=K₂=Q'₁Q'₀

(A) I, Ill, V

(B) I, IV, VI

(C) Il, III, V

(D) Il, IV, Vl

Solution: Ans: (D)

9. Convert the octal number 0.4051 into its equivalent decimal number.

(A) 0.5100098

(B) 0.2096

(C) 0.52

(D) 0.4192

Solution: Step 1:Take the given octal number.

Step 2: Find out the number of digits in the number

Step 3: Let it have n digits.

Step 4: Multiply each digit in the number with 8^n-1,when the digit is in the nth position.

Step 5: Add all digits after multiplication.

Step 6: The resultant is the equivalent decimal to the given octal number.

If octal number contains a decimal point

Step 7: Let m digits are there after the decimal

Step 8: Multiply each digit after decimal with ,when the digit is the mth position.

Ans: (A)

10. The hexadecimal equivalent of the octal number 2357 is:

(A) 2EE

(B) 2FF

(C) 4EF

(D) 4FE

Solution: Step 1: Consider the given hexadecimal number

Step 2: First count the number of digits in the number

Step 3: If n is the position of the digit from the right end then multiply each digit with 16^n-1

Step 4: Add the terms after multiplication

Step 5: Resultant is the equivalent decimal form

Step 6: Divide the decimal number with 8

Step 7: Note down the remainder

Step 8: Continue step 6 and 7 with the quotient, until the quotient is zero

Step 9: Write the remainders in reverse order

Step 10: The obtained number is the required result.

Ans: (C)

11. Which of the following cannot be passed to a function in C++?

(A) Constant

(B) Structure

(C) Array

(D) Header file

Ans: (D)

12. Which one of the following is correct for overloaded functions in C++?

(A) Compiler sets up a separate function for every definition of function.

(B) Compiler does not set up a separate function for every definition of function.

(C) Overloaded functions cannot handle different types of objects.

(D) Overloaded functions cannot have same number of arguments.

Solution: When you call an overloaded function or operator, the compiler determines the most appropriate definition to use by comparing the argument types you used to call the function or operator with the parameter types specified in the definitions. The process of selecting the most appropriate overloaded function or operator is called overload resolution.

Ans: (A)

13. Which of the following storage classes have global visibility in C/C++?

(A) Auto

(B) Extern

(C) Static

(D) Register

Ans: (B)

14. Which of the following operators cannot be overloaded in C/C++?

(A) Bitwise right shift assignment

(B) Address of

(C) Indirection

(D) Structure reference

Solution: Ans: (D)

15. If X is a binary number which is power of 2, then the value of

X&(X-1) is:

(A) 11....11

(B) 00.....00

(C) 100.....0

(D) 000.....1

Solution: A number X which is a power of 2 will have 1 at MSB and all other bits 0. In that way, X-1, will have all its bit 0 except for its MSB which is 0. If we take bitwise AND of these two numbers, it will be all 0's.

Ans: (B)

16. An attribute A of datatype varchar(20) has value 'Ram' and the attribute B of datatype char(20) has value 'Sita' in oracle. The attribute A has .......... memory spaces and B has .......... memory spaces.

(A) 20, 20

(B) 3, 20

(C) 3, 4

(D) 20, 4

Solution: In varchar, the size of the string is determined by the actual size of the string not by its allocated space. So, in this question, "Ram" will be of size 3, but in case of char, the specified space is the actual size.

Ans: (B)

17. Integrity constraints ensure that changes made to the database by authorized users do not result into loss of data consistency. Which of the following statement(s) is (are) true w.r.t. the examples of integrity constraints?

(A) An instructor Id. No. cannot be null, provided Instructor Id. No. being primary key.

(B) No two citizens have same Adhar-Id.

(C) Budget of a company must be zero.

(1) (A), (B) and (C) are true.

(2) (A) false, (B) and (C) are true.

(3) (A) and (B) are true; (C) false.

(4) (A), (B) and (C) are false.

Solution: Answer is Option (3). No Solution Required!

18. Let M and N be two entities in an E-R diagram with simple single valued attributes. R₁ and R₂ are two relationships between M and N, whereas

R₁ is one-to-many and R₂ is many-to-many.

The minimum number of tables required to represent M, N, R₁ and R₂ in the relational model are ..........

(A) 4

(B) 6

(C) 7

(D) 3

Solution: Strong entities E1 and E2 are represented as separate tables.

In addition to that many-to-many relationships(R2) must be converted as seperate table by having primary keys of E1 and E2 as foreign keys.

One-to-many relationship (R1) must be transferred to ‘many’ side table(i.e. E2) by having primary key of one side(E1) as foreign key( this way we need not to make a seperate table for R1).

Correct option is (D).

19. Consider a schema R(MNPQ) and functional dependencies M→N, P→Q. Then the decomposition of R into R₁(MN) and R₂(PQ) is .............

(A) Dependency preserving but not lossless join.

(B) Dependency preserving and lossless join

(C) Lossless join but not dependency preserving

(D) Neither dependency preserving nor lossless join.

Solution: As we know, the common attributes between R1 and R2 should be a key for any one of the relations, then the decomposition is said to be a lossless one. But here there is no common attribute, so its not a lossless decomposition. In addition to that, both dependencies are preserved in the given decomposition.

Ans: (A)

20. The order of a leaf node in a B+ tree is the maximum number of children it can have. Suppose that block size is 1 kilobytes, the child pointer takes 7 bytes long and search field value takes 14 bytes long. The order of the leaf node is ............

(A) 16

(B) 63

(C) 64

(D) 65

Solution: Disk Block size = 1024 bytes Data Record Pointer size, r = 7 bytes Value size, V = 9 bytes Disk Block ptr, P = 6 bytes
Let order of leaf be m. A leaf node in B+ tree contains at most m record pointers, at most m values, and one disk block pointer. r*m + V*m + p <= 1024 16m <= 1018 m =< 63

Ans: (B)

21.

Which of the following is true for computation time in insertion, deletion and finding maximum and minimum element in a sorted array?
(A) Insertion-O(1), Deletion-O(1), Maximum-O(1), Minimum-O(1)
(B) Insertion-O(1), Deletion-O(1), Maximum-O(n), Minimum-O(n)
(C) Insertion-O(n), Deletion-O(n), Maximum-O(1), Minimum-O(1)
(D) Insertion-O(n), Deletion-O(n), Maximum-O(n), Minimum-O(n)

Solution: To insert an element in a sorted array, in the worst case we may have to scan the whole array, so the complexity will be O(n). Same is the case for deletion.
However finding the maximum/minimum element is trivial. It takes O(1) time.
Ans: (C)

22.

The seven elements A, B, C, D, E, F and G are pushed onto a stack in reverse order, i.e., starting from G. The stack is popped five times and each element is inserted into a queue. Two elements are deleted from the queue and pushed back onto the stack. Now, one element is popped from the stack. The popped item is ...................
(A) A
(B) B
(C) F
(D) G

Solution: This is how the stack will look after inserting the elements:

A

B

C

D

E

F

G

After popping these elements and inserting them into a queue, this is how the queue will look:

A

B

C

D

E

Now, A and B are deleted from the queue and inserted into the stack.

B

A

F

G

Now the item to be popped is B.

Ans: (B)

23. Which of the following is a valid heap?

Solution: Since, in figure A, 8 comes below 4, it is not a valid heap.

In figure C, 7 comes below 1, it is not a valid heap, same is the case for figure D.

Ans: (B)

24. If h is chosen from a universal collection of hash functions and is used to hash n keys into a table of size m, where n≤m, the expected number of collisions involving a particular key x is less than ...................
(A) 1
(B) 1/n
(C) 1/m
(D) n/m

Solution: Expected number of collisions is 1.

Ans: (A)

25. Which of the following statements is false?
(A) Optimal binary search tree construction can be performed efficiently using dynamic programming.
(B) Breadth-first search cannot be used to find connected components of a graph.
(C) Given the prefix and postfix walks of a binary tree, the tree cannot be re-constructed uniquely.
(D) Depth-first-search can be used to find the components of a graph.
(A) A
(B) B
(C) C
(D) D

Ans: (B)

26. Match the following Layers and Protocols for a user browsing with SSL:
a. Application of layer i. TCP
b. Transport layer ii. IP
c. Network layer iii. PPP
d. Datalink layer iv. HTTP
Codes:
a b c d
(A) iv i ii iii
(B) iii ii i iv
(C) ii iii iv i
(D) iii i iv ii

Ans: (A)

27. The maximum size of the data that the application layer can pass on to the TCP layer below is .........
(A) 216 bytes
(B) 216 bytes + TCP header length
(C) 216 bytes - TCP header length
(D) 215 bytes

Solution: The default TCP Maximum Segment Size is 536. Where a host wishes to set the maximum segment size to a value other than the default, the maximum segment size is specified as a TCP option, initially in the TCP SYN packet during the TCP handshake. Because the maximum segment size parameter is controlled by a TCP option, a host can change the value in any later segment.

Ans: (Marks To All)

28. A packet whose destination is outside the local TCP/IP network segment is sent to ..............
(A) File server
(B) DNS server
(C) DHCP server
(D) Default gateway

Solution: A packet whose destination is outside the local TCP/IP network segment is sent to default gateway.

Ans: (D)

29. Distance vector routing algorithm is a dynamic routing algorithm. The routing tables in distance vector routing algorithm are updated ...........
(A) automatically
(B) by server
(C) by exchanging information with neighbour nodes.
(D) with back up database

Solution: A distance-vector routing protocol requires that a router inform its neighbors of topology changes periodically.

Ans: (C)

30. In link state routing algorithm after the construction of link state packets, new routes are computed using:
(A) DES algorithm
(B) Dijkstra's algorithm
(C) RSA algorithm
(D) Packets

Solution: In link state routing algorithm we uUse a routing protocol to collect the whole network topology , then we obtain destination reachability information as well as link weights/states and then we have to compute shortest paths using Dijkstra’s algorithm from a node to all other nodes.

Ans: (B)

31. Which of the following strings would match the regular expression: p+[3-5]*[xyz]?
I. p443y
Il. p6y
III. 3xyz
IV. p35z
V. p353535x
Vl. ppp5
(A) I, III and Vl only
(B) IV, V and VI only
(C) II, IV and V only
(D) I, IV and V only

Solution: Since, p has to be present as the first character of each string, III string is not valid and also p occurs only once, so VI becomes invalid.
Since 6 is not a part of the set, II string is also invalid.

Ans: (D)

32. Consider the following assembly language instructions:
mov al, 15
mov ah, 15
xor al, al
mov cl, 3
shr ax, cl
add al, 90H
adc ah, 0

What is the value in ax register after execution of above instructions?
(A) 0270H
(B) 0170H
(C) 01E0H
(D) 0370H

Ans: (A)

33. Consider the following statements related to compiler construction:
I. Lexical Analysis is specified by context-free grammars and implemented by pushdown automata.
II. Syntax Analysis is specified by regular expressions and implemented by finite-state machine.
Which of the above statement(s) is/are correct?
(A) Only l
(B) Only ll
(C) Both I and II
(D) Neither I nor Il

Solution:
Lexical Analysis is specified by regular expressions and implemented by finite-state machine. SyntaxAnalysis is specified by context-free grammars and implemented by pushdown automata.

Ans: (D)

34. The contents of Register (BL) and Register (AL) of 8085 microprocessor are 49H and 3AH respectively. The contents of AL, the status of carry flag (CF) and sign flag (SF) after executing 'SUB AL, BL' assembly language instruction, are
(A) AL=0FH; CF=1; SF=1
(B) AL=F0H; CF=0; SF=0
(C) AL=F1H; CF=1; SF=1
(D) AL=1FH; CF=1; SF=1

Ans: (A)

35. Which of the following statement(s) regarding a linker software is/are true?
I. A function of a linker is to combine several object modules into a single load module.
II. A function of a linker is to replace absolute references in an object module by symbolic references to locations in other modules.
(A) Only I
(B) Only II
(C) Both I and II
(D) Neither I nor Il

Solution: Both functions are performed by Linkers.
Ans: (C)

36. There are three processes P1, P2 and P3 sharing a semaphore for synchronising a variable. Initial value of semaphore is one. Assume that negative value of semaphore tells us how many processes are waiting in queue. Processes access the semaphore in following order:
(a) P2 needs to access
(b) P1 needs to access
(c) P3 needs to access
(d) P2 exits critical section
(e) Pi exits critical section
The final value of semaphore will be:


(A) 0
(B) 1
(C) -1
(D) -2

Solution: Initially the value of semaphore S is 1.
After (a) S=0
(b) S=-1
(c) S= -2
(d) S= -1
(e) S= 0


Ans: (A)

37. In a paging system, it takes 30 ns to search translation Look-aside Buffer (TLB) and 90 ns to access the main memory. If the TLB hit ratio is 70%, the effective memory access time is:
(A) 48 ns
(B) 147 ns
(C) 120 ns
(D) 84 ns
Solution: We can assume single level paging and TLB look and page table look happens sequentially meaning TLB look time is to be considered even for TLB miss. On a TLB miss we need to access main memory for getting the physical address for the page table before doing the actual memory access for the data.

Effective access time = Hit ratio*Time during hit + Miss Ratio * Time During Miss

=0.7*(30+90) + 0.3 (30+90+90)

= 84 + 63

=147 ns

Ans: (B)

38. Match the following w.r.t. Input/Output management:
List-l List-II
a. Device controller i. Extracts information from the
controller register and store it
in data buffer
b. Device driver ii. I/O scheduling
c. Interrupt handler iii. Performs data transfer
d. Kernel I/O subsystem iv. Processing of I/O request
Codes:
a b c d
(A) iii iv i ii
(B) ii i iv iii
(C) iv i ii iii
(D) i iii iv ii

Ans: (D)

39. Which of the following scheduling algorithms may cause starvation?
a. First-come-first-served
b. Round Robin
c. Priority
d. Shortest process next
e. Shortest remaining time first
(A) a, c and e
(B) c, d and e
(C) b, d and e
(D) b, c and d
Solution: Out of the given protocols, only round-robin is sure of not getting the starvation. However, we can assume FCFS to be starvation-free (Only by looking at the options).


Ans: (B)

40. Distributed operating systems consist of:
(A) Loosely coupled O.S. software on a loosely coupled hardware
(B) Loosely coupled O.S. software on a tightly coupled hardware
(C) Tightly coupled O.S. software on a loosely coupled hardware
(D) Tightly coupled O.S. software on a tightly coupled hardware

Solution: These systems are referred as loosely coupled systems where each processor has its own local memory and processors communicate with one another through various communication lines, such as high speed buses or telephone lines. By loosely coupled systems, we mean that such computers possess no hardware connections at the CPU - memory bus level, but are connected by external interfaces that run under the control of software.


Ans: (A)

41. Software Engineering is an engineering discipline that is concerned with:
(A) how computer systems work.
(B) theories and methods that underlie computers and software systems.
(C) all aspects of software production.
(D) all aspects of computer-based systems development, including hardware, software and process engineering.

Ans: (C)

42. Which of the following is not one of three software product aspects addressed by McCall's software quality factors?
(A) Ability to undergo change.
(B) Adaptability to new environments.
(C) Operational characteristics
(D) Production costs and scheduling
Ans: (D)

43. Which of the following statement(s) is/are true with respect to software architecture?
S1: Coupling is a measure of how well the things grouped together in a module belong together logically.
S2: Cohesion is a measure of the degree of interaction between software modules.
S3: If coupling is low and cohesion is high then it is easier to change one module without affecting others.
(A) Only S1 and S2
(B) Only S3
(C) All of S1, S2 and S3
(D) Only S1

Solution: Cohesion is a measure of how well the things grouped together in a module belong together logically. Coupling is a measure of the degree of interaction between software modules. If coupling is low and cohesion is high then it is easier to change one module without affecting others.


Ans: (B)

44. The Prototyping model of software development is:
(A) a reasonable approach when requirements are well-defined.
(B) a useful approach when a customer cannot define requirements clearly.
(C) the best approach to use for projects with large development teams.
(D) a risky model that rarely produces a meaningful product.

Ans: (B)

45. A software design pattern used to enhance the functionality of an object at run-time is:
(A) Adapter
(B) Decorator
(C) Delegation
(D) Proxy

Ans: (B)

46. Match the following:

List-l                              List-II

a. Affiliate marketing   i. Vendors ask partners to place

logos on partner's site. If customers

click, come to vendors and buy.

b. Viral Marketing        ii. Spread your brand on the net by

word-of-mouth. Receivers will send

your information to their friends.

c. Group Purchasing iii. Aggregating the demands of small

buyers to get a large volume. Then

negotiate a price.

d. Bartering Online      iv. Exchanging surplus Products and

services with the process administered

completely online by an intermediary.

Company receives “points” for its contribution.

Codes:

     a  b    c   d

(A) i   ii    iii   iv

(B) i   iii   ii    iv

(C) iii  ii   iv   i

(D) ii  iii   i    iv

Ans: (A)

47. ............ refers loosely to the process of semi-automatically analysing large databases to find useful patterns.
(A) Datamining
(B) Data Warehousing
(C) DBMS
(D) Data mirroring

Solution: Data Mining refers loosely to the process of semi-automatically analysing large databases to find useful patterns.



Ans: (A)

48. Which of the following is/are true w.r.t. applications of mobile computing?
(A) Travelling of salesman
(B) Location awareness services
(1) (A) true; (B) false
(2) Both (A) and (B) are true.
(3) Both (A) and (B) are false.
(4) (A) false; (B) true.


Ans: (2)




49. In 3G network, W-CDMA is also known as UMTS. The minimum spectrum allocation required for W-CDMA is ..........
(A) 2 MHz
(B) 20 KHz
(C) 5 KHz
(D) 5 MHz

Ans: (D)

50. Which of the following statements is/are true w.r.t. Enterprise Resource Planning (ERP)?
(A) ERP automates and integrates majority of business processes.
(B) ERP provides access to information in a Real Time Environment.
(C) ERP is inexpensive to implement.
(1) (A), (B) and (C) are false.
(2) (A) and (B) false; (C) true.
(3) (A) and (B) true; (C) false
(4) (A) true; (B) and (C) are false


Ans: (3)

*Mock Test-2 With Answers*

Q. No. 1 to 25 carry 1 mark each

1. Which of the following are tautologies?

(i) [p ^ (p⇒q)] ⇒q

(ii) (p⇒q) ⇔(q’⇒p’)

(iii) [q’^(p⇒q)] ⇒p’

(a) Only (i) and (ii) are true

(b) Only (ii) and (iii) are true

(c) Only (i) and (iii) are true

(d) All are true

Ans: (D)

2. Consider the expressions given below:

E1: (0+1)*1(0+1)*1(0+1)*

E2: (0+1)*10*1(0+1)*

E3: 0*10*1(0+1)*

E4: (0+1)*10*10*

Which of the given expressions are equivalent?

(a) E1 and E2                      (b) E1, E2 and E3

(c) E2 and E3                       (d) E1, E2, E3 and E4

Ans: (D)

3. Consider the Hasse diagram given below:

The Hasse diagram represents a

(a) Poset which is not a lattice

(b) A lattice which is not complemented

(c) Complemented lattice

(d) A Boolean algebra

Ans: (C)

4. Simplify using k-map and represent the result in SOP form

y= f(A, B, C, D) = Σ(0, 1, 2, 6, 7, 10, 14) + Σd(3, 8, 11, 15) where Σd represents don’t care conditions.

(a) A +BC                             (b) C’ + A’B’

(c) A + C’D’                          (d) C’ + B’D’

Ans: (C)

5. Individual stages of data path have following latencies:

IF	ID	EX	MEM	WB
300 ps	400ps	350ps	500ps	100ps

What is the clock time of the pipelined processor?

(a) 500 ps                             (b) 1650 ps

(c) 1050ps                            (d) None of these

Ans: (A)

6. Consider the following program:

main()

{

int i=257;

int *iptr = &i;

printf(“%d%d”, *((char*)iptr, *((char*)iptr+1);

}

What should be the output of the above program?

(a) 257, 257                         (b) -128, 127

(c) 127, 127                         (d) None of these

Ans: (D)

7. Suppose that a code consists of the following code-words:

{ 000000, 000111, 111000, 111111}

Consider the following statements:

(i) The hamming distance of the code is 3

(ii) A single bit error can be detected

(iii) 000100 received with two bit errors can be corrected

Which of the given statement(s) is/are true?

(a) only (i)

(b) Only (i) and (ii)

(c) All (i), (ii) and (iii)

(d) Only (ii) and (iii)

Ans: (B)

8. An 8-bit number with binary value 10010010 is to be encoded using an even parity hamming code. What is the binary value after encoding?

(a) 101000110010                             (b) 111100110010

(c) 110100110011                              (d) 100000110010

Ans: (B)

9.  Which of the following model is not preferred when the requirements are indicating a complex system to be built?

(a) Waterfall model

(b) Evolutionary model

(c) Prototype model

(d) Iterative Enhancement model

Ans: (A)

10. A shopkeeper advertises that a customer can have his/her hamburger with or without any or all of the following: catsup, mustard, mayonnaise, lettuce, tomato, onion, pickle, cheese or mushrooms. How many different kind of hamburgers orders are possible?

(a) 9!                     (b) 2⁹

(c) 2!9!                  (d) 9!/2!

Ans: (B)

11. Convert the following statement into symbolic form:

“Nobody can ignore her”

Where I(x) = x can ignore her

(a) (∃x)I(x)                          (b) ∀x[~I(x)]

(c) ∀x[I(x)]                          (d) None of these

Ans: (B)

12. The minimal DFA that recognizes

L= {w| w∈{0,1}* & 1<=|w| mod 5 <=3}

has how many states?

(a) 3                       (b) 4

(c) 5                       (d) 6

Ans: (C)

13. Consider an empty stack of integers. Let the numbers 1, 2, 3, 4, 5, 6, 7,8 to be pushed on to the stack only in the order they appeared from left to right. Let U indicate PUSH and O indicates POP operation and print the value. What will be the possible order printed if the given set of operation is UOUUOUOUUOUOOUOO?

(a) 12345678                       (b) 13467582

(c) 23456718                       (d) None of these

Ans: (B)

14. Using the generator (division) polynomial x⁴+ x+ 1 for CRC, what frame will be transmitted for the data M= x⁷ + x⁵ + x³ + 1

(a) 101010011001                             (b) 101010010100

(c) 101010011111                              (d) 101010011100

Ans: (D)

15. Match the following CMM levels given in Table 1 with the characterizations given in Table 2 by using codes

Table 1                                                                                  Table 2

A. Initial                                                                                1. Process Control

B. Repeatable                                                                       2. Process Definition

C. Defined                                                                           3. Adhoc Process

D. Managed                                                                        4. Basic project management

E. Optimized                                                                      5. Process measurement

    A B C D E

(a) 1 2 3 4 5

(b) 3 2 4 1 5

(c) 3 4 2 5 1

(d) 3 5 2 4 1

Ans: (C)

16. Find the time complexity for the given program-

main ()

{

                int n;

                int x = 0;

                while (n<1)

(              x=x +1;

                n= n/2;

                }

}

Where n is a positive integer?

(a) O(n)                                (b) O(logn)

(c) O(1)                                (d) None of these

Ans: (C)

17. Which of the following CNF is equivalent to the given formula?

(~p) =>  ~(q ^~(r ∨ ~(s^u)))

(a) p^q^r∨~r∨~s

(b) p∨r∨q∨s∨~u

(c) p∨~q∨r∨~s∨~u

(d) None of these

Ans: (C)

18. The number of asymmetric relations on a set of m elements:

(a) 2 ^m(m-1)/2                                      (b) 3^m(m-1)/2

(c) 2^m3^m(m-1)/2                          (d) 2^m3^m(m-1)/2

Ans: (B)

19. Consider the following grammar G-

G: S⇒ SS|a|ε

Which of the following is true about G?

(a) L(G) is accepted by DFA

(b) G is a regular grammar

(c) If x ∈ L(G) & y ∈ L(G) then xy may or may not belong to L(G)

(d) L(G) is finite

Ans: (A)

20. Suppose that you collect the following timing data for a program as a function of the input size N.

N	Time
100	0.01sec
400	0.16sec
1600	3.00sec
6400	41sec
25600	656sec

Estimate the running time of program (in seconds) as a function of N.

(a) T(n)= ϴ(n)                    (b) T(n) = ϴ(n³)

(c) T(n) = ϴ(n²)                  (d) T(n)= ϴ(nlogn)

Ans: (C)

21. Consider the following program-

main ()

{

int i= 5;

{

int i=7, j=8;

printf( “%d%d”, i, j);

}

printf(“%d%d”, i, j);

}

Which of the following is true about this program?

(a) It prints 7858                               (b) It prints 5858

(c) Compilation Error                      (d) None of these

Ans: (C)

22. You are given a hash table with n keys and m slots with the simple uniform hashing assumption (each key is equally likely to be hashed into each slot. Collisions are resolved by chaining). Thus the probability that no key hashes into the first slot is:

(a) 1/ mⁿ                              (b) 1/(m-1)ⁿ

(c) (m-1)ⁿ/mⁿ                     (d) None of these

Ans: (C)

23. Consider the following program segment:

P(S1);

a++;

P(S2);

V++;

V(S2);

V(S1);

(S1, S2 are semaphores). All variables are auto. Now, consider two threads running this fragment of code simultaneously.

Which of the following statements is true?

(a) Deadlock is possible

(b) No situation where deadlock could occur

(c) We cannot identify that the deadlock is possible or not

(d) None of these

Ans: (B)

24. Consider the m-way relationship R between entity sets E1, E2, ....,En. What is the minimum and maximum number of attributes that could form the key for a relation derived from R respectively?

(a) n, n+1                             (b) n-1, n

(c) n-1, n+1                         (d) None of these

Ans: (B)

25. Which one of the following is used at high load situations?

(a) Pure ALOHA

(b) Slotted ALOHA

(c) Non-persistent CSMA

(d) Both (a) and (b)

Ans: (C)

Q. No. 26 to 55 carry 2 marks each

26. Consider the Matrix A =

Which of the following are Eigen values of the matrix A 2 ?

(a) 1, 1, 1              (c) 1, 1, 9

(b) 2, 2, 2             (d) 9, 9, 9

Ans: (B)

27. Which of the following sets is a lattice with respect to divisibility?

(i) A 1 = { 1, 2, 4, 5, 20 }

(ii) A 2 = { 2, 4, 8, 10, 20, 40 }

(iii) A 3 = { 1, 2, 3, 4, 5, 6, 10, 15, 20, 30, 60 }

(a) Only (i) and (ii)            (c) Only (ii) and (iii)

(b) Only (iii)                        (d) All (i), (ii), and (iii)

Ans: (D)

28. What is the running time of the following function (specified as a function of the input value l)?

void function (int l)

{

int a = 1;

int b = 1;

while (b &lt; = l)

{

a++;

b = b + a;

printf(“*”);

}

}

(a) O(l log l)                         (c) O(l)

(b) O(√l)                               (d) None of these

Ans: (C)

29. Consider the given syntax directed translation

E → E 1 #T {E.Val = E 1 .Val*T.Val}

E → T {E.Val = T.Val}

T → T 1 &amp;F {(1)}

T → F {T.Val = F.Val}

F → num {F.Val = num}

If the expression 6#11&3#18&2#4&2

Evaluate to 576. Then which of the following correctly represents (1)?

(a) T.Val = T.Val – F.Val

(b) T.Val = T.Val/F.Val

(c) T.Val = T.Val + F.Val

(d) T.Val = T.Val * F.Val

Ans: (A)

30. Consider the following grammar over the terminals +, - (negation operator) and id

S → E

E → E + E | -E | id

Determine the number of states (such that i 0 , i 1, i 2 ,….) in the above given LR parser

(a) 6                       (c) 7

(b) 8                       (d) 9

Ans: (B)

31. Consider a demand paging system with a paging disk that has an average access and transfer time of 20ms. Addresses are translated through page table in memory, with an access time of 1sec per memory access. Thus, each memory reference through the page table takes two accesses. To improve this time, we have added an associative memory that reduces access time to one memory reference, if the page table entry is in the associative memory. Assume that 80% of the accesses are in associative memory and that of the remaining 10% (or 2% of the total) causes page faults. What is the effective memory access time?

(a) 312.2sec        (c) 366.8sec

(b) 538.9sec         (d) None of these

Ans: (D)

32. A system has four process and five allocatable resources, the current allocation and maximum needs are as follows

What is the smallest value of x for which system is in safe state?

(a) 0                       (c) 1

(b) 2                       (d) More than 3

Ans: (B)

Common Data Question for Q.no 33 & 34.

Consider the following preemptive priority scheduling algorithm based on dynamically changing priorities. Larger priority implies higher priority. When a process is waiting for the CPU (in the ready queue, but not running), its priority changes at a rate ‘a’; when its is running, its priority changes at a rate ‘b’. All processes are given a priority of zero when they enter the ready queue for the first time. The parameters a and b can be set to give many scheduling algorithms.

33. What is the algorithm that results from b>a>0

(a) FCFS

(b) LIFO

(c) Both (a) and (b)

(d) No algorithm apply for the above condition

Ans: (A)

34. What is the algorithm resulting from a<b<0

(a) FCFC

(b) LIFO

(c) Both (a) and (b)

(d) No algorithm apply for above condition

Ans: (B)

35. Consider the following functions:

I. f(x) = |x|

II. f(x) = x³ +6

Which of the above functions is neither one-to-one nor onto?

(a) I only                                              (b) II only

(c) Both (I) and (II)                           (d) None of these

Ans: (A)

36. In a college dance function there are 20 girls and 20 boys. Consider a match of the students into 20 girl/boy couples. Of course not all of the couples go out on the dance floor for each song. Zero or more couples may be selected for a particular song for dancing and we can call such a set of couples as a “dancing set”. Then, how many such dancing sets can there be?

(a) 20! X 2²⁰

(b) 2²⁰

(c) 20! X 20! X 2²⁰ x 2²⁰

(d) None of these

Ans: (A)

37. What happens if the schedule executing using Basic Timestamp Ordering protocol:

S: r1(A)r2(B)w1(C)r3(B)r3(C)w2(B)w3(A)

With TS values (T1, T2, T3) = (100, 200, 300). Which of the following is true?

(a) Roll back T1

(b) Roll back T2

(c) Roll back T3

(d) Roll back T1, T2 and T3

Ans: (B)

38. Consider a token ring in which there are 20 stations, and the length of the ring in a 40 Mbps token ring network is 18000 meters. The speed of propagation is 3x10⁸ m/s. Each station holds the token for 10 micro-sec. Calculate the total time for a 10 byte token to go around the ring.

(a) 0.40 x 10^-4 sec

(b) 0.60 x 10^-4 sec

(c) 0.80 x 10^-4 sec

(d) 1.00 x 10^-4 sec

Ans: (D)

.

39. Consider the given below IP header without options. The header is divided into 16-bit section.

Calculate the checksum in the hexadecimal

(a) 743E

(b) 8BC1

(c) 744E

(d) 8BB1

Ans: (D)

40. A Table T 1 in a relational database has the following rows and columns

The following sequence of SQL statements was successfully executed on table T 1

UPDATE T 1 SET Balance = Balance + 7000;

SELECT AVG(Balance) FROM T 1 ;

What is the output of the SELECT statement?

(a) 13,000

(b) 15,334

(c) 23,000

(d) None of these

Ans: (D)

41. Which of the following language is/are regular:

L 1 : the language of strings with no occurrences of the substring “010”.

L 2 : the language of strings with more occurrences of 0 than 1.

L 3 : the language of strings whose length is a multiple of 3.

L 4 : the language of strings whose number of occurrence of zero minus number of occurrences of 1 is a multiple of 3.

L 5 : the language of strings of terminals and non-terminals that can appear on the parsing stack during an LR(1) parse ( stack is read from the bottom of the stack ).

Here the alphabet is the set of terminals and non-terminals of the grammar being passed

(a) L 1, L 4 and L 5

(b) L 1, L 2 and L 4

(c) L 2, L 3 and L 4

(d) L 1, L 3, L 4 and L 5

Ans: (D)

42. A shift Reduce parser carries out the actions specified with in braces immediately after reducing the corresponding rule of grammar

A → aaB {print “x”}

A → b { print “+”}

B → Ac{ print “-“}

B→ c{print “/”}

What is the translation of aaaabcc using the syntax directed translation scheme described by the above rules.

(a) +-x-x

(b) x-x-+

(c) x-+-x

(d) None of these

Ans: (A)

Common Data Question for Q. No. 43 and 44

Consider the following table TAB1

TAB1

COL1	COL2
A	10
B	20
C	30
A	10
D	40
C	30

43. Assuming that the following results are desired:

TAB

COL1	COL2
A	10
B	20
C	30
D	40

Which of the following given statements will produce the above results?

(a) SELECT UNIQUE *FROM TAB1

(b) SELECT DISTINCT *FROM TAB1

(c) SELECT UNIQUE (*) FROM TAB1

(d) SELECT DISTINCT (*) FROM TAB1

Ans: (B)

44. Assuming table TAB1 contains 100 rows. Which of the following queries will return only half of the rows available:

(a) SELECT * FROM TAB1 FIND FIRST 50 ROWS

(b) SELECT * FROM TAB1 FETCH FIRST 50 ROWS ONLY

(c) SELECT * FROM TAB1 WHILE ROW.NUM<50

(d) SELECT * FROM TAB1 MAXROWS 50

Ans: (B)

45. Consider the following code segment

# include <stdlib.h>;

int *f1 (void)

{

int x = 10;

return &x;

}

int *f2 (void)

{

int *ptr;

*ptr = 10;

return ptr;

}

int *f3 (void)

{

int *ptr;

ptr = malloc (size of *ptr);

return ptr;

}

Which of these function uses pointers incorrectly?

(a) f1 only

(b) f1 and f2 only

(c) f1 and f3 only

(d) f1, f2 and f3

Ans: (B)

Common Data Question 46 and 47.

Consider the following given C program

# include <stdio.h>

main ()

{

float sum = 0.0, j = 1.0, i = 2.0;

while (i/j &gt; 0.001)

{

j = j + j;

sum = sum + i/j;

printf(“%f\n”,sum);

}

}

46. How many lines of output does the program produce?

(a) 0-9

(b) 10-19

(c) 20-29

(d) More than 39

Ans: (B)

47. For the C code shown above, which of the following integer that best approximates the last number printed?

(a) 0

(b) 1

(c) 2

(d) 3

Ans: (C)

48. The employee information of an Organization is stored in the relation : 

Employee (name, sex, salary, deptname) 

Consider the following SQL query:

Select deptname from Employee  

Where sex = ‘M’   

group by deptname  

having avg (salary) > {select avg (salary) from Employee} 

Output of the given query corresponds to 

(A) Average salary of employee more than average salary of the organization.  

(B) Average salary less than average salary of the organization.  

(C) Average salary of employee equal to average salary of the organization. 

(D) Average salary of male employees in a department is more than average salary of the organization.

Ans: (D)

49. For a database relation R(a, b, c, d) where the domains of a, b, c, d include only the atomic values. The functional dependency a → c, b → d holds in the following relation 

(A) In 1NF not in 2NF 

(B) In 2NF not in 3NF 

(C) In 3NF  

(D) In 1NF

Ans: (A)

50. A pushdown automaton M = (Q, Σ, Γ, δ, q0, z, F) is set to be deterministic subject to which of          the following condition(s), for every q ∈ Q, a ∈ Σ ∪ {λ} and b ∈ Γ  

(s1) δ(q, a, b) contains at most one element  

(s2) if δ(q, λ, b) is not empty then δ(q, c, b) must be empty for every        c ∈ Σ  

(A) only s1  

(B) only s2  

(C) both s1 and s2 

(D) neither s1 nor s2

Ans: (C)

51. For every context free grammar (G) there exists an algorithm that passes any w ∈ L(G) in number of steps proportional to 

(A) ln|w| 

(B) |w| 

(C) |w|²

(D) |w|³

Ans: (D)

52. The simplified function in product of sums of Boolean function F(W, X, Y, Z) = Σ(0, 1, 2, 5, 8, 9, 10) is 

(A) (W' + X') (Y' + Z') (X' + Z)  

(B) (W' + X') (Y' + Z') (X' + Z')  

(C) (W' + X') (Y' + Z) (X' + Z)  

(D) (W' + X') (Y + Z') (X' + Z)

Ans: (A)

53. What will be the output of the following segment of the program?  

main( )  

{   

char *s = “hello world”;    

int i = 7;    

printf(“%, *s”, i, s);   

}  

(A) Syntax error  

(B) hello w  

(C) hello 

(D) o world

54. Consider the following processes with time slice of 4 milliseconds (I/O requests are ignored):

The average turn around time of these processes will be   

(A) 19.25 milliseconds  

(B) 18.25 milliseconds  

(C) 19.5 milliseconds  

(D) 18.5 milliseconds

Ans: (B)

55. A job has four pages A, B, C, D and the main memory has two page frames only. The job needs to process its pages in following order: 

ABACABDBACD  

Assuming that a page interrupt occurs when a new page is brought in the main memory, irrespective of whether the page is swapped out or not. 

The number of page interrupts in FIFO and LRU page replacement algorithms are   

(A) 9 and 7 

(B) 7 and 6  

(C) 9 and 8 

(D) 8 and 6

Ans: (C)

Q. No. 56 to Q. No. 60 carries 1 mark each

56. Consider given sentence having one or two idioms.

The two women are so jealous that at the drop of a hat they start insulting each other.

Which of the following best describe the meaning of the idiom?

(a) On every occasion

(b) For no reason at all

(c) When a hat is dropped

(d) Very rarely

Ans: (A)

57. Eight friends Ankit, Arjit, Ram, Mohan, Simran, Rupali, Pinki and Monu are sitting in a circle facing the centre. Ram is sitting between Pinki and Simran, Ankit is third to the left of Ram and second to the right of Monu. Rupali is sitting between Ankit and Pinki, and Ram and Mohan are not sitting opposite to each other. Who is second right to the Rupali?

(a) Mohan                           (c) Ram

(b) Simran                           (d) Arjit

Ans: (B)

58. In a class 40% of the students enrolled for Math and 70% enrolled for Hindi. If 15% of the students enrolled for both Math and Hindi, what percent of the student of the class did not enroll for either of the two subjects?

(a) 5%                   (c) 95%

(b) 0%                    (d) None of these

Ans: (A)

59. Pick the Oddman out:

(a) Wisdom; folly              (c) Friendship; enmity

(b) Often; seldom            (d) Loyalty; treachery

Ans: (C)

60. Fill in the blank with the appropriate word:

Value of currency was increasing which ultimately kick started ________ in economy.

(a) Deflation

(b) Depreciation

(c) Disinflation

(d) None of these is appropriate word

Ans: (A)

Q. No. 61 to Q. No. 65 carries 2 marks each

61. Today is 8/10/12. Keeping this figure 81012 in mind, I have arrived at the following sequence 1, 1, 3, 10, __. Which of the following number can fill the blank?

(a) 10812                              (c) 108

(b) 12                                    (d) 65

Ans: (D)

62. In a bike race five participants Ajay, Akhilesh, Riya, Sapna, Sumit take part. Track 1 is extreme left and track 5 is extreme right. The following conditions exist:

(i) Akhilesh and Sumit are not cycling adjacent to each other.

(ii) Sapna is not in one of the extreme tracks.

(iii) Ajay is to the left of Riya.

If Sapna is left to Ajay, then Sapna could be in

(a) Track 3 only                  (c) Track 2 only

(b) Track 2 or 3                  (d) None of these

Ans: (B)

63. Sum of square of two numbers X and Y is less or equal to 100. How many sets of integers solutions of X and Y are possible?

(a) 299

(b) 297

(c) 315

(d) None of these

Ans: (D)

64. There are 6 tasks and 6 students. Task 1 cannot be assigned to either student 1 or student 2. Task 2 must be assigned to either student 3 or student 4. Every student is to be assigned a task. In how many ways can the assignment be done?

(a) 180

(b) 192

(c) 360

(d) 144

Ans: (D)

65. Consider two trains A and B at stations x and y with a distance of 150 km between them. A travels with a speed of 60 km/hr and B travels with a speed of 100 km/hr towards A on parallel track. A has started with a delay of 6 minutes compared to that of B. Find the distance at which the two trains will meet when measured from station y.

(a) 97.5                 (b) 26.5

(c) 92.5                 (d) 24.5

Ans: (A)