Computer Science Engineering (CSE)
Which of the following statements is true?- a)If a language is context free it can always be accepted by a deterministic push-down automaton
- b)The union of two context free languages is context free
- c)The intersection of two contest free languages is a context free
- d)The complement of a context free language is a context free
Correct answer is option 'B'. Can you explain this answer?
Which of the following statements is true?
a)
If a language is context free it can always be accepted by a deterministic push-down automaton
b)
The union of two context free languages is context free
c)
The intersection of two contest free languages is a context free
d)
The complement of a context free language is a context free
Hardik Mittal answered • 1 hour ago(A) is wrong as a language can be context free even if it is being accepted by non deterministic 
reverse}
(C) and (D) not always true as Context free languages are not closed under Complement and Intersection.
On a disk with 1000 cylinders, numbers 0 to 999, compute the number of tracks the disk arm must move to satisfy all the requests in the disk queue. Assume the last request serviced was at tracks 345 and the head is moving towards track 0. The queue in FIFO order contains requests for the following tracks. 123, 874, 692, 475, 105, 376. Perform the computation using C-SCAN scheduling algorithm. What is the total distance?- a)1219
- b)1009
- c)1967
- d)1507
Correct answer is option 'C'. Can you explain this answer?
On a disk with 1000 cylinders, numbers 0 to 999, compute the number of tracks the disk arm must move to satisfy all the requests in the disk queue. Assume the last request serviced was at tracks 345 and the head is moving towards track 0. The queue in FIFO order contains requests for the following tracks. 123, 874, 692, 475, 105, 376. Perform the computation using C-SCAN scheduling algorithm. What is the total distance?
a)
1219
b)
1009
c)
1967
d)
1507
Vikram Bansal answered • 1 hour ago
∴ Total distance covered by the head
= (345 -123) + (123 -105) + (105 - 0) + (999 - 0)
+ (999-874) + (874-692) + (692-475) + (475 -376)
= 222 + 18 + 105 + 999 + 125 + 182 + 217 + 99
= 1967
DIVIJ NAGPAL asked • 6 minutes agoLet Nf and Np denote the classes of languages accepted by non-deterministic finite automata and non-deterministic push-down automata, respectively. Let Df and Dp denote the classes of languages accepted by deterministic finite automata and deterministic push-down automata, respectively. Which one of the following is TRUE?- a)Df ⊂ Nf and Dp ⊂ Np
- b)Df ⊂ Nf and Dp = Np
- c)Df = Nf and Dp = Np
- d)Df = Nf and Dp ⊂ Np
Correct answer is option 'D'. Can you explain this answer?
Let Nf and Np denote the classes of languages accepted by non-deterministic finite automata and non-deterministic push-down automata, respectively. Let Df and Dp denote the classes of languages accepted by deterministic finite automata and deterministic push-down automata, respectively. Which one of the following is TRUE?
a)
Df ⊂ Nf and Dp ⊂ Np
b)
Df ⊂ Nf and Dp = Np
c)
Df = Nf and Dp = Np
d)
Df = Nf and Dp ⊂ Np
The chip select logic for a certain DRAM chip in a memory- system design is shown below Assume that the memory system has 16 address lines denoted by A15 to A0. What is the range of addresses (in hexadecimal) of the memory system that can get enabled by the chip select (CS) signal?
- a)C800 to CFFF
- b)C800 to C8FF
- c)DA00 to DFFF
- d)CA00 to CAFF
Correct answer is option 'A'. Can you explain this answer?
The chip select logic for a certain DRAM chip in a memory- system design is shown below Assume that the memory system has 16 address lines denoted by A15 to A0. What is the range of addresses (in hexadecimal) of the memory system that can get enabled by the chip select (CS) signal?
a)
C800 to CFFF
b)
C800 to C8FF
c)
DA00 to DFFF
d)
CA00 to CAFF
Saurabh Verma answered • 14 hours agoChip select signal will be enable only of
And rest of the bits
Will be available from 00000000000 to 11111111111 Hence address
And rest of the bits
Will be available from 00000000000 to 11111111111 Hence address
DIKSHA KUMARI asked • 1 hour agoConsider the following experiment.
Step 1. Flip a fair coin twice.
Step 2. If the outcomes are (TAILS, HEADS) then output Y and stop.
Step 3. If the outcomes are either (HEADS, HEADS) or (HEADS, TAILS), then output N and stop.
Step 4. If the outcomes are (TAILS, TAILS), then go to Step 1.
The probability that the output of the experiment is Y is (up to two decimal places) ____________.
Correct answer is '0.33'. Can you explain this answer?
Consider the following experiment.
Step 1. Flip a fair coin twice.
Step 2. If the outcomes are (TAILS, HEADS) then output Y and stop.
Step 3. If the outcomes are either (HEADS, HEADS) or (HEADS, TAILS), then output N and stop.
Step 4. If the outcomes are (TAILS, TAILS), then go to Step 1.
The probability that the output of the experiment is Y is (up to two decimal places) ____________.
Step 1. Flip a fair coin twice.
Step 2. If the outcomes are (TAILS, HEADS) then output Y and stop.
Step 3. If the outcomes are either (HEADS, HEADS) or (HEADS, TAILS), then output N and stop.
Step 4. If the outcomes are (TAILS, TAILS), then go to Step 1.
The probability that the output of the experiment is Y is (up to two decimal places) ____________.
The minimum number of multiplications needed to evaluate p on an input x is KUMAR UTKARSH asked • 1 hour agoThe characters a to h have the set of frequencies based on the first 8 Fibonacci numbers as followsa : 1, b : 1, c : 2, d : 3, e : 5, f : 8, g : 13, h : 21A Huffman code is used to represent the characters. What is the sequence of characters corresponding to the following code? 110111100111010- a)fdheg
- b)ecgdf
- c)dchfg
- d)fehdg
Correct answer is option 'A'. Can you explain this answer?
The characters a to h have the set of frequencies based on the first 8 Fibonacci numbers as follows
a : 1, b : 1, c : 2, d : 3, e : 5, f : 8, g : 13, h : 21
A Huffman code is used to represent the characters. What is the sequence of characters corresponding to the following code? 110111100111010
a)
fdheg
b)
ecgdf
c)
dchfg
d)
fehdg
Ambati Rajendra asked • 2 hours agoHow is a privilege exception dealt with?- a)The program is alted and the system switches into supervisor mode and restarts the program execution
- b)The Program is stopped and removed from the queue
- c)The system switches the mode and starts the execution of a new process
- d)The system switches mode and runs the debugger
Correct answer is option 'A'. Can you explain this answer?
How is a privilege exception dealt with?
a)
The program is alted and the system switches into supervisor mode and restarts the program execution
b)
The Program is stopped and removed from the queue
c)
The system switches the mode and starts the execution of a new process
d)
The system switches mode and runs the debugger
SUNAINA RAJESH asked • 3 hours agoAn application loads 100 libraries at startup. Loading each library requires exactly one disk access. The seek time of the disk to a random location is given as 10ms.Rotational speed of disk is 6000rpm. If all 100 libraries are loaded from random locations on the disk, how long does it take to load all libraries? (The time to transfer data from the disk block once the head has been positioned at the start of the block may be neglected)- a)0.50s
- b)1.50s
- c)1.25s
- d)1.00s
Correct answer is option 'B'. Can you explain this answer?
An application loads 100 libraries at startup. Loading each library requires exactly one disk access. The seek time of the disk to a random location is given as 10ms.Rotational speed of disk is 6000rpm. If all 100 libraries are loaded from random locations on the disk, how long does it take to load all libraries? (The time to transfer data from the disk block once the head has been positioned at the start of the block may be neglected)
a)
0.50s
b)
1.50s
c)
1.25s
d)
1.00s
ABHINAV RANA asked • 4 hours ago Let G = (V, E) be an undirected graph with a subgraph G1 = (V1, El). Weights are assigned to edges of G as follows :
A single-source shortest path algorithm is executed on the weighted graph (V, E, w) with an arbitrary vertex ν1 of V1 as the source. Which of the following can always be inferred from the path costs computed?- a)The number of edges in the shortest paths from ν1 to all vertices of G
- b)G1 is connected
- c)V1 forms a clique in G
- d)G1 is a tree
Correct answer is option 'B'. Can you explain this answer?
Let G = (V, E) be an undirected graph with a subgraph G1 = (V1, El). Weights are assigned to edges of G as follows :
A single-source shortest path algorithm is executed on the weighted graph (V, E, w) with an arbitrary vertex ν1 of V1 as the source. Which of the following can always be inferred from the path costs computed?
a)
The number of edges in the shortest paths from ν1 to all vertices of G
b)
G1 is connected
c)
V1 forms a clique in G
d)
G1 is a tree
SAPNA DEVI asked • 4 hours agoSuppose 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?- a)0, 10, 110, 1110, 11110, 11111
- b)11, 10, 011, 010, 001, 000
- c)11, 10, 01, 001, 0001, 0000
- d)110, 100, 010, 000, 001, 111
Correct answer is option 'A'. Can you explain this answer?
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?
a)
0, 10, 110, 1110, 11110, 11111
b)
11, 10, 011, 010, 001, 000
c)
11, 10, 01, 001, 0001, 0000
d)
110, 100, 010, 000, 001, 111
Mayank Raj asked • 5 hours agoWhich of the following problems is undecidable?- a)Deciding if a given context-free grammar is ambiguous.
- b)Deciding if a given string is generated by a given context-free grammar.
- c)Deciding if the language generated by a given context-free grammar is empty.
- d)Deciding if the language generated by a given context-free grammar is finite.
Correct answer is option 'A'. Can you explain this answer?
Which of the following problems is undecidable?
a)
Deciding if a given context-free grammar is ambiguous.
b)
Deciding if a given string is generated by a given context-free grammar.
c)
Deciding if the language generated by a given context-free grammar is empty.
d)
Deciding if the language generated by a given context-free grammar is finite.
POOJA DEVI asked • 5 hours agoWhich of the following statements is false with regard to fully associative and direct mapped cache organizations?- a)Direct mapped caches do not need a cache block replacement policy, whereas fully associative caches do.
- b)In a fully associative cache, the full address is stored alongside the data block.
- c)A direct mapped cache is organized according to an 'index', and the'tag' part of the memory ‘ address is stored alongside the data block.
- d)Direct mapped caches may produce more misses if programs refer to memory words that occupy a single tag value.
Correct answer is option 'D'. Can you explain this answer?
Which of the following statements is false with regard to fully associative and direct mapped cache organizations?
a)
Direct mapped caches do not need a cache block replacement policy, whereas fully associative caches do.
b)
In a fully associative cache, the full address is stored alongside the data block.
c)
A direct mapped cache is organized according to an 'index', and the'tag' part of the memory ‘ address is stored alongside the data block.
d)
Direct mapped caches may produce more misses if programs refer to memory words that occupy a single tag value.
Rajbala asked • 6 hours agoConsider the circuit-shown below. Each of the control inputs, C0 through C3, must be tied to a constant, either ‘0’ or '1'.
What are the values of C0 through C3 that would cause F to be the exclusive OR of A and B?- a)(1 ,0, 0 ,1 )
- b)( 0 ,1 ,1 ,1 )
- c)(0, 1,1,0)
- d)(1,1, 1,1)
Correct answer is option 'C'. Can you explain this answer?
Consider the circuit-shown below. Each of the control inputs, C0 through C3, must be tied to a constant, either ‘0’ or '1'.
What are the values of C0 through C3 that would cause F to be the exclusive OR of A and B?
What are the values of C0 through C3 that would cause F to be the exclusive OR of A and B?
a)
(1 ,0, 0 ,1 )
b)
( 0 ,1 ,1 ,1 )
c)
(0, 1,1,0)
d)
(1,1, 1,1)
SUNITA KUMARI asked • 6 hours agoIf e1 and e2 are the RE denoting the languages L1 and L2 respectively, then which of the following is wrong?- a)(e1) | (e2) is a regular expression denoting
- b)(e1)(e2) is a RE denoting L1. L2
- c)φ is not a RE
- d){e1}* is a RE denoting L1*
Correct answer is option 'C'. Can you explain this answer?
If e1 and e2 are the RE denoting the languages L1 and L2 respectively, then which of the following is wrong?
a)
(e1) | (e2) is a regular expression denoting
b)
(e1)(e2) is a RE denoting L1. L2
c)
φ is not a RE
d)
{e1}* is a RE denoting L1*
NISHA KUMARI asked • 6 hours ago 6 files F1, F2, F3, F4, F5and 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 frequency.- a)F3,F4, F1.F5, F6, F2
- b)F2, F6, F5, F1.F4, F3
- c)F1,F2, F3, F4, F5, F6
- d)Ordering is immaterial as all files are accessed with the same frequency
Correct answer is option 'A'. Can you explain this answer?
6 files F1, F2, F3, F4, F5and 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 frequency.
a)
F3,F4, F1.F5, F6, F2
b)
F2, F6, F5, F1.F4, F3
c)
F1,F2, F3, F4, F5, F6
d)
Ordering is immaterial as all files are accessed with the same frequency
SUMAN DEVI asked • 6 hours agoA trigger is - a)A statement that enables to start any DBMS.
- b)A statement that is executed by the user when debugging an application program.
- c)A condition the system tests for the validity of the database user.
- d)A statement that is executed automatically by the system as a side effect of a modification to the database.
Correct answer is option 'D'. Can you explain this answer?
A trigger is
a)
A statement that enables to start any DBMS.
b)
A statement that is executed by the user when debugging an application program.
c)
A condition the system tests for the validity of the database user.
d)
A statement that is executed automatically by the system as a side effect of a modification to the database.
Ratnesh Yadav asked • 6 hours agoConsider the following :
int numreader = 0;
mutex = semaphore (1);
room empty (1);
The above code is a proposed solution of the Readers/Writer problem.
Consider which of the following statements is/are true?
1. The code allow several writers to execute in the writers critical area at the same time
2. The code allow several readers to execute in the readers critical area at the same time.- a)1 only
- b)2 only
- c)1 and 2 both
- d)None of these
Correct answer is option 'B'. Can you explain this answer?
Consider the following :
int numreader = 0;
mutex = semaphore (1);
room empty (1);
The above code is a proposed solution of the Readers/Writer problem.
Consider which of the following statements is/are true?
1. The code allow several writers to execute in the writers critical area at the same time
2. The code allow several readers to execute in the readers critical area at the same time.
int numreader = 0;
mutex = semaphore (1);
room empty (1);
The above code is a proposed solution of the Readers/Writer problem.
Consider which of the following statements is/are true?
1. The code allow several writers to execute in the writers critical area at the same time
2. The code allow several readers to execute in the readers critical area at the same time.
a)
1 only
b)
2 only
c)
1 and 2 both
d)
None of these
Sai Charan asked • 6 hours agoMatch List-I (Function) with List-lI (Layer) and select the correct answer using the codes given below the listsList-I
A. Reassembly of packets
B. Responsibility for delivery between adjacent nodes
C. Mechanical electrical and functional interface
D. Error correction and retransmissionList-II
1. Transport
2. Data link
3. Physical 
- a)a
- b)b
- c)c
- d)d
Correct answer is option 'D'. Can you explain this answer?
Match List-I (Function) with List-lI (Layer) and select the correct answer using the codes given below the lists
List-I
A. Reassembly of packets
B. Responsibility for delivery between adjacent nodes
C. Mechanical electrical and functional interface
D. Error correction and retransmission
A. Reassembly of packets
B. Responsibility for delivery between adjacent nodes
C. Mechanical electrical and functional interface
D. Error correction and retransmission
List-II
1. Transport
2. Data link
3. Physical
1. Transport
2. Data link
3. Physical
a)
a
b)
b
c)
c
d)
d
GURMEETKAUR DEVENDER asked • 6 hours agoWhich of the following actions an operator- precedence parser may take to recover from an error?- a)Insert symbols onto the stack
- b)Delete symbols from the stack
- c)Insert or delete symbols from the input
- d)All of the above
Correct answer is option 'D'. Can you explain this answer?
Which of the following actions an operator- precedence parser may take to recover from an error?
a)
Insert symbols onto the stack
b)
Delete symbols from the stack
c)
Insert or delete symbols from the input
d)
All of the above
KANCHAN VIJAY asked • 6 hours agoA pipelined processor uses a 4-stage instruction pipeline with the following stages: instruction fetch (IF), Instruction decode (ID), Execute (EX) and Write-back (WB). The arithmetic operations as well as the load and store operations are carried out in the EX stage. The sequence of instructions corresponding to the statement X = (S - R * (P+ G))/T is given below. The values of variables P, Q, R, S and T are available in the registers R0, R 1, R2, R3 and R4 respectively, before the execution of the instruction sequence.
Q. The IF, ID and WB stages take 1 clock cycle each. The EX stage takes 1 clock cycle each for the ADD, SUB and STORE operations, and 3 clock cycles each for MUL and DIV operations. Operand forwarding from the EX stage to the ID stage is used. The number of clock cycles required to complete the sequence of instructions is- a)10
- b)12
- c)14
- d)16
Correct answer is option 'B'. Can you explain this answer?
A pipelined processor uses a 4-stage instruction pipeline with the following stages: instruction fetch (IF), Instruction decode (ID), Execute (EX) and Write-back (WB). The arithmetic operations as well as the load and store operations are carried out in the EX stage. The sequence of instructions corresponding to the statement X = (S - R * (P+ G))/T is given below. The values of variables P, Q, R, S and T are available in the registers R0, R 1, R2, R3 and R4 respectively, before the execution of the instruction sequence.
Q. The IF, ID and WB stages take 1 clock cycle each. The EX stage takes 1 clock cycle each for the ADD, SUB and STORE operations, and 3 clock cycles each for MUL and DIV operations. Operand forwarding from the EX stage to the ID stage is used. The number of clock cycles required to complete the sequence of instructions is
a)
10
b)
12
c)
14
d)
16
RAJJI DEVI asked • 6 hours agoOn a non-pipelined sequential processor, a program segment, which is a part of the interrupt service routine, is given to transfer 500 bytes from an I/O device to memory.
Initialize the address registerInitialize the count to 500LOOP: Load a byte from deviceStore in memory at address given by address registerIncrement the address registerDecrement the countIf count != 0 go to LOOPAssume that each statement in this program is equivalent to a machine instruction which takes one clock cycle to execute if it is a non-load/store instruction. The load-store instructions take two clock cycles to execute.
The designer of the system also has an alternate approach of using the DMA controller to implement the same transfer. The DMA controller requires 20 clock cycles for initialization and other overheads. Each DMA transfer cycle takes two clock cycles to transfer one byte of data from the device to the memory. Q. What is the approximate speedup when the DMA controller based design is used in place of the interrupt driven program based input-output?... more
On a non-pipelined sequential processor, a program segment, which is a part of the interrupt service routine, is given to transfer 500 bytes from an I/O device to memory.
Initialize the address register
Initialize the address register
Initialize the count to 500
LOOP: Load a byte from device
Store in memory at address given by address register
Increment the address register
Decrement the count
If count != 0 go to LOOP
Assume that each statement in this program is equivalent to a machine instruction which takes one clock cycle to execute if it is a non-load/store instruction. The load-store instructions take two clock cycles to execute.
The designer of the system also has an alternate approach of using the DMA controller to implement the same transfer. The DMA controller requires 20 clock cycles for initialization and other overheads. Each DMA transfer cycle takes two clock cycles to transfer one byte of data from the device to the memory.
The designer of the system also has an alternate approach of using the DMA controller to implement the same transfer. The DMA controller requires 20 clock cycles for initialization and other overheads. Each DMA transfer cycle takes two clock cycles to transfer one byte of data from the device to the memory.
Q. What is the approximate speedup when the DMA controller based design is used in place of the interrupt driven program based input-output?
SUNAINA RAJESH asked • 6 hours agoWhat is common in three different types of traversals (Inorder, Preorder and Postorder)?- a)Root is visited before right subtree
- b)Left subtree is always visited before right subtree
- c)Root is visited after left subtree
- d)All of the above
- e)None of the above
Correct answer is option 'B'. Can you explain this answer?
What is common in three different types of traversals (Inorder, Preorder and Postorder)?
a)
Root is visited before right subtree
b)
Left subtree is always visited before right subtree
c)
Root is visited after left subtree
d)
All of the above
e)
None of the above
ADITYA NIGAM asked • 6 hours agoLet 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 ?- a)
- b)
- c)
there is a path of length ≤ 2 from u and v in E - d)
Where V4 is the set of vertics in G which are not isolated
Correct answer is option 'B'. Can you explain this answer?
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 ?
a)
b)
c)
there is a path of length ≤ 2 from u and v in Ed)
Where V4 is the set of vertics in G which are not isolated AMEY MOHITE asked • 6 hours agoConsider the entities 'hotel room', and 'person' with a many to many relationship 'lodging' as shown below:
If we wish to store information about the rent payment to be made by person (s) occupying different hotel rooms, then this information should appear as an attribute of - a)Person
- b)Hotel Room
- c)Lodging
- d)None of these
Correct answer is option 'C'. Can you explain this answer?
Consider the entities 'hotel room', and 'person' with a many to many relationship 'lodging' as shown below:
If we wish to store information about the rent payment to be made by person (s) occupying different hotel rooms, then this information should appear as an attribute of
a)
Person
b)
Hotel Room
c)
Lodging
d)
None of these
ASHA THAKUR asked • 6 hours agoWhich of the following is true for the language 
- a)It is not accepted by a Turing Machine
- b)It is regular but not context-free
- c)It is context-free but not regular
- d)It is neither regular nor context-free, but accepted by a Turing machine
Correct answer is option 'D'. Can you explain this answer?
Which of the following is true for the language
a)
It is not accepted by a Turing Machine
b)
It is regular but not context-free
c)
It is context-free but not regular
d)
It is neither regular nor context-free, but accepted by a Turing machine
DHIRENDRA GUPTA asked • 7 hours agoConsider the hash table of size seven, with starting index zero, and a hash function (3x + 4) mod 7. Assuming the has table is initially empty, which of the following is the contents of the table when the sequence 1, 3, 8, 10 is inserted into the table using dosed hashing?
Note that - denotes an empty location in the table- a)8, 10
- b)1, 8, 10, -, -, 3
- c)1 , 3
- d)1,10, 8, 3
Correct answer is option 'B'. Can you explain this answer?
Consider the hash table of size seven, with starting index zero, and a hash function (3x + 4) mod 7. Assuming the has table is initially empty, which of the following is the contents of the table when the sequence 1, 3, 8, 10 is inserted into the table using dosed hashing?
Note that - denotes an empty location in the table
Note that - denotes an empty location in the table
a)
8, 10
b)
1, 8, 10, -, -, 3
c)
1 , 3
d)
1,10, 8, 3
Sampath Warrior asked • 7 hours agoIn a compact single dimensional array representation for lower triangular matrices (i.e. all the elements above the diagonal are zero) of size n x n, non-zero elements (i.e. elements of the lower triangle) of each row are stored one after another, starting from the first row, the index of the (i, j)th element of the lower triangular matrix in this new representation is - a)i + j
- b)i + j - 1
- c)
- d)
Correct answer is option 'C'. Can you explain this answer?
In a compact single dimensional array representation for lower triangular matrices (i.e. all the elements above the diagonal are zero) of size n x n, non-zero elements (i.e. elements of the lower triangle) of each row are stored one after another, starting from the first row, the index of the (i, j)th element of the lower triangular matrix in this new representation is
a)
i + j
b)
i + j - 1
c)
d)
Manikant Sharma asked • 7 hours agoConsider the pushdown automaton (PDA) below which runs over the input alphabet (a, b, c). It has the stack alphabet {Z0, X} where Z0 is the bottom-of-stack marker. The set of states of the PDA is (s, t, u, f} where s is the start state and f is the final state. The PDA accepts by final state. The transitions of the PDA given below are depicted in a standard manner. For example, the transition (s, b, X) → (t, XZ0) means that if the PDA is in state s and the symbol on the top of the stack is X, then it can read b from the input and move to state t after popping the top of stack and pushing the symbols Z0 and X (in that order) on the stack.
... more
Consider the pushdown automaton (PDA) below which runs over the input alphabet (a, b, c). It has the stack alphabet {Z0, X} where Z0 is the bottom-of-stack marker. The set of states of the PDA is (s, t, u, f} where s is the start state and f is the final state. The PDA accepts by final state. The transitions of the PDA given below are depicted in a standard manner. For example, the transition (s, b, X) → (t, XZ0) means that if the PDA is in state s and the symbol on the top of the stack is X, then it can read b from the input and move to state t after popping the top of stack and pushing the symbols Z0 and X (in that order) on the stack.
GOVIND KUMAR asked • 7 hours agoLet r1 = ab*c*and r2 = (a*b+c)*and r3 = (a+b+c)*. Then which of the following is true- a) w = ’ac’ belongs to L(r2) and L(r3) but not L(r1)
- b)w = 'ac' belongs to L(r3) only
- c)w = 'ac' belongs to L(r1), L(r2) and L(r3)
- d)w = ‘ac’ belongs to L(r1) and L(r3) but not L(r2)
Correct answer is option 'D'. Can you explain this answer?
Let r1 = ab*c*and r2 = (a*b+c)*and r3 = (a+b+c)*. Then which of the following is true
a)
w = ’ac’ belongs to L(r2) and L(r3) but not L(r1)
b)
w = 'ac' belongs to L(r3) only
c)
w = 'ac' belongs to L(r1), L(r2) and L(r3)
d)
w = ‘ac’ belongs to L(r1) and L(r3) but not L(r2)
SUMRILIK SHAUNAK asked • 9 hours agoThe address sequence generated by tracing a particular program executing in a pure demand paging system with 100 records per page, with 1 free main memory frame is recorded as follows. What is the number of page faults?
0100, 0200, 0430, 0499, 0510, 0530, 0560, 0120, 0220, 0240, 0260, 0320, 0370 - a)13
- b)8
- c)7
- d)10
Correct answer is option 'C'. Can you explain this answer?
The address sequence generated by tracing a particular program executing in a pure demand paging system with 100 records per page, with 1 free main memory frame is recorded as follows. What is the number of page faults?
0100, 0200, 0430, 0499, 0510, 0530, 0560, 0120, 0220, 0240, 0260, 0320, 0370
0100, 0200, 0430, 0499, 0510, 0530, 0560, 0120, 0220, 0240, 0260, 0320, 0370
a)
13
b)
8
c)
7
d)
10
SAPNA DEVI asked • 9 hours agoAssume that the algorithms considered here sort the input sequences in ascending order. If the input is already in ascending order, which of the following are TRUE?I. Quicksort runs in Θ(n2) time
II. Bubblesort runs in Θ(n2) time
III. Mergesort runs in Θ(n) time
IV. Insertion sort runs in Θ(n) time- a)I and II only
- b)I and III only
- c)II and IV only
- d)I and IV only
Correct answer is option 'D'. Can you explain this answer?
Assume that the algorithms considered here sort the input sequences in ascending order. If the input is already in ascending order, which of the following are TRUE?
I. Quicksort runs in Θ(n2) time
II. Bubblesort runs in Θ(n2) time
III. Mergesort runs in Θ(n) time
IV. Insertion sort runs in Θ(n) time
II. Bubblesort runs in Θ(n2) time
III. Mergesort runs in Θ(n) time
IV. Insertion sort runs in Θ(n) time
a)
I and II only
b)
I and III only
c)
II and IV only
d)
I and IV only
MAMTA DEVI asked • 10 hours agoWhich 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, c is a constant.- a)T(n) = 2T (n/2) + cn
- b)T(n) = T(n – 1) + T(0) + cn
- c)T(n) = 2T (n – 2) + cn
- d)T(n) = T(n/2) + cn
Correct answer is option 'B'. Can you explain this answer?
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, c is a constant.
a)
T(n) = 2T (n/2) + cn
b)
T(n) = T(n – 1) + T(0) + cn
c)
T(n) = 2T (n – 2) + cn
d)
T(n) = T(n/2) + cn
PRAKHAR AGRAWAL asked • 10 hours agoWhich one of the following is TRUE at any valid state in shift-reduce parsing?- a)Viable prefixes appear only at the bottom of the stack and not inside
- b)Viable prefixes appear only at the top of the stack and not inside
- c)The stack contains only a set of viable prefixes
- d)The stack never contains viable prefixes
Correct answer is option 'C'. Can you explain this answer?
Which one of the following is TRUE at any valid state in shift-reduce parsing?
a)
Viable prefixes appear only at the bottom of the stack and not inside
b)
Viable prefixes appear only at the top of the stack and not inside
c)
The stack contains only a set of viable prefixes
d)
The stack never contains viable prefixes
AMISH KUMAR asked • 11 hours agoWhich of the following is NOT true of deadlock prevention and deadlock avoidance schemes?- a)In deadlock prevention, the request for resources is always granted if the resulting state is. safe.
- b)In deadlock avoidance, the request for resources is always granted if the resulting state is safe.
- c)Deadlock avoidance is less restrictive than deadlock prevention.
- d)Deadlock avoidance requires knowledge of resource requirements a priori.
Correct answer is option 'A'. Can you explain this answer?
Which of the following is NOT true of deadlock prevention and deadlock avoidance schemes?
a)
In deadlock prevention, the request for resources is always granted if the resulting state is. safe.
b)
In deadlock avoidance, the request for resources is always granted if the resulting state is safe.
c)
Deadlock avoidance is less restrictive than deadlock prevention.
d)
Deadlock avoidance requires knowledge of resource requirements a priori.
ANITA KUMARI asked • 11 hours agoLet G be a graph with n vertices and m edges. What is the tightest upper bound on the running time on Depth First Search of G? Assume that the graph is represented using adjacency matrix.- a)O(n)
- b)O(m+n)
- c)O(n2)
- d)O(mn)
Correct answer is option 'C'. Can you explain this answer?
Let G be a graph with n vertices and m edges. What is the tightest upper bound on the running time on Depth First Search of G? Assume that the graph is represented using adjacency matrix.
a)
O(n)
b)
O(m+n)
c)
O(n2)
d)
O(mn)
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 Boolean variables is
DIKSHA KUMARI asked • 11 hours agoIn a bottom-up evaluation of a syntax directed definition, inherited attributes can- a)Always be evaluated
- b)Be evaluated only if the definition is L-attributed
- c)Be evaluated only if the definition has synthesized attributes
- d)Never be evaluated
Correct answer is option 'C'. Can you explain this answer?
In a bottom-up evaluation of a syntax directed definition, inherited attributes can
a)
Always be evaluated
b)
Be evaluated only if the definition is L-attributed
c)
Be evaluated only if the definition has synthesized attributes
d)
Never be evaluated
ANCHAL NIRANJAN asked • 11 hours agoIn the context of abstract-syntax-tree (AST) and control-flow-graph (CFG), which one of the following is True?- a)In both AST and CFG, let node N2 be the successor of node N1. In the input program, the code corresponding to N2 is present after the code corresponding to N1
- b)For any input program, neither AST nor CFG will contain a cycle
- c)The maximum number of successors of a node in an AST and a CFG depends on the input program
- d)Each node in AST and CFG corresponds to at most one statement in the input program
Correct answer is option 'C'. Can you explain this answer?
In the context of abstract-syntax-tree (AST) and control-flow-graph (CFG), which one of the following is True?
a)
In both AST and CFG, let node N2 be the successor of node N1. In the input program, the code corresponding to N2 is present after the code corresponding to N1
b)
For any input program, neither AST nor CFG will contain a cycle
c)
The maximum number of successors of a node in an AST and a CFG depends on the input program
d)
Each node in AST and CFG corresponds to at most one statement in the input program
BINTA BALA asked • 11 hours agoA networking company uses a compression technique to encode the message before transmitting over the network. Suppose the message contains the following characters with their frequency:
Note : Each character in input message takes 1 byte. If the compression technique used is Huffman Coding, how many bits will be saved in the message?- a)224
- b)800
- c)576
- d)324
Correct answer is option 'C'. Can you explain this answer?
A networking company uses a compression technique to encode the message before transmitting over the network. Suppose the message contains the following characters with their frequency:
Note : Each character in input message takes 1 byte. If the compression technique used is Huffman Coding, how many bits will be saved in the message?
a)
224
b)
800
c)
576
d)
324
Saryu Bakshi asked • 12 hours agoConsider a queue between the two processes indicated below. A/is the length of queue and e, f and b are semaphore, init : e : = N; f = 0; b : = 1;
Which of the following statements is/are true?
1. The purpose of semaphore f is to ensure that dequeue is not executed on an empty queue.
2. The purpose of semaphore e is to ensure that deadlock does not occur.
3. The purpose of semaphore b is to provide mutual exclusion for queue operations.- a)1 only
- b)2 only
- c)1 and 3 only
- d)2 and 3 only
Correct answer is option 'C'. Can you explain this answer?
Consider a queue between the two processes indicated below. A/is the length of queue and e, f and b are semaphore, init : e : = N; f = 0; b : = 1;
Which of the following statements is/are true?
1. The purpose of semaphore f is to ensure that dequeue is not executed on an empty queue.
2. The purpose of semaphore e is to ensure that deadlock does not occur.
3. The purpose of semaphore b is to provide mutual exclusion for queue operations.
Which of the following statements is/are true?
1. The purpose of semaphore f is to ensure that dequeue is not executed on an empty queue.
2. The purpose of semaphore e is to ensure that deadlock does not occur.
3. The purpose of semaphore b is to provide mutual exclusion for queue operations.
a)
1 only
b)
2 only
c)
1 and 3 only
d)
2 and 3 only
GURIK SINGH asked • 12 hours agoThe data flow model of an application mainly shows- a)The underlying data and the relationships among them.
- b)Processing requirements and the flow of data.
- c)Decision and control information.
- d)Communication network structure.
Correct answer is option 'B'. Can you explain this answer?
The data flow model of an application mainly shows
a)
The underlying data and the relationships among them.
b)
Processing requirements and the flow of data.
c)
Decision and control information.
d)
Communication network structure.
SUMAN LATA asked • 12 hours ago Select the option closest to the meaning of the idiom – Skeleton crew- a)A group of stupid people
- b)A group of highly skilled people
- c)Minimum number of people required to keep a job running
- d)A group of lazy people
Correct answer is option 'C'. Can you explain this answer?
Select the option closest to the meaning of the idiom – Skeleton crew
a)
A group of stupid people
b)
A group of highly skilled people
c)
Minimum number of people required to keep a job running
d)
A group of lazy people
CHANDER KALA asked • 12 hours agoIf P and Q are two random events, then the following is TRUE:- a)Independence of P and Q implies that probability (P ∩ Q) = 0
- b)Probability (P ∪ Q) ≥ Probability (P) + Probability (Q)
- c)If P and Q are mutually exclusive, then they must be independent
- d)Probability (P ∩ Q) ≤ Probability (P)
Correct answer is option 'D'. Can you explain this answer?
If P and Q are two random events, then the following is TRUE:
a)
Independence of P and Q implies that probability (P ∩ Q) = 0
b)
Probability (P ∪ Q) ≥ Probability (P) + Probability (Q)
c)
If P and Q are mutually exclusive, then they must be independent
d)
Probability (P ∩ Q) ≤ Probability (P)
Subodh Kumar asked • 12 hours agoConsider 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- a)Ω(log n)
- b)Ω(n)
- c)Ω(n log n)
- d)Ω(n2)
Correct answer is option 'A'. Can you explain this answer?
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
a)
Ω(log n)
b)
Ω(n)
c)
Ω(n log n)
d)
Ω(n2)
SEEMA DEVI asked • 13 hours agoThe order of an internal node in a B+ tree index is the maximum number of children it can have. Suppose that a child pointer takes 6 bytes, the search field value takes 14 bytes, and the block size is 512 bytes. What is the order of the internal node?- a)24
- b)25
- c)26
- d)27
Correct answer is option 'C'. Can you explain this answer?
The order of an internal node in a B+ tree index is the maximum number of children it can have. Suppose that a child pointer takes 6 bytes, the search field value takes 14 bytes, and the block size is 512 bytes. What is the order of the internal node?
a)
24
b)
25
c)
26
d)
27
Virat Kohli asked • 13 hours agoWhich of the following is true about merge sort?- a)Merge Sort works better than quick sort if data is accessed from slow sequential memory.
- b)Merge Sort is stable sort by nature
- c)Merge sort outperforms heap sort in most of the practical situations.
- d)All of the above.
Correct answer is option 'D'. Can you explain this answer?
Which of the following is true about merge sort?
a)
Merge Sort works better than quick sort if data is accessed from slow sequential memory.
b)
Merge Sort is stable sort by nature
c)
Merge sort outperforms heap sort in most of the practical situations.
d)
All of the above.
AMAN THAPLIYAL asked • 13 hours agoConsider the following two functions. What are time complexities of the functions?
- a)O(2^n) for both fun1() and fun2()
- b)O(n) for fun1() and O(2^n) for fun2()
- c)O(2^n) for fun1() and O(n) for fun2()
- d)O(n) for both fun1() and fun2()
Correct answer is option 'B'. Can you explain this answer?
Consider the following two functions. What are time complexities of the functions?
a)
O(2^n) for both fun1() and fun2()
b)
O(n) for fun1() and O(2^n) for fun2()
c)
O(2^n) for fun1() and O(n) for fun2()
d)
O(n) for both fun1() and fun2()
ANCHAL NIRANJAN asked • 13 hours agoConsiderthe values A = 2.0 x 1030, B = -2.0x1030, C = 1.0 and the sequence. What will be the values of X and Y if the following sequence of statements are carried out
- a)X = 1.0, Y = 1.0
- b)X = 0.0, Y = 1.0
- c)X = 1.0, Y = 0.0
- d)X = 0.0, Y = 0.0
Correct answer is option 'C'. Can you explain this answer?
Considerthe values A = 2.0 x 1030, B = -2.0x1030, C = 1.0 and the sequence. What will be the values of X and Y if the following sequence of statements are carried out
a)
X = 1.0, Y = 1.0
b)
X = 0.0, Y = 1.0
c)
X = 1.0, Y = 0.0
d)
X = 0.0, Y = 0.0
GOVIND KUMAR asked • 14 hours agoIn the following table, the left column contains the names of standard graph algorithms and the right column contains the time complexities of the algorithms. Match each algorithm with its time complexity.1. Bellman-Ford algorithm
2. Kruskal’s algorithm
3. Floyd-Warshall algorithm
4. Topological sortingA : O(m log n)
B : O(n3)
C : O(nm)
D : O(n + m)- a)1→ C, 2 → A, 3 → B, 4 → D
- b)1→ B, 2 → D, 3 → C, 4 → A
- c)1→ C, 2 → D, 3 → A, 4 → B
- d)1→ B, 2 → A, 3 → C, 4 → D
Correct answer is option 'A'. Can you explain this answer?
In the following table, the left column contains the names of standard graph algorithms and the right column contains the time complexities of the algorithms. Match each algorithm with its time complexity.
1. Bellman-Ford algorithm
2. Kruskal’s algorithm
3. Floyd-Warshall algorithm
4. Topological sorting
2. Kruskal’s algorithm
3. Floyd-Warshall algorithm
4. Topological sorting
A : O(m log n)
B : O(n3)
C : O(nm)
D : O(n + m)
B : O(n3)
C : O(nm)
D : O(n + m)
a)
1→ C, 2 → A, 3 → B, 4 → D
b)
1→ B, 2 → D, 3 → C, 4 → A
c)
1→ C, 2 → D, 3 → A, 4 → B
d)
1→ B, 2 → A, 3 → C, 4 → D
POOJA KUMARI asked • 14 hours agoIn quick sort, for sorting n elements, the (n/4)th smallest element is selected as pivot using an O(n) time algorithm. What is the worst case time complexity of the quick sort?- a)θ(n)
- b)θ(nLogn)
- c)θ(n^2)
- d)θ(n^2 log n)
Correct answer is option 'B'. Can you explain this answer?
In quick sort, for sorting n elements, the (n/4)th smallest element is selected as pivot using an O(n) time algorithm. What is the worst case time complexity of the quick sort?
a)
θ(n)
b)
θ(nLogn)
c)
θ(n^2)
d)
θ(n^2 log n)
ANCHAL NIRANJAN asked • 14 hours agoA given relation is known to be in third normal form. Select the statement which can be inferred from this- a)All attributes contribute to the primary key.
- b)Each non-key attribute determine the primary key.
- c)Each non-key attribute is determine by the primary key.
- d)Every determinant is a candidate key.
Correct answer is option 'C'. Can you explain this answer?
A given relation is known to be in third normal form. Select the statement which can be inferred from this
a)
All attributes contribute to the primary key.
b)
Each non-key attribute determine the primary key.
c)
Each non-key attribute is determine by the primary key.
d)
Every determinant is a candidate key.
, T(1) = 1, T(0) = 0
MONIKA TEMPTA asked • 16 hours agoWhich of the following is TRUE?- a)Every subset of a regular set is regular
- b)Every finite subset of a non-regular set is regular
- c)The union of two non-regular sets is not regular
- d)Infinite union of finite sets is regular
Correct answer is option 'B'. Can you explain this answer?
Which of the following is TRUE?
a)
Every subset of a regular set is regular
b)
Every finite subset of a non-regular set is regular
c)
The union of two non-regular sets is not regular
d)
Infinite union of finite sets is regular
MANISHA DESH asked • 17 hours agoFor a context-free grammar, FOLLOW(A) is the set of terminals that can appear immediately to the right of non-terminal A in some “sentential” form. We defined to sets LFOLLOW(A) and RFOLLOW(A) by replacing the word “left most sentential” and “right most sentential” respectively in the definition of FOLLOW(A).Which of the following statements is/are tru- a)FOLLOW(A) and RFOLLOW(A) may be different.
- b)FOLLOW(A) and RFOLLOW(A) are always the same.
- c)All the three sets are identical.
- d)All the three sets are different.
Correct answer is option 'C'. Can you explain this answer?
For a context-free grammar, FOLLOW(A) is the set of terminals that can appear immediately to the right of non-terminal A in some “sentential” form. We defined to sets LFOLLOW(A) and RFOLLOW(A) by replacing the word “left most sentential” and “right most sentential” respectively in the definition of FOLLOW(A).
Which of the following statements is/are tru
a)
FOLLOW(A) and RFOLLOW(A) may be different.
b)
FOLLOW(A) and RFOLLOW(A) are always the same.
c)
All the three sets are identical.
d)
All the three sets are different.
SHUBHAM VINAY asked • 17 hours agoK4 and Q3 are graphs with the following structures
Q. Which one of the following statements is TRUE in relation to these graphs?- a)K4 is planar while Q3 is not
- b)Both K4 and Q3 are planar
- c)Q3 is planar while K4 is not
- d)Neither K4 not Q3 is planar
Correct answer is option 'B'. Can you explain this answer?
K4 and Q3 are graphs with the following structures
Q. Which one of the following statements is TRUE in relation to these graphs?
a)
K4 is planar while Q3 is not
b)
Both K4 and Q3 are planar
c)
Q3 is planar while K4 is not
d)
Neither K4 not Q3 is planar
Fetching relevant content for you
Ask a question
Related Courses
Follow Us
