GATE CSE 2014 PYQ

Consider the following sorting algorithms. I. Quicksort II. Heapsort III> Mergesort Which of them perform in least time in the worst case?

Suppose you want to move from 0 to 100 on the number line. In each step, you either move right by a unit distance or you take a shortcut. A shortcut is simply a pre-specified pair of integers i,j with

The minimum number of comparisons required to find the minimum and the maximum of 100 numbers is _________________.

Consider two strings A="qpqrr" and B="pqprqrp". Let x be the length of the longest common subsequence (not necessarily contiguous) between A and B and let y be the number of such longest common subseq

Let P be a quick sort program to sort numbers in ascending order using the first element as the pivot. Let t1 and t2 be the number of comparisons made by P for the inputs [1 2 3 4 5] and [4 1 5 3 2] r

Consider the tree arcs of a BFS traversal from a source node W in an unweighted, connected, undirected graph. The tree T formed by the tree arcs is a data structure for computing

Suppose P, Q, R, S, T are sorted sequences having lengths 20, 24, 30, 35, 50 respectively. They are to be merged into a single sequence by merging together two sequences at a time. The number of compa

Suppose depth first search is executed on the graph below starting at some unknown vertex. Assume that a recursive call to visit a vertex is made only after first checking that the vertex has not been

Let G be a graph with n vertices and m edges. What is the tightest upper bound on the running time of Depth First Search on G, when G is represented as an adjacency matrix?

Which one of the following correctly determines the solution of the recurrence relation with T(1) = 1?

The number of distinct minimum spanning trees for the weighted graph below is

You have an array of n elements. Suppose you implement quick sort by always choosing the central element of the array as the pivot. Then the tightest upper bound for the worst case performance is

Which of the following statements are CORRECT? 1) Static allocation of all data areas by a compiler makes it impossible to implement recursion. 2) Automatic garbage collection is essential to implemen

Which one of the following is NOT performed during compilation?

Which one of the following is FALSE?

For a C program accessing x[i][j][k], the following intermediate code is generated by a compiler. Assume that the size of an integer is 32 bits and the size of a character is 8 bits. t0 = i * 1024 t1

Consider the grammar defined by the following production rules, with two operators * and + S T *P T U| T*U P Q +P |Q Q Id U Id Which one of the following is TRUE?

One of the purposes of using intermediate code in compilers is to

Consider the following grammar. Which of the following statements is FALSE?

The minimum number of arithmetic operations required to evaluate the polynomial for a given value of x, using only one temporary variable is _____.

A canonical set of items is given below S Q R. On input symbol the set has

Which of the following is NOT represented in a subroutine's activation record frame for a stack-based programming language?

What is the number of steps required to derive the string ((() ()) ()) for the following grammar?

Consider the following Java code fragment: public class While { public void loop() { int x = 0; while(1) { System.out.println("x plus one is" +(x+1)); } } }

Consider the basic block given below. a= b + c c =a + d d =b + c e =d - b a =e + b The minimum number of nodes and edges present in the DAG representation of the above basic block respectively are

In the following pairs of OSI protocol layer/sub-layer and its functionality, the INCORRECT pair is

Identify the correct order in which the following actions take place in an interaction between a web browser and a web server. 1. The web browser requests a webpage using HTTP. 2. The web browser esta

An organization is granted the block 130.34.12.64/26. It needs to have 4 subnets. Which of the following is not an address of this organization?

Which one of the following socket API functions converts an unconnected active TCP socket into a passive socket?

Suppose you are browsing the world wide web using a web browser and trying to access the web servers. What is the underlying protocol and port number that are being used?

A supernet has a first address of 205.16.32.0 and a supernet mask of 255.255.248.0. A router receives 4 packets with the following destination addresses.which packet belongs to this supernet?

What is routing algorithm used by OSPF routing protocol?

Consider a 50 kbps satellite channel with a 500 milliseconds round trip propagation delay. If the sender wants to transmit 1000 bit frames, how much time will it take for the receiver to receive the f

A mechanism or technology used in Ethernet by which two connected devices choose common transmission parameters such as speed, duplex mode and flow control is called

Which of the following is not a valid multicast MAC address?

Which one of the following is TRUE about the interior gateway routing protocols - Routing Information Protocol (RIP) and Open Shortest Path First (OSPF)?

A bit-stuffing based framing protocol uses an 8-bit delimiter pattern of 01111110. If the output bit-string after stuffing is 01111100101, then the input bit-string is

An IP router implementing Classless Inter-domain routing (CIDR) receives a packet with address 131.23.151.76. The router's routing table has the following entries: The identifier of the output interfa

In a system an RSA algorithm with p=5 and q=11, is implemented for data security. What is the value of the decryption key if the value of the encryption key is 27?

A graphical HTML browser resident at a network client machine Q accesses a static HTML webpage from a HTTP server S. The static HTML page has exactly one static embedded image which is also at S. Assu

Which one of the following are used to generate a message digest by the network security protocols? (P) RSA (Q) SHA-1 (R) DES (S) MD5

In the diagram shown below, L1 is an Ethernet LAN and L2 is a Token-Ring LAN. An IP packet originates from sender S and traverses to R, as shown. The links within each ISP and across the two ISPs, are

An IP machine Q has a path to another IP machine H via three IP routers R1, R2, and R3. Q---R1---R2---R3---H H acts as an HTTP server, and Q connects to H via HTTP and downloads a file. Session layer

Let the size of congestion window of a TCP connection be 32 KB when a timeout occurs. The round trip time of the connection is 100 msec and the maximum segment size used is 2kB. The time taken (in mse

The process of modifying IP address information in IP packet headers while in transit across a traffic routing device is called

Assume the following information. Original timestamp value = 46 Receive timestamp value = 59 Transmit timestamp value = 60 Timestamp at arrival of packet = 69 Which of the following statements is corr

Consider the following three statements about link state and distance vector routing protocols, for a large network with 500 network nodes and 4000 links [S1] The computational overhead in link state

Consider a token ring network with a length of 2km having 10 stations including a monitoring station. The propagation speed of the signal is 2x m/s and the token transmission time is ignored. If each

Consider the store and forward packet switched network given below. Assume that the bandwidth of each link is bytes / sec. A user on host A sends a file of size bytes to host B through routers R1 and

An IP router with a Maximum Transmission Unit (MTU) of 1500 bytes has received an IP packet of size 4404 bytes with an IP header of length 20 bytes. The values of the relevant fields in the header of

A IP packet has arrived in which the fragmentation offset value is 100,the value of HLEN is 5 and the value of total length field is 200. What is the number of the last byte?

Consider a selective repeat sliding window protocol that uses a frame size of 1 KB to send data on a 1.5 Mbps link with a one-way latency of 50 msec. To achieve a link utilization of 60%, the minimum

An IP packet has arrived with the first 8 bits as 0100 0010. Which of the following is correct?

Every host in an IPv4 network has a 1-second resolution real-time clock with battery backup. Each host needs to generate up to 1000 unique identifiers per second. Assume that each host has a globally

Host A (on TCP/IP v4 network A) sends an IP datagram D to host B (also on TCP/IP V4 network B). Assume that no error occurred during the transmission of D. When D reaches B, which of the following IP

Consider the following processors (ns stands for nanoseconds). Assume that the pipeline registers have zero latency. P1: Four-stage pipeline with stage latencies 1 ns, 2 ns, 2 ns, 1 ns. P2: Four-stage

Assume that 16-bit CPU is trying to access a double word stating at an odd address. How many memory operations are required to access the data?

If each address space represents one byte of storage space, how many address lines are needed to access RAM chips arranged in a array, where each chip is bits ?

If the associativity of a processor cache is doubled while keeping the capacity and block size unchanged, which one of the following is guaranteed to be NOT affected?

Consider a 6-stage instruction pipeline, where all stages are perfectly balanced. Assume that there is no cycle-time overhead of pipelining. When an application is executing on this 6-stage pipeline,

A 4-way set-associative cache memory unit with a capacity of 16 KB is built using a block size of 8 words. The word length is 32 bits. The size of the physical address space is 4 GB. The number of bit

In designing a computer's cache system, the cache block (or cache line) size is an important Parameter. Which one of the following statements is correct in this context?

Consider two processors P1 and P2 executing the same instruction set. Assume that under identical conditions, for the same input, a program running on P2 takes 25% less time but incurs 20% more CPI (c

The memory access time is 1 nanosecond for a read operation with a hit in cache, 5 nanoseconds for a read operation with a miss in cache, 2 nanoseconds for a write operation with a hit in cache and 10

An access sequence of cache block addresses is of length N and contains n unique block addresses. The number of unique block addresses between two consecutive accesses to the same block address is bou

Suppose you want to build a memory with 4 byte words and a capacity of bits. What is type of decoder required if the memory is built using RAM chips?

A machine has a 32-bit architecture, with 1-word long instructions. It has 64 registers, each of which is 32 bits long. It needs to support 45 instructions, which have an immediate operand in addition

An instruction pipeline has five stages, namely, instruction fetch (IF), instruction decode and register fetch (ID/RF), instruction execution (Ex), memory access (MEM), and register write back (WB) wi

Consider a main memory system that consists of 8 memory modules attached to the system bus, which is one word wide. When a write request is made, the bus is occupied for 100 nanoseconds (ns) by the da

An aggregation association is drawn using which symbol?

Consider the following relational schema: Employee (empId, empName, empDept ) Customer (custId,custName, salesRepId, rating) SalesRepId is a foreign key referring to empId of the employee relation. As

Consider the relation scheme R = (E, F, G, H, I, J, K, L, M, N) and the set of functional dependencies {{E,F} {G}, {F} {I,J}, {E,H} {K,L}, {K} {M}, {L} {N} } on R. What is the key for R?

The maximum number of super keys for the relation schema R (E, F, G, H) with E as the key is __________.

Let x, y, z, a, b, c be the attributes of an entity set E. If {x}, {x,y}, {a,b}, {a,b,c}, {x,y,z} are superkeys then which of the following are the candidate keys?

Given the following statements: S1: A foreign key declaration can always be replaced by an equivalent check assertion in SQL S2: Given the table R(a,b,c) where a and b together form the primary key, t

Consider the following schedule S of transactions T1, T2, T3, T4: Which one of the following statements is CORRECT?

Consider the schema and the functional dependencies and . If the decomposition is made as and , then which of the following is TRUE?

Consider the following four schedules due to three transactions (indicted by the subscript) using read and write on a data item x, denoted by r(x) and w(x) respectively. Which one of them is conflict

SQL allows duplicate tuples in relations, and correspondingly defines the multiplicity of tuples in the result of joins. Which one of the following queries always gives the same answer as the nested q

Consider the transactions T1, T2, and T3 and the schedules S1 and S2 given below. T1 : r1(x); r1(Z) ; w1(x); w1(Z) T2 : r2(x); r2(Z); w2(Z) T3 : r3(x); r3(x); w3(Y) S1: r1(x); r3(Y); r3(x); r2(Y); r2(

Given an instance of the STUDENTS relation as shown below For (StudentName, StudentAge) to be a key for this instance, the value x should NOT be equal to_______.

Given the following schema: employees(emp-id, first-name, last-name, hire-date, dept-id, salary) departments(dept-id, dept-name, manager-id, location-id) You want to display the last names and hire da

Consider a join (relation algebra) between relations r(R)and s(S) using the nested loop method. There are 3 buffers each of size equal to disk block size, out of which one buffer is reserved for inter

Consider the following table The table is in which normal form?

What is the optimized version of the relation algebra expression , where A1, A2 are sets of attributes in r with and F1, F2 are Boolean expressions based on the attributes in r?

Consider a system where each file is associated with a 16 bit number. For each file, each user should have the read and write capability. How much memory is needed to store each user's access data?

Every time the attribute A appears, it is matched with the same value of attribute B but not the same value of attribute C. Which of the following is true?

A prime attribute of a relation scheme R is an attribute that appears

Consider the relational schema given below, where eId of the relation dependentis a foreign key referring to empId of the relation employee. Assume that every employee has at least one associated depe

Given the following two statements: S1: Every table with two single-valued attributes is in 1NF, 2NF, 3NF and BCNF S2 : AB C, D E, E C is a minimal cover for the set of functional dependencies AB C, D

Consider the logic circuit given below. The inverter, AND and OR gates have delays of 6, 10 and 11 nanoseconds respectively. Assuming that wire delays are negligible, what is the duration of glitch fo

Let denote the Exclusive OR (XOR) operation. Let '1' and '0' denote the binary constants. Consider the following Boolean Algebra for F over two variables P and Q. The equivalent expression for F is

Consider the following combinational function block involving four Boolean variables x, y, a, b where x, a, b are inputs and y is the output. f (x, y, a, b) { if (x is 1) y = a; else y = b; } Which on

The dual of a Boolean function , written as , is the same expression as that of F with + and swapped. F is said to be self-dual if . The number of self-dual functions with n Boolean variables is

Consider the following minterm expression for F. F(P,Q,R,S) = 0, 2, 5, 7, 8, 10, 13, 15 The minterms 2, 7, 8 and 13 are 'do not care terms. The minimal sum of-products form for F is

Consider the logic circuit given below: Q=__________?

Consider the following Boolean Algebra for F: The minimal sum-of products form of F is

Consider the equation with x and y as unknown. The number of possible solutions is _____ .

Consider the 4-to-1 multiplexer with two lines S1 and S0 given below. The minimal sum of-products form of the Boolean expression for the output F of the multiplexer is

Let . A circuit is built by giving the output of an n-bit binary counter as input to an n-to- bit decoder. This circuit is equivalent to a

The above synchronous sequential circuit built using JK flip-flops is initialized with = 000. The state sequence for this circuit for the next 3 clock cycles is

In the standard IEEE 754 single precision floating point representation, there is 1 bit for sign, 23 bits for fraction and 8 bits for exponent. What is the precision in terms of the number of decimal

How many different BCD numbers can be stored in 12 switches ? (Assume two position or on-off switches).

The value of a float type variable is represented using the single-precision 32-bit floating point format of IEEE-754 standard that uses 1 bit for sign, 8 bits for biased exponent and 23 bits for mant

The output of a tristate buffer when the enable input in 0 is

The base (or radix) of the number system such that the following equation holds is_______.

Which of the following is not valid Boolean algebra rule ?

What are the final values of Q1 and Q0 after 4 clock cycles, if initial values are 00 in the sequential circuit shown below:

Let S denote the set of all functions f: . Denote by N the number of functions from S to the set {0,1}. The value of is______.

A function f(x) is continuous in the interval [0,2]. It is known that f(0)=f(2)=-1 and f(1)=1. Which one of the following statements must be true?

In the Newton-Raphson method, an initial guess of is made and the sequence is obtained for the function Consider the statements (I) =0. (II) The method converges to a solution in a finite number of it

The conic section that is obtained when a right circular cone is cut through a plane that is parallel to the side of the cone is called _____

The CORECT formula for the sentence, "not all rainy days are cold" is

The value of the integral given below is

The rank of the matrix is ____ .

An ordered n-tuple ( ) with is called graphic if there exists a simple undirected graph with n vertices having degrees respectively. Which of the following 6-tuples is NOT graphic?

Four fair six-sided dice are rolled. The probability that the sum of the results being 22 is . The value of X is _________

Let denote the minimum degree of a vertex in a graph. For all planar graphs on n vertices with , which one of the following is TRUE?

The security system at an IT office is composed of 10 computers of which exactly four are working. To check whether the system is functional, the officials inspect four of the computers picked at rand

The probability that a given positive integer lying between 1 and 100 (both inclusive) is NOT divisible by 2, 3 or 5 is ______ .

Which one of the following statements is TRUE about every n x n matrix with only real eigenvalues?

The number of distinct positive integral factors of 2014 is ____

Suppose depth first search is executed on the graph below starting at some unknown vertex. Assume that a recursive call to visit a vertex is made only after first checking that the vertex has not been

If V1 and V2 are 4-dimensional subspaces of a 6-dimensional vector space V, then the smallest possible dimension of V1 V2 is _______.

Consider the directed graph given below. Which one of the following is TRUE?

Each of the nine words in the sentence "The quick brown fox jumps over the lazy dog" is written on a separate piece of paper. These nine pieces of paper are kept in a box. One of the pieces is drawn a

A cube of side 1 unit is placed in such a way that the origin coincides with one of its top vertices and the three axes along three of its edges. What are the co-ordinates of the vertex which is diago

What is the median of data if its mode is 15 and the mean is 30?

Consider the following relation on subsets of the set S of integers between 1 and 2014. For two distinct subsets U and V of S we say U V if the minimum element in the symmetric difference of the two s

The probability that two friends are born in the same month is ____ ?

If G is a forest with n vertices and k connected components, how many edges does G have?

There are two elements x,y in a group (G,*) such that every element in the group can be written as a product of some number of x's and y's in some order. It is known that x * x = y * y = x * y *x * y

The maximum number of edges in a bipartite graph on 12 vertices is _____.

There are 5 bags labelled 1 to 5. All the coins in a given bag have the same weight. Some bags have coins of weight 10 gm, others have coins of weight 11 gm. I pick 1, 2, 4, 8, 16 coins respectively f

Consider an undirected graph G where self-loops are not allowed. The vertex set of G is {(i,f):1 i 12, 1 j 12}. There is an edge between (a,b) and (c,d) if |a-c| 1 and |b-d| 1. The number of edges in

The number of bit strings of length 8 that will either start with 1 or end with 00 is?

Suppose you break a stick of unit length at a point chosen uniformly at random. Then the expected length of the shorter stick is

The function satisfies the following equation: . The value of t is______.

If the matrix A is such that Then the determinant of A is equal to ________.

A pennant is a sequence of numbers, each number being 1 or 2. An n-pennant is a sequence of numbers with sum equal to n. For example, (1,1,2) is a 4-pennant. The set of all possible 1- pennants is {(1

Consider the set of all functions f:{0,1,...,2014} {0,1...,2014} such that f(f(i))=i, for 0 i 2014 . Consider the following statements. P. For each such function it must be the case that for every i,

If , then the value of k is equal to _______.

The value of the dot product of the eigenvectors corresponding to any pair of different eigenvalues of a 4-by-4 symmetric positive definite matrix is

Let G=(V,E) be a directed graph where V is the set of vertices and E the set of edges. Then which one of the following graphs has the same strongly connected components as G ?

Consider the following system of equations: 3x + 2y = 1 4x + 7z = 1 x + y + z = 3 x - 2y + 7z = 0 The number of solutions for this system is

A cycle on n vertices is isomorphic to its complement. The value of n is _____.

Let the function where and denote the derivative of f with respect to . Which of the following statements is/are TRUE? (I) There existrs such that (I) There existrs such that

A non-zero polynomial f(x) of degree 3 has roots at x = 1,x = 2 and x = 3. Which one of the following must be TRUE?

Consider the following statements: P: Good mobile phones are not cheap Q: Cheap mobile phones are not good L: P implies Q M: Q implies P N: P is equivalent to Q Which one of the following about L, M,

Let G be a group with 15 elements. Let L be a subgroup of G. It is known that L G and that the size of L is at least 4. The size of L is _______.

The product of the non-zero eigenvalues of the matrix is_______.

Let A be a finite set having elements and let B be a finite set having elements. What is the number of distinct functions mapping B into A.

Let A be a square matrix size n x n. Consider the following pseudocode. What is the expected output? C = 100; for i = 1 to n do for j = 1 to n do { Temp = A[ i ] [ j ] + C ; A [ i ] [ j ] = A [ j ] [

Let G be a graph with n vertices and m edges. What is the tightest upper bound on the running time of Depth First Search on G, when G is represented as an adjacency matrix?

With respect to the numerical evaluation of the definite integral, , where a and b are given, which of the following statements is/are TRUE? (I) The value of K obtained using the trapezoidal rule is a

Let S be a sample space and two mutually exclusive events A and B be such that A B = S. If P(.) denotes the probability of the event, the maximum value of P(A)P(B) is ______

Which one of the following propositional logic formulas is TRUE when exactly two of p, q, and r are TRUE?

Let x and Y be finite sets and f:x Y be a function. Which one of the following statements is TRUE?

Consider the statement "Not all that glitters is gold" Predicate glitters(x) is true if x glitters and predicate gold(x) is true if x is gold. Which one of the following logical formulae represents th

A FAT (file allocation table) based file system is being used and the total overhead of each entry in the FAT is 4 bytes in size. Given a 100x bytes disk on which the file system is stored and data bl

A system uses 3 page frames for storing process pages in main memory. It uses the Least Recently Used (LRU) page replacement policy. Assume that all the page frames are initially empty. What is the to

A computer has 16 pages of virtual address space but the size of main memory is only four frames. Initially the memory is empty. A program references the virtual pages in the order 0, 2, 4, 5, 2, 4, 3

Consider the following segment table in segmentation scheme : What happens if the logical address requested is - Segment Id 2 and offset 1000?

Three processes A, B and C each execute a loop of 100 iterations. In each iteration of the loop, a process performs a single computation that requires CPU milliseconds and then initiates a single I/O

Consider the procedure below for the Producer-Consumer problem which uses semaphores: Which one of the following is TRUE?

What is the size of the physical address space in a paging system which has a page table containing 64 entries of 11 bit each (including valid and invalid bit) and a page size of 512 bytes?

Using the page table shown below, translate the physical address 25 to virtual address. The address length is 16 bits and page size is 2048 words while the size of the physical memory is four frames.

An operating system uses the Banker's algorithm for deadlock avoidance when managing the allocation of three resource types X, Y, and Z to three processes P0, P1, and P2. The table given below present

Consider a paging hardware with a TLB. Assume that the entire page table and all the pages are in the physical memory. It takes 10 milliseconds to search the TLB and 80 milliseconds to access the phys

What is the minimum number of resources required to ensure that deadlock will never occur, if there are currently three processes , and running in a system whose maximum demand for the resources of sa

Assume that there are 3 page frames which are initially empty. If the page reference string 1, 2, 3, 4, 2, 1, 5, 3, 2, 4, 6, the number of page faults using the optimal replacement policy is ______

Which one of the following is FALSE?

Consider the following set of processes that need to be scheduled on a single CPU. All the times are given in milliseconds Using the shortest remaining time first scheduling algorithm, the average pro

A system contains three programs and each requires three tape units for its operation. The minimum number of tape units which the system must have such that deadlocks never arise is _________.

Which of the following is not an optimization criterion in the design of a CPU scheduling algorithm?

Dirty bit is used to indicate which of the following?

Suppose a disk has 201 cylinders, numbered from 0 to 200. At some time the disk arm is at cylinder 100, and there is a queue of disk access requests for cylinders 30, 85, 90, 100, 105, 110, 135 and 14

An operating system uses shortest remaining time first scheduling algorithm for pre-emptive scheduling of processes. Consider the following set of processes with their arrival times and CPU burst time

A computer has twenty physical page frames which contain pages numbered 101 through 120. Now a program accesses the pages numbered 1, 2, ..., 100 in that order, and repeats the access sequence THRICE.

There are 200 tracks on a disc platter and the pending requests have come in the order - 36, 69, 167, 76, 42, 51, 126, 12 and 199. Assume the arm is located at the 100th track and moving towards track

Consider the following function double f (double x) { if ( abs (x*x - 3) < 0. 01) return x; else return f (x / 2 + 1.5/x); } Give a value q (to 2 decimals) such that f(q) will return q:______

Consider the function func shown below: int func(int num) { int count = 0; while (num) { count++; num >> = 1; } return (count); } The value returned by func(435)is __________.

Consider a 13 element hash table for which f(key)=key mod 13 is used with integer keys. Assuming linear probing is used for collision resolution, at which location would the key 103 be inserted, if th

How many lines of output does the following C code produce? #include float i=2.0; float j=1.0; float sum = 0.0; main() { while (i/j > 0.001) { j+=j; sum=sum+(i/j); printf("%f ", sum); } }

Suppose there are 11 items in sorted order in an array. How many searches are required on the average, if binary search is employed and all searches are successful in finding the item?

Consider the pseudocode given below. The function Dosomething () takes as argument a pointer to the root of an arbitrary tree represented by the leftMostChild-rightSibling representation. Each node of

Consider the expression tree shown. Each leaf represents a numerical value, which can either be 0 or 1. Over all possible choices of the values at the leaves, the maximum possible value of the express

Consider the following program in C language: # include main() { int i; int * pi = &i; scanf( "%d", pi) ; printf ("%d \ n", i+5) ; } Which one of the following statements is TRUE?

Consider the following C function in which size is the number of elements in the array E: int MyX(int *E, unsigned int size) { int Y = 0; int Z; int i, j, k; for(i = 0; i Y) Y = Z; } return Y; } The v

Consider the C function given below int f(int j) { static int i = 50; int k; if (i == j) { printf("something"); k = f(i); return 0; } else return 0; } Which one of the following is TRUE?

Suppose a stack implementation supports an instruction REVERSE, which reverses the order of elements on the stack, in addition to the PUSH and POP instructions. Which one of the following statements i

Consider rooted n node binary tree represented using pointers. The best upper bound on the time required to determine the number of sub trees having exactly 4 nodes is . Then the value of a+10b is____

Consider a hash table with 100 slots. Collisions are resolved using chaining. Assuming simple uniform hashing, what is the probability that the first 3 slots are unfilled after the first 3 insertions?

Consider a single linked list where F and L are pointers to the first and last elements respectively of the linked list. The time for performing which of the given operations depends on the length of

The following three 'C' language statements is equivalent to which single statement? y=y+1; z=x+y; x=x+1

A frame buffer array is addressed in row major order for a monitor with pixel locations starting from (0,0) and ending with (100,100). What is address of the pixel(6,10)? Assume one bit storage per pi

Suppose n and p are unsigned int variables in a C program. We wish to set p to . If n is large, which one of the following statements is most likely to set p correctly?

Which of the following is true with respect to Reference?

A priority queue is implemented as a Max-Heap. Initially, it has 5 elements. The level-order traversal of the heap is: 10, 8, 5, 3, 2. Two new elements 1 and 7 are inserted into the heap in that order

What is the output of the following C program? #include void main(void){ int shifty; shifty=0570; shifty=shifty>>4; shifty=shifty<<6; printf("The value of shifty is %o ",shifty); }

How many different trees are there with four nodes A,B,C and D?

Consider the C function given below. Assume that the array listA contains n (> 0) elements, sorted in ascending order. int ProcessArray(int *listA, int x, int n) { int i, j, k; i = 0; j = n-1; do { k

Consider the following binary search tree T given below: Which node contains the fourth smallest element in T?

Consider a standard Circular Queue implementation (which has the same condition for Queue Full and Queue Empty) whose size is 11 and the elements of the queue are q[0],q[1],... q[10]. The front and re

Suppose we have a balanced binary search tree T holding n numbers. We are given two numbers L and H and wish to sum up all the numbers in T that lie between L and H. Suppose there are m such numbers i

Consider the following pseudo code. What is the total number of multiplications to be performed? D= 2 for i = 1 to n do for j = i to n do for k = j + 1 to n do D = D * 3

What is the time complexity for the following C module? Assume that . int module(int n) { if (n == 1) return 1; else return (n + module(n-1)); }

What is the output of the following C program? #include #define SQR(x) (x*x) int main() { int a; int b=4; a=SQR(b+2); printf("%d ",a); return 0; }

Consider a hash table with 9 slots. The hash function is h(k)=k mod 9. The collisions are resolved by chaining. The following 9 keys are inserted in the order: 5, 28, 19, 15, 20, 33, 12, 17, 10. The m

Which of the regular expressions given below represent the following DFA? I) 0*1(1+00*1)* II) 0*1*1+11*0*1 III) (0+1)*1

Which of the following is FALSE with respect to possible outcomes of executing a Turing Machine over a given input?

Consider the following languages over the alphabet Here is the reverse of the string w. Which of these languages are deterministic Contextfree languages?

Let denotes that language A is mapping reducible (also known as many-to-one reducible) to language B. Which one of the following is FALSE?

Consider the finite automaton in the following figure. What is the set of reachable states for the input string 0011?

Consider the following Deterministic Finite Automaton M. Let S denote the set of eight bit strings whose second, third, sixth and seventh bits are 1. The number of strings in S that are accepted by M

Which one of the following problems is undecidable?

How many states are there in a minimum state deterministic finite automaton accepting the language , number of 0's is divisible by 2 and number of 1's is divisible by 5, respectively }?

The number of states required by a Finite State Machine,to simulate the behavior of a computer with a memory capable of storing 'm' words, each of length 'n' bits is?

Let be a finite non-empty alphabet and let be the power set of . Which one of the following is TRUE?

Which one of the following is TRUE?

The following Finite Automaton recognizes which of the given languages?

Let L be a language and be its complement. Which of the following is NOT a viable possibility?

The length of the shortest string NOT in the language (over ={a,b}) of the following regular expression is _________. a*b* (ba)* a*

If and , Consider (I) is a regular language (II) Which one of the following is CORRECT?

Let has at least as many occurrences of (110)'s as (011)'s}. Let has at least as many occurrence of (000)'s as (111)'s}. Which one of the following is TRUE?

Let be the encoding of a Turing machine as a string over ={0,1}. Let L = { |M is a Turning machine that accepts a string of length 2014}. Then, L is