UGC NET CS 2013 Junepaper2
Question 1 
COCOMO stands for
COmposite COst MOdel  
COnstructive COst MOdel  
COnstructive Composite MOdel  
COmprehensive Construction MOdel 
Question 1 Explanation:
COCOMO stands for COnstructive COst MOdel. It is a procedural software cost estimation model but not software process model. Linear sequential,prototype and spiral models are software process models.
The basic COCOMO equations take the form
1. Effort Applied (E) = a(KLOC)^{b} [ manmonths ]
2. Development Time (D) = c(Effort Applied)^{d }[months]
3. People required (P) = Effort Applied / Development Time [count]
The basic COCOMO equations take the form
1. Effort Applied (E) = a(KLOC)^{b} [ manmonths ]
2. Development Time (D) = c(Effort Applied)^{d }[months]
3. People required (P) = Effort Applied / Development Time [count]
Question 2 
Match the following :
aiii, bii, civ, di  
aii, biii, civ, di  
ai, bii, civ, diii  
ai, bii, ciii, div 
Question 2 Explanation:
Good quality→ Meets both functional and nonfunctional requirements
Correctness→ Meets the functional requirements
Predictable→ Process is under statistical control
Reliable→ Program does not fail for a specified time in a given environment
Correctness→ Meets the functional requirements
Predictable→ Process is under statistical control
Reliable→ Program does not fail for a specified time in a given environment
Question 3 
While estimating the cost of software, Lines Of Code(LOC) and Function Points(FP) are used to measure which one of the following ?
Length of code  
Size of software  
Functionality of software  
None of the above 
Question 3 Explanation:
→ A function point is a "unit of measurement" to express the amount of business functionality an information system (as a product) provides to a user. Function points are used to compute a functional size measurement (FSM) of software. The cost (in dollars or hours) of a single unit is calculated from past projects.
→ Lines of code (LOC) is a software metric used to measure the size of a computer program by counting the number of lines in the text of the program's source code.
→ Lines of code (LOC) is a software metric used to measure the size of a computer program by counting the number of lines in the text of the program's source code.
Question 4 
A good software design must have
High module coupling, High module cohesion  
High module coupling, Low module cohesion  
Low module coupling, High module cohesion  
Low module coupling, Low module cohesion 
Question 4 Explanation:
→ A good software design must have low module coupling and high module cohesion.
→ Coupling and Cohesion are used in software design. Cohesion measures strength of a module while coupling measures interdependency between modules.
→ Coupling and Cohesion are used in software design. Cohesion measures strength of a module while coupling measures interdependency between modules.
Question 5 
Cyclometric complexity of a flow graph G with n vertices and e edges is
V(G) = e+n–2  
V(G) = e–n+2  
V(G) = e+n+2  
V(G) = e–n–2 
Question 5 Explanation:
Cyclomatic complexity uses 3 formulas:
1. The number of regions corresponds to the cyclomatic complexity
2. V(G),Flow graph is defined as V(G)=EN+2 where E is the number of flow graph edges, and N is the number of flow graph nodes.
3. V(G),Flow graph is defined as V(G)=P+1 where p is the number of predicate nodes contained in the flow graph G.
1. The number of regions corresponds to the cyclomatic complexity
2. V(G),Flow graph is defined as V(G)=EN+2 where E is the number of flow graph edges, and N is the number of flow graph nodes.
3. V(G),Flow graph is defined as V(G)=P+1 where p is the number of predicate nodes contained in the flow graph G.
Question 6 
When the following code is executed what will be the value of x and y ?
int x = 1, y = 0;
y = x++;
2,1  
2,2  
1,1  
1,2 
Question 6 Explanation:
Given post increment for x value. In post increment the value assign first and update after assigning.
So, x=2 and y=1
So, x=2 and y=1
Question 7 
How many values can be held by an array A(–1,m;1,m) ?
m  
m^{2}  
m(m+1)  
m(m+2) 
Question 7 Explanation:
int A[n] means "n" elements and index starts from 0 to n1.
→ Similarly, int A[n][n] means both column and rows has "n" elements and total elements are n*n nothing but n^{2} elements.
In the given example ,an array A(1,m;1,m)
→ In which rows indexes are 1,0,1,2, and so on up to m then total rows are "m+2".
→ columns consist of 1,2,3 and so on up to m then total elements in columns are "m".
Total elements are (m+2)*m
→ Similarly, int A[n][n] means both column and rows has "n" elements and total elements are n*n nothing but n^{2} elements.
In the given example ,an array A(1,m;1,m)
→ In which rows indexes are 1,0,1,2, and so on up to m then total rows are "m+2".
→ columns consist of 1,2,3 and so on up to m then total elements in columns are "m".
Total elements are (m+2)*m
Question 8 
What is the result of the expression (1&2)+(3/4) ?
1  
2  
3  
0 
Question 8 Explanation:
Given statement, (1&2)+(3/4)
(1&2) means (1 AND 2)
(¾) means (3 divided by 4)
Step1: First consider (1&2)
(1&2) means (1 AND 2)
(¾) means (3 divided by 4)
Step1: First consider (1&2)
Question 9 
How many times the word ‘print’ shall be printed by the following program segment ?
for (i=1, i≤2,i++)
for (j=1,j≤2,j++)
for(k=1,k≤2,k++)
printf("print/n")
for (i=1, i≤2,i++)
for (j=1,j≤2,j++)
for(k=1,k≤2,k++)
printf("print/n")
1  
3  
6  
8 
Question 9 Explanation:
Iteration1: In iteration1 of ith loop will execute once and jth loop 2 times.
Each jth loop will execute kth loop 2 times.
Finally, iteration1 will display 4 times of “print/n” word.
Iteration2: In iteration2 of ith loop will execute once and jth loop 2 times.
Each jth loop will execute kth loop 2 times.
Finally, iteration2 will display 4 times of “print/n” word.
Above code segment will print 8 times.
Better understanding purpose given modified code segment:
#include
int main()
{
int i,j,k,jj=0,kk=0,ii=0;
for(i=1;i<=2;i++)
{
ii++;
for(j=1;j<=2;j++)
{
jj++;
for(k=1;k<=2;k++)
{
kk++;
printf("print/n");
}
}
}
printf("ii=%d \t jj=%d \t kk=%d",ii,jj,kk);
return 0;
}
Output:
print/n print/n print/n print/n print/n print/n print/n print/n
ii=2 jj=4 kk=8
Each jth loop will execute kth loop 2 times.
Finally, iteration1 will display 4 times of “print/n” word.
Iteration2: In iteration2 of ith loop will execute once and jth loop 2 times.
Each jth loop will execute kth loop 2 times.
Finally, iteration2 will display 4 times of “print/n” word.
Above code segment will print 8 times.
Better understanding purpose given modified code segment:
#include
int main()
{
int i,j,k,jj=0,kk=0,ii=0;
for(i=1;i<=2;i++)
{
ii++;
for(j=1;j<=2;j++)
{
jj++;
for(k=1;k<=2;k++)
{
kk++;
printf("print/n");
}
}
}
printf("ii=%d \t jj=%d \t kk=%d",ii,jj,kk);
return 0;
}
Output:
print/n print/n print/n print/n print/n print/n print/n print/n
ii=2 jj=4 kk=8
Question 10 
Which of the following is not a type of Database Management System ?
Hierarchical  
Network  
Relational  
Sequential 
Question 10 Explanation:
Most common types of database management system types are
1. Hierarchical databases
2. Network databases
3. Relational databases
4. Objectoriented databases
5. Graph databases
6. ER model databases
7. Document databases
1. Hierarchical databases
2. Network databases
3. Relational databases
4. Objectoriented databases
5. Graph databases
6. ER model databases
7. Document databases
Question 11 
Manager’s salary details are to be hidden from Employee Table. This Technique is called as
Conceptual level Datahiding  
Physical level Datahiding  
External level Datahiding  
Logical level Datahiding 
Question 11 Explanation:
1. Physical (or) Internal view is at the lowest level of abstraction, closest to the physical storage method used. It indicates how the data will be stored and describes the data structures and access methods to be used by the database. There is one internal view for the entire database.
2. Global or Conceptual View : At this level of abstraction all the database entities and the relationships among them are included. There is one conceptual view for the entire database.
3. External or User View: The external or user view is at the highest level of database abstraction where only those portions of the database concern to a user or application programme are included. Any number if external or user views may exists for a given global or conceptual view.
2. Global or Conceptual View : At this level of abstraction all the database entities and the relationships among them are included. There is one conceptual view for the entire database.
3. External or User View: The external or user view is at the highest level of database abstraction where only those portions of the database concern to a user or application programme are included. Any number if external or user views may exists for a given global or conceptual view.
Question 12 
A Network Schema
restricts to one to many relationship  
permits many to many relationship  
stores Data in a Database  
stores Data in a Relation 
Question 12 Explanation:
→ The network model expands upon the hierarchical structure, allowing manytomany relationships in a treelike structure that allows multiple parents. It was most popular before being replaced by the relational model, and is defined by the CODASYL specification.
→ The network model organizes data using two fundamental concepts, called records and sets.
→ Records contain fields (which may be organized hierarchically, as in the programming language COBOL).
→ Sets (not to be confused with mathematical sets) define onetomany relationships between records: one owner, many members.
→ A record may be an owner in any number of sets, and a member in any number of sets.
→ The network model organizes data using two fundamental concepts, called records and sets.
→ Records contain fields (which may be organized hierarchically, as in the programming language COBOL).
→ Sets (not to be confused with mathematical sets) define onetomany relationships between records: one owner, many members.
→ A record may be an owner in any number of sets, and a member in any number of sets.
Question 13 
Which normal form is considered as adequate for usual database design ?
2NF  
3NF  
4NF  
5NF 
Question 13 Explanation:
3NF normal form is considered as adequate for usual database design. BCNF doesn't guarantee dependency preservation.
Question 14 
If D_{1},D_{2}, .. ..D_{n} are domains in a relational model, then the relation is a table, which is a subset of
D_{1}+D_{2}+ … +D_{n}  
D_{1}×D_{2}× … ×D_{n}  
D_{1}∪D_{2}∪ … ∪D_{n}  
D_{1}–D_{2}– … –D_{n} 
Question 14 Explanation:
In D_{1},D_{2},..,D_{n} are domains in a relational model, then the relation is a table, which s a subset of D_{1}xD_{2}x..xD_{n}
Question 15 
Which of the following addresses is used to deliver a message to the correct application program running on a host ?
Port  
IP  
Logical  
Physical 
Question 15 Explanation:
Port addresses is used to deliver a message to the correct application program running on a host.
Question 16 
In ________ substitution, a character in the plaintext is always changed to the same character in the ciphertext, regardless of its position in the text.
polyalphabetic  
monoalphabetic  
transpositional  
multi alphabetic 
Question 16 Explanation:
Monoalphabetic Substitution: The relationship between a character in the plaintext and a character in the ciphertext is always onetoone
Polyalphabetic Substitution: This is an improvement over the Caesar cipher. In polyalphabetic substitution, each occurrence of a character may have a different substitute. Here the relationship between a character in the plaintext and a character in the ciphertext is always onetomany.
Transposition Cipher: The transposition cipher, the characters remain unchanged but their positions are changed to create the ciphertext. A transposition cipher does not substitute one symbol for another, instead it changes the location of the symbols. A transposition cipher reorders symbols.
Polyalphabetic Substitution: This is an improvement over the Caesar cipher. In polyalphabetic substitution, each occurrence of a character may have a different substitute. Here the relationship between a character in the plaintext and a character in the ciphertext is always onetomany.
Transposition Cipher: The transposition cipher, the characters remain unchanged but their positions are changed to create the ciphertext. A transposition cipher does not substitute one symbol for another, instead it changes the location of the symbols. A transposition cipher reorders symbols.
Question 17 
In classful addressing, the IP address 190.255.254.254 belongs to
Class A  
Class B  
Class C  
Class D 
Question 17 Explanation:
→ Class A addresses only include IP starting from 1.x.x.x to 126.x.x.x only. The IP range 127.x.x.x is reserved for loopback IP addresses.
→ Class B IP Addresses range from 128.0.x.x to 191.255.x.x. The default subnet mask for Class B is 255.255.x.x.
→ Class C IP addresses range from 192.0.0.x to 223.255.255.x. The default subnet mask for Class C is 255.255.255.x.
→ Class B IP Addresses range from 128.0.x.x to 191.255.x.x. The default subnet mask for Class B is 255.255.x.x.
→ Class C IP addresses range from 192.0.0.x to 223.255.255.x. The default subnet mask for Class C is 255.255.255.x.
Question 18 
In hierarchical routing with 4800 routers, what region and cluster sizes should be chosen to minimize the size of the routing table for a three layer hierarchy ?
10 clusters, 24 regions and 20 routers  
12 clusters, 20 regions and 20 routers  
16 clusters, 12 regions and 25 routers  
15 clusters, 16 regions and 20 routers 
Question 18 Explanation:
Given data,
 Hierarchical routing with 4800 routers.
Hierarchical routing = cluster size * Regions * Routers
 Cluster size=?
 Regions=?
 Routers=?
Step1: Minimize size= (Clusters1) + (Regions1) + Routers
OptionA: 10 clusters, 24 regions and 20 routers
= 9 + 23 + 20
= 52
OptionB: 12 clusters, 20 regions and 20 routers
= 11 + 19 + 20
= 50
OptionC: 16 clusters, 12 regions and 25 routers
= 15 + 11 + 25
= 51
OptionD: 15 clusters, 16 regions and 20 routers
= 14 + 15 + 20
= 49
Hierarchical routing = cluster size * Regions * Routers
 Cluster size=?
 Regions=?
 Routers=?
Step1: Minimize size= (Clusters1) + (Regions1) + Routers
OptionA: 10 clusters, 24 regions and 20 routers
= 9 + 23 + 20
= 52
OptionB: 12 clusters, 20 regions and 20 routers
= 11 + 19 + 20
= 50
OptionC: 16 clusters, 12 regions and 25 routers
= 15 + 11 + 25
= 51
OptionD: 15 clusters, 16 regions and 20 routers
= 14 + 15 + 20
= 49
Question 19 
In IPv4 header, the ______ field is needed to allow the destination host to determine which datagram a newly arrived fragments belongs to.
identification  
fragment offset  
time to live  
header checksum 
Question 19 Explanation:
→ In IPv4 header, the identification field is needed to allow the destination host to determine which datagram a newly arrived fragments belongs to.
→ Identification field is primarily used for uniquely identifying the group of fragments of a single IP datagram.
→ Some experimental work has suggested using the ID field for other purposes, such as for adding packettracing information to help trace datagrams with spoofed source addresses.
→ Identification field is primarily used for uniquely identifying the group of fragments of a single IP datagram.
→ Some experimental work has suggested using the ID field for other purposes, such as for adding packettracing information to help trace datagrams with spoofed source addresses.
Question 20 
Given L1=L(a*baa*) and L2=L(ab*). The regular expression corresponding to language L3 = L1/L2 (right quotient) is given by
a*b  
a*baa*  
a*ba*  
None of the above 
Question 20 Explanation:
L1=L(a*baa*) and L2=L(ab*). The regular expression corresponding to language L3 = L1/L2
L1={ba, baa, baaa, .........................aba, aaba, aaaba,................abaa, abaaa, ....................}
L2={a, ab, abb, abbb, ..........................}
Take "a" from L1:
L1/a ={ b, ba, baa, .................ab, aab, aaab, ....................aba, abaa, .....................}
So we get : a*ba*
If you take "ab" from L2
Like:
L1/ab = you will not get any string i,e. empty set will be in result in case of L1/ab
as no string in L1 end with "ab"
L1={ba, baa, baaa, .........................aba, aaba, aaaba,................abaa, abaaa, ....................}
L2={a, ab, abb, abbb, ..........................}
Take "a" from L1:
L1/a ={ b, ba, baa, .................ab, aab, aaab, ....................aba, abaa, .....................}
So we get : a*ba*
If you take "ab" from L2
Like:
L1/ab = you will not get any string i,e. empty set will be in result in case of L1/ab
as no string in L1 end with "ab"
Question 21 
Given the production rules of a grammar G1 as
S_{1} → AB  aaB
A → a  Aa
B → b
and the production rules of a grammar G2 as
S_{2} → aS_{2}bS_{2}  bS_{2}aS_{2}  λ
Which of the following is correct statement ?
S_{1} → AB  aaB
A → a  Aa
B → b
and the production rules of a grammar G2 as
S_{2} → aS_{2}bS_{2}  bS_{2}aS_{2}  λ
Which of the following is correct statement ?
G1 is ambiguous and G2 is not ambiguous.  
G1 is ambiguous and G2 is ambiguous.  
G1 is not ambiguous and G2 is ambiguous.  
G1 is not ambiguous and G2 is not ambiguous. 
Question 21 Explanation:
Question 22 
Given a grammar : S1 → Sc, S → SA  A, A → aSb  ab, there is a rightmost derivation
S1 ⇒ Sc ⇒ SAC ⇒ SaSbc
Thus, SaSbc is a right sentential form, and its handle is
S1 ⇒ Sc ⇒ SAC ⇒ SaSbc
Thus, SaSbc is a right sentential form, and its handle is
SaS  
bc  
Sbc  
aSb 
Question 22 Explanation:
A “handle” of a string is a substring that matches the RHS of a production and whose reduction to the nonterminal (on the LHS of the production) represents one step along the reverse of a rightmost derivation toward reducing to the start symbol.
And in above question aSb is a handle because it's reduction to the LHS of production A → aSb represents one step along the reverse of a rightmost derivation toward reducing to the start symbol.
And in above question aSb is a handle because it's reduction to the LHS of production A → aSb represents one step along the reverse of a rightmost derivation toward reducing to the start symbol.
Question 23 
The equivalent production rules corresponding to the production rules
S → Sα_{1}  Sα_{2 } β_{1}  β_{2} is
S → β_{1}  β_{2}, A → α_{1}A  α_{2}A  λ  
S → β_{1} β_{2}  β_{1}A  β_{2}A, A → α_{1}A  α_{2}A  
S → β_{1}  β_{2}, A → α_{1}A  α_{2}A  
S → β_{1}  β_{2}  β_{1}A  β_{2}A, A → α_{1}A  α_{2}A  λ 
Question 23 Explanation:
Given grammar can generate { β_{1}, β_{2} , β_{2}α_{2}, , β_{2} α_{1}, , β_{1}α_{2}, , β_{1}α1 , β_{1} α_{1}α_{2}..................}
Option A can generate only {β_{1}, β_{2}} so it is not a correct option.
Option B is not correct because it have no terminating point strings containing {α_{1 } , α_{2}}
Option C is not correct because it can generate only {β_{1}, β_{2}}
Option D is correct answer because it can generate all the strings generated by given grammar.
Option A can generate only {β_{1}, β_{2}} so it is not a correct option.
Option B is not correct because it have no terminating point strings containing {α_{1 } , α_{2}}
Option C is not correct because it can generate only {β_{1}, β_{2}}
Option D is correct answer because it can generate all the strings generated by given grammar.
Question 24 
Given a Nondeterministic Finite Automation (NFA) with states p and r as initial and final states respectively and transition table as given below :
The minimum number of states required in Deterministic Finite Automation (DFA) equivalent to NFA is
The minimum number of states required in Deterministic Finite Automation (DFA) equivalent to NFA is
5  
4  
3  
2 
Question 24 Explanation:
The blank is nothing but "dead state". We have to consider as a dead state.
Now minimize the above DFA ( state q and s are equivalent and hence can be merged)
The min DFA will have 4 states.
Now minimize the above DFA ( state q and s are equivalent and hence can be merged)
The min DFA will have 4 states.
Question 25 
Which is the correct statement(s) for Non Recursive predictive parser ?
S1 : First(α) = { t  α⇒ *tβ for some string β}⇒ *tβ
S2 : Follow(X) = { a  S⇒ *αXaβ for some strings α and β}
S1 : First(α) = { t  α⇒ *tβ for some string β}⇒ *tβ
S2 : Follow(X) = { a  S⇒ *αXaβ for some strings α and β}
Both statements S1 and S2 are incorrect.  
S1 is incorrect and S2 is correct.  
S1 is correct and S2 is incorrect.  
Both statements S1 and S2 are correct. 
Question 25 Explanation:
Statement1:
→ See the symbol (⇒ *) means after some step , here * represent an arbitrary number of steps. * is not part of terminal.
→ So if alpha after some step has t as first symbol (terminal) in some sentential form , then first(alpha) must be {t}
Statement2:
α→∗tβ Here First(α) = {*} .
S→∗αXaβ
Follow(X) = {a}
So Statement S2 is correct.
→ So if alpha after some step has t as first symbol (terminal) in some sentential form , then first(alpha) must be {t}
Statement2:
α→∗tβ Here First(α) = {*} .
S→∗αXaβ
Follow(X) = {a}
So Statement S2 is correct.
Question 26 
Given an open address hash table with load factor α < 1, the expected number of probes in a successful search is
At most (1/α) ln ((1–α)/α)  
At most (1/α) ln (1/(1–α))  
At least (1/α) ln (1/(1– α))  
At least (1/α) ln (α/(1– α)) 
Question 26 Explanation:
Analysis of Open Addressing:
→ Given an openaddress hash table with load factor α = n/m < 1, the expected number of probes in an unsuccessful search is at most 1/(1 − α), assuming uniform hashing.
→ Given an openaddress hash table with load factor α = n/m < 1, the expected number of probes in a successful search is at most (1/α) ln (1/(1 − α)), assuming uniform hashing and assuming that each key in the table is equally likely to be searched for.
→ Given an openaddress hash table with load factor α = n/m < 1, the expected number of probes in an unsuccessful search is at most 1/(1 − α), assuming uniform hashing.
→ Given an openaddress hash table with load factor α = n/m < 1, the expected number of probes in a successful search is at most (1/α) ln (1/(1 − α)), assuming uniform hashing and assuming that each key in the table is equally likely to be searched for.
Question 27 
For a Btree of height h and degree t, the total CPU time used to insert a node is
O(h log t)  
O(h log t)  
O(t^{2}h)  
O(th) 
Question 27 Explanation:
→ For a Btree of height h and degree t, the total CPU time used to insert a node is O(th).
→ The number of disk pages accessed by Btree search is therefore O(h) = O(logt n), where ‘h’ is the height of the Btree and ‘n’ is the number of keys in the Btree.
→ The time taken by each node is O(t), and the total CPU time is O(th) = O(t logt n).
→ The number of disk pages accessed by Btree search is therefore O(h) = O(logt n), where ‘h’ is the height of the Btree and ‘n’ is the number of keys in the Btree.
→ The time taken by each node is O(t), and the total CPU time is O(th) = O(t logt n).
Question 28 
The time complexity to build a heap with a list of n numbers is
O(log n)  
O(n)  
O(n logn)  
O(n^{2}) 
Question 28 Explanation:
BuildMaxHeap(A)
// Input: A: an (unsorted) array
// Output: A modified to represent a heap.
// Running Time: O(n) where n = length[A]
1 heapsize[A] ← length[A]
2 for i ← Floor(length[A]/2) downto 1
3 MaxHeapify(A, i)
The BuildMaxHeap function that follows, converts an array A which stores a complete binary tree with n nodes to a maxheap by repeatedly using MaxHeapify in a bottom up manner. It is based on the observation that the array elements indexed by floor(n/2) + 1, floor(n/2) + 2, ..., n are all leaves for the tree (assuming that indices start at 1), thus each is a oneelement heap.
→ BuildMaxHeap runs MaxHeapify on each of the remaining tree nodes.
// Input: A: an (unsorted) array
// Output: A modified to represent a heap.
// Running Time: O(n) where n = length[A]
1 heapsize[A] ← length[A]
2 for i ← Floor(length[A]/2) downto 1
3 MaxHeapify(A, i)
The BuildMaxHeap function that follows, converts an array A which stores a complete binary tree with n nodes to a maxheap by repeatedly using MaxHeapify in a bottom up manner. It is based on the observation that the array elements indexed by floor(n/2) + 1, floor(n/2) + 2, ..., n are all leaves for the tree (assuming that indices start at 1), thus each is a oneelement heap.
→ BuildMaxHeap runs MaxHeapify on each of the remaining tree nodes.
Question 29 
The value of postfix expression :
8 3 4 + – 3 8 2 / + * 2 $ 3 + is
8 3 4 + – 3 8 2 / + * 2 $ 3 + is
17  
131  
64  
52 
Question 29 Explanation:
Question 30 
Consider the following statements for priority queue :
S1 : It is a data structure in which the intrinsic ordering of the elements does determine the result of its basic operations.
S2 : The elements of a priority queue may be complex structures that are ordered on one or several fields.
Which of the following is correct ?
S1 : It is a data structure in which the intrinsic ordering of the elements does determine the result of its basic operations.
S2 : The elements of a priority queue may be complex structures that are ordered on one or several fields.
Which of the following is correct ?
Both S1 and S2 are incorrect.  
S1 is correct and S2 is incorrect.  
S1 is incorrect and S2 is correct.  
Both S1 and S2 are correct 
Question 30 Explanation:
S1: TRUE: It is a data structure in which the intrinsic ordering of the elements does determine the result of its basic operations.
S2: TRUE: The elements of a priority queue may be complex structures that are ordered on one or several fields.
S2: TRUE: The elements of a priority queue may be complex structures that are ordered on one or several fields.
Question 31 
Repository of information gathered from multiple sources, storing under unified scheme at a single site is called as
Data mining  
Meta data  
Data warehousing  
Database 
Question 31 Explanation:
→ Repository of information gathered from multiple sources, storing under unified scheme at a single site is called as Data Warehousing.
→ Data warehousing will support OLAP and OLTP.
→ Business intelligence and Data warehousing is used for forecasting and Data mining.
→ Business intelligence and Data warehousing is used for analysis of large volumes of sales data.
→ The Data warehouse Hadoop cluster at Facebook has become the largest known Hadoop storage cluster in the world.
→ Data warehousing will support OLAP and OLTP.
→ Business intelligence and Data warehousing is used for forecasting and Data mining.
→ Business intelligence and Data warehousing is used for analysis of large volumes of sales data.
→ The Data warehouse Hadoop cluster at Facebook has become the largest known Hadoop storage cluster in the world.
Question 32 
The task of correcting and preprocessing data is called as
Data streaming  
Data cleaning  
Data mining  
Data storming 
Question 32 Explanation:
→ Data cleansing or data cleaning is the process of detecting and correcting (or removing) corrupt or inaccurate records from a record set, table, or database and refers to identifying incomplete, incorrect, inaccurate or irrelevant parts of the data and then replacing, modifying, or deleting the dirty or coarse data.
→ Data cleansing may be performed interactively with data wrangling tools, or as batch processing through scripting.
→ Data cleansing may be performed interactively with data wrangling tools, or as batch processing through scripting.
Question 33 
Using data p=3, q=11, n=pq, d=7 in RSA algorithm find the cipher text of the given plain text SUZANNE
BUTAEEZ  
SUZANNE  
XYZABCD  
ABCDXYZ 
Question 33 Explanation:
n = p*q = 33,
Φ = (p1)*(q1) = 20,
d = 7 and e = 3 (solve by e*d = 1 mod 20)
Message M= SUZANNE
Here take A = 1, B = 2, C = 3 ….. Z = 26, A = 27, …...
Cipher text = (M^{e} mod n)
⇒ S = 19, Cipher = 19^{3 }mod 33 = 28 = B
⇒ U = 21, Cipher = 21^{3} mod 33 = 21 = U
and so on ..
Φ = (p1)*(q1) = 20,
d = 7 and e = 3 (solve by e*d = 1 mod 20)
Message M= SUZANNE
Here take A = 1, B = 2, C = 3 ….. Z = 26, A = 27, …...
Cipher text = (M^{e} mod n)
⇒ S = 19, Cipher = 19^{3 }mod 33 = 28 = B
⇒ U = 21, Cipher = 21^{3} mod 33 = 21 = U
and so on ..
Question 34 
The relation “divides” on a set of positive integers is ________.
Symmetric and transitive  
Anti symmetric and transitive  
Symmetric only  
Transitive only 
Question 34 Explanation:
The relation “divides” on a set of positive integers is Anti symmetric and Transitive.
Proof:
Let assume a,b two set elements.
The relation is antisymmetric if and only if for every a,b in the set.
IF(a∣b AND b∣a), then it must follow that a=b.
→ If it's FALSE then both a∣b AND b∣a, then it's perfectly consistent to have a≠b.
→ The only time a∣b AND b∣a is exactly when a=b, since then we have a∣b ⟺ a∣a is TRUE for all a.
Hence the relation is antisymmetric.
Proof:
Let assume a,b two set elements.
The relation is antisymmetric if and only if for every a,b in the set.
IF(a∣b AND b∣a), then it must follow that a=b.
→ If it's FALSE then both a∣b AND b∣a, then it's perfectly consistent to have a≠b.
→ The only time a∣b AND b∣a is exactly when a=b, since then we have a∣b ⟺ a∣a is TRUE for all a.
Hence the relation is antisymmetric.
Question 35 
Give as good a big–O estimate as possible for the following functions :
(nlogn+n^{2})(n^{3}+2) and (n!+2^{n})(n^{3}+log(n^{2}+1))
O(n^{5}+2n^{2}) & O(n^{3}*n!)  
O(n^{5}) & O(n^{3}*2^{n})  
O(n^{5}) & O(n^{3}* n!)  
O(n^{5}+2n^{2}) & O(n^{3}*2^{n}) 
Question 35 Explanation:
Step1: Consider first function (nlogn+n^{2})(n^{3}+2).
Here, It is performing multiplication of 2 polynomials.
(nlogn+n^{2}) → Raising value is n^{2}. We can write asymptotically O(n^{2})
(n^{3}+2) → Raising value is n^{3}. We can write asymptotically O(n^{3})
= O(n^{2})*O(n^{3})
= O(n^{5})
Step2: Second function (n!+2^{n})(n^{3}+log(n^{2}+1))
Here, It is performing multiplication of 2 polynomials.
(n!+2^{n}) → Raising value is n!. We can write asymptotically O(n!)
(n^{3}+log(n^{2}+1)) → Raising value is n3. We can write asymptotically O(n^{3})
= O(n!)*O(n^{3})
= O(n^{3}* n!)
Here, It is performing multiplication of 2 polynomials.
(nlogn+n^{2}) → Raising value is n^{2}. We can write asymptotically O(n^{2})
(n^{3}+2) → Raising value is n^{3}. We can write asymptotically O(n^{3})
= O(n^{2})*O(n^{3})
= O(n^{5})
Step2: Second function (n!+2^{n})(n^{3}+log(n^{2}+1))
Here, It is performing multiplication of 2 polynomials.
(n!+2^{n}) → Raising value is n!. We can write asymptotically O(n!)
(n^{3}+log(n^{2}+1)) → Raising value is n3. We can write asymptotically O(n^{3})
= O(n!)*O(n^{3})
= O(n^{3}* n!)
Question 36 
A test contains 100 true/false questions. How many different ways can a student answer the questions on the test, if the answer may be left blank also.
^{100}P_{2}  
^{100}C_{2}  
2^{100}  
3^{100} 
Question 36 Explanation:
Given data,
 Total number of questions=100
 Total possibilities for each question=3 (Note: BLANK or TRUE or FALSE)
Step1: 1 question= 3 possibilities.
 Total number of questions=100
 Total possibilities for each question=3 (Note: BLANK or TRUE or FALSE)
Step1: 1 question= 3 possibilities.
Question 37 
Which of the following connected simple graph has exactly one spanning tree ?
Complete graph  
Hamiltonian graph  
Euler graph  
None of the above 
Question 37 Explanation:
→ Complete graph have n^{n2} spanning trees.
→ Hamiltonian graph will get more than one spanning tree.
→ Euler graph will get more than one spanning tree.
→ Hamiltonian graph will get more than one spanning tree.
→ Euler graph will get more than one spanning tree.
Question 38 
How many edges must be removed to produce the spanning forest of a graph with N vertices, M edges and C connected components ?
M+N–C  
M–N–C  
M–N+C  
M+N+C 
Question 38 Explanation:
→ Spanning forest is nothing but a set of spanning trees, one for each connected component in the graph
→ In the spanning forest the components are represented by a set of edges, rather than a set of vertices. Any vertices in the graph that are entirely unconnected will not appear in the spanning forest.
→ In spanning forest, we will use multiple trees to represent a path through the graph.
→ Consider the below example
Number of components(C)=3
Number of vertices(N)=9
Number of Edges(M)=8
By removing two edges, we can make spanning forest in the above graph.
The number of edges can be removed to make spanning forest is MN+C=89+3=2
So option C is correct.
→ In the spanning forest the components are represented by a set of edges, rather than a set of vertices. Any vertices in the graph that are entirely unconnected will not appear in the spanning forest.
→ In spanning forest, we will use multiple trees to represent a path through the graph.
→ Consider the below example
Number of components(C)=3
Number of vertices(N)=9
Number of Edges(M)=8
By removing two edges, we can make spanning forest in the above graph.
The number of edges can be removed to make spanning forest is MN+C=89+3=2
So option C is correct.
Question 39 
Which of the following shall be a compound proposition involving the propositions p, q and r, that is true when exactly two of the p, q and r are true and is false otherwise
(p ∨ q ∧ ⌐r) ∨ ( p ∧ q ∧ r) ∧ (⌐p ∧ q ∨ r)  
(p ∧ q ∨ r) ∧ ( p ∧ q ∧ r) ∨ (⌐q ∧ ⌐p∧ ⌐r)  
(p ∧ q ∧⌐ r) ∨ ( p ∧ ⌐q ∧ r) ∨ (⌐ p ∧ q ∧ r)  
(p ∨ r ∧ q) ∨ ( p ∧ q ∧ r) ∨ (⌐p ∧ q ∧ r) 
Question 39 Explanation:
From the question, the propositions consists of exactly two of the variables should true and final proposition should be true.
Only option C consists of exactly two of the variables are true and all remaining variables deviating this rule.
In this proposition, (p ∧ q ∧⌐ r) ∨ ( p ∧ ⌐q ∧ r) ∨ (⌐ p ∧ q ∧ r)
(p ∧ q ∧⌐ r) → p and q are true
( p ∧ ⌐q ∧ r) → p and r are true
(⌐ p ∧ q ∧ r) → q and r are true
Finally the proposition consists of “V” operation , so the entire proposition is true.
Only option C consists of exactly two of the variables are true and all remaining variables deviating this rule.
In this proposition, (p ∧ q ∧⌐ r) ∨ ( p ∧ ⌐q ∧ r) ∨ (⌐ p ∧ q ∧ r)
(p ∧ q ∧⌐ r) → p and q are true
( p ∧ ⌐q ∧ r) → p and r are true
(⌐ p ∧ q ∧ r) → q and r are true
Finally the proposition consists of “V” operation , so the entire proposition is true.
Question 40 
The truth value of the statements :
∃!xP(x) → ∃xP(x) and ∃!x ⌐P(x) →⌐∀xP(x), (where the notation ∃!xP(x)
denotes the proposition “There exists a unique x such that P(x) is true”) are :
True and False  
False and True  
False and False  
True and True 
Question 40 Explanation:
From the given question,
→ The symbol ∃ is call the existential quantifier and represents the phrase “there exists” or “for some”. The existential quantification of P(x) is the statement “P(x) for some values x in the universe”, or equivalently, “There exists a value for x such that P(x) is true”, which is written ∃xP(x). So the statement ∃!xP(x) → ∃xP(x) is true.
→ If P(x) is true for at least one element in the domain, then ∃xP(x) is true. Otherwise it is false.
→ Accordingly DeMorgan’s laws for quantifiers:the following statements are true.
¬∀xP(x) ≡ ∃x¬P(x)
¬∃xP(x) ≡ ∀x¬P(x) then the statement is ∃!x ⌐P(x) →⌐∀xP(x) is true.
→ If P(x) is true for at least one element in the domain, then ∃xP(x) is true. Otherwise it is false.
→ Accordingly DeMorgan’s laws for quantifiers:the following statements are true.
¬∀xP(x) ≡ ∃x¬P(x)
¬∃xP(x) ≡ ∀x¬P(x) then the statement is ∃!x ⌐P(x) →⌐∀xP(x) is true.
Question 41 
How many different Boolean functions of degree 4 are there ?
2^{4}  
2^{8}
 
2^{12}  
2^{16} 
Question 41 Explanation:
Boolean functions of n variables, there are 2^{2n} different Boolean functions on n Boolean variables.
Question 42 
A Boolean operator Ɵ is defined as follows :
1 Ɵ 1 = 1,
1 Ɵ 0 = 0,
0 Ɵ 1 = 0,
0 Ɵ 0 = 1
What will be the truth value of the expression (x Ɵ y) Ɵ z = x Ɵ (y Ɵ z) ?
1 Ɵ 1 = 1,
1 Ɵ 0 = 0,
0 Ɵ 1 = 0,
0 Ɵ 0 = 1
What will be the truth value of the expression (x Ɵ y) Ɵ z = x Ɵ (y Ɵ z) ?
Always false  
Always true  
Sometimes true  
True when x, y, z are all true 
Question 42 Explanation:
They given XNOR property for Ɵ.
Question 43 
Which one of the following is decimal value of a signed binary number 1101010, if it is in 2’s complement form ?
42  
22  
21  
106 
Question 43 Explanation:
Step1: 2's complement number are weighted number. So,
1101010= 1*(0.26) + 1*25 + 1*23 + 1*21
= 64 + 32 +8 +2
= 22
Hence (1101010)=(22) in 2's complement form
Question 44 
A set of processors P1, P2, ……, Pk can execute in parallel if Bernstein’s conditions are satisfied on a pairwise basis; that is
P1  P2  P3  …..  Pk if and only if :
Pi  Pj for all i ≠ j  
Pi  Pj for all i = j+1  
Pi  Pj for all i ≤ j  
Pi  Pj for all i ≥ j 
Question 44 Explanation:
Bernstein’s conditions for parallelism:
Define:
I_{i} as the input set of a process P_{i}
O_{i }as the output set of a process P_{i}
P_{1 }and P_{2} can execute in parallel (denoted as P_{1}  P_{2}) under the condition:
I_{1} ∩ O_{2} = 0
I_{2} ∩ O_{1} = 0
O_{1} ∩ O_{2} = 0
Note that I_{1} ∩ I_{2} <> 0 does not prevent parallelism.
Input set: also called read set or domain of a process
Output set: also called write set or range of a process
A set of processes can execute in parallel if Bernstein’s conditions are satisfied on a pairwise basis; that is, P_{1}  P_{2}  …  P_{K} if and only if P_{i}  P_{j} for all i<>j
The parallelism relation is commutative: Pi  Pj implies that Pj  Pi
The relation is not transitive: Pi  Pj and Pj  Pk do not necessarily mean Pi  Pk
Associativity: Pi  Pj  Pk implies that (Pi  Pj)  Pk = Pi  (Pj  Pk)
For n processes, there are 3n(n1)/2 conditions; violation of any of them prohibits parallelism collectively or partially
Statements or processes which depend on runtime conditions are not transformed to parallelism. (IF or conditional branches)
The analysis of dependences can be conducted at code, subroutine, process, task, and program levels; higherlevel dependence can be inferred from that of subordinate levels.
Define:
I_{i} as the input set of a process P_{i}
O_{i }as the output set of a process P_{i}
P_{1 }and P_{2} can execute in parallel (denoted as P_{1}  P_{2}) under the condition:
I_{1} ∩ O_{2} = 0
I_{2} ∩ O_{1} = 0
O_{1} ∩ O_{2} = 0
Note that I_{1} ∩ I_{2} <> 0 does not prevent parallelism.
Input set: also called read set or domain of a process
Output set: also called write set or range of a process
A set of processes can execute in parallel if Bernstein’s conditions are satisfied on a pairwise basis; that is, P_{1}  P_{2}  …  P_{K} if and only if P_{i}  P_{j} for all i<>j
The parallelism relation is commutative: Pi  Pj implies that Pj  Pi
The relation is not transitive: Pi  Pj and Pj  Pk do not necessarily mean Pi  Pk
Associativity: Pi  Pj  Pk implies that (Pi  Pj)  Pk = Pi  (Pj  Pk)
For n processes, there are 3n(n1)/2 conditions; violation of any of them prohibits parallelism collectively or partially
Statements or processes which depend on runtime conditions are not transformed to parallelism. (IF or conditional branches)
The analysis of dependences can be conducted at code, subroutine, process, task, and program levels; higherlevel dependence can be inferred from that of subordinate levels.
Question 45 
When a mobile telephone physically moves from one to another cell, the base station transfers ownership to the cell getting strongest signal. This process is known as _______.
handoff  
mobile switching  
mobile routing  
cell switching 
Question 45 Explanation:
→ When a mobile telephone physically moves from one to another cell, the base station transfers ownership to the cell getting strongest signal. This process is known as handoff.
→ Hard handover (or) Hard Handoff: Early systems used hard handoff. In a hard handoff, a mobile station only communicates with one base station. When the MS moves from one cell to another, communication must first be broken with the previous base station before communication can be established with the new one.
→ Soft handover (or) Soft Handoff: New systems use a soft Handoff. In this case, a mobile station can communicate with base stations at the same time. This means that, during handoff, a mobile station may continue with the new base station before breaking off from the old one.
→ Hard handover (or) Hard Handoff: Early systems used hard handoff. In a hard handoff, a mobile station only communicates with one base station. When the MS moves from one cell to another, communication must first be broken with the previous base station before communication can be established with the new one.
→ Soft handover (or) Soft Handoff: New systems use a soft Handoff. In this case, a mobile station can communicate with base stations at the same time. This means that, during handoff, a mobile station may continue with the new base station before breaking off from the old one.
Question 46 
A virtual memory based memory management algorithm partially swaps out a process. This is an example of
short term scheduling  
long term scheduling  
medium term scheduling  
mutual exclusion 
Question 46 Explanation:
A virtual memory based memory management algorithm partially swaps out a process. This is an example of medium term scheduling.
Mediumterm scheduling:The decision to add to the number of processes that are partially or fully in main memory.
Longterm scheduling:The decision to add to the pool of processes to be executed.
Shortterm scheduling:The decision as to which available process will be executed by the processor.
Mediumterm scheduling:The decision to add to the number of processes that are partially or fully in main memory.
Longterm scheduling:The decision to add to the pool of processes to be executed.
Shortterm scheduling:The decision as to which available process will be executed by the processor.
Question 47 
Assuming that the disk head is located initially at 32, find the number of disk moves required with FCFS if the disk queue of I/O block requests are 98, 37, 14, 124, 65, 67 :
310  
324  
320  
321 
Question 47 Explanation:
= 66 + 61 + 23 + 110 + 59 + 2
= 321
Question 48 
Let the page fault service time be 10 millisecond(ms) in a computer with average memory access time being 20 nanosecond(ns). If one page fault is generated for every 10^{6} memory accesses, what is the effective access time for memory ?
21 ns  
23 ns  
30 ns  
35 ns 
Question 48 Explanation:
P=page fault rate
EA = p*page fault service time + (1p) * Memory access time
=1/10^{6}*10*10^{6}+(11/10^{6})*20
≅ 29.9 ns
EA = p*page fault service time + (1p) * Memory access time
=1/10^{6}*10*10^{6}+(11/10^{6})*20
≅ 29.9 ns
Question 49 
Consider the following UNIX command :
sort <in> temp; head – 30 <temp; rm temp Which of the following functions shall be performed by this command ?
sort <in> temp; head – 30 <temp; rm temp Which of the following functions shall be performed by this command ?
Sort, taking the input from“temp”, prints 30 lines from temp and delete the file temp  
Sort the file “temp”, removes 30 lines from temp and delete the file temp  
Sort, taking the input from “in” and writing the output to“temp” then prints 30 lines
from temp on terminal. Finally “temp” is removed.
 
Sort, taking the input from “temp” and then prints 30 lines from “temp” on terminal.
Finally “temp” is removed

Question 49 Explanation:
sort temp; → Sort, taking the input from “in” and writing the output to“temp”
head – 30
rm temp→ “temp” is removed.
head – 30
Question 50 
The ‘mv’ command changes
the inode  
the inodenumber  
the directory entry  
both the directory entry and the inode 
Question 50 Explanation:
mv (short for move) is a Unix command that moves one or more files or directories from one place to another. If both filenames are on the same filesystem, this results in a simple file rename; otherwise the file content is copied to the new location and the old file is removed.
There are 50 questions to complete.