wayground logo

Free Printable Worksheets

NEW

Font size

S
M
L
XL
Worksheets

MidtermExam-FCPC-DiscreteStructure

Total questions: 47

Worksheet time: 47mins

Name
Class
Date
1.

A graph is made up of:

a)

Only edges

b)

Only vertices

c)

Vertices and edges

d)

Numbers only

2.

A graph with no edges is called:

a)

Simple graph

b)

Null graph

c)

Complete graph

d)

Tree

3.

In an undirected graph, edges:

a)

Have a direction

b)

Do not have direction

c)

Point to one vertex

d)

Always form a loop

4.

The degree of a vertex is:

a)

Number of loops

b)

Number of edges connected to it

c)

Number of vertices in graph

d)

Number of components

5.

A simple graph cannot have:

a)

Loops

b)

Parallel edges

c)

Both A and B

d)

Weighted edges

6.

The number of edges in a complete graph with 4 vertices is:

a)

4

b)

5

c)

6

d)

8

7.

A tree is a connected graph with:

a)

No loops

b)

No cycles

c)

No weights

d)

Both A and B

8.

A connected graph with n vertices must have at least:

a)

n edges

b)

n−1 edges

c)

n+1 edges

d)

n² edges

9.

A cycle in a graph means:

a)

All edges are removed

b)

Vertices form a closed path

c)

Graph is disconnected

d)

Only one vertex exists

10.

In a directed graph, edges have:

a)

Weight

b)

No endpoints

c)

Direction

d)

None

11.

A graph with all vertices connected to every other vertex is called:

a)

Simple graph

b)

Tree

c)

Complete graph

d)

Path

12.

The adjacency matrix stores:

a)

Vertex names

b)

Edge connections between vertices

c)

Edge colors

d)

None

13.

The sum of all vertex degrees in an undirected graph is equal to:

a)

Number of edges

b)

Twice the number of edges

c)

Half the number of edges

d)

None

14.

A disconnected graph means:

a)

All vertices are connected

b)

Some vertices are not connected

c)

No vertices

d)

Graph is empty

15.

A loop in a graph is:

a)

An edge from a vertex to itself

b)

An edge to another vertex

c)

A long path

d)

A cycle with 2 edges

16.

A graph with a single vertex and no edges is called:

a)

Null graph

b)

Simple graph

c)

Complete graph

d)

Empty graph

17.

The adjacency list is used to store:

a)

List of vertices only

b)

List of connected vertices for each vertex

c)

Edge weights

d)

Graph colors

18.

The number of edges in a tree with 10 vertices is:

a)

9

b)

10

c)

8

d)

11

19.

A planar graph can be drawn on paper:

a)

Without edges crossing

b)

Only in 3D

c)

With loops

d)

With multiple edges

20.

Two vertices are adjacent if:

a)

They are same

b)

They are connected by an edge

c)

They have same degree

d)

They are disconnected

21.

A graph with edges showing distance is called:

a)

Directed graph

b)

Weighted graph

c)

Simple graph

d)

Complete graph

22.

The number of vertices in a triangle graph (cycle) is:

a)

2

b)

3

c)

4

d)

5

23.

A path is a sequence of:

a)

Random numbers

b)

Connected vertices

c)

Loops

d)

Unconnected edges

24.

In a simple connected graph, removing one edge can make it:

a)

Disconnected

b)

Complete

c)

Loopless

d)

Weighted

25.

A minimum spanning tree contains:

a)

All edges

b)

All vertices

c)

Both A and B

d)

Random edges

26.

Dijkstra’s algorithm is used to find:

a)

Shortest path

b)

Minimum spanning tree

c)

Largest path

d)

Maximum flow

27.

Dijkstra’s algorithm works only with:

a)

Negative weights

b)

Positive weights

c)

Directed acyclic graphs

d)

Trees

28.

The starting point of Dijkstra’s algorithm is called:

a)

Source vertex

b)

Root

c)

Parent node

d)

Leaf

29.

Dijkstra’s algorithm is based on:

a)

Breadth-first search

b)

Greedy method

c)

Divide and conquer

d)

Dynamic programming

30.

In Dijkstra’s algorithm, once a vertex is marked “visited”:

a)

Its shortest path is found

b)

It can still change

c)

It’s removed

31.

The main data structure used in Dijkstra’s algorithm is:

a)

Stack

b)

Queue

c)

Priority queue

d)

Linked list

32.

Dijkstra’s algorithm fails when:

a)

Graph is disconnected

b)

Graph has negative edge weights

c)

Graph has loops

d)

Graph has too many vertices

33.

The first step in Dijkstra’s algorithm is to:

a)

A. Initialize all distances to infinity

b)

B. Select smallest vertex

c)

C. Remove all edges

d)

D. Create adjacency list

34.

In Dijkstra’s algorithm, distance to the source vertex is always:

a)

0

b)

1

c)

Infinity

d)

Undefined

35.

Dijkstra’s algorithm stops when:

a)

All vertices are visited

b)

The destination is found

c)

Both A and B

36.

Dijkstra’s algorithm gives correct results only if:

a)

Edges are positive

b)

Graph is undirected

c)

Graph has cycles

d)

Graph is complete

37.

If a vertex has distance ∞ (infinity) after algorithm ends, it means:

a)

It’s unreachable

b)

It has smallest distance

c)

It’s a loop

d)

It’s weighted

38.

Dijkstra’s algorithm can be applied to:

a)

Road networks

b)

Binary trees

c)

Stacks

d)

Queues

39.

The output of Dijkstra’s algorithm is:

a)

Minimum spanning tree

b)

Shortest distance from source to all vertices

c)

Graph degree

d)

Number of edges

40.

Prim’s algorithm is used to find:

a)

Shortest path

b)

Minimum spanning tree

c)

Maximum flow

d)

Longest path

41.

Which of the following is a greedy algorithm?

a)

Prim’s algorithm

b)

Divide and conquer

c)

Backtracking

d)

Dynamic programming

42.

Prim’s algorithm starts from:

a)

Any vertex

b)

Smallest edge

c)

Source vertex only

d)

Center vertex

43.

The main data structure used in Prim’s algorithm is:

a)

Stack

b)

Queue

c)

Priority queue

d)

Array

44.

Prim’s algorithm works for:

a)

Directed graphs

b)

Undirected graphs

c)

Weighted directed graphs

d)

All graphs

45.

In Prim’s algorithm, edges are added if they:

a)

Form a cycle

b)

Connect a new vertex

c)

Have negative weight

d)

Are already visited

46.

Prim’s algorithm stops when:

a)

All vertices are included in the tree

b)

One vertex remains

c)

All edges are used

d)

No edge left

47.

The output of Prim’s algorithm is:

a)

Shortest path

b)

Minimum spanning tree

c)

Weighted path

d)

Hamiltonian cycle

Similar Resources on Wayground

Mathematics in Modern World MIDTERM EXAM

43 questions

Mathematics in Modern World MIDTERM EXAM

quiz

Worksheet

•

Professional Development