Previous Year Questions
1 paper · 121 questions — organised by subject with solutions and explanations.
🎯 Practice smarter, not harder
Just sign in to unlock everything. Free for all students.
What is the number of swaps required to sort n elements using selection sort, in the worst case?
The running time of an algorithm is represented by the following recurrence relation: Which one of the following represents the time complexity of the algorithm?
Consider the following graph: Which one of the following is NOT the sequence of edges added to the minimum spanning tree using Kruskal's algorithm?
In quick sort, for sorting n elements, the (n/4)th smallest element is selected as pivot using an O(n) time algorithm. What is the worst case time complexity of the quick sort?
A sub-sequence of a given sequence is just the given sequence with some elements (possibly none or all) left out. We are given two sequences X[m] and Y[n] of lengths m and n, respectively, with indexe
Which of the following statement(s) is/are correct regarding Bellman-Ford shortest path algorithm? P. Always finds a negative weighted cycle, if one exists. Q. Finds whether any negative weighted cycl
A sub-sequence of a given sequence is just the given sequence with some elements (possibly none or all) left out. We are given two sequences X[m] and Y[n] of lengths m and n, respectively, with indexe
Which of the following statements are TRUE? I There exist parsing algorithms for some programming languages whose complexities are less than . II A programming language which allows recursion can be i
Match all items in Group 1 with correct options from those given in Group 2.
What is the primary purpose of a VLAN?
Frames of 1000 bits are sent over a bps duplex link between two hosts. The propagation time is 25ms. Frames are to be transmitted into this link to maximally pack them in transit (within the link). Wh
Which of the following is a MAC address?
The address resolution protocol (ARP) is used for
While opening a TCP connection, the initial sequence number is to be derived using a time-of-day (ToD) clock that keeps running even when the host is down. The low order 32 bits of the counter of the
Use of IPSEC in tunnel mode results in
The subnet mask for a particular network is 255.255.31.0. Which of the following pairs of IP addresses could belong to this network?
Frames of 1000 bits are sent over a bps duplex link between two hosts. The propagation time is 25ms. Frames are to be transmitted into this link to maximally pack them in transit (within the link). Su
Advanced Encryption Standard (AES) is based on
In networking, UTP stands for
In the RSA public key cryptosystem, the private and public keys are (e,n) and (d,n) respectively, where n=p*q and p and q are large primes. Besides, n is public and p and q are private. Let M be an in
Let G(x) be the generator polynomial used for CRC checking. What is the condition that should be satisfied by G(x) to detect odd number of bits in error?
SHA-1 is a
A hard disk has 63 sectors per track, 10 platters each with 2 recording surfaces and 1000 cylinders. The address of a sector is given as a triple (c,h,s), where c is the cylinder number, h is the surf
A CPU generally handles an interrupt by executing an interrupt service routine
A processor that has carry, overflow and sign flag bits as part of its program status word (PSW) performs addition of the following two 2's complement numbers 01001101 and 11101001. After the executio
Consider a disk pack with 16 surfaces, 128 tracks per surface and 256 sectors per track. 512 bytes of data are stores in a bit serial manner in a sector. The capacity of the disk pack and the number o
The use of multiple register windows with overlap causes a reduction in the number of memory accesses for: I. Function locals and parameters II. Register saves and restores III. Instruction fetches
Compared to CISC processors,RISC processors contain
Which of the following statements about synchronous and asynchronous I/O is NOT true?
Consider a 4-way set associative cache (initially empty) with total 16 cache blocks. The main memory consists of 256 blocks and the request for memory blocks is in the following order: 0, 255, 1, 4, 3
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
A hard disk has 63 sectors per track, 10 platters each with 2 recording surfaces and 1000 cylinders. The address of a sector is given as a triple (c,h,s), where c is the cylinder number, h is the surf
Consider a 4 stage pipeline processor. The number of cycles needed by the four instructions I1, I2, I3, I4 in stages S1, S2, S3, S4 is shown below: What is the number of cycles needed to execute the f
In which addressing mode, the effectives address of the operand is generated by adding a constant value to the content of a register?
A certain microprocessor requires 4.5 microseconds to respond to an interrupt. Assuming that the three interrupts , and require the following execution time after the interrupt is recognized: I. requi
On receiving an interrupt from an I/O device,the CPU
The process of organizing the memory into two banks to allow 8-and 16-bit data operation is called
Consider a pipelined processor with the following four stages: IF: Instruction Fetch ID: Instruction Decode and Operand Fetch EX: Execute WB: Write Back The IF, ID and WB stages take one clock cycle e
How many 32K x 1 RAM chips are needed to provide a memory capacity of 256Kbytes?
Which of the following is/are true of the auto-increment addressing mode? I. It is useful in creating self-relocating code II. If it is included in an Instruction Set Architecture, then an additional
Consider two transactions T1 and T2, and four schedules S1, S2, S3, S4 of T1 and T2 as given below: Which of the above schedules are conflict-serializable?
Consider the following relational schema: Suppliers(sid:integer, sname:string, city:string, street:string) Parts(pid:integer, pname:string, color:string) Catalog(sid:integer, pid:integer, cost:real) A
Which of the following scenarios may lead to an irrecoverable error in a database system?
Which of the following contains complete record of all activity that affected the contents of a database during a certain period of time?
Let R and S be relational schemes such that R={a,b,c} and S={c}. Now consider the following queries on the database: IV. Select R.a, R.b From R,S Where R.c=S.c Which of the above queries are equivalen
Purpose of 'Foreign Key' in a table is to ensure
A locked database file can be
Consider the following relational schema: Suppliers(sid:integer, sname:string, city:string, street:string) Parts(pid:integer, pname:string, color:string) Catalog(sid:integer, pid:integer, cost:real) C
The addition of 4-bit, two's complement, binary numbers 1101 and 0100 results in
The binary operation is defined as follows Which one of the following is equivalent to ?
Consider the following boolean function of four variables , the function is
What is the minimum number of gates required to implement the Boolean function (AB+C) if we have to use only 2-input NOR gates?
The two numbers given below are multiplied using the Booth's algorithm Multiplicand: 0101 1010 1110 1110 Multiplier: 0111 0111 1011 1101 How many additions/subtractions are required for the multiplica
The switching expression corresponding to is
Consider the binary relation R = {(x,y), (x,z), (z,x), (z,y)} on the set {x,y,z}. Which one of the following is TRUE?
A simple graph ( a graph without parallel edge or loops) with n vertices and k components can have at most
The formula is called
Which one of the following is the most appropriate logical formula to represent the statement? "Gold and silver ornaments are precious". The following notations are used: G(x): x is a gold ornament S(
An unbalanced dice (with 6 faces, numbered from 1 to 6) is thrown. The probability that the face value is odd is 90% of the probability that the face value is even. The probability of getting any even
Which one of the following is TRUE for any simple connected undirected graph with more than 2 vertices?
The value of x at which y is minimum for is
A root of equation can be computed to any degree of accuracy if a 'good' initial approximation is chosen for which
A square matrix A is called orthogonal if A'A=
If then the value of is
Let be the continuous probability density function of a random variable , the probability that , is :
If the pdf of a Poisson distribution is given by then its mean is
The cubic polynomial y(x) which takes the following values: y(0)=1, y(1)=0, y(2)=1 and y(3)=10 is
Let G be an arbitrary graph with n nodes and k components. If a vertex is removed from G, the number of components in the resultant graph must necessarily lie down between
Which one of the following in NOT necessarily a property of a Group?
Which of the following statement is correct
If A, B, C are any three matrices, then A'+B'+C' is equal to
Consider the polynomial , where . The minimum number of multiplications needed to evaluate p on an input x is:
If two adjacent rows of a determinant are interchanged, the value of the determinant
evaluates to
If G is a graph with e edges and n vertices the sum of the degrees of all vertices in G is
What is the chromatic number of an n-vertex simple connected graph which does not contain any odd length cycle? Assume n 2.
A graph in which all nodes are of equal degree, is known as
For the composition table of a cyclic group shown below Which one of the following choices is correct?
The formula is
Consider the following well-formed formulae: I. II. III. IV. Which of the above are equivalent?
In a graph G there is one and only one path between every pair of vertices then G is a
is the parametric form of
Consider three CPU-intensive processes, which require 10, 20 and 30 time units and arrive at times 0, 2 and 6, respectively. How many context switches are needed if the operating system implements a s
Process is
The enter_CS() and leave_CS() functions to implement critical section of a process are realized using test-and-set instruction as follows: void enter_CS(x) { while test-and-set(x) ; } void leave_CS(x)
Consider a set of 5 processes whose arrival time, CPU time needed and the priority are given below: (smaller the number, higher the priority) If the CPU scheduling policy is priority scheduling withou
In which one of the following page replacement policies, Belady's anomaly may occur?
When a process is rolled back as a result of deadlock the difficulty which arises is
Which is the correct definition of a valid process transition in an operating system?
In the following process state transition diagram for a uniprocessor system, assume that there are always some processes in the ready state: Now consider the following statements: I. If a process make
Consider a system having "n" resources of same type. These resources are shared by 3 processes, A, B, C. These have peak demands of 3, 4, and 6 respectively. For what value of "n" deadlock won't occur
Special software to create a job queue is called a
A page fault
Using a larger block size in a fixed block size file system leads to
A multilevel page table is preferred in comparison to a single level page table for translating virtual address to physical address because
Consider a disk system with 100 cylinders. The requests to access the cylinders occur in following sequence: 4, 34, 10, 7, 19, 73, 2, 15, 6, 20 Assuming that the head is currently at cylinder 50, what
The essential content(s) in each entry of a page table is / are
The correct matching of the following pairs is
The performance of Round Robin algorithm depends heavily on
Consider a system with 4 types of resources R1 (3 units), R2 (2 units), R3 (3 units), R4 (2 units). A non-preemptive resource allocation policy is used. At any given instance, a request is not enterta
Consider the following code written in a pass-by-reference language like FORTRAN and these statements about the code. subroutine swap(ix,iy) it = ix L1 : ix = iy L2 : iy = it end ia = 3 ib = 8 call sw
Consider a binary max-heap implemented using an array. Which one of the following array represents a binary max-heap?
A full binary tree with n leaves contains
A one dimensional array A has indices 1....75. Each element is a string and takes up three memory words. The array is stored at location 1120 decimal. The starting address of A[49] is
What is the maximum height of any AVL-tree with 7 nodes? Assume that the height of a tree with a single node is 0.
The following key values are inserted into a B+ tree in which order of the internal nodes is 3, and that of the leaf nodes is 2, in the sequence given below. The order of internal nodes is the maximum
Consider the program below: # include int fun(int n, int * f_p) { int t, f; if (n <=1) { *f_p =1; return 1; } t = fun (n-1, f_p); f = t+*f_p; *f_p = t; return f; } int main() { int x = 15; printf ("%d
Suppose the numbers 7,5,1,8,3,6,0,9,4,2 are inserted in that order into an initially empty binary search tree. The binary search tree uses the usual ordering on natural numbers. What is the in-order t
The infix expression is correctly represented in prefix notation as
Assume that the operators are left associative and is right associative. The order of precedence (from highest to lowest) is . The postfix expression corresponding to the infix expression is
Consider a binary max-heap implemented using an array. What is the content of the array after two delete operations on {25,14,16,13,10,8,12}
The keys 12, 18, 13, 2, 3, 23, 5 and 15 are inserted into an initially empty hash table of length 10 using open addressing with hash function h(k) = k mod 10 and linear probing. What is the resultant
A data structure is required for storing a set of integers such that each of the following operations can be done in time, where n is the number of elements in the set. 1. Deletion of the smallest ele
The expression will be evaluated as
Given the following state table of an FSM with two states A and B, one input and one output: If the initial state is A = 0, B=0, what is the minimum length of an input string which will take the machi
S aSa|bSb|a|b; The language generated by the above grammar over the alphabet {a,b} is the set of
The above DFA accepts the set of all strings over {0,1} that
Let , where and are languages as defined below: Then L is
Which one of the following languages over the alphabet {0,1} is described by the regular expression: (0+1)*0(0+1)*0(0+1)*?
Which one of the following is FALSE?