Archive for the ‘GATE Previous Year Question Papers’ Category

Dear friends, you can discuss answers through comments. And please give your answers ( with explanation if possible ), you will help others. If you feel that an answer is wrong, please discuss it.

1 —  25 carry one mark each.

1. In a compiler, keywords of a language are recognized during
(A) parsing of the program
(B) the code generation
(C) the lexical analysis of the program
(D) dataflow analysis

2. A layer-4 firewall (a device that can look at all protocol headers up to the transport layer) CANNOT
(A) block entire HTTP traffic during 9:00PM and 5 :0OAM
(B) block all ICMP traffic
(C) stop incoming traffic from a specific IP address but allow outgoing traffic to the same IP address
(D) block TCP traffic from a specific user on a multi-user system during 9:00PM and 5:00AM

3. If two fair coins are flipped and at least one of the outcomes is known to be a head, what is the probability that both outcomes are heads?
(A) 1/3
(B) 1/4
(C) 1/2
(D) 2/3

4. Consider different activities related to email.
m1: Send an email from a mail client to a mail server
m2: Download an email from mailbox server to a mail client
m3: Checking email in a web browser
Which is the application level protocol used in each activity?
(A) ml: HTTP  m2: SMTP  m3: POP
(B) ml: SMTP  m2: FTP     m3: HTTP
(C) ml: SMTP  m2: POP    m3: HTTP
(D) ml: POP    m2: SMTP  m3: IMAP

5. A company needs to develop a strategy for software product development for which it has a choice of two programming languages L1 and L2. The number of lines of code (LOC) developed using L2 is estimated to be twice the LOC developed with Ll. The product will have to be maintained for five years. Various parameters for the company are given in the table below.
Parameter
Language L1
Language L2
Man years needed for development
LOC/10000
LOC/10000
Development cost per man year
Rs. 10,00,000
Rs. 7,50,000
Maintenance time
5 years
5 years
Cost of maintenance per year
Rs. 1,00,000
Rs. 50,000
Total cost of the project includes cost of development and maintenance. What is the LOC for L1 for which the cost of the project using L1 is equal to the cost of the project using L2?
(A) 4000 
(B) 5000
(C) 4333
(D) 4667

6. Let the time taken to switch between user and kernel modes of execution be t1 while the time taken to switch between two processes be t2. Which of the following is TRUE?
(A) t1 > t2
(B) t1 = t2 
(C) t1 < t2
(D) nothing can be said about the relation betweent1 and t2

7. A company needs to develop digital signal processing software for one of its newest inventions. The software is expected to have 40000 lines of code. The company needs to determine the effort in person-months needed to develop this software using the basic COCOMO model. The multiplicative factor for this model is given as 2.8 for the software development on embedded systems, while the exponentiation factor is given as 1.20. What is the estimated effort in person -months?
(A) 234.25
(B) 932.50
(C) 287.80
(D) 122.40

8. Which of the following pairs have DIFFERENT expressive power?
(A) Deterministic finite automata (DFA) and Non—deterministic finite automata (NFA)
(B) Deterministic push down automata (DPDA) and Non-deterministic push down automata (NPDA)
(C) Deterministic single-tape Turing machine and Non-deterministic single-tape Turing machine
(D) Single-tape Turing machine and multi-tape Turing machine

9. HTML (HyperText Markup Language) 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) Embed web objects from different sites into the same page
(B) Refresh the page automatically after a specified interval
(C) Automatically redirect to another page upon download
(D) Display the client time as part of the page

10. Which one of the following is NOT desired in a good Software Requirement Specifications (SRS) document’?
(A) Functional Requirements
(B) Non-Functional Requirements
(C) Goals of Implementation
(D) Algorithms for Software Implementation

11. A computer handles several interrupt sources of which the following are relevant for this question.
• Interrupt from CPU temperature sensor (raises interrupt if CPU temperature is too high)
• Interrupt from Mouse (raises interrupt if the mouse is moved or a button is pressed)
• Interrupt from Keyboard (raises interrupt when a key is pressed or released)
• Interrupt from Hard Disk (raises interrupt when a disk read is completed)
Which one of these will be handled at the HIGHEST priority?
(A) Interrupt from Hard Disk
(B) Interrupt from Mouse
(C) Interrupt from Keyboard
(D) Interrupt from CPU temperature sensor
  
12. Consider a relational table with a single record for each registered student with the following attributes.
1. Registration_Num: Unique registration number of each registered student
2. UID: Unique identity number, unique at the national level for each citizen
3. BdnkAccount_Num: Unique account number at the bank. A student can have multiple accounts or joint accounts. This attribute stores the primary account number.
4. Name: Name of the student
5. Hoszel_Room: Room number of the hostel
Which of the following options is INCORRECT?
(A) BankAccount_Num is a candidate key
(B) Registration_Num can be a primary key
(C) UID is a candidate key if all students are from the same country
(D) If S is a superkey such that that SUID is NULL then SUID is also a superkey

 13
Which one of the following circuits is NOT equivalent to a 2-input XNOR (exclusive NOR) gate?
14. The simplified SOP (Sum of Product) form of the Boolean expression
is
(A)
(B)
(c)  
(D)

15. The minimum number of D flip—flops needed to design a mod-258 counter is
(A) 9
(B) 8
(C) 512
(D) 258

 16. A thread is usually defined as a “light weight process” because an operating system (OS) maintains
smaller data structures for a thread than for a process. In relation to this, which of the following is TRUE?
(A) On per-thread basis, the OS maintains only CPU register state
(B) The OS does not maintain a separate stack for each thread
(C) On per-thread basis, the OS does not maintain virtual memory state
(D) On per-thread basis, the OS maintains only scheduling and accounting information

 17. K4 and Q3 are graphs with the following structures.
Which one of the following statements is TRUE in relation to these graphs?
(A) K4 is planar while Q3 is not
(B) Both K4 and Q3 are planar
(C) Q3 is planar while K3 is not
(D) Neither K4 nor Q3 is planar

18. If the difference between the expectation of the square of a random variable and the square of the expectation of the random variable is denoted by R , then
(A) R = O
(B) R < O
(C) R ³ O
(D) R > O

 19. The lexical analysis for a modem computer language such as Java needs the power of which one of the following machine models in a necessary and sufficient sense?
(A) Finite state automata
(B) Deterministic pushdown automata
(C) Non-deterministic pushdown automata
(D) Turing machine

20. Let the page fault service time be 10 ms in a computer with average memory access time being 20 ns. If one page fault is generated for every 106 memory accesses, what is the effective access time for the memory?
(A) 21 ns
(B) 30 ns
(C) 23 ns
(D) 35 ns

21. Consider a hypothetical processor with an instruction of type LW R1 , 20 (R2), which during execution reads a 32-bit word from memory and stores it in a 32-bit register R1. The effective address of the memory location is obtained by the addition of a constant 20 and the contents of register R2. Which of the following best reflects the addressing mode implemented by this instruction for the operand in memory?
(A) Immediate Addressing
(B) Register Addressing
(C) Register Indirect Scaled Addressing
(D) Base Indexed Addressing

22. What does the following fragment of C program print?
Char c [] = “GATE2011″;
char *p = c;
printf <"%S", p + p[3] — p[1] ):
(A) GATE2011
(B) E2011
(C) 2011
(D) 011

23. A max-heap is a heap where the value of each parent is greater than or equal to the value of its children. Which of the following is a max-heap?

24. Let P be a regular language and Q be a context-free language such that Q Í  P. (For example, let P be the language represented by the regular expression p* q* and Q be { p” q” | n Î N}). Then which of the following is ALWAYS regular?
(A) P Ç Q
(B) P – Q
(C) S* – P
(D) S* – Q

25. An algorithm to find the length of the longest monotonically increasing sequence of numbers in an array A[O : n - 1] is given below.
Let Li denote the length of the longest monotonically increasing sequence starting at index i in the array.
Initialize Ln-1 =1.
For all i such that 0 £ i £ n – 2
Li =
Finally the length of the longest monotonically increasing sequence is Max (L0, L1,…….Ln-1).
Which of the following statements is TRUE?
(A) The algorithm uses dynamic programming paradigm
(B) The algorithm has a linear complexity and uses branch and bound paradigm
(C) The algorithm has a non-linear polynomial complexity and uses branch and bound paradigm
(D) The algorithm uses divide and conquer paradigm.

 26 to  55 carry two marks each.

26. Consider the languages L1. L2 and L3 as given below.
L1= {0p 1q | p, q Î N},
L2= {0p 1q | p, q Î N and p = q} and
L3 = {0p 1q 0r | p, q, r Î N and p = q = r}. Which of the following statements is NOT TRUE?
(A) Push Down Automata (PDA) can be used to recognize L1 and L2
(B) L1 is a regular language
(C) All the three languages are context free
(D) Turing machines can be used to recognize all the languages

27
Consider two binary operators ‘­’ and ‘¯’ with the precedence of operator ¯ being lower than that of the operator­. Operator ­ is right associative while operator¯ is left associative. Which one of the following represents the parse tree for expression (7¯3­4­3¯2)?

28. On a non-pipelined sequential processor, a program segment, which is a part of the interrupt service
routine, is given to transfer 500 bytes from an I/O device to memory.
Initialize the address register
Initialize the count to 500
LOOP: Load a byte from device
Store in memory at address given by address register
Increment the address register
Decrement the count
If count != 0 go to LOOP
Assume that each statement in this program is equivalent to a machine instruction which takes one clock cycle to execute if it is a non-load/store instruction. The load-store instructions take two clock cycles to execute.
The designer of the system also has an alternate approach of using the DMA controller to implement the same transfer. The DMA controller requires 20 clock cycles for initialization and other overheads. Each DMA transfer cycle takes two clock cycles to transfer one byte of data from the device to the memory.
What is the approximate speedup when the DMA controller based design is used in place of the interrupt driven program based input-output?
(A) 3.4
(B) 4.4
(C) 5.1
(D) 6.7

29. We are given a set of n distinct elements and an unlabeled binary tree with n nodes. In how many ways can we populate the tree with the given set so that it becomes a binary search tree?
(A) 0
(B) 1
(C) n!
(D)
30. Which one of the following options is CORRECT given three positive integers x, y and z , and a predicate
P(x)= -,(x=1)L”y($z(x= y*z) Þ (y = x)v(y =1))
(A) P(x) being true means that x is a prime number
(B) P(x) being true means that x is a number other than 1
(C) P(x) is always true irrespective of the value of x
(D) P(x) being true means that x has exactly two factors other than 1 and x
31. Given i=, what will be the evaluation of the definite integral  ?
(A) 0
(B) 2
(C) -i
(D) i
32. Consider a database table T containing two columns X and Y each of type integer. After the creation of the table, one record (X=1, Y=1) is inserted in the table.
Let MX and MY denote the respective maximum values of X and Y among all records in the table at any point in time. Using MX and MY, new records are inserted in the table 128 times with X and Y values being MX+1, 2*MY+1 respectively. It may be noted that each time after the insertion, values of MX and MY change.
What will be the output of the following SQL query after the steps mentioned above are carried out?
SELECT Y FROM T WHERE X=7;
(A) 127
(B) 255
(C) 129
(D) 257
33. Consider a finite sequence of random values X = [x1, x 2,...,xn ]. Let mx be the mean and sx be the standard deviation of X. Let another finite sequence Y of equal length be derived from this as yi = a * xi + b, where a and b are positive constants. Let my be the mean and sy be the standard deviation of this sequence. Which one of the following statements is INCORRECT?
(A) Index position of mode of X in X is the same as the index position of mode of Y in Y.
(B) Index position of median of X in X is the same as the index position of median of Y in Y
(C) my = amx + b
(D) sy= asx + b
34. A deck of 5 cards (each carrying a distinct number from 1 to 5) is shuffled thoroughly. Two cards are then removed one at a time from the deck. What is the probability that the two cards are selected with the number on the first card being one higher than the number on the second card?
(A) 1/5
(B) 4/25
(C) 1/4
(D) 2/5
35. Consider the following table of arrival time and burst time for three processes P0, P1 and P2.
Process
Arrival time
Burst Time
P0
0 ms
9 ms
P1
1 ms
4 ms
P2
2 ms
9 ms
The pre-emptive shortest job first scheduling algorithm is used. Scheduling is carried out only at arrival or completion of processes. What is the average waiting time for the three processes?
(A) 5.0 ms
(B) 4.33 ms
(C) 6.33 ms
(D) 7.33 ms
36. Consider evaluating the following expression tree on a machine with load-store architecture in which memory can be accessed only through load and store instructions. The variables a, b, c, d and e are initially stored in memory. The binary operators used in this expression tree can be evaluated by the machine only when the operands are in registers. The instructions produce result only in a register. If no intermediate results can be stored in memory, what is the minimum number of registers needed to evaluate this expression?
(A) 2
(B) 9
(C) 5
(D) 3
37. Which of the given options provides the increasing order of asymptotic complexity of functions f1, f2,f3, and f4?
f1(n) = 2     f2(n) = n3/2       f3(n) = n log2 n         f4(n) = nlog2 n
(A) f3, f2, f4, f1
(B) f3, f2, f1, f4
(C) f2, f3, f1, f4
(D) f2, f1, f4, f1
38. Four matrices M1, M2 , M3 and M4, of dimensions p ´ q , q ´ r , r ´ s and s ´ t respectively can be multiplied in several ways with different number of total scalar multiplications. For example when multiplied as ((M1 ´ M2) ´ (M3 ´M4)). The total number of scalar multiplications is pqr + rst + prt. When multiplied as (((M1 ´ M2) ´M3) ´M4,), the total number of scalar multiplications is pqr+ prs+ pst.
If p = 10, q = 100, r = 20, s = 5, and t = 80, then the minimum number of scalar multiplications needed is
(A) 248000
(B) 44000
(C) 19000
(D) 25000
39. Consider a relational table r with sufficient number of records, having attributes A1, A2,……An and
let 1 £  p £ n. Two queries Q1 and Q2 are given below.
Q1: where c is a constant
Q2:  where c1 and c2 are constants
The database can be configured to do ordered indexing on Ap or hashing on Ap.  Which of the following statements is TRUE?
(A) Ordered indexing will always outperform hashing for both queries
(B) Hashing will always outperform ordered indexing for both queries
(C) Hashing will outperform ordered indexing on Q1, but not on Q2
(D) Hashing will outperform ordered indexing on Q2, but not on Q1
40. Consider the matrix as given below.
Which one of the following options provides the CORRECT values of the eigenvalues of the matrix?
(A) 1, 4, 3
(B) 3, 7, 3
(C) 7, 3, 2
(D) 1,2,3
41. Consider an instruction pipeline with four stages (S1, S2, S3 and S4) each with combinational circuit only. The pipeline registers are required between each stage and at the end of the last stage.
Delays for the stages and for the pipeline registers are as given in the figure.
What is the approximate speed up of the pipeline in steady state under ideal conditions when compared to the corresponding non-pipeline implementation’?
(A) 4.0
(B) 2.5
(C) 1.1
(D) 3.0
42. Definition of a language L with alphabet {a} is given as following.
L = {ank | k > 0, and n is a positive integer constant}
What is the minimum number of states needed in a DFA to recognize L?
(A)  k+1
(B) n + 1  
(C) 2n+1  
(D) 2k+1
43. An 8KB direct-mapped write-back cache is organized as multiple blocks, each of size 32-bytes. The processor generates 32-bit addresses. The cache controller maintains the tag information for each cache block comprising of the following.
1 Valid bit
1 Modified bit
As many bits as the minimum needed to identify the memory block mapped in the cache.
What is the total size of memory needed at the cache controller to store meta-data (tags) for the cache?
(A) 4864 bits
(B) 6144 bits
(C) 6656 bits
(D) 5376 bits
44. An application loads 100 libraries at startup. Loading each library requires exactly one disk access.
The seek time of the disk to a random location is given as 10 ms. Rotational speed of disk is 6000 rpm. lf all 10() libraries are loaded from random locations on the disk, how long does it take to load all libraries? (The time to transfer data from the disk block once the head has been positioned at the start of the block may be neglected.)
(A) 0.50 s
(B) 1.50 s
(C) 1.25 s
(D) 1.00 s
45
A deterministic finite automaton (DFA) D with alphabet X å = {a, b} is given below.
Which of the following finite state machines is a valid minimal DFA which accepts the same language as D?
46. Database table by name Loan_Records is given below.
Borrower
Bank_Manager
Loan_Amount
Ramesh
Sunderajan
10000.00
Suresh
Ramgopal
5000.00
Mahesh
Sunderajan
7000.00
What is the output of the following SQL query?
SELECT count(*)
FROM (
(SELECT Borrower, Bank_Manager FROM Loan_Records) AS S
NATURAL JOIN
(SELECT Bank_Manager, Loan_Amount FROM Loan_Records) AS T
);
(A) 3
(B) 9
(C) 5
(D) 6
47. The following is the comment written for a C function.
/* This function computes the roots of a quadratic equation
a.x^2 + b.x + c = 0. The function stores two real roots
in *root1 and *root2 and returns the status of validity
of roots. It handles four different kinds of cases.
(i) When coefficient a is zero irrespective of discriminant
(ii) When discriminant is positive
(iii) When discriminant is zero
(iv) When discriminant is negative.
Only in case (ii) and (iii), the stored roots are valid.
Otherwise 0 is stored in the roots. The function returns
0 when the roots are valid and -1 otherwise.
The function also ensures root1 >= root2.
int get_QuadRoots (float a, float b, float c,
float *root1, float *root2);
*/
A software test engineer is assigned the job of doing black box testing. He comes up with the following test cases, many of which are redundant.
Test Case
Input set
Expected Output set
a
b
c
Root1
Root2
Return Value
T1
0.0
0.0
7.0
0.0
0.0
-1
T2
0.0
1.0
3.0
0.0
0.0
-1
T3
1.0
2.0
1.0
-1.0
-1.0
0
T4
4.0
-12.0
9.0
1.5
1.5
0
T5
1.0
-2.0
-3.0
3.0
-1.0
0
T6
1.0
1.0
4.0
0.0
0.0
-1
Which one of the following options provide the set of non-redundant tests using equivalence class partitioning approach from input perspective for black box testing?
(A) T1, T2, T3, T6
(B) T1, T3, T4, T5
(C) T2, T4, T5, T6
(D) T2, T3, T4, T5
Common Data Questions
Common Data for Questions 48 and 49:
Consider the following recursive C function that takes two arguments.
unsigned int foo (unsigned int n, unsigned int r) {
if (n>O) return ((n% r) + foo (n/r, r) );
else return 0;
}
48. What is the return value of the function foo when it is called as foo (345, 10)?
(A) 345
(B) 12
(C) 5
(D) 3
49. What is the return value of the function foo when it is called as foo (513 , 2) ?
(A) 9
(B) 8
(C) 5
(D) 2
Common Data for Questions 50 and 51:
Consider the following circuit involving three D-type flip-flops used in a certain type of counter configuration.
50. lf at some instance prior to the occurrence of the clock edge, P, Q and R have a value 0, 1 and 0 respectively, what shall be the value of PQR after the clock edge?
(A) 000
(B) 001
(C) 010
(D) 011
51. If all the flip-flops were reset to 0 at power on, what is the total number of distinct outputs (states) represented by PQR generated by the counter?
(A) 3
(B) 4
(C) 5
(D) 6
Linked Answer Questions
Statement for Linked Answer Questions 52 and 53:
Consider a network with five nodes, N1 to N5, as shown below.
The network uses a Distance Vector Routing protocol. Once the routes have stabilized, the distance vectors
at different nodes are as following.
N1:(0,1, 7, 8, 4)
N2: (1, 0, 6, 7, 3)
N3: (7, 6, 0, 2, 6)
N4: (8,7, 2,0,4)
N5: (4, 3, 6, 4, 0)
Each distance vector is the distance of the best known path at that instance to nodes, N1 to N5, where the distance to itself is O. Also, all links are symmetric and the cost is identical in both directions. In each round, all nodes exchange their distance vectors with their respective neighbors. Then all nodes update their distance vectors. In between two rounds, any change in cost of a link will cause the two incident nodes to change only that entry in their distance vectors.
52. The cost of link N2-N3 reduces to 2 (in both directions). After the next round of updates, what will be the new distance vector at node, N3?
(A) (3, 2, 0, 2, 5)
(B) (3, 2, 0, 2, 6)
(C) (7, 2, 0, 2, 5)
(D) (7, 2, 0, 2, 6)
53. After the update in the previous question, the link N1-N2 goes down. N2 will reflect this change immediately in its distance vector as cost, ¥. After the NEXT ROUND of update, what will be the cost to N1 in the distance vector of N3?
(A) 3
(B) 9
(C) 10
(D) ¥
Statement for Linked Answer Questions 54 and 55:
An undirected graph G(V,E) contains n (n > 2) nodes named v1,,v2,. .., vn. Two nodes vi, vj are connected if and only if 0 <| i – j | £ 2. Each edge (vi, vj)is assigned a weight i +j. A sample graph with n = 4 is shown below.
54. What will be the cost of the minimum spanning tree (MST) of such a graph with n nodes?
(A) (11 n2 -5 n)
(B) n2 – n+1
(C) 6n -11
(D) 2n +1
55. The length of the path from v5 to v6 in the MST of previous question with n = 10 is
(A) 11
(B) 25
(C) 31
(D) 41
General Aptitude (GA) Questions
 56 —  60 carry one mark each.
56. Which of the following options is the closest in the meaning to the word below:
lnexplicable
(A) lncomprehensible
(B) Indelible
(C) Inextricable
(D) Infallible
  
57. If Log (P) = (1/2) Log (Q) = (1/3) Log (R), then which of the following options is TRUE?
(A) P2= Q3R2
(B) O2= PR
(C) Q3 =R3P
(D) R = P2Q2
58. Choose the most appropriate word(s) from the options given below to complete the following sentence.
I contemplated ——— Singapore for my vacation but decided against it.
(A) to visit
(B) having to visit
(C) visiting
(D) for a visit
59. Choose the most appropriate word from the options given below to complete the following sentence.
If you arc trying to make a strong impression on your audience, you cannot do so by being understated, tentative or————–.
(A) hyperbolic
(B) restrained
(C) argumentative
(D) indifferent
60. Choose the word from the options given below that is most nearly opposite in meaning to the given word: Amalgamate
(A) merge
(B) split
(C) collect
(D) separate
 61 to  65 carry two marks each.
61. Few school curricula include a unit on how to deal with bereavement and grief, and yet all students at some point in their lives suffer from losses through death and parting.
Based on the above passage which topic would not be included in a unit on bereavement?
(A) how to write a letter of condolence
(B) what emotional stages are passed through in the healing process
(C) what the leading causes of death are
(D) how to give support to a grieving friend
  
62. P, Q, R and S are four types of dangerous microbes recently found in a human habitat. The area of each circle with its diameter printed in brackets represents the growth of a single microbe surviving human immunity system within 24 hours of entering the body. The danger to human beings varies proportionately with the toxicity, potency and growth attributed to a microbe shown in the figure
below:
A pharmaceutical company is contemplating the development of a vaccine against the most dangerous microbe. Which microbe should the company target in its first attempt?
(A) P
(B) Q
(C) R
(D) S
63. The variable cost (V) of manufacturing a product varies according to the equation V= 4q, where q is the quantity produced. The fixed cost (F) of production of same product reduces with q according to the equation F = 100/q. How many units should be produced to minimize the total cost (V+F)?
(A) 5
(B) 4
(C) 7
(D) 6
64. A transporter receives the same number of orders each day. Currently, he has some pending orders (backlog) to be shipped. If he uses 7 trucks, then at the end of the 4th day he can clear all the orders. Alternatively, if he uses only 3 trucks, then all the orders are cleared at the end of the l0th day. What is the minimum number of trucks required so that there will be no pending order at the end of the 5th day?
(A) 4
(B) 5
(C) 6
(D) 7
65. A container originally contains 10 litres of pure spirit. From this container 1 litre of spirit is replaced with 1 litre of water. Subsequently, 1 litre of the mixture is again replaced with 1 litre of water and this process is repeated one more time. How much spirit is now left in the container?
(A) 7.58 litres
(B) 7.84 litres
(C) 7 litres
(D) 7.29 litres

End of Question Paper

 
Dear friends, you can discuss answers through comments. And please give your answers ( with explanation if possible ), you will help others. If you feel that an answer is wrong, please discuss it.

Q. No. 1 – 25 Carry One Mark Each

1.         Let G = (V, E) be a graph. Define ξ (G) =, where id is the number of vertices of degree d in
            G. If S and T are two different trees with ξ (S) = ξ (T), then
            (A)        |S| = 2 |T|       (B)        |S| = |T| − 1    (C)        |S| = |T|          (D)        |S| = |T| + 1
2.         Newton-Raphson method is used to compute a root of the equation x2 − 13 = 0 with 3.5 as the initial value. The approximation after one iteration is
            (A)        3.575                (B)        3.676                (C)        3.667                (D)        3.607
3.         What is the possible number of reflexive relations on a set of 5 elements?
            (A)        210                   (B)        215                   (C)        220                   (D) 225
4.         Consider the set S = {1, ω, ω2}, where ω and ω2are cube roots of unity. If * denotes the multiplication operation, the structure (S, *) forms
            (A)        A group                                                 (B)        A ring
            (C)        An integral domain                                 (D)        A field
5.         What is the value of  ?
            (A)        0                      (B)        e-2                   (C)        e-1/2                 (D)        1
6.         The minterm expansion of f (P, Q, R) =  is
            (A)        m2+ m4 + m6 + m7                                 (B)        m0 +m1 + m3 + m5
            (C)        m0+m1 + m6 + m7                                  (D)        m2 + m3 + m4 + m5
7.         A main memory unit with a capacity of 4 megabytes is built using 1M×1-bit DRAM chips.
      Each DRAM chip has 1K rows of cells with 1K cells in each row. The time taken for a single refresh
      operation is 100 nanoseconds. The time required to perform one refresh operation on all the cells in
      the memory unit is
            (A)        100 nanoseconds                                   (B)        100*210 nanoseconds
            (C)        100*220 nanoseconds                             (D)        3200*220 nanoseconds
8.         P is a 16-bit signed integer. The 2′s complement representation of P is (F87B)16. The 2′s complement representation of 8*P is
            (A)        (C3D8)16           (B)        (187B)16             (C)        (F878)16            (D)        (987B)1
9.         The Boolean expression for the output f of the multiplexer shown below is
(A)         
           
            (B)        P ⊕ Q ⊕ R
           
            (D)       
           
            (C)        P + Q + R
10.        In a binary tree with n nodes, every node has an odd number of descendants. Every node is considered to be its own descendant. What is the number of nodes in the tree that have exactly one child?
            (A)        0                      (B)        1                      (C)        (n − 1) /2          (D)        n-1
11.        What does the following program print?
            #include
            void f (int *p, int * g) {
                                    p = q;
                                    *p = 2;
            }
            int I = 0, j =1;
            int main ( ){
                        f(&i, & j);
                        print f (“%d%d / n”, i, j ;
                        return 0;
            }
            (A)        2 2                    (B)        2 1                    (C)        0 1                    (D)        0 2
12.        Two alternative packages A and B are available for processing a database having 10k records. Package A requires 0.0001n2 time units and package B requires 10nlog10n time units to process n records. What is the smallest value of k for which package B will be preferred over A?
            (A)        12                     (B)        10                     (C)        6                      (D)        5
13.        Which data structure in a compiler is used for managing information about variables and their attributes?
            (A)        Abstract syntax tree                                (B)        Symbol table
            (C)        Semantic stack                                       (D)        Parse table
14.        Which languages necessarily need heap allocation in the runtime environment?
            (A)        Those that support recursion                   (B)        Those that use dynamic scoping
            (C)        Those that allow dynamic data structures(D)         Those that use global variables
15.        One of the header fields in an IP datagram is the Time to Live (TTL) field. Which of the following statements best explains the need for this field?
            (A)        It can be used to prioritize packets
            (B)        It can be used to reduce delays
            (C)        It can be used to optimize throughput
            (D)        It can be used to prevent packet looping
16.        Which one of the following is not a client server application?
            (A)        Internet chat      (B)        Web browsing (C)          E-mail               (D)                    Ping
17.        Let L1 be a recursive language. Let L2 and L3 be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true?
            (A)        L2 – L1 is recursively enumerable
            (B)        L1 – L3 is recursively enumerable
            (C)        L2 ∩ L1 is recursively enumerable
            (D)        L2 ∪ L1 is recursively enumerable
18.        Consider a B+-tree in which the maximum number of keys in a node is 5. What is the minimum number of keys in any non-root node?
            (A)        1                      (B)        2                      (C)        3                      (D)        4
19.        A relational schema for a train reservation database is given below
            Passenger (pid, pname, age)
            Re servation (pid, cass, tid)
            Table: Passenger                                              
pid
‘pname
Age
0
‘Sachin’
65
1
‘Rahul’
66
2
‘Sourav’
67
3
‘Anil’
69

Table: Re servation
Pid
Class
Tid
0
‘AC’
8200
1
‘AC’
8201
2
‘SC’
8201
5
‘AC’
8203
1
‘SC’
8204
3
‘AC’
8202
            What pids are returned by the following SQL query for the above instance of the tables?
            SELECT             pid
            FROM                Re servation
            WHERE class = ‘AC’ AND
                                    EXISTS (SELECT *
                                                FROM Passenger
                                                WHERE age 65 AND
                                                Passenger.pid Reservation.pid)
            (A)        1, 0                   (B)        1, 2                   (C)        1, 3                   (D)        1, 5
20.        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               (C)        Both I and II       (D)        Neither I nor II
21.        The cyclomatic complexity of each of the modules A and B shown below is 10. What is the cyclomatic complexity of the sequential integration shown on the right hand side?

 

            (A)        19                     (B)        21                     (C)        20                     D)         10
22.        What is the appropriate pairing of items in the two columns listing various activities encountered in a software life cycle?
            P. Requirements Capture                        1. Module Development and Integration
            Q. Design                                              2. Domain Analysis
            R. Implementation                                  3. Structural and Behavioral Modeling
            S. Maintenance                                      4. Performance Tuning
            (A)        P-3, Q-2, R-4, S-1                                  (B)        P-2, Q-3, R-1, S-4
            (C)        P-3, Q-2, R-1, S-4                                  (D)        P-2, Q-3, R-4, S-1
23.        Consider the methods used by processes P1 and P2 for accessing their critical sections whenever needed, as given below. The initial values of shared Boolean variables S1 and S2 are randomly assigned.
            Method used by PI                              Method used by P2
            while (S1 = = S2) ;                                while (S1 != S2) ;
            Critica1 Section                                      Critica1 section             
            S1 = S2;                                               S2 = not (S1);
                                                                       
            Which one of the following statements describes the properties achieved?
            (A)        Mutual exclusion but not progress
            (B)        Progress but not mutual exclusion
            (C)        Neither mutual exclusion nor progress
            (D)        Both mutual exclusion and progress
24.        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)        96                     (B)        192                   (C)        197                   (D)        195
25.        Which of the following statements are true?
            I.          Shortest remaining time first scheduling may cause starvation
            II.         Preemptive scheduling may cause starvation
            III.        Round robin is better than FCFS in terms of response time
            (A)        I only                (B)        I and III only      (C)        II and III only     (D)        I, II and III
                                                 
Q. No. 26 – 51 Carry Two Marks Each
                                                                                   
26.        Consider a company that assembles computers. The probability of a faulty assembly of any computer is p. The company therefore subjects each computer to a testing process. This testing process gives the correct result for any computer with a probability of q. What is the probability of a computer being declared faulty?
            (A)        pq + (1 − p) (1 − q)                                (B)        (1 − q)p
            (C)        (1 − p) q                                               (D)        pq
27.        What is the probability that divisor of 1099 is a multiple of 1096?
            (A)        1/625                (B)        4/625                (C)        12/625              (D)        16/625
28.        The degree sequence of a simple graph is the sequence of the degrees of the nodes in the graph in decreasing order. Which of the following sequences can not be the degree sequence of any graph?
            I.          7, 6, 5, 4, 4, 3, 2, 1                                II.         6, 6, 6, 6, 3, 3, 2, 2
            III.        7, 6, 6, 4, 4, 3, 2, 2                                IV.        8, 7, 7, 6, 4, 2, 1, 1
            (A)        I and II (B)        III and IV           (C)        IV only              (D)        II and IV
29.        Consider the following matrix
             
            A =
            If the eigenvalues of A are 4 and 8, then
            (A)        x = 4,y = 10      (B)        x = 5,y = 8        (C)        x = −3,y = 9      (D)        x = −4,y = 10
30.        Suppose the predicate F(x, y, t) is used to represent the statement that person x can fool person y at time t. which one of the statements below expresses best the meaning of the formula
            ∀x∃y∃t(¬F (x,y, t))?
            (A)        Everyone can fool some person at some time
            (B)        No one can fool everyone all the time
            (C)        Everyone cannot fool some person all the time
            (D)        No one can fool some person at some time
31.        What is the Boolean expression for the output f of the combinational logic circuit of NOR gates given below?
 


            (A)          
           
            (B)       
           
            (C)       
           
            (D)         
32.        In the sequential circuit shown below, if the initial value of the output Q1Q0 is 00, what are the next four values of Q1Q0?
            (A)        11,10,01,00
            (B)        10,11,01,00
            (C)        10,00,01,11
            (D)        11,10,00,01
33.        A 5-stage pipelined processor has Instruction Fetch (IF), Instruction Decode (ID), Operand Fetch (OF), Perform Operation (PO) and Write Operand (WO) stages. The IF, ID, OF and WO stages take 1 clock cycle each for any instruction. The PO stage takes 1 clock cycle for ADD and SUB instructions, 3 clock cycles for MUL instruction, and 6 clock cycles for DIV instruction respectively. Operand forwarding is used in the pipeline. What is the number of clock cycles needed to execute the following sequence of instructions?
                        Instruction                                                      Meaning of instruction
            I0:MUL R2 ,R0 ,R1                                                                        R2¬ R0 *R1
            I1 :DIV R5 ,R3 ,R4                                                                         R5 ¬ R3 /R4
            I2: ADD R2 ,R5 ,R2                                                                       R2¬ R5 + R2
            I3:SUB R5 ,R2 ,R6                                                                        R5¬ R2 – R6
            (A)        13                     (B)        15                     (C)        17                     (D)        19
34.        The weight of a sequence a0, a1,…, an-1 of real numbers is defined as a0 + a1 /2 +…+ aa-1/2n-1. A subsequence of a sequence is obtained by deleting some elements from the sequence, keeping the order of the remaining elements the same. Let X denote the maximum possible weight of a subsequence of a0, a1,…, an-1. Then X is equal to
            (A)        max(Y, a0 + Y)                           (B)        max(Y, a0 +Y/2)
            (C)        max(Y, a0 +2Y)                           (D)        a0 + Y /2
35.        What is the value printed by the following C program?
            #include stdio.h
            int f(int * a, int n)
            {
                        if (n<= 0)return 0;
                        else if(*a% 2= = 0) return * a + f(a +1,n -1);
                        else return * a – f(a +1, n – 1);
            }
            int main ( )
            {
                        int a[ ] = {12, 7, 13, 4, 11, 6};
                        pr int f (“%d”, f(a,6));
                        return 0;
            }
            (A)        -9                     (B)        5                      (C)        15                     (D)        19
36.        The following C function takes a simply-linked list as input argument. It modifies the list by moving the last element to the front of the list and returns the modified list. Some part of the code is left blank.
            typedef struct node {
                        int value;
                        struct node *next;
            }           Node;
            Node *move_to_front(Node *head) {
                        Node *p, *q;
                        if ((head = = NULL: || (head->next = = NULL)) return head;
                        q = NULL; p = head;
                        while (p-> next !=NULL) {
                                    q=P;
                                    p=p->next;
            }
            _______________________________
            return head;
            }
            Choose the correct alternative to replace the blank line.
            (A)        q = NULL; p->next = head; head = p;
            (B)        q->next = NULL; head = p; p->next = head;
            (C)        head = p; p->next = q; q->next = NULL;
            (D)        q->next = NULL; p->next = head; head = p;
37.        The program below uses six temporary variables a, b, c, d, e, f.
            a = 1
            b = 10
            c = 20
            d = a + b
            e = c + d
            f = c + e
            b = c + e
            e = b + f
            d = 5 + e
            return d + f
            Assuming that all operations take their operands from registers, what is the minimum number of registers needed to execute this program without spilling?
            (A)        2                      (B)        3                      (C)        4                      (D)        6
38.        The grammar S → aSa|bS|c is
            (A)        LL(1) but not LR(1)                                 (B)        LR(1) but not LR(1)
            (C)        Both LL(1) and LR(1)                               (D)        Neither LL(1) nor LR(1)
39.        Let L = {w ∈ (0 + 1)*|w has even number of 1s}, i.e. L is the set of all bit strings with even number of 1s. Which one of the regular expressions below represents L?
            (A)        (0 *10 *1) *                                          (B)        0 * (10 *10 *) *
            (C)        0 * (10 *1*) * 0 *                                 (D)        0 *1(10 *1) *10 *
40.        Consider the languages L1 = {0i1j| i ≠ j}. L2 = {0i1j| i = j}. L3 = {0i1j | i = 2j + 1}.
            L4 = {0i1j | i ≠ 2j}. Which one of the following statements is true?
            (A)        Only L2 is context free                            (B)        Only L2 and L3 are context free
            (C)        Only L1 and L2 are context free               (D)        All are context free
41.        Let w be any string of length n in {0, 1}*. Let L be the set of all substrings of w. What is the minimum number of states in a non-deterministic finite automaton that accepts L?
            (A)        n-1                   (B)        n                      (C)        n+1                   (D)        2n-1
42.        Consider the following schedule for transactions T1, T2 and T3:
                        T1                    T2                                T3
                        Re ad (X)
                                                Re ad (Y)
                                                                                    Re ad (Y)
                                                Write (Y)
                        Write (X)
                                                                                    Write (X)
                                                Re ad (X)
                                                Write (X)
            Which one of the schedules below is the correct serialization of the above?
            (A)        T1 → T3 → T2                                        (B)        T2 → T1 → T3
            (C)        T2 → T3 → T1                                        (D)        T3 → T1 → T2
43.        The following functional dependencies hold for relations R(A, B, C) and S(B, D, E)
            B ® A,
            A ® C
            The relation R contains 200tuples and the relation S contains 100tuples. What is the maximum number of tuples possible in the natural join R      S?
            (A)        100                   (B)        200                   (C)        300                   (D)        2000
44.        The following program is to be tested for statement coverage:
            begin
                        if (a = = b) {S1; exit;}
                        else if (c = = d) {S2;]
                        else {S3; exit;}
            S4;
            end
            The test cases T1, T2, T3 and T4 given below are expressed in terms of the properties satisfied by the values of variables a, b, c and d. The exact values are not given.
            T1 : a, b, c and d are all equal
            T2 : a, b, c and d are all distinct
            T3 : a=b and c !=d
            T4 : a !=b and c=d
            Which of the test suites given below ensures coverage of statements S1, S2, S3 and S4?
            (A)        T1, T2, T3         (B)        T2, T4               (C)        T3, T4               (D)        T1, T2, T4
45.        The following program consists of 3 concurrent processes and 3 binary semaphores. The semaphores are initialized as S0=1, S1=0, S2=0.
           
Process P0
Process P1
Process P2
while (true) {
wait (S0);
print ’0′
release (S1);
release (S2);
}
wait (S1);
Release (S0);
wait (S2);
release (S0);
            How many times will process P0 print ’0′?
            (A)        At least twice                                         (B)        Exactly twice
            (C)        Exactly thrice                                         (D)        Exactly once
46.        A system has n resources R0,…, Rn-1, and k processes P0,…..Pk-1. The implementation of the resource request logic of each process Pi. is as follows:
            if (i% 2==0) {
                        if (i<n) request Ri ;
                        if (i+2<n)request Ri+2 ;
            }
            else {
                        if (i<n) request Rn-i ;
                        if (i+2<n)request Rn-i-2 ;
            }
            In which one of the following situations is a deadlock possible?
            (A)        n = 40,k = 26                                        (B)        n = 21,k = 12
            (C)        n = 20,k = 10                                        (D)        n = 41,k = 19
47.        Suppose computers A and B have IP addresses 10.105.1.113 and 10.105.1.91 respectively and they both use the same net mask N. Which of the values of N given below should not be used if A and B should belong to the same network?
            (A)        255.255.255.0                                        (B)        255.255.255.128
            (C)        255.255.255.192                                    (D)        255.255.255.224
                                                 
Common Data Questions: 48 & 49
A computer system has an L1 cache, an L2 cache, and a main memory unit connected as shown below. The block size in L1 cache is 4 words. The block size in L2 cache is 16 words. The memory access times are 2 nanoseconds. 20 nanoseconds and 200 nanoseconds for L1 cache, L2 cache and main memory unit respectively.
                                   
48.        When there is a miss in L1 cache and a hit in L2 cache, a block is transferred from L2 cache to L1 cache. What is the time taken for this transfer?
            (A)        2 nanoseconds                                       (B)        20 nanoseconds
            (C)        22 nanoseconds                                     (D)        88 nanoseconds
49.        When there is a miss in both L1 cache and L2 cache, first a block is transferred from main memory to L2 cache, and then a block is transferred from L2 cache to L1 cache. What is the total time taken for these transfers?
            (A)        222 nanoseconds                                   (B)        888 nanoseconds
            (C)        902 nanoseconds                                   (D)        968 nanoseconds
                                                 
Common Data Questions: 50 & 51
Consider a complete undirected graph with vertex set {0, 1, 2, 3, 4}. Entry Wij in the matrix W below is the weight of the edge {i, j}.
                                                W =
50.        What is the minimum possible weight of a spanning tree T in this graph such that vertex 0 is a leaf node in the tree T?
            (A)        7                      (B)        8                      (C)        9                      (D)        10
51.        What is the minimum possible weight of a path P from vertex 1 to vertex 2 in this graph such that P contains at most 3 edges?
            (A)        7                      (B)        8                      (C)        9                      (D)        10
                         
Linked Answer Questions: Q.52 to Q.55 Carry Two Marks Each
                                    
Statement for Linked Answer Questions: 52 & 53
A hash table of length 10 uses open addressing with hash function h(k)=k mod 10, and linear probing. After inserting 6 values into an empty hash table, the table is as shown below
                       
0
1
2
42
3
23
4
34
5
52
6
46
7
33
8
9
52.        Which one of the following choices gives a possible order in which the key values could have been inserted in the table?
            (A)        46, 42, 34, 52, 23, 33                             (B)        34, 42, 23, 52, 33, 46
            (C)        46, 34, 42, 23, 52, 33                             (D)        42, 46, 33, 23, 34, 52
53.        How many different insertion sequences of the key values using the same hash function and linear probing will result in the hash table shown above?
            (A)        10                     (B)        20                     (C)        30                     (D)        40
                                    
Statement for Linked Answer Questions: 54 & 55
            
Consider a network with 6 routers R1 to R6 connected with links having weights as shown in the following diagram
54.        All the routers use the distance vector based routing algorithm to update their routing tables. Each router starts with its routing table initialized to contain an entry for each neighbour with the weight of the respective connecting link. After all the routing tables stabilize, how many links in the network will never be used for carrying any data?
            (A)        4                      (B)        3                      (C)        2                      (D)        1
55.        Suppose the weights of all unused links in the previous question are changed to 2 and the distance vector algorithm is used again until all routing tables stabilize. How many links will now remain unused?
            (A)        0                      (B)        1                      (C)        2                      (D)        3
                                               
 Q. No. 56 – 60 Carry One Mark Each
56.        Choose the most appropriate word from the options given below to the complete the following sentence:
            His rather casual remarks on politics ___________ his lack of seriousness about the subject.
            (A)        masked             (B)        belied                (C)        betrayed            (D)        suppressed
57.        Which of the following options is closest in meaning to the word Circuitous.
            (A)        cyclic                 (B)        indirect              (C)        confusing           (D)        crooked
58.        Choose the most appropriate word from the options given below to complete the following sentence:
            If we manage to ____________ our natural resources, we would leave a better planet for our children.
            (A)        uphold               (B)        restrain             (C)        cherish              (D)        conserve
59.        25 persons are in a room. 15 of them play hockey, 17 of them play football and 10 of them play both hockey and football. Then the number of persons playing neither hockey nor football is:
            (A)        2                      (B)        17                     (C)        13                     (D)        3
60.        The question below consists of a pair of related words followed by four pairs of words. Select the pair that best expresses the relation in the original pair.
            Unemployed: Worker
            (A)        fallow: land                                           (B)        unaware: sleeper
            (C)        wit: jester                                             (D)        renovated:house
Q. No. 61 – 65 Carry Two Marks Each
61.        If 137+276=435 how much is 731+672?
            (A)        534                   (B)        1403                 (C)        1623                 (D)        1513
62.        Hari (H), Gita (G), Irfan (I) and Saira (S) are siblings (i.e. brothers and sisters). All were born on 1st january. The age difference between any two successive siblings (that is born one after another) is less than 3 years. Given the following facts:
            i.          Hari’s age + Gita’s age > Irfan’s age + Saira’s age
            ii.          The age difference between Gita and Saira is 1 year. However Gita is not the oldest and Saira is not the youngest.
            iii.         There are no twins.
            In what order were they born (oldest first)?
            (A)        HSIG                 (B)        SGHI                 (C)        IGSH                 (D)        IHSG
63.        Modern warfare has changed from large scale clashes of armies to suppression of civilian populations.
Chemical agents that do their work silently appear to be suited to such warfare; and regretfully, there exist people in military establishments who think that chemical agents are useful tools for their cause.
            Which of the following statements best sums up the meaning of the above passage:
            (A)        Modern warfare has resulted in civil strife.
            (B)        Chemical agents are useful in modern warfare.
            (C)        Use of chemical agents in warfare would be undesirable
            (D)        People in military establishments like to use chemical agents in war.
64.        5 skilled workers can build a wall in 20days: 8 semi-skilled workers can build a wall in 25 days; 10 unskilled workers can build a wall in 30days. If a team has 2 skilled, 6 semi-skilled and 5 unskilled workers, how long will it take to build the wall?
            (A)        20                     (B)        18                     (C)        16                     (D)        15
65.        Given digits 2,2,3,3,4,4,4,4 how many distinct 4 digit numbers greater than 3000 can be formed?
            (A)        50                     (B)        51                     (C)        52                     (D)        54

End of Question Paper

Dear friends, you can discuss answers through comments. And please give your answers ( with explanation if possible ), you will help others. If you feel that an answer is wrong, please discuss it.
 

Q. No. 1 – 20 Carry One Mark Each

1.         Which one of the following in NOT necessarily a property of a Group?
            (A)        Commutativity                                        (B)        Associativity
            (C)        Existence of inverse for every element      (D)        Existence of identity
2.         What is the chromatic number of an n-vertex simple connected graph which does not contain any odd length cycle? Assume n = 2.
            (A)        2                                                          (B)        3
            (C)        n-1                                                       (D)        n
3.         Which one of the following is TRUE for any simple connected undirected graph with more than 2 vertices?
            (A)        No two vertices have the same degree.
            (B)        At least two vertices have the same degree.
            (C)        At least three vertices have the same degree.
            (D)        All vertices have the same degree.
4.         Consider the binary relation R = {(x,y), (x,z), (z,x), (z,y)} on the set {x,y,z}.
            Which one of the following is TRUE?
            (A)        R is symmetric but NOT antisymmetric
            (B)        R is NOT symmetric but antisymmetric
            (C)        R is both symmetric and antisymmetric
            (D)        R is neither symmetric nor antisymmetric
5.         (1217)8is equivalent t o
            (A)        (1217)16            (B)        (028F)16             (C)        (2297)10 (D) (0B17)16
6.         What is the minimum number of gates required to implement the Boolean function (AB+C) if we have to use only 2-input NOR gates?
            (A)        2                      (B)        3                      (C)        4                      (D)        5
7.         How many 32K ´ 1 RAM chips are needed to provide a memory capacity of 256K-bytes?
            (A)        8                      (B)        32                     (C)        64                     (D)        128
8.         A CPU generally handles an interrupt by executing an interrupt service routine
            (A)        As soon as an interrupt is raised
            (B)        By checking the interrupt register at the end of fetch cycle.
            (C)        By checking the interrupt register after finishing the execution of the current instruction.
            (D)        By checking the interrupt register at fixed time intervals.
9.         In which one of t he following page replacement policies, Belady’s anomaly may occur?
            (A)        FIFO                 (B)        Optimal             (C)        LRU                   (D)        MRU
10.        The essential content (s) in each entry of a page table is / are
            (A)        Virtual page number
            (B)        Page frame number
            (C)        Both virtual page number and page frame number
            (D)        Access right information
11.        What is the number of swaps required t o sort n elements using selection sort, in the worst case?
            (A)        q(n)                  (B)        q(n log n)          (C)        q(n2) (D)           q(n2 log n)
 12.       S aSa | bSb | a | b; The language generated by the above grammar over the alphabet {a,b} is the set of
            (A)        All palindromes.
            (B)        All odd length palindromes.
            (C)        Strings that begin and end with the same symbol
            (D)        All even length palindromes.
13.        Which of the following statement (s) is / are correct regarding Bellman-Ford shortest path algorithm?
            P.         Always finds a negative weighted cycle, if one exist s.
            Q.         Finds whether any negative weighted cycle is reachable from the source.
            (A)        P only                                                    (B)        Q only
            (C)        both P and Q                                          (D)        Neither P nor Q
14.        Let pA be a problem that belongs to the class NP. Then which one of the following is TRUE?
            (A)        There is no polynomial time algorithm for pA.
            (B)        If pA can be solved deterministically in polynomial time, then P = NP.
            (C)        If pA is NP-hard, then it is NP-complete.
            (D)        pA may be undecidable.
15.        Which one of the following languages over the alphabet {0,1} is described by the regular expression: (0+1)*0(0+1)*0(0+1)*?
            (A)        The set of all strings containing the substring 00.
            (B)        The set of all strings containing at most two 0′s.
            (C)        The set of all strings containing at least two 0′s.
            (D)        The set of all strings that begin and end with either 0 or 1.
16.        Which one of the following is FALSE?
            (A)        There is unique minimal DFA for every regular language
            (B)        Every NFA can be convert ed to an equivalent PDA.
            (C)        Complement of every context-free language is recursive.
            (D)        Every nondeterministic PDA can be converted to an equivalent deterministic PDA.
17.        Match all items in Group 1 with correct options from those given in Group 2.
Group 1
Group 2
P.
Regular expression
1.
Syntax analysis
Q.
Pushdown automata
2.
Code generation
R.
Dataflow analysis
3.
Lexical analysis
S.
Register allocation
4.
Code optimization
            (A)        P-4. Q-1, R-2, S-3                                  (B)        P-3, Q-1, R-4, S-2
            (C)        P-3, Q-4, R-1, S-2                                 (D)        P-2, Q-1, R-4, S-3
18.        Consider the program below:
            # include
            int fun(int n, int * f_p) {
            int t, f;
            if (n <= 1) {
            * f_p =1;
            return 1;
            }
            t = fun (n- 1, f_p);
             f = t+ * f_p;
            * f_p = t;
            return f;
            }
            int main() {
            int x = 15;
            printf (” % d\ n”, fun(5, & x));
            return 0;
            }
            The value printed is 
            (A) 6 (B) 8 (C) 14 (D) 15
19.        The coupling between different modules of a software is categorized as follows:
            I. Content coupling         II. Common coupling
            III. Control coupling        IV Stamp coupling
            V. Data coupling
            Coupling between modules can be ranked in the order of strongest (least desirable) to weakest (most desirable) as follows:
            (A)        I-II-III-IV-V                                            (B)        V-IV-III-II-I
            (C)        I-III-V -II-IV                                           (D)        IV-II-V -III-I
 20.       Consider the HTML t able definition given below:
           
           

           

           

           

           

           

           

           

           
ab cd
ef gh
ik

            The number of rows in each column and the number of columns in each row are:
            (A)        á2,2,3ñand á2,3,2ñ                                 (B)        á2,2,3ñand á2,2,3ñ
            (C)        á2,3,2ñand á2,3,2ñ                                 (D)        á2,3,2ñ and á2,2,3ñ
  
Q. No. 21 – 56 Carry Two Marks Each
21.        An unbalanced dice (with 6 faces, numbered from 1 to 6) is thrown. The probability that the face value is odd is 90% of the probability that the face value is even. The probability of getting any even numbered face is the same. If the probability that the face is even given that it is greater than 3 is 0.75, which one of the following options is closest to the probability that the face value exceeds 3?
            (A)        0.453    (B) 0.468           (C) 0.485           (D) 0.492
22.        For the composition table of a cyclic group shown below
*
a
b
c
d
a
a
b
c
d
b
b
a
d
c
c
c
d
b
a
d
d
c
a
b
            Which one of the following choices is correct?
            (A)        a, b are generators                                (B)        b, c are generat ors
            (C)        c, d are generators                                 (D)        d, a are generators
  
23.        Which one of the following is the most appropriate logical formula to represent the statement? “Gold and silver ornaments are precious”.
            The following notations are used:
            G(x): x is a gold ornament
            S(x): x is a silver ornament
            P(x): x is precious
            (A)        x (P(x) ® (G(x) ÙS (x)))                      (B)        x ((G(x) ÙS (x)) ® P (x))
            (C)        $x ((G (x) Ù S (x)) ® P (x)                      (D)        x((G(x) Ú S(x)) ®P (x))
 24. The binary operation c is defined as follows
P
Q
PcQ
T
T
T
T
F
T
F
T
F
F
F
T
 Which one of the following is equivalent to P Ú Q?
 (A)       ØQc ØP                         (B)        PcØQ                (C)ØPcQ                       (D) ØPcØQ
25.         evaluates to
            (A)        0                      (B)        1                      (C)        ln 2                   (D)        1/2 ln 2
26.        Consider the following well-formed formulae:
            I.          Øx (P (x))        II.         Ø$x(P (x))         III.        Ø$x(ØP(x))        IV.        Ø$x (ØP(x))
            (A)        I and III             (B)        I and IV             (C)        II and III            (D)        II and IV
27.        Given the following state table of an FSM with two states A and B, one input and one output:
Present State A
Present State B
Input
Next State A
Next State B
Output
0
0
0
0
0
1
0
1
0
1
0
0
1
0
0
0
1
0
1
1
0
1
0
0
0
0
1
0
1
0
0
1
1
0
0
1
1
0
1
0
1
1
1
1
1
0
0
1
            If the initial state is A = 0, B=0, what is the minimum length of an input string which will take the machine to the state A=0, B=1 with Output=1?
            (A)        3                      (B)        4                      (C)        5                      (D)        6
28.        Consider a 4 stage pipeline processor. The number of cycles needed by the four instructions I1, I2, I3, I4 in stages S1, S2, S3, S4 is shown below:
           
S1
S2
S3
S4
I1
2
1
1
1
I2
1
3
2
2
I3
2
1
1
3
I4
1
2
2
2
             What is the number of cycles needed to execute the following loop?
             For (i=1 to 2) {I1; I2; I3; I4;}
             (A)       16                     (B)        23                     (C)        28                     (D)        30
29.        Consider a 4-way set associative cache (initially empty) with total 16 cache blocks. The main memory consists of 256 blocks and the request for memory blocks is in the following order:
            0, 255, 1, 4, 3, 8, 133, 159, 216, 129, 63, 8, 48, 32, 73, 92, 155.
            Which one of the following memory block will NOT be in cache if LRU replacement policy is used?
            (A)        3                      (B)        8                      (C)        129                   (D)        216
30.        Consider a system with 4 types of resources R1 (3 units), R2 (2 units), R3 (3 units), R4 (2 units). A non-preemptive resource allocation policy is used. At any given instance, a request is not entertained if it cannot be completely satisfied. Three processes P1, P2, P3 request the sources as follows if executed independently.
Process P1:
Process P2:
Process P3:
t=0: requests 2 units of R2
t=0: requests 2 units of R3
t=0: requests 1 unit of R4
t=1: requests 1 unit of R3
t=2: requests 1 unit of R4
t=2: requests 2 units of R1
t=3: requests 2 units of R1
t=4: requests 1 unit of R1
t=5: releases 2 units of R1
t=5: releases 1 unit of R2
t=6: releases 1 unit of R3
t=7: requests 1 unit of R2
         and 1 unit of R1.
t=8: Finishes
t=8: requests 1 unit of R3
t=7: releases 1 unit of R3
t=9: Finishes
t=8: requests 2 units of R4
t=10: Finishes
            Which one of the following st atements is TRUE if all three processes run concurrently starting at time t=0?
            (A)        All processes will finish without any deadlock
            (B)        Only P1 and P2 will be in deadlock.
            (C)        Only P1 and P3 will be in a deadlock.
            (D)        All three processes will be in deadlock.
31.        Consider a disk system with 100 cylinders. The requests to access the cylinders occur in following sequence:
            4, 34, 10, 7, 19, 73, 2, 15, 6, 20
            Assuming that the head is currently at cylinder 50, what is the time taken to satisfy all requests if it takes 1ms to move from one cylinder to adjacent one and shortest seek time first policy is used?
            (A) 95ms                       (B) 119ms                     (C) 233ms                     (D) 276ms
32.        In the following process state transition diagram for a uniprocessor system, assume that there are always some processes in the ready state:


 

              Now consider the following statements:
            I.          If a process makes a transition D, it would result in another process making transition A immediately.
            II.         A process P2 in blocked state can make transition E while another process P1 is in running state.
            III.        The OS uses preemptive scheduling.
            IV.        The OS uses non-preemptive scheduling.
            Which of the above statements are TRUE?
            (A)        I and II              (B)        I and III             (C)        II and III            (D)        II and IV
33.        The enter_CS() and leave_CS() functions to implement critical section of a process are realized using test-and-set instruction as follows:
            void enter_CS(X)
            {
            ( )
                        while test-and-set(X) ;
            }
            void leave_CS(X)
            {
                        X=0;
            }
            In the above solution, X is a memory location associated with the CS and is initialized to 0. Now consider the following statements:
            I. The above solution to CS problem is deadlock-free
            II. The solution is starvation free.
            III. The processes enter CS in FIFO order.
            IV More than one process can enter CS at the same time.
            Which of the above statements is TRUE?
            (A)        I only                (B)        I and II              (C)        II and III            (D)        IV only
34.        A multilevel page table is preferred in comparison t o a single level page table for translating virtual address to physical address because
            (A)        It reduces the memory access time to read or write a memory location.
            (B)        It helps to reduce the size of page table needed to implement the virtual address space of a process.
            (C)        It is required by the translation look aside buffer.
            (D)        It helps to reduce the number of page faults in page replacement algorithms.
  
35.        The running time of an algorithm is represented by the following recurrence relation:
             
            Which one of the following represents the time complexity of the algorithm?
             (A) q(n)                        (B)        q(n log n)          (C)        q(n2)                 (D)        q(n2 log n)
36.        The keys 12, 18, 13, 2, 3, 23, 5 and 15 are inserted into an initially empty hash table of length 10 using open addressing with hash function h(k) = k mod 10 and linear probing. What is the resultant hash table?


 

           
37.        What is the maximum height of any AVL-tree with 7 nodes? Assume that the height of a tree with a single node is 0.
            (A)        2                      (B)        3                      (C)        4                      (D)        5
38.        Consider the following graph:
 
            Which one of the following is NOT the sequence of edges added to the minimum spanning tree using Kruskal’s algorithm?
            (A) (b,e) (e,f) (a,c) (b,c) (f,g) (c,d)                      (B) (b,e) (e,f) (a,c) (f,g) (b,c) (c,d)
            (C) (b,e) (a,c) (e,f) (b,c) (f,g) (c,d)                      (D) (b,e) (e,f) (b,c) (a,c) (f,g) (c,d)
39.        In quick sort , for sorting n elements, the (n/4)th smallest element is selected as pivot using an O(n) time algorithm. What is the worst case time complexity of the quick sort?
            (A) q(n)                         (B) q(n log n)                 (C) q(n2)                       (D) (qn2log n)
 40.       Let L = L1 Ç L2, where L1 and L2 are languages as defined below:
            L1= {am bm c an bm | m, n ³0}
            L2 = {aibjck | i, j, k ³ 0}
            Then L is
            (A)        Not recursive
            (B)        Regular
            (C)        Context free but not regular
            (D)        Recursively enumerable but not context free.
41.
             The above DFA accepts the set of all strings over {0,1} that
            (A)        begin either with 0 or 1              (B)        end with 0
            (C)        end with 00                                           (D)        contain the substring 00.
42.        Which of the following statements are TRUE?
            I.          There exist parsing algorithms for some programming languages whose complexities are less than q(n3).
            II.         A programming language which allows recursion can be implemented with static storage allocation.
            III.        No L-attributed definition can be evaluated in t he framework of bottom-up parsing.
            IV.        Code improving transformations can be performed at both source language and intermediate code level.
            (A)        I and II                                      (B)        I and IV
            (C)        III and IV                                              (D)        I, III and IV
43.        Consider two transactions T1 and T2, and four schedules S1, S2, S3, S4 of T1and T2 as given below:
            T1 : R1 [x] W1[x] W1 [y]
            T2 : R2 [x] R2[y] W2 [y]
            S1 : R1 [x] R2[x] R2 [y] W1 [x] W1 [y] W2 [y]
            S2 : R1 [x] R2[x] R2 [y] W1 [x] W2 [y] W1 [y]
            S3 : R1 [x] W1[x] R2 [x] W1 [y] R2 [y] W2 [y]
            S4 : R2 [x] R2[y] R1 [x] W1 [x] W1 [y] W2 [y]
            Which of the above schedules are conflict-serializable?
            (A)        S1and S2           (B)        S2 and S3           (C)        S3 only              (D)        S4 only
44.        The following key values are inserted into a B+ – tree in which order of the internal nodes is 3, and that of the leaf nodes is 2, in the sequence given below. The order of internal nodes is the maximum number of tree pointers in each node, and the order of leaf nodes is the maximum number of data items that can be stored in it. The B+ – tree is initially empty.
            10, 3, 6, 8, 4, 2, 1
            The maximum number of times leaf nodes would get split up as a result of these insertions is
            (A)        2                      (B)        3                      (C)        4                      (D)        5


45.        Let R and S be relational schemes such that R={a,b,c} and S={c}. Now consider the following queries on the database:
            I.          pR-S (r) - pR-S (pR-S (r) ´S - pR-S,S (r))
            II.         {t | t Î pR-S (r) Ùu Î s ($v € r (u = v [s] Ù t = v [R -S]))}
            III.        {t | t Î pR-S (r) Ùv Î r ($u € s (u = v [s] Ù t = v [R -S]))}
            IV.        Select R.a, R.b
                                    From R, S
                                    Where R.c = S.c
            Which of the above queries are equivalent?
            (A)        I and II (B)        I and III             (C)        II and IV            (D)        III and IV
46.        In the RSA public key cryptosystem, the private and public keys are (e,n) and (d,n) respectively, where n=p*q and p and q are large primes. Besides, n is public and p and q are private. Let M be an integer such that 0<M<n and f(n) = (p -1) (q - 1). Now consider the following equations.
            I.          M¢ = Me mod n               II.         ed º 1 mod n
                        M = (M¢)dmod n
            III.        ed º 1 mod f(n) IV.        M¢ = Me mod f(n)
                                                                        M = (M¢)d mod f(n)
            Which of the above equations correctly represent RSA cryptosystem?
            (A)        I and II (B)        I and III             (C)        II and IV            (D)        III and IV
47.        While opening a TCP connection, the initial sequence number is t o be derived using a time-of-day (ToD) clock that keeps running even when the host is down. The low order 32 bits of the counter of the ToD clock is to be used for the initial sequence numbers. The clock counter increments once per millisecond. The maximum packet lifetime is given to be 64s.
            Which one of the choices given below is closest to the minimum permissible rate at which sequence numbers used for packets of a connection can increase?
            (A)        0.015/s             (B)        0.064/s             (C)        0.135/s             (D) 0.327/s
48.        Let G(x) be the generator polynomial used for CRC checking. What is the condition that should be satisfied by G(x) to detect odd number of bits in error?
            (A)        G(x) contains more than two terms
            (B)        G(x) does not divide 1+xk , for any not exceeding the frame length k
            (C)        1+x is a fact or of G(x)
            (D)        G(x) has an odd number of terms.
49.        Which of the following statements are TRUE?
            I.          The context diagram should depict t he system as a single bubble.
            II.         External entities should be identified clearly at all levels of DFDs.
            III.        Control information should not be represented in a DFD.
            IV.        A data store can be connected either to another data store or to an external entity.
            (A)        II and III            (B)        II and III            (C)        I and III             (D) I, II and III
50.        Consider the following statements about the cyclomatic complexity of the control flow graph of a program module. Which of these are TRUE?
            I.          The cyclomatic complexity of a module is equal to the maximum number of linearly independent circuits in the graph.
            II.         The cyclomatic complexity of a module is the number of decisions in the module plus one, where a decision is effectively any conditional statement in the module.
            III.        The cyclomatic complexity can also be used as a number of linearly independent paths that should be tested during path coverage testing.
            (A)        I and II (B)        II and III            (C)        I and III             (D)        I, II and III
  
Common Data Questions: 51 & 52
A hard disk has 63 sectors per track, 10 platters each with 2 recording surfaces and 1000 cylinders. The address of a sector is given as a triple ác, h, sñ, where c is the cylinder number, h is the surface number and s is the sector number. Thus, the 0th sector is addressed as á0, 0, 0ñ, the 1st sector as á0, 0, 1ñ, and so on
51.        The address corre4sponds tp sector number:
            (A)        505035             (B)        505036             (C)        505037             (D)        505038
52.        The address of the 1039th sector is
             (A)       á0, 15,31ñ          (B)        á0,16,30ñ          (C)        á0,16, 31ñ          (D)        á0, 17,31ñ
Common Data Questions: 53 & 54
A sub-sequence of a given sequence is just the given sequence with some elements (possibly none or all) left out. We are given two sequences X[m] and Y[n] of lengths m and n, respectively, with indexes of X and Y starting from 0.
53.        We wish to find the length of the longest common sub-sequence (LCS) of X[m] and Y[n] as l(m,n), where an incomplete recursive definition for the function l(i,j) to compute the length of t he LCS of X[m] and Y[n] is given below:
            l (i, j) 0, if either i=0 or j=0
            = expr1, if i,j>0 and X[i -1] =  Y[j - 1]
            = expr2, if i,j>0 and X[i - 1] = Y[j - 1]
            Which one of the following options is correct?
            (A)        expr1 º (i – 1, j) + 1                               (B)        expr1 º l(i, j – 1)
            (C)        expr2 º max (l(i – 1, j), l(i, j – 1)              (D)        expr2 º max (l(i – 1, j – 1), l(i, j))
54.        The values of l(i,j) could be obtained by dynamic programming based on the correct recursive definition of l(i,j) of the form given above, using an array L[M,N], where M = m+1 and N=n+1, such that L[i,j] = l(i,j).
            Which one of the following statements would be TRUE regarding the dynamic programming solution for the recursive definition of l(i,j)?
            (A)        All elements L should be initialized to 0 for the values of l(i,j) to be properly computed.
            (B)        The values of l(i,j) may be computed in a row major order or column major order of L(M,N).
            (C)        The values of l(i,j) cannot be computed in either row major order or column major order of L(M,N).
            (D)        L[p,q] needs to be computed before L[r,s] if either p<r or q<s.
  
Common Data Questions: 55 & 56
Consider the following relational schema:
Suppliers(sid:integer, sname:string, city:string, street:string)
Parts(pid:integer, pname:string, color:string)
Catalog(sid:integer, pid:integer, cost:real)
55.        Consider the following relational query on the above database:
            SELECT S.sname
            FROM Suppliers S
            WHERE S.sid NOT IN (SELECT C.sid
            FROM Catalog C
            WHERE C.pid NOT (SELECT P.pid
            FROM Parts P
            WHERE P.color ‘blue’))
            Assume that relations corresponding to the above schema are not empty. Which one of the following is the correct interpretation of the above query?
            (A)        Find the names of all suppliers who have supplied a non-blue part.
            (B)        Find the names of all suppliers who have not supplied a non-blue part.
            (C)        Find the names of all suppliers who have supplied only blue parts.
            (D)        Find the names of all suppliers who have not supplied only blue parts.
56.        Assume that, in the suppliers relation above, each supplier and each street within a city has a unique name, and (sname, city) forms a candidate key. No other functional dependencies are implied other than those implied by primary and candidate keys. Which one of the following is TRUE about the above schema?
            (A)        The schema is in BCNF
            (B)        The schema is in 3NF but not in BCNF
            (C)        The schema is in 2NF but not in 3NF
            (D)        The schema is not in 2NF
Linked Answer Questions: Q.57 to Q.60 Carry Two Marks Each
Statement for Linked Answer Questions: 57 & 58
Frames of 1000 bits are sent over a 10 bps duplex link between two hosts. The 6 propagation time is 25ms. Frames are to be transmitted into this link to maximally pack them in transit (within the link).
57.        What is the minimum number of bits (l) that will be required to represent the sequence numbers distinctly? Assume that no time gap needs to be given between transmissions of two frames.
            (A)        l=2                   (B)        l=3                   (C)        l=4                   (D)        l=5
58.        Suppose that the sliding window protocol is used with the sender window size of 2| , where l is the number of bits identified in t he earlier part and l acknowledgements are always piggy backed. After sending 2| frames, what is the l minimum time the sender will have to wait before starting transmission of the next frame? (Identify the closest choice ignoring the frame processing time.)
            (A)        16ms                (B)        18ms                (C)        20ms                (D)        22ms
 


Statement for Linked Answer Questions: 59 & 60
Consider a binary max-heap implemented using an array.
59.        Which one of the following array represents a binary max-heap?
            (A)        {25,12,16,13,10, 8,14}                           (B)        {25,14,13, 16,10, 8,12}
            (C)        {25,14,16,13,10, 8,12}                           (D)        {25,14,12,13,10, 8,16}
60.        What is the content of the array after two delete operations on the correct answer to the previous question?
            (A)        {14, 13,12,10, 8}                                   (B)        {14,12,13, 8,10}
            (C)        {14,13, 8, 12,10}                                   (D)        {14,13,12, 8,10}
End of Question Paper
Dear friends, you can discuss answers through comments. And please give your answers ( with explanation if possible ), you will help others. If you feel that an answer is wrong, please discuss it.

Q.1 – Q.20 Carry One Mark Each

1.         equals
            (A)        1                      (B)        -1                     (C)        ¥                      (D)        – ¥
2.         If P, Q, R are subsets of the universal set U, then
            (P ∩ Q ∩ R) U (Pc ∩ Q ∩ R) U Qc U Rc is
            (A)        Qc U Rc             (B)        P U Qc U Rc       (C)        Pc U Qc U Rc     (D)        U
3.         The following system of equations
           
           
           
            has a unique solution. The only possible value(s) for a is/are
            (A)        0                                                          (B)        either 0 or 1
            (C)        one of 0, 1 or -1                                     (D)        any real number
4.         In the IEEE floating point representation the hexadecimal value 0×00000000 corresponds to
            (A)        The normalized value 2-127                    (B)        The normalized value 2-126
            (C)        The normalized value +0                         (D)        The special value +0
5.         In the Karnaugh map shown below, X denotes a don’t care term. What is the minimal form of the function represented by the Karnaugh map?
     
            (A)                                                      (B)       
            (C)                                                    (D)       
6.         Let r denote number system radix. The only value(s) of r that satisfy the equation  is / are
            (A)        decimal 10                                             (B)        decimal 11
            (C)        decimal 10 and 11                                  (D)        any value >2
7.         The most efficient algorithm for finding the number of connected components in an undirected graph on n vertices and m edges has time complexity
            (A)        Q(n)                  (B)        Q(m)                 (C)        Q(m+n) (D)        Q(mn)
8.         Given f1, f3 and f in canonical sum of products form (in decimal) for the circuit
            f1= åm (4, 5, 6, 7, 8)
            f3= åm (1, 6, 15)
            f = åm (1, 6, 8, 15)
            then f2is
            (A)        å m (4, 6)         (B)        åm (4, 8)          (C)        åm (6, 8)          (D)        åm (4, 6, 8)
9.         Which of the following is true for the language {ap | p is a prime}?
            (A)        It is not accepted by a Turing Machine
            (B)        It is regular but not context-free
            (C)        It is context-free but not regular
            (D)        It is neither regular nor context-free, but accepted by a Turing machine
10.        Which of the following are decidable?
             I.         Whether the intersection of two regular languages is infinite
             II.        Whether a given context-free language is regular
             III.       Whether two push-down automata accept the same language
             IV.       Whether a given grammar is context-free
             (A)       I and II (B)        I and IV             (C)        II and III            (D)        II and IV
11.        Which of the following describes a handle (as applicable to LR-parsing) appropriately?
            (A)        It is the position in a sentential form where the next shift or reduce operation will occur
            (B)        It is non-terminal whose production will be used for reduction in the next step
            (C)        It is a production that may be used for reduction in a future step along with a position in the sentential form where the next shift or reduce operation will occur
            (D)        It is the production p that will be used for reduction in the next step along with a position in the sentential form where the right hand side of the production may be found
12.        Some code optimizations are carried out on the intermediate code because
            (A)        They enhance the portability of the compiler to other target processors
            (B)        Program analysis is more accurate on intermediate code than on machine code
            (C)        The information from dataflow analysis cannot otherwise be used for optimization
            (D)        The information from the front end cannot otherwise be used for optimization
13.        If L and are recursively enumerable then L is
            (A)        regular                                      (B)        context-free
            (C)        context-sensitive                        (D)        recursive
14.        What is the maximum size of data that the application layer can pass on to the TCP layer below?
             (A)       Any size                                    (B)        216bytes-size of TCP header
             (C)       216 bytes                                  (D)        1500 bytes
15.        Which of the following tuple relational calculus expression(s) is/are equivalent to
            I.          Ø$t Î r(P(t))
            II.         $t Ï r (P(t))
            III.        Ø$t Î r(ØP(t))
            IV.        $t Ï r (ØP(t))
            (A)        I only                (B)        II only               (C)        III only              (D)        III and IV only
16.        A clustering index is defined on the fields which are of type
            (A)        non-key and ordering                              (B)        non-key and non-ordering
            (C)        key and ordering                                    (D)        key and non-ordering
17.        Which of the following system calls results in the sending of SYN packets?
            (A)        socket                                                   (B)        bind
            (C)        listen                                                     (D)        connect
18.        Which combination of the integer variables x, y and z makes the variable a get the value 4 in the following expression?
            a = (x > y) ? ((x > z) ? x : z) : ((y > z) ? y : z)
            (A)        x = 3, y = 4, z = 2                                  (B)        x = 6, y = 5, z = 3
            (C)        x = 6, y = 3, z = 5                                  (D)        x = 5, y = 4, z = 5
19.        The Breadth First Search algorithm has been implemented using the queue data structure. One possible order of visiting the nodes of the following graph is
 
            (A)        MNOPQR           (B)        NQMPOR           (C)        QMNPR O          (D)        QMNPOR
20.        The data blocks of a very large file in the Unix file system are allocated using
            (A)        contiguous allocation
            (B)        linked allocation
            (C)        indexed allocation
            (D)        an extension of indexed allocation
Q.21 – Q.75 Carry Two Marks Each
 21.       The minimum number of equal length subintervals needed to approximate to an accuracy of at least  ´ 10-6 using the trapezoidal rule is
            (A)        1000e               (B)        1000                 (C)        100e                 (D)        100
22.        The Newton-Raphson iteration can be used to compute the
            (A)        square of R                                            (B)        reciprocal of R
            (C)        square root of R                                     (D)        logarithm of R
23.        Which of the following statements is true for every planar graph on n vertices?
            (A)        The graph is connected
            (B)        The graph is Eulerian
            (C)        The graph has a vertex-cover of size at most 3n/4
            (D)        The graph has an independent set of size at least n/3
24.        Let P = and Q = where k is a positive integer. Then
            (A)        P = Q – K          (B)        P = Q + K          (C)        P = Q                (D)        P = Q + 2K
25.        A point on a curve is said to be an extremum if it is a local minimum or a local maximum. The number of distinct extrema for the curve 3x4 – 16x3 + 24x2 + 37 is
            (A)        0                      (B)        1                      (C)        2                      (D)        3
26.        If P, Q, R are Boolean variables, then
           
            Simplifies to
            (A) P.                       (B)        P.                  (C)        P.+ R             (D)        P.+ Q
27.        Aishwarya studies either computer science or mathematics everyday. If she studies computer science on a day, then the probability that the studies mathematics the next day is 0.6. If she studies mathematics on a day, then the probability that the studies computer science the next day is 0.4. Given that Aishwarya studies computer science on Monday, what is the probability that she studies computer science on Wednesday?
            (A)        0.24                  (B)        0.36                  (C)        0.4                    (D)        0.6
28.        How many of the following matrices have an eigenvalue 1?
             and
            (A)        one                   (B)        two                   (C)        three                 (D)        four
29.        Let X be a random variable following normal distribution with mean +1 and variance 4. Let Y be another normal variable with mean -1 and variance unknown. If P (X £-1) = P (Y ³ 2), the standard deviation of Y is
            (A)        3                      (B)        2                      (C)        2                      (D)        1
30.        Let fsa and pda be two predicates such that fsa(x) means x is a finite state automaton, and pda(y) means that y is a pushdown automaton. Let equivalent be another predicate such that equivalent (a, b) means a and b are equivalent.
            Which of the following first order logic statements represents the following:
            Each finite state automaton has an equivalent pushdown automaton
            (A)        (“x fsa(x)) Þ ($y pda(y) Ù equivalent (x,y))
            (B)        ~ “y ($x fsa(x) Þ pda(y) Ù equivalent (x, y))
            (C)        “x $y (fsa(x) Ù pda(y) Ù equivalent (x, y))
            (D)        “x $y (fsa(y) Ù pda(x) Ù equivalent (x, y))
31.        P and Q are two propositions. Which of the following logical expressions are equivalent?
            I.          P Ú ~ Q
            II.         ~ (~ P Ù Q)
            III.        (P Ù Q) Ú (P Ù ~ Q) Ú (~ P Ù ~ Q)
            IV.        (P Ù Q) Ú (P Ù ~ Q) Ú (~ P Ù Q)
            (A)        Only I and II                                           (B)        Only I, II and III
            (C)        Only I, II and IV                          (D)        All of I, II III and IV
32.        For a magnetic disk with concentric circular tracks, the seek latency is not linearly proportional to the seek distance due t o
            (A)        non-uniform distribution of requests
            (B)        arm starting and stopping inertia
            (C)        higher capacity of tracks on the periphery of the platter
            (D)        use of unfair arm scheduling policies
33.        Which of the following is/are true of the auto-increment addressing mode?
            I.          It is useful in creating self-relocating code
            II.         If it is included in an Instruction Set Architecture, then an additional ALU is required for effective address calculation
            III.        The amount of increment depends on the size of the data item accessed
            (A)        I only                (B)        II only               (C)        III only              (D)        II and III only
34.        Which of the following must be true for the RFE (Return From Exception) instruction on a general purpose processor?
            I. It must be a trap instruction
            II. It must be a privileged instruction
            III. An exception cannot be allowed to occur during execution of an RFE instruction
            (A)        I only                (B)        II only               (C)        I and II only       (D)        I, II and III only
35.        For inclusion to hold between two cache levels L1 and L2 in a multi-level cache hierarchy, which of the following are necessary?
            I.          L1 must be a write-through cache
            II.         L2 must be a write-through cache
            III.        The associativity of L2 must be greater than that of L1
            IV.        The L2 cache must be at least as large as the L1 cache
            (A)        IV only                                                  (B)        I and IV only
            (C)        I, II and IV only                          (D)        I, II, III and IV
36.        Which of the following are NOT true in a pipelined processor?
            I.          Bypassing can handle all RAW hazards
            II.         Register renaming can eliminate all register carried WAR hazards
            III.        Control hazard penalties can be eliminated by dynamic branch prediction
            (A)        I and II only       (B)        I and III only      (C)        II and III only     (D)        I, II and III
37.        The use of multiple register windows with overlap causes a reduction in the number of memory accesses for
            I.          Function locals and parameters
            II.         Register saves and restores
            III.        Instruction fetches
            (A)        I only                (B)        II only               (C)        III only              (D)        I, II and III
38.        In an instruction execution pipeline, the earliest that the data TLB (Translation Lookaside Buffer) can be accessed is
            (A)        Before effective address calculation has started
            (B)        During effective address calculation
            (C)        After effective address calculation has completed
            (D)        After data cache lookup has completed
39.        Consider the following functions:
            f(n) = 2n
            g(n) = n!
            h(n) = nlogn
            Which of the following statements about the asymptotic behaviour of f(n), g(n), and h(n) is true?
            (A)        f (n) = O(g(n)); g(n) = O(h(n))                (B)        f (n) = W(g(n)); g(n) = O(h(n))
            (C)        g(n) = O(f (n)); h(n) = O(f (n))               (D)        h(n) = O(f (n)); g(n) = W(f (n))
40.        The minimum number of comparisons required to determine if an integer appears more than n/2 times in a sorted array of n integers is
            (A)        Q(n)                  (B)        Q(logn)             (C)        Q(log*n)           (D)        Q(1)
41.        A B-tree of order 4 is built from scratch by 10 successive insertions. What is the maximum number of node splitting operations that may take place?
            (A)        3                      (B)        4                      (C)        5                      (D)        6
42.        G is a graph on n vertices and 2n-2 edges. The edges of G can be partitioned into two edge-disjoint spanning trees. Which of the following is NOT true for G?
            (A)        For every subset of k vertices, the induced subgraph has at most 2k-2 edges
            (B)        The minimum cut in G has at least two edges
            (C)        There are two edge-disjoint paths between every pair of vertices
            (D)        There are two vertex-disjoint paths between every pair of vertices
43.        Consider the Quicksort algorithm. Suppose there is a procedure for finding a pivot element which splits the list into two sub-lists each of which contains at least one-fifth of the elements. Let T(n) be the number of comparisons required to sort n elements. Then
            (A)        T (n) £ 2T (n / 5) + n                             (B)        T (n) £ T (n / 5) + T (4n / 5) + n
            (C)        T (n) £ 2T (4n / 5) + n                            (D)        T (n) £ 2T (n / 2) + n
44.        The subset-sum problem is defined as follows: Given a set S of n positive integers and a positive integer W, determine whether there is a subset of S whose elements sum to W.
            An algorithm Q solves this problem in O(nW) time. Which of the following statements is false?
            (A)        Q solves the subset-sum problem in polynomial time when the input is encoded in unary
            (B)        Q solves the subset-sum problem in polynomial time when the input is encoded in binary
            (C)        The subset sum problem belongs to the class NP
            (D)        The subset sum problem is NP-hard
45.       
            Dijkstra’s single source shortest path algorithm when run from vertex a in the above graph, computes the correct shortest path distance to
            (A)        only vertex a                                          (B)        only vertices a, e, f, g, h
            (C)        only vertices a, b, c, d                             (D)        all the vertices
46.        You are given the postorder traversal, P, of a binary search tree on the n elements 1, 2,….,n. You have to determine the unique binary search tree that has P as its postorder traversal. What is the time complexity of the most efficient algorithm for doing this?
            (A)        Q(logn)            
            (B)        Q(n)
            (C)        Q(n log n)
            (D)        None of the above, as the tree cannot be uniquely determined
47.        We have a binary heap on n elements and wish to insert n more elements (not necessarily one after another) into this heap. The total time required for this is
            (A)        Q(log n)            (B)        Q(n)                  (C)        Q(n log n)          (D)        Q(n2)
48.        Which of the following statements is false?
            (A)        Every NFA can be converted to an equivalent DFA
            (B)        Every non-deterministic Turing machine can be converted to an equivalent deterministic Turing machine
            (C)        Every regular language is also a context-free language
            (D)        Every subset of a recursively enumerable set is recursive
49.        Given below are two finite state automata (® indicates the start state and F indicates a final state)

50.        Which of the following statements are true?
            I.          Every left-recursive grammar can be converted to a right-recursive grammar and vice-versa
            II.         All e-productions can be removed from any context-free grammar by suitable transformations
            III.        The language generated by a context-free grammar all of whose productions are of the form X ® w or X ® wY (where, w is a string of terminals and Y is a non-terminal), is always regular
            IV.        The derivation trees of strings generated by a context-free grammar in Chomsky Normal Form are always binary trees
            (A)        I, II, III and IV                                        (B)        II, III and IV only
            (C)        I, III and IV only                                     (D)        I, II and IV only
51.        Match the following:      
E.
Checking that identifiers are declared before their use
P.
L = {anbmcndm|n ³ 1, m ³ 1|}
F.
Number of formal parameters in the declaration of a function agrees with the number of actual parameters in use of that function
Q.
X ® XbX | XcX | dXf | g
G.
Arithmetic expressions with matched pairs of parentheses
R.
L = {wcw|wÎ(a|b)*}|
H.
Palindromes
S.
X ® bXb | cXc | e
            (A)        E – P, F – R, G – Q, H – S                         (B)        E – R, F – P, G – S, H – Q
            (C)        E – R, F – P, G – Q, H – S                         (D)        E – P, F – R, G – S, H – Q
52.        Match the following NFAs with the regular expressions they correspond to
            1.         e + 0(01*1 + 00) * 01*
            2.         e + 0(10 *1 + 00) * 0
            3.         e + 0(10 *1 + 10) *1
            4.         e + 0(10 *1 + 10) *10 *
            (A)        P – 2, Q – 1, R – 3, S – 4                         (B)        P – 1, Q – 3, R – 2, S – 4
            (C)        P – 1, Q – 2, R – 3, S – 4                         (D)        P – 3, Q – 2, R – 1, S – 4
53.        Which of the following are regular sets?
            I.          {anb2m|n ³ 0, m ³ 0}
            II.         {anbm|n = 2m}
            III.        {anbm|n ¹ m}
            IV.        {xcy|x, y, Î {a, b} *}
            (A)        I and IV only                                          (B)        I and III only
            (C)        I only                                                    (D)        IV only
54.        Which of the following are true?
            I.          A programming language which does not permit global variables of any kind and has no nesting of procedures/functions, but permits recursion can be implemented with static storage allocation
            II.         Multi-level access link (or display) arrangement is needed to arrange activation records only if the programming language being implemented has nesting of procedures/functions
            III.        Recursion in programming languages cannot be implemented with dynamic storage allocation
            IV.        Nesting procedures/functions and recursion require a dynamic heap allocation scheme and cannot be implemented with a stack-based allocation scheme for activation records
            V.         Programming languages which permit a function to return a function as its result cannot be implemented with a stack-based storage allocation scheme for activation records
            (A)        II and V only                                          (B)        I, III and IV only
            (C)        I, II and V only                                       (D)        II, III and V only
55.        An LALR(1) parser for a grammar G can have shift-reduce (S-R) conflicts if and only if
            (A)        The SLR(1) parser for G has S-R conflicts
            (B)        The LR(1) parser for G has S-R conflicts
            (C)        The LR(0) parser for G has S-R conflicts
            (D)        The LALR(1) parser for G has reduce-reduce conflicts
56.        In the slow start phase of the TCP congestion control algorithm, the size of the congestion window
            (A)        does not increase                                   (B)        increases linearly
            (C)        increases quadratically                            (D)        increases exponentially
57.        If a class B network on the Internet has a subnet mask of 255.255.248.0, what is the maximum number of host s per subnet?
            (A)        1022                 (B)        1023                 (C)        2046                 (D)        2047
58.        A computer on a 10Mbps network is regulated by a token bucket. The token bucket is filled at a rate of 2Mbps. It is initially filled to capacity with 16Megabits.
            What is the maximum duration for which the computer can transmit at the full 10Mbps?
            (A)        1.6 seconds       (B)        2 seconds          (C)        5 seconds          (D)        8 seconds
59.        A client process P needs to make a TCP connection to a server process S. Consider the following situation: the server process S executes a socket (), a bind () and a listen () system call in that order, following which it is preempted.
            Subsequently, the client process P executes a socket () system call followed by connect () system call to connect to the server process S. The server process has not executed any accept () system call. Which one of the following events could take place?
            (A)        connect () system call returns successfully
            (B)        connect () system call blocks
            (C)        connect () system call returns an error
            (D)        connect () system call results in a core dump
60.        What is printed by the following C program?
            {                                                           {
                        int y,     z;                                             int   c, *b,   **a;
                        **ppz + = 1; z = *ppz;                          c = 4;   b = &c;   a = &b;
                        *py + = 2;   y = *py;                             print f(“%d”, f(c, b, a));
                        x + = 3;                                    }
                        return x + y + z:
            }
            (A)        18                     (B)        19                     (C)        21                     (D)        22
61.        Choose the correct option to fill ? 1 and ? 2 so that the program below prints an input string in reverse order. Assume that the input string is terminated by a newline character.
                        void recerse void {
                                    int c;
                                    if (?1) reverse ();
                                    ?2
                        }
                        main () {
                                    print f (“Enter Text”); print f (“\ n”);
                                    reverse (); print f (“\ n”);
                        }
            (A)        ?1 is (getchar ( )! = ‘\ n’)
                        ?2 is getchar (c);
            (B)        ?1 is (c = getchar ( ) )! = ‘\ n’)
                        ?2 is getchar (c);
            (C)        ?1 is (c ! = ‘\ n’)
                        ?2 is putchar (c);
            (D)        ?1 is ((c = getchar ( ) )! = ‘\ n’)
                        ?2 is putchar (c);
62.        The following C function takes a single-linked list of integers as a parameter and rearranges the elements of the list. The function is called with the list containing the integers 1,2,3,4,5,6,7 in the given order. What will be the contents of the list after the function completes execution?
            struct node {
                    int value;
                    struct node * next;
            };
            Void rearrange (struct node * list) {
            struct node * p, * q;
            int temp;
            if (!list || !list – > next) return;
            p = list; q = list – > next;
            while q {
                    temp = p – > value; p – > value = q – > value;
                    q – > value = temp; p = q – > next
                    q = p? p – > next : 0;
                    }
            }
            (A)        1,2,3,4,5,6,7      (B)        2,1,4,3,6,5,7      (C)        1,3,2,5,4,7,6      (D)        2,3,4,5,6,7,1
63.        The P and V operations on counting semaphores, where s is a counting semaphore, are defined as follows:
            P(s) : s = s – 1;
                        if s < 0 then wait;
            V(s) : s = s + 1;
                        if s <= 0 then wakeup a process waiting on s;
            Assume that Pb and Vbthe wait and signal operations on binary semaphores are provided. Two binary semaphores xb and yb are used to implement the semaphore operations P(s) and V(s) as follows:
            P(s) : Pb(xb);
                        s = s -1;
                        if (s < 0) {
                           Vb (xb);
                           Pb (yb);
                        }
                        else Vb (xb);
            V(s) : Pb(xb);
                        s = s + 1;
                        if (s <=0) Vb (yb);
                           Vb (xb);
            The initial values of xb and ybare respectively
            (A) 0 and 0        (B) 0 and 1        (C) 1 and 0 (D) 1 and 1
64.        Which of the following statements about synchronous and asynchronous I/O is NOT true?
            (A)        An ISR is invoked on completion of I/O in synchronous I/O but not in asynchronous I/O
            (B)        In both synchronous and asynchronous I/O, an ISR (Interrupt Service Routine) is invoked after completion of the I/O
            (C)        A process making a synchronous I/O call waits until I/O is complete, but a process making an asynchronous I/O call does not wait for completion of the I/O
            (D)        In the case of synchronous I/O, the process waiting for the completion of I/O is woken up by the ISR that is invoked after the completion of I/O
65.        Which of the following is NOT true of deadlock prevention and deadlock avoidance schemes?
            (A)        In deadlock prevention, the request for resources is always granted if the resulting state is safe
            (B)        In deadlock avoidance, the request for resources is always granted if the result state is safe
            (C)        Deadlock avoidance is less restrictive than deadlock prevention
            (D)        Deadlock avoidance requires knowledge of resource requirements a priori
66.        A process executes the following code
            for (i = 0; i < n; i + +) for ( );
            The total number of child processes created is
             (A)       n                      (B) 2n – 1                      (C) 2n                           (D) 2n+1 – 1
67.        A processor uses 36 bit physical addresses and 32 bit virtual addresses, with a page frame size of 4 Kbytes. Each page table entry is of size 4 bytes. A three level page table is used for virtual to physical address translation, where the virtual address is used as follows
            •           Bits 30-31 are used to index into the first level page table
            •           Bits 21-29 are used to index into the second level page table
            •           Bits 12-20 are used to index into the third level page table, and
            •           Bits 0-11 are used as offset within the page
            The number of bits required for addressing the next level page table (or page frame) in the page table entry of the first, second and third level page tables are respectively
            (A)        20, 20 and 20                                        (B)        24, 24 and 24
            (C)        24, 24 and 20                                        (D)        25, 25 and 24
68.        Let R and S be two relations with the following schema
            R ()
            S ()
            Where {P, Q} is the key for both schemas. Which of the following queries are equivalent?
            I.          Õp(R         S)
            II.         Õp(R)         Õp (S)
            III.        Õpp, Q (R) Ç Õp, Q (S))
            IV.        Õpp, Q (R) – (Õp, Q (R) – Õp, Q (S)))
            (A)        Only I and II                                           (B)        Only I and III
            (C)        Only I, II and III                          (D)        Only I, III and IV
69.        Consider the following relational schemes for a library database:
            Book (Title, Author, Catalog_no, Publisher, Year, Price)
            Collection (Title, Author, Catalog_no)
            with in the following functional dependencies:
                        I.          Title Author ® Catalog_no
                        II.         Catalog_no ® Title Author Publisher Year
                        III.        Publisher Title Year ® Price
            Assume {Author, Title} is the key for both schemes. Which of the following statements is true?
            (A)        Both Book and Collection are in BCNF
            (B)        Both Book and Collection are in 3NF only
            (C)        Book is in 2NF and Collection is in 3NF
            (D)        Both Book and Collection are in 2NF only
70.        Consider a file of 16384 records. Each record is 32 bytes long and its key field is of size 6 bytes. The file is ordered on a non-key field, and the file organization is unspanned. The file is stored in a file system with block size 1024 bytes, and the size of a block pointer is 10 bytes. If the secondary index is built on the key field of the file, and a multi-level index scheme is used to store the secondary index, the number of first-level and second-level blocks in the multi-level index are respectively
            (A)        8 and 0             (B)        128 and 6          (C)        256 and 4          (D)        512 and 5
 
Common Data for Questions: 71 72 and 73
Consider a machine with a 2-way set associative data cache of size 64Kbytes and block size 16bytes. The cache is managed using 32 bit virtual addresses and the page size is 4Kbyts. A program to be run on this machine begins as follows:
            double ARR 1024 1024 ;
            int i, j ;
            /* Initialize array ARR to 0.0 * /
            for (i = 0; i < 1024; i ++)
              for (j = 0; j < 1024; j ++)
                ARR [i]  [j] = 0.0;
The size of double is 8Bytes. Array ARR is located in memory starting at the beginning of virtual page 0xFF000 and stored in row major order. The cache is initially empty and no pre-fetching is done. The only data memory references made by the program are those to array ARR
71.        The total size of the tags in the cache directory is
            (A)        32Kbits              (B)        34Kbits              (C)        64Kbits              (D)        68Kbits
72.        Which of the following array elements has the same cache index as ARR [0] [0]?
            (A)        ARR [0] [4]        (B)        ARR [4] [0]        (C)        ARR [0] [5]        (D)        ARR [5] [0]
73.        The cache hit ratio for this initialization loop is
            (A)        0%                   (B)        25%                  (C)        50%                  (D)        75%
Common Data for Questions: 74 and 75
Consider the following C functions:
            int f1 (int n)
            {
               if (n == 0 | | n == 1)
                 return n;
            else
              return (2* f1 (n – 1) + 3 * f1 (n – 2))
            }
            int f2 (int n)
            {
              int i:
              int X[N], Y[N], Z[N];
              X[0] = Y[0] = Z[0] = 0;
              X[1] = 1; Y[1] = 2; Z[1] = 3;
              for (i = 2; i <= n; i ++) {
                        X[i] = Y[i - 1] + Z[i - 2];
                        Y[i] = 2 * X[i];
                        Z[i] = 3 * X[i];
               }
            return X[n];
            }          
74.        The running time of f1 (n) and f2 (n) are
            (A)        Q (n) and Q (n)                                      (B)        Q (2n) and Q (n)
            (C)        Q (n) and Q (2n)                                    (D)        Q (2n) and Q (2n)
75.        F1 (8) and f2 (8) return the values
            (A)        1661 and 1640                                       (B)        59 and 59
            (C)        1640 and 1640                                       (D)        1640 and 1661
Linked Answer Questions: Q.76 to 85 Carry Two Marks Each
Statement for Linked Answer Questions: 76 & 77
Delayed branching can help in the handling of control hazards
76.        For all delayed conditional branch instructions, irrespective of whether the condition evaluates to true or false
            (A)        The instruction following the conditional branch instruction in memory is executed
            (B)        The first instruction in the fall through path is executed
            (C)        The first instruction in the taken path is executed
            (D)        The branch takes longer to execute than any other instruction
77.        The following code is to run on a pipelined processor with one branch delay slot:
            I1 :       ADD R2 ¬ R7 + R8
            I2 :       SUB R4 ¬ R5 – R6
            I3 :       ADD R1 ¬ R2 + R3
            I4 :       STORE Memory [R4] ¬ R1
                        BRANCH to Label if R1 == 0
            Which of the instructions I1, I2, I3 or I4 can legitimately occupy the delay slot without any other program modification?
            (A)        I1                     (B)        I2                     (C)        I3                     (D)        I4
Statement for Linked Answer Questions: 78 & 79
Let xndenote the number of binary strings of length n that contain no consecutive 0s.
78.        Which of the following recurrences does x satisfy?
            (A)        xn = 2xn-1                                              (B)        xn =  + 1
            (C)        xn =  + n                                      (D)        xn = xn-1 + xn-2
79.        The value of x5 is
            (A)        5                      (B)        7                      (C)        8                      (D) 16
Statement for Linked Answer Questions: 80 & 81
The subset-sum problem is defined as follows. Given a set of n positive integers, S = {a1, a2, a3, …, an}, and positive integer W, is there a subset of S whose elements sum to W? A dynamic program for solving this problem uses a 2-dimensional Boolean array, X, with n rows and W+1 columns.
X[i, j], 1 £ i £ n, 0 £ 0 £ j £ W, is TRUE if and only if there is a subset of {a1, a2, … ai} whose elements sum to j.
80.        Which of the following is valid for 2 £ i £ n and ai £ j £ W?
            (A)        X[i, j] = X[i - 1, j] Ú X[i, j - ai]               (B)        X[i, j] = X[i - 1, j] Ú X[i - 1, j -ai]
            (C)        X[i, j] = X[i - 1, j] Ù X[i, j - ai]               (B)        X[i, j] = X[i - 1, j] Ù X[i - 1, j -ai]
81.        Which entry of the array X, if TRUE, implies that there is a subset whose elements sum to W?
            (A)        X[1, W]             (B)        X[n, 0]              (C)        X[n, W]             (D)        X[n - 1, n]
Statement for Linked Answer Questions: 82 & 83
Consider the following ER diagram
 
82.        The minimum number of tables needed to represent M, N, P, R1, R2 is
            (A)        2                      (B)        3                      (C)        4                      (D)        5
83.        Which of the following is a correct attribute set for one of the tables for the correct answer to the above question?
            (A)        {M1,M2,M3, P1}                         (B)        {M1,P1,N1,N2}
            (C)        {M1, P1, N1}                                          (D)        {M1, P1}
Statement for Linked Answer Questions: 84 & 85
Consider the following C program that attempts to locate an element x in an array Y[ ] using binary search. The program is erroneous.
1.         f(int Y[10], int x) {
2.           int u, j, k;
3.           i = 0; j = 9;
4.           do {
5.                     k = (i + j) / 2;
6.                     if (Y[k] < x) i = k; else j = k;
7.                  }  while ((Y[k]! = x) && (i < j));
8.         if (Y [k] == x) print f (“x is in the array”);
9.         else print f (“x is not in the array”);
10.        }          
84.        On which of the following contents of Y and x does the program fail?
            (A)        Y is [1 2 3 4 5 6 7 8 9 10] and x < 10
            (B)        Y is [1 3 5 7 9 11 13 15 17 19] and x < 1 
            (C)        Y is [2 2 2 2 2 2 2 2 2 2] and x > 2
            (D)        Y is [2 4 6 8 10 12 14 16 18 20] and 2 < x < 20 and x is even
85.        The correction needed in the program to make it work properly is
            (A)        Change line 6 to: if (Y[k] < x) i = k + 1; else j = k – 1;
            (B)        Change line 6 to: if (Y[k] < x) i = k – 1; else j = k + 1;
            (C)        Change line 6 to: if (Y[k] <= x) i = k; else j = k;
            (D)        Change line 7 to:} while ((Y[k] == x) && (i < j));
End of Question Paper
Dear friends, you can discuss answers through comments. And please give your answers ( with explanation if possible ), you will help others. If you feel that an answer is wrong, please discuss it.

Q.1 – Q.20 Carry One Mark Each

1.         Consider the following two statements about the function f (x) = |x|:
            P.         f (x) is continuous for all real values of x
            Q.         f (x) is differentiable for all real values of x
            Which of the following is TRUE?
            (A)        P is true and Q is false.                          (B)        P is false and Q is true.
            (C)        Both P and Q are true.                           (D)        Both P and Q are false.
2.         Let S be a set of n elements. The number of ordered pairs in the largest and the smallest equivalence relations on S are:
            (A)        n and n            (B)        n2 and n          (C)        n2and 0            (D)        n and 1
3.         What is the maximum number of different Boolean functions involving n Boolean variables?
            (A)        n2                     (B)        2n                     (C)                          (D)       
4.         Let G be the non-planar graph with the minimum possible number of edges. Then G has
            (A)        9 edges and 5 vertices                            (B)        9 edges and 6 vertices
            (C)        10 edges and 5 vertices                          (D)        10 edges and 6 vertices
5.         Consider the DAG with = V = {1, 2, 3, 4, 5, 6}, shown below.

            Which of the following is NOT a topological ordering?
            (A)        1 2 3 4 5 6        (B)        1 3 2 4 5 6        (C)        1 3 2 4 6 5        (D)        3 2 4 1 6 5
6.         Which of the following problems is undecidable?
            (A)        Membership problem for CFGs.               (B)        Ambiguity problem for CFGs.
            (C)        Finiteness problem for FSAs.                  (D)        Equivalence problem for FSAs.
7.         Which of the following is TRUE?
            (A)        Every subset of a regular set is regular.
            (B)        Every finite subset of a non-regular set is regular.
            (C)        The union of two non-regular sets is not regular.
            (D)        Infinite union of finite sets is regular.
8.         How many 3-to-8 line decoders with an enable input are needed to construct a 6-to-64 line decoder without using any other logic gates?
            (A)        7                     (B)        8                     (C)        9                     (D)        10
9.         Consider the following Boolean function of four variables:
                        f (w x y z) = å (1,3, 4, 6, 9, 11,12,14)
            The function is:
            (A)        independent of one variables.                 (B)        independent of two variables.
            (C)        independent of three variables.               (D)        dependent on all the variables.
10.        Consider a 4-way set associative cache consisting of 128 lines with a line size of 64 words. The CPU generates a 20-bit address of a word in main memory. The number of bits in the TAG, LINE and WORD fields are respectively:
            (A)        9, 6, 5              (B)        7, 7, 6              (C)        7, 5, 8              (D)        9, 5, 6
11.        Consider a disk pack with 16 surfaces, 128 tracks per surface and 256 sectors per track. 512 bytes of data are stored in a bit serial manner in a sector. The capacity of the disk pack and the number of bits required to specify a particular sector in the disk is respectively:  
            (A)        256 Mbyte, 19 bits                                 (B)        256 Mbyte, 28 bits
            (C)        512 Mbyte, 20 bits                                 (D)        64 Gbyte, 28 bits
12.        The height of a binary tree is the maximum number of edges in any root to leaf path. The maximum number of nodes in a binary tree of height h is:
            (A)        2h -1                    (B)        2h-1 -1             (C)        2h+1 -1              (D)        2h+1     
13.        The maximum number of binary trees that can be formed with three unlabeled nodes is:
            (A)        1                     (B)        5                     (C)        4                     (D)        3
14.        Which of the following sorting algorithms has the lowest worst-case complexity?
            (A)        Merge sort        (B)        Bubble sort       (C)        Quick sort         (D)        Selection sort
15.        Consider the following segment of C-code:
                         int j, n;
                              j = 1;
                                while (j <=n)
                                     j = j*2;
            The number of comparisons made in the execution of the loop for any n > 0 is:
            (A)        [log2n] + 1         (B)        n                     (C)        [log2n]               (D)        [log2n] + 1
16.        Group 1 contains some CPU scheduling algorithms and Group 2 contains some applications. Match entries in Group 1 to entries in Group 2.
                         Group I                                               Group II
           
            (P) Gang Scheduling                               (1) Guaranteed Scheduling
            (Q) Rate Monotonic Scheduling                (2) Real-time Scheduling
            (R) Fair Share Scheduling                       (3) Thread Scheduling
            (A)        P – 3    Q – 2     R – 1                             (B)        P – 1    Q – 2     R – 3
            (C)        P – 2    Q – 3     R – 1                             (D)        P – 1    Q – 3     R – 2
17.        Consider the following statements about user level threads and kernel level threads. Which one of the following statements is FALSE?
            (A)        Context switch time is longer for kernel level threads than for user level threads.
            (B)        User level threads do not need any hardware support.
            (C)        Related kernel level threads can be scheduled on different processors in a multi-processor   system.
            (D)        Blocking one kernel level thread blocks all related threads.
18.        Which one of the following is a top-down parser?
            (A)        Recursive descent parser.                      (B)        Operator precedence parser.
            (C)        An LR (k) parser.                                   (D)        An LALR (k) parser.
19.        In Ethernet when Manchester encoding is used, the bit rate is:
            (A)        Half the baud rate.                                (B)        Twice the baud rate.
            (C)        Same as the baud rate.                         (D)        None of the above
20.        Which one of the following uses UDP as the transport protocol?
            (A)        HTTP   (B)        Telnet  (C)        DNS     (D)        SMTP
                                                            
Q.21 – Q.75 Carr y Two Marks Each
21.        How many different non-isomorphic Abelian groups of order 4 are there?
            (A)        2                     (B)        3                     (C)        4                     (D)        5
22.        Let Graph(x) be a predicate which denotes that x is a graph. Let Connected(x) be a predicate which denotes that x is connected. Which of the following first order logic sentences DOES NOT represent the statement: “Not every graph is connected”?
            (A)        ¬ x (Graph(x) Þ Connected (x))          (B)        x (Graph (x)  Ù ¬Connected (x))
            (C)        ¬ x (¬Graph(x) Ù Connected (x))         (D)        x (Graph (x) Þ ¬Connected (x))
23.        Which of the following graphs has an Eulerian circuit?
            (A)        Any k-regular graph where k is an even number.
            (B)        A complete graph on 90 vertices.
            (C)        The complement of a cycle on 25 vertices.
            (D)        None of the above
24.        Suppose we uniformly and randomly select a permutation from the 20! Permutations of 1, 2, 3,….., 20. What is the probability that 2 appears at an earlier position than any other even number in the selected permutation?
            (A)                            (B)                           (C)                          (D)        None of these
25.        Let A be a 4 × 4 matrix with eigenvalues -5, -2, 1, 4. Which of the following is an eigenvalue of  , where I is the 4 × 4 identity matrix?
            (A)        -5                    (B)        -7                    (C)        2                     (D)        1
26.        Consider the set S = {a, b, c, d}. Consider the following 4 partitions p1, p2, p3, p4,on S: p1= ,
            p2 = , p3 = , p4 =  . Let p be the partial order on the set of partitions
            S¢ = { p1, p2, p3, p4,} defined as follows: pi p pj if and only ifpi refines pj . The poset diagram for
            (S¢ , p) is:


 

27.        Consider the set of (column) vectors defined by
            X = {x Î R3|x1 + x2 + x3 = 0, where, xT= [x1 , x2 , x3 ]T }. Which of the following is TRUE?
            (A)        {[1, -1, 0]T, [1, 0, -1]T }is a basis for the subspace X.
            (B)        {[1, -1, 0]T, [1, 0, -1]T }is a linearly independent set, but it does not span X and therefore is          not a basis of X.
            (C)        X is not a subspace of R3
            (D)        None of the above
28.        Consider the series  obtained from the Newton-Raphson method. The series converges to
            (A)        1.5                   (B)                          (C)        1.6                   (D)        1.4
29.        A minimum state deterministic finite automaton accepting the language L = {w | w Î {0, 1}*, number of 0s and 1s in are divisible by 3 and 5, respectively} has
            (A)        15 states          (B)        11 states          (C)        10 states          (D)        9 states
30.        The language L   = {0i 21i |i ³ 0} over the alphabet {0, 1, 2} is:
            (A)        not recursive                                         (B)        is recursive and is a deterministic CFL
            (C)        is a regular language.                            (D)        is not a deterministic CFL but a CFL.
31.        Which of the following languages is regular?
            (A)        {wwR |w Î {0,1}+}                               (B)        {wwR x|x, w Î {0,1}+
            (C)        {wxwR |x, w Î {0,1}+                        (D)        {xwwR |x, w Î {0,1}+
32.        Let f (w, x, y, z) = å (0, 4,5,7, 8, 9, 13,15). Which of the following expressions are NOT equivalent to f?
            (P)        x¢ y¢ z¢ + w¢ xy¢ + wy¢ z + xz
            (Q)       w¢ y¢ z¢ + wx¢ y¢ + xz
            (R)        w¢ y¢ z¢ + wx¢ y¢ + xyz + xy¢z
            (S)        x¢ y¢ z¢ + wx¢ y¢ + w¢ y   
            (A)        P only               (B)        Q and S            (C)        R and S            (D)        S only
33.        Define the connective * for the Boolean variables X and Y as: X * Y = XY + X¢ Y¢. Let Z =X * Y. Consider the following expressions P, Q and R.
                        pP: X = Y * Z                 Q: Y = X * Z                  R: X * Y * Z = 1
            Which of the following is TRUE?
            (A)        Only P and Q are valid.                          (B)        Only Q and R are valid.
            (C)        Only P and R are valid.                           (D)        All P, Q, R are valid.
34.        Suppose only one multiplexer and one inverter are allowed to be used to implement any Boolean function of n variables. What is the minimum size of the multiplexer needed?
            (A)        2n line to 1 line                                      (B)        2n+1 line to 1 line          
            (C)        2n-1 line to 1 line                                   (D)        2n-2 line to 1 line
35.        In a look-ahead carry generator, the carry generate function Gi and the carry propagate function Pi for inputs Ai and Bi are given by:
                         Pi= Ai Å Biand Gi = Ai Bi
            The expressions for the sum bit Si and the carry bit Ci+1 of the look-ahead carry adder are given by:
                        Si= Pi Å Ciand Ci+1 = Gi + Pi Ci, where is the input carry.
            Consider a two-level logic implementation of the look-ahead carry generator. Assume that all Pi and Gi are available for the carry generator circuit and that the AND and OR gates can have any number of inputs. The number of AND gates and OR gates needed to implement the look-ahead carry generator for a 4-bit adder with S3 , S2 S1 , S0 , and C4 as its outputs are respectively:
            (A)        6, 3                  (B)        10, 4                (C)        6, 4                  (D)        10, 5
36.        The control signal functions of a 4-bit binary counter are given below (where X is “don’t ca re”):
            Clear
Clock
Load
Count
Function
1
x
x
x
Clear to 0
0
x
0
0
No change
0
­
1
x
Load input
0
­
0
1
Count next
             The counter is connected as follows:


 

             Assume that the counter and gate delays are negligible. If the counter starts at 0, then it cycles through the following sequence:
            (A)        0, 3, 4              (B)        0, 3, 4, 5          (C)        0, 1, 2, 3, 4      (D)        0, 1, 2, 3, 4, 5
37.        Consider a pipelined processor with the following four stages:
                        IF: Instruction Fetch
                        ID: Instruction Decode and Operand Fetch
                        EX: Execute
                        WB: Write Back
            The IF, ID and WB stages take one clock cycle each to complete the operation. The number of clock cycles for the EX stage depends on the instruction. The ADD and SUB instructions need 1 clock cycle and the MUL instruction needs 3 clock cycles in the EX stage. Operand forwarding is used in the pipelined processor. What is the number of clock cycles taken to complete the following sequence of instructions?
                        ADD      R2, R1, R0                    R2 ¬ R1 + R0
                        MUL      R4, R3,  R2                    R4 ¬ R3 * R2
                        SUB      R6, R5, R4                     R6 ¬ R5 – R4
            (A)        7                     (B)        8                     (C)        10                    (D)        14
38.        The following postfix expression with single digit operands is evaluated using a stack:
                                                 8 2 3  Ù  / 2 3 * + 5 1 * -
            Note that Ù  is the exponentiation operator. The top two elements of the stack after the first * is evaluated are:
            (A)        6, 1                  (B)        5, 7                  (C)        3, 2                  (D)        1, 5
39.        The inorder and preorder traversal of a binary tree are
                        d  b  e  a  f  c  g  and  a  b  d  e  c  f  g, respectively
            The postorder traversal of the binary tree is:
            (A)        d e b f g c a      (B)        e d b g f c a      (C)        e d b f g c a      (D)        d e f g b c a
  
40.        Consider a hash table of size seven, with starting index zero, and a hash function (3x + 4) mod7. Assuming the hash table is initially empty, which of the following is the contents of the table when the sequence 1, 3, 8, 10 is inserted into the table using closed hashing? Note that – denotes an empty location in the table.
            (A)        8, – , – , – , – , – , 10                               (B)        1, 8, 10, – , – , – , 3
            (C)        1, – , – , – , – , – , 3                                (D)        1, 10, 8, – , – , – , 3
41.        In an unweighted, undirected connected graph, the shortest path from a node S to every other node is computed most efficiently, in terms of time complexity, by
            (A)        Dijkstra’s algorithm starting from S.        (B)        Warshall’s algorithm
            (C)        Performing a DFS starting from S.          (D)        Performing a BFS starting from S.
42.        Consider the following C function:
                         int f(int n)
                        {static int r = 0;
                                    if (n <= 0) return 1;
                                     if (n > 3)
                                    {r = n;
                                    return f(n-2)+2;
                                     }
                                    return f(n-1)+r;
                        }
             What is the value of f (5)?
            (A)        5                     (B)        7                     (C)        9                     (D)        18
43.        A complete n-ary tree is a tree in which each node has n children or no children. Let I be the number of internal nodes and L be the number of leaves in a complete n-ary tree. If L = 41, and I = 10, what is the value of n?
            (A)        3                     (B)        4                     (C)        5                     (D)        6
44.        In the following C function, let n ³ m.
                        int gcd(n,m)
                        {
                                    if (n%m ==0) return m;
                                                n = n%m;
                                    return gcd(m,n);
                        }
            How many recursive calls are made by this function?
            (A)        Q log2 n             (B)        W(n)                (C)        Q(log2 log2 n)    (D)        Q()
45.        What is the time complexity of the following recursive function :
                        int DoSomething (int n) {
                                     if (n <= 2)
                                                return 1;
                                    else
                                                return (DoSomething (floor(sqrt(n))) + n);
                        }
            (A)        Q(n2)                (B)        Q (n log2 n)        (C)        Q(log2 n)           (D)        Q(log2 log2 n)
46.        Consider the following C program segment where CellNode represents a node in a binary tree:
                        struct CellNode {
                                    struct CellNOde *leftChild;
                                     int element;
                        struct CellNode *rightChild;
                        };
            int GetValue (struct CellNode *ptr) {
                        int value = 0;
                        if (ptr != NULL) {
                                     if ((ptr->leftChild == NULL) &&
                                                (ptr->rightChild == NULL))
                                                value = 1;
            else
                        value = value + GetValue(ptr->leftChild)
                                                + GetValue(ptr->rightChild);
                        }
            return(value);
            }
            The value returned by GetValue when a pointer to the root of a binary tree is passed as its argument is:
            (A)        the number of nodes in the tree
            (B)        the number of internal nodes in the tree
            (C)        the number of leaf nodes in the tree
            (D)        the height of the tree
47.        Consider the process of inserting an element into a Max Heap, where the Max Heap is represented by an array. Suppose we perform a binary search on the path from the new leaf to the root to find the position for the newly inserted element, the number of comparisons performed is:
            (A)        Q(log2 n)           (B)        Q(log2 log2 n)     (C)        Q(n)                  (D)        Q(n log2 n)
48.        Which of the following is TRUE about formulae in Conjunctive Normal Form?
            (A)        For any formula, there is a truth assignment for which at least half the clauses evaluate to   true.
            (B)        For any formula, there is a truth assignment for which all the clauses evaluate to true.
            (C)        There is a formula such that for each truth assignment, at most one-fourth of the clauses    evaluate to true.
            (D)        None of the above.
49.        Let w be the minimum weight among all edge weights in an undirected connected graph. Let be a specific edge of weight. Which of the following is FALSE?
            (A)        There is a minimum spanning tree containing e.
            (B)        If is not in a minimum spanning tree T, then in the cycle formed by adding e to T, all edges have the same weight.
            (C)        Every minimum spanning tree has an edge of weight w.
            (D)        is present in every minimum spanning tree.
50.        An array n numbers is given, where n is an even number. The maximum as   well as the minimum of these n numbers needs to be determined. Which of the following is TRUE about the number of comparisons needed?
            (A)        At least 2n – c comparisons, for some constant, c are needed.
            (B)        At most 1.5 – 2 comparisons a re needed.
            (C)        At least nlog2 n comparisons are needed.
            (D)        None of the above.
51.        Consider the following C code segment:
                        int IsPrime(n)
                                    {
                                    int i,n;
                                    for(i=2;i<=sqrt(n);i++)
                                                 if(n%i == 0)
                                                            {printf(“Not Prime\n”); return 0;}
                                                return 1;
                                                }          
            Let T (n) denote the number of times the for loop is executed by the program on input n. Which of the following is TRUE?
            (A)        T (n) = Oand T (n) = Ω          (B)        T (n) = Oand T (n) = Ω
            (C)        T (n) = O (n) and T (n) = Ω (D)        None of the above
52.        Consider the grammar with non-terminals N = {S, C, S1 }, terminals T = {a, b, i, t, e}, with S as the start symbol, and the following set of rules:
                                                S ® iCtSS | a
                                                S1®eS | e
                                                C ® b
            The grammar is NOT LL (1) because:
            (A)        it is left recursive                                   (B)        it is right recursive
            (C)        it is ambiguous                                      (D)        it is not context-free.
53.        Consider the following two statements: P: Every regular grammar is LL (1) Q: Every regular set has a LR(1) grammar
            Which of the following is TRUE?
            (A)        Both P and Q are true                            (B)        P is true and Q is false
            (C)        P is false and Q is true                           (D)        Both P and Q a re false
54.        In a simplified computer the instructions are:
                        OP RJ, Ri                        – Performs RJ OP Ri and stores the result in register. Ri.
                        OP m, Ri                        – Performs val OP Ri and stores the result in Ri .val
                                                                        denotes the content of memory location m.
                        MOV, m Ri                     – Moves the content of memory location m to register Ri.
                        MOV Ri, m                     – Moves the content of register Ri to memory location m.
            The computer has only to registers, and OP is either ADD or SUB. Consider the following basic block:
                        t1= a + b
                        t2 = c + d
                        t3 = e – t2
                        t4 = t1 – t3
            Assume that all operands are initially in memory. The final value of the computation should be in memory. What is the minimum number of MOV instructions in the code generated for this basic block?
            (A)        2                     (B)        3                     (C)        5                     (D)        6
55.        An operating system uses Shortest Remaining Time first (SRT) process scheduling algorithm. Consider the arrival times and execution times for the following processes:
                                               
                                                Process             Execution time               Arrival time
                                                  P1                     20                                  0
                                                  P2                     25                                 15
                                                  P3                     10                                 30
                                                  P4                     15                                 45
            What is the total waiting time for process P2?
            (A)        5                     (B)        15                    (C)        40                    (D)        55
56.        A virtual memory system uses First in First out (FIFO) page replacement policy and allocates a fixed number of frames to a process. Consider the following statements:
            P:         Increasing the number of page frames allocated to a process sometimes increases the page            fault rate.
            Q:         Some programs do not exhibit locality of reference.
            Which one of the following is TRUE?
            (A)        Both P and Q are true, and Q is the reason for P
            (B)        Both P and Q are true, but Q is not the reason for P.
            (C)        P is false, but Q is true
            (D)        Both P and Q are false.
57.        A single processor system has three resource types X, Y and Z, which are shared by three processes. There are 5 units of each resource type. Consider the following scenario, where the column alloc denotes the number of units of each resource type allocated to each process, and the column request denotes the number of units of each resource type requested by a process in order to complete execution. Which of these processes will finish LAST?


 


            (A)        P0                    (B)        P1                    (C)        P2
            (D)        None of the above, since the system is in a deadlock.
58.        Two processes, P1 and P2, need to access a critical section of code. Consider the following synchronization construct used by the processes:
             /*        P1         */                                                         /*         P2         */
            while (true) {                                                                 while (true) {
            wants1 = true;                                                               wants2 = true;
            while (wants2==true);                                                   while (wants1==true);
             /* Critical                                                                     /* Critical
            Section */                                                                     Section */
            Wants1=false;                                                               Wants2=false;
             }                                                                                 }
            /* Remainder section */                                                 /* Remainder section */
            Here, wants1 and wants2 are shared variables, which are initialized to
            Which one of the following statements is TRUE about the above construct?
            (A)        It does not ensure mutual exclusion.
            (B)        It does not ensure bounded waiting.
            (C)        It requires that processes enter the critical section in strict alternation.
            (D)        It does not prevent deadlocks, but ensures mutual exclusion.
59.        Information about a collection of students is given by the relation studinfo(studId, name, sex). The relation enroll (studId, courseId) gives which student has enrolled for (or taken) what course(s). Assume that every course is taken by at least one male and at least one female student. What does the following relational algebra expression represent?
                        ÕcourseId ((Õstudid (ssex=”female” (studinfo)) ´ Õcourseid (enroll)) – enrooll)
            (A)        Courses in which all the female students are enrolled.
            (B)        Courses in which a proper subset of female students are enrolled.
            (C)        Courses in which only male students are enrolled.
            (D)        None of the above
60.        Consider the relation (name, sex, supervisorName) with name as the employee key. supervisorName
 gives the name of the supervisor of the employee under consideration. What does the following Tuple Relational Calculus query produce?
                       
                        {e.name | employee (e)Ù}
                       
                                    (x) [¬ employee (x) Ú x. supervisorName ¹ e.name Ú x.sex = "male" ] }
            (A)        Names of employees with a male supervisor.
            (B)        Names of employees with no immediate male subordinates.
            (C)        Names of employees with no immediate female subordinates.
            (D)        Names of employees with a female supervisor.
61.        Consider the table employee(empId, name, department, salary) and the two employee queries Q1, Q2 below. Assuming that department 5 has more than one employee, and we want to find the employees who get higher salary than anyone in the department 5, which one of the statements is TRUE for any arbitrary employee table?
            Q1:        Select e.empId
                        From employee e
                        Where not exists
                        (Select * From employee s where s.department = “5″ and s.salary >=e.salary)
            Q2:        Select e.empId
                         From employee e
                        Where e.salary > Any
                        (Select distinct salary From employee s Where s.department = “5″)
            (A)        Q1 is the correct query
            (B)        Q2 is the correct query
            (C)        Both Q1 and Q2 produce the same answer.
            (D)        Neither Q1 nor Q2 is the correct query
62.        Which one of the following statements if FALSE?
            (A)        Any relation with two attributes is in BCNF
            (B)        A relation in which every key has only one attribute is in 2NF
            (C)        A prime attribute can be transitively dependent on a key in a 3 NF relation.
            (D)        A prime attribute can be transitively dependent on a key in a BCNF relation.
63.        The order of a leaf node in a B+-tree is the maximum number of (value, data record pointer) pairs it can hold. Given that the block size is 1K bytes, data record pointer is 7 bytes long, the value field is 9 bytes long and a block pointer is 6 bytes long, what is the order of the leaf node?
            (A)        63                    (B)        64                    (C)        67                    (D)        68
64.        Consider the following schedules involving two transactions. Which one of the following statements is TRUE?
                        S1: r1 (x); r1 (y); r2 (x); r2 (y); w2(y); w2 (x)
                        S2: r1 (x); r2 (x); r2 (y); w2 (y); r1(y); w1 (x)
            (A)        Both S1 and S2 are conflict serializable.
            (B)        S1 is conflict serializable and S2 is not conflict serializable.
            (C)        S1 is not conflict serializable and S2 is conflict serializable.
            (D)        Both S1 and S2 are not conflict serializable.
65.        There are n stations in a slotted LAN. Each station attempts to transmit with a probability p in each time slot. What is the probability that ONLY one station transmits in a given time slot?
            (A)        np (p 1)n-1        (B)        (1 – p)n-1          (C)        p (p 1)n-1           (D)        1 - (p 1)n-1
66.        In a token ring network the transmission speed is 107bps and the propagation speed is 200 metres/ms. The 1-bit delay in this network is equivalent to:
            (A)        500 metres of cable.      (B)        200 metres of cable.
            (C)        20 metres of cable.       (D)        50 metres of cable.
67.        The address of a class B host is to be split into subnets with a 6-bit subnet number. What is the maximum number of subnets and the maximum number of hosts in each subnet?
            (A)        62 subnets and 262142 hosts.    (B)        64 subnets and 262142 hosts.
            (C)        62 subnets and 1022 hosts.        (D)        64 subnets and 1024 hosts.
68.        The message 11001001 is to be transmitted using the CRC polynomial x3+ 1 to protect it from errors. The message that should be transmitted is:
            (A)        11001001000    (B)        11001001011
            (C)        11001010         (D)        110010010011
69.        The distance between two stations M and N is L kilometers. All frames are K bits long. The propagation delay per kilometer is t seconds. Let R bits/second be the channel capacity. Assuming that processing delay is negligible, the minimum number of bits for the sequence number field in a frame for maximum utilization, when the sliding window protocol is used, is:
            (A)                                           (B)             
            (C)                                            (D)       
70.        Match the following:
                       
                                    (P) SMTP           (1) Application layer
                                    (Q) BGP             (2) Transport layer
                                    (R) TCP             (3) Data link layer
                                    (S) PPP                         (4) Network layer
                                                            (5) Physical layer
            (A)        P – 2    Q – 1     R – 3     S – 5                 (B)        P – 1    Q – 4     R – 2     S – 3
            (C)        P – 1    Q – 4     R – 2     S – 5                 (D)        P – 2    Q – 4     R – 1     S – 3
  
                                                             
Common Data Questions
  
Common Data for Questions 71, 72, 73:
  
Consider the following program segment. Here R1, R2 and R3 are the general purpose registers.
                        Instruction                     Operation                      Instruction size (no. of words)
                      MOV R1, (3000)               R1 ¬ m [3000]                                      2
            LOOP: MOV R2, (R3)                  R2 ¬ M [R3]                                         1
                       ADD R2, R1                     R2 ¬ R1 + R2                                        1
                       MOV (R3), R2                  M [R3] ¬ R2                                         1
                      INC R3                            R3 ¬ R3 + 1                                          1
                       DEC R1                           R1 ¬ R1 – 1                                          1
                       BNZ LOOP                       Branch on not zero                                 2
                      HALT                               Stop                                                      1
            Assume that the content of memory location 3000 is 10 and the content of the register R3 is 2000. The content of each of the memory locations from 2000 to 2010 is 100. The program is loaded from the memory location 1000. All the numbers are in decimal.
  
71.        Assume that the memory is word addressable. The number of memory references for accessing the data in executing the program completely is:
            (A)        10        (B)        11        (C)        20        (D)        21
72.        Assume that the memory is word addressable. After the execution of this program, the content of memory location 2010 is:
            (A)        100      (B)        101      (C)        102      (D)        110
73.        Assume that the memory is byte addressable and the word size is 32 bits. If an interrupt occurs during the execution of the instruction “INC R3″, what return address will be pushed on to the stack?
            (A)        1005    (B)        1020    (C)        1024    (D)        1040
                                              


Common Data for Questions 74, 75:
Consider the following Finite State Automaton:


 


74.        The language accepted by this automaton is given by the regular expression
            (A)        b*  ab*  ab*  ab*                                 (B)        (a + b) *         
            (C)        b*  a( a + b) *                                      (D)        b*  ab*  ab*
75.        The minimum state automaton equivalent to the above FSA has the following number of states
            (A)        1         (B)        2         (C)        3         (D)        4
                         
Linked Answer Questions: Q.76 to Q.85 Carry Two Marks Each
Statement for Linked Answer Questions 76 & 77:
Suppose the letters a, b, c, d, e, f have probabilities  respectively.
76.        Which of the following is the Huffman code for the letter a, b, c, d, e, f?
            (A)        0, 10, 110, 1110, 11110, 11111
            (B)        11, 10, 011, 010, 001, 000
            (C)        11, 10, 01, 001, 0001, 0000
            (D)        110, 100, 010, 000, 001, 111
77.        What is the average length of the correct answer to Q.76?
            (A)        3                     (B)        2.1875             (C)        2.25                 (D)        1.9375
Statement for Linked Answer Questions 78 & 79:
Consider the CFG with {S A B} as the non-terminal alphabet, {a b} as the terminal alphabet,
S as the start symbol and the following set of production rules:
                                    S ®  aB                        S ® bA
                                    B ®  b                          A ® a
                                    B ® bS                                     A ® aS
                                    B ® aBB                        S ® bAA
78.        Which of the following strings is generated by the grammar?
            (A)        aaaabb (B)        aabbbb (C)        aabbab (D)        abbbba
79.        For the correct answer strings to Q.78, how many derivation trees are there?
            (A)        1         (B)        2         (C)        3         (D)        4
Statement for Linked Answer Questions 80 & 81:
            Consider a machine with a byte addressable main memory of 216bytes. Assume that a direct mapped data cache consisting of 32 lines of 64 bytes each is used in the system. A 50 ´ 50 two-dimensional array of bytes is stored in the main memory starting from memory location 1100H. Assume that the data cache is initially empty. The complete array is accessed twice. Assume that the contents of the data cache do not change in between the two accesses.
80.        How many data cache misses will occur in total?
            (A)        48                    (B)        50                    (C)        56                    (D)        59
81.        Which of the following lines of the data cache will be replaced by new blocks in accessing the array for the second time?
            (A)        line 4 to line 11                                     (B)        line 4 to line 12
            (C)        line 0 to line 7                                       (D)        line 0 to line 8
Statement for Linked Answer Questions 82 & 83:
            A process has been allocated 3 page frames. Assume that none of the pages of the process are available in the memory initially. The process makes the following sequence of page references (reference string): 1, 2, 1, 3, 7, 4, 5, 6, 3, 1
82.        If optimal page replacement policy is used, how many page faults occur for the above reference string?
            (A)        7                     (B)        8                     (C)        9                     (D)        10
83.        Least Recently Used (LRU) page replacement policy is a practical approximation to optimal page replacement. For the above reference string, how many more page faults occur with LRU than with the optimal page replacement policy?
            (A)        0                     (B)        1                     (C)        2                     (D)        3
Statement for Linked Answer Questions 84 & 85:
            Suppose that a robot is placed on the Cartesian plane. At each step it is allowed to move either one unit up or one unit right, i.e., if it is at ( i, j) then it can move to either , (i + 1, j) or (i, j + 1).
84.        How many distinct paths are there for the robot to reach the point (10, 10) starting from the initial position (0, 0)?
            (A)                        (B)        220                   (C)        210                   (D)        None of the above
85.        Suppose that the robot is not allowed to traverse the line segment from (4, 4) to (5, 4). With this constraint, how many distinct paths are there for the robot to reach (10,10) starting from (0,0)?
            (A)        29                                                        (B)        219                  
            (C)                                                    (D)       
End of question paper
Dear friends, you can discuss answers through comments. And please give your answers ( with explanation if possible ), you will help others. If you feel that an answer is wrong, please discuss it.

Q.1 – Q.20 Carry One Mark Each

1.         Consider the polynomial p(x) = a0 + a1x + a2x2 + a3x2, where ai ¹ 0, “i. The minimum number of multiplications needed to evaluate p on an input x is:
            (A)        3                      (B)        4                      (C)        6                      (D)        9
2.         Let X, Y, Z be sets of sizes x, y and z respectively. Let W X Y = × and E be the set of all subsets of W. The number of functions from Z to E is:
            (A)                         (B)        Z ´ 2xy              (C)                       (D)        2xyz
3.         The set {1, 2, 3, 5, 7, 8, 9} under multiplication modulo 10 is not a group. Given  below are four plausible reasons. Which one of them is false?
            (A)        It is not closed                                       (B)        2 does not have an inverse
            (C)        3 does not have an inverse                      (D)        8 does not have an inverse
4.         A relation R is defined on ordered pairs of integers as follows:
            (x, y) R (u, v) if x v. Then R is:
            (A)        Neither a Partial Order nor an Equivalence Relation
            (B)        A Partial Order but not a Total Order
            (C)        A Total Order
            (D)        An Equivalence Relation
5.         For which one of the following reasons does Internet Protocol (IP) use the time- to-live (TTL) field in the IP datagram header?
            (A)        Ensure packets reach destination within that time
            (B)        Discard packets that reach later than that time
            (C)        Prevent packets from looping indefinitely
            (D)        Limit the time for which a packet gets queued in intermediate routers.
6.         Consider three CPU-intensive processes, which require 10, 20 and 30 time units and arrive at times 0, 2 and 6, respectively. How many context switches are needed if the operating system implements a shortest remaining time first scheduling algorithm? Do not count the context switches at time zero and at the end.
            (A)        1                      (B)        2                      (C)        3                      (D)        4
7.         Consider the following grammar.
                        S S * E
                        S E
                        E F + E
                        E F
                        F id
            Consider the following LR (0) items corresponding to the grammar above.
            (i)         S S * × E
            (ii)        E F × + E
            (iii)       E F + × E
            Given the items above, which two of them will appear in the same set in the  canonical sets-of-items for the grammar?
            (A)        (i) and (ii)                                              (B)        (ii) and (iii)
            (C)        (i) and (iii)                                             (D)        None of the above
8.         You are given a free running clock with a duty cycle of 50% and a digital  waveform f which changes only at the negative edge of the clock. Which one of  the following circuits (using clocked D flip-flops) will delay the phase of f by 180°?
            (A)       
            (B)       
            (C)       
            (D)       
           
9.         A CPU has 24-bit instructions. A program starts at address 300 (in decimal).  Which one of the following is a legal program counter (all values in decimal)?
            (A)        400                   (B)        500                   (C)        600                   (D)        700
10.        In a binary max heap containing n numbers, the smallest element can be found  in time
            (A)        O (n)                 (B)        O (log n)           (C)        O (log log n)      (D)        O(1)
11.        Consider a weighted complete graph G on the vertex set {v1, v2, …, vn} such that the weight of the edge (vi, vj) is 2|i – j|. The weight of a minimum spanning tree of G is:
            (A)        n – 1                 (B)        2n – 2               (C)                          (D)        n2
12.        To implement Dijkstra’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                (C)        Heap                 (D)        B-Tree
13.        A scheme for storing binary trees in an array X is as follows. Indexing of X starts at 1 instead of 0. the root is stored at X[1]. For a node stored at X[i], the left child, if any, is stored in X[2i] and the right child, if any, in X[2i+1]. To be able to store any binary tree on n vertices the minimum size of X should be
            (A)        log2 n                (B)        n                      (C)        2n + 1               (D)        2n - 1
14.        Which one of the following in place sorting algorithms needs the minimum number of swaps?
            (A)        Quick sort          (B)        Insertion sort     (C)        Selection sort     (D)        Heap sort
15.        Consider the following C-program fragment in which i, j and n are integer variables.
            for (i = n, j = 0; i > 0; i /= 2, j +=i);
            Let val (j) denote the value stored in the variable j after termination of the for loop. Which one of the following is true?
            (A)        val (j) = q (log n)                                   (B)        val (j) q ()
            (C)        val (j) = q (n)                                        (D)        val (j) = q (n log n)
16.        Let S be an NP-complete problem and Q and R be two other problems not known  to be in NP. Q is polynomial time reducible to S and S is polynomial-time  reducible to R. Which one of the following statements is true?
            (A)        R is NP-complete                                    (B)        R is NP-hard
            (C)        Q is NP-complete                                    (D)        Q is NP-hard
17.        An element in an array X is called a leader if it is greater than all elements to the right of it in X. The best algorithm to find all leaders in an array
            (A)        Solves it in linear time using a left to right pass of the array
            (B)        Solves it in linear time using a right to left pass of the array
            (C)        Solves it using divide and conquer in time q (n log n)
            (D)        Solves it in time q (n2)
18.        We are given a set X = {x1, ….. xn} where xi = 2i. A sample S Í X is drawn by selecting each xi independently with probability pi = . The expected value of the smallest number in sample S is:
            (A)                            (B)        2                      (C)                          (D)        n
19.        Let        L1= {0n+m 1n 0m | n, m ³ 0},
                        L2 = {0n+m 1n+m 0m| n, m ³ 0}, and
                        L3 {0n+m 1n+m 0n+m| n, m ³ 0}.
                        Which of these languages are not context free?
            (A)        L1 only               (B)        L3only               (C)        L1 and L2            (D)        L2and L3
20.        Consider the following log sequence of two transactions on a bank account, with initial balance 12000, that transfer 2000 to a mortgage payment and then apply a 5% interest.
            1.         T1 start
            2.         T1 B old=1200 new=10000
            3.         T1 M old=0 new=2000
            4.         T1 commit
            5.         T2 start
            6.         T2 B old=10000 new=10500
            7.         T2 commit
            Suppose the database system cra shes just before log record 7 is written. When  the system is restarted, which one statement is true of the recovery procedure?
            (A)        We must redo log record 6 to set B to 10500
            (B)        We must undo log record 6 to set B to 10000 and then redo log records 2  and 3
            (C)        We need not redo log records 2 and 3 because transaction T1 has committed
            (D)        We can apply redo and undo operations in arbitrary order because they are idempotent. 
Q.21 – Q.75 Carry Two Marks Each
21.        For each element in a set of size 2n, an unbiased coin is tossed. The 2n coin tosses are independent. An element is chosen if the corresponding coin toss were head. The probability that exactly n elements are chosen is:
            (A)                       (B)                       (C)                       (D)       
22.        Let E, F and G be finite sets.
            Let X = (E Ç F) – (F Ç G) and Y = (E – (E Ç G)) – (E – F).
            Which one of the following is true?
            (A)        X Ì Y                                                    (B)        X É Y   
            (C)        X = Y                                                    (D)        X - Y ¹ Æ and Y - X ¹ Æ
23.        F is an n ´ n real matrix. b is an n ´ 1 real vector. Suppose there are two n ´ 1 vectors, u and v such that , u ¹ v and Fu = b, Fv = b. Which one of the following statements is false?
            (A)        Determinant of F is zero
            (B)        There are an infinite number of solutions to Fx = b
            (C)        There is an x ¹ 0 such that Fx = 0
            (D)        F must have two identical rows
24.        Given a set of elements N = {1, 2, …, n} and two arbitrary subsets A Í N and B Í N, how many of the n! permutations p from N to N satisfy min (p (A)) = min (p(B)), where min(S) is the smallest integer in the set of integers S, and p(S) is the set of integers obtained by applying permutation p to each element of S?
            (A)        (n - |A È B|) |A| |B|                             (B)        (|A|2 + |B|2) n2
            (C)        n!                                            (D)               
25.        Let S = {1, 2, 3, …, m}, m > 3. Let X1 … Xn be subsets of S each of size 3. Define a function f from S to the set of natural numbers as, f(i) is the number of sets Xj that contain the llement i. That is f(i) = |{j|i Î Xj|}|. Then  is
            (A)        3m                    (B)        3n                     (C)        2m + 1              2n + 1
26.        Which one of the first order predicate calculus statements given below correctly express the following English statement?
                        Tigers and lions attack if they are hungry or threatened.
            (A)        “x [(tiger (x) Ù lion (x)) ® {(hungry (x) Ú threatened (x)) ® attacks (x)}]
            (A)        “x [(tiger (x) Ú lion (x)) ® {(hungry (x) Ú threatened (x)) Ù attacks (x)}]
            (A)        “x [(tiger (x) Ú lion (x)) ® {(hungry (x) ® hungry (x) Ú threatened (x))}]
            (A)        “x [(tiger (x) Ú lion (x)) ® {(hungry (x) Ú threatened (x)) ® attacks (x)}]
27.        Consider the following propositional statements:
            P1: ((A Ù B) → C)) º ((A → C) Ù (B → C))
            P2: ((A Ú B) → C)) º ((A → C) Ú (B → C))
            Which one of the following is true?
            (A)        P1 is a tautology, but not P2
            (B)        P2 is a tautology, but not P1
            (C)        P1 and P2 are both tautologies
            (D)        Both P1 and P2 are not tautologies
28.        A logical binary relation , is defined as follows: W
           
A
B
A  B
True
True
True
True
False
True
False
True
False
False
False
True
            Let ~ be the unary negation (NOT) operator, with higher precedence then .
            Which one of the following is equivalent to A Ù B?
            (A)        (~ A  B)                                              (B)        ~ (A  ~ B)
            (C)        ~ (~ A  ~ B)                                       (D)        ~ (~ A  B)
29.        If s is a string over (0 + 1)* then let n0 (s) denote the number of 0′s in s and n1(s) the number of 1′s in s. Which one of the following languages is not regular?
            (A)        L = {S  Î (0 + 1) * | n0(s) is a 3-digit prime}
            (B)        L = {S  Î (0 + 1) * | for every prefix s¢ of s, |n0 (s¢) – n1 (s¢) | £ 2}
            (C)        L = {S  Î (0 + 1) * | n0(s) – n1 (s) | £ 4
            (D)        L = {S  Î (0 + 1) * | n0(s) mod 7 = n1 (s) mod 5  = 0}
30.        For S Î (0 + 1) * let d(s) denote the decimal value of s (e.g. d (101) = 5).
            Let L = {s Î (0 + 1) * | d(s) mod 5 = 2 and  (s) mod 7 ¹ 4}
            Which one of the following statements is true?
            (A)        L is recursively enumerable, but not recursive
            (B)        L is recursive, but not context-free
            (C)        L is context-free, but not regular
            (D)        L is regular
31.        Let SHAM3 be the problem of finding a Hamiltonian cycle in a graph G = (V, E) with |V| divisible by 3 and DHAM3 be the problem of determining if a Hamiltonian cycle exists in such graphs. Which one of the following is true?
            (A)        Both DHAM3 and SHAM3 are NP-hard
            (B)        SHAM3 is NP-hard, but DHAM3 is not
            (C)        DHAM3 is NP-hard, but SHAM3 is not
            (D)        Neither DHAM3 nor SHAM3 is NP-hard
32.        Consider the following statements about the context free grammar
            G = {S SS, S ab, S ba, S Î }
            I.          G is ambiguous
            II.         G produces all strings with equal number of a’s and b’s
            III.        G can be accepted by a deterministic PDA.
            Which combination below expresses all the true statements about G?
            (A)        I only
            (B)        I and III only
            (C)        II and III only
            (D)        I, II and III
33.        Let L1 be a regular language, L2 be a deterministic context-free language and L3 a recursively enumerable, but not recursive, language. Which one of the following statements is false?
            (A)        L1 Ç L2 is a deterministic CFL
            (B)        L3 Ç L1 is recursive
            (C)        L1 Ç L2 is context free
            (D)        L1 Ç L2 Ç L3 is recursively enumerable
34.        Consider the regular language L = (111 + 11111) * . The minimum number of states in any DFA accepting this languages is:
            (A)        3                      (B)        5                      (C)        8                      (D)        9
35.       
             Consider the circuit above. Which one of the following options correctly represents f (x, y, z)?
            (A)             (B)             (C)             
36.        Given two three bit numbers a2a1a0 and b2b1b0and c, the carry in the function that represents the carry generate function when these two numbers are added is:
            (A)        a2b2 + a2a1b1+ a2a1a0b0 + a2a0b1b0+ a1b2b1 + a1a0b2b0+ a0b2b1b0
            (B)        a2b2 + a2b1b0+ a2a1b1b0 + a1a0b2b1+ a1a0b2 + a1a0b2b0+ a2a0b1b0
            (C)        a2 + b2 + (a2 Å b2) (a1+ b1 + (a1 Å b1) (a0 + b0))
            (D)        a2b2 + a1b1+ a0b0+ a0b0+ a1b1+ a0b0+ a0b0
37.        Consider the circuit in the diagram. The Å operator represents Ex-OR. The D flip-flops are initialized to zeroes (cleared).
 
            The following date: 100110000 is supplied to the “data” terminal in nine clock cycles. After that the values of q2q1q0are:
            (A)        000                   (B)        001                   (C)        010                   (D)        101
38.        Consider a Boolean function f(w, x, y, z). Suppose that exactly one of its inputs is allowed to change at a time. If the function happens to be true for two input vectors i1 = áw1, x1, y1, z1ñ and i2 = áw2, x2, y2, z2ñ, we would like the function to remain true as the input changes from i1 to i2(i1 and i2 differ in exactly one bit position), without becoming false momentarily. Let f(w, x, y, z) = å (5, 7, 11, 12, 13, 15). Which of the following cube covers of f will ensure that the required property is satisfied?
            (A)        xz, wx, xz, xyz, wyz
            (B)        wxy, xz, wyz
            (C)        wx, xz, wyz
            (D)        wzy, wyz, wxz, xz, xz, xyz
39.        We consider the addition of two 2′s complement numbers bn-1 bn-2 … b0 and an-1 an-2… a0. A binary adder for adding unsigned binary numbers is used to add the two numbers. The sum is denoted by cn-1 cn-2 … c0 and the carry-out by cout.
            Which one of the following options correctly identifies the overflow condition?
            (A)        cout ()                                   (B)        an-1 bn-1  +
            (C)        cout Å cn-1                                               (D)        an-1 Å bn-1 Å cn-1
40.        Consider numbers represented in 4-bit gray code. Let h3h2h1h0be the gray code representation of a number n and let g3g2g1g0be the gray code of (n+1) (modulo 16) value of the number. Which one of the following functions is correct?
            (A)        g0 (h3h2h1h0) = å (1, 2, 3, 6, 10, 13, 14, 15)
            (B)        g1(h3h2h1h0) = å (4, 9, 10, 11, 12, 13, 14, 15)
            (C)        g2 (h3h2h1h0) = å (2, 4, 5, 6, 7, 12, 13, 15)
            (D)        g3 (h3h2h1h0) = å (0, 1, 6, 7, 10, 11, 12, 13)
41.        A CPU has a cache with block size 64 bytes. The main memory has k banks, each  bank being c bytes wide. Consecutive c – byte chunks are mapped on consecutive banks with wrap-around. All the k banks can be accessed in parallel, but two accesses to the same bank must be serialized. A cache block access may involve multiple iterations of parallel bank accesses depending on the amount of data obtained by accessing all the k banks in parallel. Each iteration requires decoding the bank numbers to be accessed in parallel and this takes . The latency of one bank access is 80 ns. If c = 2 and k = 24, the latency of retrieving a cache block starting at address zero from main memory is:
            (A)        92 ns                (B)        104 ns               (C)        172 ns               (D)        184 ns
42.        A CPU has a five-stage pipeline and runs at 1 GHz frequency. Instruction fetch happens in the first stage of the pipeline. A conditional branch instruction computes the target address and evaluates the condition in the third stage of the pipeline. The processor stops fetching new instructions following a conditional branch until the branch outcome is known. A program executes 109instructions out of which 20% are conditional branches. If each instruction takes one cycle to complete on average, the total execution time of the program is:
            (A)        1.0 second         (B)        1.2 seconds       (C)        1.4 seconds       (D)        1.6 seconds
43.        Consider a new instruction named branch-on-bit-set (mnemonic bbs). The instruction “bbs reg, pos, label” jumps to label if bit in position pos of register operand reg is one. A register is 32 bits wide and the bits are numbered 0 to 31, bit in position 0 being the least significant. Consider the following emulation of this instruction on a processor that does not have bbs implemented.
                        temp ¬ reg & mask
                        Branch to label if temp is non-zero.
            The variable temp is a temporary register. For correct emulation, the variable mask must be generated by
            (A)        mask ¬ 0 ´ 1 « pos
            (B)        mask ¬ 0 ´ ffffffff » pos
            (C)        mask ¬ pos
            (D)        mask ¬ 0 ´ f
 
44.        Station A uses 32 byte packets to transmit messages to Station B using a sliding window protocol. The round trip delay between A and B is 80 milliseconds and the bottleneck bandwidth on the path between A and B is 128 kbps. What is the optimal window size that A should use?
            (A)        20                     (B)        40                     (C)        160                   (D)        320
45.        Two computers C1 and C2 are configured as follows. C1 has IP address 203.197.2.53 and netmask 255.255.128.0. C2 has IP address 203.197.75.201 and netmask 255.255.192.0. which one of the following statements is true?
            (A)        C1 and C2 both assume they are on the same network
            (B)        C2 assumes C1 is on same network, but C1 assumes C2 is on a different network
            (C)        C1 assumes C2 is on same network, but C2 assumes C1 is on a different network
            (D)        C1 and C2 both assume they are on different networks.
46.        Station A needs to send a message consisting of 9 packets to Station B using a sliding window (window size 3) and go-back-n error control strategy. All packets are ready and immediately available for transmission. If every 5thpacket that A transmits gets lost (but no acks from B ever get lost), then what is the number of packets that A will transmit for sending the message to B?
            (A)        12                     (B)        14                     (C)        16                     (D)        18
47.        Consider the following graph:


 

            Which one of the following cannot be the sequence of edges added, in that order, to a minimum spanning tree using Kruskal’s algorithm?
            (A)        (a – b), (d – f), (b – f), (d – c), (d – e)     (B)        (a – b), (d – f), (d – c), (b – f), (d – e)
            (A)        (d – f), (a – b), (d – c), (b – f), (d – e)     (A)        (d – f), (a – b), (b – f), (d – e), (d – c)
48.        Let T be a depth first search tree in an undirected graph G. Vertices and u and v are leaves of this tree T. The degrees of both u and v in G are at least 2. which one of the following statements is true?
            (A)        There must exist a vertex w adjacent to both u and v in G
            (B)        There must exist a vertex w whose removal disconnects u and v in G
            (C)        There must exist a cycle in G containing u and v
            (D)        There must exist a cycle in G containing u and all its neighbours in G.
49.        An implementation of a queue Q, using two stacks S1 and S2, is given below:
            void insert (Q, x) {
                  push (S1, x);
            }
            void delete (Q) {
                  if (stack-empty(S2)) then
                        if (stack-empty(S1)) then {
                              print(“Q is empty”);
                              return;
                        }
                  else while (!(stack-empty(S1))){
                        x=pop(S1);
                        push(S2,x);
                        }
                   x=pop(S2);
             }
            Let n insert and m (£n) delete operations be performed in an arbitrary order on an empty queue Q. Let x and y be the number of push and pop operations performed respectively in the process. Which one of the following is true for all m and n?
            (A)        n + m £ x < 2n and 2m £ y £ n + m
            (B)        n + m £ x < 2n and 2m £ y £ 2n
            (C)        2m £ x < 2n and 2m £ y £ n + m
            (D)        2m £ x £ 2n and 2m £ y £ 2n
50.        A set X can be represented by an array x [n] as follows:
           
            Consider the following algorithm in which x, y and z are Boolean arrays of size n:
            algorithm zzz(x[ ], y[ ], z [ ] ) {
            int i;
            for(i=0;i<n;++i)
            z[i] = (x[i] ~y[i]) (~x[i] y[i])
            }
            The set Z computed by the algorithm is:
            (A)        (X È Y)                                                 (B)        (X Ç Y)
            (B)        (X - Y) Ç (Y - X)                                    (D)        (X - Y) È (Y - X)
51.        Consider the following recurrence:
            T(n) = 2T (éù) + 1, T(1) = 1
            Which one of the following is true?
            (A)        T(n) = q (log log n)                                (B)        T(n) = q (log n)
            (C)        T(n) = q                                        (D)        T(n) = q (n)
52.        The median of n elements can be found in O (n) time. Which one of the following is correct about the complexity of quick sort, in which median is selected as pivot?
            (A)        q(n)                  (B)        q(n log n)          (C)        q(n2)                 (D)        q(n3)
53.        Consider the following C-function in which a[n] and b[m] are two sorted integer arrays and c [n + m] be another integer array.
       void xyz(int a[], int b [], int c []){
             int i,j,k;
             i=j=k=0;
             while ((i<n) && (j<m))
                   if (a[i] < b[j]) c[k++] = a[i++];
                   else c[k++] = b[j++];
       }
           Which of the following condition(s) hold(s) after the termination of the while  loop?
            (i)         j < m, k = n + j -1, and a[n -1] < b[j] if i = n
            (ii)        i < n, k = m + i -1, and b[m - 1] £ a[i] if j = m
            (A)        only (i)                                                  (B)        only (ii)
            (C)        either (i) or (ii) but not both                    (D)        neither (i) nor (ii)
54.        Given two arrays of numbers a1, …, an and b1, …, bn where each number is 0 or 1, the fastest algorithm to find the largest span (i, j) such that
            ai + ai+1+ … + aj = bi + bi+1 + … + bj, or report that there is not such span,
            (A)        Takes O(3n) and W(2n) time if hashing is permitted
            (B)        Takes O(n3) and W(n2.5) time in the key comparison model
            (C)        Takes Q(n) time and space
            (D)        Takes O() time only if the sum of the 2n elements is an even number
55.        Consider these two functions and two statements S1 and S2 about them.
      int work1(int *a, int i, int j)     int work2(int *a, int i, int j)
      {                                   {
      int x = a[i+2];                     int t1 = i+2;
      a[j] = x+1;                               int t2 = a[t1];
      return a[i+2] – 3;                  a[j] = t2+1;
      }                                   return t2 – 3;
                                          }
            S1:       The transformation form work1 to work2 is valid, i.e., for any program state and input arguments, work2 will compute the same output and have the same effect on program state as work1
            S2:       All the transformations applied to work1 to get work2 will always improve the performance (i.e reduce CPU time) of work2 compared to work1
            (A)        S1 is false and S2 is false                       (B)        S1 is false and S2 is true
            (C)        S1 is true and S2 is false                        (D)        S1 is true and S2 is true
56.        Consider the following code written in a pass-by-reference language like  FORTRAN and these statements about the code.
            subroutine swap(ix,iy)
                  it = ix
            L1 : ix = iy
            L2 : iy = it
                end
                ia = 3
                ib = 8
                call swap (ia, 1b+5)
                print *, ia, ib
                end
            S1:       The compiler will generate code to allocate a temporary nameless cell, initialize it to 13, and pass the address of the cell swap
            S2:       On execution the code will generate a runtime error on line L1
            S3:       On execution the code will generate a runtime error on line L2
            S4:       The program will print 13 and 8
            S5:       The program will print 13 and -2
             Exactly the following set of statement(s) is correct:
            (A)        S1 and S2         (B)        S1 and S4         (C)        S3                    (D)        S1 and S5
57.        Consider this C code to swap two integers and these five statements: the code
            void swap (int *px, int *py) {
                  *px = *px – *py;
                  *py = *px + *py;
                  *px = *py – *px;
            }
            S1:       will generate a compilation error
            S2:       may generate a segmentation fault at runtime depending on the arguments passed
            S3:       correctly implements the swap procedure for all input pointers referring to integers stored in memory locations accessible to the process
            S4:       implements the swa p procedure correctly for some but not all valid input  pointers
            S5:       may add or subtract integers and pointers.
            (A)        S1                    (B)        S2 and S3         (C)        S2 and S4         (D)        S2 and S5
58         Consider the following grammar:
                        S ® FR
                        R ® *S|e
                        F ® id
            In the predictive parser table, M of the grammar the entries M[S, id] and M[R, $] respectively.
            (A)        {S ® FR} and {R ® e}
            (B)        {S ® FR} and { }
            (C)        {S ® FR} and {R ® *S}
            (D)        {F ® id} and {R ® e}
59.        Consider the following translation scheme.
                        S ® ER
                        R ® *E {print (‘*’);} R|e
                        E ® F + E {print (‘+’);}|F
                        F ® (S)|id {print (id.value);}
            Here id is a token that represents an integer and id.value represents the corresponding integer value. For an input ’2 * 3 + 4′, this translation scheme prints
            (A)        2 * 3 + 4           (B)        2 * + 3 4           (C)        2 3 * 4 +           (D)        2 3 4 + *
60.        Consider the following C code segment.
             for (i – 0, i<n; i++) {
                 for (j=0; j<n; j++) {
                     if (i%2) {
                         x += (4*j + 5*i);
                             y += (7 + 4*j);
                                     }
                         }
             }
            Which one of the following is false?
            (A)        The code contains loop invariant computation
            (B)        There is scope of common sub-expression elimination in this code
            (C)        There is scope of strength reduction in this code
            (D)        There is scope of dead code elimination in this code
61.        The atomic fetch-and-set x, y instruction unconditionally sets the memory location x to 1 and fetches the old value of x n y without allowing any intervening access to the memory location x. consider the following implementation of P and V functions on a binary semaphore S.
             void P (binary_semaphore *s) {
                   unsigned y;
                   unsigned *x = &(s->value);
                   do {
                 fetch-and-set x, y;
               } while (y);
             }
             void V (binary_semaphore *s) {
                   S->value = 0;
             }
            Which one of the following is true?
            (A)        The implementation may not work if context switching is disabled in P
            (B)        Instead of using fetch-and -set, a pair of normal load/store can be used
            (C)        The implementation of V is wrong
            (D)        The code does not implement a binary semaphore
62.        A CPU generates 32-bit virtual addresses. The page size is 4 KB. The processor has a translation look-aside buffer (TLB) which can hold a total of 128 page table entries and is 4-way set associative. The minimum size of the TLB tag is:
            (A)        11 bits               (B)        13 bits               (C)        15 bits               (D)        20 bits
63.        A computer system supports 32-bit virtual addresses as well as 32-bit physical addresses. Since the virtual address space is of the same size as the physical address space, the operating system designers decide to get rid of the virtual memory entirely. Which one of the following is true?
            (A)        Efficient implementation of multi-user support is no longer possible
            (B)        The processor cache organization can be made more efficient now
            (C)        Hardware support for memory management is no longer needed
            (D)        CPU scheduling can be made more efficient now
64.        Consider three processes (process id 0, 1, 2 respectively) with compute time bursts 2, 4 and 8 time units. All processes arrive at time zero. Consider the longest remaining time first (LRTF) scheduling algorithm. In LRTF ties are broken by giving priority to the process with the lowest process id. The average turn around time is:
            (A)        13 units             (B)        14 units             (C)        15 units             (D)        16 units
65.        Consider three processes, all arriving at time zero, with total execution time of 10, 20 and 30 units, respectively. Each process spends the first 20% of execution time doing I/O, the next 70% of time doing computation, and the last 10% of time doing I/O again. The operating system uses a shortest remaining compute time first scheduling algorithm and schedules a new process either when the running process gets blocked on I/O or when the running process finishes its compute burst. Assume that all I/O operations can be overlapped as much as possible. For what percentage of time does the CPU remain idle?
            (A)        0%                   (B)        10.6%               (C)        30.0%               (D)        89.4%
66.        Consider the following snapshot of a system running n processes. Process i is holding xi instances of a resource R, 1 £ i £ n. currently, all instances of R are occupied. Further, for all i, process i has placed a request for an additional yi instances while holding the xi instances it already has. There are exactly two processes p and q such that yp= yq = 0. Which one of the following can serve as a necessary condition to guarantee that the system is not approaching a deadlock?
            (A)        min (xp, xq) < maxk¹p,q yk
            (B)        xp+ xq ³ mink¹p,q yk
            (C)        max (xp, xq) > 1
            (D)        min (xp, xq) > 1
67.        Consider the relation account (customer, balance) where customer is a primary key and there are no null values. We would like to rank customers according to decreasing balance. The customer with the largest balance gets rank 1. ties are not broke but ranks are skipped: if exactly two customers have the largest balance they each get rank 1 and rank 2 is not assigned.
                  select A.customer, count(B.customer)
      Query1:     from account A, account B
                  where A.balance <=B.balance
                  group by A.customer
                  select A.customer, 1+count(B.customer)
      Query2:     from account A, account B
                  where A.balance < B.balance
                  group by A.customer
            Consider these statements about Query1 and Query2.
            1.         Query1 will produce the same row set as Query2 for some but not all databases.
            2.         Both Query1 and Query2 are correct implementation of the specification
            3.         Query1 is a correct implementation of the specification but Query2 is not
            4.         Neither Query1 nor Query2 is a correct implementation of the specification
            5.         Assigning rank with a pure relational query takes less time than scanning in  decreasing balance order assigning ranks using ODBC.
            Which two of the above statements are correct?
            (A)        2 and 5             (B)        1 and 3             (C)        1 and 4             (D)        3 and 5
68.        Consider the relation enrolled (student, course) in which (student, course) is the primary key, and the relation paid (student, amount) where student is the primary key. Assume no null values and no foreign keys or integrity constraints.
            Given the following four queries:
            Query1:             select student from enrolled where student in (select student from paid)
            Query2:             select student from paid where student in (select student from enrolled)
            Query3:             select E.student from enrolled E, paid P where E.student = P.student
            Query4:             select student from paid where exists
            (select * from enrolled where enrolled.student = paid.student)
            Which one of the following statements is correct?
            (A)        All queries return identical row sets for any database
            (B)        Query2 and Query4 return identical row sets for all databases but there exist databases for which Query1 and Query2 return different row sets.
            (C)        There exist databases for which Query3 returns strictly fewer rows than Query2
            (D)        There exist databases for which Query4 will encounter an integrity violation at runtime.
69.        Consider the relation enrolled (student, course) in which (student, course) is the primary key, and the relation paid (student, amount) where student is the primary key. Assume no null values and no foreign keys or integrity constraints. Assume that amounts 6000, 7000, 8000, 9000 and 10000 were each paid by 20% of the students. Consider these query plans (Plan 1 on left, Plan 2 on right) to “list all courses taken by students who have paid more than x”
 
            A disk seek takes 4ms, disk data transfer bandwidth is 300 MB/s and checking a tuple to see if amount is greater than x takes 10 ms. Which of the following statements is correct?
            (A)        Plan 1 and Plan 2 will not output identical row sets for all databases
            (B)        A course may be listed more than once in the output of Plan 1 for some databases
            (C)        For x = 5000, Plan 1 executes faster than Plan 2 for all databases
            (D)        For x = 9000, Plan I executes slower than Plan 2 for all databases.
70.        The following functional dependencies are given:
            AB ® CD, AF ® D, DE ® F, C ® G, F ® E, G ® A.
            Which one of the following options is fale?
            (A)        {CF}+= {ACDEFG}                                 (B)        {BG}+ = {ABCDG}
            (C)        {AF}+ = {ACDEFG}                                 (d)        {AB}+ = {ABCDFG}
Common Data Questions:
Common Data for Questions 71, 72, 73:
The 2n vertices of a graph G corresponds to all subsets of a set of size n, for n ³ 6. Two vertices of G are adjacent if and only if the corresponding sets intersect in exactly two elements.
71.        The number of vertices of degree zero in G is:
            (A)        1                      (B)        n                      (C)        n + 1                 (D)        2n
72.        The maximum degree of a vertex in G is:
            (A)        2n/2        (B)        2n-2                   (C)        2n-3 ´ 3             (D)        2n-1
73.        The number of connected components in G is:
            (A)        n                      (B)        n + 2                 (D)        2n/2                  (D)       
Common Data for Questions 74, 75:
Consider two cache organizations: The first one is 32 KB 2-way set associative with 32-byte block size. The second one is of the same size but direct mapped. The size of an address is 32 bits in both cases. A 2-to-1 multiplexer has a latency of 0.6 ns while a k-bit comparator has a latency of k/10 ns. The hit latency of the set associative organization is h1 while that of the direct mapped one is h2.
74.        The value of h1 is:
            (A)        2.4 ns               (B)        2.3 ns               (C)        1.8 ns               (D)        1.7 ns
75.        The value of h2 is:
            (A)        2.4 ns               (B)        2.3 ns               (C)        1.8 ns               (D)        1.7 ns
Linked Answer Questions: Q.76 to Q85 Carry Two Marks Each
Statement for Linked Answer Questions 76 & 77:
A 3-ary max heap is like a binary max heap, but instead of 2 children, nodes have 3 children. A 3-ary heap can be represented by an array as follows: The root is stored in the first location, a[0], nodes in the next level, from left to right, is stored from a[1] to a[3]. The nodes from the second level of the tree from left to right are stored from a[4] location onward. An item x can be inserted into a 3-ary heap containing n items by placing x in the location a[n] and pushing it up the tree to satisfy the heap property.
76.        Which one of the following is a valid sequence of elements in an array  representing 3-ary max heap?
            (A)        1, 3, 5, 6, 8, 9                                        (B)        9, 6, 3, 1, 8, 5
            (C)        9, 3, 6, 8, 5, 1                                        (D)        9, 5, 6, 8, 3, 1
77.        Suppose the elements 7, 2, 10 and 4 are inserted, in that order, into the valid 3-ary max heap found in the above question, Q.76. Which one of the following is the sequence of items in the array representing the resultant heap?
            (A)        10, 7, 9, 8, 3, 1, 5, 2, 6, 4                       (B)        10, 9, 8, 7, 6, 5, 4, 3, 2, 1
            (C)        10, 9, 4, 5, 7, 6, 8, 2, 1, 3                       (D)        10, 8, 6, 9, 7, 2, 3, 4, 1, 5
Statement for Linked Answer Questions 78 & 79:
Barrier is a synchronization construct where a set of processes synchronizes globally i.e. each process in the set arrives at the barrier and waits for all others to arrive and then all processes leave the barrier. Let the number of processes in the set be three and S be a binary semaphore with the usual P and V functions. Consider the following C implementation of a barrier with line numbers shown on left.
void barrier (void) {
1:    P(S);
2:    process_arrived++;
3.    V(S);
4:    while (process_arrived !=3);
5:    P(S);
6:    process_left++;
7:    if (process_left==3) {
8:    process_arrived = 0;
9:    process_left = 0;
10:   }
11:   V(S);
      }
The variables process_arrived and process_left are shared among all processes and are initialized to zero. In a concurrent program all the three processes call the barrier function when they need to synchronize globally.
78.        The above implementation of barrier is incorrect. Which one of the following is true?
            (A)        The barrier implementation is wrong due to the use of binary semaphore S
            (B)        The barrier implementation may lead to a deadlock if two barrier in invocations are used in immediate succession.
            (C)        Lines 6 to 10 need not be inside a critical section
            (D)        The barrier implementation is correct if there are only two processes instead of three.
79.        Which one of the following rectifies the problem in the implementation?
            (A)        Lines 6 to 10 are simply replaced by process_arrived–
            (B)        At the beginning of the barrier the first process to enter the barrier waits  until process_arrived becomes zero before proceeding to execute P(S).
            (C)        Context switch is disabled at the beginning of the barrier and re-enabled at the end.
            (D)        The variable process_left is made private instead of shared
Statement for Linked Answer Questions 80 & 81:
A CPU has a 32 KB direct mapped cache with 128-byte block size. Suppose A is a two-dimensional array of size 512 × 512 with elements that occupy 8-bytes each. Consider the following two C code segments, P1 and P2.
P1:   for (i=0; i<512; i++) {
            for (j=0; j<512; j++) {
                 x +=A[i] [j];
            }
       }
P2:   for (i=0; i<512; i++) {
             for (j=0; j<512; j++) {
                 x +=A[j] [i];
             }
       }
P1 and P2 are executed independently with the same initial state, namely, the array A is not in the cache and i, j, x are in registers. Let the number of cache misses experienced by P1 be M1 and that for P2 be M2.
80.        The value of M1 is:
            (A)        0                      (B)        2048                 (C)        16384               (D)        262144
81.        The value of the ratio  is:
            (A)        0                      (B)                           (C)                            (D)        16
Statement for Linked Answer Questions 82 & 83:
Consider the diagram shown below where a number of LANs are connected by (transparent) bridges. In order to avoid packets looping through circuits in the graph, the bridges organize themselves in a spanning tree. First, the root bridge is identified as the bridge with the least serial number. Next, the root sends out (one or more) data units to enable the setting up of the spanning tree of shortest paths from the root bridge to each bridge.
Each bridge identifies a port (the root port) through which it will forward frames to the root bridge. Port conflicts are always resolved in favour of the port with the lower index value. When there is a possibility of multiple bridges forwarding to the same LAN (but not through the root port), ties are broken as follows: bridges closest to the root get preference and between such bridges, the one with the lowest serial number is preferred.
 
82.        For the given connection of LANs by bridges, which one of the following choices represents the depth first traversal of the spanning tree of bridges?
            (A)        B1, B5, B3, B4, B2                                   (B)        B1, B3, B5, B2, B4
            (C)        B1, B5, B2, B3, B4                                   (D)        B1, B3, B4, B5, B2
83.        Consider the correct spanning tree for the previous question. Let host H1 send out a broadcast ping packet. Which of the following options represents the correct forwarding table on B3?
            (A)        Hosts                                                    Port
                        H1, H2, H3, H4                                       3
                        H5, H6, H9, H10                                     1
                        H7, H8, H11, H12                                    2
            (B)        Hosts                                                    Port
                        H1, H2                                                   4
                        H3, H4                                                   3
                        H5, H6                                                   1
                        H5, H8 1 H9, H10, H11, H12                     2
            (C)        Hosts                                                    Port
                        H3, H4                                                   3
                        H5, H6, H9, H10                                     1
                        H1, H2                                                   4
                        H7, H8, H11, H12                                    2
            (D)        Hosts                                                    Port
                        H1, H2, H3, H4                                       3
                        H5, H7, H9, H10                                     1
                        H7, H8, H11, H12                                    4
Statement for Linked Answer Questions 84 & 85:
84.        Which one of the following grammars generates the language L = {ai bj | i ¹ j}?
            (A)        S AC | CB
                        C aC b | a | b
                        A a A | Î
                        B B b | Î
            (B)        S aS | Sb | a | b
            (C)        S AC | CB
                        C aCb | Î
                        A a A | Î
                        B Bb | Î
            (D)        S AC | CB
                        C aCb | Î
                        A aA | a
                        B B b | b
85.        In the correct grammar above, what is the length of the derivation (number of steps starring from S) to generate the string albm with l ¹ m?
            (A)        max (l, m) + 2                                       (B)        l + m + 2
            (C)        l + m + 3                                               (D)        max (l, m) + 3
End of Question Paper
Dear friends, you can discuss answers through comments. And please give your answers ( with explanation if possible ), you will help others. If you feel that an answer is wrong, please discuss it.

Q.1 – Q.30 carry one mark each.

1.         What does the following C-statement declare?
            int ( * f) (int * ) ;
            (a)        A function that takes an integer pointer as argument and returns an integer
            (b)        A function that takes an integer as argument and returns an integer pointer
            (c)        A pointer to a function that takes an integer pointer as argument and returns an integer.
            (d)        A function that takes an integer pointer as argument and returns a function pointer
2.         An Abstract Data Type (ADT) is:
            (a)        same as an abstract class
            (b)        a data type that cannot be instantiated
            (c)        a data type for which only the operations defined on it can be used, but none else
            (d)        all of the above
3.         A common property of logic programming languages and functional languages is:
            (a)        both are procedural languages
            (b)        both are based on l-calculus
            (c)        both are declarative
            (d)        both use Horn-clauses
4.         Which one of the following are essential features of an object-oriented programming language?
            (i)         Abstraction and encapsulation
            (ii)        Strictly-typedness
            (iii)       Type-safe property coupled with sub-type rule
            (iv)       Polymorphism in the presence of inheritance
            (a)        (i) and (ii) only                                       (b)        (i) and (iv) only
            (c)        (i), (ii) and (iv) only                                (d)        (i), (iii) and (iv) only
5.         A program P reads in 500 integers in the range [0,100] representing the scores of 500 students. It then prints the frequency of each score above 50. What would be the best way for P to store the frequencies?
            (a)        An array of 50 numbers
            (b)        An array of 100 numbers
            (c)        An array of 500 numbers
            (d)        A dynamically allocated array of 550 numbers
6.         An undirected graph G has n nodes. Its adjacency matrix is given by an n ´ n square matrix whose (i) diagonal elements are 0′s and (ii) non-diagonal elements are 1′s. which one of the following is TRUE?
            (a)        Graph G has no minimum spanning tree (MST)
            (b)        Graph G has a unique MST of cost n-1
            (c)        Graph G has multiple distinct MSTs, each of cost n-1
            (d)        Graph G has multiple spanning trees of different costs
7.         The time complexity of computing the transitive closure of a binary relation on a set of n elements is known to be:
            (a)        O(n)                  (b)        O(n log n)          (c)                     (d)        O(n3)
8.         Let A, B and C be non-empty sets and let
            X = (A – B) – C and Y = (A – C) – (B – C)
            Which one of the following is TRUE?
            (a)        X = Y                (b)        X Ì Y                (c)        Y Ì X                (d)        None of these
9.         The following is the Hasse diagram of the poset [{a,b,c,d,e},]


 

           The poset is:
            (a)        not a lattice
            (b)        a lattice but not a distributive lattice
            (c)        a distributive lattice but not a Boolean algebra
            (d)        a Boolean algebra
10.        Let G be a simple connected planar graph with 13 vertices and 19 edges. Then, the number of faces in the planar embedding of the graph is:
            (a)        6                      (b)        8                      (c)        9                      (d)        13
11.        Let G be a simple graph with 20 vertices and 100 edges. The size of the minimum vertex cover of G is 8. then, the size of the maximum independent set of G is:
            (a)        12                     (b)        8                      (c)        Less than 8        (d)        More than 12
12.        Let f(x) be the continuous probability density function of a random variable X.
            The probability that a < X b, is:
            (a)        f (b – a)            (b)        f (b) – f(a)         (c)                   (d)       
13.        The set {1, 2, 4, 7, 8, 11, 13, 14} is a group under multiplication modulo 15. The inverses of 4 and 7 are respectively:
            (a)         and 13             (b)        2 and 11            (c)        4 and 13            (d)        8 and 14
14.        The grammar A ® AA | (A) | e is not suitable for predictive-parsing because the grammar is:
            (a)        ambiguous                                             (b)        left-recursive
            (c)        right-recursive                                       (d)        an operator-grammar
15.        Consider the following circuit.


 

            Which one of the following is TRUE?
            (a)        f is independent of X                               (b)        f is independent of Y
            (c)        f is independent of Z                               (d)        None of X, Y, Z is redundant
16.        The range of integers that can be represented by an n bit 2′s complement number system is:
            (a)        -2n-1to (2n-1- 1)                                   (b)        -2(2n-1- 1) to (2n-1 – 1)
            (c)        -2n-1to 2n-1                                           (d)        -2(2n-1+ 1) to (2n-1- 1)
17.        The hexadecimal representation of 6578 is:
            (a)        1AF                   (b)        D78                  (c)        D71                   (d)        32F
18.        The switching expression corresponding to f(A,B,C,D)= is:
            (a)        BC¢D¢ + A¢C¢D + AB¢D                              (b)        ABC¢ + ACD + B¢C¢D
            (C)        ACD¢ + A¢BC¢ + AC¢D¢                             (c)        A¢BD + ACD¢ + BCD¢
19.        Which one of the following is true for a CPU having a single interrupt request line and a single interrupt grant line?
            (a)        Neither vectored interrupt nor multiple interrupting devices are possible
            (b)        Vectored interrupts are not possible but multiple interrupting devices are possible.
            (c)        Vectored interrupts and multiple interrupting devices are both possible
            (d)        Vectored interrupt is possible but multiple interrupting devices are not possible
20.        Normally user programs are prevented from handling I/O directly by I/O instructions in them. For CPUs having explicit I/O instructions, such I/O protection is ensured by having the I/O instructions privileged. In a CPU with memory mapped I/O, there is no explicit I/O instruction. Which one of the following is true for a CPU with memory mapped I/O?
            (a)        I/O protection is ensured by operating system routine(s)
            (b)        I/O protection is ensured by a hardware trap
            (c)        I/O protection is ensured during system configuration
            (d)        I/O protection is not possible
21.        What is the swap space in the disk used for?
            (a)        Saving temporary html pages                  (b)        Saving process data
            (c)        Storing the super-block                           (d)        Storing device drivers
22.        Increasing the RAM of a computer typically improves performance because:
            (a)        Virtual memory increases                        (b)        Larger RAMs are faster
            (c)        Fewer page faults occur              (d)        Fewer segmentation faults occur
23.        Packets of the same session may be routed through different paths in:
            (a)        TCP, but not UDP                                    (b)        TCP and UDP
            (c)        UDP, but not TCP                                    (d)        Neither TCP nor UDP
24.        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
            (c)        Finding the IP address that corresponds to a MAC address
            (d)        Finding the MAC address that corresponds to an IP address
25.        The maximum window size for data transmission using the selective reject protocol with n-bit frame sequence numbers is:
            (a)        2n                     (b)        2n-1                   (c)        2n – 1                (d)        2n-2


26.        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
            (c)        For fault tolerance
            (d)        For minimizing collisions
27.        An organization has a class B network and wishes to form subnets for 64 departments. The subnet mask would be:
            (a)        255.255.0.0       (b)        255.255.64.0     (c)        255.255.128.0 (d)          255.255.252.0
28.        Which one of the following is a key factor for preferring B+-trees to binary search trees for indexing database relations?
            (a)        Database relations have a large number of records
            (b)        Database relations are sorted on the primary key
            (c)        B+-trees require less memory than binary search trees
            (d)        Data transfer form disks is in blocks
29.        Which one of the following statements about normal forms is FALSE?
            (a)        BCNF is stricter than 3NF
            (b)        Lossless, dependency-preserving decomposition into 3NF is always possible
            (c)        Lossless, dependency-preserving decomposition into BCNF is always possible
            (d)        Any relation with two attributes is in BCNF
30.        Let r be a relation instance with schema R = (A, B, C, D). We define r1 = PA,B,C (R) and r2 = PA,D (r). Let s = r1 * r2 where * denotes natural join. Given that the decomposition of r into r1 and r2 is lossy, which one of the following is TRUE?
            (a)        s Ì r                 (b)        r È s = r           (c)        r Ì s                 (d)        r * s = s
Q.31 to Q.80 carry two m arks each.
31.        Consider the following C-program:
            void foo (int n, int sum 0) {
            int k = 0, j = 0;
            if (n==0) return;
            k = n % 10; j = n / 10;
            sum = sum + k;
            foo (j, sum);
            printf (“%d,”, k);
             }
            int main () {
            int a = 2048, sum = 0;
            foo (a, sum);
            printf(“%d\n”, sum);
            }
            What does the above program print?
            (a)        8, 4, 0, 2, 14      (b)        8, 4, 0, 2, 0       (c)        2, 0, 4, 8, 14      (d)        2, 0, 4, 8, 0
32.        Consider the following C-program:
            double foo (double); /* Line 1 */
            int main () {
            double da, db;
            // input da
            db = foo (da);
            }
            double foo (double a) {
            return a;
             }
            The above code compiled without any error or warning. If Line 1 is deleted, the above code will show:
            (a)        no compile warning or error
            (b)        some compiler-warnings not leading to unintended results
            (c)        some compiler-warnings due to type-mismatch eventually leading to unintended results
            (d)        compiler errors
33.        Postorder traversal of a given binary search tree, T produces the following sequence of keys
            10, 9, 23, 22, 27, 25, 15, 50, 95, 60, 40, 29
            Which one of the following sequences of keys can be the result of an in-order traversal of the tree T?
            (a)        9, 10, 15, 22, 23, 25, 27, 29, 40, 50, 60, 95
            (b)        9, 10, 15, 22, 40, 50, 60, 95, 23, 25, 27, 29
            (c)        29, 15, 9, 10, 25, 22, 23, 27, 40, 60, 50, 95
            (d)        95, 50, 60, 40, 27, 23, 22, 25, 10, 9, 15, 29
34.        A Priority-Queue is implemented as a Max-Heap. Initially, it has 5 elements. The level-order 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
            (c)        10, 8, 7, 1, 2, 3, 5                                  (d)        10, 8, 7, 3, 2, 1, 5
35.        How many distinct binary search trees can be created out of 4 distinct keys?
            (a)        5                      (b)        14                     (c)        24                     (d)        42
36.        In a complete k-ary tree, every internal node has exactly k children. The number of leaves in such a tree with n internal nodes is:
            (a)        nk                     (b)        (n – 1) k + 1      (c)        n(k – 1) + 1       (d)        n(k – 1)
37.        Suppose T (n) = 2T  + n, T (0) = T(1) = 1
            Which one of the following is FALSE?
            (a)        T(n) = O(n2)                                          (b)        T(n) = q (n log n)
            (c)        T(n) = W (n2)                                        (d)        T(n) = O (n log n)
38.        Let G(V,E) be an undirected graph with positive edge weights. Dijkstra’s single source shortest path algorithm can be implemented using the binary heap data structure with time complexity:
            (a)        O (|V|2)                                                            (b)        O(|E| + |V|log|V|)
            (c)        O(|V|log|V|)                                         (d)        O((|E| + |V|) log |V|)
39.        Suppose there are [log n] sorted lists of [n/log n] elements each. The time complexity of producing a sorted list of all these elements is: (Hint: Use a heap data structure)
            (a)        O (n log log n)   (b)        q (n log n)         (c)        W (n log n)        (d)        W
40.        Let P, Q and R be tree atomic prepositional assertions. Let X denote (P Ú Q) ® R and Y denote
(P ® R) Ú (Q ® R). Which one of the following is a tautology?
            (a)        X º Y                 (b)        X ® Y               (c)        Y ® X               (d)        ¬Y ® X
41.        What is the first order predicate calculus statement equivalent to the following?
            Every teacher is liked by some student
            (a)        “(x)[teacher(x) ® $(y) [student(y) ® likes (y,x)]]
            (b)        “(x)[teacher(x) ® $(y) [student(y) Ù likes (y,x)]]
            (c)        $(y) “(x)[teacher(x) ® [student(y) Ù likes (y,x)]]
            (d)        “(x)[teacher(x) Ù $(y) [student(y) ® likes (y,x)]]
42.        Let R and S be any two equivalence relations on a non-empty set A. Which one of the following statements is TRUE?
            (a)        R È S, R Ç S are both equivalence relations.
            (b)        R È S is an equivalence relation.
            (c)        R Ç S is an equivalence relation.
            (d)        Neither R È S nor R Ç S is an equivalence relation
43.        Let f: B ® C and g: A ® B be two functions let h =  f ° g. Given that h is an onto function which one of the following is TRUE?
            (a)        f and g should both be onto functions
            (b)        f should be onto but g need to be onto
            (c)        g should be onto but f need not be onto
            (d)        both f and g need to be onto
44.        What is the minimum number of ordered pairs of non-negative numbers that should be chosen to ensure that there are two pairs (a,b) and (c,d) in the chosen set such that
            a º c mod 3 and b º d mod 5
            (a)        4                      (b)        6                      (c)        16                     (d)        24
45.        Consider three decision problems P1, P2 and P3. It is known that P1 is decidable and P2 is undecidable. Which one of the following is true?
            (a)        P3 is decidable if P1is reducible to P3
            (b)        P3 is undecidable if P3is reducible to P2
            (c)        P3 is undecidable if P2is reducible to P3
            (d)        P3 is decidable if P3is reducible to P2¢s complement
46.        Consider the set H of all 3 ´ 3 matrices of the type
            where a,b,c,d,e and f are real numbers and abc 0. under the matrix multiplication operation, the set H is:
            (a)        a group                                                 (b)        a monoid but not a group
            (c)        a semi group but not a monoid                (d)        neither a group nor a semi group


47.        Which one of the following graphs is NOT planar?
            (a)        G1                     (b)        G2                     (c)        G3                     (d)        G4
48.        Consider the following system of equations in three real variables x x x , and :
                        2x1 – x2 + 3x3 = 1
                        3x1 + 2x2+ 5x3 = 2
                        -x1 + 4x2 + x3= 3
            The system of equations has
            (a)        no solution
            (b)        a unique solution
            (c)        more than one but a finite number of solutions
            (d)        an infinite number of solutions
49.        What are the eigen values of the following 2 × 2 matrix?
           
            (a)        -1 and 1            (b)        1 and 6             (c)        2 and 5             (d)        4 and -1
50.        Let G(x) =  = , where |x| < 1. What is g(i)?
            (a)        i                       (b)        i + 1                  (c)        2i                      (d)        2i
51.        Box P has 2 red balls and 3 blue balls and box Q has 3 balls and 1 blue ball. A ball is selected as follows: (i) select a box (ii) choose a ball from the selected box such that each ball in the box is equally likely to be chosen. The probabilities of selecting boxes P and Q are 1/3 and 2/3 respectively. Given that a ball selected in the above process is a red ball, the probability that it came from the box P is:
            (a)        4/19                  (b)        5/19                  (c)        2/9                   (d)        19/30
52.        A random bit string of length n is constructed by tossing a fair coin n times and setting a bit to 0 or 1 depending on outcomes head and tail, respectively. The probability that two such randomly generated strings are not identical is:
            (a)                           (b)        1 –                (c)                            (d)        1 –
53.        Consider the machine M:
            The language recognized by M is:
            (a)        {w Î {a, b} * | every a in w is followed by exactly two b’s}
            (b)        {w Î {a,b} * | every a in w is followed by at least two b’s}
            (c)        {w Î {a,b} * | w contains the substring ‘abb’}
            (d)        {w Î {a,b} * | w does not contain ‘aa’ as a substring
54.        Let Nfand np denote the classes of languages accepted by non-deterministic finite automata and non-deterministic push-down automata, respectively. Let Dfand Dp denote the classes of languages accepted by deterministic finite automata and deterministic push-down automata respectively. Which one of the following is TRUE?
            (a)        Df Ì Nf and Dp Ì Np                                            (b)        DfÌ Nf and Dp = Np
            (c)        Df = Nf and Dp = Np                                            (d)        Df= Nf and Dp Ì Np
55.        Consider the languages:
             and
            Which one of the following statements is FALSE?
            (a)        L1Ç L2 is a context-free language
            (b)        L1È L2 is a context-free language
            (c)        L1and L2 are context-free language
            (d)        L1 Ç L2 is a context sensitive language     
56.        Let L1 be a recursive language, and let L2 be a recursively enumerable but not a recursive language. Which one of the following is TRUE?
            (a)        is recursive and  is recursively enumerable
            (b)         is recursive and  is not recursively enumerable
            (c)         and  are recursively enumerable
            (d)         is recursively enumerable and  is recursive


57.        Consider the languages:
           
            L2 = , where # is a special symbol
            L3 = {ww|w Î {0, 1}*}
            Which one of the following is TRUE?
            (a)        L1is a deterministic CFL                          (b)        L2 is a deterministic CFL
            (c)        L3is a CFL, but not a deterministic CFL     (d)        L3 is a deterministic CFL
58.        Consider the following two problems on undirected graphs:
            a : Given G(V,E), does G have an independent set of size |V| – 4?
            b : Given G(V,E), does G have an independent set of size 5?
            Which one of the following is TRUE?
            (a)        a is in P and b is NP-complete                 (b)        a is NP-complete and b is in P
            (c)        Both a and b are NP-complete                 (d)        Both a and b are in P
59.        Consider the grammar:
            E ® E + n | E ´ n | n
            For a sentence n + n ´ n, the handles in the right-sentential form of the reduction are:
            (a)        n, E + n and E + n ´ n                            (b)        n, E + n and E + E ´ n
            (c)        n, n + n and n + n ´ n                            (d)        n, E + n and E ´ n
60.        Consider the grammar:
            S ® (S) | a
            Let the number of states in SLR (1), LR(1) and LALR(1) parsers for the grammar be n1, n2 and n3 respectively. The following relationship holds good:
            (a)        n1< n2 < n3       (b)        n1 = n3< n2          (c)        n1 = n2 = n3          (d)        n1³ n3 ³ n2
61.        Consider line number 3 of the following C-program.
                         int min ( ) {                              /* Line 1 */
                         int I, N;                                    /* Line 2 */
                         fro (I =0, I<N, I++);                  /* Line 3 */
                         }
            Identify the compiler’s response about this line while creating the object-module:
            (a)        No compilation error
            (b)        Only a lexical error
            (c)        Only syntactic errors
            (d)        Both lexical and syntactic errors


62.        Consider the following circuit involving a positive edge triggered D FF.


 


            Consider the following timing diagram. Let Ai represent the logic level on the line a in the i-th clock period


 


            Let A¢ represent the complement of A. The correct output sequence on Y over the clock periods 1 through 5 is:
            (a)                                            (b)       
            (a)                                            (a)       
63.        The following diagram represents a finite state machine which takes as input a binary number from the least significant bit.
 
             Which one of the following is TRUE?
             (a)       It computes 1′s complement of the input number
             (b)       It computes 2′s complement of the input number
             (c)       It increments the input number
             (d)       It decrements the input number
 
64.        Consider the following circuit.


 

            The flip-flops are positive edge triggered D FFs. Each state is designated as a two-bit string Q0 Q1 . Let the initial state be 00. the state transition sequence is
            (a)        00 ® 11 ® 01                                       (b)        00 ® 11
            (c)        00 ® 10 ® 01 ® 11                              (d)        00 ® 11 ® 01 ® 10
65.        Consider a three word machine instruction ADD A[R0], @B
            The first operand (destination) “A[R0]” uses indexed addressing mode with R0 as the index register. The second operand (source) “@B” uses indirect addressing mode. A and B are memory addresses residing at the second and the third words, respectively. The first word of the instruction specifies the opcode, the index register designation and the source and destination addressing modes.
            During execution of ADD instruction, the two operands are added and stored in the destination (first operand).
            The number of memory cycles needed during the execution cycle of the instruction is:
            (a)        3                      (b)        4                      (c)        5                      (d)        6
66.        Match each of the high level language statements given on the left hand side with the most natural addressing mode from those listed on the right hand side.
            (1)        A[I] = B[J];                                            (a)        Indirect addressing
            (2)        while (*A++);                                        (b)        Indexed addressing
            (3)        int temp =*x;                                        (c)        Auto increment
            (a)        (1, c), (2,b), (3,a)                                  (b)        (1, a), (2,c), (3,b)
            (c)        (1, b), (2,c), (3,a)                                  (d)        (1, a), (2,b), (3,c)
67.        Consider a direct mapped cache of size 32 KB with block size 32 bytes. The CPU generates 32 bit addresses. The number of bits needed for cache indexing and the number of tag bits are respectively.
            (a)        10, 17               (b)        10, 22               (c)        15, 17               (d)        5, 17
68.        A 5 stage pipelined CPU has the following sequence of stages:
            IF         –          Instruction fetch from instruction memory.
            RD        -          Instruction decode and register read.
            EX        -          Execute: ALU operation for data and address computation.
            MA        -          Data memory access œ for write access, the register read at RD state is used.
            WB       -          Register write back.
            Consider the following sequence of instructions:
            I1 : L R0, loc 1; R0 <= M[loc1]
            I2 : A R0, R0 1; R0 <= R0 + R0
            I3 : S R2, R0 1; R2 <= R2 – R0
            Let each stage take one clock cycle.  What is the number of clock cycles taken to complete the above sequence of instructions starting from the fetch of I1 ?
            (a)        8                      (b)        10                     (c)        12                     (d)        15
69.        A device with data transfer rate 10 KB/sec is connected to a CPU. Data is transferred byte-wise. Let the interrupt overhead be 4 sec. The byte transfer time between the device interfaces register and CPU or memory is negligible. What is the minimum performance gain of operating the device under interrupt mode over operating it under program-controlled mode?
            (a)        15                     (b)        25                     (c)        35                     (d)        45
70.        Consider a disk drive with the following specifications:
            16 surfaces, 512 tracks/surface, 512 sectors/track, 1 KB/sector, rotation speed 3000 rpm. The disk is operated in cycle stealing mode whereby whenever one 4 byte word is ready it is sent to memory; similarly, for writing, the disk interface reads a 4 byte word from the memory in each DMA cycle. Memory cycle time is 40 nsec. The maximum percentage of time that the CPU gets blocked during DMA operation is:
            (a)        10                     (b)        25                     (c)        40                     (d)        50
71.        Suppose n processes, P1, …. Pn share m identical resource units, which can be reserved and released one at a time. The maximum resource requirement of process Pi is si , where s >0. Which one of the following is a sufficient condition for ensuring that deadlock does not occur?
            (a)        i, si < m                                              (b)        i, si < n
            (c)                                             (d)       
72.        Consider the following code fragment:
                        if (fork () ==0)
                         { a = a + 5; printf(“%d,%d\n”, a, &a); }
                         else { a = a –5; printf(“%d, %d\n”, a, &a); }
            Let u, be the values printed by the parent process, and x,y be the values printed by the child process. Which one of the following is TRUE?
            (a)        u = x + 10 and = y                                 (b)        u = x + 10 and is y
            (c)        u + 10 = x and = y                                 (d)        u + 10 = x and y
73.        In a packet switching network, packets are routed from source to destination along a single path having two intermediate nodes. If the message size is 24 bytes and each packet contains a header of 3 bytes, then the optimum packet size is:
            (a) 4                             (b)        6                      (c)        7                      (d)        9
74.        Suppose the round trip propagation delay for a 10 Mbps Ethernet having 48-bit jamming signal is 46.4 s. The minimum frame size is:
            (a)        94                     (b)        416                   (c)        464                   (d)        512
75.        Let E1and E2 be two entities in an E/R diagram with simple single-valued attributes. R1 and R2 are two relationships between E1and 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 minimum number of tables required to represent this situation in the relational model?
            (a)        2                      (b)        3                      (c)        4                      (d)        5


76.        The following table has two attributes A and C where A is the primary key and C is the foreign key referencing a with on-delete cascade.
A
C
2
4
3
4
4
3
5
2
7
2
9
5
6
4
            The set of all tuples that must be additionally deleted to preserve referential integrity when the tuple (2,4) is deleted is:
            (a)        (3,4) and (6,4)                                       (b)        (5,2) and (7,2)
            (c)        (5,2), (7,2) and (9,5)                              (d)        (3,4), (4,3) and (6,4)
77.        The relation book (title,price) contains the titles and prices of different books. Assuming that no two books have the same price, what does the following SQL query list?
                         select title
                         from book as B
                         where (select count(*)
                         from book as T
                         where T.price>B.price)<5
             (a)       Titles of the four most expensive books     (b)       Title of the fifth most inexpensive book
             (c)       Title of the fifth most expensive book        (d)       Titles of the five most expensive books
78.        Consider a relation scheme R = (A,B,C,D,E,H) on which the following functional dependencies hold: {A ® B, BC ® D, E ® C, D ® A}. What are the candidate keys of R?
            (a) AE, BE                                  (b) AE, BE, DE
            (c) AEH, BEH, BCH                      (d) AEH, BEH, DEH
Common Data for questions 79 and 80:
Consider the following data path of a CPU. The ALU, the bus and all the registers in the data path are of identical size. All operations including incrementation of the PC and the GPRs are to be carried out in the ALU. Two clock cycles are needed for memory read operation œ the first one for loading address in the MAR and the next one for loading data from the memory bus into the MDR.
79.        The instruction “add R0, R1″ has the register transfer interpretation R0<= R0+R1. The minimum number of clock cycles needed for execution cycle of this instruction is:
            (a)        2                      (b)        3                      (c)        4                      (d)        5
80.        The instruction “call Rn, sub” is a two word instruction. Assuming that PC is incremented during the fetch cycle of the first word of the instruction, its register transfer interpretation is
                        Rn<= PC+1;
                        PC<=M[PC];
            The minimum number of CPU clock cycles needed during the execution cycle of this instruction is:
            (a)        2                      (b)        3                      (c)        4                      (d)        5
Linked Answer Questions: Q.81a to Q.85b carry two marks each.
Statement for Linked Answer Questions 81a & 81b:
Consider the following C-function:
            double foo (int n) {
            int i;
            double sum;
            if (n==0) return 1.0;
            else {
            sum = 0.0;
            for (i =0; i<n; i++)
            sum +=foo(i);
            return sum;
            } }
81a.      The space complexity of the above function is:
            (a)        O(1)                  (b)        O(n)                  (c)        O(n!)                 (d)        O(nn)
81b.      Suppose we modify the above function foo() and store the values of foo(i), 0<=I<n , as and when they are computed. With this modification, the time complexity for function foo() is significantly reduced. The space complexity of the modified function would be:
            (a)        O(1)                  (b)        O(n)                  (c)        O(n2)                (d)        O(n!)
Statement for Linked Answer Questions 82a & 82b:
Let s and t be two vetices in a undirected graph G=(V,E) having distinct positive edge weights. Let [X,Y] be a partition of V such that s X and T Y. Consider the edge e having the minimum weight amongst all those edges that have one vertex in X and one vertex in Y.
82a.      The edge e must definitely belong to:
            (a)        the minimum weighted spanning tree of G
            (b)        the weighted shortest path from s to t
            (c)        each path from s to t
            (d)        the weighted longest path from s to t
82b.      Let the weight of an edge e denote the congestion on that edge. The congestion on a path is defined to be the maximum of the congestions on the edges of the path. We wish to find the path from s to t having minimum congestion. Which one of the following paths is always such a path of minimum congestion?
            (a)        a path from s to t in the minimum weighted spanning tree
            (b)        a weighted shortest path from s to t
            (c)        an Euler walk from s to t
            (d)        a Hamiltonian path from s to t


Statement for Linked Answer Questions 83a & 83b:
Consider the following expression grammar. The semantic rules for expression evaluation are stated next to each grammar production.
            E → number                              E.val = number.val
            | E ‘+’ E                                     E(1) × val = E(2) × val + E(3)× val
            | E ‘´’ E                                     E(1) × val = E(2) × val ´ E(3) × val
83a.      The above grammar and the semantic rules are fed to a yacc tool (which is an LALR(1) parser generator) for parsing and evaluating arithmetic expressions. Which one of the following is true about the action of yacc for the given grammar?
            (a)        It detects recursion and eliminates recursion
            (b)        It detects reduce-reduce conflict, and resolves
            (c)        It detects shift-reduce conflict, and resolves the conflict in favor of a shift over a reduce action.
            (d)        It detects shift-reduce conflict, and resolves the conflict in favor of a reduce over a shift action.
83b.      Assume the conflicts in Part (a) of this question are resolved and an LALR(1) parser is generated for parsing arithmetic expressions as per the given grammar. Consider an expression 3 ´ 2 + 1. What precedence and associativity properties does the generated parser realize?
            (a)        Equal precedence and left associativity; expression is evaluated to 7
            (b)        Equal precedence and right associativity; expression is evaluated to 9
            (c)        Precedence of ‘×’ is higher than that of ‘+’, and both operators are left associative; expression is evaluated to 7
            (d)        Precedence of ‘+’ is higher than that of ‘×’, and both operators are left associative; expression is evaluated to 9
Statement for Linked Answer Questions 84a & 84b:
We are given 9 tasks T1, T2, …. T9. The execution of each task requires one unit of time. We can execute one task at a time. Each task Ti has a profit Piand a deadline di. Profit Pi is earned if the task is completed before the end of the unit of time.
Task
T1
T2
T3
T4
T5
T6
T7
T8
T9
Profit
15
20
30
18
18
10
23
16
25
Deadline
7
2
5
3
4
5
2
7
3
84a.      Are all tasks completed in the schedule that gives maximum profit?
            (a)        All tasks are completed                           (b)        T1 and T6are left out
            (c)        T1and T8 are left out                              (d)        T4and T6 are left out
84b.      What is the maximum profit earned?
            (a)        147                   (b)        165       (c)        167                   (d)        175
Statement for Linked Answer Questions 85a & 85b:
Consider the following floating-point format.


 

Mantissa is a pure fraction in sign-magnitude form.
85a.      The decimal number 0.239 × 213 has the following hexadecimal representation (without normalization and rounding off):
            (a)        0D 24                (b)        0D 4D                (c)        4D 0D                (d)        4D 3D
85b.      The normalized representation for the above format is specified as follows. The mantissa has an implicit 1 preceding the binary (radix) point. Assume that only 0′s are padded in while shifting a field. The normalized representation of the above number (0.239 ´ 213) is:
            (a) 0A 20                       (b)        11 34                (c)        49 DO               (d)        4A E8
End of Question Paper

Dear friends, you can discuss answers through comments. And please give your answers ( with explanation if possible ), you will help others. If you feel that an answer is wrong, please discuss it.


Q: 1 – Q.30 carry one m ark each

 1.         The goal of structured programming is to
             (a)       have well indented programs
             (b)       be able to infer the flow of control from the compiled code
             (c)       be able to infer the flow of control form the program text
             (d)       avoid the use of GOTO statements

2.         Consider the following C function
                        vaid swap (int a, int b)
                        { int temp;
                        temp = a ;
                        a = b ;
                        b= temp ;
                        }
             In order to exchange the values of two variables x and y.
             (a)       call swap (x, y)
             (b)       call swap (&x, &y)
             (c)       swap (x,y) cannot be used as it does not return any value
             (d)       swap (x,y) cannot be used as the parameters are passed by value

3.         A single array A[1..MAXSIZE] is used to implement two stacks. The two stacks grow from opposite ends of the array. Variables top1 and top 2 (top1< top 2) point to the location of the topmost element in each of the stacks. If the space is to be used efficiently, the condition for "stack full" is
            (a)        (top1 = MAXSIZE/2) and (top2 = MAXSIZE/2+1)
            (b)        top1 + top2 = MAXSIZE
            (c)        (top1 = MAXSIZE/2) or (top2 = MAXSIZE)
            (d)        top1 = top2 -1

4.         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                     (c)        4                     (d)        6

5.         The best data structure to check whether an arithmetic expression has balanced parentheses is a
            (a)        queue              (b)        stack                (c)        tree                  (d)        list

6.         Level order traversal of a rooted tree can be done by starting from the root and performing
            (a)        preorder traversal                                  (b)        in-order traversal
            (c)        depth first search                                   (d)        breadth first search

7.         Given the following input (4322, 1334, 1471, 9679, 1989, 6171, 6173, 4199) and the hash function x mod 10, which of the following statements are true?
            i)    9679, 1989, 4199 hash to the same value
            ii)   1471, 6171 has to the same value
            iii)   All elements hash to the same value
            iv)   Each element hashes to a different value
            (a)        i only                (b)        ii only               (c)        i and ii only       (d)        iii or iv

8.         Which of the following grammar rules violate the requirements of an operator grammar? P, Q, R are nonterminals, and r,s,t are terminals.
            (i)         P ® Q R            (ii)        P ® Q s R         (iii)       P ® e                (iv)       P ® Q t R r
            (a)        (i) only  (b)                                           (i)         and (iii) only
            (c)        (ii) and (iii) only                                     (d)        (iii) and (iv) only

9.         Consider a program P that consists of two source modules M1 and M2 contained in two different files. If M1 contains a reference to a function defined in M2 the reference will be resolved at
            (a)        Edit time            (b)        Compile time     (c)        Link time          (d)        Load time

10.        Consider the grammar rule E ® E1 - E2 for arithmetic expressions. The code generated is targeted to a CPU having a single user register. The subtraction operation requires the first operand to be in the register. If E1 and E2 do not have nay-common sub-expression, in order to get the shortest possible code
            (a)        E1should be evaluated first
            (b)        E2should be evaluated first
            (c)        Evaluation of E1 and E2 should necessarily be interleaved
            (d)        Order to evaluation of E1 and E2 is of no consequence

11.        Consider the following statements with respect to user-level threads and kernel-supported threads
            (i)         context switch is faster with kernel-supported threads
            (ii)        for user-level threads, a system call can block the entire process
            (iii)       Kernel supported threads can be scheduled independently
            (iv)       User level threads are transparent to the kernel
            Which of the above statements are true?
            (a)        (ii), (iii) and (iv) only                               (b)        (ii) and (iii) only
            (c)        (i) and (iii) only                                     (d)        (i) and (ii) only

12.        Consider an operating system capable of loading and executing a single sequential user process at a time. The disk head scheduling algorithm used is First Come First Served (FCFS). If FCFS is replaced by Shortest Seek Time First (SSTF), claimed by the vendor to give 50% better benchmark results, what is the expected improvement in the I/O performance of user programs?
            (a)        50%                 (b)        40%                 (c)        25%                 (d)        0%

13.        Let R1 (, B, ((D) and R2 (, E) be two relation schema, where the primary keys are shown underlined, and let C be a foreign key in R1 referring to R2 . Suppose there is no violation of the above referential integrity constraint in the corresponding relation instances r1 and r2 . Which one of the following relational algebra expressions would necessarily produce an empty relation?
            (a)        ÕD (r2) - ÕC (r1)                         (b)        ÕC (r1) - ÕD (r2)
            (c)        ÕD (r1   C ¹D r2)                         (d)        ÕC (r1  C =D r2)

14.        Consider the following relation schema pertaining to a students database:
                        Students (rollno, name, address)
                        Enroll(rollno,courseno, coursename)
            Where the primary keys are shown underlined. The number of tuples in the student and Enroll tables are 120 and 8 respectively. What are the maximum and minimum number of tuples that can be present in (Student * Enroll), where ‘*’ denotes natural join?
            (a)        8, 8                  (b)        120, 8              (c)        960, 8              (d)        960, 120

15.        Choose the best matching between Group 1 and Group 2
            Group -1                                              Group - 2
            P.         Data link layer                            1.         Ensures reliable transport of data over a physical point-to-point link
            Q.         Network layer                            2.         Encodes/decodes data for physical transmission
            R.         Transport layer                          3.         Allows end-to-end communication between two processes
                                                                        4.         Routes data from one network node to the next
             (a)       P - 1, Q - 4, R - 3                      (b)        P - 2, Q - 4, R - 1
             (c)       P - 2, Q - 3, R - 1                      (d)        P - 1, Q - 3, R - 2

16.        Which of the following is NOT true with respect to a transparent bridge and a router?
            (a)        Both bridge and router selectively forward data packets
            (b)        A bridge uses IP addresses while a router uses MAC addresses
            (c)        A bridge builds up its routing table by inspecting incoming packets
            (d)        A router can connect between a LAN and a WAN

17.        A Boolean function x¢y¢ + xy + x¢y is equivalent to
            (a)        x¢ + y¢               (b)        x + y                 (c)        x + y¢                (d)        x¢ + y¢

18.        In an SR latch made by cross-coupling two NAND gates, if both S and R inputs are set to 0, then it will result in
            (a)        Q = 0, Q¢ = 1                                         (b)        Q = 1, Q¢ = 0
            (c)        Q = 1, Q¢ = 1                                         (d)        Indeterminate states
  
19.        If 73x(in base-x number system) is equal to 54y (in base y-number system), the possible values of x and y are
            (a)        8, 16                (b)        10, 12              (c)        9, 13                (d)        8, 11

20.        Which of the following addressing modes are suitable for program relocation at run time?
            (i)         Absolute addressing (ii) Based addressing
            (iii)       Relative addressing (iv) Indirect addressing
            (a)        (i) and (iv)          (b)       (i) and (ii)          (c)        (ii) and (iii)       (d)       (i), (ii) and (iv)

21.        The minimum number of page frames that must be allocated to a running process in a virtual memory environment is determined by
            (a)        the instruction set architecture                 (b)        page size
            (c)        physical memory size                              (d)        number of processes in memory

22.        How many 8-bit characters can be transmitted per second over a 9600 baud serial communication link using asynchronous mode of transmission with one start bit, eight data bits, two stop bits, and one parity bit?
            (a)        600                  (b)        800                  (c)        876                  (d) 1200

23.        Identify the correct translation into logical notation of the following assertion.  Some boys in the class are taller than all the girls
            Note: taller (x, y) is true if x is taller than y.
            (a)        ($x) (boy(x) ® (y) (girl(y) Ù taller (x, y)))
            (b)        ($x) (boy(x) Ù (y) (girl(y) Ù taller (x, y)))
            (c)        ($x) (boy(x) ® (y) (girl(y) ® taller (x, y)))
            (d)        ($x) (boy(x) Ù (y) (girl(y) Ù taller (x, y)))

24.        Consider the binary relation:
            S = {(x, y)|y = x + 1 and x, y Î {0, 1, 2}}
            The reflexive transitive closure of S is
            (a)        {(x, y)|y > x and x, y Î {0, 1, 2}}            (b)        {(x, y)|y ³ x and x, y Î {0, 1, 2}}
            (c)        {(x, y)|y < x and x, y Î {0, 1, 2}}            (b)        {(x, y)|y £ x and x, y Î {0, 1, 2}}

25.        If a fair coin is tossed four times. What is the probability that two heads and two tails will result?
            (a)                           (b)                           (c)                           (d)       

26.        The number of different n × n symmetric matrices with each element being either 0 or 1 is : (Note: power (2,x) is same as 2x)
            (a)        power (2,n)                                           (b)        power(2,n2)
            (c)        power (2, (n2 +n/2)                                (d)        power (2, (n2 - n)/2)

27.        Let A,B,C,D be n × n matrices, each with non-zero determinant. If ABCD=I, then B-1 is
            (a)        D-1 C-1 A-1                                             (b)        CDA
            (c)        ADC                                                      (d)        Does not necessarily exist

28.        What is the result of evaluating the following two expressions using three-digit floating point arithmetic with rounding?
                        (113. + - 111.) + 7.51
                        113. + (- 111.) + 7.51)
            (a)        9.51 and 10.0 respectively                       (b)        10.0 and 9.51 respectively
            (c)        9.51 and 9.51 respectively                       (d)        10.0 and 10.0 respectively

29.        The tightest lower bound on the number of comparisons, in the worst case, for comparison-based sorting is of the order of
            (a)        n                      (b)        n2                     (c)        nlogn                (d)        nlog2n  

30.        The problem 3-SAT and 2-SAT are
            (a)        both in P           
            (b)        both NP complete
            (c)        NP-complete and in P respectively
            (d)        undecidable and NP-complete respectively