GATE CSE format:msq PYQs & Answers — Page 3

Questions 21–30 of 160. Imported answers require independent review unless marked reviewed.

Consider the following two finite automata

and

Diagram for Computer Science and Information Technology question 47

Which of the following statements is/are true?

Your answerSelect all correct options. You can choose more than one.

is a proper subset of

consists of all strings in

whose length is divisible by 3

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

Consider a Boolean function

with the following minterm expression:

Which of the following options is/are the minimal sum-of-products expression(s) of

Your answerSelect all correct options. You can choose more than one.

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

Let

and let

Which of the following constraints ensure(s) that the language

is context-free?

Your answerSelect all correct options. You can choose more than one.

and

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

Let

be a simple, undirected, edge-weighted graph with unique edge weights.

Which of the following statements about the minimum spanning tree (MST) of

is/are true?

Your answerSelect all correct options. You can choose more than one.

In every cycle

, the edge with the largest weight in

is not in any MST

In every cycle

, the edge with the smallest weight in

is in every MST

For every vertex

, the edge with the largest weight incident on

is not in any MST

For every vertex

, the edge with the smallest weight incident on

is in every MST

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

Consider a binary search tree (BST) with

leaf nodes (

). Given any node

, the key present in the node is denoted as

. All the keys present in the given BST are distinct. The keys belong to the set of real numbers.

For a node

, let

denote the node that is its inorder successor. If a node

does not have an inorder successor, then

. As there are no duplicates, if

is not

, then

Corresponding to every leaf node

that has a non-NULL

, a new key

with the following property is to be inserted into the BST.

Let

represent the list of all such new keys to be inserted into the BST.

Which of the following statements is/are true?

Your answerSelect all correct options. You can choose more than one.

cannot have any duplicates

will have at least one element

After inserting all keys from

, the height of the BST can increase at most by one

Number of nodes in the BST will double after inserting all keys from

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

Consider the following pseudocode for depth-first search (DFS) algorithm which takes a directed graph

as input, where

and

are the discovery time and finishing time, respectively, of the vertex

Suppose that the input directed graph

is a directed acyclic graph (DAG).

For an edge

, which of the following options will NEVER be correct?

Your answerSelect all correct options. You can choose more than one.

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

Consider a stack

and a queue

. Both of them are initially empty and have the capacity to store ten elements each. The elements 1, 2, 3, 4, and 5 arrive one by one, in that order. When an element arrives, it is assigned either to

(pushed on

) or to

(enqueued to

). Once all the five elements are stored, the output is generated in two steps. First, stack

is emptied by popping all elements. Then queue

is emptied by dequeuing all elements. The output obtained by following this process is 4 3 1 2 5.

Given the output, the objective is to predict whether an element was assigned to

Which of the following options are possible valid assignment(s) of the elements?

Note: In the options, the notation

denotes that element

was assigned to

and

denotes that element

was assigned to

Your answerSelect all correct options. You can choose more than one.

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

Let

and

be two languages over a finite alphabet, such that

and

are regular languages. Which of the following statements is/are always true?

Your answerSelect all correct options. You can choose more than one.

is regular

is context-free

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

Consider three processes P1, P2, and P3 running identical code, as shown in the pseudocode below. A and B are two binary semaphores initialized to 1 and 0, respectively. X is a shared variable initialized to 0. Each line in the pseudocode is executed atomically.

Pseudocode of P1, P2, and P3

Wait(A);

Print(*);

X = X+1;

If (X == 2)

{

Print($);

Signal(B);

}

Signal(A);

Wait(B);

Print(#);

Signal(B);

Assume that any of the three processes can start to execute first and context switching can happen between these processes at any arbitrary time and in any arbitrary order.

Which of the following patterns is/are possible to be generated as an outcome of the execution of these three processes?

Your answerSelect all correct options. You can choose more than one.

**$###

**#*##

**##*#

***$##

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

Consider the following context-free grammar

In the above grammar,

is the start symbol,

and

are terminal symbols, and

and

are non-terminal symbols.

Let

be the language generated by the grammar

. For a string

, let

be the number of

’s in

and

be the number of

’s in

Which of the following statements is/are true?

Your answerSelect all correct options. You can choose more than one.

There is a string

such that

For every string

There is a string

such that

For every string

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

GATE CSE format:msq PYQs

Question 47

Question 48

Question 48

Question 49

Question 49

Question 50

Question 50

Question 51

Question 51

Question 52