GATE CSE 2007 PYQ

Exponentiation is a heavily used operation in public key cryptography. Which of the following options is the tightest upper bound on the number of multiplications required to compute ?

Suppose the letters a, b, c, d, e, f have probabilities 1/2, 1/4, 1/8, 1/16, 1/32, 1/32 respectively. What is the average length of the Huffman code for the letters a,b,c,d,e,f?

What is the Asymptotic Notation of the following recursive function: int DoSomething (int n) { if (n <= 2) return 1; else return (DoSomething (floor(sqrt(n))) + n); }

Suppose the letters a, b, c, d, e, f have probabilities 1/2, 1/4, 1/8, 1/16, 1/32, 1/32 respectively. Which of the following is the Huffman code for the letter a, b, c, d, e, f?

In the following C function, let n m. int gcd(n,m) { if (n%m ==0) return m; n = n%m; return gcd(m,n); } How many recursive calls are made by this function?

Consider a job scheduling problem with 4 jobs and with corresponding deadlines: . Which of the following is not a feasible schedule without violating any job schedule?

In an unweighted, undirected connected graph, the shortest path from a node S to every other node is computed most efficiently, in terms of time complexity, by

The time taken by binary search algorithm to search a key in a sorted array of n elements is

A depth-first search is performed on a directed acyclic graph. Let d[u] denote the time at which vertex u is visited for the first time and f[u] the time at which the DFS call to the vertex u terminat

Consider a weighted, undirected graph with positive edge weights and let be an edge in the graph. It is known that the shortest path from the source vertex to has weight 53 and the shortest path from

Which of the following sorting algorithms has the lowest worst-case complexity?

What is the largest integer m such that every simple connected graph with n vertices and n edges contains at least m different spanning trees ?

Let w be the minimum weight among all edge weights in an undirected connected graph. Let e be a specific edge of weight w . Which of the following is FALSE?

Selection sort algorithm design technique is an example of

Consider n jobs such that job has execution time and a non-negative integer weight . The weighted mean completion time of the jobs is defined to be , where is the completion time of job . Assuming tha

Consider the following C code segment: int IsPrime(n) { int i,n; for(i=2;i<=sqrt(n);i++) if(n%i == 0) {printf("Not Primen"); return 0;} return 1; } Let T(n)denote the number of times the for loop is e

Suppose that a robot is placed on the Cartesian plane. At each step it is allowed to move either one unit up or one unit right, i.e., if it is at (i,j) then it can move to either (i+1,j) or (i,j+1). S

Suppose that a robot is placed on the Cartesian plane. At each step it is allowed to move either one unit up or one unit right, i.e., if it is at (i,j) then it can move to either (i+1,j) or (i,j+1). H

Djikstra's algorithm is used to

Consider the DAG with V = {1,2,3,4,5,6}, shown below. Which of the following is NOT a topological ordering?

The average case and worst case complexities for Merge sort algorithm are

Early binding refers to a binding performed at compile time and late binding refers to a binding performed at execution time. Consider the following statements: i. Static scope facilitates w1 bindings

Consider the CFG with {S, A,B} as the non-terminal alphabet, {a,b} as the terminal alphabet, S as the start symbol and the following set of production rules: S aB S bA B b A a B bS A aS B aBB S bAA Wh

Consider the grammar given below: Consider the following strings. i. xxyyx ii. xxyyxy iii. xyxy iv. yxxy v. yxx vi. xyx Which of the above strings are generated by the grammar ?

Consider the following grammars. Names representing terminals have been specified in capital letters. G1 G2 + * Which one of the following statements is true?

Consider the grammar with non-terminals N={ }, terminals T={a,b,i,t,e}, with S as the start symbol, and the following set of rules: The grammar is NOT LL(1) because:

Consider an ambiguous grammar G and its disambiguated version D. Let the language recognized by the two grammars be denoted by L(G) and L(D) respectively. Which one of the following is true?

In a simplified computer the instructions are: The computer has only two registers, and OP is either ADD or SUB. Consider the following basic block: Assume that all operands are initially in memory. T

Consider the CFG with {S, A,B} as the non-terminal alphabet, {a,b} as the terminal alphabet, S as the start symbol and the following set of production rules: S aB S bA B b A a B bS A aS B aBB S bAA Fo

The distance between two stations M and N is L kilometers. All frames are K bits long. The propagation delay per kilometer is t seconds. Let R bits/second be the channel capacity. Assuming that proces

IEEE 802.11 is standard for

For the network given in the figure below, the routing tables of the four nodes A, E, D and G are shown. Suppose that F has estimated its delay to its neighbors, A, E, D and G as 8, 10, 12 and 6 msecs

In Ethernet when Manchester encoding is used, the bit rate is:

A group of 15 routers is interconnected in a centralized complete binary tree with a router at each tree node. Router i communicates with router j by sending a message to the root of the tree. The roo

There are n stations in a slotted LAN. Each station attempts to transmit with a probability p in each time slot. What is the probability that ONLY one station transmits in a given time slot?

Consider a token ring topology with N stations (numbered 1 to N) running token ring protocol where the stations are equally spaced. When a station gets the token it is allowed to send one frame of fix

An Ethernet hub

An error correcting code has the following code words: 00000000, 00001111, 01010101, 10101010, 11110000. What is the maximum number of bit errors that can be corrected?

Consider a TCP connection in a state where there are no outstanding ACKs. The sender sends two segments back to back. The sequence numbers of the first and second segments are 230 and 290 respectively

Consider the following statements about the timeout value used in TCP. i.The timeout value is set to the RTT (Round Trip Time) measured during TCP connection establishment for the entire duration of t

The standard for certificates used on internet is

When a host on network A sends a message to a host on network B, which address does the router look at?

Which one of the following uses UDP as the transport protocol?

By using an eight bit optical encoder the degree of resolution that can be obtained is (approximately)

Phase transition for each bit are used in

The minimum positive integer p such that is

The message 11001001 is to be transmitted using the CRC polynomial +1 to protect it from errors. The message that should be transmitted is:

Which of these is not a feature of WAP 2.0

Hashed message is signed by a sender using his

You are given the following four bytes : Which of the following are substrings of the base 64 encoding of the above four bytes?

Match the following: (P) SMTP (1) Application layer (Q) BGP (2) Transport layer (R) TCP (3) Data link layer (S) PPP (4) Network layer (5) Physical layer

Consider a token ring topology with N stations (numbered 1 to N) running token ring protocol where the stations are equally spaced. When a station gets the token it is allowed to send one frame of fix

If there are five routers and six networks in intranet using link state routing, how many routing tables are there?

If the bandwidth of a signal is 5 kHz and the lowest frequency is 52 kHz, what is the highest frequency

Consider the following two statements: i.A hash function (these are often used for computing digital signatures) is an injective function. ii.A. encryption technique such as DES performs a permutation

SSL is not responsible for

Range of IP Address from 224.0.0.0 to 239.255.255.255 are

In a token ring network the transmission speed is bps and the propagation speed is 200 metres/ . The 1-bit delay in this network is equivalent to:

Let us consider a statistical time division multiplexing of packets. The number of sources is 10. In a time unit, a source transmits a packet of 1000 bits. The number of sources sending data for the f

A firewall is to be configured to allow hosts in a private network to freely open TCP connections and send packets on open connections. However, it will only allow external hosts to send packets on ex

In the waveform (a) given below, a bit stream is encoded by Manchester encoding scheme. The same bit stream is encoded in a different coding scheme in wave form (b). The bit stream and the coding sche

A broadcast channel has 10 nodes and total capacity of 10 Mbps. It uses polling for medium access. Once a node finishes transmission, there is a polling delay of 80 to poll the next node. Whenever a n

Silly Window Syndrome is related to

Assume that each character code consists of 8 bits. The number of characters that can be transmitted per second through a synchronous serial line at 2400 baud rate, and with two stop bits is

Consider a machine with a byte addressable main memory of bytes. Assume that a direct mapped data cache consisting of 32 lines of 64 bytes each is used in the system. A 50 x 50 two-dimensional array o

The floating point unit of a processor using a design D takes 2t cycles compared to t cycles taken by the fixed point unit. There are two more design suggestions and . uses 30% more cycles for fixed p

In comparison with static RAM memory, the dynamic Ram memory has

Consider the following program segment. Here R1, R2 and R3 are the general purpose registers. Assume that the content of memory location 3000 is 10 and the content of the register R3 is 2000. The cont

Consider a Direct Mapped Cache with 8 cache blocks (numbered 0-7). If the memory block requests are in the following order 3, 5, 2, 8, 0, 63, 9,16, 20, 17, 25, 18, 30, 24, 2, 63, 5, 82,17, 24. Which o

Following table indicates the latencies of operations between the instruction producing the result and instruction using the result. Consider the following code segment: Load R1, Loc 1; Load R1 from m

In the Big-Endian system, the computer stores

A read bit can be read

Consider a machine with a byte addressable main memory of bytes. Assume that a direct mapped data cache consisting of 32 lines of 64 bytes each is used in the system. A 50 x 50 two-dimensional array o

A processor takes 12 cycles to complete an instruction . The corresponding pipelined processor uses 6 stages with the execution times of 3, 2, 5, 4, 6 and 2 cycles respectively. What is the asymptotic

Consider the following program segment. Here R1, R2 and R3 are the general purpose registers. Assume that the content of memory location 3000 is 10 and the content of the register R3 is 2000. The cont

Consider a disk pack with 16 surfaces, 128 tracks per surface and 256 sectors per track. 512 bytes of data are stored in a bit serial manner in a sector. The capacity of the disk pack and the number o

Consider a 4-way set associative cache consisting of 128 lines with a line size of 64 words. The CPU generates a 20-bit address of a word in main memory. The number of bits in the TAG, LINE and WORD f

Consider the following program segment. Here R1, R2 and R3 are the general purpose registers. Assume that the content of memory location 3000 is 10 and the content of the register R3 is 2000. The cont

The principal of the locality of reference justifies the use of

Consider a small 2-way set-associative cache memory, consisting of four blocks. For choosing the block to be replaced, use the least recently (LRU) scheme. The number of cache misses for the following

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

Which of the following RAID level provides the highest Data Transfer Rate (Read/Write)

Consider a pipelined processor with the following four stages: IF: Instruction Fetch ID: Instruction Decode and Operand Fetch EX: Execute WB: Write Back The IF, ID and WB stages take one clock cycle e

Data forwarding techniques can be used to speed up the operation in presence of data dependencies. Consider the following replacements of LHS with RHS. i. ii. iii. iv. In which of the following option

Which operation is used to extract specified columns from a table?

Consider the relation employee(name, sex, supervisorName) with name as the key. supervisorName gives the name of the supervisor of the employee under consideration. What does the following Tuple Relat

Which of the following is correct with respect to Two phase commit protocol?

Consider the following two transactions : T1 and T2. T1:read (A); read (B); if A = 0 then B B + 1; write (B); T2 : read (B); read (A); if B 0 then A A - 1; write (A); Which of the following schemes, u

Which of the following is aggregate function in SQL?

Consider the table employee(empId, name, department, salary) and the two queries Q1 ,Q2 below. Assuming that department 5 has more than one employee, and we want to find the employees who get higher s

Consider the following implications relating to functional and multivalued dependencies given below, which may or may not be correct. i. if and then ii. if and then iii. if and then iv. if and then Ex

What is the result of the following SQL query if the table contains only one tuple with ? [equation]

Which one of the following statements if FALSE?

Consider a selection of the form , where r is a relation with 1000 tuples. Assume that the attribute values for A among the tuples are uniformly distributed in the interval [0, 500]. Which one of the

BCNF is not used for cases where a relation has

Armstrong's inference rule doesnot determine

Which commands are used to control access over objects in relational database?

Information about a collection of students is given by the relation studinfo( , name, sex). The relation enroll(studId, courseId) gives which student has enrolled for (or taken) what course(s). Assume

Consider the following schedules involving two transactions. Which one of the following statements is TRUE?

Consider the following relation schemas : b-Schema = (b-name, b-city, assets) a-Schema = (a-num, b-name, bal) d-Schema = (c-name, a-number) Let branch, account and depositor be respectively instances

Which of the following is TRUE about formulae in Conjunctive Normal Form?

The order of a leaf node in a B+ 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 fie

The following expression was to be realized using 2-input AND and OR gates. However, during the fabrication all 2-input AND gates were mistakenly substituted by 2-input NAND gates. What is the functio

The line T in the following figure is permanently connected to the ground. Which of the following inputs will detect the fault ?

In a look-ahead carry generator, the carry generate function i G and the carry propagate function for inputs and are given by: The expressions for the sum bit and the carry bit of the look-ahead carry

Consider the following expression Which of the following Karnaugh Maps correctly represents the expression?

Consider the following Boolean function of four variables: f (w, x, y, z)= (1,3,4,6,9,11,12,14) The function is:

Consider the following expression Which of the following expressions does not correspond to the Karnaugh Map obtained for the given expression?

Define the connective * for the Boolean variables X and Y as: X * Y = XY + X'Y'. Let Z= X *Y. Consider the following expressions P, Q and R. P : X = Y * Z Q :Y = X * Z R : X *Y * Z = 1 Which of the fo

In an SR latch made by cross-coupling two NAND gates, if both S and R inputs are set to 0, then it will result in

The circuit shown in the given figure is a

0.75 decimal system is equivalent to ____ in octal system

The characteristic equation of an SR flip-flop is given by :

Which of the following input sequences for a cross-coupled R-S flip-flop realized with two NAND gates may lead to an oscillation?

When two numbers are added in excess-3 code and the sum is less than 9, then in order to get the correct answer it is necessary to

The number of digit 1 present in the binary representation of is

The Boolean expression is given by

Suppose only one multiplexer and one inverter are allowed to be used to implement any Boolean function of n variables. What is the minimum size of the multiplexer needed?

The control signal functions of a 4-bit binary counter are given below (where X is "don't care"): Assume that the counter and gate delays are negligible. If the counter starts at 0, then it cycles thr

What is the maximum number of different Boolean functions involving n Boolean variables?

What is the final value stored in the linear feedback shift register if the input is 101101?

How many 3-to-8 line decoders with an enable input are needed to construct a 6- to-64 line decoder without using any other logic gates?

The circuit shown in the following figure realizes the function.

The following circuit implements a two-input AND gate using two 2-1 multiplexers. What are the values of ?

The output 0 and 1 level for TTL Logic family is approximately

Consider a computer system that stores a floating-point numbers with 16-bit mantissa and an 8-bit exponent, each in two's complement. The smallest and largest positive values which can be stored are :

One approach to handling fuzzy logic data might be to design a computer using ternary (base-3) logic so that data could be stored as "true," "false," and "unknown." If each ternary logic element is ca

Let f(w,x,y,z)= (0,4,5,7,8,9,13,15). Which of the following expressions are NOT equivalent to f ? (P) x'y'z' + w'xy' + wy'z + xz (Q) w'y'z' + wx'y' + xz (R) w'y'z' + wx'y' + xyz + xy'z (S) x'y'z' + wx

Ring counter is analogous to

The Hexadecimal equivalent of 01111100110111100011 is

A graph with n vertices and n-1 edges that is not a tree, is

Suppose there are two coins. The first coin gives heads with probability when tossed, while the second coin gives heads with probability . One of the two coins is picked up at random with equal probab

Consider the sequence defined by the recurrence relation , where c > 0. For which of the following values of c, does there exist a non-empty open interval (a, b) such that the sequence converges for a

Company X shipped 5 computer chips, 1 of which was defective. and company Y shipped 4 computer chips, 2 of which were defective. One computer chip is to be chosen uniformly at a random from the 9 chip

Eigen vectors of are

A depth-first search is performed on a directed acyclic graph. Let d[u] denote the time at which vertex u is visited for the first time and f[u] the time at which the DFS call to the vertex u terminat

Which one of these first-order logic formulae is valid?

A program consists of two modules executed sequentially. Let and respectively denote the probability density functions of time taken to execute the two modules. The probability density function of the

A partial order P is defined on the set of natural numbers as follows. Here denotes integer division. i. ii. if and only if and . Consider the following ordered pairs: i. (101, 22) ii. (22, 101) iii.

Which of the following graphs has an Eulerian circuit?

Consider the set of (column) vectors defined by Which of the following is TRUE?

Consider the DAG with V = {1,2,3,4,5,6}, shown below. Which of the following is NOT a topological ordering?

Which of the following is TRUE?

The set of all Equivalence Classes of a set A of Cardinality C

Let A be the matrix . What is the maximum value of where the maximum is taken over all x that are the unit eigenvectors of A?

Let G be the non-planar graph with the minimum possible number of edges. Then G has

The trapezoidal method is used to evaluate the numerical value of . Consider the following values for the step size h. i. ii. iii. iv. For which of these values of the step size h, is the computed val

Identify the correct translation into logical notation of the following assertion. Some boys in the class are taller than all the girls Note: taller (x, y) is true if x is taller than y.

Suppose we uniformly and randomly select a permutation from the 20! Permutations of 1, 2,3 ,...,20. What is the probability that 2 appears at an earlier position than any other even number in the sele

If a graph requires k different colours for its proper colouring, then the chromatic number of the graph is

Let Graph(x) be a predicate which denotes that x is a graph. Let Connected(x) be a predicate which denotes that x is connected. Which of the following first order logic sentences DOES NOT represent th

Consider the sequence defined by the recurrence relation , where c > 0. Suppose there exists a non-empty, open interval (a, b) such that for all satisfying , the sequence converges to a limit. The seq

Let A be a 4 x 4 matrix with eigenvalues -5, -2, 1, 4. Which of the following is an eigenvalue of where I is the 4 x 4 identity matrix?

In a multi-user operating system on an average, 20 requests are made to use a particular resource per hour. The arrival of requests follows a Poisson distribution. The probability that either one, thr

Consider the series obtained from the Newton-Raphson method. The series converges to

How many different non-isomorphic Abelian groups of order 4 are there?

Let X be the adjacency matrix of a graph G with no self loops. The entries along the principal diagonal of X are

Let S be a set of n elements. The number of ordered pairs in the largest and the smallest equivalence relations on S are:

Consider the following two statements about the function f(x)=|x|: P. f(x) is continuous for all real values of x Q. f(x) is differentiable for all real values of x Which of the following is TRUE?

What is the name of the technique in which the operating system of a computer executes several programs concurrently by switching back and forth between them?

Group 1 contains some CPU scheduling algorithms and Group 2 contains some applications. Match entries in Group 1 to entries in Group 2. Group I Group II

The head of a hard disk serves requests following the shortest seek time first (SSTF) policy. The head is initially positioned at track number 180. Which of the request sets will cause the head to cha

The address sequence generated by tracing a particular program executing in a pure demand paging system with 100 bytes per page is Suppose that the memory can store only one page and if x is the addre

An operating system uses Shortest Remaining Time first (SRT) process scheduling algorithm. Consider the arrival times and execution times for the following processes: Process Execution time Arrival ti

Synchronization in the classical readers and writers problem can be achieved through use of semaphores. In the following incomplete code for readers-writers problem, two binary semaphores mutex and wr

A process has been allocated 3 page frames. Assume that none of the pages of the process are available in the memory initially. The process makes the following sequence of page references (reference s

Two processes, P1 and P2, need to access a critical section of code. Consider the following synchronization construct used by the processes: Here, wants1 and wants2 are shared variables, which are ini

A process has been allocated 3 page frames. Assume that none of the pages of the process are available in the memory initially. The process makes the following sequence of page references (reference s

Consider a set of n tasks with known runtimes to be run on a uniprocessor machine. Which of the following processor scheduling algorithms will result in the maximum throughput?

Consider a system having 'm' resources of the same type. The resources are shared by 3 processes A, B, C, which have peak time demands of 3, 4, 6 respectively. The minimum value of 'm' that ensures th

Consider the following statements about user level threads and kernel level threads. Which one of the following statements is FALSE?

A virtual memory system uses First In First Out (FIFO) page replacement policy and allocates a fixed number of frames to a process. Consider the following statements: P: Increasing the number of page

The head of a hard disk serves requests following the shortest seek time first (SSTF) policy. What is the maximum cardinality of the request set, so that the head changes its direction after servicing

The contents of the text file t1 txt containing four lines are as follows : a1 b1 a2 b2 a3 b2 a4 b1 The contents of the text file t2 txt containing five lines are as follows : a1 c1 a2 c2 a3 c3 a4 c3

Disk requests are received by a disk drive for cylinder 5, 25, 18, 3, 39, 8 and 35 in that order. A seek takes 5 msec per cylinder moved. How much seek time is needed to serve these requests for a Sho

A task in a blocked state

A demand paging system takes 100 time units to service a page fault and 300 time units to replace a dirty page. Memory access time is 1 time unit. The probability of a page fault is p. In case of a pa

Round Robin schedule is essentially the pre-emptive version of

On a system using non-preemptive scheduling, processes with expected run times of 5, 18, 9 and 12 are in the ready queue. In what order should they be run to minimize wait time?

A single processor system has three resource types X, Y and Z, which are shared by three processes. There are 5 units of each resource type. Consider the following scenario, where the column alloc den

Let a memory have four free blocks of sizes 4k, 8k, 20k, 2k. These blocks are allocated following the best-fit strategy. The allocation requests are stored in a queue as shown below. The time at which

Processes P1 and P2 use critical_flag in the following routine to achieve mutual exclusion. Assume that critical_flag is initialized to FALSE in the main program. get_exclusive_access ( ) { if (critic

Semaphores

The term 'aging' refers to

Virtual memory is

The minimum number of page frames that must be allocated to a running process in a virtual memory environment is determined by

Consider the program below in a hypothetical language which allows global variable and a choice of call by reference or call by value methods of parameter passing. int i ; program main () { int j = 60

Consider a hash table of size seven, with starting index zero, and a hash function (3x + 4)mod7. Assuming the hash table is initially empty, which of the following is the contents of the table when th

Consider the C program given below : #include int main () { int sum = 0, maxsum = 0, i, n = 6; int a [] = {2, -2, -1, 3, 4, 2}; for (i = 0; i maxsum) maxsum = sum; sum = (a [i] > 0) ? a [i] : 0; } els

Consider the tree in the adjoining figure, where each node has at most two keys and three links. Keys K15 and then K25 are inserted into this tree in that order. Exactly how many of the following node

Study the following program //precondition: x>=0 public void demo(int x) { System.out.print(x % 10); if (x % 10 != 0) { demo(x/10); } System.out.print(x%10); } Which of the following is printed as a r

Consider the program below in a hypothetical programming language which allows global variables and a choice of static or dynamic scoping. int i ; program main () { i = 10; call f(); } procedure f() {

When searching for the key value 60 in a binary search tree, nodes containing the key values 10, 20, 40, 50, 70, 80, 90 are traversed, not necessarily in the order given. How many different orders are

The maximum number of binary trees that can be formed with three unlabeled nodes is:

Consider a hash function that distributes keys uniformly. The hash table size is 20. After hashing of how many keys will the probability that any new key hashed collides with an existing one exceed 0.

The function f is defined as follows: int f (int n) { if (n <= 1) return 1; else if (n % 2 == 0) return f(n/2); else return f(3n - 1); } Assuming that arbitrarily large integers can be passed as a par

Consider the following segment of C-code: int j, n; j = 1; while (j <=n) j=j*2; The number of comparisons made in the execution of the loop for any is:

An array of n numbers is given, where n is an even number. The maximum as well as the minimum of these n numbers needs to be determined. Which of the following is TRUE about the number of comparisons

The height of a binary tree is the maximum number of edges in any root to leaf path. The maximum number of nodes in a binary tree of height h is:

Consider the tree in the adjoining figure, where each node has at most two keys and three links. Keys K15 and then K25 are inserted into this tree in that order. Now the key K50 is deleted from the tr

Consider the following pseudo-code x:=1; i:=1; while (x <= 1000) begin x:=2^x; i:=i+1; end; What is the value of i at the end of the pseudo-code?

The following postfix expression with single digit operands is evaluated using a stack: 8 2 3 ^ / 2 3 * + 5 1 * - Note that ^ is the exponentiation operator. The top two elements of the stack after th

Consider the following C program segment where CellNode represents a node in a binary tree: struct CellNode { struct CellNOde *leftChild; int element; struct CellNode *rightChild; }; int GetValue(stru

Consider the process of inserting an element into a Max Heap, where the Max Heap is represented by an array. Suppose we perform a binary search on the path from the new leaf to the root to find the po

Consider the following C function: #include int f(int n) { static int r = 0; if (n 3) { r = n; return f(n-2)+2; } return f(n-1)+r; } int main() { printf("%d", f(5)); } What is the value of f(5)?

Consider the following C program: #include #define EOF -1 void push (int); /* push the argument on the stack */ int pop (void); /* pop the top of the stack */ void flagError (); int main () { int c, m

The five items: A, B, C, D, and E are pushed in a stack, one after other starting from A. The stack is popped four items and each element is inserted in a queue. The two elements are deleted from the

Suppose you are given an implementation of a queue of integers. The operations that can be performed on the queue are: i. isEmpty(Q) returns true if the queue is empty, false otherwise. ii. delete(Q)

The inorder and preorder traversal of a binary tree are d b e a f c g and a b d e c f g, respectively The postorder traversal of the binary tree is:

Consider the regular expression Which one of the regular expressions given below defines the same language as defined by the regular expression R ?

Consider the following finite automata P and Q over the alphabet {a, b, c}. The start states are indicated by a double arrow and final states are indicated by a double circle. Let the languages recogn

The two grammars given below generate a language over the alphabet G1 : G2 : Which one of the following choices describes the properties satisfied by the strings in these languages?

The language over the alphabet {0,1,2} is:

Which of the following languages is regular?

Consider the following Finite State Automaton: The language accepted by this automaton is given by the regular expression

A minimum state deterministic finite automaton accepting the language L={w|w {0,1}*} , number of 0s and 1s in w are divisible by 3 and 5, respectively has

Consider the following Finite State Automaton: The minimum state automaton equivalent to the above FSA has the following number of states

Consider the regular expression Which of the following non-deterministic finite automata recognizes the language defined by the regular expression R? Edges labeled denote transitions on the empty stri

Consider the following two statements: P: Every regular grammar is LL(1) Q: Every regular set has a LR(1) grammar Which of the following is TRUE?

Consider the following DFA in which is the start state and , are the final states What language does this DFA recognize?

Which of the following problems is undecidable?

Consider the regular expression Which deterministic finite automaton accepts the language represented by the regular expression R?