The goal of structured programming is to:

Consider the following C function.

void swap (int a, int b)
{
   int temp;
   temp = a;
   a = b;
   b = temp;
}

In order to exchange the values of two variables x and y.

A single array A[1..MAXSIZE] is used to implement two stacks. The two stacks grow from opposite ends of the array. Variables top1 and top2 (topl < top2) point to the location of the topmost element in each of the stacks. If the space is to be used efficiently, the condition for “stack full” is

The following numbers are inserted into an empty binary search tree in the given order: 10, 1, 3, 5, 15, 12, 16. What is the height of the binary search tree (the height is the maximum distance of a leaf node from the root)?

The best data structure to check whether an arithmetic expression has balanced parentheses is a

Level order traversal of a rooted tree can be done by starting from the root and performing

Given the following input (4322, 1334, 1471, 9679, 1989, 6171, 6173, 4199) and the hash function x mod 10, which of the following statements are true?

i) 9679, 1989, 4199 hash to the same value
ii) 1471, 6171 hash to the same value
iii) All elements hash to the same value
iv) Each element hashes to a different value

Which of the following grammar rules violate the requirements of an operator grammar? P,Q,R are nonterminals, and r,s,t are terminals.

(i) P → Q R
(ii) P → Q s R
(iii) P → ε
(iv) P → Q t R r

Consider a program P that consists of two source modules M₁ and M₂ contained in two different files. If M₁ contains a reference to a function defined in M₂, the reference will be resolved at

Consider the grammar rule E → E₁ - E₂ for arithmetic expressions. The code generated is targeted to a CPU having a single user register. The subtraction operation requires the first operand to be in the register. If E₁ and E₂ do not have any common sub expression, in order to get the shortest possible code

Consider the following statements with respect to user-level threads and kernel supported threads

(i) context switch is faster with kernel-supported threads
(ii) for user-level threads, a system call can block the entire process
(iii) Kernel supported threads can be scheduled independently
(iv) User level threads are transparent to the kernel

Which of the above statements are true?

Consider an operating system capable of loading and executing a single sequential user process at a time. The disk head scheduling algorithm used is First Come First Served (FCFS). If FCFS is replaced by Shortest Seek Time First (SSTF), claimed by the vendor to give 50% better benchmark results, what is the expected improvement in the I/O performance of user programs?

Let R₁(A,B,C) and R₂(D,E) be two relation schema, where the primary keys are shown underlined, and let C be a foreign key in R₁ referring to R₂. Suppose there is no violation of the above referential integrity constraint in the corresponding relation instances r₁ and r₂. Which one of the following relational algebra expressions would necessarily produce an empty relation?

Consider the following relation schema pertaining to a students database:

   Student (rollno, name, address)
   Enroll (rollno, courseno, coursename) 

Where the primary keys are shown underlined. The number of tuples in the Student and Enroll tables are 120 and 8 respectively. What are the maximum and minimum number of tuples that can be present in (Student * Enroll), where '*' denotes natural join ?

Choose the best matching between Group 1 and Group 2.

   Group-1   	  	  Group-2   
 P. Data link          1. Ensures reliable transport of data
                          over a physical point-to-point link
 Q. Network layer      2. Encoder/decodes data for physical
                          transmission
 R. Transport layer    3. Allows end-to-end communication
                          between two processes
                       4. Routes data from one network
                          node to the next

Which of the following is NOT true with respect to a transparent bridge and a router?

The Boolean function x'y' + xy + x'y is equivalent to

In an SR latch made by cross-coupling two NAND gates, if both S and R inputs are set to 0, then it will result in

If 73_x (in base-x number system) is equal to 54_y (in base-y number system), the possible values of x and y are

Which of the following addressing modes are suitable for program relocation at run time?

(i)  Absolute addressing     (ii) Based addressing
(iii) Relative addressing     (iv) Indirect addressing 

he minimum number of page frames that must be allocated to a running process in a virtual memory environment is determined by

How many 8-bit characters can be transmitted per second over a 9600 baud serial communication link using asynchronous mode of transmission with one start bit, eight data bits, two stop bits, and one parity bit?

Identify the correct translation into logical notation of the following assertion.

      "Some boys in the class are taller than all the girls"  

Note: taller(x,y) is true if x is taller than y.

Consider the binary relation:

       S = {(x,y)|y = x+1 and x,y ∈ {0,1,2, ...}}  

The reflexive transitive closure of S is

If a fair coin is tossed four times. What is the probability that two heads and two tails will result?

The number of different n × n symmetric matrices with each element being either 0 or 1 is: (Note: power(2,x) is same as 2^x)

Let A, B, C, D be n × n matrices, each with non-­zero determinant. If ABCD = 1, then B^-1 is

What is the result of evaluating the following two expressions using three-digit floating point arithmetic with rounding?

   (113. + -111.) + 7.51
   113. + (-111. + 7.51) 

The tightest lower bound on the number of comparisons, in the worst case, for comparison-based sorting is of the order of

The problems 3-SAT and 2-SAT are

Consider the following C function:

     int f(int n)
     {
        static int i = 1;
        if (n >= 5)
           return n;
        n = n+i;
        i++;
        return f(n);
     } 

The value returned by f(1) is

Consider the following program fragment for reversing the digits in a given integer to obtain a new integer. Let n = d₁d₂…d_m.

     int n, rev;
     rev = 0;
     while (n > 0)
     {
        rev = rev*10 + n%10;
        n = n/10;
     }

The loop invariant condition at the end of the ith iteration is:

Consider the following C program segment:

     char p[20];
     char *s = "string";
     int length = strlen(s);
     int i;
     for (i = 0; i < length; i++)
          p[i] = s[length — i];
     printf("%s",p); 

The output of the program is

It is desired to design an object-oriented employee record system for a company. Each employee has a name, unique id and salary. Employees belong to different categories and their salary is determined by their category. The functions to get Name, getld and compute salary are required. Given the class hierarchy below, possible locations for these functions are:

(i) getld is implemented in the superclass
(ii) getld is implemented in the subclass
(iii) getName is an abstract function in the superclass
(iv) getName is implemented in the superclass
(v) getName is implemented in the subclass
(vi) getSalary is an abstract function in the superclass
(vii) getSalary is implemented in the superclass
(viii) getSalary is implemented in the subclass

Choose the best design

Consider the label sequences obtained by the following pairs of traversals on a labeled binary tree. Which of these pairs identify a tree uniquely?

(i) preorder and postorder     (ii) inorder and postorder
(iii) preorder and inorder     (iv) level order and postorder 

A circularly linked list is used to represent a Queue. A single variable p is used to access the Queue. To which node should p point such that both the operations enQueue and deQueue can be performed in constant time?

The elements 32, 15, 20, 30, 12, 25, 16 are inserted one by one in the given order into a Max Heap. The resultant Max Heap is

Two matrices M₁ and M₂ are to be stored in arrays A and B respectively. Each array can be stored either in row-major or column-major order in contiguous memory locations. The time complexity of an algorithm to compute M₁ × M₂ will be

Suppose each set is represented as a linked list with elements in arbitrary order. Which of the operations among union, intersection, membership, cardinality will be the slowest?

Consider the following C program

     main()
     {   int x, y, m, n;
         scanf ("%d %d", &x, &y);
         /* Assume x > 0 and y > 0  */
         m = x; n = y;
         while (m! = n)
            {    if (m > n)
                   m = m - n;
                 else
                   n = n - m;
            } 
          print f ("% d", n);
          }

The program computes

What does the following algorithm approximate?(Assume m > 1, ε > 0).

     x = m;
     y = 1;
     while (x - y > ε)
           {          x = (x + y)/2;
                      y = m/x;
            }
     print(x); 

Consider the following C program segment

struct CellNode
{
  struct CelINode *leftchild;
  int element;
  struct CelINode *rightChild;
}
 
int Dosomething(struct CelINode *ptr)
{
    int value = 0;
    if (ptr != NULL)
    {
      if (ptr->leftChild != NULL)
        value = 1 + DoSomething(ptr->leftChild);
      if (ptr->rightChild != NULL)
        value = max(value, 1 + DoSomething(ptr->rightChild));
    }
    return (value);
}

The value returned by the function DoSomething when a pointer to the root of a non-empty tree is passed as argument is

Suppose we run Dijkstra’s single source shortest-path algorithm on the following edge weighted directed graph with vertex P as the source. In what order do the nodes get included into the set of vertices for which the shortest path distances are finalized?

Consider the grammar with the following translation rules and E as the start symbol.

E → E1 # T     {E.value = E1.value * T.value}
    |    T     {E.value = T.value}
T → T1 & F     {T.value = T1.value + F.value}
    |    F     {T.value = F.value}
F → num        {F.value = num.value}  

Compute E.value for the root of the parse tree for the expression: 2 # 3 & 5 # 6 & 4.

Consider the following set of processes, with the arrival times and the CPU-burst times given in milliseconds.

  Process   Arrival Time    Burst Time
     P1          0              5
     P2          1              3
     P3          2              3
     P4          4              1 

What is the average turnaround time for these processes with the preemptive shortest remaining processing time first (SRPT) algorithm?

Consider a system with a two-level paging scheme in which a regular memory access takes 150 nanoseconds, and servicing a page fault takes 8 milliseconds. An average instruction takes 100 nanoseconds of CPU time, and two memory accesses. The TLB hit ratio is 90%, and the page fault rate is one in every 10,000 instructions. What is the effective average instruction execution time?

Consider two processes P₁ and P₂ accessing the shared variables X and Y protected by two binary semaphores S_X and S_Y respectively, both initialized to 1. P and V denote the usual semaphone operators, where P decrements the semaphore value, and V increments the semaphore value. The pseudo-code of P₁ and P₂ is as follows:

P1 :
 While true do {
   L1 : ................
   L2 : ................
   X = X + 1;
   Y = Y - 1;
   V(SX);
   V(SY);             
 }
P2 :
 While true do {
   L3 : ................   
   L4 : ................
   Y = Y + 1;
   X = Y - 1;
   V(SY);
   V(SX);            
}

In order to avoid deadlock, the correct operators at L₁, L₂, L₃ and L₄ are respectively

A Unix-style i-node has 10 direct pointers and one single, one double and one triple indirect pointers. Disk block size is 1 Kbyte, disk block address is 32 bits, and 48-bit integers are used. What is the maximum possible file size?

The relation scheme Student Performance (name, courseNo, rollNo, grade) has the following functional dependencies:

   name, courseNo → grade
   rollNo, courseNo → grade
               name → rollNo
             rollNo → name 

The highest normal form of this relation scheme is

Consider the relation Student (name, sex, marks), where the primary key is shown underlined, pertaining to students in a class that has at least one boy and one girl. What does the following relational algebra expression produce? (Note: p is the rename operator).

The condition in join is "(sex = female ^ x = male ^ marks ≤ m)"

The order of an internal node in a B⁺ tree index is the maximum number of children it can have. Suppose that a child pointer takes 6 bytes, the search field value takes 14 bytes, and the block size is 512 bytes. What is the order of the internal node?

The employee information in a company is stored in the relation

Employee (name, sex, salary, deptName)
Consider the following SQL query
         Select deptName
                    From Employee
                    Where sex = 'M'
                    Group by deptName
                    Having avg (salary) > 
                       (select avg (salary) from Employee)

It returns the names of the department in which

A and B are the only two stations on an Ethernet. Each has a steady queue of frames to send. Both A and B attempt to transmit a frame, collide, and A wins the first backoff race. At the end of this successful transmission by A, both A and B attempt to transmit and collide. The probability that A wins the second backoff race is:

The routing table of a router is shown below:

 Destination     Sub net mask 	     Interface
 128.75.43.0 	 255.255.255.0 	        Eth0
 128.75.43.0 	 255.255.255.128 	Eth1
 192.12.17.5 	 255.255.255.255 	Eth3
 Default 	  	                Eth2 

On which interfaces will the router forward packets addressed to destinations 128.75.43.16 and 192.12.17.10 respectively?

Consider three IP networks A, B and C. Host H_A in network A sends messages each containing 180 bytes of application data to a host H_C in network C. The TCP layer prefixes a 20 byte header to the message. This passes through an intermediate net­work B. The maximum packet size, including 20 byte IP header, in each network is:

     A : 1000 bytes 
     B : 100 bytes 
     C : 1000 bytes

The network A and B are connected through a 1 Mbps link, while B and C are connected by a 512 Kbps link (bps = bits per second).

Assuming that the packets are correctly delivered, how many bytes, including headers, are delivered to the IP layer at the destination for one application message, in the best case? Consider only data packets.

Consider three IP networks A, B and C. Host H_A in network A sends messages each containing 180 bytes of application data to a host H_C in network C. The TCP layer prefixes a 20 byte header to the message. This passes through an intermediate net­work B. The maximum packet size, including 20 byte IP header, in each network is:

     A : 1000 bytes 
     B : 100 bytes 
     C : 1000 bytes

The network A and B are connected through a 1 Mbps link, while B and C are connected by a 512 Kbps link (bps = bits per second).

What is the rate at which application data is transferred to host H_C? Ignore errors, acknowledgements, and other overheads.

A circuit outputs a digit in the form of 4 bits. 0 is represented by 0000, 1 by 0001, ..., 9 by 1001. A combinational circuit is to be designed which takes these 4 bits as input and outputs 1 if the digit ≥ 5, and 0 otherwise. If only AND, OR and NOT gates may be used, what is the minimum number of gates required?

Which are the essential prime implicants of the following Boolean function?

 f(a,b,c) = aȼc + acȼ + bȼc 

Consider a multiplexer with X and Y as data inputs and Z as control input. Z = 0 selects input X, and Z = 1 selects input Y. What are the connections required to realize the 2-variable Boolean function f = T + R, without using any additional hardware?

Consider the partial implementation of a 2-bit counter using T flip-flops following the sequence 0-2-3-1-0, as shown below

To complete the circuit, the input X should be

A 4-bit carry lookahead adder, which adds two 4-bit numbers, is designed using AND, OR, NOT, NAND, NOR gates only. Assuming that all the inputs are available in both complemented and uncomplemented forms and the delay of each gate is one time unit, what is the overall propagation delay of the adder? Assume that the carry network has been implemented using two-level AND-OR logic.

Consider the following program segment for a hypothetical CPU having three user registers R1, R2 and R3.

 Instruction 	     Operation 	      Instruction Size(in words)
 MOV R1,5000; 	 ;R1 ← Memory[5000] 	         2
 MOV R2(R1); 	 ;R2 ← Memory[(R1)] 	         1
 ADD R2,R3; 	 ;R2 ← R2 + R3 	                 1
 MOV 6000,R2; 	 ;Memory[6000] ← R2 	         2
 HALT 	         ;Machine halts 	         1 

Consider that the memory is byte addressable with size 32 bits, and the program has been loaded starting from memory location 1000 (decimal). If an interrupt occurs while the CPU has been halted after executing the HALT instruction, the return address (in decimal) saved in the stack will be

Consider the following program segment for a hypothetical CPU having three user registers R1, R2 and R3.

 Instruction 	     Operation 	      Instruction Size(in words)
 MOV R1,5000; 	 ;R1 ← Memory[5000] 	         2
 MOV R2(R1); 	 ;R2 ← Memory[(R1)] 	         1
 ADD R2,R3; 	 ;R2 ← R2 + R3 	                 1
 MOV 6000,R2; 	 ;Memory[6000] ← R2 	         2
 HALT 	         ;Machine halts 	         1 

Let the clock cycles required for various operations be as follows:

Register to/ from memory transfer     : 3 clock cycles 
ADD with both operands in register    : 1 clock cycle 
Instruction fetch and decode          : 2 clock cycles per word  

The total number of clock cycles required to execute the program is

Consider a small two-way set-associative cache memory, consisting of four blocks. For choosing the block to be replaced, use the least recently used (LRU) scheme. The number of cache misses for the following sequence of block addresses is 8, 12, 0, 12, 8

Let A = 1111 1010 and B = 0000 1010 be two 8-bit 2's complement numbers. Their product in 2's complement is

The microinstructions stored in the control memory of a processor have a width of 26 bits. Each microinstruction is divided into three fields: a micro-operation field of 13 bits, a next address field (X), and a MUX select field (Y). There are 8 status bits in the inputs of the MUX.

How many bits are there in the X and Y fields, and what is the size of the control memory in number of words?

A hard disk with a transfer rate of 10 Mbytes/ second is constantly transferring data to memory using DMA. The processor runs at 600 MHz, and takes 300 and 900 clock cycles to initiate and complete DMA transfer respectively. If the size of the transfer is 20 Kbytes, what is the percentage of processor time consumed for the transfer operation?

A 4-stage pipeline has the stage delays as 150, 120, 160 and 140 nanoseconds respectively. Registers that are used between the stages have a delay of 5 nanoseconds each. Assuming constant clocking rate, the total time taken to process 1000 data items on this pipeline will be

The following propositional statement is (P → (Q v R)) → ((P v Q) → R)

How many solutions does the following system of linear equations have?

  -x + 5y = -1
   x - y = 2
   x + 3y = 3 

The following is the incomplete operation table a 4-element group.

The last row of the table is

The inclusion of which of the following sets into

S = {{1,2}, {1,2,3}, {1,3,5}, (1,2,4), (1,2,3,4,5}}

is necessary and sufficient to make S a complete lattice under the partial order defined by set containment?

An examination paper has 150 multiple-choice questions of one mark each, with each question having four choices. Each incorrect answer fetches -0.25 mark. Suppose 1000 students choose all their answers randomly with uniform probability. The sum total of the expected marks obtained by all these students is:

Mala has a colouring book in which each English letter is drawn two times. She wants to paint each of these 52 prints with one of k colours, such that the colour-pairs used to colour any two letters are different. Both prints of a letter can also be coloured with the same colour. What is the minimum value of k that satisfies this requirement?

In an M×N matrix such that all non-zero entries are covered in a rows and b columns. Then the maximum number of non-zero entries, such that no two are on the same row or column, is

The minimum number of colours required to colour the following graph, such that no two adjacent vertices are assigned the same colour, is

Two n bit binary strings, S₁ and S₂, are chosen randomly with uniform probability. The probability that the Hamming distance between these strings (the number of bit positions where the two strings differ) is equal to d is

How many graphs on n labeled vertices exist which have at least (n² - 3n)/2 edges?

A point is randomly selected with uniform probability in the X-Y plane within the rectangle with corners at (0,0), (1,0), (1,2) and (0,2). If p is the length of the position vector of the point, the expected value of p² is

Let G₁ = (V,E₁) and G₂ = (V,E₂) be connected graphs on the same vertex set V with more than two vertices. If G₁ ∩ G₂ = (V, E₁ ∩ E₂) is not a connected graph, then the graph G₁ U G₂ = (V, E₁ U E₂)

Let A[1,...,n] be an array storing a bit (1 or 0) at each location, and f(m) is a function whose time complexity is θ(m). Consider the following program fragment written in a C like language:

counter = 0;
for (i = 1; i < = n; i++)
{ if (A[i] == 1) counter++;
      else { f(counter); counter = 0; }
}

The complexity of this program fragment is

The time complexity of the following C function is (assume n > 0)

int recursive (int n) {
   if (n == 1)
   return (1);
   else
   return (recursive (n - 1) + recursive (n - 1));
} 

The recurrence equation

   T(1) = 1
   T(n) = 2T(n - 1) + n, n ≥ 2 

evaluates to

A program takes as input a balanced binary search tree with n leaf nodes and computes the value of a function g(x) for each node x. If the cost of computing g(x) is min{no. of leaf-nodes in left-subtree of x, no. of leaf-nodes in right-subtree of x} then the worst-case time complexity of the program is

The following finite state machine accepts all those binary strings in which the number of 1's and 0's are respectively.

The language {a^m bⁿ C^m+n | m, n ≥ 1} is

Consider the following grammar G:

S → bS| aA| b
A → bA| aB
B → bB| aS |a 

Let N_a(w) and N_b(w) denote the number of a's and b's in a string w respectively. The language L(G) ⊆ {a, b}⁺ generated by G is

L₁ is a recursively enumerable language over Σ. An algorithm A effectively enumerates its words as w₁, w₂, w₃, ... Define another language L₂ over Σ Union {#} as {w_i # w_j : w_i, w_j ∈ L₁, i < j}. Here # is a new symbol. Consider the following assertions.

S1: L1 is recursive implies L2 is recursive
S2: L2 is recursive implies L1 is recursive

Which of the following statements is true?

Choose the best matching between the programming styles in Group 1 and their characteristics in Group 2.

      Group-1		        Group-2 
 P. Functional	      1. Command-based, procedural
 Q. Logic	      2. Imperative, abstract data type
 R. Object-oriented   3. Side-effect free, declarative, expression evaluation
 S. Imperative	      4. Declarative, clausal representation, theorem proving