1
Any decision tree that sorts $n$ elements has height $\Omega (\lg n)$ $\Omega ( n)$ $\Omega (n \lg n)$ $\Omega ( n^{2})$
2
Any decision tree that sorts $n$ elements has height $\Omega (\lg n)$ $\Omega ( n)$ $\Omega (n \lg n)$ $\Omega ( n^{2})$
3
Any decision tree that sorts $n$ elements has height $\Omega (\lg n)$ $\Omega ( n)$ $\Omega (n \lg n)$ $\Omega ( n^{2})$
4
Red-black trees are one of many search tree schemes that are “balanced” in order to guarantee that basic dynamic–set operations take____ time in the worst case. $O(1)$ $O(\lg n)$ $O( n)$ $O(n \lg n)$
5
Dijkstra’s algorithm is based on Divide and conquer paradigm Dynamic programming Greedy approach Backtracking paradigm
6
The minimum number of scalar multiplication required, for parenthesization of a matrix-chain product whose sequence of dimensions for four matrices is $< 5,10,3,12,5>$ is $630$ $580$ $480$ $405$
7
Consider the following JAVA program: public class First { public static int CBSE (int x) { if (x < 100)x = CBSE (x+10); return (x-1); } public static void main(String[]args){ System.out.print(First.CBSE(60)); } } What does this program print? $59$ $95$ $69$ $99$
8
Match the following with respect to algorithm paradigms: ...
9
Consider double hashing of the form $h(k,i)=(h_1(k)+ih_2(k)) \text{mod m}$ where $h_{1}(k) = \text{k mod m} \ , \ \ h_{2}(k)=1+(\text{k mod n})$ where $n=m-1$ and $m=701$. For $k=123456$, what is the difference between first and second probes in terms of slots? $255$ $256$ $257$ $258$
1 vote
10
Consider three CPU intensive processes, which require $10$, $20$ and $30$ units of time 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. $4$ $2$ $3$ $1$
Consider the following grammar: $S \rightarrow XY$ $X \rightarrow YaY \mid a \text{ and } Y \rightarrow bbX$ Which of the following statements is/are true about the above grammar? Strings produced by the grammar can have consecutive three $a$'s. Every string produced by the ... s. Every string produced by the grammar have $b$'s in multiple of $2$. a only b and c only d only c and d only
You need $500$ subnets, each with about $100$ usable host address per subnet. What network mask will you assign using a class B network address? $255.255.255.252$ $255.255.255.128$ $255.255.255.0$ $255.255.254.0$
X->aABe B->c | d A->a What will be the follow of A here? {c, d, $} or {c, d, e, dollar} 4 votes 15 A->aB/bA/b B->aC/bB C->aA/bC/a If the above regular grammar is converted into DFA then how many final states will be there? According to me there should be 2 final states: A and C But the resource from where I am reading it says only one final state will be there which will be A. Kindly explain. 2 votes 16 S→ A/a A→ a LL1 or not? 2 votes 17 Which of the following is$\textbf{not}$TRUE? (a) In a complete graph$K_n$($n\geq3$), Euler circuit exists$\Leftrightarrown$is odd. (b) In a complete bipartite graph$K_{m,n}$(m$\geq$2 and n$\geq$2), Euler circuit exists$\Leftrightarrow$m and n ...$n$(d) In a wheel graph$W_n$($n \geq 4$), Euler circuit exits$\Leftrightarrown$is even. 0 votes 18 A$64000$-byte message is to be transmitted over a$2$-hop path in a store-and-forward packet-switching network. The network limits packets toa maximum size of$2032$bytes including a$32$-byte header. The trans-mission lines in the network are error free and have a speed of$50$Mbps. ... getting answer as$1*3*(T_t+T_p) + \;31*T_t$where$T_t=0.325\; ms$and$T_p=3.333\; ms$. Please Confirm. 0 votes 19 There is given a infix expression:${\color{Red} {1}}A+B\times C/\left ( \left ( D+E \right )+F\times G \right )$While converting infix expression to postfix expression number of symbols in the stack at indicated${\color{Red} {point-1}}$infix expression (assume stack is initially empty) ______________ they told$5$, but is it correct? Can anyone give some explanation?? 0 votes 20 What is the value of$x$when$81\times\left (\frac{16}{25} \right )^{x+2}\div\left (\frac{3}{5} \right )^{2x+4}=144?1-1-2\text{Can not be determined}$2 votes 21 Consider the two processes need to access$P_{i}$and$P_{j}$need to access the C.S. The following synchronization construct used by both the processes. Process Pi While(true){ j=false; i=true; while(j==true); CRITICAL SECTION i=false; } Process Pj While(true){ i= ... while(i==true); CRITICAL SECTION j=false; } I got it is not satisfying M.E., but will it satisfying deadlock too?? Plz explain- 2 votes 22 Consider the following statements:$S_1:\{(a^n)^m|n\leq m\geq0\}S_2:\{a^nb^n|n\geq 1\} \cup \{a^nb^m|n \geq1,m \geq 1\} $Which of the following is regular?$S_1$only$S_2$only Both Neither of the above 0 votes 23 If A =$\begin{bmatrix} -1 & 1 & 0 \\ 0 & 2 &-2 \\ 0& 0 & 3 \end{bmatrix}$then trace of the matrix 3A2 + adj A is ____ 4 votes 24 A digital computer has memory unit with$24$bits word.The instruction set consists of$150$different operations. All instructions have an operation code part and an address part. Each instruction is stored in one word of memory.$Q1$How many bits are needed for the OP-CODE and how many bit are left for the ...$2^{16}, 2^{24}2^{16},2^{24}-1\textrm{None of these}$1 vote 25 minimum number of nodes (both leaf and non leaf) of B+ tree index required for storing 5500 keys and order of B+ tree is 8 _________ (order is maximum pointers a node can have) am getting 4681 2 votes 26 Consider the following program fragment: var a,b : integer; procedure G(c,d: integer); begin c:=c-d; d:=c+d; c:=d-c end; a:=2; b:=3; G(a,b); If both parameters to$G$are passed by reference, what are the values of$a$and$b$at the end of the above program fragment ?$a=0$and$b=2a=3$and$b=2a=2$and$b=3a=1$and$b=5$None of the above 0 votes 27 Consider the relation$R\left ( A,B,C,D,E \right )$with functional dependencies$F=${$A\rightarrow BBC\rightarrow EED\rightarrow A$} Number of additional relation required to convert it into lossless , dependency preserving$3NF$decomposition is _____________ What is meaning of additional relation (Here no table mentioned previously)?? 0 votes 28 Design a combinational Circuit that generates the 9’s complement of a BCD digit.? 0 votes 29 Give DFA's accepting the following languages over the alpabet$\{0,1\}:a)$The set of all strings ending in$00.b)$The set of all strings with three consecutive$0's$(not necessarily at the end)$.c)$The set of strings with$011\$ as a substring.