HCU PHD CS MAY 2014
Question 1 
One way of showing that one string is equal to another string is to compare and match them character by character. What happens if we allow both the strings to be of infinite length?
The method fails because we can only show that the two strings are not equal.
 
The method fails because we can only show that the two strings are equal.  
The method works correctly and tells if the strings are equal or not.  
The method works only if the strings are numeric. 
Question 2 
In the C Programming Language, arrays can be defined in two ways. The first is static: int a[4000] [3000];
the second is dynamic: declare as int **a;
and then allocate memory using malloc() . Which of the following is TRUE?
In the first case, memory is contiguous while in the second case, memory is not contiguous.
 
In the first case, elements may be accessed as a[i] [j], while in the second, they cannot be accessed so.  
In the first case, the array elements are stored in rowmajor order, while in the second they are stored in columnmajor order.  
None of the above. 
Question 2 Explanation:
In the first case the array is contiguoaus while in the second case array is not contiguos because in the second case the declaration is array of ponters to pointers.
Question 3 
If flexibility is defined as having maximum choice in cache placement, which of the following is correctly ordered in ascending order of flexibility?
Direct Mapping, SetAssociative Mapping, Associative Mapping  
SetAssociative Mapping, Direct Mapping, Associative Mapping  
Associative Mapping, SetAssociative Mapping, Direct Mapping
 
None of the above. 
Question 3 Explanation:
In direct mapping only choice is there.
In set associative mapping of set size k,there are k choices.
While in associative mapping the choice is any block of cache.
Hence ascending order of flexibility is ,
Direct mapping , Set associative Mapping, Associative mapping.
In set associative mapping of set size k,there are k choices.
While in associative mapping the choice is any block of cache.
Hence ascending order of flexibility is ,
Direct mapping , Set associative Mapping, Associative mapping.
Question 4 
Heap sort may be considered as
Insertion sort done on a heap data structure instead of a list.  
Selection sort done on a heap data structure instead of a list.  
Bubble sort done on a heap data structure instead of a list.  
None of the above. 
Question 4 Explanation:
When we do min or max heapify in heap sort, we get the min or max element in the root then we exchange it with the last element. And we repeat the procedure for the remaining element .
We do similar type in selection sort,we find min or max element and then we exchange that element with first element and we repeat the element with the remaining procedure .
We do similar type in selection sort,we find min or max element and then we exchange that element with first element and we repeat the element with the remaining procedure .
Question 5 
Which of the following is NOT a feature of the Von Neumann architecture?
Storage space for programs.  
Storage space for data  
Unique next instruction for execution.  
Separating instructions from data. 
Question 6 
The correct result of Lexicographically sorting
109, 20, 119, 2,207, 27, 19
in ascending order is:
19, 109, 119, 2, 20, 27, 207  
109, 119, 19, 2,20,27,207  
109, 119, 19, 2,20,207,27  
2, 19, 20, 27, 109, 119 , 207 
Question 6 Explanation:
Lexicographical sorting of numbers is similar to the Lexicographical sorting of words in a dictionary.
So the correct answer is,
109,119,19,2,20,207,27
So the correct answer is,
109,119,19,2,20,207,27
Question 7 
All IP addresses in the range 186.220.64.0 to 186.220.71.254 are kept in a VLAN.
The correct netmask so that messages are broadcast only within this VLAN is
186.220.255.255  
186.220.248.0  
186.220.248.0  
186.220.8.0 
Question 7 Explanation:
We have to select such subnet mask by which ANDing the both IP address we get the same network ID.
And option D gives same network ID after ANDing .The network ID we get is 186.220.0.0
Question 8 
Which sentence can be generated by: S → aS  bA, A → d  ccA
aadb  
bccddd  
aabccd  
None of the above 
Question 8 Explanation:
S ⟶ aS
⟶ aaS (∵ S ⟶ aS)
⟶ aabA (∵ S ⟶ bA)
⟶ aabccA (∵ A ⟶ ccA)
⟶ aabccd (∵ A ⟶ d)
⟶ aaS (∵ S ⟶ aS)
⟶ aabA (∵ S ⟶ bA)
⟶ aabccA (∵ A ⟶ ccA)
⟶ aabccd (∵ A ⟶ d)
Question 9 
Which sort uses features of the key to operate in Linear time relative to the number
of elements in the array?
Quick Sort  
Merge Sort  
Radix Sort  
Bubble Sort 
Question 9 Explanation:
Examples of sorting algorithms that run in linear time are counting sort, radix sort and bucket sort. Counting sort and radix sort assume that the input consists of integers in a small range.
Question 10 
Convert FAFAFA in hexadecimal into octal.
76767676  
76737672  
76727672  
76575372 
Question 10 Explanation:
Hexadecimal number consists of 4 bit binary no. An octal number is comprising of 3 bit binary no.
So first we will convert the Hexadecimal number into binary no. and then by taking each 3 bit from right side we will convert it into octal no.
So first we will convert the Hexadecimal number into binary no. and then by taking each 3 bit from right side we will convert it into octal no.
Question 11 
Which of the following decision procedures does NOT have exponential time complexity?
Graphcolouring Problem  
Travelling Salesperson Problem  
Hamiltonian Circuit Problem  
Linear Programming Problem 
Question 12 
Simplify the following boolean expression: 2xyz' + xy'z' + x'yz'?
xy + y'z' + x'y  
xy + xz' + x'z'  
(y + z')x  
(x + y)z' 
Question 12 Explanation:
2xyz’ + xy’z’ + x’yz’
= xyz’ + xyz’ + xy’z’ + x’yz’
= xyz’ + x’yz’ + xyz’ + xy’z’
= yz’ (x + x’) + xz’ (y + y’)
= yz’ + xz’
= z’(y + x)
= xyz’ + xyz’ + xy’z’ + x’yz’
= xyz’ + x’yz’ + xyz’ + xy’z’
= yz’ (x + x’) + xz’ (y + y’)
= yz’ + xz’
= z’(y + x)
Question 13 
Which of the following problems is solvable?
Determining if a universal Turing machine and some input will halt  
Writing a universal Turing machine  
Determining if a universal Turing machine can be written in fewer than k instructions for some k  
Determining if an arbitrary Turing machine is a universal Turing machine 
Question 13 Explanation:
Universal Turing Machine is a machine which can simulate the work of other turing machine.Also universal TM can accept any other machine's input other than itself.
Now lets check option wise,
A) It is the halting problem of turing machine which is undecidable.
B) Universal turing machine cannot recognize its own action,so undecidable.
C) By rice’s theorem it is undecidable.
D) If a TM can simulate the work of any other TM, then it will be UTM. Here definite "yes" and "no" ans possible. So, will be decidable
Now lets check option wise,
A) It is the halting problem of turing machine which is undecidable.
B) Universal turing machine cannot recognize its own action,so undecidable.
C) By rice’s theorem it is undecidable.
D) If a TM can simulate the work of any other TM, then it will be UTM. Here definite "yes" and "no" ans possible. So, will be decidable
Question 14 
How many possible bytes have exactly three bits on (i.e., bit=true)?
8*7  
8*7*6  
8*3
 
None of the above 
Question 15 
What is the value of F(4) using the following procedure?
function F(k: integer) : integer;
begin
if (k<3) then F:=k
else F := F(k1)*f(k2)+F(k3);
end;
5  
6  
7  
8 
Question 15 Explanation:
Question 16 
Queues serve a major role in:
simulation of recursion  
simulation of arbitrary linked lists  
expression evaluation  
simulation of limited resource allocation 
Question 16 Explanation:
Queues serve a major role in simulation of limited resource allocation .
Stack serves major role in simulation of recursion and expression evaluation.
Stack serves major role in simulation of recursion and expression evaluation.
Question 17 
What is True for a complete bipartite graph K(3,3)?
it is a planar graph  
it requires three colours to be minimally coloured  
it is nonplanar  
it is isomorphic to K(2,4) 
Question 17 Explanation:
The graph K(5) and K(3,3) are two of the most important graphs within the subject of planarity in graph theory.Kuratowski’s theorem tells us that if we can find the subgraph in any graph that is homeomorphic to K(5) or K(3,3) then the graph is not planar,meaning its not possible for the edges to be redrawn such that they are none overlapping. Of course this theorem relies on the fact that K(5) and K(3,3) are themselves are not planar.
Question 18 
A complete binary tree of level 5 has how many nodes?
15  
63  
25  
71  
None of the above 
Question 18 Explanation:
Tree with 5 levels of nodes has height 4. So the no. of nodes in a complete binary tree is of height 4 is
2^(4+1)  1 = 2^5  1 = 31
2^(4+1)  1 = 2^5  1 = 31
Question 19 
In the following Karnaugh map with don't care states, which values of X and Y would minimize the final function's expression length?
0 0 X 0
0 1 1 0
1 Y 1 0
0 0 0 0
X=0, Y=0  
X=0, Y=1  
X=1, Y=0  
X=1, Y=1 
Question 19 Explanation:
Question 20 
The grammar G=<{S},{0,1},P,S>, where P={S→ SS, S→ 0S1, S→ 1S0, S→ empty} will generate a:
Contextfree language  
Contextsensitive language  
Regular language  
Recursively enumerable language 
Question 20 Explanation:
The given grammar generates the language which generates strings having
No. of 0’s = no. of 1’s
Which is context free language.
No. of 0’s = no. of 1’s
Which is context free language.
Question 21 
In Question 20, the language generated is?
{0^{n}1^{n} where n ≥ 0}  
{0^{n}1^{n} where n ≥ 0} U {1^{n}0^{n} where n ≥ 0}  
{0^{m}1^{k} where m,k ≥ 0} U {1^{m}0^{k} where m,k ≥ 0}  
{W where W has an equal number of 0's and 1's} 
Question 21 Explanation:
The language generated by the grammar in Q.20 is
{w where w has an equal no. of 0’s and 1’s}
{w where w has an equal no. of 0’s and 1’s}
Question 22 
Answer Questions 22  25 using the following reading passage:
Since the Hawaiian Islands have never been connected to other land masses, the great variety of plants in Hawaii must be a result of the longdistance dispersal of seeds, a process that requires both a method of transport and an equivalence between the ecology of the source area and that of the recipient area.
There is some dispute about the method of transport involved. Some biologists argue that ocean and air currents are responsible for the transport of plant seeds to Hawaii. Yet the results of flotation experiments and the low temperatures of air currents cast doubt on these hypotheses. More probable is bird transport, either externally by accidental attachment of the seeds to feathers, or internally, by the
swallowing of fruit and subsequent excretion of the seeds. While it is likely that fewer varieties of plant seeds have reached Hawaii externally than internally more varieties are known to be adapted to external than to internal transport.
The author of the passage is mainly concerned with
discussing different approaches biologists have taken to testing theories about the distribution of plants in Hawaii  
discussing different theories about the transport of plant seeds to Hawaii  
discussing the extent to which air currents are responsible for the dispersal of plant seeds to Hawaii  
resolving a dispute about the adaptability of plant seeds to bird transport 
Question 23 
Answer Questions 22  25 using the following reading passage:
Since the Hawaiian Islands have never been connected to other land masses, the great variety of plants in Hawaii must be a result of the longdistance dispersal of seeds, a process that requires both a method of transport and an equivalence between the ecology of the source area and that of the recipient area.
There is some dispute about the method of transport involved. Some biologists argue that ocean and air currents are responsible for the transport of plant seeds to Hawaii. Yet the results of flotation experiments and the low temperatures of air currents cast doubt on these hypotheses. More probable is bird transport, either externally by accidental attachment of the seeds to feathers, or internally, by the
swallowing of fruit and subsequent excretion of the seeds. While it is likely that fewer varieties of plant seeds have reached Hawaii externally than internally more varieties are known to be adapted to external than to internal transport.
The author mentions
two methods of transport of seeds to Hawaii, namelg currents (ocean and air) and birds  
that Hawaiian ecology does not match with any other ecology of the world  
that the plant variety is due only to the ecology innate to Hawaii  
None of the above 
Question 24 
Answer Questions 22  25 using the following reading passage:
Since the Hawaiian Islands have never been connected to other land masses, the great variety of plants in Hawaii must be a result of the longdistance dispersal of seeds, a process that requires both a method of transport and an equivalence between the ecology of the source area and that of the recipient area.
There is some dispute about the method of transport involved. Some biologists argue that ocean and air currents are responsible for the transport of plant seeds to Hawaii. Yet the results of flotation experiments and the low temperatures of air currents cast doubt on these hypotheses. More probable is bird transport, either externally by accidental attachment of the seeds to feathers, or internally, by the
swallowing of fruit and subsequent excretion of the seeds. While it is likely that fewer varieties of plant seeds have reached Hawaii externally than internally more varieties are known to be adapted to external than to internal transport.
The author asserts that
Hawaiian plant variety evolved independently from flora in other parts of the world  
birds can not carry plant seeds long distances  
bird transport happens more due to swallowing and subsequent excretion of seeds  
bird transport is more likely due to accidental attachment of the seeds to feathers 
Question 25 
Answer Questions 22  25 using the following reading passage:
Since the Hawaiian Islands have never been connected to other land masses, the great variety of plants in Hawaii must be a result of the longdistance dispersal of seeds, a process that requires both a method of transport and an equivalence between the ecology of the source area and that of the recipient area.
There is some dispute about the method of transport involved. Some biologists argue that ocean and air currents are responsible for the transport of plant seeds to Hawaii. Yet the results of flotation experiments and the low temperatures of air currents cast doubt on these hypotheses. More probable is bird transport, either externally by accidental attachment of the seeds to feathers, or internally, by the
swallowing of fruit and subsequent excretion of the seeds. While it is likely that fewer varieties of plant seeds have reached Hawaii externally than internally more varieties are known to be adapted to external than to internal transport.
The author mentions the results of flotation experiments on plant seed,most probably in order to
support the claim that the distribution of plants in Hawaii is the result of the longdistance dispersal of seeds  
lend credibility to the thesis that air currents provide a method of transport for plant seeds to Hawaii  
suggest that the longdistance dispersal of seeds is a process that requires long periods of time  
challenge the claim that ocean plant seeds to Hawaii currents are responsible for the transport of
Plants seed t Hawaii

Question 26 
Consider a schema R(A, B, C, D) and functional dependencies A→ B and C→ D. Then the decomposition of R into R1 (A, B) and R2(C, D) is
lossless join but not dependency preserving  
dependency preserving but not lossless join  
not dependency preserving and not lossless join  
part dependency preserving and lossless join 
Question 26 Explanation:
The given decomposition is not lossless join because there is no common attributes between R1 and R2.
But the given decomposition is dependency preserving, A→ B is covered by R1 and C→ D is covered by R2.
Question 27 
Given relations R(w, x) and S(y,z), the result of select distinct w, x from R, S is guaranteed to be same as R, Provided
R and S have no duplicates  
S has no duplicates and R is nonempty  
R and S have the same number of tuples  
R has no duplicates and S is nonempty 
Question 27 Explanation:
A)Lets assume that S is empty(no duplicates) and R is not empty then RXS will be empty which will not be equal to R.Hence false.
B)Same reason as (A) .Hence false.
C)Lets assume R has duplicates,in this case,due to distinct keyword those duplicates will get eliminated in final result and the output will not be same as R.Hence false.
D)True.From above all options explaination we can conclude this as the answer.
B)Same reason as (A) .Hence false.
C)Lets assume R has duplicates,in this case,due to distinct keyword those duplicates will get eliminated in final result and the output will not be same as R.Hence false.
D)True.From above all options explaination we can conclude this as the answer.
Question 28 
Suppose (A, B) and (C,D) are two relation schemas. Let r1 and r2 be the corresponding relation instances. B is a foreign key that refers to C in r2. If data in r1 and r2 satisfy referential integrity constraints, which of the following is ALWAYS TRUE?
π_{C}(r_{2})  π_{B}(r_{1}) = Ф  
π_{B}(r_{1}) π_{C}(r_{2}) = Ф  
π_{B}(r_{1})  π_{C}(r_{2}) ≠ Ф  
π_{B}(r_{1})  π_{C}(r_{2}) = Ф 
Question 28 Explanation:
Since B is the foreign key that refers C in r2. So the B will contain the values that will be definitely present in C and C might contain more different values. So for sure
π_{B}(r_{1}) π_{C}(r_{2}) = Ф
π_{B}(r_{1}) π_{C}(r_{2}) = Ф
Question 29 
Consider the following relations A, B, C. How many tuples does the result of the following relational algebra expression contain? Assume that the schema of A U B is the same as that of A.
7  
4  
5  
9 
Question 29 Explanation:
Question 30 
Consider the above tables A, B and C. How many tuples does the result of the following SQL query contains?
SELECT A.id
FROM A
WHERE A.age > ALL (SELECT B.age
FROM B
WHERE B.name  "Arun")
3  
0  
1  
4 
Question 30 Explanation:
All condition with empty return true
Also the result of subquery is empty So all id of A will be selected.
Also the result of subquery is empty So all id of A will be selected.
Question 31 
Relation R is decomposed using a set of functional dependencies, F, and relation S Is decomposed using another set of functional dependencies, G. One decomposition is definitely BCNF, the other is definitely 3NF, but it is not known which is which.
To make a guaranteed identification, which one of the following tests should be used on the decompositions? (Assume that the closure of F and G are available).
Losslessjoin  
BCNF definition  
3NF definition  
DependencyPreservation 
Question 31 Explanation:
Since one decomposition is in 3NF so it will not satisfy the BCNF conditions.Hence BCNF tests should be used on the decompositions.
Question 32 
Consider a table T in a relational database with a key field K. A Btree of order p is used as an access structure on K, where p denotes the maximum number of tree pointers in a Btree index node. Assume that K is 10 bytes long; disk block size is 512 Bytes; each data pointer D is 8 bytes long and each block pointer PB is 5 bytes long. In order for each Btree node to fit in a single disk block, the maximum value Of p is
22  
23  
32  
20 
Question 32 Explanation:
< img src="https://solutionsadda.in/wpcontent/uploads/2020/04/Screenshot_520.png">
Question 33 
A B+ tree index is to be built on the Name attribute of the relation STUDENT. Assume that all student names are of length 8 bytes, disk blocks are of size 512 bytes, and index pointers are of size 4 bytes. Given this scenario, what would be the best choice of the degree (i.e. the number of pointers per node) of the B+ tree?
42  
43  
44  
16 
Question 33 Explanation:
For B^{+} Tree (By default internal node)
Let the degree be p.
Let the index pointer be b.
Let the key value be k.
Let the degree be p.
Let the index pointer be b.
Let the key value be k.
Question 34 
Consider a hash table of size seven, with starting index zero, and a hash function (3x + 4) mod 7 . Assuming the hash table is initially empty which of the following is the contents of the table when the sequence 1, 3, 8, 10 is inserted into the table using closed hashing? Note that _ denotes an empty location in the table
1, 8, 10, _,_,_, 3  
1, _,_,_,_,_, 3  
1, 10, 8, _,_,_, 3  
1, _,_,_,_,_, 10 
Question 34 Explanation:
The elements to be inserted are,
1, 3, 8, 10
⟶ Insert 1,
(3 × 1 + 4) mod 7 = 0
1, 3, 8, 10
⟶ Insert 1,
(3 × 1 + 4) mod 7 = 0
Question 35 
Which of the following best describes source routing concept?
The source sends packets for next hop router for forwarding according to router's tables  
The source relies on OSPF optimal approach for finding the route to the destination from the OSPF routers  
A sequence of forwarding router's addresses is generated at source and enclosed in the IP packet header.  
None of the above. 
Question 36 
CSMA/CA is used in IEEE 802.11 series of standards. Which of the following is most appropriate to describe its function?
Set up medium access control using a token.  
Set up medium access control in which hosts may transmit on the same channel simultaneously.  
Establish a sequence of RTS and CTS packets to sense the channel utilisation.  
To reduce transmission errors in a network. 
Question 37 
To reduce transmission errors in a network.
A denialofservice attack  
The uncontrolled cycle of increased retransmissions due to dropped packets by routers  
A problem caused due to hacking of web servers  
The uncontrolled injection of packets into firewall 
Question 38 
Network Address Translation is mainly used for
Separation of host addresses from the outer network  
Finding the next host for forwarding packets from a domain  
To increase the speed of accessing the Internet  
Accessing a mail server 
Question 38 Explanation:
Network Address Translation allows a single device, such as a router, to act as an agent between the Internet (or "public network") and a local (or "private") network
Question 39 
Threeway handshake is used for
Dropping a TCP connection  
Reliable establishment of a connection in the Internet transport layer  
Multiplexing between three hosts on the same LAN  
Exchange of packets at data link layer 
Question 39 Explanation:
A threeway handshake is primarily used to create a TCP socket connection to reliably transmit data between devices
Question 40 
A DNS server is most useful for
Finding the address of a host given a text query  
Send an HTTP error message  
Send an ICMP error message  
Finding the address of the next forwarding router 
Question 40 Explanation:
DNS stands for Domain Name System. The main function of DNS is to translate domain names into IP Addresses, which computers can understand. It also provides a list of mail servers which accept Emails for each domain name.
Question 41 
TCP is often referred to as selfclocking because
TCP is often referred to as selfclocking because  
TCP allows special encoding of clock signal in packet body  
TCP uses acknowledgments to trigger increase in congestion window size
 
TCP allows for adjustment of time for retransmissions in packet networks 
Question 42 
To see that a sender's data may fit into the receiver's buffer, TCP adopts a method known as
Retransmission  
Dropping of Packets  
Congestion contro  
Flow control 
Question 42 Explanation:
Flow control is the process of managing the rate at which data is transmitted. Using flow control, a computer receiving data can signal that it is not ready to receive data. TCP provides a flow control mechanism using acknowledgements of TCP sequence numbers.
Question 43 
It is known that SMTP protocol uses only ASCII data. Which of the following allows for sending any kind of data?
MIME  
TIFF  
MIPS  
JPEG 
Question 43 Explanation:
MIME is a kind of add on or a supplementary protocol which allows nonASCII data to be sent through SMTP. It allows the users to exchange different kinds of data files on the Internet: audio, video, images, application programs as well.
Question 44 
Software consists of
Set of instructions + Operating System  
Programs + Documentation + Operating Procedures  
Programs + Hardware Manuals  
Set of programs

Question 44 Explanation:
System software consists of the operating system and utility programs that control a computer system and allow you to use a computer.
Question 45 
Project risk factor is considered in
Waterfall model  
Waterfall model  
Spiral model
 
Iterative enhancement model 
Question 45 Explanation:
Project risk factor is considered in Spiral model
Question 46 
The outcome of construction phase may be treated as
A. P
Product release  
Beta release  
Alpha release  
All of the above 
Question 47 
FAST stands for
Functional Application Specification Technique  
Facilitated Application Specification Technique  
Fast Application Specification Technique  
None of the above. 
Question 47 Explanation:
FAST stands for Facilitated Application Specification Technique
Question 48 
Which of the following is NOT a size measure for software?
LOC  
Function count  
Cyclomatic complexity  
Holstead's program length 
Question 48 Explanation:
Cyclomatic complexity is not a size measure for software,it is the part of white box testing.
Question 49 
The most desirable form of coupling is
Control coupling  
Data coupling  
Common coupling
 
Content coupling 
Question 49 Explanation:
Coupling between modules can be ranked in the order of strongest (least desirable) to weakest (most desirable) as follows: Content Coupling, Common Coupling, External Coupling, Control Coupling, Stamp Coupling, Data Coupling
Question 50 
For a function of n variables, boundary value analysis yields
4n + 2 test cases  
4n + 1 test cases  
n+4 test cases  
None of the above. 
Question 50 Explanation:
The basic idea of BVA is to use input variable values at their minimum, just above the minimum, a nominal value, just below their maximum and at their maximum. ... Thus, for a function of n variables, BVA yields (4n + 1) test cases.
Question 51 
The process of transforming a model into source code is
Forward engineering  
Reengineering  
Restructuring
 
Reverse engineering 
Question 51 Explanation:
The process of transforming a model into source code is Forward engineering.
Question 52 
Which of the following is NOT TRUE with respect to a simple graph?
Every fully connected graph is a tree  
Every minimally connected graph is a tree  
Every graph with n nodes and n1 edges is a tree  
Every connected graph with no cycles is a tree 
Question 52 Explanation:
A is false because fully connected graph or complete graph with more than 2 vertices is having cycles,But tree do not have cycles.
B is true.Tree is a connected graph with minimum no. of edges.
C is false because in this statement ‘connected’ word is not used ,so a graph with n vertices and n1 edges can have cycles if the graph is disconnected.
D is true.
B is true.Tree is a connected graph with minimum no. of edges.
C is false because in this statement ‘connected’ word is not used ,so a graph with n vertices and n1 edges can have cycles if the graph is disconnected.
D is true.
Question 53 
The number of substrings that can be obtained from a string of length n is
⩰ n!  
⩰ 2^{n}  
⩰ n^{2}  
⩰ n^{n} 
Question 53 Explanation:
Assuming in the string of length n,all alphabets are distincts.
No. of distinct strings of length 1 = n
No. of distinct strings of length 2 = n1
No. of distinct strings of length 3 = n2
:
:
No. of distinct strings of length n = 1
Hence total no. of substrings = n+(n1)+(n2)+.........+1
=n(n+1)/1 ⩰ n^2
No. of distinct strings of length 1 = n
No. of distinct strings of length 2 = n1
No. of distinct strings of length 3 = n2
:
:
No. of distinct strings of length n = 1
Hence total no. of substrings = n+(n1)+(n2)+.........+1
=n(n+1)/1 ⩰ n^2
Question 54 
When data to be sorted is larger than the main memory capacity ,which sorting algorithm would you prefer?
Heap sort  
Insertion sort  
Quick sort  
Merge sort 
Question 54 Explanation:
External sorting is a term for a class of sorting algorithms that can handle massive amounts of data. External sorting is required when the data being sorted do not fit into the main memory of a computing device (usually RAM) and instead they must reside in the slower external memory (usually a hard drive). External sorting typically uses a hybrid sortmerge strategy. In the sorting phase, chunks of data small enough to fit in main memory are read, sorted, and written out to a temporary file. In the merge phase, the sorted subfiles are combined into a single larger file.
One example of external sorting is the external merge sort algorithm, which sorts chunks that each fit in RAM, then merges the sorted chunks together. We first divide the file into runs such that the size of a run is small enough to fit into main memory. Then sort each run in main memory using merge sort sorting algorithm. Finally merge the resulting runs together into successively bigger runs, until the file is sorted.
One example of external sorting is the external merge sort algorithm, which sorts chunks that each fit in RAM, then merges the sorted chunks together. We first divide the file into runs such that the size of a run is small enough to fit into main memory. Then sort each run in main memory using merge sort sorting algorithm. Finally merge the resulting runs together into successively bigger runs, until the file is sorted.
Question 55 
VFAT, EXT2, EXT3 are examples of
File system types  
Hard disk formatting commands  
CPU architectures  
Instruction set design formats 
Question 55 Explanation:
Some examples of filesystems are FAT, NTFS for Windows/DOS, HFS for MAC OS etc. In Linux, the popular filesystems are ext2, ext3 and ext4 filesystems. Some other filesystems such as ReiserFS are also natively supported by Linux.
Question 56 
Which of the following is FALSE with respect to regular languages?
Regular languages form a subset of context free languages  
Some regular languages can be infinite  
Every finite language is regular  
Context free languages form a subset of regular languages 
Question 56 Explanation:
All regular languages are context free languages but the reverse is not true. Hence option D in false.
Question 57 
Putnam resource allocation model is based on
Putnam theory of software management  
Function points  
Norden/Rayleigh curve  
Bochm's observations on man 
Question 57 Explanation:
Created by Lawrence Putnam, Sr. the Putnam model describes the time and effort required to finish a software project of specified size. SLIM (Software LIfecycle Management) is the name given by Putnam to the proprietary suite of tools his company QSM, Inc. has developed based on his model.
Question 58 
Consider the five letters with percentage of occurrence in the text as a=35%, b= 20%, C=20%, d=15%, e=10%. If a binary tree is generated using Huffman code algorithm, with assigning 0 to every left edge and 1 to every right edge, then the code for letter e is:
10  
110  
111  
011  
None of the above 
Question 58 Explanation:
Question 59 
Which design paradigm is based on Principle of Optimality?
Divide and conquer  
Greedy technique  
Backtracking  
Dynamic Programming 
Question 59 Explanation:
Dynamic Programming is a paradigm of algorithm design in which an optimization problem is solved by a combination of achieving subproblem solutions and appearing to the "principle of optimality".
Question 60 
Given S1 : AAACCGTGAGTTATTCGTTCTAGAA and S2  CACCCCTAAGGTACCTTTGGTTC,
Longest Common Subsequence (LCS) is:
ACCTAGTACTTG  
ACCTAGTACGTTG  
ACCTAGTACTGTG
 
ACCTAGTACTTTG 
Question 61 
Consider the join of a relation R with relation ,S. If R has m tuples and S has n tuples, then the maximum size of join is:
mn  
m+1  
(m + n)/2
 
2(m + n) 
Question 61 Explanation:
For join the maximum size of join possible is m*n.
Question 62 
If text T is of size n and pattern P of size m then the KnuthMorrisPratt Algorithm for pattern matching runs in time
O(m^{2} + n)
 
O(n log_{2} n)  
O(m+n)  
O(m^{n}) 
Question 62 Explanation:
Time complexity of KnuthMorrisPratt Algorithm is O(m+n).
Question 63 
The BigOh estimate for an algorithm that takes 8n log n + 4n^(3/2) steps is
O(n log n)  
O(n^{3/2})
 
O(n)  
None of the above 
Question 63 Explanation:
n^(3/2) is greater than nlogn. Hence the correct answer is B.
Question 64 
Which command is used to remove an index from the database in SQL?
DROP INDEX  
REMOVE INDEX
 
ROLL BACK INDEX  
DELETE INDEX 
Question 64 Explanation:
The DROP INDEX command is used to delete an index in a table.
Question 65 
A relational scheme is in ...... if it is in 1NF and if aII non prime attributes are fully functionally dependent on the relation key
Second Normal Form  
Boyce Codd Normal Form  
Fourth Normal Form  
First Normal Form 
Question 65 Explanation:
If a relation schema is in 1NF and if aII non prime attributes are fully functionally dependent on the relation key then the relation schema is in 2NF, because the condition for the relation to be in 2NF is that ,non prime attributes should not be partially functionally dependent on key.
Question 66 
A binary tree has n leaf nodes. The number of nodes of degree 2 in this tree is?
n1  
n  
2^{n}  
log_{2}n 
Question 66 Explanation:
If the binary tree has n nodes then no. of nodes of degree 2 in this tree is n1.Take some examples and check it.
Question 67 
A database trigger is:
A statement that is executed by user when debugging an application program  
A condition the system tests for the validity of the database user  
A statement that is executed automatically by the system as a side effect of modification on the database  
A statement that enables to start any DBMS 
Question 67 Explanation:
A database trigger is procedural code that is automatically executed in response to certain events on a particular table or view in a database. The trigger is mostly used for maintaining the integrity of the information on the database.
Question 68 
The natural join is equal to :
Combination of Union and Cartesian product  
Combination of selection and Cartesian product  
Combination of projection and Cartesian product  
Cartesian Product 
Question 69 
Consider the following multiplicative loop of some program. What is the running time of this loop in terms of bigoh notations:
m :=1;
for i:= 1 to n do begin
m:= m * 3;
for j:= 1 to m do
{ Something that is O(1) }
end;
O(n*m^{3})  
O(n^{3})  
O(3^{n})
 
O(3^{m}) 
Question 69 Explanation:
When i=1, j runs 3 times
When i=2, j runs 3^{2 }times
When i=3, j runs 3^{3} times
⋮
When i=n, j runs 3^{n} times
When i=2, j runs 3^{2 }times
When i=3, j runs 3^{3} times
⋮
When i=n, j runs 3^{n} times
Question 70 
A logical schema is
standard way of organizing information into accessible parts  
depends on physical storage  
describes how data is actually stored on the disk  
the entire database 
Question 70 Explanation:
Physical schema will deal with the how the data are stored on disk
Logical scheme ,deal with relation and how data are organized.
Question 71 
Which one is a virtual table that draws its data from the result of an SQL SELECT statement.
Synonym  
View  
Transaction  
Sequence 
Question 71 Explanation:
Views in SQL are kind of virtual tables. A view also has rows and columns as they are in a real table in the database. We can create a view by selecting fields from one or more tables present in the database. A View can either have all the rows of a table or specific rows based on certain condition.
Question 72 
A Btree of order m has maximum of ...... children
m+l  
m1  
m/2  
m 
Question 72 Explanation:
A B tree of order m has maximum of m children and m1 keys.
Question 73 
If Cache Size is 64KB, Block size is 32B and the cache is TwoWay Set Associative. For a 32bit physical address, the division between Block Offset, Index and Tag are:
10 bits, 10 bits, 10 bits  
17 bits, 32 bits, 16 bits  
32 bits, 64 bits, 22 bits
 
5 bits, 10 bits , 17 bits 
Question 73 Explanation:
The structure of 32 bit address will be like,
∴ Tag field bits = 32  (10 + 5) = 17
∴ Tag field bits = 32  (10 + 5) = 17
Question 74 
RAID is used for
Fault tolerance and Performance in multiple disks  
Used for generating speed of data access  
Resource sharing tool  
Rotating disks for access 
Question 74 Explanation:
RAID is Redundant Array of Independent Disk. In this the data is stored in multiple disk to deal with fault tolerance.
Question 75 
When a process is created using fork(), what is shared between parent process and
child process?
Stack  
Code segments  
I/O handles  
Heap 
Question 75 Explanation:
Only the shared memory segments are shared between the parent process and the newly forked child process.And the rest like heap,stack are duplicated.
There are 75 questions to complete.