GATE 1995 CSE & IT
40 questions across 1 session
Merge sort uses
In some programming languages, an identifier is permitted to be a letter following by any number of letters or digits. If L and D denote the sets of letters and digits respectively...
In a vectored interrupt
If the proposition $$\neg p \Rightarrow q$$ is true, then the truth value of the proposition $$\neg p \vee \left( {p \Rightarrow q} \right)$$ where $$'\neg '$$ is negation, $$' \ve...
The head of a moving head disk with $$100$$ tracks numbered $$0$$ to $$99$$ is currently serving a request at tract $$55.$$ If the queue of requests kept in $$FIFO$$ order is $$10,...
A linker is given object modules for a set of programs that were compiled separately. What information need to be included in an object module?
A computer installation has 1000K of main memory. The jobs arrive and finish in the following sequence. Job 1 requiring 200k arrives Job 2 requiring 350k arrives Job 3 requiring 30...
What are x and y in the following macro definition? macro Add x,y Load y Mul x Store y end macro
The probability that a number selected at random between $$100$$ and $$999$$ (both inclusive ) will not contain the digit $$7$$ is
The rank of the following (n + 1) x (n + 1) matrix, where a is a real number is $$$\left[ {\matrix{ 1 & a & {{a^2}} & . & . & . & {{a^n}} \cr 1 & a & {{a^2}} & . & . & . & {{a^n}}...
The rank of the following (n + 1) x (n + 1) matrix, where a is a real number is $$$\left[ {\matrix{ 1 & a & {{a^2}} & . & . & . & {{a^n}} \cr 1 & a & {{a^2}} & . & . & . & {{a^n}}...
A binary tree T has n leaf nodes. The number of nodes of degree 2 in T is:
Which of the following strings can definitely be said to be tokens without looking at the next input character while compiling a Pascal program? I. begin II. program III. <>
Let $$R$$ be a symmetric and transitive relation on a set $$A$$. Then
The capacity of a memory unit is defined by the number of words multiplied by the number of bits/word. How many separate address and data lines are needed for a memory of $$4K$$ $$...
(a) Consider the relation scheme $$R(A, B, C)$$ with the following functional dependencies: $$\eqalign{ & A,B \to C \cr & \,\,\,\,\,\,C \to A \cr} $$ Show that the scheme $$R$$ is...
If the disk in (a) is rotating at $$3600$$ rpm, determine the effective data transfer rate which is defined as the number of bytes transferred per second between disk and memory.
If at every point of a certain curve, the slope of the tangent equals $${{ - 2x} \over y}$$ the curve is
Let A be the set of all nonsingular matrices over real numbers and let * be the matrix multiplication operator. Then
Which of the following statements is true? I. As the number of entries in a hash table increases, the number of collisions increases. II. Recursive programs are efficient III. The...
For merging two sorted lists of sizes m and n into a sorted list of size m+n, we require comparisons of
A $$ROM$$ is used to store a truth table for a binary multiplier unit that will multiply two $$4$$ bit numbers. The size of the $$ROM$$ (number of words $$ \times $$ number of bits...
The number of elements in the power set $$P(S)$$ of the set $$S = \left\{ {\left\{ \phi \right\},1,\left\{ {2,3} \right\}} \right\}$$ is
The principle of locality justifies the use of
$$\mathop {Lim}\limits_{x \to \infty } {{{x^3} - \cos x} \over {{x^2} + {{\left( {\sin x} \right)}^2}}} = \_\_\_\_\_\_.$$
The address sequence generated by tracing a particular program executing in a pure demand paging system with $$100$$ records per page with $$1$$ free main memory frame is recorded...
A bag contains 10 white balls and 15 black balls. Two balls drawn in succession. The probability that one of them is black the other is white is
Let $${G_1}$$ and $${G_2}$$ be subgroups of a group $$G$$. (a) Show that $${G_1}\, \cap \,{G_2}$$ is also a subgroup of $$G$$. (b) $${\rm I}$$s $${G_1}\, \cup \,{G_2}$$ always a su...
A linker is given object modules for a set of programs that were compiled separately. What information need to be included in an object module?
Which scheduling policy is most suitable for a time-shared operating systems?
What is the value of X printed by the following program? program COMPUTE (input, output); var X:integer; procedure FIND (X:real); begin X:=sqrt(X); end; begin X:=2 Find(X) Writeln(...
The capacity of a memory unit is defined by the number of words multiplied by the number of bits/word. How many separate address and data lines are needed for a memory of $$4K\,\,...
In a paged segmented scheme of memory management, the segment table itself must have a page table because:
A computer system has a $$4K$$ word cache organized in block set associative manner with $$4$$ blocks per set, $$64$$ words per block. The number of bits in the $$SET$$ and $$WORD$...
In a virtual memory system the address space specified by the address lines of the $$CPU$$ must be __________ than the physical memory size and _______ than the secondary storage s...
Prove that in a finite graph, the number of vertices of odd degree is always even.
If the overhead for formatting a disk is $$96$$ bytes for $$40000$$ bytes sector, Compute the unformatted capacity of the disk of the following parameters: Number of surface: $$8$$...
A shift reduce parser carries out the actions specified within braces immediately after reducing with the corresponding rule of grammar. $$\eqalign{ & S \to xxW\,\left\{ {pr{\matho...
Consider the grammar with the following productions. $$S \to a\,\alpha \,\,b\left| {\,\,b\,\alpha } \right.\,c\,\left| {aB} \right.$$ $$S \to \alpha S\,\left| b \right.$$ $$S \to \...
Which of the following definitions below generates the same language as $$L$$ Where $$L = {\left\{ x \right.^n}{y^n}\left| {n \ge \left. 1 \right\}} \right.$$ i) $$\,\,E \to xEy\le...