If the strings of a language L can be effectively enumerated in lexicographic (i.e.,alphabetic) order, which of the following statements is true?
-
Solution
According to the theory of the language, if a language is effectively enumerated in lexicographic order then the language is necessarily a regualr language.
Now, the language is arranged alphabetically, so there are less chances of repetition however, the surity is that, the language L is regular but not finite.
Consider the following languages:
L1= {WW| W ∈ {a, b}*}
L2= {WWR| W ∈ {a, b}*,WR is the reverse of W}
L3= {02i| i si an integer}
L3= {0i2|i is an integer}
Which of the languages are regular?
A program takes as input a balanced binary search tree with n leaf nodes and computes the value of a function g (x) for each node x. If the cost of computing g (x) is min (number of leaf-nodes in left-sub tree of x, number of leaf-nodes in right-sub tree of x)then the worst-case time complexity of the program is
-
Solution
As given, input is a balanced binary search tree with n leaf nodes.
G(x) is calculated for each x.
With the behaviour, we can easily suggest that program has linear worst case complexity which is given by (n).
Consider the following functions :
f(n) = 3n√n
g(n) = 2√nlog√nn
h(n) = n!
Which of the following is true?
-
Solution
Solution is obtained by solving the given f(n) and h(n) can not be solved further. We need to solve g(n).Solving g(n) will bring out a relation related to f(n). The complexity of f(n) is hence, f(n) is O(g (n)).
Consider the following C function:
void swap (int a, int b)
{int temp;
temp = a;
a= b;
b= temp;
}
In order to exchange the values of two variables x and y.
A data structure is required for storing a set of integers such that each of the following operations can be done in O(log n), time,where n is the number of elements in the set I.Deletion of the smallest element.II.Insertion of an element, if it is not already present in the set.Which of the following data structures can be used forth is purpose?
-
Solution
Both the tasks can be performed by both the data structures but heap is a data structure where to perform these function every element has to be checked so O(n) complexity.But the balance binary search tree is efficient data structure since at every decision it selects one of its sub tree to no. of elements to be checked are reduced by a factor of 1/2 every time.
n /2!= x
x = log n
Hence (b) is correct option.
The most appropriate matching for the following pairs
X:Indirect addressing 1 :Loops
Y:Immediate addressing 2 :Pointers
Z:Auto decrement addressing 3 :Constants
is
In 8085, which of the following modifies the program counter?
-
Solution
Program counter is the register which has the next location of the program to be executed next. JMP & CALL changes the value of PC. PCHL instruction copies content of registers H & L to PC.
ADD instruction after completion increments program counter.So program counter is modified in all cases. Hence(d) is correct option.
Given the following Karnaugh map, which one of the following represents the minimal Sum-Of-Products of the map?
-
Solution
Which function does not implement the Karnaugh map given below?
-
Solution