National Champion Test - GATE 2018 CS : Discrete Mathematics for GATE & PSU CS Exams

Question 1

The number of integral solutions of x + y + z = 0 with x ≥ -5, y ≥ -5 and z ≥ -5 is ________.

Question 2

Let a_n be the number of n-bit strings that contain two consecutive 1s. Which one of the following is the recurrence relation for a_n?

Question 3

The number of integers between 1 and 500 (both inclusive) that are divisible by 3 or 5 or 7 is ______.

Question 4

Consider the following sequence: s₁ : s₂ =1 and s₁ = 1 + mine {s_i₋₁, s_i₋₂} for i >2.
_S_n =

Question 5

The coefficient of

in

is ____________.

Question 6

Let Gbe a connected planar graph with 10 vertices.If the number of edges on each face is three, then the number of edges in Gis _________.

Question 7

Which of the following graphs is connected

Question 8

In a binary tree with n nodes, every node has an odd number of descendants. Every node is considered to be its own descendant. What is the number of nodes in the tree that have exactly one child?

Question 9

Let G = (V,E) be a graph. Define ξ(G) = Σd id x d, where id is the number of vertices of degree d in G. If S and T are two different trees with ξ(S) = ξ(T),then

Question 10

The line graph L(G) of a simple graph G is defined as follows:
* There is exactly one vertex v(e) in L(G) for each edge e in G.
* For any two edges e and e' in G, L(G) has an edge between v(e) and v(e'), if and only if e and e' are incident with the same vertex in G.
Which of the following statements is/are TRUE?
(P) The line graph of a cycle is a cycle.
(Q) The line graph of a clique is a clique.
(R) The line graph of a planar graph is planar.
(S) The line graph of a tree is a tree.

Question 11

Which of the following graphs has an Eulerian circuit?

Question 12

Which one of the following Boolean expressions is NOT a tautology?

Question 13

Let a, b, c, d be propositions. Assume that the equivalence a ↔ (b V~b) and b ↔ c hold. Then the truth-value of the formula (a ∧b) → (a ∧c) ∨ b is always

Question 14

Consider the following logic program P
A(x) ←B(x, y), C(y)
←B(x,x)
Which of the following first order sentences is equivalent to P?

Question 15

Suppose the predicate F(x, y, t) is used to represent the statement that person x can fool person y at time t. which one of the statements below expresses best the meaning of the formula

Question 16

Let A = {0, ±1, ±2, 3}, Consider the function f : A Ã R where R is the set of all real numbers, defined by
f(x) =

- 2

+ 3x + 1
for x € A. The range of f is

Question 17

If A->B is surjective then,

Question 18

A simple ordering of A is,

Question 19

What is the number of functions from the set of lowercaseRoman alphabet ∑ = {a,b,…,z} to the set S = {-1, 0, 1}?

Question 20

Which of the following lattices are complete lattices?