HCU PHD CS MAY 2013
Question 1 
The adjacency matrix of a graph is nonsymmetric. The simplest may be drawn conclusion that is
The graph is directed.
 
The graph is undirected.  
The graph is disconnected.  
The graph has cycles. 
Question 1 Explanation:
If the adjacency matrix of the graph is non symmetric then definitely graph is directed,because in undirected graph if there is a path from vertex A to vertex B then there will definitely a path from vertex B to vertex A,and hence the adjacency matrix of undirected graph will be symmetric.
Question 2 
What is the radix of the numbers if the solutions to the quadratic equation
x^{2}  10x + 31=0
are x=5 and x=8?
11  
13  
10  
None of the above. 
Question 2 Explanation:
Let radix be ‘b’.
For the quadratic equation
ax^{2} + bx + c
Product of roots is = c/a
So from question the quadratic equation given is,
x^{2}  10 + 31 = 0
and the roots given are
5, 8
For the quadratic equation
ax^{2} + bx + c
Product of roots is = c/a
So from question the quadratic equation given is,
x^{2}  10 + 31 = 0
and the roots given are
5, 8
Question 3 
Agile software development is NOT based on
Incremental Development  
Cross Functional Teams  
Detailed project plan  
Iterative Development 
Question 3 Explanation:
Agile software development is a group of software development methodologies based on iterative and incremental development, where requirements and solutions evolve through collaboration between selforganizing, crossfunctional teams. The Agile Manifesto introduced the term in 2001.
Question 4 
Consider the following SQL schema for a database about schoors in a university and departments in the schools. Data types are omitted for brevity.
create table School (schoolName primary key, dean)
create table Dept (deptName primary key,
schoolName references School on delete cascade)
Write a single SQL statement that deletes all schools with more than 10 departments and also deletes all departments in those schools.
delete from School where 10<(select count (*) from School where Dept.schoolName=School.schoolName)  
delete from School where 10 < (select count (*) from Dept where Dept.schoolName=school.schoorNanre)  
delete from School where 10 <= (select count (*) from Dept Dept.schoonName=School.schoolName)  
None of the above.

Question 4 Explanation:
Option B is the correct SQL query.
Option A is wrong because the subquery contains School schema instead of Dept schema.
Option C is wrong because in question it is clearly said “more than 10” and not “more than or equal to 10”.
Option A is wrong because the subquery contains School schema instead of Dept schema.
Option C is wrong because in question it is clearly said “more than 10” and not “more than or equal to 10”.
Question 5 
A machine uses a 16bit two's complement representation for integers and little endian byte ordering, that is, the least significant byte of an integer is stored at the lower address. show what the following program will print out:
int x; /* 16bit signed integer */
char *cp = (char *) &x;
x = 0x0013;
printf(“x is %d\n', , x) ;
printf(“%d %d\n”, p[0], p[1] );
x=:9  
x=19  
x=9  
None of the above. 
Question 6 
The phases in the software development process are listed below in arbitrary order:
(a) Design
(b) Test
(c) Code
(d) Requirements Analysis
(e) Maintenance
(f) Deployment
The correct ordering is
a,b,c,d,e,f  
d,a,c,b,f,e  
b,c,f,a,d,e  
d,a,c,b,e,f 
Question 6 Explanation:
There are following six phases in every Software development life cycle model:
* Requirement gathering and analysis.
* Design.
* Implementation or coding.
* Testing.
* Deployment.
* Maintenance.
* Requirement gathering and analysis.
* Design.
* Implementation or coding.
* Testing.
* Deployment.
* Maintenance.
Question 7 
Which of the following is NoT true about design patterns?
They are templates that can be used in different situations
 
They are formalized best practices  
They can be directly transformed into code  
None of the above. 
Question 7 Explanation:
In software engineering, a software design pattern is a general, reusable solution to a commonly occurring problem within a given context in software design. It is not a finished design that can be transformed directly into source or machine code. Rather, it is a description or template for how to solve a problem that can be used in many different situations. Design patterns are formalized best practices that the programmer can use to solve common problems when designing an application or system.
Question 8 
Data items grouped together for storage purposes are called
Title  
List  
String  
Record 
Question 8 Explanation:
Data items grouped together for storage purposes are called records.
Question 9 
Testing which is performed after modification to the existing system is known as
Regression testing  
Acceptance testing  
Integration testing  
Blackbox testing 
Question 9 Explanation:
Testing an application as a whole for the modification in any module or functionality is termed as Regression Testing. It is difficult to cover all the systems in Regression Testing, so typically Automation Testing Tools are used for these types of testing.
Question 10 
In DBMS, two files may be joined into a third file, if
they have a row in common  
they have a field in common  
they have no records with the same value in common field  
both B and C 
Question 10 Explanation:
In DBMS, two files may be joined into a third file, if they have a field in common
Question 11 
The correct recurrence relation for computing the timecomplexity of Towers of Hanoi problem is
where T(n) is the number of steps to solve the problem of size n.
T(n)=2T(n1) + 1  
T(n)=T(n1) + 1  
T(n)=T(n/2) + 1  
T(n)=2T(n/2) + 1

Question 11 Explanation:
Pseudo code for towers of hanoi is
TOH(n, x, y, z)
{
if (n >= 1)
{
TOH((n1), x, z, y)
move:x→ y
TOH((n1), z, y, x)
}
}
Recurrence relation for computing the timecomplexity of Towers of Hanoi problem is
T(n)=2T(n1) + 1
TOH(n, x, y, z)
{
if (n >= 1)
{
TOH((n1), x, z, y)
move:x→ y
TOH((n1), z, y, x)
}
}
Recurrence relation for computing the timecomplexity of Towers of Hanoi problem is
T(n)=2T(n1) + 1
Question 12 
An example of a consumable resource is
signal  
text file  
memory
 
printer 
Question 12 Explanation:
The resources that are depleted after the use by a process. Examples include Hardware interrupts, Unix signals, pthread_cond_signal calls, messages, and information in I/O buffers.
Question 13 
Given the declarations: int *p and int a[12], which of the following is illegal in C?
P=a  
a=p  
*p=a[2]  
P=NULL 
Question 13 Explanation:
We cant the change the address of ‘a’ because it is mnemonic and not any variable.
Question 14 
What does the following code do?
a = a + b;
b = a  b;
a = a  b;
make a = a + b and b = a  
make a = 0 and b = a  
make a = b and b = a  b  
swap the values of a and b 
Question 14 Explanation:
The following code swaps the values of ‘a’ and ‘b’. Take some examples of ‘a’ and ‘b’.
Question 15 
Which of the following transitions between process states is generally disallowed in operating systems?
From run to ready state  
From ready to run state  
From wait to run state  
From run to wait state 
Question 15 Explanation:
The transition from wait to run state is generally not allowed in operating system. But transition from wait to ready state and then from ready to run state is allowed.
Question 16 
Fixed Partition allocation
Segmented Memory allocation  
Paged Memory allocation  
Fixed Partition allocation  
Demand Paging 
Question 17 
Which of the following is usually a result of 'buggy' code?
Segmentation fault  
Page fault  
Cache fault  
. None of the above. 
Question 18 
Which of the following is valid return value for a function fn in 'C' which is declared as
void fn(int, char *);
NULL  
0  
1  
None of the above 
Question 18 Explanation:
Void functions are created and used just like valuereturning functions except they do not return a value after the function executes.
Question 19 
Quick sort program is used to sort the input numbers {5,4,3,2,1} in ascending order. If the first element is chosen as the pivot element, what is the total number of swaps (excluding swapping of the same element) the program is going to make in order to sort the input data in ascending order?
0  
4  
3  
2 
Question 20 
Which of the following sorting algorithms yield approximately the same worstcase and averagecase running time behaviour in o(nlogn)?
Quicksort and Radix sort  
Heap sort and Merge sort  
Bubble sort and Selection sort  
None of the above. 
Question 20 Explanation:
Heap sort has worst case time complexity as O(nlogn) and average case time complexity as O(nlogn)
Merge sort has worst case time complexity as O(nlogn) and average case time complexity as O(nlogn)
Bubble sort has worst case time complexity as O(n^2) and average case time complexity as O(n^2)
Selection sort has worst case time complexity as O(n^2) and average case time complexity as O(n^2)
Quick sort has worst case time complexity as O(n^2) and average case time complexity as O(nlogn)
Radix sort has worst case time complexity as O(n+K) and average case time complexity as O(n+K)
Merge sort has worst case time complexity as O(nlogn) and average case time complexity as O(nlogn)
Bubble sort has worst case time complexity as O(n^2) and average case time complexity as O(n^2)
Selection sort has worst case time complexity as O(n^2) and average case time complexity as O(n^2)
Quick sort has worst case time complexity as O(n^2) and average case time complexity as O(nlogn)
Radix sort has worst case time complexity as O(n+K) and average case time complexity as O(n+K)
Question 21 
Answer Questions 21  22 using the following Finite Automaton (FA) where the start S is state and T is the ending state:
The language accepted by the FA is:
(a + b)*(a + b)  
(a + b)*b  
(a + b)*a  
a*b 
Question 21 Explanation:
The given automata generates all the strings ending with ‘a’.
Question 22 
Answer Questions 21  22 using the following Finite Automaton (FA) where the start S is state and T is the ending state:
In order to make the automaton shown above accept the string of length zero, the language of all words not ending with letter b (and also the null string), the following minor changes will suffice:
Make righthand state the start state and lefthand static the final state  
Make righthand state both the start and final state  
Make lefthand state both the start and final state  
Delete the lefthand state's selfloop labelled with b 
Question 22 Explanation:
Let’s make the right hand state both start and final state,
And we can clearly see that above automata accepts all the string not ending with ‘b’ and also accepts the empty string.
And we can clearly see that above automata accepts all the string not ending with ‘b’ and also accepts the empty string.
Question 23 
The term "aging" refers to:
Keeping track of the time a page has been in memory for the purpose of LRU replacement  
Keeping track of the total time a job has been in the system since it was first  
Letting jobs reside in memory for a certain amount of time so that the number of pages required can be estimated accurately  
Gradually increasing the priority of jobs that wait in the system for a long time to remedy indefinite blocking 
Question 23 Explanation:
In Operating systems, aging or ageing is a scheduling technique used to avoid starvation. Aging is used to gradually increase the priority of a task, based on its waiting time in the ready queue.
Question 24 
Which conclusion "logically follows” from the premises given below?
Prices are high
If prices are high, one should sell bonds.
If interest rates are not low, one should not sell bonds.
Do not sell bonds  
No conclusion can be drawn since the relationship between prices and interest rates has not been explicitly defined.  
Interest rates are high  
Interest rates are low 
Question 25 
Choose the best answer from the following if A⊕B=C, (the symbol ⊕ is used for Exclusive OR (XOR)):
A ⊕C=B  
B ⊕ C= A  
A ⊕ B ⊕ C=0  
All of the above. 
Question 25 Explanation:
Equation A⊕B = C is satisfied for roq 1, 4, 6, 7.
Also, for the given equations in options,
A⊕C = B
B⊕C = A
A⊕B⊕C = 0
is also satisfied for row 1,4,6,7.
Hence, option D is correct.
Question 26 
The logical expression ((A ⋀ B)' ⇒ (C' ⋀ A)) ⇒ (A ≡ 1) is:
A contradiction (always false)  
A regular expression  
A tautology (always true)  
None of the above. 
Question 26 Explanation:
We know that if A⇒B and if B is true then whatever the A is the complete expression is always true.
Hence in question it is clearly given that the right side of ’ ⇒’ is 1(or true).Hence the complete expression is always true.
Hence in question it is clearly given that the right side of ’ ⇒’ is 1(or true).Hence the complete expression is always true.
Question 27 
Software that measures, monitors, analyzes, and controls realworld events is called:
Realtime Software  
System Software  
Business Software  
Scientific Software 
Question 27 Explanation:
Software that measures, monitors, analyzes, and controls realworld events is called realtime software.
Question 28 
A onedimensional array A has indices 1 ... 75. Each element is a string and takes three memory words. The array is stored starting at location 1120 decimal. The starting address of A[49] is:
1169  
1264  
1267  
None of the above 
Question 28 Explanation:
Each element of the array has a size of 3 words.
Now the starting address of array A[49] is = 1120 + (48*3) = 1264
Now the starting address of array A[49] is = 1120 + (48*3) = 1264
Question 29 
As an ordered group of homogeneous elements, a stack is more like a(n):
Record  
File  
Array
 
All of the above. 
Question 30 
A die is tossed 7 times. What is the probability that all six faces appear at 1east
once?
63/64  
2/9  
5/54  
5/324 
Question 30 Explanation:
Question 31 
Ethernet belongs to the____in the ISO/OSI Network architecture.
Physical Layer  
Application Layer  
Session Layer  
Medium Access Layer 
Question 31 Explanation:
Ethernet operates in the lower two layers of the OSI model: the Data Link layer and the Physical layer
Question 32 
In the Linux operating system, which important components needed for connectivity
to the Internet are found in the file named /etc/resolv.conf?
Gateways  
Firewalls  
Domain Name Servers  
None of the above. 
Question 33 
Which of the following is NOT a string matching algorithm?
KnuthMorrisPratt  
GrahamKruskall  
BoyerMoore  
RabinKarp 
Question 33 Explanation:
The Graham Kruskal algorithm is not a string matching algorithm,it is a greedy algorithm to find the minimum spanning tree of the graph.
Question 34 
Which of the following is a protocol for sending email?
IMAP  
POPS  
SMTP  
None of the above. 
Question 34 Explanation:
SMTP is used for sending mail.IMAP and POP is used to receive email.
Question 35 
Which of the following is the world's first graphical browser?
Mosaic  
Internet Explorer  
Opera  
Netscape 
Question 35 Explanation:
Mosaic is the world's first graphical browser.
Question 36 
which of the following could be a valid lPv4 address? [ Note: where '0x' indicates that the addresses are specified in hexadecimal notation. ]
0x3425  
0x34256721  
0x34  
None of the above. 
Question 36 Explanation:
IP address consist of total 32 bits.So Option B could be the valid IP address as it consists of 32 bits (8*4=32)
Question 37 
Which of the following is false about Greedy algorithms?
They never revisit a choice made earlier.  
They always run in O(n) time.  
They always make the best choice possible given the information available at that time.  
None of the above. 
Question 37 Explanation:
There are many greedy algorithms whose time complexity is either O(n^2) or O(nlogn).
Question 38 
An undirected graph with n nodes is represented by its adjacency matrix A. It was
found that A^{n} has only '0's along its diagonal. Which of the following is then true
about the graph represented by A?
The graph is acyclic.  
The graph is planar.  
The shortest path between any two nodes is longer than n hops.  
None of the above. 
Question 39 
The correct way to show that a new problem is NPComplete is
Reduce a known NPComplete problem into the new problem in P time  
Reduce the new problem into a known NPComplete problem in P time  
Show that there exists an algorithm for the probieren which is equivalent to a known NPComplete problem  
None of the above 
Question 40 
Which of the following graph problems is solved using a dynamic programming approach?
Shortest Path between any pair of nodes.  
Maximum Clique Problem.  
Colouring Problem.  
All of the above. 
Question 40 Explanation:
All pairs shortest path problems are solved using a Dynamic programming approach.
Colouring problem is solved using backtracking.
Maximum clique problem is not solved using a dynamic programming approach.
Colouring problem is solved using backtracking.
Maximum clique problem is not solved using a dynamic programming approach.
Question 41 
Questions 41  44 are based on the following paragraph. please read it carefully and then answer the questions.
Over the last two decades, stochastic resonance has continuously attracted considerable attention. The term is given to a phenomenon that is manifest in nonlinear systems whereby generally feeble input information (such as a weak signal) can be amplified and optimized by the assistance of noise. The effect requires three basic ingredients:
(i) an energetic activation barrier or, more generally, a form of threshold;
(ii) a weak coherent input (such as a periodic signal);
(iii) a source of noise that is inherent in the system, or that adds to the coherent input.
Given these features, the response of the system undergoes resonancelike behavior as a function of the noise level; hence the name stochastic resonance. The underlying mechanism is fairly simple and robust. As a consequence, stochastic resonance has been observed in a large variety of systems, including bistable ring lasers, semiconductor devices, chemical reactions, and mechanoreceptor cells in the tail fan of a crayfish.
In this paper, the authors report, interpret, and extend much of the current understanding of the theory and physics of stochastic resonance. They introduce the readers to the basic features of stochastic resonance and its recent history.
Which of the following best defines stochastic resonance?
Changes in probabilities of occurrence of certain signals based on random processes  
Amplification of a signal by the addition of noise  
Attenuation of a signal by the addition of noise  
Resonance caused by random processes 
Question 41 Explanation:
From the line “ The term is given to a phenomenon that is manifest in nonlinear systems whereby generally feeble input information (such as a weak signal) can be amplified and optimized by the assistance of noise” it is clear that the answer is option B.
Question 42 
Questions 41  44 are based on the following paragraph. please read it carefully and then answer the questions.
Over the last two decades, stochastic resonance has continuously attracted considerable attention. The term is given to a phenomenon that is manifest in nonlinear systems whereby generally feeble input information (such as a weak signal) can be amplified and optimized by the assistance of noise. The effect requires three basic ingredients:
(i) an energetic activation barrier or, more generally, a form of threshold;
(ii) a weak coherent input (such as a periodic signal);
(iii) a source of noise that is inherent in the system, or that adds to the coherent input.
Given these features, the response of the system undergoes resonancelike behavior as a function of the noise level; hence the name stochastic resonance. The underlying mechanism is fairly simple and robust. As a consequence, stochastic resonance has been observed in a large variety of systems, including bistable ring lasers, semiconductor devices, chemical reactions, and mechanoreceptor cells in the tail fan of a crayfish.
In this paper, the authors report, interpret, and extend much of the current understanding of the theory and physics of stochastic resonance. They introduce the readers to the basic features of stochastic resonance and its recent history.
Which of the following is not required for stochastic resonance?
A threshold type barrier  
Noise within the signal  
Weak signal  
Strong signal 
Question 42 Explanation:
From the lines
“The effect requires three basic ingredients:
(i) an energetic activation barrier or, more generally, a form of threshold;
(ii) a weak coherent input (such as a periodic signal);
(iii) a source of noise that is inherent in the system, or that adds to the coherent input.”
It is clear that a strong signal is not required for stochastic resonance.
“The effect requires three basic ingredients:
(i) an energetic activation barrier or, more generally, a form of threshold;
(ii) a weak coherent input (such as a periodic signal);
(iii) a source of noise that is inherent in the system, or that adds to the coherent input.”
It is clear that a strong signal is not required for stochastic resonance.
Question 43 
Questions 41  44 are based on the following paragraph. please read it carefully and then answer the questions.
Over the last two decades, stochastic resonance has continuously attracted considerable attention. The term is given to a phenomenon that is manifest in nonlinear systems whereby generally feeble input information (such as a weak signal) can be amplified and optimized by the assistance of noise. The effect requires three basic ingredients:
(i) an energetic activation barrier or, more generally, a form of threshold;
(ii) a weak coherent input (such as a periodic signal);
(iii) a source of noise that is inherent in the system, or that adds to the coherent input.
Given these features, the response of the system undergoes resonancelike behavior as a function of the noise level; hence the name stochastic resonance. The underlying mechanism is fairly simple and robust. As a consequence, stochastic resonance has been observed in a large variety of systems, including bistable ring lasers, semiconductor devices, chemical reactions, and mechanoreceptor cells in the tail fan of a crayfish.
In this paper, the authors report, interpret, and extend much of the current understanding of the theory and physics of stochastic resonance. They introduce the readers to the basic features of stochastic resonance and its recent history.
In the last sentence, the word "they" refers to
Authors  
Weak signals  
Reporting, interpreting and extending the understanding of signals  
None of the above. 
Question 43 Explanation:
From the line “In this paper, the authors report, interpret, and extend much of the current understanding of the theory and physics of stochastic resonance” it is clear that they refer to “authors”.
Question 44 
Questions 41  44 are based on the following paragraph. please read it carefully and then answer the questions.
Over the last two decades, stochastic resonance has continuously attracted considerable attention. The term is given to a phenomenon that is manifest in nonlinear systems whereby generally feeble input information (such as a weak signal) can be amplified and optimized by the assistance of noise. The effect requires three basic ingredients:
(i) an energetic activation barrier or, more generally, a form of threshold;
(ii) a weak coherent input (such as a periodic signal);
(iii) a source of noise that is inherent in the system, or that adds to the coherent input.
Given these features, the response of the system undergoes resonancelike behavior as a function of the noise level; hence the name stochastic resonance. The underlying mechanism is fairly simple and robust. As a consequence, stochastic resonance has been observed in a large variety of systems, including bistable ring lasers, semiconductor devices, chemical reactions, and mechanoreceptor cells in the tail fan of a crayfish.
In this paper, the authors report, interpret, and extend much of the current understanding of the theory and physics of stochastic resonance. They introduce the readers to the basic features of stochastic resonance and its recent history.
What is the reason for stochastic resonance to be observed in a large variety of systems?
There is noise everywhere  
There are signals everywhere  
The basic mechanism is simple and robust  
Resonance occurs all the time 
Question 44 Explanation:
From the line “The underlying mechanism is fairly simple and robust. As a consequence, stochastic resonance has been observed in a large variety of systems, ” it is clear that answer is option C.
Question 45 
Questions 45  48 are based on the following paragraph. Please read it carefully and then answer the questions.
The following text is from the Turing Award Lecture by the great computer scientist, C. A. R. Hoare.
"Arouncl Easter 1961, a course on ALGOL 60 was offered in Brighton, England, with Peter Naur, Edsger W. Dijkstra, and Peter Landin as tutors. I attended this course with my colleague in the language project, Jill Pym, our divisional Technical Manager, Roger Cook, and our Sales Manager, Paul King. It was there that I first learned about recursive procedures and saw how to program the sorting method which I had earlier found such difficulty in explaining. It was there that I wrote the procedure, .immodestly named QUICKSORT, on which my career as a computer scientist is founded. Due credit must be paid to the genius of the designers of ALGOL 60 who included recursion in their language and enabled me to describe my invention so elegantly to the world. I have regarded it as the highest goal of programming language design to enable good ideas to be elegantly expressed.."
From the above paragraph, which of the following statements is true?
A course on ALGOL 60 was offered to Edsger W. Dijkstra arrcl otlurrs by C. A. R. Hoare  
QUICKSORT is invented by C. A. R. Hoare C.  
A. R. Hoare was a divisional Technical Manager  
None of the above. 
Question 45 Explanation:
QUICKSORT is invented by C.A.R. Hoare.
Question 46 
Questions 45  48 are based on the following paragraph. Please read it carefully and then answer the questions.
The following text is from the Turing Award Lecture by the great computer scientist, C. A. R. Hoare.
"Arouncl Easter 1961, a course on ALGOL 60 was offered in Brighton, England, with Peter Naur, Edsger W. Dijkstra, and Peter Landin as tutors. I attended this course with my colleague in the language project, Jill Pym, our divisional Technical Manager, Roger Cook, and our Sales Manager, Paul King. It was there that I first learned about recursive procedures and saw how to program the sorting method which I had earlier found such difficulty in explaining. It was there that I wrote the procedure, .immodestly named QUICKSORT, on which my career as a computer scientist is founded. Due credit must be paid to the genius of the designers of ALGOL 60 who included recursion in their language and enabled me to describe my invention so elegantly to the world. I have regarded it as the highest goal of programming language design to enable good ideas to be elegantly expressed.."
Where did C. A. R. Hoare first learn about recursive procedures?
In a course on ALGOL 60  
During discussions with Jill Pym, Roger Cook and Paul King  
From the designers of ALGOL 60  
None of the above. 
Question 46 Explanation:
In the course of ALGOL 60 C. A. R. Hoare first learned about recursive procedure.
Question 47 
Questions 45  48 are based on the following paragraph. Please read it carefully and then answer the questions.
The following text is from the Turing Award Lecture by the great computer scientist, C. A. R. Hoare.
"Arouncl Easter 1961, a course on ALGOL 60 was offered in Brighton, England, with Peter Naur, Edsger W. Dijkstra, and Peter Landin as tutors. I attended this course with my colleague in the language project, Jill Pym, our divisional Technical Manager, Roger Cook, and our Sales Manager, Paul King. It was there that I first learned about recursive procedures and saw how to program the sorting method which I had earlier found such difficulty in explaining. It was there that I wrote the procedure, .immodestly named QUICKSORT, on which my career as a computer scientist is founded. Due credit must be paid to the genius of the designers of ALGOL 60 who included recursion in their language and enabled me to describe my invention so elegantly to the world. I have regarded it as the highest goal of programming language design to enable good ideas to be elegantly expressed.."
Why does C. A. R. Hoare say QUICKSORT is "immodestly" named?
It is not easy to explain QUICKSORT  
Giving the adjective "quick" in the name is not modest  
QUICKSORT is not possible without the recursive procedures of ALGOL 60  
None of the above. 
Question 48 
Questions 45  48 are based on the following paragraph. Please read it carefully and then answer the questions.
The following text is from the Turing Award Lecture by the great computer scientist, C. A. R. Hoare.
"Arouncl Easter 1961, a course on ALGOL 60 was offered in Brighton, England, with Peter Naur, Edsger W. Dijkstra, and Peter Landin as tutors. I attended this course with my colleague in the language project, Jill Pym, our divisional Technical Manager, Roger Cook, and our Sales Manager, Paul King. It was there that I first learned about recursive procedures and saw how to program the sorting method which I had earlier found such difficulty in explaining. It was there that I wrote the procedure, .immodestly named QUICKSORT, on which my career as a computer scientist is founded. Due credit must be paid to the genius of the designers of ALGOL 60 who included recursion in their language and enabled me to describe my invention so elegantly to the world. I have regarded it as the highest goal of programming language design to enable good ideas to be elegantly expressed.."
What, in C. A. R. Hoare's opinion, is the main aspect to aim for in designing programming languages?
Having QUICKSORT procedure  
Errable elegant expression of ideas  
Easy to program sorting routines  
Having recursion 
Question 48 Explanation:
According to C. A. R. Hoare's opinion having recursion is the main aspect to aim for in designing programming language.
Question 49 
Two algorithms A and B take n2 days and 2n seconds respectively to solve a problem on an instance of size n. What is the size of the smallest instance for which algorithm A outperforms B in the given choices?
10  
20  
30  
40 
Question 49 Explanation:
A = n^{2} days = n^{2} × 24 × 60 × 60 sec
B = 2^{n} sec
The question is asking for what minimum value of n, A will take less time than B.
Let’s take option wise
A) n=10,
A = 10^{2} × 24 × 60 × 60 = 2400 × 3600 sec
B = 2^{10} = 1024 sec
Wrong.
B) n=20
A = 20^{2} × 24 × 60 × 60 = 34560000
B = 2^{20} = 1048576
Wrong.
C) n=30,
A = 30^{2} × 24 × 3600 = 77760000
B = 2^{30} = 1073741824
Yes, for n=30, A outperforms B.
B = 2^{n} sec
The question is asking for what minimum value of n, A will take less time than B.
Let’s take option wise
A) n=10,
A = 10^{2} × 24 × 60 × 60 = 2400 × 3600 sec
B = 2^{10} = 1024 sec
Wrong.
B) n=20
A = 20^{2} × 24 × 60 × 60 = 34560000
B = 2^{20} = 1048576
Wrong.
C) n=30,
A = 30^{2} × 24 × 3600 = 77760000
B = 2^{30} = 1073741824
Yes, for n=30, A outperforms B.
Question 50 
Suppose that a list of n sorted integers is given. Which of the following algorithms can detect that the input is sorted in O(n) time?
insertion sort only  
selection sort only  
bubble sort and selection sort  
bubble sort and insertion sort 
Question 50 Explanation:
Since the input is already sorted so insertion sort and bubble sort will take O(n). But selection sort in all cases takes O(n^2) time.
Question 51 
The following statements are about Prim’s and Kruskal's algorithm to find Minimum spanning Tree in a weighted connected graph of n vertices. Which of them is not true?
Kruskal's algorithm starts by finding an edge with the least weight  
At any intermediatestage, the output of Prim's algorithm is a tree  
Kruskal's algorithm terminate once the output has (n  1) edges  
Prim's algorithm needs to check at each step if a cycle is formed 
Question 51 Explanation:
In prim's algorithm cycle can never be formed because in prims algorithm we focus on vertices rather than edges,so no need to check about if cycle is formed.
Question 52 
A(n)=Theta(B(n)) for
A(n)= n log n and B(n)=nlog(n!)  
A(n)=2^{n} and B(n)=2^{10}  
A(n)= 2^{logn} and B(n)=n  
A(n)=n^{2} and B(n)=n^{3} 
Question 52 Explanation:
Let’s check option wise,
A)
A(n) = n log n
B(n) = n log (n!) ≅ n log (n^{n}) ≅ n^{2} log n
So, A(n) ≠ Ө(B(n))
But A(n) = O(B(n))
B)
A(n) = 2^{n}
B(n) = 2^{10}
A(n) ≠ Ө(B(n))
A(n) = ᘯ(B(n))
C)
A(n) = 2^{logn} = n
B(n) = n
∴ A(n) = Ө(B(n))
D)
A(n) = n^{2}
B(n) = n^{3 A(n) ≠ Ө(B(n)) A(n) = O(B(n)) }
A)
A(n) = n log n
B(n) = n log (n!) ≅ n log (n^{n}) ≅ n^{2} log n
So, A(n) ≠ Ө(B(n))
But A(n) = O(B(n))
B)
A(n) = 2^{n}
B(n) = 2^{10}
A(n) ≠ Ө(B(n))
A(n) = ᘯ(B(n))
C)
A(n) = 2^{logn} = n
B(n) = n
∴ A(n) = Ө(B(n))
D)
A(n) = n^{2}
B(n) = n^{3 A(n) ≠ Ө(B(n)) A(n) = O(B(n)) }
Question 53 
A tree has x vertices of degree 1,2 vertices of degree 2,4 vertices of degree 3 and
3 vertices of degree 4. What is the value of x?
12  
10  
8  
Cannot be computed 
Question 53 Explanation:
Total no. of vertices = x + 2 + 4 + 3 = 9 + x
In a tree of n vertices no. of edges is n1.
So for given tree no. of edges is (9 + x  1) = 8 + x
Now,
Sum of degree of vertices = 2 × no. of edges
x × 1 + 2 × 2 + 4 × 3 + 3 × 4 = 2(8 + x)
x + 4 + 12 + 12 = 16 + 2x
x + 28 = 16 + 2x
12 = x
∴ x = 12
In a tree of n vertices no. of edges is n1.
So for given tree no. of edges is (9 + x  1) = 8 + x
Now,
Sum of degree of vertices = 2 × no. of edges
x × 1 + 2 × 2 + 4 × 3 + 3 × 4 = 2(8 + x)
x + 4 + 12 + 12 = 16 + 2x
x + 28 = 16 + 2x
12 = x
∴ x = 12
Question 54 
Given the following grammar,
S → AB
A → a
A → BaB
B → bbA
Which of the statements below is false?
The length of every string produced by the grammar is even  
No string produced by the grammar has an odd number of consecutive b's  
No string produced by the grammar has three consecutive a's  
No string produced by the grammar has four consecutive b's 
Question 54 Explanation:
S ⟶ AB
BaBB (∵ A ⟶ BaB)
bbAaBB (∵ B ⟶ bbA)
bbBaBaBB (∵ A ⟶ BaB)
bbbbAaBaBB (∵ B ⟶ bbA)
bbbbaaBaBB (∵ A ⟶ a)
bbbbaabbAaBB (∵ B ⟶ bbA)
bbbbaabbaaBB (∵ A ⟶ a)
bbbbaabbaabbAB (∵ B ⟶ bbA)
bbbbaabbaabbaB (∵ A ⟶ a)
bbbbaabbaabbabbA (∵ B ⟶ bbA)
bbbbaabbaabbabba (∵ A ⟶ a)
Hence we got the string which contains four consecutive b’s.
Hence option (D) is False.
BaBB (∵ A ⟶ BaB)
bbAaBB (∵ B ⟶ bbA)
bbBaBaBB (∵ A ⟶ BaB)
bbbbAaBaBB (∵ B ⟶ bbA)
bbbbaaBaBB (∵ A ⟶ a)
bbbbaabbAaBB (∵ B ⟶ bbA)
bbbbaabbaaBB (∵ A ⟶ a)
bbbbaabbaabbAB (∵ B ⟶ bbA)
bbbbaabbaabbaB (∵ A ⟶ a)
bbbbaabbaabbabbA (∵ B ⟶ bbA)
bbbbaabbaabbabba (∵ A ⟶ a)
Hence we got the string which contains four consecutive b’s.
Hence option (D) is False.
Question 55 
Which of the following programming language features requires stackbased storage allocation rather than static allocation?
Recursive procedures  
Call by Reference parameters  
Arbitrary goto's  
Two dimensional arrays 
Question 55 Explanation:
Recursive procedures require stack based storage allocation.
Question 56 
What is the postfix form of the expression in prefix form **ABCD?
AB*CD*  
ABC**D  
ABC*D*  
AB**CD 
Question 56 Explanation:
Let first draw tree from given prefix expression,
* *ABCD
Now the sequence for postfix traversal is (Left, Right, Root).
∴ The postfix expression is AB*CD*
Now the sequence for postfix traversal is (Left, Right, Root).
∴ The postfix expression is AB*CD*
Question 57 
The initial configuration ofa queue is a,b,c,d (a is at the front), To get the configuration d,b,c,a, one needs a minimum of
2 deletions and 3 insertions  
3 deletions and 2 insertions  
3 deletions and 3 insertions  
3 deletions and 4 insertions 
Question 57 Explanation:
< img src="https://solutionsadda.in/wpcontent/uploads/2020/05/Screenshot_538.png">
< img src="https://solutionsadda.in/wpcontent/uploads/2020/05/Screenshot_539.png">
< img src="https://solutionsadda.in/wpcontent/uploads/2020/05/Screenshot_539.png">
Question 58 
In the following binary search tree if we delete the node 14, then the preorder traversal of the tree after deletion is
12,6,3,30,85,67,95  
6,3,12,30,85,95,67  
12,3,6,85,30,95,67  
30,6,3,12,85,67,95 
Question 58 Explanation:
The given binary tree is,
Now preorder traversal for above tree is, 12, 6, 3, 30, 85, 67, 95 0r ⟶ Let’s replace 14 with inorder successor,
Now preorder traversal for above tree is, 12, 6, 3, 30, 85, 67, 95 0r ⟶ Let’s replace 14 with inorder successor,
Question 59 
The running time of an algorithm is given by
Then T(n)=
O(n)  
O(logn)  
O(1)  
O(n^{2}) 
Question 59 Explanation:
T(1) = 1
T(2) = 1
T(3) = 1
T(n) = T(n1) + T(n2)  T(n3)
Now,
T(4) = T(3) + T(2)  T(1) = 1 + 1  1 = 1
T(5) = T(4) + T(3)  T(2) = 1 + 1  1 = 1
T(6) = 1
⋮
T(n) = 1
Hence, T(n) = 1
T(2) = 1
T(3) = 1
T(n) = T(n1) + T(n2)  T(n3)
Now,
T(4) = T(3) + T(2)  T(1) = 1 + 1  1 = 1
T(5) = T(4) + T(3)  T(2) = 1 + 1  1 = 1
T(6) = 1
⋮
T(n) = 1
Hence, T(n) = 1
Question 60 
If a graph G(V,E) is a complete graph, time required to reach any node graph in the using breadth first search is
O(v)  
O(1)  
O(E)  
O(V*E) 
Question 60 Explanation:
Since the graph is complete ,each vertex is connected to every other vertex. So using BFS any node can be visited in O(V) time ,because initially whatever vertex we chose ,then next time all the remaining vertex will be at level 1 for breadth first traversal and can be visited one after another directly .
Question 61 
If an array is used to implement a tertiary tree, the positions of children for any node i can be found at the locations
2i, 2i+1, 2i+2  
3i, 3i+1, 3i+2  
3i1, 3i, 3i+1  
3i+3, 3i+4, 3i+5 
Question 61 Explanation:
Let take example of tertiary tree,
Now let’s check option C,
3i1, 3i, 3i+1
Let’s put i=2, we get
5, 6, 7
and yes 5, 6, 7 is the children of node i=2
Now let’s check option C,
3i1, 3i, 3i+1
Let’s put i=2, we get
5, 6, 7
and yes 5, 6, 7 is the children of node i=2
Question 62 
In C, which of the following variables are created at the time of a function call and
destroyed when the function returns?
integer variables  
parameters to the function  
static variables declared within the function  
extern variables 
Question 62 Explanation:
Function parameters have local scope. This means that they are created when the function is invoked, and are destroyed when the function block terminates.
Question 63 
Which of the following methods is used for accessing disk blocks in an operating system?
Linked list  
Indirect Access  
Hashing  
All of the above. 
Question 64 
Which of the scheduling algorithms does not result in starvation?
FCFS  
Multilevel queues  
Shortest Job First  
Priority scheduling 
Question 64 Explanation:
A) FCFS does not result in starvation because it is a first come first serve scheduling method.
B) In multilevel queues the process with low priority scheduling algorithm may starve.
C) In the shortest job, the first scheduling process with a longer burst time may starve.
D) The priority scheduling algorithm process with low priority may starve.
B) In multilevel queues the process with low priority scheduling algorithm may starve.
C) In the shortest job, the first scheduling process with a longer burst time may starve.
D) The priority scheduling algorithm process with low priority may starve.
Question 65 
Waterfall model in software engineering is an example of a(n)
Linear  
Rapid  
Iterative  
Interactive 
Question 65 Explanation:
The Waterfall model in software engineering is an example of an iterative method.
Question 66 
A system has a 24bit processor and uses a page size of 2KB. Considering that
all the registers in the processor are limited to 24 bits, how many entries may be
expected in the page table?
8192  
4096  
2048  
None of the above. 
Question 66 Explanation:
Lets first find offset bits,
2KB = 2^11 B. So offset bits = 11
Hence no. of page table entries is = 2^(2411) = 2^13 = 8192
2KB = 2^11 B. So offset bits = 11
Hence no. of page table entries is = 2^(2411) = 2^13 = 8192
Question 67 
A sequence d=(d_{1},d_{2},...,d_{n}) is called graphic if there is a simple undirected graph with degree sequence d. Which of the following are not valid graphic sequences?
(2, 3, 3, 4, 4, 5)  
(2, 3, 4, 4, 5)  
(1, 3, 3, 3)  
(1, 2, 2, 2,3) 
Question 67 Explanation:
By using the havel hakimi theorem we can show that only the sequence given in option D is valid and rest are invalid.
Question 68 
What is the maximum number of edges in a simple undirected bipartite graph of n nodes?
^{n}C_{2}  
⌊n^2/4 ⌋  
⌊n^2/2⌋  
⌊n/2⌋ 
Question 68 Explanation:
Maximum no. of edges in a simple undirected bipartite graph of n nodes is (n/2) * (n/2) = n^2 /4,which is closest to the option B.
Question 69 
Component level design metric includes
Cohesion metric  
Complexity metric  
Coupling metric  
AIl of the above 
Question 69 Explanation:
Componentlevel design metrics focus on internal characteristics of a software component and include measures of the “three Cs”—module cohesion, coupling, and complexity. These measures can help a software engineer to judge the quality of a componentlevel design.
Question 70 
Fault tolerance in software applications can be ensured through
Selfchecking facility  
Redundant modules  
Recovery blocks  
All of the above 
Question 70 Explanation:
Fault tolerance in software applications can be ensured through self checking facility,redundant modules recovery blocks .
Question 71 
Simplify the following Boolean function using fourvariable Karnaugh maps.
F(A,B,C,D)=Σ(3,7,11, 13, 14, 15)
CD + ABC + ABD  
ACD + BCD + ABC + ABD  
ABC’D + ABC + CD  
None of the above. 
Question 71 Explanation:
Let first draw kmap and then we will find the Boolean function using kmap.
∴ Boolean function is,
CD + ABD + ABC
∴ Boolean function is,
CD + ABD + ABC
Question 72 
A new child process is required for
I. A login shell
II. Web server
III. Device driver for disks
I only  
II only  
III only  
II and III only 
Question 73 
Which of the following is not related to static testing?
Code Review  
Code Walkthrough  
Code Inspection  
Code Execution 
Question 74 
A square matrix is stored either in rowmajor or columnmajor order. Which of the following statements is necessarily true?
The diagonal elements are stored in the same locations in either order  
The elements in (i,j) locations where i and j are both odd are stored in the same locations  
AII the elements in the last row are in the same locations  
None of the above. 
Question 74 Explanation:
In whatever order a square matrix is stored, either row major or column major, the diagonal elements are stored in the same locations in either order.
Question 75 
uint8 is used in a programming language to represent 8bit unsigned integers from 0 onwards. If there is either an under or overflow, the numbers cycle around.
What is the result of adding 210 and 56.
16  
15  
10  
None of the above. 
Question 75 Explanation:
The binary value of 210 = 11010010
The binary value of 56 = 00111000
Now let’s add two binary nos.,
The binary value of 56 = 00111000
Now let’s add two binary nos.,
There are 75 questions to complete.