Related InterviewSolutions

• Consider the following grammar.S -> S * ES -> EE -> F + EE -> FF -> idConsider the following LR(0) items corresponding to the grammar above.(i) S -> S * .E(ii) E -> F. + E(iii) E -> F + .E Given the items above, which two of them will appear in the same set in the canonical sets-of-items for the grammar?(A) (i) and (ii)(B) (ii) and (iii)(C) (i) and (iii)(D) None of the above
• Consider a weighted complete graph G on the vertex set {v1, v2, ..vn} such that the weight of the edge (vi, vj) is 2|i-j|. The weight of a minimum spanning tree of G is: (GATE CS 2006)(A) n — 1(B) 2n — 2(C) nC2(D) 2
• To implement Dijkstra’s shortest path algorithm on unweighted graphs so that it runs in linear time, the data structure to be used is:(A) Queue(B) Stack(C) Heap(D) B-Tree
• 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)?(A) 400(B) 500(C) 600(D) 700
• In a binary max heap containing n numbers, the smallest element can be found in time(A) O(n)(B) O(Logn)(C) O(LogLogn)(D) O(1)
• 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°?(A) A(B) B(C) C(D) D
• Which one of the following in place sorting algorithms needs the minimum number of swaps?(A) Quick sort(B) Insertion sort(C) Selection sort(D) Heap sort
• 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.(A) log2n(B) n(C) 2n + 1(D) 2^n — 1
• 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?(A) val(j) = (logn)(B) vaI(j) = (sqrt(n))(C) val(j) = (n)(D) val(j) = (nlogn)(A) A(B) B(C) C(D) D
• Let S be an NP-complete problem and Q and R be two other problems not known to be in NP. Q is polynomial time reducible to S and S is polynomial-time reducible to R. Which one of the following statements is true?(A) R is NP-complete(B) R is NP-hard(C) Q is NP-complete(D) Q is NP-hard