1. How many committees of five people can be chosen from 20 men and 12 women such that each committee contains at least three women?
(A) 75240 (B) 52492
(C) 41800 (D) 9900
Answer: B
Explanation:
We must choose at least 3 women, so we calculate the case of 3 women, 4 women and 5 women and by addition rule add the results.
^{12}C_{3} x ^{20}C_{2} + ^{12}C_{4} x ^{20}C_{1} + ^{12}C_{5} x ^{20}C_{0} = (^{12x11x10}/_{3x2x1}) x (^{20x19}/_{2x1})
+ (^{12x11x10x9}/_{4x3x2x1}) x 20
+ (^{12x11x10x9x8}/_{5x4x3x2x1}) x 1
= 220 x 190 + 495 x 20 + 792
= 52492
2. Which of the following statement(s) is/are false?
(a) A connected multigraph has an Euler Circuit if and only if each of its vertices has even degree.
(b) A connected multigraph has an Euler Path but not an Euler Circuit if and only if it has exactly two vertices of odd degree.
(c) A complete graph (K_{n}) has a Hamilton Circuit whenever n≥3
(d) A cycle over six vertices (C_{6}) is not a bipartite graph but a complete graph over 3 vertices is bipartite.
Codes:
(A) (a) only (B) (b) and (c)
(C) (c) only (D) (d) only
Answer: D
Explanation:
EulerCircuits
HamiltonCircuit
From the above definitions, we can see that (d) is false. So answer is (D).
3. Which of the following is/are not true?
(a) The set of negative integers is countable.
(b) The set of integers that are multiples of 7 is countable.
(c) The set of even integers is countable.
(d) The set of real numbers between 0 and ^{1}/_{2} is countable.
(A) (a) and (c) (B) (b) and (d)
(C) (b) only (D) (d) only
Answer: D
4. Consider the graph given below:
The two distinct sets of vertices, which make the graph bipartite are:
(A) (v_{1}, v_{4}, v_{6}); (v_{2}, v_{3}, v_{5}, v_{7}, v_{8}) (B) (v_{1}, v_{7}, v_{8}); (v_{2}, v_{3}, v_{5}, v_{6})
(C) (v_{1}, v_{4}, v_{6}, v_{7}); (v_{2}, v_{3}, v_{5}, v_{8}) (D) (v_{1}, v_{4}, v_{6}, v_{7}, v_{8}); (v_{2}, v_{3}, v_{5})
Answer: C
Explanation:
A simple graph G=(V,E) is called bipartite if its vertex set can be partitioned into two disjoint subsets V=V_{1}⋃V_{2}, such that every edge has the form e=(a,b) where aϵV_{1} and bϵV_{2}.
Bipartite graphs are equivalent to twocolorable graphs.
1. Assign Red color to the source vertex (putting into set V_{1}).
2. Color all the neighbours with Black color (putting into set V_{2}).
3. Color all neighbour’s neighbour with Red color (putting into set V_{1}).
4. This way, assign color to all vertices such that it satisfies all the constraints of m way coloring problem where m = 2.
5. While assigning colors, if we find a neighbour which is colored with same color as current vertex, then the graph cannot be colored with 2 colors (ie., graph is not Bipartite).
So answer is option (C).
5. A tree with n vertices is called graceful, if its vertices can be labelled with integers 1, 2, ...,n such that the absolute value of the difference of the labels of adjacent vertices are all different. Which of the following trees are graceful?
Codes:
(A) (a) and (b) (B) (b) and (c)
(C) (a) and (c) (D) (a), (b) and (c)
Answer: D
Explanation:
Caterpillar tree: In graph theory, a caterpillar is a tree in which all the vertices are within distance 1 of a central path.
Theorem: All caterpillars are graceful.
So, (a), (b) and (c) are graceful.
6. Which of the following arguments are not valid?
(a) “If Gora gets the job and works hard, then he will be promoted. If Gora gets promotion, then he will be happy. He will not be happy, therefore, either he will not get the job or he will not work hard”.
(b) “Either Puneet is not guilty or Pankaj is telling the truth. Pankaj is not telling the truth, therefore, Puneet is not guilty”.
(c) If n is a real number such that n>1, then n^{2}>1. Suppose that n^{2}>1, then n>1.
Codes:
(A) (a) and (c) (B) (b) and (c)
(C) (a), (b) and (c) (D) (a) and (b)
Answer: A
Explanation:
(a) P: Gora gets the job
Q: Gora works hard
R: Gora gets promotion
S: Gora will be happy
The argument can bet written as
(P˄Q)→R
R→S
¬S
Therefore ¬P˅¬Q
(b) Let P: Puneet is not guilty
Q: Pankaj is telling the truth
The argument can bet written as
P˅Q
~Q
Therefore, P
Thus by disjunctive syllogism, the argument is valid.
Disjunctive Syllogism:
The disjunctive syllogism rule may be written as:
P˅Q, ¬P ⊢Q
It may also be written as:
((P˅Q)˄¬P)→Q
where P, and Q are propositions expressed in some formal system.
7. Let P(m,n) be the statement “m divides n” where the Universe of discourse for both the variables is the set of positive integers. Determine the truth values of the following propositions.
(a) ∃m ∀n P(m,n) (b) ∀n P(1,n) (c) ∀m ∀n P(m,n)
(A) (a)True; (b)True; (c)False (B) (a)True; (b)False; (c)False
(C) (a)False; (b)False; (c)False (D) (a)True; (b)True; (c)True
Answer: A
8. Match the following terms:
List  I List  II
(a) Vacuous proof (i) A proof that the implication p→q is true
based on the fact that p is false
(b) Trivial proof (ii) A proof that the implication p→q is true
based on the fact that q is true
(c) Direct proof (iii) A proof that the implication p→q is true
that proceeds by showing that q must be true when p is true.
(d) Indirect proof (iv) A proof that the implication p→q is true
that proceeds by showing that p must be false when q is false.
Codes:
(a) (b) (c) (d)
(A) (i) (ii) (iii) (iv)
(B) (ii) (iii) (i) (iv)
(C) (iii) (ii) (iv) (i)
(D) (iv) (iii) (ii) (i)
Answer: A
9. Consider the compound propositions given below as:
(a) p˅~(p˄q) (b) (p˄~q)˅~(p˄q) (c) p˄(q˅r)
Which of the above propositions are tautologies?
(A) (a) and (c) (B) (b) and (c)
(C) (a) and (b) (D) (a), (b) and (c)
Answer: Marks to all
Only (a)
10. Which of the following property/ies a Group G must hold, in order to be an Abelian group?
(a) The distributive property
(b) The commutative property
(c) The symmetric property
Codes:
(A) (a) and (b) (B) (b) and (c)
(C) (a) only (D) (b) only
Answer: D
11. Consider the following program:
#include
main()
{
int i, inp;
float x, term=1, sum=0;
scanf(“%d %f”,&inp, &x);
for(i=1;i<=inp;i++)
{
term=term*x/i;
sum=sum+term;
}
printf(“Result=%f\n”,sum);
}
The program computes the sum of which of the following series?
(A) x+x^{2}/2+x^{3}/3+x^{4}/4+... (B) x+x^{2}/2!+x^{3}/3!+x^{4}/4!+...
(C) 1+x^{2}/2+x^{3}/3+x^{4}/4+... (D) 1+x^{2}/2!+x^{3}/3!+x^{4}/4!+...
Answer: B
12. Consider the following two statements:
(a) A publicly derived class is a subtype of its base class.
(b) Inheritance provides for code reuse.
Which of the following statements is correct?
(A) Both the statements (a) and (b) are correct
(B) Neither of the statements (a) and (b) are correct
(C) Statement (a) is correct and (b) is incorrect
(D) Statement (a) is incorrect and (b) is correct
Answer: A
13. Consider a “CUSTOMERS” database table having a column “CITY” filled with all the names of Indian cities (in capital letters). The SQL statement that finds all cities that have “GAR” somewhere in its name, is:
(A) Select *from customers where city=’%GAR%’;
(B) Select *from customers where city=’$GAR$’;
(C) Select *from customers where city like ‘%GAR%’;
(D) Select *from customers where city as ’%GAR’;
Answer: C
14. Match the following database terms to their functions:
ListI ListII
(a) Normalization (i) Enforces match of primary key to foreign key
(b) Data Dictionary (ii) Reduces data redundancy in a database
(c) Referential Integrity (iii) Define view(s) of the database for particular user(s).
(d) External Schema (iv) Contains metadata describing database structure.
Codes:
(a) (b) (c) (d)
(A) (iv) (iii) (i) (ii)
(B) (ii) (iv) (i) (iii)
(C) (ii) (iv) (iii) (i)
(D) (iv) (iii) (ii) (i)
Answer: B
15. In general, in a recursive and nonrecursive implementation of a problem (program):
(A) Both time and space complexities are better in recursive than in nonrecursive program
(B) Both time and space complexities are better in nonrecursive than in recursive program
(C) Time complexity is better in recursive version but space complexity is better in nonrecursive version of the program
(D) Space complexity is better in recursive version but time complexity is better in nonrecursive version of the program
Answer: C
16. A three dimensional array in ‘C’ is declared as int A[x][y][z]. Here, the address of an item at the location A[p][q][r] can be computed as follows (where w is the word length of an integer):
(A) &A[0][0][0]+w(y*z*q+z*p+r)
(B) &A[0][0][0]+w(y*z*p+z*q+r)
(C) &A[0][0][0]+w(x*y*p+z*q+r)
(D) &A[0][0][0]+w(x*y*q+z*p+r)
Answer: B
17. In C++, which systemprovided function is called when no handler is provided to deal with an exception?
(A) terminate() (B) unexpected()
(C) abort() (D) kill()
Answer: A
18. Which of the following provides the best description of an entity type?
(A) A specific concrete object with a defined set of processes (e.g. Jatin with diabetes)
(B) A value given to a particular attribute (e.g. height230 cm)
(C) A thing that we wish to collect data about zero or more, possibly real world examples of it may exist.
(D) A template for a group of things with the same set of characteristics that may exist in the real world
Answer: D
19. Data which improves the performance and accessibility of the database are called:
(A) Indexes (B) User Data
(C) Application Metadata (D) Data Dictionary
Answer: A
20. A relation R={A,B,C,D,E,F,G} is given with following set of functional dependencies:
F={AD→E, BE→F, B→C, AF→G}
Which of the following is a candidate key?
(A) A (B) AB
(C) ABC (D) ABD
Answer: D
21. Which of the following services is not provided by wireless access point in 802.11 WLAN?
(A) Association (B) Disassociation
(C) Error Correction (D) Integration
Answer: C
22. Which of the following fields in IPv4 datagram is not related to fragmentation?
(A) Type of service (B) Fragment offset
(C) Flags (D) Identification
Answer: A
23. Four channels are multiplexed using TDM. If each channel sends 100 bytes/second and we multiplex 1 byte per channel, then the bit rate for the link is ...............
(A) 400 bps (B) 800 bps
(C) 1600 bps (D) 3200 bps
Answer: D
Explanation:
The multiplexer is shown in the Figure.
Each frame carries 1 byte from each channel; the size of each frame, therefore, is 4 bytes, or 32 bits. Because each channel is sending 100 bytes/s and a frame carries 1 byte from each channel, the frame rate must be 100 frames per second. The bit rate is 100 × 32 = 3200 bps.
24. In a typical mobile phone system with hexagonal cells, it is forbidden to reuse a frequency band in adjacent cells. If 840 frequencies are available, how many can be used in a given cell?
(A) 280 (B) 210
(C) 140 (D) 120
Answer: A
Explanation:
Each cell has six other adjacent cells, in a hexagonal grid. If the central cell uses frequency group A, its six adjacent cells can use B, C, B, C, B, and C respectively. In other words, only 3 unique cells are needed. So the answer is 840/3 = 280 frequencies.
25. Using p=3, q=13, d=7 and e=3 in the RSA algorithm, what is the value of ciphertext for a plain text 5?
(A) 13 (B) 21
(C) 26 (D) 33
Answer: Marks to all
Explanation:
p=3, q=13, d=7, e=3, M=5, C=?
C = M^{e }mod n
n = p*q
= 3*13 = 39
C = 5^{3} mod 39
= 8
Answer is 8.
26. A virtual memory has a page size of 1K words. There are eight pages and four blocks. The associative memory page table contains the following entries:
Which of the following list of virtual addresses (in decimal) will not cause any page fault if referenced by the CPU?
(A) 1024, 3072, 4096, 6144 (B) 1234, 4012, 5000, 6200
(C) 1020, 3012, 6120, 8100 (D) 2021, 4050, 5112, 7100
Answer: C
Explanation:
The pages which are not in main memory are:
Page

Address

Address that will cause page fault

1

1K

10242047

3

3K

30724095

4

4K

40965119

6

6K

61447167

1020 will not cause page fault (10242047)
3012 will not cause page fault (30724095)
6120 will not cause page fault (40965119)
8100 will not cause page fault (61447167)
27. Suppose that the number of instructions executed between page faults is directly proportional to the number of page frames allocated to a program. If the available memory is doubled, the mean interval between page faults is also doubled. Further, consider that a normal instruction takes one micro second, but if a page fault occurs, it takes 2001 micro seconds. If a program takes 60 sec to run, during which time it gets 15000 page faults, how long would it take to run if twice as much memory were available?
(A) 60 sec (B) 30 sec
(C) 45 sec (D) 10 sec
Answer: C
Explanation:
T = N_{instr} x 1µs + 15,000 x 2,000 µs = 60s
N_{instr} x 1µs = 60,000,000 µs – 15,000,000 µs = 30,000,000 µs
N_{instr} = 30,000,000
The number of instruction between two page faults is
N_{instr }/N_{PageFaults} = 30,000,000/15,000 = 2,000
If the mean interval between page faults is doubled, the number of instruction between two page faults is also doubled and is 4,000. Now the number of page faults is
30,000,000/4,000 = 7,500
T’ = 30,000,000 µs + 7,500 x 2,000 µs
= 30,000,000 µs + 15,000,000 µs = 45,000,000 µs = 45s
Doubling the memory, doesn’t mean that the program runs twice as fast as on the first system. Here, the performance increase is of 25%.
28. Consider a disk with 16384 bytes per track having a rotation time of 16 msec and average seek time of 40 msec. What is the time in msec to read a block of 1024 bytes from this disk?
(A) 57 msec (B) 49 msec
(C) 48 msec (D) 17 msec
Answer: B
Explanation:
Time in msec to read a block of 1024 bytes (Access time or Disk Latency) = seek time + average rotational delay + transfer time
If there are 16384 bytes per track there are 1024/16384 tracks to be read for this block.
Seek time = 40 msec
Rotational delay = 16 msec
Transfer time = (sectors_read/sectors per rev.) x rotational delay
= (1024/16384) x 16 = 1
average rotational delay = rotational delay/2 = 16/2 = 8
access time = 40 + 8 + 1 = 49
29. A system has four processes and five allocatable resources. The current allocation and maximum needs are as follows:
Allocated

Maximum

Available
 
Process A

1 0 2 1 1

1 1 2 1 3

0 0 x 1 1

Process B

2 0 1 1 0

2 2 2 1 0
 
Process C

1 1 0 1 0

2 1 3 1 0
 
Process D

1 1 1 1 0

1 1 2 2 1

The smallest value of x for which the above system in safe state is .............
(A) 1 (B) 3
(C) 2 (D) 0
Answer: Marks to all
Explanation:
If Process A’s Maximum need is 1 1 2 1 2 instead of 1 1 2 1 3, then answer will be x=1
The needs matrix is as follows:
0 1 0 0 1
0 2 1 0 0
1 0 3 0 0
0 0 1 1 1
If x is 0, available vector will be 0 0 0 1 1, we have a deadlock immediately.
If x is 1, available vector will be 0 0 1 1 1, now, process D can run to completion. When it is finished, the available vector is 1 1 2 2 1.
Now A can run to complete, the available vector then becomes 2 1 4 3 2.
Then C can run and finish, return the available vector as 3 2 4 4 2.
Then B can run to complete. Safe sequence D A C B.
30. In Unix, the login prompt can be changed by changing the contents of the file ...............
(A) contrab (B) init
(C) gettydefs (D) inittab
Answer: C
31. A data cube C, has n dimensions, and each dimension has exactly p distinct values in the base cuboid. Assume that there are no concept hierarchies associated with the dimensions. What is the maximum number of cells possible in the data cube, C?
(A) p^{n} (B) p
(C) (2^{n}1)p+1 (D) (p+1)^{n}
Answer: D
Explanation:
(a) What is the maximum number of cells possible in the base cuboid?
p^{n}.
This is the maximum number of distinct tuples that you can form with p distinct values per dimensions.
(b) What is the minimum number of cells possible in the base cuboid?
p.
You need at least p tuples to contain p distinct values per dimension. In this case no tuple shares any value on any dimension.
(c) What is the minimum number of cells possible in the data cube, C?
(2^{n}1)×p+1.
The minimum number of cells is when each cuboid contains only p cells, except for the apex, which contains a single cell.
(d) What is the maximum number of cells possible (including both base cells and aggregate cells) in the data cube, C?
(p+1)^{n}.
The argument is similar to that of part (a), but now we have p+1 because in addition to the p distinct values of each dimension we can also choose ∗.
32. Suppose that from given statistics, it is known that meningitis causes stiff neck 50% of the time, that the proportion of persons having meningitis is 1/50000, and that the proportion of people having stiff neck is 1/20. Then the percentage of people who had meningitis and complain about stiff neck is:
(A) 0.01% (B) 0.02%
(C) 0.04% (D) 0.05%
Answer: B
Explanation:
The computation is based on the simplified Bayes’ formula.
P{BA} = (P{AB}·P{B) / P{A}.
P{MS} = probability that a person had meningitis, conditioned by the existence of stiff neck.
P{SM} = probability that a person complains about stiff neck, conditioned by the existence of meningitis. = 50%=1/2
P{S} = proportion of people who complain about stiff neck. = 1/20
P{M} = proportion of people who had meningitis. = 1/50,000
Then:
P{MS} = (P{SM}·P{M}) / P{S} =(^{1}/_{2} x ^{1}/_{50,000}) / ^{1}/_{20 }= 0.0002 = 0.02%
33. ................. system is market oriented and is used for data analysis by knowledge workers including Managers, Executives and Analysts.
(A) OLTP (B) OLAP
(C) Data System (D) Market System
Answer: B
34. .................. allows selection of the relevant information necessary for the data warehouse.
(A) The TopDown View (B) Data Warehouse View
(C) Data source View (D) Business Query View
Answer: A
35. The hash function used in double hashing is of the form:
(A) h(k, i)=(h_{1}(k)+h_{2}(k)+i)mod m (B) h(k, i)=(h_{1}(k)+h_{2}(k)i)mod m
(C) h(k, i)=(h_{1}(k)+ih_{2}(k))mod m (D) h(k, i)=(h_{1}(k)ih_{2}(k))mod m
Answer: C
36. In the following graph, discovery time stamps and finishing time stamps of Depth First Search (DFS) are shown as x/y where x is discovery time stamp and y is finishing time stamp.
It shows which of the following depth first forest?
(A) {a,b,e} {c,d,f,g,h} (B) {a,b,e} {c,d,h} {f,g}
(C) {a,b,e} {f,g} {c,d} {h} (D) {a,b,c,d} {e,f,g} {h}
Answer: C
37. The number of disk pages access in Btree search, where h is height, n is the number of keys, and t is the minimum degree, is:
(A) θ(log_{n} h*t) (B) θ(log_{t} n*h)
(C) θ(log_{h} n) (D) θ(log_{t} n)
Answer: D
38. The inorder traversal of the following tree is:
(A) 2 3 4 6 7 13 15 17 18 18 20
(B) 20 18 18 17 15 13 7 6 4 3 2
(C) 15 13 20 4 7 17 18 2 3 6 18
(D) 2 4 3 13 7 6 15 17 20 18 18
Answer: D
39. An ideal sort is an inplacesort whose additional space requirement is ...............
(A) O(log_{2}n) (B) O(nlog_{2}n)
(C) O(1) (D) O(n)
Answer: C
40. Which of the following is not a congestion policy at network layer?
(A) Flow Control Policy
(B) Packet Discard Policy
(C) Packet Lifetime Management Policy
(D) Routing Algorithm
Answer: A
41. Loop unrolling is a code optimization technique:
(A) that avoids tests at every iteration of the loop
(B) that improves performance by decreasing the number of instructions in a basic block.
(C) that exchanges inner loops with outer loops
(D) that reorders operations to allow multiple computations to happen in parallel.
Answer: A
42. What will be the hexadecimal value in the register ax (32bit) after executing the following instructions?
Mov al, 15
Mov ah, 15
Xor al, al
Mov cl, 3
Shr ax, cl
Codes:
(A) 0F00 h (B) 0F0F h
(C) 01E0 h (D) FFFF h
Answer: C
43. Which of the following statements is false?
(A) Topdown parsers are LL parsers where first L stands for lefttoright scan and second L stands for a leftmost derivation.
(B) (000)* is a regular expression that matches only strings containing an odd number of zeroes, including the empty string.
(C) Bottomup parsers are in the LR family, where L stands for lefttoright scan and R stands for rightmost derivation
(D) The class of contextfree languages is closed under reversal. That is, if L is any contextfree language, then the language L^{R}={W^{R}:wϵL} is context free.
Answer: B
44. System calls are usually invoked by using:
(A) A privileged instruction (B) An indirect jump
(C) A software interrupt (D) Polling
Answer: C
45. The ............... transfers the executable image of a C++ program from hard disk to main memory.
(A) Compiler (B) Linker
(C) Debugger (D) Loader
Answer: D
46. In software testing, how the error, fault and failure are related to each other?
(A) Error leads to failure but fault is not related to error and failure
(B) Fault leads to failure but error is not related to fault and failure
(C) Error leads to fault and fault leads to failure
(D) Fault leads to error and error leads to failure
Answer: C
47. Which of the following is not a software process model?
(A) Prototyping (B) Iterative
(C) Timeboxing (D) Glassboxing
Answer: D
48. How many solutions are there for the equation x+y+z+u=29 subject to the constraints that x≥1, y≥2, z≥3 and u≥0?
(A) 4960 (B) 2600
(C) 23751 (D) 8855
Answer: B
49. A unix file system has 1KB blocks and 4byte disk addresses. What is the maximum file size if inodes contain 10 direct entries and one single, double and triple indirect entry each?
(A) 32 GB (B) 64 GB
(C) 16 GB (D) 1 GB
Answer: C
Explanation:
block = 2^{10}
block pointer size = 4B
entries possible in block = 2^{10}/2^{2} = 256
direct pointer gives = 10 * 256 = 10 blocks
single indirect gives = 256 * 256 = 2^{8} blocks
double indirect gives = 256 * 256 * 256 = 2^{16} blocks
triple indirect gives = 256 * 256 * 256 * 256 = 2^{24} blocks
total = 10 blocks + 2^{8} blocks + 2^{16} blocks + 2^{24} blocks
= 16843018 blocks = 16843018 * 1024 = 17247250432 ≈ 16 GB
50. ................. uses electronic means to transfer funds directly from one account to another rather than by cheque or cash?
(A) MBanking (B) EBanking
(C) OBanking (D) CBanking
Answer: B
Like the Post? Share with your Friends: