Recent questions tagged gate2006
Register

Recent questions tagged gate2006

Recent questions tagged gate2006
0 votes
0 answers 34 views
GATE2006-51, ISRO2016-34 Video Solution
Consider the following recurrence: $ T(n)=2T\left ( \sqrt{n}\right )+1,$ $T(1)=1$ Which one of the following is true? $ T(n)=\Theta (\log\log n)$ $ T(n)=\Theta (\log n)$ $ T(n)=\Theta (\sqrt{n})$ $ T(n)=\Theta (n)$
admin asked in Algorithms Apr 18, 2020
by admin
585 points
34 views
0 votes
0 answers 21 views
GATE2006-74 Video Solution
Consider two cache organizations. First one is $32 \hspace{0.2cm} KB$ $2-way$ set associative with $32 \hspace{0.2cm} byte$ block size, the second is of same size but direct mapped. The size of an address is $32 \hspace{0.2cm} bits$ in both cases . A $2-to-1$ multiplexer has ... value of $h_1$ is: $2.4 \text{ ns} $ $2.3 \text{ ns}$ $1.8 \text{ ns}$ $1.7 \text{ ns}$
admin asked in CO & Architecture Apr 18, 2020
by admin
585 points
21 views
0 votes
0 answers 21 views
GATE2006-62, ISRO2016-50 Video Solution
A CPU generates $32$-bit virtual addresses. The page size is $4$ KB. The processor has a translation look-aside buffer (TLB) which can hold a total of $128$ page table entries and is $4$-way set associative. The minimum size of the TLB tag is: $\text{11 bits}$ $\text{13 bits}$ $\text{15 bits}$ $\text{20 bits}$
admin asked in Operating System Apr 18, 2020
by admin
585 points
21 views
0 votes
0 answers 18 views
GATE2006-61 Video Solution
The atomic fetch-and-set $x, y$ instruction unconditionally sets the memory location $x$ to $1$ and fetches the old value of $x$ in $y$ without allowing any intervening access to the memory location $x$ ... a pair of normal load/store can be used The implementation of $V$ is wrong The code does not implement a binary semaphore
admin asked in Operating System Apr 18, 2020
by admin
585 points
18 views
0 votes
0 answers 25 views
GATE2006-32, ISRO2016-35 Video Solution
Consider the following statements about the context free grammar $G = \left \{ S \rightarrow SS, S \rightarrow ab, S \rightarrow ba, S \rightarrow \epsilon \right \} $ $G$ is ambiguous $G$ produces all strings with equal number of $a$'s ... combination below expresses all the true statements about $G$? I only I and III only II and III only I, II and III
admin asked in Compiler Design Apr 18, 2020
by admin
585 points
25 views
0 votes
0 answers 14 views
GATE2006-82 Video Solution
Consider the diagram shown below where a number of LANs are connected by (transparent) bridges. In order to avoid packets looping through circuits in the graph, the bridges organize themselves in a spanning tree. First, the root bridge is identified as the bridge with the least serial number. ... $\text{B1, B5, B2, B3, B4}$ $\text{B1, B3, B4, B5, B2}$
admin asked in Computer Networks Apr 18, 2020
by admin
585 points
14 views
0 votes
0 answers 26 views
GATE2006-38 Video Solution
Consider a Boolean function $ f(w,x,y,z)$. Suppose that exactly one of its inputs is allowed to change at a time. If the function happens to be true for two input vectors $ i_{1}=\left \langle w_{1}, x_{1}, y_{1},z_{1}\right \rangle $ ... $ wx\overline{y} \overline{z}, xz, w\overline{x}yz$ $ wx\overline{y}, wyz, wxz, \overline{w}xz, x\overline{y}z, xyz$
admin asked in Digital Logic Apr 18, 2020
by admin
585 points
26 views
0 votes
0 answers 20 views
GATE2006-12 Video Solution
To implement Dijkstra’s shortest path algorithm on unweighted graphs so that it runs in linear time, the data structure to be used is: Queue Stack Heap B-Tree
admin asked in Algorithms Apr 18, 2020
by admin
585 points
20 views
0 votes
0 answers 19 views
GATE2006-34 Video Solution
Consider the regular language $L=(111+11111)^{*}.$ The minimum number of states in any DFA accepting this languages is: $3$ $5$ $8$ $9$
admin asked in Theory of Computation Apr 18, 2020
by admin
585 points
19 views
0 votes
0 answers 30 views
GATE2006-63, UGCNET-June2012-III-45 Video Solution
admin asked in Operating System Apr 18, 2020
by admin
585 points
30 views
0 votes
0 answers 38 views
GATE2006-49 Video Solution
An implementation of a queue $Q$, using two stacks $S1$ and $S2$, is given below: void insert (Q, x) { push (S1, x); } void delete (Q) { if (stack-empty(S2)) then if (stack-empty(S1)) then { print( Q is empty ); return; } else while (!(stack-empty(S1))){ x=pop( ... and $2m\leq y\leq 2n $ $ 2m\leq x<2n $ and $2m\leq y\leq n+m $ $ 2m\leq x<2n $ and $2m\leq y\leq 2n $
admin asked in DS Apr 18, 2020
by admin
585 points
38 views
0 votes
0 answers 19 views
GATE2006-67 Video Solution
Consider the relation account (customer, balance) where the customer is a primary key and there are no null values. We would like to rank customers according to decreasing balance. The customer with the largest balance gets rank 1. Ties are not broke but ranks are skipped ... ranks using ODBC. Which two of the above statements are correct? 2 and 5 1 and 3 1 and 4 3 and 5
admin asked in Databases Apr 18, 2020
by admin
585 points
19 views
0 votes
0 answers 12 views
GATE2006-39 Video Solution
We consider the addition of two $2's$ complement numbers $ b_{n-1}b_{n-2}\dots b_{0}$ and $a_{n-1}a_{n-2}\dots a_{0}$. A binary adder for adding unsigned binary numbers is used to add the two numbers. The sum is denoted by $ c_{n-1}c_{n-2}\dots c_{0}$ and the carry-out ... $ c_{out}\oplus c_{n-1}$ $ a_{n-1}\oplus b_{n-1}\oplus c_{n-1}$
admin asked in Digital Logic Apr 18, 2020
by admin
585 points
12 views
0 votes
0 answers 59 views
GATE2006-42 Video Solution
A CPU has a five-stage pipeline and runs at $1$ GHz frequency. Instruction fetch happens in the first stage of the pipeline. A conditional branch instruction computes the target address and evaluates the condition in the third stage of the pipeline. The processor stops fetching new ... is: $\text{1.0 second}$ $\text{1.2 seconds}$ $\text{1.4 seconds}$ $\text{1.6 seconds}$
admin asked in CO & Architecture Apr 18, 2020
by admin
585 points
59 views
0 votes
0 answers 150 views
GATE2006-8 Video Solution
You are given a free running clock with a duty cycle of $50\%$ and a digital waveform $f$ which changes only at the negative edge of the clock. Which one of the following circuits (using clocked D flip-flops) will delay the phase of $f$ by $180°$?
admin asked in Digital Logic Apr 18, 2020
by admin
585 points
150 views
0 votes
0 answers 29 views
GATE2006-78 Video Solution
Barrier is a synchronization construct where a set of processes synchronizes globally i.e., each process in the set arrives at the barrier and waits for all others to arrive and then all processes leave the barrier. Let the number of processes ... need not be inside a critical section The barrier implementation is correct if there are only two processes instead of three.
admin asked in Operating System Apr 18, 2020
by admin
585 points
29 views
0 votes
0 answers 25 views
GATE2006-54 Video Solution
Given two arrays of numbers $a_{1},...,a_{n}$ and $b_{1},...,b_{n}$ where each number is $0$ or $1$, the fastest algorithm to find the largest span $(i, j)$ such that $ a_{i}+a_{i+1}+\dots+a_{j}=b_{i}+b_{i+1}+\dots+b_{j}$ or ... time in the key comparison mode Takes $\Theta (n)$ time and space Takes $O(\sqrt n)$ time only if the sum of the $2n$ elements is an even number
admin asked in Algorithms Apr 18, 2020
by admin
585 points
25 views
0 votes
0 answers 27 views
GATE2006-52 Video Solution
The median of $n$ elements can be found in $O(n)$ time. Which one of the following is correct about the complexity of quick sort, in which median is selected as pivot? $\Theta (n)$ $\Theta (n \log n)$ $\Theta (n^{2})$ $\Theta (n^{3})$
admin asked in Algorithms Apr 18, 2020
by admin
585 points
27 views
0 votes
0 answers 20 views
GATE2006-14, ISRO2011-14 Video Solution
Which one of the following in place sorting algorithms needs the minimum number of swaps? Quick sort Insertion sort Selection sort Heap sort
admin asked in Algorithms Apr 18, 2020
by admin
585 points
20 views
0 votes
0 answers 20 views
GATE2006-40 Video Solution
Consider numbers represented in 4-bit Gray code. Let $ h_{3}h_{2}h_{1}h_{0}$ be the Gray code representation of a number $n$ and let $ g_{3}g_{2}g_{1}g_{0}$ be the Gray code of $ (n+1)(modulo 16)$ ... $ g_{3}(h_{3}h_{2}h_{1}h_{0})=\sum (0,1,6,7,10,11,12,13) $
admin asked in Digital Logic Apr 18, 2020
by admin
585 points
20 views
0 votes
0 answers 18 views
GATE2006-29 Video Solution
If $s$ is a string over $(0+1)^*$ then let $n_0(s)$ denote the number of $0$'s in $s$ and $n_1(s)$ the number of $1$'s in $s$. Which one of the following languages is not regular? $L=\left \{ s\in (0+1)^* \mid n_{0}(s) \text{ is a 3-digit prime } \right \}$ ... $L=\left \{ s\in (0+1)^*\mid n_{0}(s) \mod 7=n_{1}(s) \mod 5=0 \right \}$
admin asked in Theory of Computation Apr 18, 2020
by admin
585 points
18 views
0 votes
0 answers 12 views
GATE2006-48 Video Solution
Let $T$ be a depth first search tree in an undirected graph $G$. Vertices $u$ and $ν$ are leaves of this tree $T$. The degrees of both $u$ and $ν$ in $G$ are at least $2$ ... exist a cycle in $G$ containing $u$ and $ν$ There must exist a cycle in $G$ containing $u$ and all its neighbours in $G$
admin asked in Algorithms Apr 18, 2020
by admin
585 points
12 views
0 votes
0 answers 22 views
GATE2006-65 Video Solution
Consider three processes, all arriving at time zero, with total execution time of $10$, $20$ and $30$ units, respectively. Each process spends the first $\text{20%}$ of execution time doing I/O, the next $\text{70%}$ ... percentage of time does the CPU remain idle? $\text{0%}$ $\text{10.6%}$ $\text{30.0%}$ $\text{89.4%}$
admin asked in Operating System Apr 18, 2020
by admin
585 points
22 views
0 votes
0 answers 25 views
GATE2006-66 Video Solution
Consider the following snapshot of a system running $n$ processes. Process $i$ is holding $x_i$ instances of a resource $R$, $ 1\leq i\leq n$ . Currently, all instances of $R$ are occupied. Further, for all $i$, process $i$ has placed a request for an additional $y_i$ instances while ... $ \max(x_{p},x_{q})>1$ $ \min(x_{p},x_{q})>1$
admin asked in Operating System Apr 18, 2020
by admin
585 points
25 views
0 votes
0 answers 23 views
GATE2006-15 Video Solution
Consider the following C-program fragment in which $i$, $j$ and $n$ are integer variables. for( i = n, j = 0; i > 0; i /= 2, j +=i ); Let $val(j)$ denote the value stored in the variable $j$ after termination of the for loop. Which one of the following is true? $val(j)=\Theta(\log n)$ $val(j)=\Theta (\sqrt{n})$ $val(j)=\Theta( n)$ $val(j)=\Theta (n\log n)$
admin asked in Algorithms Apr 18, 2020
by admin
585 points
23 views
0 votes
0 answers 25 views
GATE2006-71 Video Solution
The $2^n$ vertices of a graph $G$ corresponds to all subsets of a set of size $n$, for $n \geq 6$. Two vertices of $G$ are adjacent if and only if the corresponding sets intersect in exactly two elements. The number of vertices of degree zero in $G$ is: $1$ $n$ $n + 1$ $2^n$
admin asked in Graph Theory Apr 18, 2020
by admin
585 points
25 views
0 votes
0 answers 19 views
GATE2006-57 Video Solution
Consider this C code to swap two integers and these five statements: the code void swap (int *px, int *py) { *px = *px - *py; *py = *px + *py; *px = *py - *px; } S1: will generate a compilation error S2: may generate a ... procedure correctly for some but not all valid input pointers S5: may add or subtract integers and pointers S1 S2 and S3 S2 and S4 S2 and S5
admin asked in Programming Apr 18, 2020
by admin
585 points
19 views
0 votes
0 answers 26 views
GATE2006-41 Video Solution
A CPU has a cache with block size 64 bytes. The main memory has $k$ banks, each bank being $c$ bytes wide. Consecutive $c$ − byte chunks are mapped on consecutive banks with wrap-around. All the $k$ banks can be accessed in parallel, but two ... , the latency of retrieving a cache block starting at address zero from main memory is: 92 ns 104 ns 172 ns 184 ns
admin asked in CO & Architecture Apr 18, 2020
by admin
585 points
26 views
0 votes
0 answers 23 views
GATE2006-36 Video Solution
Given two three bit numbers $a_{2}a_{1}a_{0}$ and $b_{2}b_{1}b_{0}$ and $c$ ...
admin asked in Digital Logic Apr 18, 2020
by admin
585 points
23 views
0 votes
0 answers 18 views
GATE2006-72 Video Solution
The $2^n$ vertices of a graph $G$ corresponds to all subsets of a set of size $n$, for $n \geq 6$. Two vertices of $G$ are adjacent if and only if the corresponding sets intersect in exactly two elements. The maximum degree of a vertex in $G$ is: $\binom{\frac{n}{2}}{2}.2^{\frac{n}{2}}$ $2^{n-2}$ $2^{n-3}\times 3$ $2^{n-1}$
admin asked in Graph Theory Apr 18, 2020
by admin
585 points
18 views
0 votes
0 answers 12 views
GATE2006-80 Video Solution
A CPU has a $32 KB$ direct mapped cache with $128$ byte-block size. Suppose A is two dimensional array of size $512 \times512$ with elements that occupy $8$-bytes each. Consider the following two C code segments, $P1$ and $P2$. P1: for (i=0; i<512; i++) { for (j=0; ... by $P1$ be $M_{1}$and that for $P2$ be $M_{2}$. The value of $M_{1}$ is: $0$ $2048$ $16384$ $262144$
admin asked in CO & Architecture Apr 18, 2020
by admin
585 points
12 views
0 votes
0 answers 23 views
GATE2006-09, ISRO2009-35 Video Solution
A CPU has $24$-$bit$ instructions. A program starts at address $300$ (in decimal). Which one of the following is a legal program counter (all values in decimal)? $400$ $500$ $600$ $700$
admin asked in CO & Architecture Apr 18, 2020
by admin
585 points
23 views
0 votes
0 answers 23 views
GATE2006-06, ISRO2009-14 Video Solution
Consider three CPU-intensive processes, which require $10$, $20$ and $30$ time units and arrive at times $0$, $2$ and $6$, respectively. How many context switches are needed if the operating system implements a shortest remaining time first scheduling algorithm? Do not count the context switches at time zero and at the end. $1$ $2$ $3$ $4$
admin asked in Operating System Apr 18, 2020
by admin
585 points
23 views
0 votes
0 answers 22 views
GATE2006-53 Video Solution
Consider the following C-function in which $a[n]$ and $b[m]$ are two sorted integer arrays and $c[n+m]$ be another integer array, void xyz(int a[], int b [], int c []){ int i,j,k; i=j=k=0; while ((i<n) && (j<m)) if (a[i] < b[j]) c[k++] = a[ ... $b[m-1]\leq a[i]$ if $j=m$ only (i) only (ii) either (i) or (ii) but not both neither (i) nor (ii)
admin asked in Algorithms Apr 18, 2020
by admin
585 points
22 views
0 votes
0 answers 23 views
GATE2006-13 Video Solution
A scheme for storing binary trees in an array $X$ is as follows. Indexing of $X$ starts at $1$ instead of $0$. the root is stored at $X[1]$. For a node stored at $X[i]$, the left child, if any, is stored in $X[2i]$ and the right child, if any, in $X[2i+1]$. To be able to store any binary tree on n vertices the minimum size of $X$ should be $\log_2 n$ $n$ $2n+1$ $2^n-1$
admin asked in DS Apr 18, 2020
by admin
585 points
23 views
0 votes
0 answers 20 views
GATE2006-17 Video Solution
An element in an array $X$ is called a leader if it is greater than all elements to the right of it in $X$. The best algorithm to find all leaders in an array solves it in linear time using a left to right pass of the array solves it in linear time using ... pass of the array solves it using divide and conquer in time $\Theta (n\log n)$ solves it in time $\Theta( n^2)$
admin asked in Algorithms Apr 18, 2020
by admin
585 points
20 views
Page:
Ask a Question
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
Developed by Chun