GATE 2003 CSE & IT

Which of the following is NOT an advantage of using shared, dynamically linked libraries as opposed to using statically linked libraries?

Consider the following class definitions in a hypothetical Object Oriented language that supports inheritance and uses dynamic binding. The language should not be assumed to be eit...

Consider the function f defined below. struct item { int data; struct item * next; }; int f(struct item *p) { return ((p == NULL) || (p ->next == NULL) || ((p->data <= p -> next ->...

$$\mathop {Lim}\limits_{x \to 0} \,{{Si{n^2}x} \over x} = \_\_\_\_.$$

Let $$A$$ be a sequence of $$8$$ distinct integers sorted in ascending order. How many distinct pairs of sequence, $$B$$ and $$C$$ are there such that i) Each is sorted in ascendin...

Consider the grammar shown below $$\eqalign{ & S \to iEtSS'\,|\,\,a \cr & S' \to eS\,|\,\,\varepsilon \cr & E \to b \cr} $$ In the predictive parse table, $$M$$, of this grammar, t...

The following resolution rule is used in logic programming. Derive clause $$\left( {P \vee Q} \right)$$ from clauses $$\left( {P \vee R} \right)$$, $$\left( {Q \vee \neg R} \right)...

Let S be a stack of size n >= 1. Starting with the empty stack, suppose we push the first n natural numbers in sequence, and then perform n pop operations. Assume that Push and Pop...

Suppose the numbers 7, 5, 1, 8, 3, 6, 0, 9, 4, 2 are inserted in that order into an initially empty binary search tree. The binary search tree uses the usual ordering on natural nu...

Assume the following C variable declaration int * A[10], B[10][10]; Of the following expressions I. A[2] II. A[2] [3] III. B[1] IV. B[2] [3] Which will not give compile-time errors...

In a system with $$32$$ bit virtual addresses and $$1$$ $$KB$$ page size, use of one-level page tables for virtual to physical address translation is not practical because of

Consider the following system of linear equations $$$\left[ {\matrix{ 2 & 1 & { - 4} \cr 4 & 3 & { - 12} \cr 1 & 2 & { - 8} \cr } } \right]\left[ {\matrix{ x \cr y \cr z \cr } } \r...

Which of the following statements is FALSE?

A processor uses $$2$$-level page tables for virtual to physical address translation. Page tables for both levels are stored in the main memory. Virtual and physical addresses are...

Consider the grammar shown below. $$\eqalign{ & S \to CC \cr & C \to cC\,|\,d \cr} $$ This grammar is

Which of the following is NOT an advantage of using shared, dynamically linked libraries as opposed to using statically linked libraries?

Which of the following functionalities must be implemented by a transport protocol over and above the network protocol?

Host A is sending data to host B over a full duplex link. A and B are using the sliding window protocol for flow control. The send and receive window sizes are 5 packets each. Data...

Which of the following suffices to convert an arbitrary CFG to an LL(1) grammar?

Suppose we want to synchronize two concurrent processes P and Q using binary semaphores S and T. The code for the processes P and Q is shown below. Process P: while(1){ W: Print '0...

Which of the following scenarios may lead to an irrecoverable error in a database system?

Using a larger block size in a fixed block size file system leads to

Which of the following statements is FALSE ?

How many perfect matchings are there in a complete graph of 6 vertices?

Consider the translation scheme shown below $$\eqalign{ & S \to TR \cr & R \to + T\left\{ {pr{\mathop{\rm int}} (' + ');} \right\}\,R\,|\,\varepsilon \cr & T \to num\,\left\{ {pr{\...

A 2 km long broadcast LAN has 10 7 bps bandwidth and uses CSMA/CD. The signal travels along the wire at 2 × 10 8 m/s. What is the minimum packet size that can be used on this netwo...

Consider the C program shown below. #include < stdio.h > #define print(x) printf("%d ", x) int x; void Q(int z) { z += x; print(z); } void P(int *y) { int x = *y+2; Q(x); *y = x-1;...

For a pipelined $$CPU$$ with a single $$ALU$$, consider the following situations $$1.\,\,\,\,\,$$ The $$j+1$$ instruction uses the result of the $$j$$-$$th$$ instruction as an oper...

$$A$$ system of equations represented by $$AX=0$$ where $$X$$ is a column vector of unknown and $$A$$ is a square matrix containing coefficients has a non-trival solution when $$A$...

The following program fragment is written in a programming language that allows global variables and does not allow nested declarations of functions. global int i = 100, j = 5; voi...

Assume that the SLR parser for a grammar G has n 1 states and the LALR parser for G has n 2 states. The relationship between n 1 and n 2 is

$$A$$ graph $$G$$ $$=$$ $$(V, E)$$ satisfies $$\left| E \right| \le \,3\left| V \right| - 6.$$ The min-degree of $$G$$ is defined as $$\mathop {\min }\limits_{v \in V} \left\{ {{{\...

$$n$$ couples are invited to a party with the condition that every husband should be accompanied by his wife. However, a wife need not be accompanied by her husband. The number of...

Consider the following SQL query: Select distinct a 1 , a 2 , ..., a n From r 1 , r 2 , ..., r m Where P; For an arbitrary predicate P, this query is equivalent to which of the fol...

Let G=(V,E) be an undirected graph with a subgraph G 1 =(V 1 ,E 1 ). Weights are assigned to edges of G as follows. $$$w(e) = \begin{cases} 0 \text{, if } e \in E_1 \\1 \text{, oth...

Ram and Shyam have been asked to show that a certain problem Π is NP-complete. Ram shows a polynomial time reduction from the 3-SAT problem to Π, and Shyam shows a polynomial time...

In a heap with n elements with the smallest element at the root, the 7 th smallest element can be found in time

Let G = (V, E) be a directed graph with n vertices. A path from v i to v j in G is sequence of vertices (v i , v i +1, ……., v j ) such that (v k , v k +1) ∈ E for all k in i throug...

Consider an array multiplier for multiplying two n bit numbers. If each gate in the circuit has a unit delay, the total delay of the multiplier is

The following program fragment is written in a programming language that allows global variables and does not allow nested declarations of functions. global int i = 100, j = 5; voi...

The usual $$\Theta ({n^2})$$ implementation of Insertion Sort to sort an array uses linear search to identify the position where an element is to be inserted into the already sorte...

Consider the set of relations shown below and the SQL query that follows. Students: (Roll_number, Name, Date_of_birth) Courses: (Course number, Course_name, Instructor) Grades: (Ro...

$$m$$ identical balls are to be placed in $$n$$ distinct bags. You are given that $$m \ge kn$$, where $$k$$ is a natural number $$ \ge 1$$. In how many ways can the balls be placed...

A uni-processor computer system only has two processes, both of which alternate $$10$$ $$ms$$ $$CPU$$ bursts with $$90$$ $$ms$$ $${\rm I}/O$$ bursts. Both the processes were create...

A processor uses $$2$$-level page tables for virtual to physical address translation. Page tables for both levels are stored in the main memory. Virtual and physical addresses are...

The subnet mask for a particular network is 255.255.31.0. Which of the following pairs of IP addresses could belong to this network?

Let $$G$$ be an arbitrary graph with $$n$$ nodes and $$k$$ components. If a vertex is removed from $$G$$, the number of components in the resultant graph must necessarily lie betwe...

A 1- input, 2- output synchronous sequential circuit behaves as follows. Let $${z_k},\,{n_k}$$ denote the number of $$0’s$$ and $$1’s$$ respectively in initial $$k$$ bits of the in...

Suppose we want to synchronize two concurrent processes P and Q using binary semaphores S and T. The code for the processes P and Q is shown below. Process P: while(1){ W: Print '0...

Which of the following assertions is FALSE about the Internet Protocol (IP)?

Let P(E) denote the probability of the event E. Given P(A) = 1, P(B) = $${\raise0.5ex\hbox{$\scriptstyle 1$} \kern-0.1em/\kern-0.15em \lower0.25ex\hbox{$\scriptstyle 2$}}$$, the va...

Consider the following functional dependencies in a database. $$\eqalign{ & \,\,\,\,Date\,\,of\,\,Birth\,\, \to \,\,Age \cr & \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,Ag...

In a bottom-up evaluation of a syntax directed definition, inherited attributes can

Consider the following C function. float f,(float x, int y) { float p, s; int i; for (s=1,p=1,i=1; i < y; i++) { p *= x/i; s+=p; } return s; } For large values of y, the return val...

Assuming all numbers are in $$2's$$ complement representation, which of the following numbers is divisible by $$11111011?$$

Nobody knows yet if $$P=NP$$. Consider the language $$L$$ defined as follows $$L = \left\{ {\matrix{ {{{\left( {0 + 1} \right)}^ * }\,\,\,if\,\,P = NP} \cr {\,\,\,\,\,\,\,\phi \,\,...

Define Languages $${L_0}$$ and $${L_1}$$ as follows $${L_0} = \left\{ { < M,\,w,\,0 > \left| {M\,\,} \right.} \right.$$ halts on $$\left. w \right\}$$ $${L_1} = \left\{ { < M,w,1 >...

The regular expression $${0^ * }\left( {{{10}^ * }} \right){}^ * $$denotes the same set as

Consider the set $$\sum {^ * } $$ of all strings over the alphabet $$\,\sum { = \,\,\,\left\{ {0,\,\,\,1} \right\}.\sum {^ * } } $$ with the concatenation operator for strings

If the strings of a language $$L$$ can be effectively enumerated in lexicographic (i.e., alphabetic$$(c)$$ order, which of the following statements is true?

Consider the following three claims I. (n + k) m = $$\Theta \,({n^m})$$ where k and m are constants II. 2 n+1 = O(2 n ) III. 2 2n = O(2 2n ) Which of those claims are correct?

The cube root of a natural number n is defined as the largest natural number m such that $${m^3} \le n$$. The complexity of computing the cube root of n (n is represented in binary...