Previous Year Questions
2 papers · 180 questions — organised by subject with solutions and explanations.
🎯 Practice smarter, not harder
Just sign in to unlock everything. Free for all students.
Let A1,A2,A3, and A4 be four matrices of dimensions 10x5, 5x20, 20x10, and 10x5, respectively. The minimum number of scalar multiplications required to find the product A1A2A3A4 using the basic matrix
Consider the following recurrence: Which one of the following is true?
Let G be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is increasedby the same value ,then which of the following statements is/are TRUE? P: Minimum s
Algorithm design technique used in quicksort algorithm is?
Consider a carry lookahead adder for adding two n-bit integers,built using gates of fan-in at most two. The time to perform addition using this adder is
Consider the following directed graph: The number of different topological orderings of the vertices of the graph is
The Floyd-Warshall algorithm for all-pair shortest paths computation is based on
Consider the weighted undirected graph with 4 vertices,where the weigh to edge {i, j} is given by the entry Wij in the matrix W. The largest possible integer value of x, for which at least one shortes
In an adjacency list representation of an undirected simple graph G = (V,E), each edge (u,v) has two adjacency list entries: [v] in the adjacency list of u, and [u] in the adjacency list of v. These a
Let G be a complete undirected graph on 4 vertices, having 6 edges with weights being 1,2,3,4,5, and 6. The maximum possible weight that a minimum weight spanning tree of G can haveis .
Assume that the algorithms considered here sort the input sequences in ascending order. If the input is already in ascending order, which of the following are TRUE? I. Quicksort runs in time II. Bubbl
Breadth First Search(BFS) is started on a binary tree beginning from the root vertex. There is a vertex t at a distance four from the root. If t is the n-th vertex in this BFS traversal, then the maxi
G = (V,E) is an undirected simple graph in which each edge has a distinct weight,and e is a particular edgeof G. Which of the following statements about the minimum spanning trees (MSTs) of G is/are T
The given diagram shows the flowchart for a recursive function A(n). Assume that all statements, except for the recursive calls,have O(1) Asymptotic Notation. If the worst case Asymptotic Notation of
Let G be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is increasedby the same value ,then which of the following statements is/are TRUE? P: Minimum s
The worst case running times of Insertion sort, Mergesort and Quicksort, respectively, are:
A student wrote two context-free grammars G1 and G2 for generating a single C-like array declaration. The dimension of the array is at least one. For example, int a[10][3]; The grammars use D as the s
Match thefollowing:
A top-down parser generates
Peephole optimization is form of
Consider the following Syntax Directed Translation Scheme(SDTS),with non-terminals {S, A} and terminals {a, b}. S aA {print 1} S a { print 2} A Sb { print 3} Using the above SDTS, the output printed b
Recursive descent parsing is an example of
Consider the following code segment. x =u-t; y =x*v; x =y+w; y =t-z; y =x*y; The minimum number of total variables required to convert the above code segment to static single assignment form is_______
simple two-pass assembler does which of the following in the first pass:
Dynamic routing protocol enable routers to
For the IEEE802.11 MAC protocol for wireless communication,which of the following statements is/are TRUE? I. At least three non-overlapping channels are available for transmissions. II. The RTS-CTS me
In CSMA/CD, if two stations start transmitting simultaneously, they detect collision and each waits a random backoff time. In binary exponential backoff after the -th collision, the backoff time is ch
Which one of the following protocols is NOT used to resolve one form of address to another one?
A network has a data transmission bandwidth of bits per second. It uses CSMA/CD in the MAClayer. The maximum signal propagation time from one node to another node is 40 microseconds. The minimum size
Identify the correct sequence in which the following packets are transmitted on the network by a host when a browser requests a webpage from a remote server,assuming that the host has just been restar
In Ethernet CSMA/CD, the special bit sequence transmitted by media access management to handle collision is called
When a DNS server accepts and uses incorrect information from a host that has no authority giving that information, then it is called
Consider that B wants to send a message m that is digitally signed to A. Let the pair of private and public keys for A and B be denoted by and for x = A,B, respectively. Let represent the operation of
A sender uses the Stop-and Wait ARQ protocol for reliable transmission of frames. Frames are of size 1000bytes and the transmission rate at the sender is 80Kbps(1Kbps=1000 bits/second). Size of anackn
Anarkali digitally signs a message and sends it to Salim. Verification of the signature by Salim requires
Which of the following is/are example(s) of stateful application layer protocols? (i) HTTP (ii) FTP (iii) TCP (iv) POP3
The message 11001001 is to be transmitted using the CRC polynomial to protect it from errors. The message that should be transmitted is:
If a class C is derived from class B, which is derived form class A, all through public inheritance, then a class C member function can access
What is the maximum size of data that the application layer can pass on to the TCP layer below?
The address of a class B host is to be split into subnets with a 6-bit subnet number. What is the maximum number of subnets and the maximum number of hosts in each subnet?
In an Ethernet local area network,which one of the following statements is TRUE?
For a host machine that uses the token bucket algorithm for congestion control, the token bucket has a capacity of 1 megabyte and the maximum output rate is 20 megabytes per second. Tokens arrive at a
An IP datagram of size 1000 bytes arrives at a router. The router has to forward this packet on a link whose MTU (maximum transmission unit)is 100bytes. Assume that the size of the IP header is 20byte
In a token ring network the transmission speed is bps and the propagation speed is 200 meters/ . The 1-bit delay in this network is equivalent to:
Frames of 1000 bits are sent over a bps duplex link between two hosts. The propagation time is 25 ms. Frames are to be transmitted into this link to maximally pack them in transit (within the link). W
Which network protocol allows hosts to dynamically get a unique IP number on each bootup
Bit stuffing refers to
Consider a bits/second satellite communication link with one way propagation delay of 150 milliseconds. Selective retransmission(repeat) protocol is used on this link to send data with a frame size of
The stage delays in a 4-stage pipeline are 800,500,400 and 300 picoseconds.The first stage (with delay 800 picoseconds)is replaced with a functionally equivalent design involving two stages with respe
Suppose the functions F and G can be computed in 5 and 3 nano seconds by functional units and , respectively. Given two instances of and two instances of , it is required to implement the computation
A file system uses an in-memory cache to cache disk blocks.The miss rate of the cache is shown in the figure. The latency to read a block from the cache is 1 ms and to read a block from the disk is 10
Consider a processor with 64 registers and an instruction set of size twelve. Each instruction has five distinct fields, namely, opcode, two source register identifiers, one destination register ident
The size of the data count register of a DMA controller is 16 bits.The processor needs to transfer a file of 29,154 kilobytes from disk to main memory.The memory is byte addressable. The minimum numbe
The width of the physical address on a machine is 40 bits. The width of the tag field in a 512KB 8-way set associative cache is ________ bits.
Consider a 3GHz (gigahertz) processor with a three-stage pipeline and stage latencies , , and such that . If the longest pipeline stage is split into two pipeline stages of equal latency, the new freq
Consider a non-pipelined processor with a clock rate of 2.5 gigahertz and average cycles per instruction of four. The same processor is upgraded to a pipelined processor with five stages; but due to t
A processor has 40 distinct instructions and 24 general purpose registers. A 32-bit instruction word has an opcode, two register operands and an immediate operand. The number of bits available for the
Register renaming is done in pipelined processors:
The dynamic hazard problem occurs in
Which of the following is NOT a superkey in a relational schema with attributes V,W, X, Y, Z and primary key V Y?
The order of a leaf node in a - tree is the maximum number of (value, data record pointer) pairs it can hold. Given that the block size is 1K bytes, data record pointer is 7 bytes long, the value fiel
Trigger is
Consider the following databases chedule with two transactions, T1 and T2. where denotes a read operation by transaction on avariable Z, denotes a write operation by on avariable Z and denotes an abor
Consider the following database table named water_schemes : The number of tuples returned by the following SQL query is __________.
Consider the join of a relation R with a relation S. If R has m tuples and S has n tuples then the maximum and minimum sizes of the join respectively are
A database of resear charticles in a journal uses the following schema. Which is the weakest normal form that the new database satisfies,but the old one does not?
Goals for the design of the logical scheme include
Consider the following two phase locking protocol. Suppose a transaction T accesses (for read or write operations), a certain set of objects {O1,... ,Ok}. This is done in the following manner: Step 1.
Which one of the following is NOT a part of the ACID properties of database transactions?
Let R(a,b,c) and S(d,e,f) be two relations in which d is the foreign key of S that refers to the primary key of R. Consider the following four operations R and S I. Insert into R II. Insert into S III
Given the relations employee (name, salary, dept-no), and department (dept-no, dept-name,address), Which of the following queries cannot be expressed using the basic relational algebra operations ?
A clustering index is defined on the fields which are of type
Suppose a database schedule S involves transactions T1,...,Tn. Construct the precedence graph of S with vertices representing the transactions and edges representing the conflicts. If S is serializabl
The relation book (title,price) contains the titles and prices of different books. Assuming that no two books have the same price, what does the following SQL query list? select title from book as B w
The simplified SOP (Sum of Product) from the Boolean expression is
The logic circuit given below converts a binary code y1, y2, y3 into
The Excess-3 code is also called
The minimum Boolean expression for the following circuit is
The functional difference between SR flip-flop and J-K flip-flop is that :
Which of the following binary number is the same as its 2's complement ?
If then the value of X is
The circuit given in the figure below is
Consider the Boolean operator with the following properties: , and . Then is equivalent to
Let X be the number of distinct 16-bit integers in 2's complement representation. Let Y be the number of distinct 16 bit integers in sign magnitude representation. Then X-Y is ________.
Consider an eight-bit ripple-carry Combinational Circuit for computing the sum of A and B, where A and B are integers represented in 2's complement form. If the decimal value of A is one, the decimal
The minimum number of gates required to implement the Boolean function is equal to
We want to design a synchronous counter that counts these quence 0-1-0-2-0-3 and then repeats. The minimum number of J-K flip flop srequired to implement this counteris ________.
For a binary half-subtractor having two inputs A and B, the correct set of logical outputs D(=A minus B) and X(=borrow) are
The 16 bit 2's complement representation of an integer is 1111 1111 1111 0101; its decimal representation is__________ .
Consider the two cascaded 2-to-1 multiplexers as shown in the figure. The minimal sum of products form of the output X is
Consider the following gate network Which one of the following gates is redundant?
Let, where are Boolean variables, and is the XOR operator. Which one of the following must always be TRUE?
Suppose that a shop has an equal number of LED bulbs of two different types. The probability of an LED bulb lasting more than 100 hours given that it is of Type 1 is 0.7, and given that it is of Type
A binary relation R on is defined as follows: (a,b)R(c,d) if or . Consider the following propositions: P: R is reflexive Q: R is transitive Which one of the following statements is TRUE?
=_________.
Consider the recurrence relation =8, . Let . The value of K is .
Two eigen values of a 3x3 real matrix P are (2+ ) and 3.The determinantof P is __________.
The maximum number of edges in a n-node undirected graph without self loops is
Consider a set U of 23 different compounds in a Chemistry lab. There is a subset S of U of 9 compounds, each of which reacts with exactly 3 compounds of U. Consider the following statements: I. Each c
is a group such that , then is a/an
Consider the following expressions: (i) false (ii) Q (iii) true (iv) (v) The number of expressions given above that are logically implied by is ________.
What is the sum to infinity of the series,
Breadth First Search(BFS) is started on a binary tree beginning from the root vertex. There is a vertex t at a distance four from the root. If t is the n-th vertex in this BFS traversal, then the maxi
A given connected graph G is a Euler Graph if and only if all vertices of G are of
A probability density function on the interval [a,1] is given by 1/ and outside this interval the value of the function is zero.The value of a is __________.
The minimum number of colours that is sufficient to vertex-colour any planar graph is _________.
Consider the following directed graph: The number of different topological orderings of the vertices of the graph is
Suppose that the eigen values of matrix A are 1, 2, 4. The determinant of is _________.
Consider the following experiment. Step 1. Flip a fair coin twice. Step 2. If the outcomes are(TAILS, HEADS) then output Y and stop. Step 3. If the outcomes are either(HEADS, HEADS) or(HEADS, TAILS),
Let f(x) be a polynomial and g(x) = f'(x) be its derivative. If the degree of (f(x)+ f(-x)) is 10, then the degree of (g(x)-g(-x)) is ________.
A function , defined on the set of positive integers , satisfies the following properties: f(n)=f(n/2) if n is even f(n)=f(n+5) if n is odd Let R={ } be the set of distinct values that f takes. The ma
The coefficient of in is ______.
is given by
Which one of the following well-formed formulae in predicate calculus is NOT valid?
Let p,q, r, s represent the following propositions. p: x {8,9,10,11,12} q: x is a composite number r: x is a perfect square s: x is a prime number The integer x 2 which satisfies is ________.
Consider the systems,each consisting of m linear equations in n variables. I. If m n, then all such systems have a solution II. If m n, then none of these systems has a solution III. If m = n, then th
Let be the number of n-bit strings that do NOT contain two consecutive 1s. Which one of the following is the recurrence relation for ?
Consider a computer system with 40-bit virtual addressing and page size of sixteen kilobytes. If the computer system has a one level page table per process and each page table entry requires 48 bits,
At a particular time of computation the value of a counting semaphore is 7. Then 20 P operations and x V operations were completed on this semaphore. If the new value of semaphore is 5, x will be
Consider a computer system with ten physical page frames. The system is provided with an accessse quence , where each is a distinct virtual page number. The difference in the number of page faults bet
A system has 3 processes sharing 4 resources. If each process needs a maximum of 2 units, then
Consider a disk queue with requests for I/O to blocks on cylinders 47,38,121,191,87,11, 92, 10. The C-LOOK scheduling algorithm is used. The head is initially at cylinder number 63, moving to wards la
In which one of the following page replacement policies, Belady's anomaly may occur?
With single resource, deadlock occurs
Determine the number of page faults when references to pages occur in the following order: 1, 2, 4, 5, 2, 1, 2, 4 Assume that the main memory can accommodate 3 pages and the main memory already has th
In which one of the following page replacement algorithms it is possible for the page fault rate to increase even when the number of allocated frames increases?
A processor can support a maximum memory of 4GB, where the memory is word-addressable (a word consists of two bytes). The size of the address bus of the process or is at least bits________.
Consider the following two-process synchronization solution. The shared variable turn is initialized to zero.Which one of the following is TRUE?
Consider an arbitrary set of CPU-bound processes with unequal CPU burst lengths submitted at the same time to a computer system.Which one of the following process scheduling algorithms would minimize
Consider the following proposed solution for the critical section problem. There are n processes: . In the code,function returns an integer not smaller than any of its arguments. For all i, t[i] is in
For the real time operating system, which of the following is the most suitable scheduling scheme?
Consider the following processes, with the arrival time and the length of the CPU burst given in milli seconds.The scheduling algorithm used is preemptive shortest remaining-time first. The average tu
Consider a non-negative counting semaphore S. The operation P(S) decrements S, and V(S) increments S. During an execution, 20 P(S) operations and 12V(S) operations are issued in some order. The larges
Working Set (t,k) at an instant of time t is
Let the page fault service time be 10 ms in a computer with average memory access time being 20 ns. If one page fault is generated for every memory accesses, what is the effective access time for the
A CPU generates 32-bit virtual addresses. The page size is 4 KB. The processor has a translation look-aside buffer (TLB) which can hold a total of 128 page table entries and is 4-way set associative.
What will be the output of the following C program? void count(intn){ static intd=1; printf("%d ",n); printf("%d ",d); d++; if(n>1) count(n-1); printf("%d ",d); } void main(){ count(3); }
What is the output of this C code? #include void main() { int k=5; int *p=&k; int **m=&p; printf("%d %d %d",k,*p,**m); }
Consider the following New-order strategy for traversing a binary tree: Visit the root; Visit the right sub tree using New-order; Visit the left sub tree using New-order; The New-order traversal of th
B+ Trees are considered BALANCED because
Consider the following C program. #include void mystery(int *ptra,int *ptrb){ int *temp; temp =ptrb; ptrb =ptra; ptra =temp; } int main(){ int a=2016,b=0,c=4,d=42; mystery(&a, &b); if (a < c) mystery(
The following function computes the maximum value contained in an integer array p[] of size n (n>=1). int max(int*p, int n){ int a=0,b=n-1; while (__________){ if (p[a]<=p[b]){a=a+1;} else {b=b-1;} }
N items are stored in a sorted doubly linked list. For a delete operation, a pointer is provided to the record to be deleted. For a decrease-key operation, a pointer is provided to the record on which
The following postfix expression with single digit operands is evaluated using a stack: Note that is the exponentiation operator. The top two elements of the stack after the first * is evaluated are
Consider thefollowingprogram: int f(int*p, int n) { if (n<=1)return0; else returnmax(f(p+1,n-1),p[0]-p[1]); } int main() { int a[]={3,5,2,6,4}; printf("%d", f(a,5)); } Note: max(x,y) returns the maxi
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
The number of ways in which the numbers 1,2,3,4,5,6,7 can be inserted in an empty binary search tree, such that the resulting tree has height 6, is _____. Note: The height of a tree with a single node
A Hash Function f defined as f(key)=keymod7. With linear probing while inserting the keys 37,38,72,48,98,11,56 into a table indexed from 0, in which location key 11 will be stored (Count table index 0
Consider the following C program. void f(int,short); void main() { int i=100; short s=12; short *p=&s; __________ ;//calltof() } Which one of the following expressions, when placed in the blank above,
What will be output of the following program? Assume that you are running this program in little-endian processor. #include int main() { short a=320; char *ptr; ptr=(char *)&a; printf("%d",*ptr); retu
The following function computes for positive integers X and Y. int exp(int X,int Y){ int res=1, a=X, b=Y; while (b!=0){ if(b%2==0){a=a*a; b=b/2;} else {res=res*a; b=b-1;} } return res; } Which one of
The attributes of three arithmetic operators in some programming language are given below. The value of the expression 2-5+1-7*3 in this language is_______ .
Access time of the symbolic table will be logarithmic if it is implemented by
Which one of the following is correct about the statements given below? I. All function calls are resolved at compile time in C lang II. All function calls are resolved at compile time in C++ lang
An operator delete(i) for a binary heap data structure is to be designed to delete the item in the i-th node.Assume that the heap is implemented in an array and i refers to the i-th index of thearray.
Consider the following segment of C-code: int j, n; j = 1; while (j 0 is:
The value printed by the following program is . void f(int*p, int m){ m =m+5; *p =*p+m; return; } void main(){ int i=5, j=10; f(&i, j); printf("%d", i+j); }
Let Q denote a queue containing sixteen numbers and S be an empty stack. Head(Q) returns the element at the head of the queue Q without removing it from Q. Similarly Top(S) returns the element at the
A complete binary min-heap is made by including each integer in [1,1023] exactly once. The depth of a node in the heap is the length of the path from the root of the heap to that node. Thus, the root
A complete binary tree with n non-leaf nodes contains
What will be the output of the following pseudo-code when parameters are passed by reference and dynamic scoping is assumed? a=3; void n(x){x=x*a; print(x);} void m(y){a=1;a=y-a;n(a);print(a);} void m
What is the highest type number that can be assigned to the following grammar?
Consider the following statements about the context free grammar I. G is ambiguous II. G produces all strings with equal number of a's and b's III. G can be accepted by a deterministic PDA. Which comb
Which one of the following grammars is free from left recursion?
Consider the transition diagram of a PDA given below with input alphabet ={a,b} and stack alphabet ={X,Z}. Z is the initial stack symbol. Let L denote the language accepted by the PDA. Which one of th
Which of the following decision problems are undecidable? I. Given NFAs N1 and N2, is L(N1) L(N2) = ? II. Given a CFG G = (N, ,P,S) and a string , does L(G)? III. Given CFGs G1 and G2, is L(G1) = L(G2
Language L1 is defined by the grammar: Language L2 is defined by the grammar: Consider the following statements: P: L1 is regular Q: L2 is regular Which one of the following is TRUE?
The number of states in the minimum sized DFA that accepts the language defined by the regular expression (0+1)* (0+1)(0+1)* is _______.
Let , i.e. is the set of all bit strings with even number of 1's. Which one of the regular expression below represents ?
Let X be a recursive language and Y be a recursively enumerable but not recursive language. Let W and Z be two languages such that reduces to W, and Z reduces to (reduction means the standard many-one
Which one of the following regular expressions represents the language: the set of all binary strings having two consecutive 0s and two consecutive 1s?
Consider the following types of languages: :Regular, :Context-free, :Recursive, :Recursively enumerable. Which of the following is/are TRUE? I. is recursivelyenumerable II. is recursive III. is contex
Consider the following context-free grammars: G1: S aS|B, B b|bB G2: S aA|bB, A aA|B| , B bB| Which one of the following pair of languages is generated by G1 and G2, respectively?
The language generated by the above grammar over the alphabet {a,b} is the set of:
If and are recursively enumerable then is
An FSM(finite state machine) can be considered to be a turing machine of finite tape length
Consider the following languages. L1 = { M |M takes at least 2016 steps on some input}, L2 = { M | M takes at least 2016 steps on all inputs} and L3 = { M|M accepts }, where for each Turing machine M,
Which of the following languages is generated by the given grammar?
Consider the following two statements: I. If all states of an NFA are accepting states then the language accepted by the NFA is . II. There exists a regular language A such that for all languages B, A
Consider the following languages: Which one of the following is TRUE?