TNPSC2012PolytechnicCS
Question 1 
Which of the following computers is least powerful?
Mini  
Micro
 
Mainframe  
Super 
Question 1 Explanation:
Micro computer is the least powerful computer and super computer is the most powerful computer.
Question 2 
The technique which repeatedly uses the same block of internal storage during different stages of problem is called
Overlay  
Overlapping  
Swapping  
Reuse 
Question 2 Explanation:
In a general computing sense, overlaying means "the process of transferring a block of program code or other data into main memory, replacing what is already stored". Overlaying is a programming method that allows programs to be larger than the computer's main memory.
Question 3 
The number of instructions needed to add n numbers and store the result in memory using only one address instruction is
n  
n+1  
n1  
independent of n

Question 3 Explanation:
At first instruction we will load the first no. in accumulator and then from second instruction we will add remaining n1 no. using accumulator. Till now n instruction is used. And finally we will use one more instruction to store the result back to memory. So in total n+1 instruction is required.
Question 4 
The most relevant addressing mode to write position independent code is
Direct mode  
Indirect mode
 
Relative mode  
Indexed mode 
Question 4 Explanation:
Relative mode is the most relevant addressing mode to write position independent code.
Indexed mode is for arrays and structure.
Indirect mode is used for pointers.
Indexed mode is for arrays and structure.
Indirect mode is used for pointers.
Question 5 
The CPU of a computer takes instruction from the memory and executes them. This process is called
Load cycle  
Time sequences  
Fetchexecute cycle  
Clock cycle 
Question 5 Explanation:
The process in which a CPU of a computer takes instruction from memory and executes them is called fetchexecute cycle.
Question 6 
A five figure number is formed by the digits 0, 1, 2, 3, 4 without repetition. Then probability that the number formed is divisible by 4 in
3/15  
5/16  
7/16  
9/16 
Question 7 
If A and B be sets with cardinalities m and n respectively, then number of oneone mappings (injections) from A to B, when m < n, is
m^{n}  
^{n}P_{m}  
^{n}C_{m}  
None of these 
Question 7 Explanation:
The formula for above given question is ^{n}P_{m}.
Question 8 
The set of all n^{th} roots of unity under multiplication of complex numbers form a/an
Semigroup with identity  
Communicative semi groups with identity  
Group  
Abelian group 
Question 8 Explanation:
More generally, if C is a group and z∈C with z^{n} = 1, where 1 is the identity of C, then G = {1,z,z^{2},...,z^{n1}} is a group (actually, a subgroup of C).
Indeed:
• Closure: z^{j}z^{k} = z^{j+k} = z^{r} ∈ G, where r = (j+k) mod n.
• Associativity: comes from C.
• Identity: 1 ∈ G by definition, and 1 is the identity of C.
• Inverse: z^{j}z^{nj} = 1.
• Commutativity: z^{j}z^{k} = z^{j+k} = z^{k+j} = z^{k}z^{j}.
Indeed:
• Closure: z^{j}z^{k} = z^{j+k} = z^{r} ∈ G, where r = (j+k) mod n.
• Associativity: comes from C.
• Identity: 1 ∈ G by definition, and 1 is the identity of C.
• Inverse: z^{j}z^{nj} = 1.
• Commutativity: z^{j}z^{k} = z^{j+k} = z^{k+j} = z^{k}z^{j}.
Question 9 
How many 10 digit numbers can be written by using the digits 1 and 2?
10 C_{1} + 9 C_{2}  
2^{10}  
10 C_{2}  
10 1 
Question 9 Explanation:
For each digit we have two choices ‘1 or 2’. So no. of possible 10 digits nos.
2*2*2*2*2*2*2*2*2*2 = 2^{10}
2*2*2*2*2*2*2*2*2*2 = 2^{10}
Question 10 
T is a graph with n vertices. T is connected and has exactly n – 1 edges. Then
T is a tree  
T contains no cycles
 
Every pair of vertices in T is connected by exactly one path  
Addition of a new edge will create a cycle 
Question 10 Explanation:
Any graph with n vertices and n1 edges which is connected will definitely be a tree.
Question 11 
Eigenvectors of a real symmetric matrix corresponding to different eigenvalues are
Orthogonal  
Singular  
Nonsingular  
None of these 
Question 11 Explanation:
Eigenvectors of a real symmetric matrix corresponding to different eigenvalues are orthogonal to each other.
Question 12 
If L_{1} and L_{2} are context free language and R is a regular set. Which one of the languages below is not necessarily a context free language?
L_{1}L_{2}  
L_{1}∩L_{2}  
L_{1}∪R  
L_{1}∪L_{2} 
Question 12 Explanation:
Context free language is not closed under intersection. Hence B is the correct option.
Question 13 
CSG can be recognized by
pushdown automata  
2 way linear bounded automaton  
finite state automata  
none of these 
Question 13 Explanation:
Context sensitive grammar can be recognized by linear bounded automata.
Question 14 
Consider the following grammar:
S → Ax By A → ByCw B → xBw C → yWhich of the regular expressions describes the same set of strings as the grammar?
xw+y+xw*yx+ywx  
xwy+xw*xy*ywx
 
xw*y+xw*yx+ywx  
xwxy+xww*yywx 
Question 14 Explanation:
Option A do not contain xy which is generated by the grammar.
Option B do not contain xy which is generated by the grammar.
Option C do not contain xy which is generated by the grammar.
Option B do not contain xy which is generated by the grammar.
Option C do not contain xy which is generated by the grammar.
Question 15 
Recursively enumerable languages are not closed under
Union  
Intersection  
Complementation  
Concatenation 
Question 15 Explanation:
Recursively enumerable language are not closed under complementation.
Question 16 
Turing machine is more powerful than FMs because
Tape movement is confined to one direction  
It has no finite state  
It has the capability to remember arbitrarily long sequences of input symbols  
None of these

Question 16 Explanation:
Turing machines is more powerful than finite machines because it has the capability to remember arbitrarily long sequences of input symbols.
Question 17 
Which of the following statements is wrong?
The language accepted by finite automata is the languages denoted by regular expressions.
 
For every DFA there is a regular expression denoting its language
 
For a regular expression r, there does not exist any NFA with transit that accepts L(r)  
None of these 
Question 17 Explanation:
NFA, DFA and regular expression are equal in power. So for every regular expression there exists DFA and NFA.
Question 18 
Can a DFA simulate NFA?
No  
Yes
 
Sometimes  
Depends of NFA

Question 18 Explanation:
DFA has equal power as NFA.
Question 19 
Let a and b be the regular expressions, then (a*∪b*)* is not equivalent to
(a∪b)*  
(b*∪a*)*  
(b∪a)*  
(a∪b) 
Question 19 Explanation:
The given regular expression is not equal to option D.
Question 20 
FDDI is a
Ring network  
Star network  
Mesh network  
Bus based network 
Question 20 Explanation:
Fiber Distributed Data Interface (FDDI) uses fiberoptic cable and is wired in a ring topology and Fiber Distributed Data Interface (FDDI) uses token passing as its mediaaccess method and can operate at high speeds.
Question 21 
Which one of the following is not a class of LAN?
Broadband  
CSMA/CD  
Token bus  
Token ring 
Question 21 Explanation:
Broadband is not a class of LAN.
Question 22 
Which of the following TCP/IP protocols is used for file transfer with minimal capability and minimal overhead?
RARP  
FTP  
TFTP  
TELNET

Question 22 Explanation:
Among the given options FTP and TFTP is used to transfer files. Trivial File Transfer Protocol (TFTP) is an Internet software utility for transferring files that is simpler to use than the File Transfer Protocol (FTP) but less capable. It is used where user authentication and directory visibility are not required.
Question 23 
ALOHA is used for
Channel allocation problem  
Data transfer
 
Buffering  
All of these 
Question 23 Explanation:
Aloha is used to get access of the link because it is a access control method or we can also say that it is a channel allocation problem.
Question 24 
Error detection at the data link level is achieved by
Bit stuffing  
Cyclic redundancy codes  
Hamming  
Equalization

Question 24 Explanation:
Error detection at the data link layer is achieved by CRC method.
Question 25 
Which topology requires a central controller or hub?
Mesh  
Star  
Bus  
Ring 
Question 25 Explanation:
A star topology is a topology for a Local Area Network (LAN) in which all nodes are individually connected to a central connection point, like a hub or a switch. A star takes more cable than e.g. a bus, but the benefit is that if a cable fails, only one node will be brought down.
Question 26 
Ethernet LAN uses
Polar encoding  
Differential Manchester encoding  
Manchester encoding  
NRZ 
Question 26 Explanation:
Ethernet LAN uses manchester encoding.
Question 27 
The parity of the binary number 100110011 is
Even  
Odd  
4  
5 
Question 27 Explanation:
The parity of a binary no. is said to be odd if it contains odd no. of 1’s and the parity of a binary no. is said to be even if it contains even no. of 1’s.
Since the given binary no. contains odd no. of 1’s so the parity is odd.
Since the given binary no. contains odd no. of 1’s so the parity is odd.
Question 28 
A switching function can also be written as
Σ(1, 3, 5, 7, 9)  
Σ(3, 5, 7, 9, 11)  
Σ(3, 5, 9, 11, 13)  
Σ(5, 7, 9,11,13) 
Question 28 Explanation:
Question 29 
The clock signals are used in sequential logic circuits to
Tell the time of the day  
Tell how much time has elapsed since the system was turned on
 
Carry serial data signals  
Synchronize events in various parts of system 
Question 29 Explanation:
The clock signals are used in sequential logic circuit for synchronization.
Question 30 
For a memory system, the cycle time is
Same as the access time  
Longer than the access time  
Shorter than the access time  
Submultiple of the access time 
Question 30 Explanation:
For a memory system, the cycle time is Longer than the access time. Cycle time is the time, usually measured in nanosecond s, between the start of one random access memory ( RAM ) access to the time when the next access can be started. Access time is sometimes used as a synonym.
Question 31 
For which of the following flipflops, the output is clearly defined for all combinations of two inputs?
Qtype flipflop  
RS flipflop  
JK flipflop  
T flipflop 
Question 31 Explanation:
or RS flip flop the output is not defined for input R=1,S=1. But for JK flip flop output is defined for all combinations of two inputs.
Note that T flipflop is 1 input flip flop and not two input flip flop.
Note that T flipflop is 1 input flip flop and not two input flip flop.
Question 32 
Functional dependencies are a generalization of
Key dependencies  
Relation dependencies
 
Database dependencies  
None of these 
Question 32 Explanation:
A functional dependency is a generalization of the notion of a key. It requires the value for a certain set of attributes determines uniquely the value for another set of attributes.
Question 33 
ER modeling technique is a
topdown approach  
bottomup approach  
leftright approach  
none of these 
Question 33 Explanation:
1. ER Modeling (Top down Approach)
2. Normalization (Bottom Up approach)
2. Normalization (Bottom Up approach)
Question 34 
Let R = (A, B, C, D, E, F) be a relation schema with the following dependencies:
C → F,E → A, EC → D, A → BWhich of the following is a key for R?
CD  
EC  
AE  
AC 
Question 34 Explanation:
Let's find closure of each options,
(CD)^{+} = CDF X
(EC)^{+} = ECFDAB ✓
(AE)^{+} = AEB X
(AC)^{+} = ACBF X
(CD)^{+} = CDF X
(EC)^{+} = ECFDAB ✓
(AE)^{+} = AEB X
(AC)^{+} = ACBF X
Question 35 
Any binary relation is in
1 NF  
2 NF  
3 NF  
BCNF 
Question 35 Explanation:
Every binary relation(relation with two attributes ) is always in BCNF.
Let there be relation R(C,D).
Possible functional dependencies are,
C>D (Candidate key C)
or
D>C (Candidate key is D)
or
CD>CD (Candidate key is CD)
No violation is there in any of the above three cases for BCNF.
Let there be relation R(C,D).
Possible functional dependencies are,
C>D (Candidate key C)
or
D>C (Candidate key is D)
or
CD>CD (Candidate key is CD)
No violation is there in any of the above three cases for BCNF.
Question 36 
The database environment has all of the following components except
Users  
Separate files
 
Database  
Database administration 
Question 36 Explanation:
The database environment has all of the following components except separate files.
Question 37 
Which of the following is not a characteristic of a relational database model?
Tables  
Treelike structure  
Complex logical relationships  
Records 
Question 37 Explanation:
Relational database model do not have tree like structure.
Question 38 
Given two union compatible R_{1}(A,B) and R_{2}(C, D). What is the result of the operations R_{1} A = C AB = DR_{2}?
R_{1}∪R_{2}  
R_{1}×R_{2}  
R_{1}R_{2}  
R_{1}∩R_{2} 
Question 38 Explanation:
The operations will give the result whose values of both the attributes of R_{1} and R_{2} are equal.Which means the operation is nothing but R_{1}∩R_{2}.
Question 39 
What is the output of the following C program?
{ int a5 = {2,3}; Printf (“/n%d%d%d”, a[2], a[3], a[4]) ; }
Garbage values  
2 3 3
 
3 2 2  
0 0 0 
Question 39 Explanation:
First two elements of array will get the value 2 and 3 and the remaining 3 elements of the array will get the value 0 by default.
Question 40 
In C language, x  = y + 1; means
x=xy+1  
x=xy1  
x=x+y+1  
x=xy1 
Question 40 Explanation:
In general, a=b means a=ab. So from this we can conclude that correct option is A.
Question 41 
If x is an array of integer, then the value of &x [t] is same as
&x[t1] + size of (int)  
x + size of (int)*t  
x+t  
x=5 
Question 42 
How many values can be held by an array A (1 … m, 1, … m)?
m  
m^{2}  
m(m+1)  
m(m+2) 
Question 42 Explanation:
Index of rows is from 1 to m, so no. of rows is m+2. And index of column is from 1 to m,so no. of rows is m.
Hence no. of values that can be held in array A is m*(m+2).
Hence no. of values that can be held in array A is m*(m+2).
Question 43 
What is true for the complete bipartite graphs k (3, 3) and k (2, 4) ?
Both are planar  
Neither is planar  
Both are isomorphic  
None of these

Question 43 Explanation:
The graph k(1,n) is planar for all n.
The graph k(2,n) is planar for all n.
Every other case deals with k(n,m) where n,m>=3, but then this graph must have k(3,3) as a subgraph and it is nonplanar by kuratowski’s theorem.
Hence K(3,3) is not planar where as k(2,4) is planar.
The graph k(2,n) is planar for all n.
Every other case deals with k(n,m) where n,m>=3, but then this graph must have k(3,3) as a subgraph and it is nonplanar by kuratowski’s theorem.
Hence K(3,3) is not planar where as k(2,4) is planar.
Question 44 
Linked lists are not suitable for
Insertion  
Binary search  
Radix sort  
Polynomial manipulation 
Question 44 Explanation:
Linked lists are not suitable for binary search because we cant directly jump to the required node while searching.
Question 45 
The postfix expression for the infix expression A+B+(C+D)/F+D+E is
AB+CD+ *F/D+E*  
ABCD+ *F/+ DE* +  
A*B+CD/F+DE++  
None of these

Question 45 Explanation:
The given infix expression is,
(A + B + (C + D))/ (F + D + F)
⇒ Push ‘(’
⇒ Read A
⇒ Push ‘+’
⇒ Read B
⇒ Since ‘+’ is Left associative, so ‘+’ in stack will have higher procedure then the current ‘+’, hence pop it,
⇒ Push ‘+’
⇒ Push ‘(’
⇒ Read C
⇒ Push ‘+’
⇒ Read D,
⇒ Now on looking ‘)’ we will pop all the operators till first ‘(‘,
⇒ Pop
⇒ Push /
⇒ Push ‘(’
⇒ Read F,
⇒ Push ‘+’
⇒ Read D,
⇒ Since + is left associative, so pop ‘+’,
⇒ Push up
⇒ Read E,
⇒ Since ‘(’ came so pop till ‘)’,
⇒ Pop ‘/’
Hence, postfix expression is,
AB + CD ++ FD ++ E +/
(A + B + (C + D))/ (F + D + F)
⇒ Push ‘(’
⇒ Read A
⇒ Push ‘+’
⇒ Read B
⇒ Since ‘+’ is Left associative, so ‘+’ in stack will have higher procedure then the current ‘+’, hence pop it,
⇒ Push ‘+’
⇒ Push ‘(’
⇒ Read C
⇒ Push ‘+’
⇒ Read D,
⇒ Now on looking ‘)’ we will pop all the operators till first ‘(‘,
⇒ Pop
⇒ Push /
⇒ Push ‘(’
⇒ Read F,
⇒ Push ‘+’
⇒ Read D,
⇒ Since + is left associative, so pop ‘+’,
⇒ Push up
⇒ Read E,
⇒ Since ‘(’ came so pop till ‘)’,
⇒ Pop ‘/’
Hence, postfix expression is,
AB + CD ++ FD ++ E +/
Question 46 
If the binary search algorithm determines that the search argument is in the lower half of the array, which of the following statements will set the appropriate variable to the appropriate value?
Start Sub = Middle Sub – 1 :  
Start Sub = Middle Sub + 1 :  
Stop Sub = Middle Sub – 1 :  
Stop Sub = Middle Sub + 1 : 
Question 46 Explanation:
If binary search algorithm determines that the search argument is in the lower half of the array then
start sub = 0;
stop sub = Middle sub + 1;
start sub = 0;
stop sub = Middle sub + 1;
Question 47 
Which of the following is not used as an intermediate representation?
Postfix notation  
DAG  
3 address code  
Context free grammar 
Question 47 Explanation:
Postfix, DAG , and three address code is an intermediate representation. But context free grammar is not an intermediate representation.
Question 48 
If L_{1} and L_{2} are two regular language defined as
L_{1} = (000, 001, 0, 010) and L_{2} = ( 00, 01, 0), then the number of strings in L_{1} ∪ L_{2} will be
L_{1} = (000, 001, 0, 010) and L_{2} = ( 00, 01, 0), then the number of strings in L_{1} ∪ L_{2} will be
7  
6  
5  
8 
Question 48 Explanation:
L_{1}UL_{2} = (000,001,0,010,00,01)
Therefore no. of strings is 6.
Therefore no. of strings is 6.
Question 49 
Two finite state machines are said to be equivalent if they
Have same number of states  
Have same number of edges
 
Have same number of states and edges  
Recognize same set of tokens 
Question 49 Explanation:
Two finite state machines are said to be equivalent if they recognize same set of tokens.
Question 50 
The number of productions of the following grammar is
E → E+T  T T → T*F  F F → E id
5  
3  
6  
4 
Question 50 Explanation:
Total 6 productions are there.
E>E+T
E>T
T>T*F
T>F
F>(E)
F>id
E>E+T
E>T
T>T*F
T>F
F>(E)
F>id
Question 51 
CFG can be recognized by a
pushdown automata  
2way linear bounded automata
 
both (A) and (B)  
none of these 
Question 51 Explanation:
CFG can be recognized by pushdown automata. Moreover every CFG is a CSG and every CSG can be recognized by linear bounded automata. Hence every CFG can be recognized by linear bounded automata.
Question 52 
Canonical derivations are otherwise called as
left most derivations  
right most derivations  
left most reductions  
right most reductions 
Question 52 Explanation:
A rightmost derivation step is also called canonical. If every derivation step is rightmost, then this is a canonical derivation. Each in a derivation is called a sequential form of G.
Question 53 
Which of the following implementations of three address codes occupy less space?
Triple  
Quadruples  
Indirect triples  
All will occupy same space 
Question 53 Explanation:
Indirect triples occupy the least space as they are just pointers to triples.
Question 54 
Macroexpansion type parameter passing is called as
Callby value  
Callby reference  
Copyrestore  
Callby name 
Question 54 Explanation:
For C, "callbymacroexpansion" doesn't exist. Instead, for macros the preprocessor does a glorified "cut&paste" operation on raw text.
Question 55 
With a single resource, deadlock occurs
If there are more than two processes competing for that resource  
If there are only two processes competing for that resource  
If there is a single process competing for that resource  
None of these 
Question 55 Explanation:
With a single resource deadlock can never occur.
For a deadlock to occur atleast two resource should be there. Suppose that two resources are there and two processes are there then each process will acquire one resource and wait for the resources held by opposition process to complete and this way deadlock can occur.
Question 56 
Mutual exclusion problem occurs between
Two disjoint processes that do not interact  
Processes that share resources  
Processes that do not use the same resource  
None of these 
Question 56 Explanation:
Mutual exclusion problem occurs between processes that share resources.
Question 57 
In a Round Robin CPU scheduling, as the time quantum is increased, the average turnaround time
Increases  
Decreases  
Remains constant  
Varies irregularly 
Question 57 Explanation:
In round robin scheduling algorithm time quantum is nowhere related to turn around time.
Question 58 
A computer system has 4k word cache organized in a blocksetassociative manner, with 4 blocks per set, 64 words per block. The number of bits in the SET and WORD fields of the main memory address format is
15, 4  
6, 4  
7, 2  
4, 6 
Question 58 Explanation:
Size of block = 64 w = 2^{6} w
So, offset bit = 6
No. of blocks in a cache = 2^{12}/2^{6} = 2^{6}
No. of sets in cache = 2^{6}/2^{2} = 2^{4}
So, index bits = 4
Question 59 
Relocatable programs
Cannot be used with fixed partitions  
Can be loaded almost anywhere in memory  
Do not need a linker  
Can be loaded only at one specific location 
Question 59 Explanation:
Relocatable programs can be loaded almost any where in memory because they use relocatable address.
Question 60 
Program threats are
Trojan Horse  
Trap doors  
Both (A) and (B)  
None of these 
Question 60 Explanation:
Program threats are :
Trojan Horse − Such program traps user login credentials and stores them to send to malicious user who can later on login to computer and can access system resources.
Trap Door − If a program which is designed to work as required, have a security hole in its code and perform illegal action without knowledge of user then it is called to have a trap door.
Logic Bomb − Logic bomb is a situation when a program misbehaves only when certain conditions met otherwise it works as a genuine program. It is harder to detect.
Virus − Virus as name suggest can replicate themselves on computer system. They are highly dangerous and can modify/delete user files, crash systems. A virus is generally a small code embedded in a program. As user accesses the program, the virus starts getting embedded in other files/ programs and can make system unusable for user.
Trojan Horse − Such program traps user login credentials and stores them to send to malicious user who can later on login to computer and can access system resources.
Trap Door − If a program which is designed to work as required, have a security hole in its code and perform illegal action without knowledge of user then it is called to have a trap door.
Logic Bomb − Logic bomb is a situation when a program misbehaves only when certain conditions met otherwise it works as a genuine program. It is harder to detect.
Virus − Virus as name suggest can replicate themselves on computer system. They are highly dangerous and can modify/delete user files, crash systems. A virus is generally a small code embedded in a program. As user accesses the program, the virus starts getting embedded in other files/ programs and can make system unusable for user.
Question 61 
Time complexity of an algorithm T(n), where n is the input size is given by
T(n) = T(n1)+1/n, if n<1 = 1, otherwiseThe order of this algorithm is
log n  
n  
n^{2}  
n^{n} 
Question 61 Explanation:
T(n) = T(n1) + 1/n  (I)
T(n1) = T(n2) + 1/n1 (II)
T(n2) = T(n3) + 1/n2 (III)
Putting (II) in (I),
T(n) = T(n2) + 1/n1 + 1/n (IV)
Putting (III) in (IV),
T(n) = T(n3) + 1/n2 + 1/n1 + 1/n
⋮
T(n) = T(nk) + 1/n(k+1) + … 1/n2 + 1/n1 + 1/n
Base condition is,
T(1) = 1
So, nk = 1
k = n1
So, T(n) = T(1) + 1/n(n1) + ½ + … + 1/n1 + 1/n
= 1 + 1/1 + ½ + ⅓ + … + 1/n
= O(log n)
T(n1) = T(n2) + 1/n1 (II)
T(n2) = T(n3) + 1/n2 (III)
Putting (II) in (I),
T(n) = T(n2) + 1/n1 + 1/n (IV)
Putting (III) in (IV),
T(n) = T(n3) + 1/n2 + 1/n1 + 1/n
⋮
T(n) = T(nk) + 1/n(k+1) + … 1/n2 + 1/n1 + 1/n
Base condition is,
T(1) = 1
So, nk = 1
k = n1
So, T(n) = T(1) + 1/n(n1) + ½ + … + 1/n1 + 1/n
= 1 + 1/1 + ½ + ⅓ + … + 1/n
= O(log n)
Question 62 
Which of the following statements is true?
I. As the number of entries in a hash table increases, the number of collisions increases.
II. Recursive programs are efficient.
III. The worst case complexity for quick sort is O(n^{2}).
IV. Binary search using a linear linked list is efficient.
I. As the number of entries in a hash table increases, the number of collisions increases.
II. Recursive programs are efficient.
III. The worst case complexity for quick sort is O(n^{2}).
IV. Binary search using a linear linked list is efficient.
I and II  
II and III  
I and IV  
I and III 
Question 62 Explanation:
I. True
II. Not always true.
III. True
IV. False, binary search using array is efficient, because using linked list random access is not possible.
II. Not always true.
III. True
IV. False, binary search using array is efficient, because using linked list random access is not possible.
Question 63 
Breadth first traversal is a method to traverse
All successor of a visited node before any successors of any of those successors  
A single path of the graph as far it can go  
Graph using shortest path  
None of these 
Question 63 Explanation:
Breadth first traversal is a method to traverse all successor of a visited node before any successors of any of those successors.
Question 64 
The algorithm design technique used in the quick sort algorithm is
Dynamic programming  
Back tracking  
Divide and conquer  
Greedy method 
Question 64 Explanation:
The algorithm design technique used in the quick sort algorithm is divide and conquer.
Question 65 
Algorithm which solves the allpair shortest path problem is
Dijkstra’s algorithm  
Floyd’s algorithm  
Prim’s algorithm  
Warshall’s algorithm  
B & D 
Question 65 Explanation:
Dijkstra’s algorithm is a single source shortest path algorithm.
Floyd’s warshall is all pair shortest path algorithm.
Prim's algorithm is minimum spanning tree algorithm.
Floyd’s warshall is all pair shortest path algorithm.
Prim's algorithm is minimum spanning tree algorithm.
Question 66 
Consider the following two functions:
g_{1}(n) = {n^{3} for 0≤n<10,000 n^{2} for n≥10,000 g_{2}(n) = {n for 0≤n<100 n^{3} for n≥100Which of the following is true?
g_{1}(n) is O(g_{2}(n))  
g_{1}(n) is 0(n^{3})
 
g_{2}(n) is 0 (g_{1}(n))  
g_{2}(n) is 0(n) 
Question 66 Explanation:
Whenever we go for asymptotic complexity, we look for large value of n. So in the given question, for large value of n like n>=10000, g_{1}(n)=n^{2} and g_{2}(n)=n^{3}. So clearly g_{1}(n) is O(g_{2}(n)).
Question 67 
Who got the Nobel Prize for Peace in the year 2011?
Thomas Sargent  
Christopher Sims  
Ellen Johnson Sirleaf. Leymah Gbowee and Tawakkol Karman  
Domas Transtroma 
Question 67 Explanation:
The Nobel Peace Prize 2011 was awarded jointly to Ellen Johnson Sirleaf, Leymah Gbowee and Tawakkol Karman "for their nonviolent struggle for the safety of women and for women's rights to full participation in peacebuilding work."
Question 68 
Which country won the Kabaddi World Cup, 2011?
United Kingdom  
India  
Canada  
Germany 
Question 68 Explanation:
India won the kabaddi world cup, 2011.
Question 69 
The Raman effect is used in the study of
Xrays  
Cells  
Chromosomes  
Molecular energy 
Question 69 Explanation:
The spectrum of the Ramanscattered light depends on the molecular constituents present and their state, allowing the spectrum to be used for material identification and analysis. Raman spectroscopy is used to analyze a wide range of materials, including gases, liquids, and solids.
Question 70 
Green India Programme is the National Action plan on
Pollution  
Climate change  
Rainfall  
Environment 
Question 70 Explanation:
GIM is one of the eight key Missions outlined under National Action Plan on Climate Change (NAPCC). It aims at protecting, enhancing and restoring India's decreasing forest cover and responding to climate change by a combination of mitigation and adaptation measures.
Question 71 
Which of the following is measured on the Richter scale?
Density of liquids  
Intensity of earthquakes  
Velocity of tornadoes  
Height of mountains 
Question 71 Explanation:
The Richter scale measures the maximum amplitude of seismic waves as they reach seismographs. This scale is expressed with a logarithmic scale. Thus, an earthquake measuring 7.0 on the Richter scale would be 10 times larger than an earthquake that measures 6.0.
Question 72 
Who led the French forces during the battle of Waterloo?
Duke of Wellington  
Duke of Cornwall  
Napoleon Bonaparte  
Duke of Scotland 
Question 72 Explanation:
A French army under the command of Napoleon Bonaparte was defeated by two of the armies of the Seventh Coalition: an Angloled Allied army under the command of the Duke of Wellington, and a Prussian army under the command of Gebhard Leberecht von Blücher.
Question 73 
Which of the following is a direct tax?
Excise duty  
Sales tax  
Income tax  
Both (B) & (C) 
Question 73 Explanation:
A taxpayer, for example, pays direct taxes to the government for different purposes, including real property tax, personal property tax, income tax or taxes on assets. Therefore, income tax is a direct tax.
Question 74 
In an 8085 microprocessor system with memory mapped I/O.
I/O devices have 8 bit addresses  
I/O devices are accessed using IN and OUT instructions  
There can be maximum of 256 input devices and 256 output devices  
Arithmetic and logic operations can be directly performed with the I/O data 
Question 74 Explanation:
In a 8085 microprocessor system with memory mapped I/O then Arithmetic and logic operations can be directly performed with the I/O data. ... An arithmeticlogic unit (ALU) is the part of a computer processor (CPU) that carries out arithmetic and logic operations on the operands in computer instruction words.
Question 75 
Consider the following set of statements?
Float x, y : x=7;y=10: x*=y*=y*28.5 :After the execution of the above set of statements, the value of x will be
70  
2695  
2995  
None of these 
Question 75 Explanation:
Arithmetic operator has the higher precedence so y*28.5 will be calculated first which will give 10*28.5=285.
So now the statement will become x*=y*=285;
The assignment operator has right to left associativity. So now,
x*=(y=y*285)
x*=(y=10*285)
x*=(y=2850)
x=x*2850
x=7*2850
x=19950
So now the statement will become x*=y*=285;
The assignment operator has right to left associativity. So now,
x*=(y=y*285)
x*=(y=10*285)
x*=(y=2850)
x=x*2850
x=7*2850
x=19950
Question 76 
Depth of a complete binary tree with n nodes is (where log is to the base 2).
log (n+1)1  
log (n)  
log (n1)+1  
log (n)+1 
Question 76 Explanation:
Let's take example,
n=7
So depth is 2.
Now let's check option by option,
A) log(n+1)  1
log(7+1)  1
= 3  1 = 2
B) log n
log 7
= 2・8
C) log(n1) + 1
log(71) + 1
log 6 + 1 = 2.58 + 1
= 3.58
D) log n + 1
log 7 + 1
= 2・8 + 1 = 3.8
n=7
So depth is 2.
Now let's check option by option,
A) log(n+1)  1
log(7+1)  1
= 3  1 = 2
B) log n
log 7
= 2・8
C) log(n1) + 1
log(71) + 1
log 6 + 1 = 2.58 + 1
= 3.58
D) log n + 1
log 7 + 1
= 2・8 + 1 = 3.8
Question 77 
The following sequence of operations is performed on a stack:
PUSH ( 10 ). PUSH ( 20 ). POP. PUSH ( 10 ). PUSH ( 20 ). POP. POP. POP. PUSH ( 20 ). POPThe sequence of values popped out is
20, 10, 20, 10, 20  
20, 20, 10, 10, 20  
10, 20, 20, 10, 20  
20, 20, 10, 20, 10 
Question 77 Explanation:
⇒ Push(10)
⇒ Push(20)
⇒ Pop 20
⇒ Push(10)
⇒ Push(20)
⇒ Pop 20
⇒ Pop 10
⇒ Pop 10
⇒ Push(20)
⇒ Pop 20
⇒ Push(20)
⇒ Pop 20
⇒ Push(10)
⇒ Push(20)
⇒ Pop 20
⇒ Pop 10
⇒ Pop 10
⇒ Push(20)
⇒ Pop 20
Question 78 
The larger the RAM of computer for faster is the speed since it eliminates
Need for ROM  
Need for external memory  
Frequent disk I/O  
Need for a data wide path 
Question 78 Explanation:
Since RAM size is large so there will be less page fault, hence less disk I/O.
Question 79 
The language L = {a^{n}b^{m}c^{n}d^{m} n≥1, m≥1}
Is context free  
Is not context free  
Abstract problem of checking number of formal and actual parameters  
Both (B) and (C).

Question 79 Explanation:
The given language is not context free because first we will push a’s and then we cant push b’s because we have to pop the a’s from the stack with corresponding c’s. And since we cant push b’s which cannot be compared by further d’s which is dependent on b’s.
Also given language is abstract problem of checking number of formal and actual parameters.
Also given language is abstract problem of checking number of formal and actual parameters.
Question 80 
What is the highest type number which can be applied to the following grammar?
S→Aa, A→Ba, B→abc
Type 0  
Type 1  
Type 2  
Type 3 
Question 80 Explanation:
The given grammar is left linear grammar which is also a regular grammar. Hence the highest type number which can be applied to the following grammar is Type 3 which is notation for regular grammar.
Question 81 
How many 4 digit even numbers have all 4 digits distinct?
2240  
2296  
2620  
4536 
Question 81 Explanation:
For the no. to be even last digit should be even,
Case3: Last digit contains ‘0’,
= 9 × 8 × 7
= 504
Case2: Last digit does not contains ‘0’,
= 8 × 8 × 7 × ^{4}C_{1}
= 1792
∴ Answer is = 1792 + 504 = 2296
Case3: Last digit contains ‘0’,
= 9 × 8 × 7
= 504
Case2: Last digit does not contains ‘0’,
= 8 × 8 × 7 × ^{4}C_{1}
= 1792
∴ Answer is = 1792 + 504 = 2296
Question 82 
In a group of 72 students, 47 have background in Electrical, 59 have background in Mathematics and 42 have background in both the subjects. How many students do not have background in any of the subjects?
8  
13  
25  
34 
Question 82 Explanation:
Let E be Electrical
Let M be Mathematics
Now,
Given: E = 47
M = 59
E ⋂ M = 42
Asking,
We know that,
Now,
E ∪ M = E + M  (E⋂M)
= 47 + 59  42
= 106  42
= 64
Let M be Mathematics
Now,
Given: E = 47
M = 59
E ⋂ M = 42
Asking,
We know that,
Now,
E ∪ M = E + M  (E⋂M)
= 47 + 59  42
= 106  42
= 64
Question 83 
The number of different signals which can be given from 6 flags of different colours taken one or more at a time, is
1958  
1956  
16  
64 
Question 83 Explanation:
The no. of different signals which can be given from 6 flags of different colours taking n colours at a time,
where,
1 ≤ n ≤ 6
when n=1,
^{6}C_{1} × ∠1 = 6
when n=2,
^{6}C_{6} × ∠2 = 30
when n=3,
^{6}C_{3} × ∠3 = 120
when n=4,
^{6}C_{4} × ∠4 = 360
when n=5,
^{6}C_{5} × ∠5 = 720
when n=6,
^{6}C_{6} × ∠6 = 720
Total no. of ways
= 6 + 30 + 120 + 360 + 720 + 720
= 1956
where,
1 ≤ n ≤ 6
when n=1,
^{6}C_{1} × ∠1 = 6
when n=2,
^{6}C_{6} × ∠2 = 30
when n=3,
^{6}C_{3} × ∠3 = 120
when n=4,
^{6}C_{4} × ∠4 = 360
when n=5,
^{6}C_{5} × ∠5 = 720
when n=6,
^{6}C_{6} × ∠6 = 720
Total no. of ways
= 6 + 30 + 120 + 360 + 720 + 720
= 1956
Question 84 
For matrix , the eigenvector is
[3 2]  
[4 3]  
[2 1]  
[2 1]  
C and D 
Question 84 Explanation:
Question 85 
A given grammar is said to be ambiguous if
Two or more productions have the same nonterminal on the left hand side  
A derivation tree has more than one associated sentence
 
There is a sentence with more than one derivation tree corresponding to it  
Brackets are not present in the grammar

Question 85 Explanation:
A given grammar is said to be ambiguous if for a sentence or a string there is more than one derivation tree present for it.
Question 86 
These are five records in a database:
Name Age Occupation Category Raman 27 CON A Akbar 22 ENG B Janifar 28 DOC C Maya 32 SER D Deva 24 MUS EThere is an index file associated with this and it contains the values 1, 3, 2, 5, 4. Which one of the fields is the index built form?
Age  
Name  
Occupation  
Category 
Question 86 Explanation:
Occupation is the field from which the index is built from, taking first letter into consideration which is ordered as they are alphabetically ordered..
First CONStarts with C
Second DOCStarts with D
Third ENGStarts with E
Fourth MUSstarts with M
Fifth SERStrats with S
First CONStarts with C
Second DOCStarts with D
Third ENGStarts with E
Fourth MUSstarts with M
Fifth SERStrats with S
Question 87 
IP address can be used to specify a broadcast and map to hardware broadcast, if available. By conversion broadcast address has hosted with all bits is
0  
1  
Both (A) and (B)  
None of these 
Question 87 Explanation:
For limited broadcast all bits are 1 in destination IP address.
Question 88 
Manchester code is a
NRZ code  
Polar code  
Both (A) and (B)  
None of these 
Question 88 Explanation:
Manchester code is a polar code.
NRZ code is a unipolar code.
NRZ code is a unipolar code.
Question 89 
A noiseless 3 kHz channel transmits bits with binary level signals. What is the maximum data rate?
3 kbps  
6 kbps  
12 kbps  
24 kbps 
Question 89 Explanation:
Bitrate = 2 * Bandwidth * log_{2}(L)
where,
L = no. of signal levels
Since it is saying binary level signals, it means two level signals.
So,
L = 2
∴ Bitrate = 2 * 3 * 10^{3} * log_{2}2
= 6 × 10^{3} × 1 bps
= 6 kbps
where,
L = no. of signal levels
Since it is saying binary level signals, it means two level signals.
So,
L = 2
∴ Bitrate = 2 * 3 * 10^{3} * log_{2}2
= 6 × 10^{3} × 1 bps
= 6 kbps
Question 90 
Poor response time is caused by
Process or busy  
High I/O rate  
High paging rates  
All of these

Question 90 Explanation:
Poor response times are usually caused by Process busy, High I/O rates and High paging rates. ... In computing, a process is an instance of a computer program that is being executed. It contains the program code and its activity.
Question 91 
Parallel printer uses
RS 232 C interface  
Centronics interface  
Handshake mode  
All of these

Question 91 Explanation:
On PCs, the parallel port uses a 25pin connector (type DB25) and is used to connect printers, computers and other devices that need relatively high bandwidth. It is often called a Centronics interface after the company that designed the original standard for parallel communication between a computer and printer.
Question 92 
Consider join of a relation R with a relation S. If R has m tuples and S has n tuples then maximum and minimum sizes of the join respectively are
m+n and O  
mn and O
 
m+n and mn  
mn and m+n 
Question 92 Explanation:
For maximum no. of tuples,
If every row of r matches with each row of s, i.e., it means, the join attribute has the same value in all the rows of both r and s, then maximum mn tuples possible.
For minimum no. of tuples, if condition of join is not satisfied for any tuple then, minimum 0 tuples will be there.
If every row of r matches with each row of s, i.e., it means, the join attribute has the same value in all the rows of both r and s, then maximum mn tuples possible.
For minimum no. of tuples, if condition of join is not satisfied for any tuple then, minimum 0 tuples will be there.
Question 93 
Errors that can be pointed out by the compiler are
Syntax errors  
Semantic errors  
Logical errors  
Internal errors

Question 93 Explanation:
The errors that can be pointed out by the compiler are Syntax error. In computer science, a syntax error is an error in the syntax of a sequence of characters or tokens that is intended to be written in a particular programming language. For compiled languages, syntax errors are detected at compiletime.
Question 94 
Consider six files: F_{1}, F_{2}, F_{3}, F_{4}, F_{5}, F_{6} with corresponding sizes 100, 200, 70, 40, 250 and 50 respectively. The files are to be stored on a sequential device in such a way that as to optimize access time. In what order should the files be stored?
F_{6}, F_{5}, F_{4}, F_{3}, F_{2}, F_{1}  
F_{1}, F_{2}, F_{3}, F_{4}, F_{5}, F_{6}  
F_{5}, F_{2}, F_{1}, F_{3}, F_{6}, F_{4}  
F_{4}, F_{6}, F_{3}, F_{1}, F_{2}, F_{5} 
Question 94 Explanation:
To optimize access time of the files they should be placed in a sequential device according to their sizes in increasing order.
So the order will be F_{4}, F_{6}, F_{3}, F_{1}, F_{2}, F_{5}.
So the order will be F_{4}, F_{6}, F_{3}, F_{1}, F_{2}, F_{5}.
Question 95 
Disk requests come to a disk driver for cylinders 10, 22, 20, 2, 40, 6 and 38. In that order at a time when the disk drive is reading from cylinder 20. The seek time is 6 ms per cylinder. If the scheduling algorithm is the closest cylinder next, then the total seek time will be
360 ms  
876 ms  
850 ms  
900 ms 
Question 95 Explanation:
∴ Total Seek time,
No. of cylinder movement × Seek time per cylinder
((2220) + (2210) + (106) + (62) + (382) + (4035)) × 6
= (2 + 12 + 4 + 4 + 36 + 2) × 6
= (22 + 38) × 6
= 360
Question 96 
A search procedure which associates an address with a key value and provides a mechanism for dealing with two or more values assigned to the same address is called
Linear search  
Binary search  
Hash coded search  
Radix search 
Question 96 Explanation:
A search procedure which associates an address with a key value and provides a mechanism for dealing with two or more values assigned to the same address is called Hash coded search.
Question 97 
Search tables used by compilers for efficient searching generally use
Hash tables  
Linear lists of records  
Binary search tables  
Binary search trees

Question 97 Explanation:
Search table used by compilers for efficient searching is hash tables.
Question 98 
he running time of an algorithm T(n) where (n) is the input size, is given by
The order of the algorithm is
T(n) = 7T(n/2)+qn, if n>1 = p if n=1Where p, q are constants.
The order of the algorithm is
n^{2}  
n^{n}  
n^{3}  
n 
Question 98 Explanation:
T(n) = 7T(n/2) + qn
a=7, b=2, k=1
a > b^{k}, so Case 1 applies here.
Hence the answer is,
a=7, b=2, k=1
a > b^{k}, so Case 1 applies here.
Hence the answer is,
Question 99 
Uniform symbol table
Contains all constants in the program  
Is a permanent table of division rules in the form of patterns for matching with the uniform symbol table to discover syntactic structure
 
Consists of full or partial list of the tokens as they appear in the program, created by Lexical Analysis and used for syntax analysis and interpretation  
A permanent table which lists all key words and special symbols of the language in symbolic form 
Question 99 Explanation:
Uniform Symbols Table consists of a full or partial list of the token's as they appear in the program. Created by Lexical analysis and used for syntax analysis and interpretation.
There are 99 questions to complete.