ISRO Scientist/Engineer SC Computer Science 2020 — ISRO Scientist/Engineer SC 2020 · Computer Science

The immediate addressing mode can be used for

1. Loading internal registers with initial values.

2. Perform arithmetic or logical operation on data contained in instructions.

Which of the following is true ?

Assume a simplified word-addressed CPU with fixed-length, one-word, single-operand instructions during a sequential fetch. Each instruction word contains an opcode and an operand field held in the instruction register. Only the opcode field is transferred to the control unit for decoding; operand data remains in the datapath. Statements associated with registers of a CPU are given. Identify the false statement.

Convert the pre-fix expression to in-fix

–* + ABC* – DE + FG 

An array of 2 two byte integers is stored in big endian machine in byte address as shown below. What will be its storage pattern in little endian machine ?

Address Data
0 × 104 78
0 × 103 56
0 × 102 34
0 × 101 12 

A non-pipelined CPU has 12 general purpose registers (R0, R1, R2, ..... R12). Following operation are supported:

ADD Ra, Rb, Rr Add Ra to Rb and store the result in Rr
MUL Ra, Rb, Rr Multiply Ra to Rb and store the result in Rr 

MUL operations takes two clock cycles, ADD takes one clock cycle. Calculate minimum number of clock cycles required to compute the value of the expression XY + XYZ + YZ. The variables X, Y, Z are initially available in registers R0, R1 and R2 and contents of these registers must not be modified.

Consider a 5-segment pipeline with a clock cycle time of 20 ns for each sub-operation. Find the approximate speed-up ratio between the pipelined and non-pipelined systems when executing 100 instructions. For the stated approximation, treat one bubble due to a data hazard as occurring per five instructions, giving 20 one-cycle bubbles during the run.

Consider a 32-bit processor which supports 70 instructions. Each instruction is 32 bit long and has 4 fields namely opcode, two register identifiers and an immediate operand of unsigned integer type. Maximum value of the immediate operand that can be supported by the processor is 8191. How many registers the processor has ?

In a 8-bit ripple carry adder using identical full adders, each full adder takes 34 ns for computing sum. If the time taken for 8-bit addition is 90 ns, find time taken by each full adder to find carry.

As a full-adder output, the following multiplexer circuit implements which equation?

Minimum number of NAND gates required to implement the following binary equation Y = (A̅ + B̅)(C + D)

If ABCD is a 4-bit binary number, then what is code generated by the following circuit?

Circuit transcription: W = A; X = A XOR B; Y = B XOR C; Z = C XOR D. WXYZ are the four output bits in order.

The number of tokens in the following C code segment is

switch(inputvalue)
 {
  case 1 : b = c * d; break;
  default : b = b++; break;
 } 

In a two-pass assembler, resolution of subroutine calls and inclusion of labels in the symbol table is done during

A stack organised computer is characterised by instructions with

A computer issues instructions in order and has only two registers and three opcodes: ADD, SUB and MOV. Compare these two orders of a basic block: Case 1 Case 2 t1 = a + b; t2 = c + d; t2 = c + d; t3 = e - t2; t3 = e - t2; t1 = a + b; t4 = t1 - t3; t4 = t1 - t3; All inputs start in memory, and the final t4 must be stored in memory. Use two-address arithmetic: ADD R,s means R ← R + s and SUB R,s means R ← R - s, where the source s may be a register or memory operand. MOV is required for loads and stores. Execute each assignment exactly once in its listed order: do not eliminate an assignment or recompute a value. Intermediate results may remain in registers until needed. Which case needs fewer MOV instructions, and by how many?

Which one indicates a technique of building cross compilers?

Consider a 2-dimensional array x with 10 rows and 4 columns, with each element storing a value equivalent to the product of the row number and column number. Count row and column positions from 1 for the element values, although the array indices start at 0. The array is stored in row-major format. If the first element x[0][0] occupies the memory location with address 1000 and each element occupies only one memory location, which locations (in decimal) hold a value of 10?

What is the in-order successor of 15 in the given binary search tree? The tree has root 15, with left child 6 and right child 18. Node 6 has children 3 and 7; node 3 has children 2 and 4; node 7 has right child 13; node 13 has left child 9; and node 18 has children 17 and 20.

When height is counted as the number of levels, with the root at level 1, the minimum height of an AVL tree with n nodes is

The master theorem

Raymonds tree based algorithm ensures

The post-order traversal of a binary tree is ACEDBHIGF. The pre-order traversal is

In linear hashing, if the blocking factor bfr, loading factor i, and number of file buckets N are known, the number of records will be:

What is compaction refers to

The operating system and the other processes are protected from being modified by an already running process because

Which of the following algorithms defines time quantum ?

Dispatch latency is defined as

An aid to determine the deadlock occurrence is

Consider the following page reference string.

1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6 

What are the minimum number of frames required to get a single page fault for the above sequence assuming LRU replacement strategy ?

Three CPU-bound tasks have execution times of 15, 12, and 5 time units and arrive at times 0, t, and 8, respectively. If the operating system uses shortest remaining time first (SRTF) scheduling, what should the value of t be to produce four context switches? Ignore the context switches at time 0 and after the last task finishes.

G is an undirected graph with vertex set {v1, v2, v3, v4, v5, v6, v7} and edge set {v1v2, v1v3, v1v4, v2v4, v2v5, v3v4, v4v5, v4v6, v5v6, v6v7}. A breadth-first search (BFS) starts at v1. Which edge must be a BFS tree edge, regardless of the order in which each vertex’s neighbors are scanned?

If the array A contains the items 10, 4, 7, 23, 67, 12 and 5 in that order, what will be the resultant array A after third pass of insertion sort ?

Huffman tree is constructed for the following data: {A, B, C, D, E} with frequency {0.17, 0.11, 0.24, 0.33 and 0.15} respectively. 100 00 01 101 is decoded as

Given the grammar S → T * S | T T → U + T | U U → a | b Which of the following statements is wrong?

What is the tightest of the listed asymptotic upper bounds for the time complexity of the following code?

sum = 0;
for (i = 1; i <= n; i *= 2)
  for (j = 1; j <= n; j++)
    sum++;

Context free languages are closed under

Which of the following is true ?

The language which is generated by the grammar S → aSa|bSb|a|b over the alphabet {a, b} is the set of

Which of the following classes of languages can validate an IPv4 address in dotted decimal format? It is to be ensured that the decimal values are between 0 and 255

Minimum number of states required in DFA accepting binary strings not ending in “101” is

Which of the following is a type of a out-of-order execution, with the reordering done by a compiler

Which of the following is an efficient method of cache updating?

In a columnar transposition cipher, the plain text is “the tomato is a plant in the night shade family”, keyword is “TOMATO”. The cipher text is

Which option explicitly describes a large ciphertext change caused by a minimal change to the cryptographic key?

A magnetic disk has 100 cylinders, each with 10 tracks of 10 sectors. If each sector contains 128 Bytes, what is the maximum capacity of the disk in decimal kilobytes (1 kilobyte = 1000 bytes)?

How many total bits are required for a direct-mapped cache with 128 KB of data and 1 word block size, assuming a 32-bit address and 1 word size of 4 bytes ?

In a DBMS where TRUNCATE auto-commits but an uncommitted DELETE can be rolled back, which statement about DELETE and TRUNCATE is true?

One instruction tries to write an operand before it is written by previous instruction. This may lead to a dependency called

Assuming the relation is in 1NF and its primary key is its only candidate key, if every non-key attribute is fully functionally dependent on the whole primary key, what is the highest normal form guaranteed by these conditions?

What happens when this SQL query is executed? SELECT columns FROM TableA RIGHT OUTER JOIN TableB ON A.columnName = B.columnName WHERE A.columnName IS NULL

To send same bit sequence, NRZ encoding require

The persist timer is used in TCP to

How is the checksum field in a TCP segment computed?

If x + 2y = 30, then (2y/5 + x/3) + (x/5 + 2y/3) will be equal to

For the distributions given below :



Which of the following is correct for the above distributions ?

The hardware implementation which provides mutual exclusion is

In a networked distributed system, Remote Procedure Calls are used for communication between which processes?

Consider the following recursive C function that takes two arguments

unsigned int rer (unsigned int n, unsigned int r) {
  if (n > 0) return (n% r + rer(n/r, r));
  else return 0;
 } 

What is the return value of the function rer when it is called as rer (513, 2) ?

A given grammar is called ambiguous if

What is the output of the code given below?

#include <stdio.h>
int main( )
 {
   char name[ ]=“satellites”;
   int len;
   int size;
   len = strlen(name);
   size = sizeof(name);
   printf(“%d”, len * size);
   return 0;
 }

What is the output of the following ‘c’ code assuming it runs on a byte addressed little endian machine?

#include <stdio.h>
int main( )
 {
   int x; char *ptr;
   x = 622,100,101;
   printf("%d", (*(char *)&x) * (x % 3));
   return 0;
 } 

What is the output in a 32 bit machine with 32 bit compiler ?

#include <stdio.h>

rer(int **ptr2, int **ptr1)
 {
  int* ii;
  ii = *ptr2;
  *ptr2 = *ptr1;
  *ptr1 = ii;
  **ptr1 *= **ptr2;
  **ptr2 += **ptr1;
 }
void main( )
 {
   int var1 = 5, var2 = 10;
   int *ptr1 = &var1, *ptr2 = &var2;
   rer(&ptr1, &ptr2);
   printf(“%d %d “, var2, var1);
 } 

Regression testing is primarily related to

Of the following sort algorithms, which guarantees O(n log n) worst-case execution time and has execution time least dependent on initial ordering of the input?

The following circuit compares two 2-bit binary numbers, X and Y represented by X1X0 and Y1Y0 respectively. (X0 and Y0 represent Least Significant Bits)

Under what condition Z will be 1 ?

What is the defect rate for Six sigma ?

Consider the following pseudo-code:

I = 0; J = 0; K = 8;
 while (I < K – 1) //while-1
 {
   J = J + 1;
   while (J < K) //while-2
   {
    if (x[I] < x[J])
    {
     temp = x[I];
     x[I] = x[J];
     x[J] = temp;
    }
   } // end of while-2
  I = I +1;
} // end of while-1 

The cyclomatic complexity of the above is

In a class definition with 10 methods, to make the class maximally cohesive, number of direct and indirect connections required among the methods are

Of the following, which best approximates the ratio of the number of non-terminal nodes in the total number of nodes in a complete K-ary tree of depth N ?

A stack is implemented with an array of ‘A[0...N – 1]’ and a variable ‘pos’. The push and pop operations are defined by the following code.

push (x)
  A[pos] ← x
  pos ← pos – 1
end push

pop ( )
  pos ← pos + 1
  return A[pos]
end pop 

Which of the following will initialize an empty stack with capacity N for the above implementation ?

Given that

B(a) means “a is a bear”
F(a) means “a is a fish” and
E(a, b) means “a eats b” 

Then what is the best meaning of

∀x[F(x) ⇒ ∀y(E(y, x) ⇒ B(y))] 

An array contains ten elements of this structure, in the declared field order: struct complex { Short s; Byte b; Long l; Int i; }; complex C[10]; The sizes of Byte, Short, Int and Long are 1, 2, 4 and 4 bytes respectively. Each n-byte field begins at an address divisible by n. Use internal padding where needed, do not rearrange fields, and give each array element the smallest stride that is a multiple of 8 bytes and accommodates all fields. The base address of C is divisible by 8. What is the total size of C in bytes?

A grammar is defined as

A → BC
B → x⏐Bx
C → B⏐D
D → y⏐Ey
E → z 

The non-terminal alphabet of the grammar is

If A = {x, y, z} and B = {u, v, w, x}, and the universe is {s, t, u, v, w, x, y, z}. Then (A U B') ∩ (A ∩ B) is equal to

Consider the following circuit

The function by the network above is,

In the following procedure

Integer procedure P(X, Y);
Integer X,Y:
value x;
begin
  K = 5;
  L = 8;
  P = x + y;
end 

X is called by value and Y is called by name. If the procedure were invoked by the following program fragment

K = 0;
  L = 0;
  Z = P(K, L); 

then the value Z would be set equal to

Consider product of three matrices M1, M2 and M3 having w rows and x columns, x rows and y columns, and y rows and z columns. Under what condition will it take less time to compute the product as (M1M2)M3 than to compute M1(M2M3) ?

A new flip flop with inputs X and Y, has the following property.

Which of the following expresses the next state in terms of X, Y, current state ?