HCU PHD CS MAY 2013

Question 1
The adjacency matrix of a graph is non-symmetric. The simplest may be drawn conclusion that is
A
The graph is directed.
B
The graph is undirected.
C
The graph is disconnected.
D
The graph has cycles.
       Data-Structures       Graphs-and-Tree
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

x2 - 10x + 31=0

are x=5 and x=8?
A
11
B
13
C
10
D
None of the above.
       Digital-Logic-Design       Number-Systems
Question 2 Explanation: 
Let radix be ‘b’.
For the quadratic equation
ax2 + bx + c
Product of roots is = c/a
So from question the quadratic equation given is,
x2 - 10 + 31 = 0
and the roots given are
5, 8
Question 3
Agile software development is NOT based on
A
Incremental Development
B
Cross Functional Teams
C
Detailed project plan
D
Iterative Development
       Software-Engineering       Software-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 self-organizing, cross-functional 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.
A
delete from School
where 10<(select count (*) from School
where Dept.schoolName=School.schoolName)
B
delete from School
where 10 < (select count (*) from Dept
where Dept.schoolName=school.schoorNanre)
C
delete from School
where 10 <= (select count (*) from Dept
Dept.schoonName=School.schoolName)
D
None of the above.
       Database-Management-System       SQL
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”.
Question 5

A machine uses a 16-bit 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; /* 16-bit signed integer */

char *cp = (char *) &x;

x = 0x0013;

printf(“x is %d\n', , x) ;

printf(“%d %d\n”, p[0], p[1] );
A
x=:919 0
B
x=199 0
C
x=99 0
D
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
a,b,c,d,e,f
B
d,a,c,b,f,e
C
b,c,f,a,d,e
D
d,a,c,b,e,f
       Software-Engineering       Software-Development
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.
Question 7
Which of the following is NoT true about design patterns?
A
They are templates that can be used in different situations
B
They are formalized best practices
C
They can be directly transformed into code
D
None of the above.
       Software-Engineering       Software-design
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
A
Title
B
List
C
String
D
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
A
Regression testing
B
Acceptance testing
C
Integration testing
D
Black-box testing
       Software-Engineering       Software-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
A
they have a row in common
B
they have a field in common
C
they have no records with the same value in common field
D
both B and C
       Database-Management-System       File-System
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 time-complexity of Towers of Hanoi problem is

where T(n) is the number of steps to solve the problem of size n.
A
T(n)=2T(n-1) + 1
B
T(n)=T(n-1) + 1
C
T(n)=T(n/2) + 1
D
T(n)=2T(n/2) + 1
       Algorithms       Time-Complexity
Question 11 Explanation: 
Pseudo code for towers of hanoi is
TOH(n, x, y, z)
{
if (n >= 1)
{
TOH((n-1), x, z, y)
move:x→ y
TOH((n-1), z, y, x)
}
}
Recurrence relation for computing the time-complexity of Towers of Hanoi problem is
T(n)=2T(n-1) + 1
Question 12
An example of a consumable resource is
A
signal
B
text file
C
memory
D
printer
       Operating-Systems       Consumable-resources
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?
A
P=a
B
a=p
C
*p=a[2]
D
P=NULL
       Programming       Arrays-and-pointers
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;
A
make a = a + b and b = a
B
make a = 0 and b = a
C
make a = b and b = a - b
D
swap the values of a and b
       Programming       Operator
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?
A
From run to ready state
B
From ready to run state
C
From wait to run state
D
From run to wait state
       Operating-Systems       Process-State-Transition-Diagram
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
A
Segmented Memory allocation
B
Paged Memory allocation
C
Fixed Partition allocation
D
Demand Paging
Question 17
Which of the following is usually a result of 'buggy' code?
A
Segmentation fault
B
Page fault
C
Cache fault
D
. 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 *);
A
NULL
B
0
C
-1
D
None of the above
       Programming       Functions
Question 18 Explanation: 
Void functions are created and used just like value-returning 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?
A
0
B
4
C
3
D
2
Question 20
Which of the following sorting algorithms yield approximately the same worst-case and average-case running time behaviour in o(nlogn)?
A
Quicksort and Radix sort
B
Heap sort and Merge sort
C
Bubble sort and Selection sort
D
None of the above.
       Algorithms       Sorting
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)
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
(a + b)*(a + b)
B
(a + b)*b
C
(a + b)*a
D
a*b
       Theory-of-Computation       Finite-Automata
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:
A
Make right-hand state the start state and left-hand static the final state
B
Make right-hand state both the start and final state
C
Make left-hand state both the start and final state
D
Delete the left-hand state's self-loop labelled with b
       Theory-of-Computation       Finite-Automata
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.
Question 23
The term "aging" refers to:
A
Keeping track of the time a page has been in memory for the purpose of LRU replacement
B
Keeping track of the total time a job has been in the system since it was first
C
Letting jobs reside in memory for a certain amount of time so that the number of pages required can be estimated accurately
D
Gradually increasing the priority of jobs that wait in the system for a long time to remedy indefinite blocking
       Operating-Systems       aging
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.
A
Do not sell bonds
B
No conclusion can be drawn since the relationship between prices and interest rates has not been explicitly defined.
C
Interest rates are high
D
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
A ⊕C=B
B
B ⊕ C= A
C
A ⊕ B ⊕ C=0
D
All of the above.
       Digital-Logic-Design       Logic-Gates-and-operators
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
A contradiction (always false)
B
A regular expression
C
A tautology (always true)
D
None of the above.
       Engineering-Mathematics       Propositional-Logic
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.
Question 27
Software that measures, monitors, analyzes, and controls real-world events is called:
A
Real-time Software
B
System Software
C
Business Software
D
Scientific Software
       Software-Engineering       Types-of-software
Question 27 Explanation: 
Software that measures, monitors, analyzes, and controls real-world events is called real-time software.
Question 28
A one-dimensional 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:
A
1169
B
1264
C
1267
D
None of the above
       Data-Structures       Arrays
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
Question 29
As an ordered group of homogeneous elements, a stack is more like a(n):
A
Record
B
File
C
Array
D
All of the above.
Question 30
A die is tossed 7 times. What is the probability that all six faces appear at 1east once?
A
63/64
B
2/9
C
5/54
D
5/324
       Engineering-Mathematics       Probability-and-statistics
Question 30 Explanation: 
Question 31
Ethernet belongs to the____in the ISO/OSI Network architecture.
A
Physical Layer
B
Application Layer
C
Session Layer
D
Medium Access Layer
       Computer-Networks       ISO-OSI-layers
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?
A
Gateways
B
Firewalls
C
Domain Name Servers
D
None of the above.
Question 33
Which of the following is NOT a string matching algorithm?
A
Knuth-Morris-Pratt
B
Graham-Kruskall
C
Boyer-Moore
D
Rabin-Karp
       Algorithms       Algorithm-Paradigms
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?
A
IMAP
B
POPS
C
SMTP
D
None of the above.
       Computer-Networks       Application-Layer-Protocol
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?
A
Mosaic
B
Internet Explorer
C
Opera
D
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 hexa-decimal notation. ]
A
0x3425
B
0x34256721
C
0x34
D
None of the above.
       Computer-Networks       IP-Adress
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?
A
They never revisit a choice made earlier.
B
They always run in O(n) time.
C
They always make the best choice possible given the information available at that time.
D
None of the above.
       Algorithms       Greedy-approach
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 An has only '0's along its diagonal. Which of the following is then true about the graph represented by A?
A
The graph is acyclic.
B
The graph is planar.
C
The shortest path between any two nodes is longer than n hops.
D
None of the above.
Question 39
The correct way to show that a new problem is NP-Complete is
A
Reduce a known NP-Complete problem into the new problem in P time
B
Reduce the new problem into a known NP-Complete problem in P time
C
Show that there exists an algorithm for the probieren which is equivalent to a known NP-Complete problem
D
None of the above
Question 40
Which of the following graph problems is solved using a dynamic programming approach?
A
Shortest Path between any pair of nodes.
B
Maximum Clique Problem.
C
Colouring Problem.
D
All of the above.
       Algorithms       Dynamic-Programming
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.
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 resonance-like 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?
A
Changes in probabilities of occurrence of certain signals based on random processes
B
Amplification of a signal by the addition of noise
C
Attenuation of a signal by the addition of noise
D
Resonance caused by random processes
       Reading-Comprehension       Reading-Comprehension
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 resonance-like 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
A threshold type barrier
B
Noise within the signal
C
Weak signal
D
Strong signal
       Reading-Comprehension       Reading-Comprehension
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.
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 resonance-like 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
A
Authors
B
Weak signals
C
Reporting, interpreting and extending the understanding of signals
D
None of the above.
       Reading-Comprehension       Reading-Comprehension
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 resonance-like 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?
A
There is noise everywhere
B
There are signals everywhere
C
The basic mechanism is simple and robust
D
Resonance occurs all the time
       Reading-Comprehension       Reading-Comprehension
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
A course on ALGOL 60 was offered to Edsger W. Dijkstra arrcl otlurrs by C. A. R. Hoare
B
QUICKSORT is invented by C. A. R. Hoare C.
C
A. R. Hoare was a divisional Technical Manager
D
None of the above.
       Reading-Comprehension       Reading-Comprehension
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?
A
In a course on ALGOL 60
B
During discussions with Jill Pym, Roger Cook and Paul King
C
From the designers of ALGOL 60
D
None of the above.
       Reading-Comprehension       Reading-Comprehension
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?
A
It is not easy to explain QUICKSORT
B
Giving the adjective "quick" in the name is not modest
C
QUICKSORT is not possible without the recursive procedures of ALGOL 60
D
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?
A
Having QUICKSORT procedure
B
Errable elegant expression of ideas
C
Easy to program sorting routines
D
Having recursion
       Reading-Comprehension       Reading-Comprehension
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?
A
10
B
20
C
30
D
40
       Algorithms       Time-instance
Question 49 Explanation: 
A = n2 days = n2 × 24 × 60 × 60 sec
B = 2n 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 = 102 × 24 × 60 × 60 = 2400 × 3600 sec
B = 210 = 1024 sec
Wrong.
B) n=20
A = 202 × 24 × 60 × 60 = 34560000
B = 220 = 1048576
Wrong.
C) n=30,
A = 302 × 24 × 3600 = 77760000
B = 230 = 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?
A
insertion sort only
B
selection sort only
C
bubble sort and selection sort
D
bubble sort and insertion sort
       Algorithms       Sorting
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?
A
Kruskal's algorithm starts by finding an edge with the least weight
B
At any intermediate-stage, the output of Prim's algorithm is a tree
C
Kruskal's algorithm terminate once the output has (n - 1) edges
D
Prim's algorithm needs to check at each step if a cycle is formed
       Algorithms       Greedy-approach
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
A(n)= n log n and B(n)=nlog(n!)
B
A(n)=2n and B(n)=210
C
A(n)= 2logn and B(n)=n
D
A(n)=n2 and B(n)=n3
       Algorithms       Asymptotic-Complexity
Question 52 Explanation: 
Let’s check option wise,
A)
A(n) = n log n
B(n) = n log (n!) ≅ n log (nn) ≅ n2 log n
So, A(n) ≠ Ө(B(n))
But A(n) = O(B(n))
B)
A(n) = 2n
B(n) = 210
A(n) ≠ Ө(B(n))
A(n) = ᘯ(B(n))
C)
A(n) = 2logn = n
B(n) = n
∴ A(n) = Ө(B(n))
D)
A(n) = n2
B(n) = n3
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?
A
12
B
10
C
8
D
Cannot be computed
       Engineering-Mathematics       Graph-Theory
Question 53 Explanation: 
Total no. of vertices = x + 2 + 4 + 3 = 9 + x
In a tree of n vertices no. of edges is n-1.
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?
A
The length of every string produced by the grammar is even
B
No string produced by the grammar has an odd number of consecutive b's
C
No string produced by the grammar has three consecutive a's
D
No string produced by the grammar has four consecutive b's
       Theory-of-Computation       Languages-and-Grammars
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.
Question 55
Which of the following programming language features requires stack-based storage allocation rather than static allocation?
A
Recursive procedures
B
Call by Reference parameters
C
Arbitrary goto's
D
Two dimensional arrays
       Data-Structures       Queues-and-Stacks
Question 55 Explanation: 
Recursive procedures require stack based storage allocation.
Question 56
What is the postfix form of the expression in prefix form **AB-CD?
A
AB*CD-*
B
ABC**D-
C
ABC*D-*
D
AB**CD-
       Data-Structures       Prefix-Postfix-Expression
Question 56 Explanation: 
Let first draw tree from given prefix expression, * *AB-CD

Now the sequence for postfix traversal is (Left, Right, Root).
∴ The postfix expression is AB*CD-*
Question 57
The initial configuration of-a queue is a,b,c,d (a is at the front), To get the configuration d,b,c,a, one needs a minimum of
A
2 deletions and 3 insertions
B
3 deletions and 2 insertions
C
3 deletions and 3 insertions
D
3 deletions and 4 insertions
       Data-Structures       Queues-and-Stacks
Question 57 Explanation: 
< img src="https://solutionsadda.in/wp-content/uploads/2020/05/Screenshot_538.png">
< img src="https://solutionsadda.in/wp-content/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


A
12,6,3,30,85,67,95
B
6,3,12,30,85,95,67
C
12,3,6,85,30,95,67
D
30,6,3,12,85,67,95
       Data-Structures       Binary-search-tree
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,
Question 59

The running time of an algorithm is given by



Then T(n)=
A
O(n)
B
O(logn)
C
O(1)
D
O(n2)
       Algorithms       Time-Complexity
Question 59 Explanation: 
T(1) = 1
T(2) = 1
T(3) = 1
T(n) = T(n-1) + T(n-2) - T(n-3)
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
A
O(v)
B
O(1)
C
O(E)
D
O(V*E)
       Data-Structures       BFS-and-DFS
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
A
2i, 2i+1, 2i+2
B
3i, 3i+1, 3i+2
C
3i-1, 3i, 3i+1
D
3i+3, 3i+4, 3i+5
       Data-Structures       Arrays
Question 61 Explanation: 
Let take example of tertiary tree,

Now let’s check option C,
3i-1, 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?
A
integer variables
B
parameters to the function
C
static variables declared within the function
D
extern variables
       Programming       Functions
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?
A
Linked list
B
Indirect Access
C
Hashing
D
All of the above.
Question 64
Which of the scheduling algorithms does not result in starvation?
A
FCFS
B
Multilevel queues
C
Shortest Job First
D
Priority scheduling
       Operating-Systems       Process-Scheduling-algorithms
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.
Question 65
Waterfall model in software engineering is an example of a(n)
A
Linear
B
Rapid
C
Iterative
D
Interactive
       Software-Engineering       Types-of-Models
Question 65 Explanation: 
The Waterfall model in software engineering is an example of an iterative method.
Question 66
A system has a 24-bit 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?
A
8192
B
4096
C
2048
D
None of the above.
       Operating-Systems       Memory-Management
Question 66 Explanation: 
Lets first find offset bits,
2KB = 2^11 B. So offset bits = 11
Hence no. of page table entries is = 2^(24-11) = 2^13 = 8192
Question 67
A sequence d=(d1,d2,...,dn) is called graphic if there is a simple undirected graph with degree sequence d. Which of the following are not valid graphic sequences?
A
(2, 3, 3, 4, 4, 5)
B
(2, 3, 4, 4, 5)
C
(1, 3, 3, 3)
D
(1, 2, 2, 2,3)
       Engineering-Mathematics       Graph-Theory
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?
A
nC2
B
⌊n^2/4 ⌋
C
⌊n^2/2⌋
D
⌊n/2⌋
       Engineering-Mathematics       Graph-Theory
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
A
Cohesion metric
B
Complexity metric
C
Coupling metric
D
AIl of the above
       Software-Engineering       Cyclomatic-metric
Question 69 Explanation: 
Component-level 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 component-level design.
Question 70
Fault tolerance in software applications can be ensured through
A
Self-checking facility
B
Redundant modules
C
Recovery blocks
D
All of the above
       Operating-Systems       Fault-tolerance
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 four-variable Karnaugh maps.

F(A,B,C,D)=Σ(3,7,11, 13, 14, 15)
A
CD + ABC + ABD
B
ACD + BCD + ABC + ABD
C
ABC’D + ABC + CD
D
None of the above.
       Digital-Logic-Design       K-Map
Question 71 Explanation: 
Let first draw k-map and then we will find the Boolean function using k-map.

∴ 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
A
I only
B
II only
C
III only
D
II and III only
Question 73
Which of the following is not related to static testing?
A
Code Review
B
Code Walkthrough
C
Code Inspection
D
Code Execution
Question 74
A square matrix is stored either in row-major or column-major order. Which of the following statements is necessarily true?
A
The diagonal elements are stored in the same locations in either order
B
The elements in (i,j) locations where i and j are both odd are stored in the same locations
C
AII the elements in the last row are in the same locations
D
None of the above.
       Data-Structures       Arrays
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 8-bit 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.
A
-16
B
15
C
10
D
None of the above.
       Digital-Logic-Design       Number-Systems
Question 75 Explanation: 
The binary value of 210 = 11010010
The binary value of 56 = 00111000
Now let’s add two binary nos.,
There are 75 questions to complete.