Mathematical Preliminaries

Question 1

T/F The goal of predicate-based test generation is to generate tests from a predicate p that guarantee the detection of any error that belongs to a class of errors in the coding of p

Answer 1

T

Question 2

What does the + sign represent?

Answer 2

OR

Question 3

What does a multiplication mean?

Answer 3

AND

Question 4

What is the condition part of the statement

Answer 4

Predicate

Question 5

T/F A predicate can be converted to a Boolean expression by replacing each relational expression with a distinct Boolean variable

Answer 5

T

Question 6

A Boolean variable or a relational expression

Answer 6

Simple predicate

Question 7

Join one or more simple predicates using bop

Answer 7

Compound predicate

Question 8

One or more Boolean variables joined by bop

Answer 8

Boolean expression

Question 9

A Boolean expression is ____ if each variable in the

expression occurs only once

Answer 9

Singular

Question 10

A Boolean expression is in ____ _____ ____ if it is represented as a sum of product terms

Answer 10

Disjunctive normal form

Question 11

A Boolean expression is in ___ ____ ____ if it is represented as a product of sums

Answer 11

Conjunctive normal form

Question 12

T/F Any Boolean expression in CNF can be converted to an equivalent DNF and vice versa

Answer 12

T

Question 13

Captures flow of control within a program

Answer 13

Control flow graph

Question 14

What has a finite set N of nodes and a finite set E of edges

Answer 14

Control flow graph

Question 15

What does descendant mean for nodes?

Answer 15

There is a path from one node to the next (m to n)

Question 16

What does proper descendant mean for nodes?

Answer 16

m != n (m and n are not the same node)

Question 17

How do you denote all successor nodes of n?

Answer 17

succ(n)

Question 18

How do you denote all predecessor nodes of n

Answer 18

pred(n)

Question 19

If there is an edge (n,m) in E, what is n and what is m?

Answer 19

m is the successor of n. n is the predecessor of m

Question 20

A path through G is ____if the first node along the path is Start and the terminating node is End.

Answer 20

complete

Question 21

A path p is ____ if there exists at least one test case which when input to program P causes p to be traversed

Answer 21

feasible

Question 22

T/F Whether a path p through program P is feasible is, in general, an undecidable problem

Answer 22

T

Question 23

T/F Any algorithm can be expressed using only three

control structures

Answer 23

T

Question 24

T/F The cyclomatic complexity of a nonstructured program is at least 2

Answer 24

F, 3

Question 25

T/F A flow graph is reducible to a structured program if and only if it contains a loop with two or more exits

Answer 25

F, if it DOES NOT CONTAIN a loop with two or more exits

Question 26

G has only one path if and only if....

Answer 26

V(G) = 1

Question 27

Inserting a new edge in G increases V(G) by _

Answer 27

1

Question 28

T/F V(G) depends only on the decision structure of G

Answer 28

T

Question 29

T/F V(G) is the maximum number of linearly independent paths in G

Answer 29

T

Question 30

What is V(G)

Answer 30

Cyclomatic Complexity

Question 31

V(G) is always >= _

Answer 31

1

Question 32

When is a boolean expression singular?

Answer 32

Each variable in the expression occurs only once

Question 33

Two expressions are ____ ____ if they do not share any variable

Answer 33

Mutually singular

Question 34

What is disjunctive normal form (DNF)?

Answer 34

Sum of product terms

Question 35

What is conjunctive normal form (CNF)?

Answer 35

Product of sums

Question 36

In an abstract syntax tree, what are leaf nodes?

Answer 36

Boolean or relational expressions

Question 37

In an abstract syntax tree, what are internal nodes?

Answer 37

Boolean operator

Question 38

T/F All loops are basic blocks by themselves

Answer 38

F, only pre-test loops

Question 39

T/F if statements are the last statement in a basic block

Answer 39

T

Question 40

T/F If a path is infeasible, you can cover the true and false branch

Answer 40

F

Question 41

T/F Not all programs can be written as a structured program

Answer 41

F, they can

Question 42

What is the structured program theorem?

Answer 42

Any program can be written as a structured program

Question 43

For nodes n and m in N, n ____ m if n lies on every path from Start to m

Answer 43

Dominates

Question 44

n is the ____ ____ of m when n is the last dominator of m along a path from Start to m

Answer 44

Immediate dominator

Question 45

If n dominates m, how is it denoted?

Answer 45

dom(n,m)

Question 46

If n is the immediate dominator of m, how is it denoted?

Answer 46

idom(n,m)

Question 47

T/F Each node, except for Start, has a unique immediate dominator

Answer 47

T

Question 48

T/F Start has a unique immediate dominator

Answer 48

F

Question 49

For nodes n and m in N, n ____ m if n lies on every path from m to the End node

Answer 49

Post-dominates

Question 50

If n post-dominates m, how is it denoted?

Answer 50

pdom(n,m)

Question 51

n is the ____ ____ of m if n is the first post-dominator along a path from m to End

Answer 51

immediate post-dominator

Question 52

If n is the immediate post-dominator of m, how is it denoted?

Answer 52

ipdom(n,m)

Question 53

T/F Each node, except for End, has a unique | immediate post-dominator

Answer 53

T

Question 54

A sequence of instructions forms a ____ ____ if the instruction in each position dominates, or always executes before all those in later positions and no other instruction executes between two instructions in the sequence

Answer 54

Basic block

Question 55

``` T/F Inserting or deleting functional statements to G affects V(G) ```

Answer 55

F, it does not

Question 56

When is a path through G considered complete?

Answer 56

The first node along the path is Start and the terminating node is End

Question 57

When is a path considered feasible?

Answer 57

There exists at least one test case which when input to program P causes p to be traversed

Question 58

When is a flow graph reducible to a structured program?

Answer 58

If and only if it does not contain a loop with two or more exits

Question 59

__ is the maximum number of linearly independent paths in G

Answer 59

V(G)

Question 60

When are two or more expressions mutually singular?

Answer 60

When they don't share any variable

Question 61

T/F if statements are the first statement in a basic block

Answer 61

F, last

Question 62

End has a unique immediate post-dominator

Answer 62

F