Let L denotes the language generated by the grammar S → 0S0/00. Which of the following is true?
-
Solution
S→0S0/00
S→0S0 (type 2 production)
This is a context-free grammar as in CFG, the left hand side of the production rule has no left and right context.
S→00
means S→^ (null)* (type 3 production)This is called the regular grammar.
Let G (V, E) be an undirected graph with positive edge weights Dijkstra’s single source shortest path algorithm can be implemented using the binary heap data structure with time complexity
-
Solution
Dijkstra Algorithm for every vertex we consider the binary heap to find shortest path. This take V log V time.
And we need to transverse each edge 1 time atleast.
So overall complexity O ((| E| + | V|) log | V |)
Two matrices M1 and M2 are to be stored in arrays A and B respectively. Each array can be stored either in row-major or column-major order in contiguous memory locations. The time complexity of an algorithm to compute M1 × M2 will be
-
Solution
Since the matrices are stored in array, there is no dependence of time complexity on row major or column major. Here only the starting address is known & on the basis of indexes the next memory locations are calculated.Hence (d) is correct option.
Assume the following C variable declaration:
int* A[10], B[10][10];
Of the following expressions which will not give compile time errors if used as left hand sides of assignment statements in a C program ?
-
Solution
From the given declaration it is clear that int* A[10] is an array of 10 printers. Thus,B[2][3] can be used as left hand side as it gives the element of second row in the third column.
To evaluate an expression without any embedded function calls
Suppose you are given an array s[1….n] and a procedure reverse (s, i, j) which reverses the order of elements in a between positions i and j(both inclusive). What does the following sequence do, where 1 £ k £ n :reverse (s, 1, k);reverse (s, k+ 1, n);reverse (s, 1, n);
-
Solution
From the given conditions it can be clearly concluded that,the given sequence rotates s left by k positions.
Consider the following nested representation of binary trees: (XYZ) indicates Y and Z are the left and right sub trees, respectively, of node X. Note that Y and Z may be NULL, or further nested. Which of the following represents a valid binary tree?
-
Solution
A processor needs software interrupt to
-
Solution
A CPU needs software interrupt to obtain system services which need execution of privileged instructions. Hence (c) is correct option.
A low memory can be connected to 8085 by usingREADY
-
Solution
Memory can be connected to 8085 by using READY signal.If READY is set then communication is possible. Hence (d)is correct option.
Consider the circuit shown below. The output of a 2 : 1 MUX is given by the function (ac’+ bc).
Which of the following is true?
-
Solution