Nielit Scientist-B CS 22-07-2017

Question 1
What does the following functions do for a given Linked list with first node as head?
void fun1(Struct node* head)
{
if(head==NULL)
return;
fun1(head → next);
printf("%d".head → data);
}
A
Prints all nodes of linked lists
B
Prints all nodes of linked list in reverse order
C
Prints alternate nodes of Linked List
D
Prints alternate nodes in reverse order
       Data-Structures       Linked-List
Question 1 Explanation: 
Given pointer to the head node of a linked list, the task is to reverse the linked list. We need to reverse the list by changing links between nodes.
Input : Head of following linked list
1->2->3->4->NULL
Output : Linked list should be changed to,
4->3->2->1->NULL
Algorithm:
1. Initialize three pointers prev as NULL, curr as head and next as NULL.
2. Iterate through the linked list. In loop, do following.
// Before changing next of current,
// store next node
next = curr->next
// Now change next of current
// This is where actual reversing happens
curr->next = prev
// Move prev and curr one step forward
prev = curr
curr = next
Question 2
Which of the following statements is/are TRUE for an undirected graph?
P: Number of odd degree vertices is even
Q: Sum of degrees of all vertices is even
A
P only
B
Q only
C
Both P and Q
D
Neither P nor Q
       Engineering-Mathematics       Graph-Theory
Question 2 Explanation: 
Euler’s Theorem 3:
The sum of the degrees of all the vertices of a graph is an even number (exactly twice the number of edges).
In every graph, the number of vertices of odd degree must be even.
Question 3
Consider the following function that takes reference to head of a Doubly Linked List as parameter. Assume that a node of doubly linked list has previous pointer as prev and next pointer as next
void fun(struct node **head_ref)
{
struct node *temp=NULL;
Struct node *current=*head_ref;
while(current!=NULL)
{
 temp=current → prev;
 Current → prev=current → next;
 Current → next=temp;
 current=current → prev;
}
if(temp!=NULL)
*head_ref=temp → prev;
}
Assume that reference of head of following doubly linked list is passed to above function 1 <-->  2 <--> 3 <--> 4<--> 5 <--> 6. What should be the modified linked list after the function call?
A
1<-->2<-->4<-->3<-->6<-->5
B
5<-->4<-->3<-->2<-->1<-->6
C
6<-->5<-->4<-->3<-->2<-->1
D
6<-->5<-->4<-->3<-->1<-->2
       Data-Structures       Linked-List
Question 3 Explanation: 
Struct node *current=*head_ref; ---> This statement meant for storing start of linked list onto current pointer.
while(current!=NULL)
{
temp=current → prev;
Current → prev=current → next;
Current → next=temp;
current=current → prev;
}
The loop meant for traversing the entire list till to end by changing prev and next pointers of all nodes.
Change prev of the head (or start) and change the head pointer in the end.
Question 4
Let A be a square matrix of size nxn. consider the following program. What is the expected output?
C=100
for i=1 to n do
for j=1 to n do
{
 Temp=A[i][j]+C
 A[i][j]=A[j][i]
 A[j][i]=Temp-C
}
for i=1 to n do
for j=1 to n do
 output(A[i][j]);
A
The matrix A itself
B
Transpose of matrix A
C
Adding 100 to the upper diagonal elements and subtracting 100 from diagonal elements of A
D
None of the option
       Programming       Arrays
Question 4 Explanation: 
Question 5
Following is C like Pseudo code of a function that takes a number as an argument, and uses a stack S to do argument, and uses a stack S to do processing.
void fun(int n)
{
Stack s;//Say it creates an empty stack S
while(n>0)
{
 // This line pushes the value of n%2 to
 Stack S;
 Push(&S,n%2);
 n=n/2l
}
// Run while Stack S is not empty
while(!is Empty(&S)) Printf(%d",pop(&S));//pop an element from S and print it
}
What does the above function do in general order
A
Prints binary representation of n in reverse order
B
prints binary representation of n
C
Prints the value of Logn
D
Prints the value of Logn in reverse order
       Data-Structures       Queues-and-Stacks
Question 5 Explanation: 
For any number, we can check whether its ‘i’th bit is 0(OFF) or 1(ON) by bitwise ANDing it with “2^i” (2 raise to i).,
1) Let us take number 'NUM' and we want to check whether it's 0th bit is ON or OFF
bit = 2 ^ 0 (0th bit)
if NUM & bit == 1 means 0th bit is ON else 0th bit is OFF
2) Similarly if we want to check whether 5th bit is ON or OFF
bit = 2 ^ 5 (5th bit)
if NUM & bit == 1 means its 5th bit is ON else 5th bit is OFF.
Let us take unsigned integer (32 bit), which consist of 0-31 bits. To print binary representation of unsigned integer, start from 31th bit, check whether 31th bit is ON or OFF, if it is ON print “1” else print “0”. Now check whether 30th bit is ON or OFF, if it is ON print “1” else print “0”, do this for all bits from 31 to 0, finally we will get binary representation of number. void bin(unsigned n)
{
unsigned i;
for (i = 1 << 31; i > 0; i = i / 2)
(n & i)? printf("1"): printf("0");
}
int main(void)
{
bin(7);
printf("\n");
bin(4);
}
Question 6
Assume that the operators +,-,x are left associative and 6 right associative. the order of precedence(from highest to lowest) is 6,x,+,-. The postfix expression corresponding to the infix expression a+bxc-d^e^f is
A
abc x+def^^-
B
abc xde^f^-
C
ab +c xd -e^f ^
D
-+ a x bc ^^def
       Data-Structures       Queues-and-Stacks
Question 6 Explanation: 
a+bc-d^e^f
⟶ left to right
Step 1: abc+
Question 7
A balance factor in AVL tree is used to check
A
What rotation to make
B
if all childs nodes are at same level
C
when the last rotation occurred
D
if the tree is unbalanced
       Data-Structures       Binary-Trees
Question 7 Explanation: 
It is a self balancing tree with height difference at most 1. A balance factor in AVL tree is used to check what rotation to make.
Question 8
A priority queue is implemented as a Max-heap. Initially, it has 5 elements. The level-order traversal of the heap is: 10,8,5,3,2. Two new elements 1 and 7 are inserted into the heap in that order. The level-order traversal of the heap after the insertion of the elements is
A
10,8,7,3,2,1,5
B
10,8,7,2,3,1,5
C
10,8,7,1,2,3,5
D
10,8,7,5,3,2,1
       Data-Structures       Queues-and-Stacks
Question 8 Explanation: 
Max-Heap has 5 elements:
The level order traversal in this max heap final is:
10, 8, 7, 3, 2, 1, 5.
Question 9
The worst case running times of insertion sort, merge sort and quick sort respectively are
A
O(nlogn),O(nlogn) and O(n2)
B
O(n2),O(n2) and O(nlogn)
C
O(n2),O(nlogn) and O(nlogn)
D
O(n2),O(nlogn) and O(n2)
       Algorithms       Sorting
Question 9 Explanation: 
→ worst case running times of insertion sort → O(n2)
merge sort → O(nlogn)
quick sort → O(n2)
Question 10
A queue is implemented using an array such that ENQUEUE and DEQUEUE operations are performed efficiently. Which one of the following statements is CORRECT(n refers to the number of items in the QUEUE)?
A
Both operations can be performed in O(1) time
       Data-Structures       Queues-and-Stacks
Question 10 Explanation: 
Since it is mentioned in the question that both of the operations are performed efficiently. Hence even the worst case time complexity will be O(1) by the use of the Circular queue there won't be any need of shifting in the array.
Question 11
Consider the following graph L and find the bridges, if any.
A
No bridges
B
{d,e}
C
{c,d}
D
{c,d} and {c,f}
       Engineering-Mathematics       Graph-Theory
Question 11 Explanation: 
A bridge, ut-edge, or cut arc is an edge of a graph whose deletion increases its number of connected components.
Equivalently, an edge is a bridge if and only if it is not contained in any cycle.
A graph is said to be bridgeless or isthmus-free if it contains no bridges.
If we remove {d,e} edge then there is no way to reach e and the graph is disconnected.
The removal of edges {c,d} and {c,f} makes graph disconnect but this forms a cycle.
Question 12
The following graph nas no Euler circuit because
A
It has 7 vertices
B
It is even-valent(all vertices have even valence)
C
It is not connected
D
It does not have a Euler circuit
       Engineering-Mathematics       Graph-Theory
Question 12 Explanation: 
An Eulerian trail or Euler walk in an undirected graph is a walk that uses each edge exactly once. If such a walk exists, the graph is called traversable or semi-eulerian.
Important Properties:
→ An undirected graph has an Eulerian cycle if and only if every vertex has even degree, and all of its vertices with nonzero degree belong to a single connected component.
→ An undirected graph can be decomposed into edge-disjoint cycles if and only if all of its vertices have even degree. So, a graph has an Eulerian cycle if and only if it can be decomposed into edge-disjoint cycles and its nonzero-degree vertices belong to a single connected component.
→ An undirected graph has an Eulerian trail if and only if exactly zero or two vertices have odd degree, and all of its vertices with nonzero degree belong to a single connected component.
→ A directed graph has an Eulerian cycle if and only if every vertex has equal in degree and out degree, and all of its vertices with nonzero degree belong to a single strongly connected component. Equivalently, a directed graph has an Eulerian cycle if and only if it can be decomposed into edge-disjoint directed cycles and all of its vertices with nonzero degree belong to a single strongly connected component.
→ A directed graph has an Eulerian trail if and only if at most one vertex has (out-degree) − (in-degree) = 1, at most one vertex has (in-degree) − (out-degree) = 1, every other vertex has equal in-degree and out-degree, and all of its vertices with nonzero degree belong to a single connected component of the underlying undirected graph
Question 13
For the graph shown, which of the following paths is a Hamilton circuit?
A
ABCDCFDEFAEA
B
AEDCBAF
C
AEFDCBA
D
AFCDEBA
       Engineering-Mathematics       Graph-Theory
Question 13 Explanation: 
A Hamiltonian cycle, also called a Hamiltonian circuit, Hamilton cycle, or Hamilton circuit, is a graph cycle (i.e., closed loop) through a graph that visits each node exactly once. A graph possessing a Hamiltonian cycle is said to be a Hamiltonian graph.
Here, Option A: A,F and E are repeated several times.
Option B: It is not a cycle. It means, not closed walk
Option C: It is closed walk and all vertex traversed. So this is final answer.
Option D: It’s not a closed walk.
Question 14
If G is an undirected planar graph on n vertices with e edges then
A
e<=n
B
e<=2n
C
e<=en
D
None of the option
       Engineering-Mathematics       Graph-Theory
Question 14 Explanation: 
Euler's formula: states that if a finite, connected, planar graph is drawn in the plane without any edge intersections, and v is the number of vertices, e is the number of edges and f is the number of faces (regions bounded by edges, including the outer, infinitely large region), then
v − e + f = 2.
→ For a simple, connected, planar graph with v vertices and e edges and faces, the following simple conditions hold for v ≥ 3:
Theorem 1. e ≤ 3v − 6;
Theorem 2. If there are no cycles of length 3, then e ≤ 2v − 4.
Theorem 3. f ≤ 2v − 4.
Theorem (The handshaking theorem):
Let G be an undirected graph (or multigraph) with V vertices and N edges. Then

Exercise:
Suppose a simple graph has 15 edges, 3 vertices of degree 4, and all others of degree 3. How many vertices does the graph have?
3*4+(x-3)*3=30
Question 15
Choose the most appropriate definition of plane graph.
A
A simple graph which is isomorphic to hamiltonian graph
B
A graph drawn in a plane in such a way that if the vertex set of graph can be partitioned into two non-empty disjoint subset X and Y in such a way that each edge of G has one end in X and one end in Y
C
A graph drawn in a plane in such a way that any pair of edges meet only at their end vertices
D
None of the option
       Engineering-Mathematics       Graph-Theory
Question 15 Explanation: 
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints.
In other words, it can be drawn in such a way that no edges cross each other. Such a drawing is called a plane graph or planar embedding of the graph.
Question 16
Which of the following propositions is tautology.
A
(p Vq) → q
B
p V(q → p)
C
pV(p → q)
D
Both B) and C)
       Engineering-Mathematics       Propositional-Logic
Question 16 Explanation: 
Question 17
The digital multiplexer is basically a combination logic circuit to perform the operation
A
AND-AND
B
OR-OR
C
AND-OR
D
OR-AND
       Digital-Logic-Design       Combinational-Circuits
Question 17 Explanation: 
The equation for digital multiplexer includes AND and OR operations . For example AB+CD. So here firstly we have to solve AND operation then OR operation.
Question 18
In digital logic, if A B=C, then which one of the following is true?
A
A ⊕ C=B
B
B ⊕ C=A
C
A ⊕ B ⊕ C=0
D
Both A) and B)
       Digital-Logic-Design       Boolean-Algebra
Question 18 Explanation: 
Question 19
To make the following circuit a tautology?

marked box should be
A
OR gate
B
AND gate
C
NAND gate
D
EX-OR gate
       Digital-Logic-Design       Logic-Gates
Question 19 Explanation: 
The output f = (x+x')+(y+y').
Starting derivation using 'f'.
→ (x+x')+(y+y')
→ (x+y)+(x'+y')
→ (Already a known Input)+(x'+y')
So, the unknown input is (x'+y'). This can be made by :-
x and y fed into a NOT gate and then AND gate to become (x'+y').
So the answer is NAND gate.
Question 20
In the following gate network which gate is redundant?
A
Gate no.1
B
Gate no.2
C
Gate no.3
D
Gate no.4
       Digital-Logic-Design       Logic-Gates
Question 20 Explanation: 
Before Gate No. 4 being removed

Question 21
The combinational circuit given below is implemented with two NAND gates. To which of the following individual gates is its equivalent?
A
NOT
B
OR
C
AND
D
XOR
       Digital-Logic-Design       Combinational-Circuits
Question 21 Explanation: 
[(a.b)'. (a.b)' ]'= ((a.b)')' + ((a.b)')'
=(a.b)+(a.b)
=(a.b)
Question 22
What is the average access time for a Drum rotating at 4000 revolutions per minute?
A
2.5 milliseconds
B
5.0 milliseconds
C
7.5 milliseconds
D
4.0 milliseconds
       Computer-Organization       Secondary-Memory
Question 22 Explanation: 
→ 4000 revolution per minute means 60/4000 seconds for 1 revolution.
→ Average access time is time to complete 1/2 revolution= 7.5milliseconds.
Question 23
Comparing the time T1 taken for a single instruction on a pipelined CPU, with time T2 taken on a no-pipelined but identical CPU, we can say that___?
A
T1=T2
B
T1>T2
C
T1
D
T1 is T2 plus time taken for one instruction fetch cycle
       Computer-Organization       Pipelining
Question 23 Explanation: 
PIPELINING SYSTEM:
Pipelining is an implementation technique where multiple instructions are overlapped in execution. It has a high throughput (amount of instructions executed per unit time). In pipelining, many instructions are executed at the same time and execution is completed in fewer cycles. The pipeline is filled by the CPU scheduler from a pool of work which is waiting to occur. Each execution unit has a pipeline associated with it, so as to have work pre-planned. The efficiency of pipelining system depends upon the effectiveness of CPU scheduler.
NON- PIPELINING SYSTEM:
All the actions (fetching, decoding, execution of instructions and writing the results into the memory) are grouped into a single step. It has a low throughput. Only one instruction is executed per unit time and execution process requires more number of cycles. The CPU scheduler in the case of non-pipelining system merely chooses from the pool of waiting work when an execution unit gives a signal that it is free. It is not dependent on CPU scheduler.
Question 24
How many wires are threaded through the cores in a coincided-current core memory?
A
2
B
3
C
4
D
6
       Operating-Systems       Memory-Management
Question 24 Explanation: 
The most common form of core memory, X/Y line coincident-current, used for the main memory of a computer, consists of a large number of small toroidal ferrimagnetic ceramic ferrites (cores) held together in a grid structure (organized as a "stack" of layers called planes), with wires woven through the holes in the cores' centers.
In early systems there were four wires: X, Y, Sense, and Inhibit, but later cores combined the latter two wires into one Sense/Inhibit line. Each toroid stored one bit (0 or 1).
Question 25
Which access method is used for obtaining a record from cassette tape?
A
Direct
B
Sequential
C
Random
D
Parallel
       Operating-Systems       Memory-Management
Question 25 Explanation: 
Question 26
The process of converting the analog sample into discrete form is called
A
Modulation
B
Multiplexing
C
Quantization
D
Sampling
       Data-Communication       Sampling-Types
Question 26 Explanation: 
Sampling is the process of recording an analog signal at regular discrete moments of time.
sampling is the reduction of a continuous-time signal to a discrete-time signal. A common example is the conversion of a sound wave (a continuous signal) to a sequence of samples (a discrete-time signal).
Quantization in digital signal processing, is the process of mapping input values from a large set (often a continuous set) to output values in a (countable) smaller set, often with a finite number of elements.
The sampling rate fs is the number of samples per second.
The time interval between samples is called the sampling interval Ts=1/fs
Question 27
Which memory is difficult to interface with processor?
A
Static memory
B
Dynamic memory
C
ROM
D
None of the option
       Computer-Organization       Memory-Interfacing
Question 27 Explanation: 
Dynamic random-access memory (DRAM) is a type of random access semiconductor memory that stores each bit of data in a separate tiny capacitor within an integrated circuit.
The electric charge on the capacitors slowly leaks off, so without intervention the data on the chip would soon be lost.
To prevent this, DRAM requires an external memory refresh circuit which periodically rewrites the data in the capacitors, restoring them to their original charge. This refresh process is the defining characteristic of dynamic random-access memory, in contrast to static random-access memory (SRAM) which does not require data to be refreshed.
Question 28
For a memory system, the cycle time is
A
Same as the access time
B
Longer than the access time
C
Shorter than the access time
D
Multiple of the access time
       Computer-Organization       Memory-Interfacing
Question 28 Explanation: 
For Memory Access, Cycle time=Latency time+Transfer Time
Latency time is overhead of finding the right memory location and preparing to access it.
Transfer Time = Time required to transfer the data.
Hence cycle time is longer than access time
Question 29
In comparison with static RAM memory, the dynamic RAM memory has
A
Lower bit density and higher power consumption
B
Higher bit density and lower power consumption
C
Lower bit density and lower power consumption
D
None of the option
       Digital-Logic-Design       Combinational-Circuits
Question 29 Explanation: 
Dynamic memory uses capacitor for storing information, so it doesn't need constant power but it has higher bit density due to its configuration.
Question 30
If each address space represents one byte of storage space, how many address lines are needed to access RAM chips arranged in a 4 x 6 array, where each chip is 8K x 4 bits?
A
13
B
14
C
16
D
17
       Computer-Organization       Memory-Interfacing
Question 30 Explanation: 
Size of each Ram chip = 8K x 4 bits = 23 x 210x 22 ⇒ 215 bits = 212 bytes
Number of chips required = 6 x 4 = 24 = 5 bits
So, total number of bits required = 12 + 5 = 17 bits
Question 31
A CPU generates 32 bit virtual addresses. The page size is 4KB. The processor has a Translation Lookaside Buffer(TLB) which can hold a total of 128 page table entries and is 4-way set associative. The minimum size of the TLB tag is
A
11 bits
B
13 bits
C
15 bits
D
20 bits
       Operating-Systems       Memory-Management
Question 31 Explanation: 
Page size = 4 KB = 4 × 210 Bytes = 212 Bytes
Virtual Address = 32 bit
No. of bits needed to address the page frame = 32 - 12 = 20
TLB can hold 128 page table entries with 4-way set associative
⇒ 128/4=32=25
→ 5 bits are needed to address a set.
→ The size of TLB tag = 20 - 5 = 15 bits
Question 32
Computer uses 46-bit virtual address, 32 bit physical address, and a three level paged page table organization. The page table base register stores the base address of the first level table(T1), which occupies exactly one page. Each entry of T1 stores the base address of a page of the second level table (T2). Each entry of T2 stores the base address of a page of the third level table(T3). Each entry of T3 stores a page table entry(PTE). The PTE is 32 bits in size, The processor used in the computer has a 1MB 16 way set associative virtually indexed physically tagged cache. the cache block size is 64 bytes. What is the size of a page in KB in this computer?
A
2
B
4
C
8
D
16
       Operating-Systems       Memory-Management
Question 32 Explanation: 
Architecture of physically indexed cache:

VIPT cache and aliasing effect and synonym.
Alias: Same physical address can be mapped to multiple virtual addresses.
Synonym: Different virtual addresses mapped to same physical address (for data sharing).
So these synonyms should be in same set to avoid write-update problems.
In our problem VA = 46bits

We are using 16 bits for indexing into cache.
To have two synonym is same set we need to have same 16 bits index for PA & VA.
Assume that physical pages are colored and each set should have pages of same color so that any synonyms are in same set.
Since page size = 8KB ⇒ 13 bits
These 13bits are not translated during VA→PA. So 13 bits are same out of 16 Index bits, 13 are same we need to make 3 bits (16-13) same now.
3 bits can produce, 23 = 8 combinations which can be mapped on the different sets, so we need 8 different colors to color our pages. >br> In physically indexed cache indexing is done via physical address bits, but in virtual indexed cache, cache is indexed from (offset + set) bits. In physical Index cache indexing is done one to one (1 index maps to one page in one block of cache). In VIPT we have more/ extra bits, so mapping is not one-one. Hence these extra bits have to be taken care, such that if two virtual address refers to same page in cache block of different sets then they have to be assumed same i.e., we say of same color and put same color page in one set to avoid write update problems.
Question 33
Consider data given in the above question. What is the minimum number of page colours needed to guarantee that no two synonyms map to different sets in the processor cache of this computer?
A
2
B
4
C
8
D
16
       Computer-Organization       Machine-Instructions
Question 33 Explanation: 
1 MB 16-way set associative virtually indexed physically tagged cache(VIPT).
The cache block size is 64 bytes.
Question 34
A disk has 200 tracks(numbered 0 through 199). At a given time, it was servicing the request of reading data from track 120 and at the previous request, service was for track 90. The pending requests(in order of their arrival) are for track numbers 30 70 115 130 110 80 20 25. How many times will the head change its direction for the disk scheduling policies SSTF(Shortest Seek Time First) and FCFS(First come first serve)?
A
2 and 3
B
3 and 3
C
3 and 4
D
4 and 4
       Computer-Organization       Secondary-Memory
Question 34 Explanation: 
According to Shortest Seek Time First:
90-> 120-> 115-> 110-> 130-> 80-> 70-> 30-> 25-> 20
Change of direction(Total 3); 120->15; 110->130; 130->80
According to First Come First Serve:
90-> 120-> 30-> 70-> 115-> 130-> 110-> 80-> 20-> 25
Change of direction(Total 4); 120->30; 30->70; 130->110;20->25
Question 35
Consider the following snapshot of a system running n processes. Process i is holding Xi instances of a resource R, 1<=i<=n. Currently, all instances of R are occupied. Further, for all i, process i has placed a request for an additional Yi instances while holding the Xi instances it already p and q such that Yp=Yp=0. which one of the following can serve as a necessary condition to guarantee that the system is not approaching a deadlock?
A
min(Xp,Xq)i)where i!=p and i!=q
B
Xp+Xq>=min(Yi)where i!=p and i!=q
C
max(Xp,Xq) >1
D
min(Xp,Xq)>1
       Operating-Systems       Deadlock
Question 35 Explanation: 
Deadlock refers stops the execution of process due to non-availability of resources.
→ When two (or) more processes waiting for another process to release the resources.
→ P and Q can execute if they have sufficient resources, they don’t wait for extra resources (i.e., Xp+ Xq) required.
→ Option B can satisfies the corresponding equation i.e., Xp+ Xq >= min(Yk) where k != p and k != q.
Here we have sufficient resources.
Question 36
A system has n resources R0,..,Rn-1 and k processes P0,..Pk-1. The implementation of the resources request logic of each process P
i is a follows:
if(i%2==0)
{
if(i<n) request Ri
if(i+2 <n) request Ri+2
}
else
{
if(i<n) request Rn-i
if(i+2 < n) request Rn-i-2
}
In which one of the following situations is a deadlock possible?
A
n=40, k=26
B
n=21, k=12
C
n=20, k=10
D
n=41, k=19
       Operating-Systems       Deadlock
Question 36 Explanation: 
Consider the case where i = 10 & i = 11, n = 21 & k = 12
P10 requests R10 & R11
P11 requests R10 & R8
Hence P10 & P11 inorder in deadlock.
Question 37
A system contains three programs and each requires three tape units for its operation. The minimum number of tape units which the system must have such that deadlocks never arise is__
A
6
B
7
C
8
D
9
       Operating-Systems       Deadlock
Question 37 Explanation: 
Three programs and each requires 3 tapes.
We will allocate minimum two tapes to each program then total tapes are 6 and each program requires one more tape to complete its operation.
So, we will allocate one tape to one program and that program will complete its operation.
After completion of operation of one program, all tapes allocated to that program are free. So no need of the extra tape to complete action.
Minimum tapes required are=(3*2 tape units) + 1 tape unit = 7
Question 38
Which of the following standard algorithms is not Dynamic Programming based?
A
Bellman ford algorithm for single source shortest path
B
floyd Warshall for all pairs shortest paths
C
0-1 knapsack problem
D
Prim’s minimum spanning tree
       Algorithms       Dynamic-Programming
Question 38 Explanation: 
Prim’s minimum spanning tree is following greedy technique.
Question 39
Kadane algorithm is used to find
A
Maximum sum subsequence in an array
B
Maximum sum subarray in an array
C
Maximum product subsequence in an array
D
Maximum product subarray in an array
       Algorithms       Dynamic-Programming
Question 39 Explanation: 
Kadane algorithm is used to find the maximum sum subarray in an array. It runs in O(n) time complexity Implementation in python:
def max_subarray(A):
max_ending_here = max_so_far = A[0]
for x in A[1:]:
max_ending_here = max(x, max_ending_here + x)
max_so_far = max(max_so_far, max_ending_here)
return max_so_far
Question 40
Four matrices M1, M2, M3 and M4 of dimensions pxq, qxr, rxs and sxt respectively can be multiplied is several ways with different number of total scalar multiplications. For example, when multiplied as ((M1 X M2) X (M3 X M4)), the total number of multiplications is pqr + rst + prt. When multiplied as (((M1 X M2) X M3) X M4), the total number of scalar multiplications is pqr + prs + pst. If p = 10, q = 100, r = 20, s = 5 and t = 80, then the number of scalar multiplications needed is
A
248000
B
44000
C
19000
D
25000
Question 40 Explanation: 


Question 41
Let G be a graph with n vertices and m edges. What is the tightest upper bound on the running time on DFS of G? Assume that the graph is represented using adjacency matrix
A
O(n)
B
O(m+n)
C
O(n^2)
D
O(mn)
       Data-Structures       Graphs
Question 41 Explanation: 
DFS visits each vertex once and as it visits each vertex, we need to find all of its neighbours to figure out where to search next. Finding all its neighbours in an adjacency matrix requires O(V) time, so overall the running time will be O(V2).
Question 42
Which one of the following is a key factor for preferring B+-trees to binary search trees for indexing database relations?
  1. Database relations have a large number of records
  2. Database relations are sorted on the primary key
  3. B-trees require less memory than binary search trees
  4. Data transfer from disks is in blocks
A
Database relations have a large number of records
B
Database relations are sorted on the primary key
C
B-trees require less memory than binary search trees
D
Data transfer from disks is in blocks
       Database-Management-System       B-and-B+-Trees
Question 42 Explanation: 
A B+ tree is an N-ary tree with a variable but often large number of children per node. A B+ tree consists of a root, internal nodes and leaves.
The root may be either a leaf or a node with two or more children.
The primary value of a B+ tree is in storing data for efficient retrieval in a block-oriented storage context — in particular, filesystems.
This is primarily because unlike binary search trees, B+ trees have very high fanout (number of pointers to child nodes in a node,typically on the order of 100 or more), which reduces the number of I/O operations required to find an element in the tree.
Question 43
The cyclomatic complexity of each of the modules A and B shown below is 10. what is the cyclomatic complexity of the sequential integration shown on the right hand side?
A
19
B
21
C
20
D
10
       Software-Engineering       COCOMO-Model
Question 43 Explanation: 
Cyclomatic complexity is a software metric used to indicate the complexity of a program.
It is a quantitative measure of the number of linearly independent paths through a program's source code.
Cyclomatic Complexity of module = Number of decision points of program + 1
Number of decision points in module-A = 10 - 1 = 9
Number of decision points in module-B = 10 - 1 = 9
Cyclomatic Complexity of the integration(both A and B) = Number of decision points + 1
= (9 + 9) + 1
= 19
Question 44
What is the appropriate pairing items in the two columns listing various activities encountered in a software life cycle?  
A
P-3, Q-2,R-4,S-1
B
P-2,Q-3,R-1,S-4
C
P-3,Q-2,R-1,S-4
D
P-2,Q-3,R-4,S-1
       Software-Engineering       SDLC
Question 44 Explanation: 
A requirement is a capability to which a project outcome (product or service) should conform and cover functional and non-functional aspects of a system.
Requirements Capture is the process of analysing and identifying the requirements of a system and often involves a series of facilitated workshops attended by stakeholders of the system.
Software maintenance in software engineering is the modification of a software product after delivery to correct faults, to improve performance or other attributes.
Software design is the process by which an agent creates a specification of a software artifact, intended to accomplish goals, using a set of primitive components and subject to constraints.
Implementation is the realization of an application, or execution of a plan, idea, model, design, specification, standard, algorithm, or policy.
Question 45
Consider the following four schedules due to three transactions (indicated by the subscript) using read and write on a data item x, denoted by r(x) and w(x) respectively. Which one of them is conflict serializable.
  1. r1(x); r2(x); w1(x); r3(x); w2(x)
  2. r2(x); r1(x); w2(x); r3(x); w1(x)
  3. r3(x); r2(x); r1(x); w2(x); w1(x)
  4. r2(x); w2(x); r3(x); r1(x); w1(x)
A
1
B
2
C
3
D
4
       Database-Management-System       Transactions
Question 45 Explanation: 



Question 46
What is the maximum number of reduce moves that can be taken by a bottom up parser for a grammar with no epsilon and unit production(i.e., of type A →   and A →  a) to parse a string with n tokens?
A
n/2
B
n-1
C
2n-1
D
2n
       Compiler-Design       Parsers
Question 46 Explanation: 
Since it is given that the grammar cannot have:
1) epsilon production
2) production of the form A → a
Consider the grammar:
S → Sa | a
If we were to derive the string “aaa” whose length is 3 then the number of reduce moves that would have been required are shown below:
S→ Sa
→Saa
→aaa
This shows us that it has three reduce moves. The string length is 3 and the number of reduce moves is also 3. So presence of such kinds of production might give us the answer “n” for maximum number of reduce moves. But these productions are not allowed as per the question.
Also note that if a grammar does not have unit production then the maximum number of reduce moves can not exceed “n” where “n” denotes the length of the string.
3) No unit productions
Consider the grammar:
S→ A
A→ B
B→C
C→a
If we were to derive the string “a” whose length is 1 then the number of reduce moves that would have been required are shown below:
S→ A
A→ B
B→C
C→a
This shows us that it has four reduce moves. The string length is 1 and the number of reduce moves is 4. So presence of such kind of productions might give us the answer “n+1” or even more, for maximum number of reduce moves. But these productions are not allowed as per the question.
Now keeping in view the above points suppose we want to parse the string “abcd”. (n = 4) using bottom-up parsing where strings are parsed finding the rightmost derivation of a given string backwards. So here we are concentrating on deriving rightmost derivations only.
We can write the grammar which accepts this string which in accordance to the question, (i.e., with no epsilon- and unit-production (i.e., of type A → є and A → B) and no production of the form A→a) as follows:
S→aB
B→bC
C→cd
The Right Most Derivation for the above is:
S → aB (Reduction 3)
→ abC (Reduction 2)
→ abcd (Reduction 1)
We can see here the number of reductions present is 3.
We can get less number of reductions with some other grammar which also doesn’t produce unit or epsilon productions or production of the form A→a:
S→abA
A→ cd
The Right Most Derivation for the above is:
S → abA (Reduction 2)
→ abcd (Reduction 1)
Hence 2 reductions.
But we are interested in knowing the maximum number of reductions which comes from the 1st grammar. Hence total 3 reductions as maximum, which is (n – 1) as n = 4 here.
Question 47
What is the complement of the language accepted by the NFA shown below?
1.∅
2.{∈}
3.a*
4.{a, ∈}
A
1
B
2
C
3
D
4
       Theory-of-Computation       Finite-Automata
Question 47 Explanation: 
The Σ= {a} and the given NFA accepts the strings {a, aa, aaa, aaaa, ……….} i.e. the language accepted by the NFA can be represented by the regular expression: {a+}
Hence the complement of language is: {a* − a+} = {ϵ}
Question 48
In a compiler, keywords of a language are recognized during
A
Parsing of the program
B
the code generation
C
the lexical analysis of the program
D
dataflow analysis
       Compiler-Design       Compilers
Question 48 Explanation: 
Lexical analysis is the first phase of a compiler. It takes the modified source code from language preprocessors that are written in the form of sentences.
The lexical analyzer breaks these syntaxes into a series of tokens, by removing any whitespace or comments in the source code.
In programming language, keywords, constants, identifiers, strings, numbers, operators and punctuations symbols can be considered as tokens.
Question 49
Match the problem domains in GROUP I with the solution technologies in GROUP II
A
P-1,Q-2,R-3,S-4
B
P-3,Q-4,R-2,S-1
C
P-3,Q-1,R-4,S-2
D
P-4,Q-3,R-2,S-1
       Web-Technologies       XML
Question 49 Explanation: 
Extensible Markup Language (XML) is a markup language that defines a set of rules for encoding documents in a format that is both human-readable and machine-readable.
Interoperability is a characteristic of a product or system, whose interfaces are completely understood, to work with other products or systems, at present or in the future, in either implementation or access, without any restrictions.
Service-oriented computing (SOC) is the computing paradigm that utilizes services as fundamental elements for developing applications/solutions.
To build the service model, SOC relies on the service oriented architecture (SOA), which is a way of reorganizing software applications and infrastructure into a set of interacting services
Question 50
A company needs to develop a strategy for software product development for which it has a choice of two programming languages L1 and L2. The number of lines of code (LOC) developed using L2 is estimated to be twice the LOC developed with Ll. The product will have to be maintained for five years. Various parameters for the company are given in the table below

A
4000
B
5000
C
4333
D
4667
       Software-Engineering       LOC
Question 50 Explanation: 
Let LOC of L1=x, so LOC of L2=2x
Now,
(x/10000)*1000000 + 5*100000 = (2x/10000)*750000 + 5*50000
Solving for x, we get x =5000
Question 51
A company needs to develop digital signal processing software for one of its newest inventions. The software is expected to have 40000 lines of code. The company needs to determine the effort in person-months needed to develop this software using the basic COCOMO model. The multiplicative factor for this model is given as 2.8 for the software development on embedded systems, while the exponentiation factor is given as 1.20. What is the estimated effort in person-months?
A
234.25
B
932.50
C
287.80
D
122.40
       Software-Engineering       COCOMO-Model
Question 51 Explanation: 
The Constructive Cost Model (COCOMO) is an algorithmic software cost estimation model developed by Barry Boehm. The model uses a basic regression formula, with parameters that are derived from historical project data and current project characteristics
In the Constructive Cost Model (COCOMO), following is formula for effort applied
Effort Applied (E) = ab(KLOC)b [ person-months ]
= 2.8 x(40)1.20
= 2.8 x 83.65
= 234.25
Question 52
Which one of the following is NOT desired in a good software requirement specifications(SRS) document?
A
Functional requirements
B
Non Functional requirements
C
Goals of implementation
D
Algorithm for software implementation
       Software-Engineering       Software-requirements
Question 52 Explanation: 
The software requirements specification document is a requirements specification for a software system, is a complete description of the behavior of a system to be developed and may include a set of use cases that describe interactions the users will have with the software. In addition it also contains non-functional requirements. Non-functional requirements impose constraints on the design or implementation (such as performance engineering requirements, quality standards, or design constraints)
An SRS document should clearly document the following aspects of a system: Functional Requirements, Non-Functional Requirements and Goals of implementation
Question 53
In a complete k-array, every internal node has exactly k children. The number of leafs in such a tree with n internal nodes is
A
nk
B
(n-1)k+1
C
n(k-1)+1
D
n(k-1)
       Data-Structures       Trees
Question 53 Explanation: 
Total nodes = nk+1 (1 for root)
Leaves = total nodes - internal nodes
= nk+1-n
= n(k-1)+1
Question 54
Suppose T(n)=2T(n/2)+n, T(0)=T(1)=1 which one of the following is false?
A
T(n)=O(n2)
B
T(n)=O(nlogn)
Question 54 Explanation: 
Question 55
The part of machine level instruction, which tells the central processor what has to be done, is
A
Operation code
B
Address
C
locator
D
Flip flop
       Computer-Organization       Machine-Instructions
Question 55 Explanation: 
An opcode (abbreviated from operation code) is the portion of a machine language instruction that specifies the operation to be performed. Beside the opcode itself, most instructions also specify the data they will process, in the form of operands.
In addition to opcodes used in the instruction set architectures of various CPUs, which are hardware devices, they can also be used in abstract computing machines as part of their byte code specifications.
A flip-flop or latch is a circuit that has two stable states and can be used to store state information. A flip-flop is a bistable multivibrator. The circuit can be made to change state by signals applied to one or more control inputs and will have one or two outputs
Question 56
A system program that combines the separately compiled modules of a program into a form suitable for execution
A
Assembler
B
linking loader
C
cross compiler
D
load and go
       Compiler-Design       Linker-Loader
Question 56 Explanation: 
An assembler is a type of computer program that interprets software programs written in assembly language into machine language, code and instructions that can be executed by a computer.
A loader which combines the functions of a relocating loader with the ability to combine a number of program segments that have been independently compiled into an executable program.
A cross compiler is a compiler capable of creating executable code for a platform other than the one on which the compiler is running.
Question 57
Bug means
A
A logical error in a program
B
A difficult syntax error in a program
C
Documenting programs using an efficient documentation tool
D
All of the above
       Software-Engineering       Basics
Question 57 Explanation: 
A bug is an error in a software program. It may cause a program to unexpectedly quit or behave in an unintended manner. For example, a small bug may cause a button within a program's interface not to respond when you click it. A more serious bug may cause the program to hang or crash due to an infinite calculation or memory leak.
Question 58
Let L be a language and L' be its complement. Which one of the following is NOT a viable possibility?
A
Neither L nor L' is RE
B
One of L and L' is RE but not recursive;The other is not RE
C
Both L and L' are RE but not recursive
D
Both L and L' are recursive
       Theory-of-Computation       Recursive-and-Recursively-Enumerable-Language
Question 58 Explanation: 
If both L and L’ are recursively enumerable, then L must be recursive. Hence, both L and L´ are recursively enumerable, but not recursive is not a viable possibility.
Question 59
Let L1 be a recursive language, and let L2 be a recursively enumerable but not a recursive language. Which one of the following is TRUE?
A
L1′ is recursive and L2′ is recursively enumer­able
B
L1′ is recursive and L2′ is not recursively enumerable
C
L1′ and L2′ are recursively enumerable
D
L1′ is recursively enumerable and L2′ is recursive
       Theory-of-Computation       Recursive-and-Recursively-Enumerable-Language
Question 59 Explanation: 
Recursive languages are closed under complementation.
But, recursive enumerable languages are not closed under complementation.
If L1 is recursive, then L1', is also recursive.
If L2 is recursive enumerable, then L2', is not recursive enumerable language.
There are 59 questions to complete.