GATE CSE 2015 PYQ

Consider the following C function. int fun1(int n){ int i,j,k,p,q=0; for (i=1; i 1; j=j/2) ++p; for (k=1; k < p; k=k*2) ++q; } return q; } Which one of the following most closely approximates the retu

Let G = (V, E) be a simple undirected graph, and s be a particular vertex in it called the source. For , let d(x) denote the shortest distance in G from s to x. A breadth first search (BFS) is perform

Let G be a connected undirected graph of 100 vertices and 300 edges. The weight of a minimum spanning tree of G is 500. When the weight of each edge of G is increased by five, the weight of a minimum

The number of spanning trees for a complete graph with seven vertices is

The time complexity of the following C function is (assume n>0) int recursive (int n) { if(n == 1) return (1); else return (recursive (n-1) + recursive (n-1)); }

If one uses straight two-way merge sort algorithm to sort the following elements in ascending order: 20, 47, 15, 8, 9, 4, 40, 30, 12, 17 then the order of these elements after second pass of the algor

A machine needs a minimum of 100 sec to sort 1000 names by quick sort. The minimum time needed to sort 100 names will be approximately

Let G = (V, E) be a simple undirected graph, and s be a particular vertex in it called the source. For , let d(x) denote the shortest distance in G from s to x. A breadth first search (BFS) is perform

Match the following:

A Young tableau is a 2D array of integers increasing from left to right and from top to bottom. Any unfilled entries are marked with , and hence there cannot be any entry to the right of, or below a .

Consider the equality and the following choices for X I. II. III. IV. The equality above remains correct if X is replaced by

Let and where n is a positive integer. Which of the following statements is/are correct? I. II.

Assume that a mergesort algorithm in the worst case takes 30 seconds for an input of size 64. Which of the following most closely approximates the maximum input size of a problem that can be solved in

The graph shown below has 8 edges with distinct integer edge weights. The minimum spanning tree (MST) is of weight 36 and contains the edges: {(A, C), (B, C), (B, E), (E, F), (D, F)}. The edge weights

Suppose you are provided with the following function declaration in the C programming language. int partition(int a[ ], int n); The function treats the first element of a[] as a pivot, and rearranges

Which one of the following is the recurrence equation for the worst case time complexity of the Quicksort algorithm for sorting n ( 2) numbers? In the recurrence equations given in the options below,

Given below are some algorithms, and some algorithm design paradigms. Match the above algorithms on the left to the corresponding design paradigm they follow.

Consider the following grammar S F|H F p|c H d|c where S,F, and H are non-terminal symbols, p,d, and c are terminal symbols. Which of the following statement(s) is/are correct? S1. LL(1) can parse all

Which one of the following is TRUE at any valid state in shift-reduce parsing?

Which statement is true?

Consider the intermediate code given below. (1) i = 1 (2) j = 1 (3) t1 = 5 * i (4) t2 = t1 + j (5) t3 = 4 * t2 (6) t4 = t3 (7) a[t4] = -1 (8) j = j + 1 (9) if j 5 goto (3) (10) i=i+1 (11) if i 5 goto

Which one of the following is a top-down parser?

Among simple LR (SLR) , canonical LR, and look-ahead LR (LALR), which of the following pairs identify the method that is very easy to implement and the method that is the most powerful , in that order

The least number of temporary variables required to create a three-address code in static single assignment form for the expression q + r / 3 + s - t * 5 + u * v /w is _______________.

Which grammar rules violate the requirement of the operator grammar? A, B, C are variables and a, b, c are terminals 1. 2. 3. 4.

A variable x is said to be live at a statement in a program if the following three conditions hold simultaneously: i. There exists a statement that uses x ii. There is a path from to in the flow graph

Match the following:

The number of tokens in the following C statement is printf("i=%d, &i=%x", i, &i);

Given the following expression grammar: Which of the following is true?

In the context of abstract-syntax-tree (AST) and control-flow-graph (CFG), which one of the following is TRUE?

Yacc stands for

In the network 200.10.11.144/27, the fourth octet (in decimal) of the last IP address of the network which can be assigned to a host is ____________.

In one of the pairs of protocols given below, both the protocols can use multiple TCP connections between the same client and the server. Which one is that?

A link has a transmission speed of bits/sec. It uses data packets of size 1000 bytes each. Assume that the acknowledgment has negligible transmission delay, and that its propagation delay is the same

In CRC if the data unit is 100111001 and the divisor is 1011 then what is dividend at the receiver?

In a class B subnet, we know the IP address of one host and the mask as given below: IP address: 125.134.112.66 Mask: 255.255.224.0 What is the first address(Network address)?

Which layers of the OSI reference model are host-to-host layers?

Consider a CSMA/CD network that transmits data at a rate of 100 Mbps ( bits per second) over a 1 km (kilometer) cable with no repeaters. If the minimum frame size required for this network is 1250 byt

How many bits internet address is assigned to each host on a TCP/IP internet which is used in all communication with the host?

A certain population of ALOHA users manages to generate 70 request/sec. If the time is slotted in units of 50 msec, then channel load would be

Assume that the bandwidth for a TCP connection is 1048560 bits/sec. Let be the value of RTT in milliseconds (rounded off to the nearest integer) after which the TCP window scale option is needed. Let

How many characters per sec (7 bits + 1 parity) can be transmitted over a 2400 bps line if the transfer is synchronous ( 1 start and 1 stop bit)?

Suppose two hosts use a TCP connection to transfer a large file. Which of the following statements is/are FALSE with respect to the TCP connection? I. If the sequence number of a segment is m, then th

Consider a network connecting two systems located 8000 kilometers apart. The bandwidth of the network is 500x bits per second. The propagation speed of the media is 4x meters per second. It is needed

An ACK number of 1000 in TCP always means that

Which statement is false?

Consider the following routing table at an IP router: For each IP address in Group I identify the correct choice of the next hop from Group II using the entries from the routing table above.

A router uses the following routing table: Packet bearing a destination address 144.16.68.117 arrives at the router. On which interface will it be forwarded?

Consider the following statements. I. TCP connections are full duplex II. TCP has no option for selective acknowledgement III. TCP connections are message streams

Suppose that the stop-and-wait protocol is used on a link with a bit rate of 64 kilobits per second and 20 milliseconds propagation delay. Assume that the transmission time for the acknowledgement and

Two hosts are connected via a packet switch with bits per second links. Each link has a propagation delay of 20 microseconds. The switch begins forwarding a packet 35 microseconds after it receives th

A T-switch is used to

Which one of the following fields of an IP header is NOT modified by a typical IP router?

The DNS maps the IP address to

Host A sends a UDP datagram containing 8880 bytes of user data to host B over an Ethernet LAN. Ethernet frames may carry data up to 1500 bytes (i.e. MTU=1500 bytes). Size of UDP header is 8 bytes and

Suppose that everyone in a group of N people wants to communicate secretly with the N-1 others using symmetric key cryptographic system. The communication between any two persons should not be decodab

Which one of the following statements is NOT correct about HTTP cookies?

Consider a LAN with four nodes . Time is divided into fixed-size slots, and a node can begin its transmission only at the beginning of a slot. A collision is said to have occurred if more than one nod

What frequency range is used for microwave communications, satellite and radar?

Consider the following reservation table for a pipeline having three stages S1,S2 and S3. The minimum average latency (MAL) is ________.

In X=(M+NxO)/(PxQ), how many one-address instructions are required to evaluate it?

Consider the following code sequence having five instructions I1 to I5. Each of these instructions has the following format. OP Ri, Rj, Rk where operation OP is performed on contents of registers Rj a

Assume that for a certain processor, a read request takes 50 nanoseconds on a cache miss and 5 nanoseconds on a cache hit. Suppose while running a program, it was observed that 80% of the processor's

The contents of the flag register after execution of the following program by 8085 microprocessor will be Program SUB A MVI B,(01)H DCR B HLT

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

Six files F1, F2, F3, F4, F5 and F6 have 100, 200, 50, 80, 120, 150 records respectively. In what order should they be stored so as to optimize act. Assume each file is accessed with the same frequenc

Consider a machine with a byte addressable main memory of bytes, block size of 16 bytes and a direct mapped cache having cache lines. Let the addresses of two consecutive bytes in main memory be and .

Consider a processor with byte-addressable memory. Assume that all registers, including Program Counter (PC) and Program Status Word (PSW), are of size 2 bytes. A stack in the main memory is implement

For computers based on three-address instruction formats, each address field can be used to specify which of the following: (S1) A memory operand (S2) A processor register (S3) An implied accumulator

Consider the sequence of machine instructions given below: MUL R5, R0, R1 DIV R6, R2, R3 ADD R7, R5, R6 SUB R8, R7, R4 In the above sequence, R0 to R8 are general purpose registers. In the instruction

A hard disk system has the following parameters : Number of tracks =500 Number of sectors/track =100 Number of bytes /sector =500 Time taken by the head to move from one track to adjacent track =1 ms

Consider a typical disk that rotates at 15000 rotations per minute (RPM) and has a transfer rate of 50x bytes/sec. If the average seek time of the disk is twice the average rotational delay and the co

Consider a disk pack with a seek time of 4 milliseconds and rotational speed of 10000 rotations per minute (RPM). It has 600 sectors per track and each sector can store 512 bytes of data. Consider a f

How many 32K x 1 RAM chips are needed to provide a memory capacity of 256K-bytes?

Consider the following relational query on the above database: SELECT S.name FROM Suppliers S Where S.sid NOT IN (SELECT C.sid FROM Catalog C WHERE C.pid NOT IN (SELECT P.pid FROM Parts P WHERE P.colo

Consider the following transaction involving two bank accounts x and y. read(x); x:=x-50; write(x); read(y); y:=y+50; write(y) The constraint that the sum of the accounts x and y should remain constan

Consider the following Relationship Entity Diagram(ERP) Which of the following possible relations will not hold if the above ERD is mapped into a relation model?

A file is organized so that the ordering of data records is the same as or close to the ordering of data entries in some index. Then that index is called

The maximum length of an attribute of type text is

Consider two relations R1(A,B) with the tuples (1,5), (3,7) and R2(A,C) = (1,7), (4,9). Assume that R(A,B,C) is the full natural outer join of R1 and R2. Consider the following tuples of the form (A,B

Consider a B+ tree in which the search key is 12 bytes long, block size is 1024 bytes, record pointer is 10 bytes long and block pointer is 8 bytes long. The maximum number of keys that can be accommo

SELECT operation in SQL is equivalent to

Consider an Entity-Relationship (ER) model in which entity sets E1 and E2 are connected by an m : n relationship R12. E1 and E3 are connected by a 1 : n (1 on the side of E1 and n on the side of E3) r

Let R=(A,B,C,D,E,F) be a relation scheme with the following dependencies , , , . Which of the following is a key of R?

Consider the following relation Cinema(theater, address, capacity) Which of the following options will be needed at the end of the SQL query SELECT P1.address FROM Cinema P1 such that it always finds

Consider the following schema: Emp (Empcode, Name, Sex, Salary, Deptt) A simple SQL query is executed as follows: SELECT Deptt FROM Emp where sex = 'Male' GROUP by Dept Having avg (Salary) > {select a

Consider the following partial Schedule S involving two transactions T1 and T2. Only the read and the write operations have been shown. The read operation on data item P is denoted by read(P) and the

Consider a simple checkpointing protocol and the following set of operations in the log. (start, T4); (write, T4, y, 2, 3); (start, T1); (commit, T4); (write, T1, z, 5, 7); (checkpoint); (start, T2);

If are domains in a relational model, then the relation is a table, which is a subset of

Given a block can hold either 3 records or 10 key pointers. A database contains n records, then how many blocks do we need to hold the data file and the dense index

Consider the following log sequence of two transactions on a bank account, with initial balance 12000, that transfer 2000 to a mortgage payment and then apply a 5% interest. 1.T1 start 2.T1 B old =120

Consider the following relations: Consider the following SQL query. The number of rows that will be returned by the SQL query is _____________.

Consider the relation X(P,Q,R,S,T,U) with the following set of functional dependencies F= {{P,R} {S,T}, {P,S,U} {Q,R} } Which of the following is the trivial functional dependency in , where is closur

The number of min-terms after minimizing the following Boolean Algebra is _________.

The total number of prime implicants of the function f(w,x,y,z)= (0,2,4,5,6,10) is _______.

Let # be a binary operator defined as X#Y=X'+Y' where X and Y are Boolean variables. Consider the following two statements. (S1) (P # Q) # R = P # (Q # R) (S2) Q # R = R # Q Which of the following is/

The range of integers that can be represented by an n bit 2's complement number system is:

Which of the given number has its IEEE-754 32-bit floating point representation as (0 10000000 110 0000 0000 0000 0000 0000)

Given the function F=P'+QR , where F is a function in three Boolean variables P,Q and R and P'=!P, consider the following statements. (S1) F= (4,5,6) (S2) F= (0,1,2,3,7) (S3) F= (4,5,6) (S4) F= (0,1,2

If half adders and full adders are implements using gates, then for the addition of two 17 bit numbers (using minimum gates) the number of half adders and full adders required will be

The code which uses 7 bits to represent a character is :

The minimum number of JK flip-flops required to construct a synchronous counter with the count sequence (0,0,1,1,2,2,3,3,0,0,...) is __________ .

A positive edge-triggered D flip-flop is connected to a positive edge-triggered JK flip-flop as follows. The Q output of the D flip-flop is connected to both the J and K inputs of the JK flip-flop, wh

A half adder is implemented with XOR and AND gates. A full Combinational Circuit is implemented with two half Combinational Circuits and one OR gate. The propagation delay of an XOR gate is twice that

Minimum number of 2x1 multiplexers required to realize the following function, Assume that inputs are available only in true form and Boolean a constant 1 and 0 are available.

The complement of the Boolean expression is

The boolean expression is independent of the boolean variable

Consider a 4-bit Johnson counter with an initial value of 0000. The counting sequence of this counter is

Consider the equation where x and y are unknown. The number of possible solutions is ______________

A modulus -12 ring counter requires a minimum of

The decimal number has 64 digits. The number of bits needed for its equivalent binary representation is?

Consider the operations and . Which one of the following is correct?

The number of 1's in the binary representation of are:

The larger of the two eigenvalues of the matrix is _______.

Which one of the following well formed formulae is a tautology?

If for non-zero where then is

The number of divisors of 2100 is _____ .

Let X and Y denote the sets containing 2 and 20 distinct objects respectively and F denote the set of all possible functions defined from X to Y. Let f be randomly chosen from F. The probability of f

Which one of the following is NOT equivalent to ?

The binary operator is defined by the following truth table. Which one of the following is true about the binary operator ?

For a set A, the power set of A is denoted by . If A={5,{6},{7}}, which of the following options are TRUE? I. II. III. {5,{6}} IV. {5,{6}}

In the LU decomposition of the matrix , if the diagonal elements of U are both 1, then the lower diagonal entry of L is________.

In the given matrix , one of the eigenvalues is 1. The eigenvectors corresponding to the eigenvalue 1 are

Let and A denote the area of the region bounded by f(x) and the x-axis, when x varies from -1 to 1. Which of the following statements is/are TRUE? I) f is continuous in [-1,1] II) f is not bounded in

Let G = (V, E) be a simple undirected graph, and s be a particular vertex in it called the source. For , let d(x) denote the shortest distance in G from s to x. A breadth first search (BFS) is perform

The velocity v (in kilometer/minute) of a motorbike which starts from rest, is given at fixed intervals of time t (in minutes) as follows: The approximate distance (in kilometers) rounded to two place

The number of onto functions (surjective functions) from set x={1,2,3,4} to set Y={a,b,c} is __________.

Let represent the number of bit strings of length n containing two consecutive 1s. What is the recurrence relation for ?

Consider the following two statements. S1: If a candidate is known to be corrupt, then he will not be elected S2: If a candidate is kind, he will be elected Which one of the following statements follo

Let R be a relation on the set of ordered pairs of positive integers such that if and only if . Which one of the following is true about R?

=__________ .

In a room there are only two types of people, namely Type 1 and Type 2. Type 1 people always tell the truth and Type 2 people always lie. You give a fair coin to a person in that room, without knowing

The number of 4 digit numbers having their digits in non-decreasing order (from left to right) constructed by using the digits belonging to the set {1, 2, 3} is____________.

The secant method is used to find the root of an equation f(x)=0. It is started from two distinct estimates and for the root. It is an iterative procedure involving linear interpolation to a root. The

is

Consider the following 2x2 matrix A where two elements are unknown and are marked by a and b. The eigenvalues of this matrix are -1 and 7. What are the values of a and b? .

If the following system has non-trivial solution, px+qy+rz=0 qx+ry+pz=0 rx+py+qz=0, then which one of the following options is TRUE?

Let R be the relation on the set of positive integers such that aRb if and only if a and b are distinct and have a common divisor other than 1. Which one of the following statements about R is true?

A graph is self-complementary if it is isomorphic to its complement. For all self-complementary graphs on n vertices, n is

Perform the following operations on the matrix . (i) Add the third row to the second row (ii) Subtract the third column from the first column. The determinant of the resultant matrix is___________.

Suppose for i =1,2,3 are independent and identically distributed random variables whose probability mass functions are for i=1,2,3. Define another random variable denotes XOR. Then _______________.

Suppose L={p,q,r,s,t} is a lattice represented by the following Hasse diagram: For any not necessarily distinct, and are join and meet of x,y respectively. Let be the set of all ordered triplets of th

_________.

Suppose U is the power set of the set S={1,2,3,4,5,6}. For any T U, let |T| denote the number of elements in T and T' denote the complement of T. For any T,R U, let T be the set of all elements in T w

The cardinality of the power set of { 0, 1, 2,..., 10 } is _________.

Let G be a connected planar graph with 10 vertices. If the number of edges on each face is three, then the number of edges in G is ___________.

If and , then is:

In a connected graph, a bridge is an edge whose removal disconnects a graph. Which one of the following statements is true?

The value of is

Suppose two jobs, each of which needs 10 minutes of CPU time, start simultaneously. Assume 50% I/O wait time. How long will it take for both to complete, if they run sequentially?

Choose the correct alternatives (more than one may be correct) and write the corresponding letters only: At a particular time of computation, the value of a counting semaphore is 7. Then 20 P operatio

A computer system implements 8 kilobyte pages and a 32-bit physical address space. Each page table entry contains a valid bit, a dirty bit, three permission bits, and the translation. If the maximum s

Consider six memory partitions of sizes 200 KB, 400 KB, 600 KB, 500 KB, 300 KB and 250 KB, where KB refers to kilobyte. These partitions need to be allotted to four processes of sizes 357 KB, 210 KB,

Consider the following policies for preventing deadlock in a system with mutually exclusive resources. I. Processes should acquire all their resources at the beginning of execution. If any resource is

Increasing the RAM of a computer typically improves performance because:

If there are 32 segments, each size 1k bytes, then the logical address should have

A computer system implements a 40-bit virtual address, page size of 8 kilobytes, and a 128-entry translation look-aside buffer (TLB) organized into 32 sets each having four ways. Assume that the TLB t

Dirty bit for a page in a page table

Consider a uniprocessor system executing three tasks T1, T2 and T3, each of which is composed of an infinite sequence of jobs (or instances) which arrive periodically at intervals of 3, 7 and 20 milli

Consider a system with byte-addressable memory, 32-bit logical addresses, 4 kilobyte page size and page table entries of 4 bytes each. The size of the page table in the system in megabytes is ________

Semaphores are used to solve the problem of I. Race Condition II. Process Synchronization III. Mutual Exclusion IV. None of the above

For the processes listed in the following table, which of the following scheduling schemes will give the lowest average turnaround time?

A system has 6 identical resources and N processes competing for them. Each process can request atmost 2 resources. Which one of the following values of N could lead to a deadlock?

The following two functions P1 and P2 that share a variable B with an initial value of 2 execute concurrently. The number of distinct values that B can possibly take after the execution is____________

The maximum number of processes that can be in Ready state for a computer system with n CPUs is

Identify the correct order in which a server process must invoke the function calls accept, bind, listen, and recv according to UNIx socket API.

Consider a main memory with five page frames and the following sequence of page references: 3, 8, 2, 3, 9, 1, 6, 3, 8, 9, 3, 6, 2, 1, 3. Which one of the following is true with respect to page replace

Consider the following program. main() { fork(); fork(); fork(); } How many new processes will be created?

Suppose a system contains n processes and system uses the round-robin algorithm for CPU scheduling then which data structure is best suited ready queue of the process

Two processes X and Y need to access a critical section. Consider the following synchronization construct used by both the processes Here, varP and varQ are shared variables and both are initialized t

Suppose the following disk request sequence (track numbers) for a disk with 100 tracks is given: 45, 20, 90, 10, 50, 60, 80, 25, 70. Assume that the initial position of the R/W head is on track 50. Th

In a lottery scheduler with 40 tickets, how we will distribute the tickets among 4 processes P1,P2,P3 and P4 such that each process gets 10%, 5%, 60% and 25% respectively?

Consider the following statements #define hypotenuse (a, b) sqrt (a*a+b*b); The macro call hypotenuse(a+2,b+3);

If a node has children in B tree, then the node contains exactly _____ keys.

Consider a binary tree T that has 200 leaf nodes. Then, the number of nodes in T that have exactly two children are ________.

Consider the following code fragment void foo(int x, int y) { x+=y; y+=x; } main() { int x=5.5; foo(x,x); } What is the final value of x in both call by value and call by reference, respectively?

Consider the following pseudo code, where x and y are positive integers. begin q := 0 r := x while r >= y do begin r := r - y q := q + 1 end end The post condition that needs to be satisfied after the

Given a hash table T with 25 slots that stores 2000 elements, the load factor for T is ____________.

Consider the following array of elements. (89,19,50,17,12,15,2,5,7,11,6,9,100) The minimum number of interchanges needed to convert it into a max-heap is

The result evaluating the postfix expression 10 5 + 60 6 / * 8 - is

Consider the following function written in the C programming language. void foo(char *a){ if ( *a && *a != ' '){ foo(a+1); putchar(*a); } } The output of the above function on input is

Consider the following program fragment i=6720; j=4; while (i%j)==0 { i=i/j; j=j+1; } On termination j will have the value

Which one of the following hash functions on integers will distribute keys most uniformly over 10 buckets numbered 0 to 9 for i ranging from 0 to 2020?

Consider the following C program segment. #include int main() { char s1[7] = "1234", *p; p = s1 + 2; *p = '0'; printf("%s", s1); } What will be printed by the program?

A binary tree T has 20 leaves. The number of nodes in T having two children is _______.

A hash table with ten buckets with one slot per bucket is shown in the following figure. The symbols S1 to S7 initially entered using a hashing function with linear probing. The maximum number of comp

The height of a tree is the length of the longest root-to-leaf path in it. The maximum and minimum number of nodes in a binary tree of height 5 are

Consider a complete binary tree where the left and the right subtrees of the root are max-heaps. The lower bound for the number of operations to convert the tree to a heap is

Consider the following declaration: int a, *b=&a, **c=&b; The following program fragment a=4; **c=5;

What are the worst-case complexities of insertion and deletion of a key in a binary search tree?

The queue data structure is to be realized by using stack. The number of stacks needed would be

Consider the C program below. #include int *A, stkTop; int stkFunc(int opcode, int val) { static int size=0, stkTop=0; switch (opcode) { case -1: size = val; break; case 0: if (stkTop < size) A[stkTop

The for loop for (i=0; i<10; ++i) printf("%d", i&1); prints

An algorithm performs find operations, insert operations, delete operations, and decrease-key operations on a set of data items with keys drawn from a linearly ordered set. For a delete operation, a p

Consider the following recursive C function. void get(int n) { if (n<1) return; get(n-1); get(n-3); printf("%d", n); } If get(6) function is being called in main()then how many times will the get()fun

The output of the following program is main() { static int x[] = {1,2,3,4,5,6,7,8} int i; for (i=2; i<6; ++i) x[x[i]]=x[i]; for (i=0; i<8; ++i) printf("%d", x[i]); }

Consider the following C program. #include int main( ) { static int a[ ] = {10, 20, 30, 40, 50}; static int *p[ ] = {a, a+3, a+4, a+1, a+2}; int **ptr = p; ptr++; printf("%d%d", ptr-p,**ptr); } The ou

If the sequence of operations - push (1), push (2), pop, push (1), push (2), pop, pop, pop, push (2), pop are performed on a stack, the sequence of popped out values

Consider the following C program: #include int main( ) { int i, j, k = 0; j = 2 * 3 / 4 + 2.0 / 5 + 8 / 5; k -= --j; for(i = 0; i < 5; i++) { switch(i + k) { case 1: case 2: printf(" %d", i+k); case 3

Consider the following two C code segments. Y and X are one and two dimensional arrays of size n and nxn respectively, where . Assume that in both code segments, elements of Y are initialized to 0 and

The following program main() { inc(); inc(); inc(); } inc() { static int x; printf("%d", ++x); }

Consider the following program fragment if(a > b) if(b > c) s1; else s2; s2 will be executed if

Suppose c=(c[0],...,c[k-1]) is an array of length k, where all the entries are from the set {0,1}. For any positive integers a and n, consider the following pseudocode. If k=4, c=(1,0,1,1), a=2 and n=

If n has 3, then the statement a[++n]=n++;

Consider a max heap, represented by the array: 40, 30, 20, 10, 15, 16, 17, 8, 4. Now consider that a value 35 is inserted into this heap. After insertion, the new heap is

While inserting the elements 71, 65, 84, 69, 67, 83 in an empty binary search tree (BST) in the sequence shown, the element in the lowest level is

With reference to the B+ tree index of order 1 shown below, the minimum number of nodes (including the Root node) that must be fetched in order to satisfy the following query: "Get all records with a

What is the output of the following C code? Assume that the address of x is 2000 (in decimal) and an integer requires four bytes of memory. int main () { unsigned int x[4][3] ={{1,2,3},{4,5,6},{7,8,9}

An unordered list contains n distinct elements. The number of comparisons to find an element in this list that is neither maximum nor minimum is

Consider the following C program. #include int f1(void); int f2(void); int f3(void); int x = 10; int main( ) { int x = 1; x += f1( ) + f2( ) + f3( ) + f2( ); printf("%d", x); return 0; } int f1() { in

The output of the following C program is__________. void f1(int a, int b) { int c; c=a; a=b; b=c; } void f2(int *a, int *b) { int c; c=*a; *a=*b; *b=c; } int main(){ int a=4, b=5, c=6; f1(a,b); f2(&b,

Consider the following C function. int fun(int n){ int x=1,k; if (n==1) return x; for (k=1; k < n; ++k) x = x + fun(k) * fun(n-k); return x; } The return value of fun(5) is ________.

Which of the following is/are correct inorder traversal sequence(s) of binary search tree(s)? I. 3, 5, 7, 8, 15, 19, 25 II. 5, 8, 9, 12, 10, 15, 25 III. 2, 7, 10, 8, 14, 16, 20 IV. 4, 6, 7, 9 18, 20,

Consider the following statements. I. The complement of every Turing decidable language is Turing decidable II. There exists some language which is in NP but is not Turing decidable III. If L is a lan

The number of states in the minimal deterministic finite automaton corresponding to the regular expression (0+1)*(10) is __________.

Consider the DFAs M and N given above. The number of states in a minimal DFA that accepts the language L(M) L(N) is___________

Consider the alphabet ={0, 1}, the null/empty string and the sets of strings generated by the corresponding non-terminals of a regular grammar. are related as follows. Which one of the following choic

Consider the NPDA , where (as per usual convention) Q is the set of states, is the input alphabet, is the stack alphabet, is the state transition function, is the initial state, is the initial stack s

Let L be the language represented by the regular expression where ={0,1}. What is the minimum number of states in a DFA that recognizes (complement of L)?

For any two languages L1 and L2 such that L1 is context-free and L2 is recursively enumerable but not recursive, which of the following is/are necessarily true? I. (complement of L1) is recursive II.

Which of the following languages is/are regular? is the reverse of string w

Which of the following languages are context-free?

Let and be regular sets defined over the alphabet, then