GATE CSE discipline:computing-and-data PYQs & Answers — Page 86

Questions 851–860 of 975. Imported answers require independent review unless marked reviewed.

Match the algorithms with their time complexities:

Algorithm Time complexity (P) Towers of Hanoi with n disks (i) Θ(n²) (Q) Binary search given n sorted numbers (ii) Θ(n log n) (R) Heap sort given n numbers at the worst case (iii) Θ(2ⁿ) (S) Addition of two n × n matrices (iv) Θ(log n)

Your answerChoose one option.

P → (iii), Q → (iv), R → (i), S → (ii)

P → (iv), Q → (iii), R → (i), S → (ii)

P → (iii), Q → (iv), R → (ii), S → (i)

P → (iv), Q → (iii), R → (ii), S → (i)

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

Consider the following functions from positive integers to real numbers:

The CORRECT arrangement of the above functions in increasing order of asymptotic complexity is:

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

Let L₁, L₂ be any two context-free languages and R be any regular language. Then which of the following is/are CORRECT?

I. L₁ ∪ L₂ is context-free. II. L̅₁ is context-free. III. L₁ − R is context-free. IV. L₁ ∩ L₂ is context-free.

Your answerChoose one option.

I, II and IV only

I and III only

II and IV only

I only

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

Consider the following table:

Algorithms	Design Paradigms
(P) Kruskal	(i) Divide and Conquer
(Q) Quicksort	(ii) Greedy
(R) Floyd-Warshal	(iii) Dynamic Programming

Match the algorithms to the design paradigms they are based on.

Your answerChoose one option.

(P) ↔ (ii), (Q) ↔ (iii), (R) ↔ (i)

(P) ↔ (iii), (Q) ↔ (i), (R) ↔ (ii)

(P) ↔ (ii), (Q) ↔ (i), (R) ↔ (iii)

(P) ↔ (i), (Q) ↔ (ii), (R) ↔ (iii)

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

Match the following according to input (from the left column) to the compiler phase (in the right column) that processes it:

(P) Syntax tree (Q) Character stream (R) Intermediate representation (S) Token stream

(i) Code generator (ii) Syntax analyser (iii) Semantic analyser (iv) Lexical analyser

Your answerChoose one option.

P → (ii), Q → (iii), R → (iv), S → (i)

P → (ii), Q → (i), R → (iii), S → (iv)

P → (iii), Q → (iv), R → (i), S → (ii)

P → (i), Q → (iv), R → (ii), S → (iii)

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

Let

be a binary search tree with 15 nodes. The minimum and maximum possible heights of

are:

Note: The height of a tree with a single node is 0.

Your answerChoose one option.

4 and 15 respectively

3 and 14 respectively

4 and 14 respectively

3 and 15 respectively

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

Which of the following statements about parser is/are CORRECT?

I. Canonical LR is more powerful than SLR. II. SLR is more powerful than LALR. III. SLR is more powerful than Canonical LR.

Your answerChoose one option.

I only

II only

III only

II and III only

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

The

-bit fixed-point representation of an unsigned real number

uses

bits for the fraction part. Let

. The range of decimal values for

in this representation is

Your answerChoose one option.

0 to

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

Which of the following is/are shared by all the threads in a process?

I. Program counter II. Stack III. Address space IV. Registers

Your answerChoose one option.

I and II only

III only

IV only

III and IV only

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

Consider the C code fragment given below:

typedef struct node {

int data;

node* next;

} node;

void join(node* m, node* n){

node* p = n;

while(p->next != NULL) {

p = p->next;

}

p->next = m;

}

Assuming that m and n point to valid NULL-terminated linked lists, invocation of join will

Your answerChoose one option.

append list m to the end of list n for all inputs.

either cause a null pointer dereference or append list m to the end of list n.

cause a null pointer dereference for all inputs.

append list n to the end of list m for all inputs.

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

GATE CSE discipline:computing-and-data PYQs

Question 3

Question 4

Question 4

Question 5

Question 5

Question 6

Question 6

Question 7

Question 7

Question 8