APPSC-2016-DL-CS

Question 1
The minimum number of edges of a graph containing n vertices and c connected components is
A
n-c
B
c
C
c(n-1)
D
n/c
Question 1 Explanation: 
We have to find a minimum no. of edges. So for c connected components let's assume c-1 independent vertices which are also c-1 components and remaining 1 component will contain n-(c-1) vertices or n-c+1 vertices. So for minimum no. of edges will be no. of vertices in the single component (which contains n-c+1 vertices) -1, which is (n-c+1)-1 = n-c
Question 2
In first order predicate logic, ∼∀x P(x) is equivalent to Options:
A
∼∃x P(x)
B
∃x ∼P(x)
C
∀x ∼P(x)
D
the given expression is not a well formed
Question 2 Explanation: 
∼∀x P(x) = ∃x ∼P(x)
Question 3
How many different 6-member committees can be formed from 6 men and 4 women with a restriction that each committee should include an equal number of men and women
A
120
B
80
C
420
D
6045
Question 3 Explanation: 
Given data,
Committee members=6,
Mens=6
Women=4
Equal numbers of men and women are= ?
3 men out of 6, 3 women out of 4
6C3 * 4C3 ways
⇒ 20 * 4
⇒ 80
Note: There are 3 possibilities to consider an equal number of men and women.
Choose 4 men and 4 women then we get 6C4 * 4C4 ways = 15
Choose 2 men and 2 women then we get 6C2 * 4C2 ways = 90
Choose 3 men and 3 women then we get 6C3 * 4C3 ways = 80
Question 4
Consider 4-character long codes generated by using an alphabet consisting of 8-characters with no restriction on the number of repetitions of a character in a code. How many codes at least one character repeated?
A
2416
B
6720
C
1680
D
4096
Question 5
How many distinct Boolean functions can be formed from ‘n’ Boolean variables?
A
n2
B
2n2
C
2n
D
2 to the power of 2n
Question 5 Explanation: 
Each “boolean” variable has two possible values i.e 0 and 1.
Number of variables= n
Number of input combinations is 2n.
Each “boolean” function has two possible outputs i.e 0 and 1.
Number of boolean functions possible is 22^n.
Formula: The number of m-ary functions possible with n k-ary variables is mk^n.
Question 6
In order for a function to be invertible, it should be _______
A
one-one
B
onto
C
both one-one and onto
D
into
Question 6 Explanation: 
A function is invertible if and only if it is both one-one and onto.
Question 7
What is the maximum value of the function f(x)=x2-3x+5 in the internal [0,5]?
A
15
B
5
C
3
D
9
Question 7 Explanation: 
Question 8
In an IT company, given that the probability of finding an employee with programming skills is 0.7, documentation skills is 0.6, and if the probability of finding an employee with either of the skills is 0.9, then what is the probability of finding an employee with both the skills?
A
0.42
B
0.5
C
0.4
D
0.8
Question 8 Explanation: 
Let A = probability of finding an employee with programming skills
Let B = probability of finding an employee with documentation skill
So A=0.7
B=0.6
AUB=0.9
Hence ,A∩B = A + B - (AUB)
= 0.7+0.6-0.9
= 0.4
Question 9
Let A, B and C are finite sets. Which of the following options is TRUE, if X=((A∩B)-(B∩C)) and Y=(A-(A∩C))-(A-B)?
A
X⊂Y
B
X⊃Y
C
X=Y
D
X-Y≠φ and Y-X≠φ
Question 9 Explanation: 

Now,
x=((AB)-(BC))
=(b,c)-(e,f))
=b
y=(A-(AC))-(A-B)
=((a,b,d,e)-(d,e))-(a,d)
=(a,b)-(a,d)
=b
Hence, x=y
Question 10
Which of the following options is TRUE with regard to a relation R defined on ordered pairs of integers as given below: (x,y) R (low,up) if x>low and y<up?
A
R is totally ordered
B
R is partially ordered but not totally ordered
C
R is an equivalence relation
D
R is neither partially ordered nor an equivalence relation
Question 10 Explanation: 
If a relation is equivalence then it must be
i) Symmetric
ii) Reflexive
iii) Transitive
If a relation is a partial order relation then it must be
i) Reflexive
ii) Anti-symmetric
iii) Transitive
If a relation is total order relation then it must be
i) Reflexive
ii) Symmetric
iii) Transitive
iv) Comparability
Given ordered pairs are (x,y)R(low,up) if (x,up).
Here < , > are using while using these symbols between (x,y) and (y,up) then they are not satisfy the reflexive relation. If they use (x< =low) and (y >=low) then reflexive relation can satisfies.
So, given relation cannot be an Equivalence. Total order relation or partial order relation.
Question 11
The Hasse diagram representing a lattice, P when turned upside-down represents the poset, Q. Poset Q is a ______
A
dual of P
B
Greatest Upper Bound of P
C
Lattice
D
dual of P and Lattice
Question 11 Explanation: 
The Hasse diagram representing a lattice, P when turned upside-down represents the poset Q which is dual of P and lattice.
Question 12
A pair of dice is tossed twice. What is the probability of scoring 9 at least in one of the two times?
A
16/81
B
17/81
C
1/36
D
64/81
Question 12 Explanation: 
We will use binomial distribution here.
Total possible outcomes will be 6*6=36
Lets first calculate probability of getting sum as 9. We will get sum as 9 when first dice and second dice will have number (3,6) ,(4,5) ,(5,4) ,(6,3). So total 4 possibility are there out of 36.
So Let probability of getting sum as 9 = P(A) = 4/36 = 1/9
Now
Probability of scoring 9 at least in one of the two times
= Probability of scoring 9 exactly one time + Probability of scoring 9 exactly two times
Question 13
Which of the following probability distributions is applicable to consider the problem of estimating the probability of exactly two defective items manufactured in an industry in a batch of 20 items, if the probability of manufacture defect is 0.1?
A
Poisson distribution
B
Binomial distribution
C
Uniform distribution
D
Gaussian distribution
Question 13 Explanation: 
Binomial distribution will be used. And will be calculated as 20C2 = (0.1)2 (0.9)18
Question 14
The propositional expression [(∼P∨Q)→(Q→P)] is
A
a tautology
B
not a tautology
C
contradiction
D
not a well-formed formula
Question 14 Explanation: 
Question 15
The maximum number of non-zero elements of a n×n matrix whose [i,j]th element is equal to 0 for all i<j is
A
n(n-1)/2
B
n(n+1)/2
C
n2
D
n
Question 15 Explanation: 
From given description we can conclude that all the elements above the diagonal are 0. So we can say that,
1st row will have 1 non-zero element,
2nd row will have 2 non zero elements,
3rd row will have 3 non-zero elements ,
:
:
:
nth row will contain n non-zero elements.

Therefore total no. of non-zero elements are,
1+2+3+...........+n = n(n+1)/2
Question 16
At a given moment a queue contains stored in it. If the capacity of the queue is 6 then which of the following sequence of operations results in a modified queue contents?
A
delete a, b; and insert e,a,f;
B
insert e,a,f and delete a,b
C
insert e, delete b and insert f
D