GATE CSE format:mcq PYQs & Answers — Page 22

Questions 211–220 of 534. Imported answers require independent review unless marked reviewed.

Consider the context-free grammar

below

where

and

are non-terminals, and

and

are terminal symbols. The starting non-terminal is

Which one of the following statements is CORRECT?

Your answerChoose one option.

The language generated by

is not a regular language

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

Consider the pushdown automaton (PDA)

below, which runs on the input alphabet

, has stack alphabet

, and has three states

, with

being the start state. A transition from state

to state

, labelled

, where

is an input symbol or

is a stack symbol, and

is a string of stack symbols, represents the fact that in state

, the PDA can read

from the input, with

on the top of its stack, pop

from the stack, push in the string

on the stack, and go to state

. In the initial configuration, the stack has only the symbol

in it. The PDA accepts by empty stack.

Which one of the following options correctly describes the language accepted by

Diagram for Computer Science and Information Technology question 40

Your answerChoose one option.

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

Consider the given C-code and its corresponding assembly code, with a few operands U1–U4 being unknown. Some useful information as well as the semantics of each unique assembly instruction is annotated as inline comments in the code. The memory is byte-addressable.

//C-code ;assembly-code (; indicates comments)

;r1-r5 are 32-bit integer registers

;initialize r1=0, r2=10

;initialize r3, r4 with base address of a, b

int a[10], b[10], i; L01: jeq r1, r2, end ;if(r1==r2) goto end

// int is 32-bit L02: lw r5, 0(r4) ;r5 <- Memory[r4+0]

for (i=0; i<10; i++) L03: shl r5, r5, U1 ;r5 <- r5 << U1

a[i] = b[i] * 8; L04: sw r5, 0(r3) ;Memory[r3+0] <- r5

L05: add r3, r3, U2 ;r3 <- r3+U2

L06: add r4, r4, U3

L07: add r1, r1, 1

L08: jmp U4 ;goto U4

L09: end

Which one of the following options is a CORRECT replacement for operands in the position (U1, U2, U3, U4) in the above assembly code?

Your answerChoose one option.

(8, 4, 1, L02)

(3, 4, 4, L01)

(8, 1, 1, L02)

(3, 1, 1, L01)

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

A 4 kilobyte (KB) byte-addressable memory is realized using four 1 KB memory blocks. Two input address lines (IA4 and IA3) are connected to the chip select (CS) port of these memory blocks through a decoder as shown in the figure. The remaining ten input address lines from IA11–IA0 are connected to the address port of these blocks. The chip select (CS) is active high.

The input memory address (IA11–IA0), in decimal, for the starting locations (Addr=0) of each block (indicated as X1, X2, X3, X4 in the figure are among the options given below. Which one of the following options is CORRECT?

Diagram for Computer Science and Information Technology question 42

Your answerChoose one option.

(0, 1, 2, 3)

(0, 1024, 2048, 3072)

(0, 8, 16, 24)

(0, 0, 0, 0)

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

Consider a sequential digital circuit consisting of T flip-flops and D flip-flops as shown in the figure. CLKIN is the clock input to the circuit. At the beginning, Q1, Q2 and Q3 have values 0, 1 and 1, respectively.

Diagram for Computer Science and Information Technology question 43

Which one of the given values of (Q1, Q2, Q3) can NEVER be obtained with this digital circuit?

Your answerChoose one option.

(0, 0, 1)

(1, 0, 0)

(1, 0, 1)

(1, 1, 1)

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

A Boolean digital circuit is composed using two 4-input multiplexers (M1 and M2) and one 2-input multiplexer (M3) as shown in the figure. X0–X7 are the inputs of the multiplexers M1 and M2 and could be connected to either 0 or 1. The select lines of the multiplexers are connected to Boolean variables A, B and C as shown.

Diagram for Computer Science and Information Technology question 44

Which one of the following sets of values of (X0, X1, X2, X3, X4, X5, X6, X7) will realise the Boolean function

Your answerChoose one option.

(1, 1, 0, 0, 1, 1, 1, 0)

(1, 1, 0, 0, 1, 1, 0, 1)

(1, 1, 0, 1, 1, 1, 0, 0)

(0, 0, 1, 1, 0, 1, 1, 1)

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

Consider the IEEE-754 single precision float point numbers P=0xC1800000 and Q=0x3F5C2EF4. Which one of the following corresponds to the product of these numbers (i.e., P × Q), represented in the IEEE-754 single precision format?

Your answerChoose one option.

0x404C2EF4

0x405C2EF4

0xC15C2EF4

0xC14C2EF4

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

Let A be a priority queue for maintaining a set of elements. Suppose A is implemented using a max-heap data structure. The operation Extract-Max(A) extracts and deletes the maximum element from A. The operation Insert(A,key) inserts a new element key in A. The properties of a max-heap are preserved at the end of each of these operations.

When A contains n elements, which one of the following statements about the worst case running time of these two operations is TRUE?

Your answerChoose one option.

Both Extract-Max(A) and Insert(A,key) run in O(1).

Both Extract-Max(A) and Insert(A,key) run in O(log(n)).

Extract-Max(A) runs in O(1) whereas Insert(A,key) runs in O(n).

Extract-Max(A) runs in O(1) whereas Insert(A,key) runs in O(log(n)).

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

Consider the C function foo and the binary tree shown.

typedef struct node {

int val;

struct node *left, *right;

} node;

int foo(node *p) {

int retval;

if (p == NULL)

return 0;

else {

retval = p->val + foo(p->left) + foo(p->right);

printf("%d ", retval);

return retval;

}

When foo is called with a pointer to the root node of the given binary tree, what will it print?

Diagram for Computer Science and Information Technology question 47

Your answerChoose one option.

3 8 13 11 10

3 8 10 11 13

3 8 16 13 24 50

3 16 8 50 24 13

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

Let

, where

is a large positive integer greater than 100. Let

be a positive integer less than

. Let

be subsets of

with

and

. We say that a permutation of

separates

from

if one of the following is true.

All members of

appear in the permutation before any of the members of

All members of

appear in the permutation before any of the members of

How many permutations of

separate

from

Your answerChoose one option.

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

GATE CSE format:mcq PYQs

Question 39

Question 40

Question 41

Question 42

Question 43

Question 44

Question 45

Question 46

Question 47

Question 48