Previous Year Questions
1 paper · 128 questions — organised by subject with solutions and explanations.
🎯 Practice smarter, not harder
Just sign in to unlock everything. Free for all students.
Consider product of three matrices , and 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 than to comp
Of the following sort algorithms, which has execution time that is least dependant on initial ordering of the input?
Let be a weighted undirected graph and let T be a Minimum Spanning Tree (MST) of G maintained using adjacency lists. Suppose a new weighed edge is added to G. The worst case time complexity of determi
What is the complexity of the following code? sum=0; for(i=1;i<=n;i*=2) for(j=1;j<=n;j++) sum++; Which of the following is not a valid string?
The master theorem
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 01101 is decoded as
For parameters a and b, both of which are , and . Then is
Consider a graph , where , , and weight of the edge . The weight of minimum spanning tree of G is _________
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 of the graph is performed with
Let be a directed, weighed graph with weight function . For some function , for each edge , define as . Which one of the options completes the following sentence so that it is TRUE? "The shortest path
Consider the following statements. I. Symbol table is accessed only during lexical analysis and syntax analysis. II. Compilers for programming languages that support recursion necessarily need heap st
A given grammar is called ambiguous if
Which of the following is a type of a out-of-order execution, with the reordering done by a compiler
In a two-pass assembler, resolution of subroutine calls and inclusion of labels in the symbol table is done during
A grammar is defined as The non terminal alphabet of the grammar is
The number of tokens in the following C code segment is switch(inputvalue) { case 1 : b =c*d; break; default : b =b++; break; }
Given the grammar Which of the following statements is wrong?
Consider the following grammar. The number of reduction steps taken by a bottom-up parser while accepting the string is___________.
Consider the productions and . Each of the five non-terminals A,P,Q,X, and Y has two attributes: s is a synthesized attribute, and i is an inherited attribute. Consider the following rules. Rule 1: P.
Avalanche effect in cryptography refers
Assume that you have made a request for a web page through your web browser to a web server. Initially the browser cache is empty. Further, the browser is configured to send HTTP requests in non-persi
To send same bit sequence, NRZ encoding require
The persist timer is used in TCP to
Checksum field in TCP header is
Remote Procedure Calls are used for
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 lie between 0 and 255.
Consider a TCP connection between a client and a server with the following specifications; the round trip time is 6 ms, the size of the receiver advertised window is 50 KB, slow-start threshold at the
Consider the following statements about the functionality of an IP based router. I. A router does not modify the IP packets during forwarding. II. It is not necessary for a router to implement any rou
In a columnar transportation cipher, the plain text is "the tomato is a plant in the night shade family", keyword is "TOMATO". The cipher text is
An organization requires a range of IP address to assign one to each of its 1500 computers. The organization has approached an Internet Service Provider (ISP) for this task. The ISP uses CIDR and serv
A processor has 64 registers and uses 16-bit instruction format. It has two types of instructions: I-type and R-type. Each I-type instruction contains an opcode, a register name, and a 4-bit immediate
Consider the following data path diagram. Consider an instruction: . The following steps are used to execute it over the given data path. Assume that PC is incremented appropriately. The subscripts r
Consider the following statements. I. Daisy chaining is used to assign priorities in attending interrupts. II. When a device raises a vectored interrupt, the CPU does polling to identify the source of
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 t
One instruction tries to write an operand before it is written by previous instruction. This may lead to a dependency called
Statements associated with registers of a CPU are given. Identify the false statement.
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 kilobytes?
A computer which issues instructions in order, has only 2 registers and 3 opcodes ADD, SUB and MOV. Consider 2 different implementations of the following basic block : Assume that all operands are ini
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?
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.
A non-pipelined CPU has 12 general purpose registers?(R0,R1,R2,...,R12). Following operations 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
Consider a non-pipelined processor operating at 2.5 GHz. It takes 5 clock cycles to complete an instruction. You are going to make a 5-stage pipeline out of this processor. Overheads associated with p
A stack organized computer is characterised by instructions with
A direct mapped cache memory of 1 MB has a block size of 256 bytes. The cache has an access time of 3 ns and a hit rate of 94%. During a cache miss, it takes 20 ns to bring the first word of a block f
Consider a 5- segment pipeline with a clock cycle time 20 ns in each sub operation. Find out the approximate speed-up ratio between pipelined and non-pipelined system to execute 100 instructions. (if
An array of 2 two byte integers is stored in big endian machine in byte addresses as shown below. What will be its storage pattern in little endian machine ?
Which of the following is an efficient method of cache updating?
A computer system with a word length of 32 bits has a 16 MB byte- addressable main memory and a 64 KB, 4-way set associative cache memory with a block size of 256 bytes. Consider the following four ph
The SQL query SELECT columns FROM TableA RIGHT OUTER JOIN TableB ON A.columnName = B.columnName WHERE A.columnName IS NULL returns the following:
If every non-key attribute functionally dependent on the primary key, then the relation will be in
Consider a relational database containing the following schemas. The primary key of each table is indicated by underlining the constituent fields. SELECT s.sno, s.sname FROM Suppliers s, Catalogue c W
Properties of 'DELETE' and 'TRUNCATE' commands indicate that
Consider a schedule of transactions T1 and T2: Here, RX stands for "Read(X)" and WX stands for "Write(X)". Which one of the following schedules is conflict equivalent to the above schedule?
Which one of the following is used to represent the supporting many-one relationships of a weak entity set in an entity-relationship diagram?
Consider a database implemented using B+ tree for file indexing and installed on a disk drive with block size of 4 KB. The size of search key is 12 bytes and the size of tree/disk pointer is 8 bytes.
Consider a relational table R that is in 3NF, but not in BCNF. Which one of the following statements is TRUE?
Consider the Boolean function . Which one of the following minterm lists represents the circuit given above?
Following Multiplexer circuit is equivalent to
A multiplexer is placed between a group of 32 registers and an accumulator to regulate data movement such that at any given point in time the content of only one register will move to the accumulator.
Consider three registers R1, R2, and R3 that store numbers in IEEE-754 single precision floating point format. Assume that R1 and R2 contain the values (in hexadecimal notation) 0x42200000 and 0xC1200
Consider the following circuit The function by the network above is
A new flipflop with inputs X and Y, has the following property Which of the following expresses the next state in terms of X,Y, current state?
If there are m input lines and n output lines for a decoder that is used to uniquely address a byte addressable 1 KB RAM, then the minimum value of m+n is ________ .
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 carr
The following circuit compares two 2-bit binary numbers, X and Y represented by and respectively. ( and represent Least Significant Bits) Under what conditions Z will be 1?
Minimum number of NAND gates required to implement the following binary equation
If ABCD is a 4-bit binary number, then what is the code generated by the following circuit?
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 of the graph is performed with
Let G be a group of 35 elements. Then the largest possible size of a subgroup of G other than G itself is _______.
Let be the set of all binary relations on the set {1,2,3}. Suppose a relation is chosen from at random. The probability that the chosen relation is reflexive (round off to 3 decimal places) is ______.
For the distributions given below : Which of the following is correct for the above distributions?
Which one of the following predicate formulae is NOT logically valid? Note that W is a predicate formula without any free occurrence of x.
Consider the functions I. II. III. Which of the above functions is/are increasing everywhere in [0,1] ?
The number of permutations of the characters in LILAC so that no character appears in its original position, if the two L's are indistinguishable, is ______.
Graph G is obtained by adding vertex s to and making s adjacent to every vertex of . The minimum number of colours required to edge-colour G is _______
If ,then will be equal to
Let A and B be two nxn matrices over real numbers. Let rank(M) and det(M) denote the rank and determinant of a matrix M, respectively. Consider the following statements. I. rank(AB)=rank (A)rank (B) I
If and , and the universe is . Then is equal to
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
For n 2, let be a non-zero vector. Suppose that x is chosen uniformly at random from . Then, the probability that is an odd number is______
The hardware implementation which provides mutual exclusion is
Consider the following statements about process state transitions for a system using preemptive scheduling. I. A running process can move to ready state. II. A ready process can move to running state.
Raymonds tree based algorithm ensures
Consider the following five disk five disk access requests of the form (request id, cylinder number) that are present in the disk scheduler queue at a given time. (P,155),(Q,85),(R,110),(S,30),(T,115)
Consider a paging system that uses 1-level page table residing in main memory and a TLB for address translation. Each main memory access takes 100 ns and TLB lookup takes 20 ns. Each page transfer to/
Which of the following algorithms defines time quantum?
Consider the following set of processes, assumed to have arrived at time 0. Consider the CPU scheduling algorithms Shortest Job First (SJF) and Round Robin (RR). For RR, assume that the processes are
Dispatch latency is defined as
Three CPU-bound tasks, with execution times of 15, 12 and 5 time units respectively arrive at times 0, t and 8, respectively. If the operating system implements a shortest remaining time first schedul
The operating system and the other processes are protected from being modified by an already running process because
An aid to determine the deadlock occurrence is
Each of a set of n processes executes the following code using two semaphores a and b initialized to 1 and 0, respectively. Assume that count is a shared variable initialized to 0 and not used in CODE
What is compaction refers to
Consider allocation of memory to a new process. Assume that none of the existing holes in the memory will exactly fit the process's memory requirement. Hence, a new hole of smaller size will be create
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 repl
The minimum height of an AVL tree with n nodes is
Consider the following C program. #include int main () { int a[4] [5] = {{1, 2, 3, 4, 5}, {6, 7,8, 9, 10}, {11, 12, 13, 14, 15}, {16, 17,18, 19, 20}}; printf("%d ", *(*(a+**a+2)+3)); return(0); } The
Consider a double hashing scheme in which the primary hash function is , and the secondary hash function is . Assume that the table size is 23. Then the address returned by probe 1 in the probe sequen
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 retturn 0; } What is the return value of th
What is the worst case time complexity of inserting n elements into an empty linked list, if the linked list needs to be maintained in sorted order?
Consider a 2-dimensional array x with 10 rows and 4 columns, with each element storing a value equivalent to the product of row number and column number. The array is stored in row-major format. If th
What is the in-order successor of 15 in the given binary search tree?
What is the output in a 32 bit machine with 32 bit compiler? #include rer(int **ptr2, int **ptr1) { int *ii; ii=*ptr2; *ptr2=*ptr1; *ptr1=ii; **ptr1*=**ptr2; **ptr2+=**ptr1; } void main(){ int var1=5,
The preorder traversal of a binary search tree is 15,10,12,11,20,18,16,19. Which one of the following is the postorder traversal of the tree?
Following declaration of an array of struct, assumes size of byte, short, int and long are 1,2,3 and 4 respectively. Alignment rule stipulates that n byte field must be located at an address divisible
Consider the array representation of a binary min-heap containing 1023 elements. The minimum number of comparisons required to find the maximum in the heap is ___________.
The post-order traversal of binary tree is ACEDBHIGF. The pre-order traversal is
Convert the pre-fix expression to in-fix
In linear hashing, if blocking factor bfr, loading factor i and file buckets N are known, the number of records will be
Consider the following C functions. The return value of fun2(5) is ______
Consider the following C functions. The value returned by pp(3,4) is _____
What is output of the following 'C' code assuming it runs on a byte addressed little endian machine? #include int main() { int x; char *ptr; x=622,100,101; printf("%d",(*(char *)&x)*(x%3)); return 0;
What is the worst case time complexity of inserting elements into an AVL-tree with n elements initially?
What is the output of the code given below? #include int main() { char name[]="satellites"; int len; int size; len= strlen(name); size = sizeof(name); printf("%d",len*size); return 0; }
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 progr
If an 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?
In a balanced binary search tree with n elements, what is the worst case time complexity of reporting all elements in range [a,b]? Assume that the number of reported elements is k.
A stack is implemented with an array of and a variable 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 p
Consider the following language. L={ number of a's in x divisible by 2 but not divisible by 3} The minimum number of states in DFA that accepts L is _______
Consider the following statements. I. If is regular, then both must be regular. II. The class of regular languages is closed under infinite union. Which of the above statements is/are TRUE?
Context free languages are closed under
Minimum number of states required in DFA accepting binary strings not ending in "101" is
Which of the following languages are undecidable? Note that indicates encoding of the Turing machine . { on input w reaches state q in exactly 100 steps}
Which of the following is true?
The language which is generated by the grammar over the alphabet of {a,b} is the set of
Consider the language and the following statements. I. L is deterministic context-free. II. L is context-free but not deterministic context-free. III. L is not LL(k) for any k. Which of the above stat
Consider the following languages. Which one of the following is TRUE?
Which one of the following regular expressions represents the set of all binary strings with an odd number of 1's?