GATE CSE 2007 PYQ
| Q1➡ | Engineering Mathematics Consider the following two statements about the function f(x)=|x| P. f(x) is continuous for all real values of x Q. f(x) is differentiable for all real values of x Which of the following is TRUE? |
| i ➥ P is true and Q is false. |
| ii ➥ P is false and Q is true. |
| iii ➥ Both P and Q are true. |
| iv ➥ Both P and Q are false. |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Calculus | Help-Line |
| Q2➡ | Engineering Mathematics Let S be a set of n elements. The number of ordered pairs in the largest and the smallest equivalence relations on S are: |
| i ➥ n and n |
| ii ➥ n2 and n |
| iii ➥ n2 and 0 |
| iv ➥ n and 1 |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Sets and relation | Help-Line |
| Q3➡ | Digital Logic Design What is the maximum number of different Boolean functions involving n Boolean variables? |
| i ➥ n2 |
| ii ➥ 2n |
| iii ➥ 22n |
| iv ➥ 2n2 |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Boolean algebra | Help-Line |
| Q4➡ | Engineering Mathematics Let G be the non-planar graph with the minimum possible number of edges. Then G has |
| i ➥ 9 edges and 5 vertices |
| ii ➥ 9 edges and 6 vertices |
| iii ➥ 10 edges and 5 vertices |
| iv ➥ 10 edges and 6 vertices |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Graph theory | Help-Line |
| Q5➡ | Data Structures Consider the DAG with Consider V = {1, 2, 3, 4, 5, 6}, shown below.  Which of the following is NOT a topological ordering? |
| i ➥ 1 2 3 4 5 6 |
| ii ➥ 1 3 2 4 5 6 |
| iii ➥ 1 3 2 4 6 5 |
| iv ➥ 3 2 4 1 6 5 |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Graphs | Help-Line |
| Q6➡ | Theory of computation Which of the following problems is undecidable? |
| i ➥ Membership problem for CFGs. |
| ii ➥ Ambiguity problem for CFGs. |
| iii ➥ Finiteness problem for FSAs. |
| iv ➥ Equivalence problem for FSAs. |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Learn Topic Wise | Help-Line |
| Q7➡ | Theory of computation Which of the following is TRUE? |
| i ➥ Every subset of a regular set is regular. |
| ii ➥ Every finite subset of a non-regular set is regular. |
| iii ➥ The union of two non-regular sets is not regular. |
| iv ➥ Infinite union of finite sets is regular. |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Regular language | Help-Line |
| Q8➡ | Digital Logic design How many 3-to-8 line decoders with an enable input are needed to construct a 6-to-64 line decoder without using any other logic gates? |
| i ➥ 7 |
| ii ➥ 8 |
| iii ➥ 9 |
| iv ➥ 10 |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Decoder | Help-Line |
| Q9➡ | Digital Logic design Consider the following Boolean function of four variables: f(w,x,y,z) = ∑(1,3,4,6,9,11,12,14) The function is: |
| i ➥ independent of one variable. |
| ii ➥ independent of two variables. |
| iii ➥ independent of three variables. |
| iv ➥ dependent on all the variables. |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Boolean variables | Help-Line |
| Q10➡ | Computer architecture Consider a 4-way set associative cache consisting of 128 lines with a line size of 64 words. The CPU generates a 20-bit address of a word in main memory. The number of bits in the TAG, LINE and WORD fields are respectively: |
| i ➥ 9, 6, 5 |
| ii ➥ 7, 7, 6 |
| iii ➥ 7, 5, 8 |
| iv ➥ 9, 5, 6 |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Cache | Help-Line |
| Q11➡ | Computer architecture Consider a disk pack with 16 surfaces, 128 tracks per surface and 256 sectors per track. 512 bytes of data are stored in a bit serial manner in a sector. The capacity of the disk pack and the number of bits required to specify a particular sector in the disk are respectively: |
| i ➥ 256 Mbyte, 19 bits |
| ii ➥ 256 Mbyte, 28 bits |
| iii ➥ 512 Mbyte, 20 bits |
| iv ➥ 64 Gbyte, 28 bit |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Secondary storage | Help-Line |
| Q12➡ | Data Structures The height of a binary tree is the maximum number of edges in any root to leaf path. The maximum number of nodes in a binary tree of height h is: |
| i ➥ 2h−1 |
| ii ➥ 2h−1 – 1 |
| iii ➥ 2h+1 – 1 |
| iv ➥ 2h+1 |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Binary trees | Help-Line |
| Q13➡ | Data Structures The maximum number of binary trees that can be formed with three unlabeled nodes is: |
| i ➥ 1 |
| ii ➥ 5 |
| iii ➥ 4 |
| iv ➥ 3 |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Binary trees | Help-Line |
| Q14➡ | Algorithms Which of the following sorting algorithms has the lowest worst-case complexity? |
| i ➥ Merge sort |
| ii ➥ Bubble sort |
| iii ➥ Quick sort |
| iv ➥ Selection sort |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Time complexity | Help-Line |
| Q15➡ | Algorithms Consider the following segment of C-code: int j, n; j = 1; while (j <= n) j = j*2; The number of comparisons made in the execution of the loop for any n > 0 is: Base of Log is 2 in all options. |
| i ➥ ⌈log2n⌉ + 1 |
| ii ➥ n |
| iii ➥ ⌈log2n⌉ |
| iv ➥ ⌊log2n⌋+1 |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Time complexity | Help-Line |
| Q16➡ | Operating systems Group 1 contains some CPU scheduling algorithms and Group 2 contains some applications. Match entries in Group 1 to entries in Group 2. Group I Group II (P) Gang Scheduling (1) Guaranteed Scheduling (Q) Rate Monotonic Scheduling (2) Real-time Scheduling (R) Fair Share Scheduling (3) Thread Scheduling |
| i ➥ P – 3 Q – 2 R – 1 |
| ii ➥ P – 1 Q – 2 R – 3 |
| iii ➥ P – 2 Q – 3 R – 1 |
| iv ➥ P – 1 Q – 3 R – 2 |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Match the following | Help-Line |
| Q17➡ | Operating systems Consider the following statements about user level threads and kernel level threads. Which one of the following statements is FALSE? |
| i ➥ Context switch time is longer for kernel level threads than for user level threads. |
| ii ➥ User level threads do not need any hardware support. |
| iii ➥ Related kernel level threads can be scheduled on different processors in a multi-processor system. |
| iv ➥ Blocking one kernel level thread blocks all related threads. |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Threads | Help-Line |
| Q18➡ | Compiler design Which one of the following is a top-down parser? |
| i ➥ Recursive descent parser. |
| ii ➥ Operator precedence parser. |
| iii ➥ An LR(k) parser. |
| iv ➥ An LALR(k) parser. |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Parsers | Help-Line |
| Q19➡ | Computer network In Ethernet when Manchester encoding is used, the bit rate is: |
| i ➥ Half the baud rate. |
| ii ➥ Twice the baud rate. |
| iii ➥ Same as the baud rate. |
| iv ➥ Same as the baud rate. |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Ethernet | Help-Line |
| Q20➡ | Computer network Which one of the following uses UDP as the transport protocol? |
| i ➥ HTTP |
| ii ➥ Telnet |
| iii ➥ DNS |
| iv ➥ SMTP |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Transport layer protocol | Help-Line |
| Q21➡ | Engineering Mathematics How many different non-isomorphic Abelian groups of order 4 are there? |
| i ➥ 2 |
| ii ➥ 3 |
| iii ➥ 4 |
| iv ➥ 5 |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Sets and relation | Help-Line |
| Q22➡ | Engineering Mathematics Let Graph(x) be a predicate which denotes that x is a graph. Let Connected(x) be a predicate which denotes that x is connected. Which of the following first order logic sentences DOES NOT represent the statement: “Not every graph is connected”? |
| i ➥ ¬∀x (Graph (x) ⇒ Connected (x)) |
| ii ➥ ¬∃x (Graph (x) ∧ ¬Connected (x)) |
| iii ➥ ¬∀x (¬Graph (x) ∨ Connected (x)) |
| iv ➥ ∀x (Graph (x) ⇒ ¬Connected (x)) |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Propositional logic | Help-Line |
| Q23➡ | Engineering Mathematics Which of the following graphs has an Eulerian circuit? |
| i ➥ Any k-regular graph where k is an even number. |
| ii ➥ A complete graph on 90 vertices. |
| iii ➥ The complement of a cycle on 25 vertices. |
| iv ➥ None of the above. |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Graph theory | Help-Line |
| Q24➡ | Engineering Mathematics Suppose we uniformly and randomly select a permutation from the 20! Permutations of 1, 2, 3,….., 20. What is the probability that 2 appears at an earlier position than any other even number in the selected permutation? |
| i ➥ 1/2 |
| ii ➥ 1/10 |
| iii ➥ 9!/20! |
| iv ➥ None of these |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Probability | Help-Line |
| Q25➡ | Engineering Mathematics Let A be a 4 x 4 matrix with eigenvalues -5, -2, 1, 4. Which of the following is an eigenvalue of [A I] [I A] where I is the 4 x 4 identity matrix? |
| i ➥ -5 |
| ii ➥ -7 |
| iii ➥ 2 |
| iv ➥ 1 |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Linear algebra | Help-Line |
| Q26➡ | Engineering Mathematics Consider the set S = {a,b,c,d}. Consider the following 4 partitions π1, π2, π3, π4 on S : π1 Let p be the partial order on set of partitions S’ = {π1, π2, π3, π4} defined as follows: πi p πj if and only if πi refines πj. The poset diagram for (S’,p) is: |
i ➥  |
ii ➥  |
iii ➥  |
iv ➥  |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Sets and relation | Help-Line |
| Q27➡ | Engineering Mathematics Consider the set of (column) vectors defined bu |
| i ➥ {[1,-1,0]T, [1,0,-1]T} is a basis for the subspace X. |
| ii ➥ {[1,-1,0]T, [1,0,-1]T} is a linearly independent set, but it does not span X and therefore is not a basis of X. |
| iii ➥ X is not a subspace of R3 |
| iv ➥ None of the above |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Linear algebra | Help-Line |
| Q28➡ | Engineering Mathematics Consider the series obtained from the Newton Raphson method. The series converges to |
| i ➥ 1.5 |
| ii ➥ √2 |
| iii ➥ 1.6 |
| iv ➥ 1.4 |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Newton raphson method | Help-Line |
| Q29➡ | Theory of computation A minimum state deterministic finite automaton accepting the language L={w | w ε {0,1} *, number of 0s and 1s in w are divisible by 3 and 5, respectively} has |
| i ➥ 15 states |
| ii ➥ 11 states |
| iii ➥ 10 states |
| iv ➥ 9 states |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Finite automata | Help-Line |
| Q30➡ | Theory of computation The language L = {0i21i | i≥0} over the alphabet {0,1, 2} is: |
| i ➥ not recursive. |
| ii ➥ is recursive and is a deterministic CFL. |
| iii ➥ is a regular language. |
| iv ➥ is not a deterministic CFL but a CFL. |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Identity class language | Help-Line |
| Q31➡ | Theory of computation Which of the following languages is regular? |
| i ➥ {wwR|w ∈ {0,1}+} |
| ii ➥ {wwRx|x, w ∈ {0,1}+} |
| iii ➥ {wxwR|x, w ∈ {0,1}+} |
| iv ➥ {xwwR|x, w ∈ {0,1}+} |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Regular language | Help-Line |
| Q32➡ | Digital Logic design Let f(w, x, y, z) = ∑(0, 4, 5, 7, 8, 9, 13, 15). Which of the following expressions are NOT equivalent to f? P x’y’z’ + w’xy’ + wy’z + xz Q w’y’z’ + wx’y’ + xz w’y’z’ + wx’y’ + xyz + xy’z x’y’z’ + wx’y’ + w’y |
| i ➥ P only |
| ii ➥ Q and S |
| iii ➥ R and S |
| iv ➥ S only |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Boolean expressions | Help-Line |
| Q33➡ | Digital Logic design Define the connective * for the Boolean variables X and Y as: X * Y = XY + X’ Y’. Let Z = X * Y. Consider the following expressions P, Q and R. P: X = Y⋆Z Q: Y = X⋆Z R: X⋆Y⋆Z=1 Which of the following is TRUE? |
| i ➥ Only P and Q are valid. |
| ii ➥ Only Q and R are valid. |
| iii ➥ Only P and R are valid. |
| iv ➥ All P, Q, R are valid |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Boolean expressions | Help-Line |
| Q34➡ | Digital Logic design Suppose only one multiplexer and one inverter are allowed to be used to implement any Boolean function of n variables. What is the minimum size of the multiplexer needed? |
| i ➥ 2n line to 1 line |
| ii ➥ 2n+1 line to 1 line |
| iii ➥ 2n-1 line to 1 line |
| iv ➥ 2n-2 line to 1 line |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Multiplexer | Help-Line |
| Q35➡ | Digital Logic design In a look-ahead carry generator, the carry generate function Gi and the carry propagate function Pi for inputs Ai and Bi are given by: Pi = Ai ⨁ Bi and Gi = AiBi The expressions for the sum bit Si and the carry bit Ci+1 of the look-ahead carry adder are given by: Si = Pi ⨁ Ci and Ci+1 = Gi + PiCi , where C0 is the input carry. Consider a two-level logic implementation of the look-ahead carry generator. Assume that all Pi and Gi are available for the carry generator circuit and that the AND and OR gates can have any number of inputs. The number of AND gates and OR gates needed to implement the look-ahead carry generator for a 4-bit adder with S3, S2, S1, S0 and C4 as its outputs are respectively: |
| i ➥ 6, 3 |
| ii ➥ 10, 4 |
| iii ➥ 6, 4 |
| iv ➥ 10, 5 |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Carry look ahead adder | Help-Line |
| Q36➡ | Digital Logic design Assume that the counter and gate delays are negligible. If the counter starts at 0, then it cycles through the following sequence: The control signal functions of a 4-bit binary counter are given below (where X is “don’t care”)  The counter is connected as follows:  |
| i ➥ 0, 3, 4 |
| ii ➥ 0, 3, 4, 5 |
| iii ➥ 0, 1, 2, 3, 4 |
| iv ➥ 0, 1, 2, 3, 4, 5 |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Circuits output | Help-Line |
| Q37➡ | Computer architecture Consider a pipelined processor with the following four stages: IF: Instruction Fetch ID: Instruction Decode and Operand Fetch EX: Execute WB: Write Back The IF, ID and WB stages take one clock cycle each to complete the operation. The number of clock cycles for the EX stage dependson the instruction. The ADD and SUB instructions need 1 clock cycle and the MUL instruction needs 3 clock cycles in the EX stage. Operand forwarding is used in the pipelined processor. What is the number of clock cycles taken to complete the following sequence of instructions? ADD R2, R1, R0 R2 <- R0 + R1 MUL R4, R3, R2 R4 <- R3 * R2 SUB R6, R5, R4 R6 <- R5 – R4 |
| i ➥ 7 |
| ii ➥ 8 |
| iii ➥ 10 |
| iv ➥ 14 |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Pipelining | Help-Line |
| Q38➡ | Data Structures The following postfix expression with single digit operands is evaluated using a stack: 8 2 3 ^ / 2 3 * + 5 1 * – Note that ^ is the exponentiation operator. The top two elements of the stack after the first * is evaluated are: |
| i ➥ 6, 1 |
| ii ➥ 5, 7 |
| iii ➥ 3, 2 |
| iv ➥ 1, 5 |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Stacks | Help-Line |
| Q39➡ | Data Structures The inorder and preorder traversal of a binary tree are d b e a f c g and a b d e c f g, respectively. The postorder traversal of the binary tree is: |
| i ➥ d e b f g c a |
| ii ➥ e d b g f c a |
| iii ➥ e d b f g c a |
| iv ➥ d e f g b c a |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Binary trees | Help-Line |
| Q40➡ | Data Structures Consider a hash table of size seven, with starting index zero, and a hash function (3x + 4) mod 7. Assuming the hash table is initially empty, which of the following is the contents of the table when the sequence 1, 3, 8, 10 is inserted into the table using closed hashing? Note that ‘_’ denotes an empty location in the table. |
| i ➥ 8, _, _, _, _, _, 10 |
| ii ➥ 1, 8, 10, _, _, _, 3 |
| iii ➥ 1, _, _, _, _, _,3 |
| iv ➥ 1, 10, 8, _, _, _, 3 |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Hashing | Help-Line |
| Q41➡ | Algorithms In an unweighted, undirected connected graph, the shortest path from a node S to every other node is computed most efficiently, in terms of time complexity, by |
| i ➥ Dijkstra’s algorithm starting from S. |
| ii ➥ Warshall’s algorithm. |
| iii ➥ Performing a DFS starting from S. |
| iv ➥ Performing a BFS starting from S. |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Time complexity | Help-Line |
| Q42➡ | Programming Consider the following C function, what is the output? include int f(int n) { static int r = 0; if (n <= 0) return 1; if (n > 3) { r = n; return f(n-2)+2; } return f(n-1)+r; } int main() { printf(“%d”, f(5)); } |
| i ➥ 5 |
| ii ➥ 7 |
| iii ➥ 9 |
| iv ➥ 18 |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | C Programming | Help-Line |
| Q43➡ | Data Structures A complete n-ary tree is a tree in which each node has n children or no children. Let I be the number of internal nodes and L be the number of leaves in a complete n-ary tree. If L = 41, and I = 10, what is the value of n? |
| i ➥ 3 |
| ii ➥ 4 |
| iii ➥ 5 |
| iv ➥ 6 |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | N-array tree | Help-Line |
| Q44➡ | Algorithms In the following C function, let n >= m. int gcd(n,m) { if (n%m ==0) return m; n = n%m; return gcd(m,n); } How many recursive calls are made by this function? |
| i ➥ θ (log2 n) |
| ii ➥ Ω (n) |
| iii ➥ θ (log2log2 n) |
| iv ➥ θ(√n) |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Time complexity | Help-Line |
| Q45➡ | Algorithms What is the time complexity of the following recursive function: int DoSomething (int n) { if (n <= 2) return 1; else return (DoSomething (floor(sqrt(n))) + n); } |
| i ➥ Ω (n2) |
| ii ➥ θ (nlog2 n) |
| iii ➥ θ (log2 n) |
| iv ➥ θ (log2log2 n) |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Time complexity | Help-Line |
| Q46➡ | Data Structures Consider the following C program segment where CellNode represents a node in a binary tree: struct CellNode { struct CellNOde *leftChild; int element; struct CellNode *rightChild; }; int GetValue(struct CellNode *ptr) { int value = 0; if (ptr != NULL) { if ((ptr->leftChild == NULL) && (ptr->rightChild == NULL)) value = 1; else value = value + GetValue(ptr->leftChild) + GetValue(ptr->rightChild); } return(value); } The value returned by GetValue() when a pointer to the root of a binary tree is passed as its argument is: |
| i ➥ the number of nodes in the tree |
| ii ➥ the number of internal nodes in the tree |
| iii ➥ the number of leaf nodes in the tree |
| iv ➥ the height of the tree |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Binary trees | Help-Line |
| Q47➡ | Data Structures Consider the process of inserting an element into a Max Heap, where the Max Heap is represented by an array. Suppose we perform a binary search on the path from the new leaf to the root to find the position for the newly inserted element, the number of comparisons performed is: |
| i ➥ θ(log2n) |
| ii ➥ θ(log2log2n) |
| iii ➥ θ(n) |
| iv ➥ θ(nlog2n) |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Heap tree | Help-Line |
| Q48➡ | Digital Logic design Which of the following is TRUE about formulae in Conjunctive Normal Form? |
| i ➥ For any formula, there is a truth assignment for which at least half the clauses evaluate to true. |
| ii ➥ For any formula, there is a truth assignment for which all the clauses evaluate to true. |
| iii ➥ There is a formula such that for each truth assignment, at most one-fourth of the clauses evaluate to true. |
| iv ➥ None of the above. |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Conjuctive normal form | Help-Line |
| Q49➡ | Algorithms Let w be the minimum weight among all edge weights in an undirected connected graph. Let e be a specific edge of weight w. Which of the following is FALSE? |
| i ➥ There is a minimum spanning tree containing e. |
| ii ➥ If e is not in a minimum spanning tree T, then in the cycle formed by adding e to T, all edges have the same weight. |
| iii ➥ Every minimum spanning tree has an edge of weight w. |
| iv ➥ e is present in every minimum spanning tree. |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Minimum spanning tree | Help-Line |
| Q50➡ | Algorithms An array of n numbers is given, where n is an even number. The maximum as well as the minimum of these n numbers needs to be determined. Which of the following is TRUE about the number of comparisons needed? |
| i ➥ At least 2n – c comparisons, for some constant c, are needed. |
| ii ➥ At most 1.5n – 2 comparisons are needed. |
| iii ➥ At least nlog2n comparisons are needed. |
| iv ➥ None of the above. |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Time complexity | Help-Line |
| Q51➡ | Algorithms Consider the following C code segment: int IsPrime(n) { int i,n; for(i=2;i<=sqrt(n);i++) if(n%i == 0) {printf(“Not Primen”); return 0;} return 1; } Let T(n) denotes the number of times the for loop is executed by the program on input n. Which of the following is TRUE? (A) T(n) = O(sqrt(n)) and T(n) = (sqrt(n)) (B) T(n) = O(sqrt(n)) and T(n) = (1) (C) T(n) = O(n) and T(n) = (sqrt(n)) (D) None of the above |
| i ➥ T(n) = O(√n) and T(n) = Ω(√n) |
| ii ➥ T(n) = O(√n) and T(n) = Ω(1) |
| iii ➥ T(n) = O(n) and T(n) = Ω(√n) |
| iv ➥ None of the above |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Time complexity | Help-Line |
| Q52➡ | Compiler design Consider the grammar with non-terminals N = {S,C,S1 },terminals T={a,b,i,t,e}, with S as the start symbol, and the following set of rules: S –> iCtSS1|a S1 –> eS|ϵ C –> b The grammar is NOT LL(1) because: |
| i ➥ it is left recursive |
| ii ➥ it is right recursive |
| iii ➥ it is ambiguous |
| iv ➥ it is not context-free |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Parsers | Help-Line |
| Q53➡ | Compiler design Consider the following two statements: P: Every regular grammar is LL(1) Q: Every regular set has a LR(1) grammar Which of the following is TRUE? |
| i ➥ Both P and Q are true |
| ii ➥ P is true and Q is false |
| iii ➥ P is false and Q is true |
| iv ➥ Both P and Q are false |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Parsers | Help-Line |
| Q54➡ | Computer architecture In a simplified computer the instructions are: OP Rj, Ri -Performs Rj OP Ri and stores the result in register R1. OP m, Ri -Performs val OP Ri and stores the result in Rj.val denote the content of memory location m. MOV m, Ri -Moves the content of memory location m to register Ri. MOV Ri, m -Moves the content of register Ri to memory location m. The computer has only two registers, and OP is either ADD or SUB. Consider the basic block: t1 = a + b t2 = c + d t3 = e – t2 t4 = t1 – t3 Assume that all operands are initially in memory. The final value of the computation should be in memory. What is the minimum number of MOV instructions in the code generated for this basic block? |
| i ➥ 2 |
| ii ➥ 3 |
| iii ➥ 5 |
| iv ➥ 6 |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Machine instructions | Help-Line |
| Q55➡ | Operating systems An operating system uses Shortest Remaining Time first (SRT) process scheduling algorithm. Consider the arrival times and execution times for the following processes:  What is the total waiting time for process P2? |
| i ➥ 5 |
| ii ➥ 15 |
| iii ➥ 40 |
| iv ➥ 55 |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Process scheduling | Help-Line |
| Q56➡ | Operating systems A virtual memory system uses First In First Out (FIFO) page replacement policy and allocates a fixed number of frames to a process. Consider the following statements: P: Increasing the number of page frames allocated to a process sometimes increases the page fault rate. Q: Some programs do not exhibit locality of reference. Which one of the following is TRUE? |
| i ➥ Both P and Q are true, and Q is the reason for P |
| ii ➥ Both P and Q are true, but Q is not the reason for P |
| iii ➥ P is false, but Q is true |
| iv ➥ Both P and Q are false |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Page replacement | Help-Line |
| Q57➡ | Operating systems A single processor system has three resource types X, Y and Z, which are shared by three processes. There are 5 units of each resource type. Consider the following scenario, where the column alloc denotes the number of units of each resource type allocated to each process, and the column request denotes the number of units of each resource type requested by a process in order to complete execution. Which of these processes will finish LAST?  |
| i ➥ P0 |
| ii ➥ P1 |
| iii ➥ P2 |
| iv ➥ None of the above, since the system is in a deadlock. |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Bankers algorithm | Help-Line |
| Q58➡ | Operating systems Two processes, P1 and P2, need to access a critical section of code. Consider the following synchronization construct used by the processes:Here, wants1 and wants2 are shared variables, which are initialized to false. Which one of the following statements is TRUE about the above construct?  |
| i ➥ It does not ensure mutual exclusion. |
| ii ➥ It does not ensure bounded waiting. |
| iii ➥ It requires that processes enter the critical section in strict alternation. |
| iv ➥ It does not prevent deadlocks, but ensures mutual exclusion. |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Process synchronization | Help-Line |
| Q59➡ | Database Management System Information about a collection of students is given by the relation studinfo(studId, name, sex). The relation enroll(studId, courseId) gives which student has enrolled for (or taken) that course(s). Assume that every course is taken by at least one male and at least one female student. What does the following relational algebra expression represent? |
| i ➥ Courses in which all the female students are enrolled. |
| ii ➥ Courses in which a proper subset of female students are enrolled. |
| iii ➥ Courses in which only male students are enrolled. |
| iv ➥ None of the above |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Relational algebra | Help-Line |
| Q60➡ | Database Management System Consider the relation employee(name, sex, supervisorName) with name as the key. supervisorName gives the name of the supervisor of the employee under consideration. What does the following Tuple Relational Calculus query produce? |
| i ➥ Names of employees with a male supervisor. |
| ii ➥ Names of employees with no immediate male subordinates. |
| iii ➥ Names of employees with no immediate female subordinates. |
| iv ➥ Names of employees with a female supervisor. |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Relational calculus | Help-Line |
| Q61➡ | Database Management System Consider the table employee(empId, name, department, salary) and the two queries Q1 ,Q2 below. Assuming that department 5 has more than one employee, and we want to find the employees who get higher salary than anyone in the department 5, which one of the statements is TRUE for any arbitrary employee table? Q1 : Select e.empId From employee e Where not exists (Select * From employee s where s.department = “5” and s.salary >=e.salary) Q2 : Select e.empId From employee e Where e.salary > Any (Select distinct salary From employee s Where s.department = “5”) |
| i ➥ Q1 is the correct query |
| ii ➥ Q2 is the correct query |
| iii ➥ Both Q1 and Q2 produce the same answer |
| iv ➥ Neither Q1 nor Q2 is the correct query |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | SQL | Help-Line |
| Q62➡ | Database Management System Which one of the following statements if FALSE? |
| i ➥ Any relation with two attributes is in BCNF |
| ii ➥ A relation in which every key has only one attribute is in 2NF |
| iii ➥ A prime attribute can be transitively dependent on a key in a 3NF relation |
| iv ➥ A prime attribute can be transitively dependent on a key in a BCNF relation |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Normalization | Help-Line |
| Q63➡ | Database Management System The order of a leaf node in a B+ tree is the maximum number of (value, data record pointer) pairs it can hold. Given that the block size is 1K bytes, data record pointer is 7 bytes long, the value field is 9 bytes long and a block pointer is 6 bytes long, what is the order of the leaf node? |
| i ➥ 63 |
| ii ➥ 64 |
| iii ➥ 67 |
| iv ➥ 68 |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | B+ trees | Help-Line |
| Q64➡ | Database Management System Consider the following schedules involving two transactions. Which one of the following statements is TRUE? S1: r1(X); r1(Y): r2(X); r2(Y); w2(Y); w1(X) S2: r1(X); r2(X): r2(Y); w2(Y); r1(Y); w1(X) |
| i ➥ Both S1 and S2 are conflict serializable. |
| ii ➥ S1 is conflict serializable and S2 is not conflict serializable. |
| iii ➥ S1 is not conflict serializable and S2 is conflict serializable. |
| iv ➥ Both S1 and S2 are not conflict serializable. |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Transactions | Help-Line |
| Q65➡ | Computer network There are n stations in a slotted LAN. Each station attempts to transmit with a probability p in each time slot. What is the probability that ONLY one station transmits in a given time slot? |
| i ➥ np(1-p)n-1 |
| ii ➥ (1-p)n-1 |
| iii ➥ p(1-p)n-1 |
| iv ➥ 1-(1-p)n-1 |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | LAN and probability | Help-Line |
| Q66➡ | Computer network In a token ring network the transmission speed is 107 bps and the propagation speed is 200 metres/μs. The 1-bit delay in this network is equivalent to: |
| i ➥ 500 metres of cable. |
| ii ➥ 200 metres of cable. |
| iii ➥ 20 metres of cable. |
| iv ➥ 50 metres of cable. |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Token ring network | Help-Line |
| Q67➡ | Computer network The address of a class B host is to be split into subnets with a 6-bit subnet number. What is the maximum number of subnets and the maximum number of hosts in each subnet? |
| i ➥ 62 subnets and 262142 hosts. |
| ii ➥ 64 subnets and 262142 hosts. |
| iii ➥ 62 subnets and 1022 hosts. |
| iv ➥ 64 subnets and 1024 hosts. |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | IP address | Help-Line |
| Q68➡ | Computer network The message 11001001 is to be transmitted using the CRC polynomial x3+1 to protect it from errors. The message that should be transmitted is: |
| i ➥ 11001001000 |
| ii ➥ 11001001011 |
| iii ➥ 11001010 |
| iv ➥ 110010010011 |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | CRC | Help-Line |
| Q69➡ | Computer network The distance between two stations M and N is L kilometers. All frames are K bits long. The propagation delay per kilometer is t seconds. Let R bits/second be the channel capacity. Assuming that processing delay is negligible, the minimum number of bits for the sequence number field in a frame for maximum utilization, when the sliding window protocol is used, is: |
| i ➥ ⌈log2(2LtR+2K/K)⌉ |
| ii ➥ ⌈log2(2LtR/K)⌉ |
| iii ➥ ⌈log2(2LtR+K/K)⌉ |
| iv ➥ ⌈log2(2LtR+K/2K)⌉ |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Sliding window protocol | Help-Line |
| Q70➡ | Computer network Match the following:  |
| i ➥ P – 2 Q – 1 R – 3 S – 5 |
| ii ➥ P – 1 Q – 4 R – 2 S – 3 |
| iii ➥ P – 1 Q – 4 R – 2 S – 5 |
| iv ➥ P – 2 Q – 4 R – 1 S – 3 |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Match the following | Help-Line |
| Q71➡ | Computer architecture Consider the following program segment. Here R1, R2 and R3 are the general purpose registers. Assume that the content of memory location 3000 is 10 and the content of the register R3 is 2000. The content of each of the memory locations from 2000 to 2010 is 100. The program is loaded from the memory location 1000. All the numbers are in decimal.  Assume that the memory is word addressable. The number of memory references for accessing the data in executing the program completely is: |
| i ➥ 10 |
| ii ➥ 11 |
| iii ➥ 20 |
| iv ➥ 21 |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Machine instructions | Help-Line |
| Q72➡ | Computer architecture Consider the following program segment. Here R1, R2 and R3 are the general purpose registers Assume that the content of memory location 3000 is 10 and the content of the register R3 is 2000. The content of each of the memory locations from 2000 to 2010 is 100. The program is loaded from the memory location 1000. All the numbers are in decimal. Assume that the memory is word addressable. The number of memory references for accessing the data in executing the program completely is: |
| i ➥ 100 |
| ii ➥ 101 |
| iii ➥ 102 |
| iv ➥ 110 |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Machine instructions | Help-Line |
| Q73➡ | Computer architecture Consider the following program segment. Here R1, R2 and R3 are the general purpose registers. Assume that the content of memory location 3000 is 10 and the content of the register R3 is 2000. The content of each of the memory locations from 2000 to 2010 is 100. The program is loaded from the memory location 1000. All the numbers are in decimal. Assume that the memory is byte addressable and the word size is 32 bits. If an interrupt occurs during the execution of the instruction “INC R3“, what return address will be pushed onto the stack? |
| i ➥ 1005 |
| ii ➥ 1020 |
| iii ➥ 1024 |
| iv ➥ 1040 |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Machine instructions | Help-Line |
| Q74➡ | Theory of computation Consider the following Finite State Automaton. The language accepted by this automaton is given by the regular expression |
| i ➥ b*ab*ab*ab* |
| ii ➥ (a+b)* |
| iii ➥ b*a(a+b)* |
| iv ➥ b*ab*ab* |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Finite automata | Help-Line |
| Q75➡ | Theory of computation Consider the following Finite State Automaton. The language accepted by this automaton is given by the regular expression |
| i ➥ 1 |
| ii ➥ 2 |
| iii ➥ 3 |
| iv ➥ 4 |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Finite automata | Help-Line |
| Q76➡ | Algorithms Suppose the letters a, b, c, d, e, f have probabilities 1/2, 1/4, 1/8, 1/16, 1/32, 1/32 respectively. Which of the following is the Huffman code for the letter a, b, c, d, e, f? |
| i ➥ 0, 10, 110, 1110, 11110, 11111 |
| ii ➥ 11, 10, 011, 010, 001, 000 |
| iii ➥ 11, 10, 01, 001, 0001, 0000 |
| iv ➥ 110, 100, 010, 000, 001, 111 |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Huffman coding | Help-Line |
| Q77➡ | Algorithms Suppose the letters a, b, c, d, e, f have probabilities 1/2, 1/4, 1/8, 1/16, 1/32, 1/32 respectively. What is the average length of Huffman codes? |
| i ➥ 3 |
| ii ➥ 2.1875 |
| iii ➥ 2.25 |
| iv ➥ 1.9375 |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Huffman coding | Help-Line |
| Q78➡ | Compiler design Consider the CFG with {S,A,B) as the non-terminal alphabet, {a,b) as the terminal alphabet, S as the start symbol and the following set of production rules S –> aB S –> bA B –> b A –> a B –> bS A –> aS B –> aBB A –> bAA Which of the following strings is generated by the grammar? |
| i ➥ aaaabb |
| ii ➥ aabbbb |
| iii ➥ aabbab |
| iv ➥ abbbba |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Grammar | Help-Line |
| Q79➡ | Compiler design Consider the CFG with {S,A,B) as the non-terminal alphabet, {a,b) as the terminal alphabet, S as the start symbol and the following set of production rules S –> aB S –> bA B –> b A –> a B –> bS A –> aS B –> aBB A –> bAA Which of the following strings is generated by the grammar? |
| i ➥ 1 |
| ii ➥ 2 |
| iii ➥ 3 |
| iv ➥ 4 |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Grammar | Help-Line |
| Q80➡ | Computer architecture Consider a machine with a byte addressable main memory of 216 bytes. Assume that a direct mapped data cache consisting of 32 lines of 64 bytes each is used in the system. A 50 × 50 two-dimensional array of bytes is stored in the main memory starting from memory location 1100H. Assume that the data cache is initially empty. The complete array is accessed twice. Assume that the contents of the data cache do not change in between the two accesses. How many data cache misses will occur in total? |
| i ➥ 40 |
| ii ➥ 50 |
| iii ➥ 56 |
| iv ➥ 59 |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Cache | Help-Line |
| Q81➡ | Computer architecture Consider a machine with a byte addressable main memory of 216 bytes. Assume that a direct mapped data cache consisting of 32 lines of 64 bytes each is used in the system. A 50 × 50 two-dimensional array of bytes is stored in the main memory starting from memory location 1100H. Assume that the data cache is initially empty. The complete array is accessed twice. Assume that the contents of the data cache do not change in between the two accesses. How many data cache misses will occur in total? |
| i ➥ line 4 to line 11 |
| ii ➥ line 4 to line 12 |
| iii ➥ line 0 to line 7 |
| iv ➥ line 0 to line 8 |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Cache | Help-Line |
| Q82➡ | Operating systems A process has been allocated 3 page frames. Assume that none of the pages of the process are available in the memory initially. The process makes the following sequence of page references (reference string): 1, 2, 1, 3, 7, 4, 5, 6, 3, 1 If optimal page replacement policy is used, how many page faults occur for the above reference string? |
| i ➥ 7 |
| ii ➥ 8 |
| iii ➥ 9 |
| iv ➥ 10 |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Page replacement | Help-Line |
| Q83➡ | Operating systems A process has been allocated 3 page frames. Assume that none of the pages of the process are available in the memory initially. The process makes the following sequence of page references (reference string): 1, 2, 1, 3, 7, 4, 5, 6, 3, 1 If optimal page replacement policy is used, how many page faults occur for the above reference string? |
| i ➥ 0 |
| ii ➥ 1 |
| iii ➥ 2 |
| iv ➥ 3 |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Page replacement | Help-Line |
| Q84➡ | Engineering Mathematics Consider the data given in above question. Suppose that the robot is not allowed to traverse the line segment from (4,4) to (5,4). With this constraint, how many distinct paths are there for the robot to reach (10,10) starting from (0,0)? |
| i ➥ |
| ii ➥ 220 |
| iii ➥ 210 |
| iv ➥ None of the above |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Combinatorics | Help-Line |
| Q85➡ | Engineering Mathematics Suppose that a robot is placed on the Cartesian plane. At each step it is allowed to move either one unit up or one unit right, i.e., if it is at (i,j) then it can move to either (i+1,j) or (i,j+1). How many distinct paths are there for the robot to reach the point (10,10) starting from the initial position (0, 0) |
| i ➥ 29 |
| ii ➥ 219 |
| iii ➥ |
| iv ➥ |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Combinatorics | Help-Line |
| Q27➡ | |
| i ➥ |
| ii ➥ |
| iii ➥ |
| iv ➥ |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Learn Topic Wise | Help-Line |
| Q27➡ | |
| i ➥ |
| ii ➥ |
| iii ➥ |
| iv ➥ |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Learn Topic Wise | Help-Line |
| Q27➡ | |
| i ➥ |
| ii ➥ |
| iii ➥ |
| iv ➥ |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Learn Topic Wise | Help-Line |
| Q27➡ | |
| i ➥ |
| ii ➥ |
| iii ➥ |
| iv ➥ |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Learn Topic Wise | Help-Line |
| Q27➡ | |
| i ➥ |
| ii ➥ |
| iii ➥ |
| iv ➥ |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Learn Topic Wise | Help-Line |
| Q27➡ | |
| i ➥ |
| ii ➥ |
| iii ➥ |
| iv ➥ |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Learn Topic Wise | Help-Line |
| Q27➡ | |
| i ➥ |
| ii ➥ |
| iii ➥ |
| iv ➥ |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Learn Topic Wise | Help-Line |
| Q27➡ | |
| i ➥ |
| ii ➥ |
| iii ➥ |
| iv ➥ |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Learn Topic Wise | Help-Line |
| Q27➡ | |
| i ➥ |
| ii ➥ |
| iii ➥ |
| iv ➥ |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Learn Topic Wise | Help-Line |
| Q27➡ | |
| i ➥ |
| ii ➥ |
| iii ➥ |
| iv ➥ |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Learn Topic Wise | Help-Line |
| Q27➡ | |
| i ➥ |
| ii ➥ |
| iii ➥ |
| iv ➥ |
Show Answer With Best Explanation
| More Discussion | Explanation On YouTube | Learn Topic Wise | Help-Line |