BSCS Discrete Mathematics and Logic 2

Question 1

What is a graph in discrete mathematics?

Accepted Answer

A collection of vertices and edges representing relationships

Answer

A graph G = (V, E) consists of a set of vertices V and edges E representing connections between them.

Question 2

What is a tree in graph theory?

Accepted Answer

A connected acyclic undirected graph

Answer

A tree is a connected graph with no cycles; it has exactly n−1 edges for n vertices.

Question 3

What does Big-O notation describe in the context of algorithms?

Accepted Answer

An upper bound on the growth rate of a function

Answer

Big-O notation provides an asymptotic upper bound on how an algorithm's runtime or space grows relative to input size.

Question 4

How many subsets does a set with n elements have?

Accepted Answer

2^n

Answer

A set with n elements has 2^n subsets because each element can independently be included or excluded.

Question 5

What is a relation that is reflexive, symmetric, and transitive called?

Accepted Answer

Equivalence relation

Answer

An equivalence relation satisfies reflexivity (aRa), symmetry (aRb → bRa), and transitivity (aRb ∧ bRc → aRc).

BSCS - Bachelor of Science in Computer Science Practice Test