GATE CSE branch:cs PYQs & Answers — Page 11

Questions 101–110 of 975. Imported answers require independent review unless marked reviewed.

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

Consider a system with a processor and a 4 KB direct mapped cache with block size of 16 bytes. The system has a 16 MB physical memory. Four words P, Q, R, and S are accessed by the processor in the same order 10 times. That is, there are a total of 40 memory references in the sequence P, Q, R, S, P, Q, R, S,...

Assume that the cache memory is initially empty. The physical addresses of the words are given below (1 word =1 byte).

P: 0x845B32, Q: 0x845B26, R: 0x845B36, S: 0x846B32

Which of the following statements is/are true?

Note: 1K=2¹⁰ and 1M=2²⁰

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

Every access to P results in a cache miss

Every access to R results in a cache hit

Every access to Q results in a cache miss

Except the first access to S, all subsequent accesses to S result in cache hits

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

Consider the following two syntax-directed definitions SD1 and SD2 for type declarations.

SD1 Grammar (G1) | Semantic Rules D → T V: D.type = T.type; V.type = T.type T → int: T.type = int T → float: T.type = float V → V₁ id: V₁.type = V.type; put(id.entry, V.type) V → id: put(id.entry, V.type)

SD2 Grammar (G2) | Semantic Rules D → D₁ id: D.type = D₁.type; put(id.entry, D₁.type) D → T id: D.type = T.type; put(id.entry, T.type) T → int: T.type = int T → float: T.type = float

D is the start symbol, and int, float and id are the terminals. The non-terminal V₁ is the same as V and the non-terminal D₁ is the same as D. Here, the subscript is used to differentiate the grammar symbol on the two sides of a production. The function put updates the symbol table with the type information for an identifier.

Let P and Q be the languages specified by grammars G1 and G2, respectively.

Which of the following statements is/are true?

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

The languages P and Q are the same

SD2 is S-attributed and contains only synthesized attributes

SD1 is L-attributed and contains only inherited attributes

The specifications of SD1 and SD2 are such that the same entries get added to the symbol table

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

To keep track of free blocks in a file system, one of the two approaches is generally used – using bitmaps (bit vectors) or using linked lists. Consider that the linked list approach is used to keep track of free blocks in a file system. Assume that the disk size is 16 GB, block size is 2 KB, and block numbers used are 32-bit long. A single pointer of size 4 bytes is used in each block of the list to point to the next block of the list. The number of blocks required to hold the free disk block numbers is __________. (answer in integer)

Note: 1K=2¹⁰ and 1G=2³⁰

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

Consider a system that has a cache memory unit and a memory management unit (MMU). The address input to the cache memory is a physical address. The MMU has a translation lookaside buffer (TLB). Assume that when a page is evicted from the main memory, the corresponding blocks in the cache are marked as invalid.

For a given memory reference, which of the following sequences of events can NEVER happen?

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

TLB miss, Page table hit, Cache hit

TLB hit, Page table miss, Cache hit

TLB miss, Page table miss, Cache hit

TLB miss, Page table miss, Cache miss

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

A system has a Translation Lookaside Buffer (TLB) that has a reach of 1 MB. TLB reach is defined as the total amount of physical memory that can be accessed through the TLB entries. The paging system uses pages of size 4 KB. The virtual address space is 64 GB and physical address space is 1 GB. If each TLB entry stores a 4-bit process id, page number, frame number, and a 2-bit control field, then the size of the TLB (in bytes) is __________. (answer in integer)

Note: 1K=2¹⁰, 1M=2²⁰, 1G=2³⁰

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

An undirected, unweighted, simple graph

is said to be 2-colorable if there exists a function

such that for every

Which of the following statements about 2-colorable graphs is/are true?

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

is 2-colorable, then

may contain cycles of odd length

is 2-colorable, then

may contain cycles of even length

An optimal algorithm for testing whether

is 2-colorable runs in time

, if

is represented as an adjacency list

An optimal algorithm for testing whether

is 2-colorable runs in time

, if

is represented as an adjacency list

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

Consider contiguous allocation of physical memory to processes using variable partitioning scheme. Suppose there are 8 holes in the memory of sizes 20 KB, 4 KB, 25 KB, 18 KB, 7 KB, 9 KB, 15 KB, and 12 KB. Assume that no two holes are adjacent. Two processes P1 of size 16 KB and P2 of size 9 KB arrive in that order, and they are allocated memory using the best-fit technique. After allocating space to P1 and P2, the number of holes of size less than 8 KB is __________. (answer in integer)

Note: 1K=2¹⁰

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

GATE CSE branch:cs PYQs

Question 51

Question 51

Question 52

Question 52

Question 53

Question 53

Question 54

Question 54

Question 55

Question 55