Previous Year Questions
1 paper · 120 questions — organised by subject with solutions and explanations.
🎯 Practice smarter, not harder
Just sign in to unlock everything. Free for all students.
Consider the following function: int unknown(int n){ int i, j, k=0; for (i=n/2; i<=n; i++) for (j=2; j<=n; j=j*2) k = k + n/2; return (k); } The return value of the function is
Which one of the following is the tightest upper bound that represents the number of swaps required to sort n numbers using selection sort?
What is the time complexity of Bellman-Ford single-source shortest path algorithm on a complete graph of n vertices?
The number of elements that can be sorted in time using heap sort is
Which of the following sorting algorithms has the minimum running time complexity in the best and average case?
Shift reduce parsing belongs to a class of
Consider the following two sets of LR(1) items of an LR(1) grammar. \\ X .cX, c∕ d& X → .cX, \ $ Which of the following statements related to merging of the two sets in the corresponding LALR parser i
Which of the following productions eliminate left recursion in the productions given below:
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 and ) to parse a string with n tokens?
The following code segment is executed on a processor which allows only register operands in its instructions. Each instruction can have atmost two source operands and one destination operand. Assume
The following code segment is executed on a processor which allows only register operands in its instructions. Each instruction can have atmost two source operands and one destination operand. Assume
Using public key cryptography, X adds a digital signature to message M, encrypts , and sends it to Y, where it is decrypted. Which one of the following sequences of keys is used for the operations?
What will be the cipher text produced by the following cipher function for the plain text ISRO with key k=7. [ Consider ]
What is the maximum number of characters (7 bits + parity) that can be transmitted in a second on a 19.2 Kbps line. This asynchronous transmission requires 1 start bit and 1 stop bit.
The protocol data unit for the transport layer in the internet stack is
In an IPv4 datagram, the M bit is 0, the value of HLEN is 10, the value of total length is 400 and the fragment offset value is 300. The position of the datagram, the sequence numbers of the first and
How many check bits are required for 16 bit data word to detect 2 bit errors and single bit correction using hamming code?
Which algorithm is used to shape the bursty traffic into a fixed rate traffic by averaging the data rate?
Assume that source S and destination D are connected through two intermediate routers labeled R. Determine how many times each packet has to visit the network layer and the data link layer during a tr
Which of the following encryption algorithms is based on the Feistal structure?
What is IP class and number of sub-networks if the subnet mask is 255.224.0.0?
IEEE 1394 is related to
In the Ethernet, which field is actually added at the physical layer and is not part of the frame.
The voltage ranges for a logic high and a logic low in RS-232 C standard is
The transport layer protocols used for real time multimedia, file transfer, DNS and email, respectively are
If the frame to be transmitted is 1101011011 and the CRC polynomial to be used for generating checksum is , than what is the transmitted frame?
Ethernet layer-2 switch is a network element type which gives.
What will be the efficiency of a Stop and Wait protocol, if the transmission time for a frame is 20ns and the propagation time is 30ns?
Determine the maximum length of the cable (in km) for transmitting data at a rate of 500 Mbps in an Ethernet LAN with frames of size 10,000 bits. Assume the signal speed in the cable to be 2,00,000 km
IPv6 does not support which of the following addressing modes?
A packet filtering firewall can
Consider the following sequence of micro-operations. MBR PC MAR X PC Y Memory MBR Which one of the following is a possible operation performed by this sequence?
A RAM chip has a capacity of 1024 words of 8 bits each (1K x 8). The number of 2 x 4 decoders with enable line needed to construct a 16K x 16 RAM from 1K x 8 RAM is
Consider a hard disk with 16 recording surfaces (0-15) having 16384 cylinders (0-16383) and each cylinder contains 64 sectors (0-63). Data storage capacity in each sector is 512 bytes. Data are organi
In 8085 microprocessor, the ISR for handling trap interrupt is at which location?
In case of a DVD, the speed of data transfer is mentioned in multiples of?
In 8086, the jump condition for the instruction JNBE is?
In a k-way set associative cache, the cache is divided into v sets, each of which consists of k lines. The lines of a set are placed in sequence one after another. The lines in set s are sequenced bef
A pipeline P operating at 400 MHz has a speedup factor of 6 and operating at 70% efficiency. How many stages are there in the pipeline?
Consider an instruction pipeline with five stages without any branch prediction: Fetch Instruction (FI), Decode Instruction (DI), Fetch Operand (FO), Execute Instruction (EI) and Write Operand (WO). T
How many number of times the instruction sequence below will loop before coming out of the loop? MOV AL, 00H A1: INC AL JNZ A1
How much speed do we gain by using the cache, when cache is used 80% of the time? Assume cache is faster than main memory.
A processor is fetching instructions at the rate of 1 MIPS. A DMA module is used to transfer characters to RAM from a device transmitting at 9600 bps. How much time will the processor be slowed down d
The physical location of a record determined by a formula that transforms a file key into a record location is
Consider the following dependencies and the BOOK table in a relational database design. Determine the normal form of the given relation. ISBN Title ISBN Publisher Publisher Address
Embedded pointer provides
Which of the following is the highest isolation level in transaction management?
Relation R has eight attributes ABCDEFGH. Fields of R contain only atomic values. is a set of functional dependencies (FDs) so that is exactly the set of FDs that hold for R. The relation R is
Consider the following relational schema: Suppliers (sid:integer, sname:string, saddress:string) Parts (pid:integer, pname:string, pcolor:string) Catalog (sid:integer, pid:integer, pcost:real) What is
Consider the following relational schema.
An index is clustered, if
Calculate the order of leaf ( ) and non leaf (P) nodes of a tree based on the information given below. Search key field = 12 field Record pointer = 10 bytes Block pointer = 8 bytes Block size = 1KB
Relation R has eight attributes ABCDEFGH. Fields of R contain only atomic values. is a set of functional dependencies (FDs) so that is exactly the set of FDs that hold for R. How many candidate keys d
The binary equivalent of the decimal number 42.75 is
How many programmable fuses are required in a PLA which takes 16 inputs and gives 8 outputs? It has to use 8 OR gates and 32 AND gates.
In a three stage counter, using RS flip flops what will be the value of the counter after giving 9 pulses to its input ? Assume that the value of counter before giving any pulses is 1 :
When two BCD numbers and are added what is the binary representation of the resultant number ?
Which one of the following expressions does NOT represent exclusive NOR of x and y?
In the following truth table, V = 1 if and only if the input is valid. What function does the truth table represent?
The most simplified form of the Boolean function (expressed in sum of minterms) is?
Which logic gate is used to detect overflow in 2's compliment arithmetic?
Two eight bit bytes 11000011 and 01001100 are added. What are the values of the overflow, carry and zero flags respectively, if the arithmetic unit of the CPU uses 2's complement form?
The smallest integer that can be represented by an 8-bit number in 2's complement form is
The number 1102 in base 3 is equivalent to 123 in which base system?
Any set of Boolean operators that is sufficient to represent all Boolean expressions is said to be complete. Which of the following is not complete ?
The Guass-Seidal iterative method can be used to solve which of the following sets?
The line graph L(G) of a simple graph G is defined as follows: There is exactly one vertex v(e) in L(G) for each edge e in G. For any two edges e and e' in G, L(G) has an edge between v(e) and v(e'),
What is the least value of the function in the interval [0, 5]?
Consider an undirected random graph of eight vertices. The probability that there is an edge between a pair of vertices is 1/2. What is the expected number of unordered cycles of length three?
Which one of the following functions is continuous at x = 3?
Function f is known at the following points: The value of computed using the trapezoidal rule is
Which of the following statements is/are TRUE for undirected graphs? P: Number of odd degree vertices is even. Q: Sum of degrees of all vertices is even.
Which one of the following does NOT equal ?
Suppose p is the number of cars per minute passing through a certain road junction between 5 PM and 6 PM, and p has a Poisson distribution with mean 3. What is the probability of observing fewer than
What is the matrix transformation which takes the independent vectors and transforms them to respectively?
Which one of the following is NOT logically equivalent to ?
The number of edges in a 'n' vertex complete graph is?
What is the cyclomatic complexity of a module which has seventeen edges and thirteen nodes?
What is the logical translation of the following statement? "None of my friends are perfect."
Let P(E) denote the probability of the occurrence of event E. If P(A)= 0.5 and P(B)=1 then the values of P(A|B) and P(B|A) respectively are
A binary operation on a set of integers is defined as . Which one of the following statements is TRUE about ?
How many diagonals can be drawn by joining the angular points of an octagon?
The number of elements in the power set of the set {{A, B}, C} is
Which of the following are the likely causes of thrashing?
A 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) ,wh
In a 64- bit machine, with 2 GB RAM, and 8 KB page size, how many entries will be there in the page table if its is inverted?
Which of the following is not a necessary condition for deadlock?
Three concurrent processes X, Y, and Z execute three different code segments that access and update certain shared variables. Process X executes the P operation (i.e., wait) on semaphores a, b and c;
A CPU scheduling algorithm determines an order for the execution of its scheduled processes. Given processes to be scheduled on one processor, how many possible different schedules are there?
Suppose we have variable logical records of lengths of 5 bytes, 10 bytes and 25 bytes while the physical block size in disk is 15 bytes. What is the maximum and minimum fragmentation seen in bytes?
Consider a logical address space of 8 pages of 1024 words each, mapped onto a physical memory of 32 frames. How many bits are there in the physical address and logical address respectively?
A scheduling algorithm assigns priority proportional to the waiting time of a process. Every process starts with priority zero (the lowest priority). The scheduler re-evaluates the process priorities
A starvation free job scheduling policy guarantees that no job indefinitely waits for a service. Which of the following job scheduling policies is starvation free?
A certain computation generates two arrays a and b such that a[i]=f(i)for and b[i] = g (a[i] )for . Suppose this computation is decomposed into two concurrent processes X and Y such that X computes th
Consider the following set of processes, with arrival times and the required CPU-burst times given in milliseconds. P_1 P_2 P_3 What is the sequence in which the processes are completed? Assume round
The state of a process after it encounters an I/O instruction is?
A 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) ,wh
Which of the following strategy is employed for overcoming the priority inversion problem?
Consider the list of page references in the time line as below: 9 6 2 3 4 4 4 4 3 4 4 2 5 8 6 8 5 5 3 2 3 3 9 6 2 7 What is the working set at the penultimate page reference if is 5?
A shared variable x, initialized to zero, is operated on by four concurrent processes W, X, Y, Z as follows. Each of the processes W and X reads x from memory, increments by one, stores it to memory,
A particular parallel program computation requires 100 seconds when executed on a single CPU. If 20% of this computation is strictly sequential, then theoretically the best possible elapsed times for
Consider the following process and resource requirement of each process. Predict the state of this system, assuming that there are a total of 5 instances of resource type 1 and 4 instances of resource
Consider the following psuedocode: x: integer := 1 y: integer := 2 procedure add x:= x + y procedure second (P: Procedure) x: integer := 2 p() procedure first y: integer := 3 second (add) first () wri
What is the output of the following program? Class Test { public static void main (String [] args) { int x = 0; int y = 0 for (int z = 0; z 2)||(++y > 2)) { x++; } } System.out.printIn (x+ "" + y); }
The number of rotations required to insert a sequence of elements 9, 6, 5, 8, 7, 10 into an empty AVL tree is?
The preorder traversal sequence of a binary search tree is 30, 20, 10, 15, 25, 23, 39, 35, 42. Which one of the following is the postorder traversal sequence of the same tree?
What is the return value of f(p,p), if the value of p is initialized to 5 before the call? Note that the first parameter is passed by reference, whereas the second parameter is passed by value. int f
In an array of 2N elements that is both 2-ordered and 3-ordered, what is the maximum number of positions that an element can be from its position if the array were 1-ordered?
Which one of the following is the tightest upper bound that represents the time complexity of inserting an object into a binary search tree of n nodes?
Let A(1:8, -5:5, -10:5) be a three dimensional array. How many elements are there in the array A?
Consider the following operation along with Enqueue and Dequeue operations on queues, where k is a global parameter. MultiDequeue(Q){ m = k while (Q is not empty) and (m > 0) { Dequeue(Q) m = m - 1 }
Which of the following number of nodes can form a full binary tree?
Consider the following C code. #include #include void main () { double pi = 3.1415926535; int a = 1; int i; for (i=0; i < 3; i++) if (a = cos(pi * i/2)) printf("% d", 1); else printf("%d", 0); } What
The following steps in a linked list p = getnode() info(p) = 10 next (p) = list list = p result in which type of operation?
Consider the following languages. Which one of the following statements is FALSE?
Which of the following statements is/are FALSE? 1. For every non-deterministic Turing machine, there exists an equivalent deterministic Turing machine. 2. Turing recognizable languages are closed unde
Consider the languages abd . Which one of the following represents ?
Which of the following is/are undecidable? 1. G is a CFG. Is L(G) = ? 2. G is a CFG. Is L(G) = ? 3. M is a Turing machine. Is L(M) regular? 4. A is a DFA and N is an NFA. Is L(A) = L(N)?
Consider the DFA A given below. Which of the following are FALSE? 1. Complement of L(A) is context-free. 2. L(A) = L((11*0+0) (0+1)*0*1*) 3. For the language accepted by A, A is the minimal DFA. 4. A
What are the final states of the DFA generated from the following NFA?