# 数据结构、算法与应用——C++语言描述 课后习题答案

此页面的内容及资料需要长期更新，现存页面中资料未必是最新。  ==>  展开 / 收缩

# Chapter 1

## Exercise 1

The function swap fails to swap the values of the actual parameters because x and y are value parameters. The invocation swap(a, b) results in the values of the actual parameters a and b being copied into the formal parameters x and y, respectively. Then, within the body of swap, the values of x and y are interchanged, and the function terminates. Upon termination, the new values of x and y are not copied back into the actual parameters. Consequently, the values of the actual parameters are unaffected by the function.
To get the function to work properly we should change the header to

void swap(int& x, int& y);


void swap(int& x, int& y);


## Exercise 2

template <class T>
int count(T a[], int n, const T& value)
{// 返回数组 a[0:n-1] 中 value 出现的次数.
int theCount = 0;
for (int i = 0; i < n; i++)
if (a[i] == value)
theCount++;
return theCount;
}


## Exercise 3

template <class T>
void fill(T* a, int start, int end, const T& value)
{// 建立数组 a[start:end-1].
for (int i = start; i < end; i++)
a[i] = value;
}


## Exercise 4

template <class T>
T inner_product(T a[], T b[], int n)
{// 返回 sum_(0  < = i  <  n) a[i] * b[i].
T ip = 0;
for (int i = 0; i  <  n; i++)
ip += a[i] * b[i];
return ip;
}


## Exercise 5

template <class T>
void iota(T* a, int n, const T& value)
{// 建立 a[i] = a[i] + value, 0 <= i < n.
for (int i = 0; i < n; i++)
a[i] += value;
}


## Exercise 6

template <class T>
bool is_sorted(T a[], int n)
{// 当且仅当 a[0:n-1] 有序时，返回 true.
for (int i = 0; i < n - 1; i++)
if (a[i] > a[i + 1])
return false;
return true;
}


## Exercise 7

template <class T>
int mismatch(T* a, T* b, int n)
{// 返回使不等式 a[i] != b[i] 成立的最小索引 i.
// Return n if no such i.
for (int i = 0; i < n; i++)
if (a[i] != b[i])
return i;

// no mismatch
return n;
}


## Exercise 8

The signature of a function is given by the number and data types of its actual parameters. Both functions have the same signature (int, int, int).

## Exercise 5

1. The signature of the function invocation agrees with that of the abc function of Program 1.1. Therefore, the abc function of Program 1.1 is invoked.

2. The signature of the function invocation agrees with that of the abc function of Program 1.2. Therefore, the abc function of Program 1.2 is invoked.

3. vThe signature of the function invocation does not agree with that of either of the abc functions. Since type conversions from both float to int and int to float are possible, C++ cannot resolve which function to use and gives a compile-time error.

4. The actual parameters are of type double. C++ cannot resolve which function to use and gives a compile-time error as type conversions from double to both int and float are possible.

• 函数调用的签名与程序 1.1 的 abc 函数的签名一致。 因此，将调用程序 1.1 的 abc 函数。

• 函数调用的签名与程序 1.2 的 abc 函数的签名一致。 因此，将调用程序 1.2 的 abc 函数。

• 函数调用的签名与任何一个 abc 函数的签名不一致。 由于可以进行从 floatint 以及从 intfloat 的类型转换，因此 C++ 无法解析要使用的函数，并且会给出编译时错误。

• 实参的类型为 double。 C ++无法解析要使用的函数，并且会给出编译时错误，因为可能会将类型从double 转换为 intfloat

## Exercise 10

int abc(int a, int b, int c)
{
if (a < 0 && b < 0 && c < 0)
throw 1;
if (a == 0 && b == 0 && c == 0)
throw 2;
return a + b * c;
}

int main()
{
int a = -1, b = -2, c= -3;
cout << "The parameters to abc were " << a << ", "
<< b << ", " << c << endl;
try {cout << abc(a,b,c) << endl;}
catch (int e)
{
if (e == 1)
cout << "All are < 0" << endl;
else
cout << "All are = 0" << endl;
}
a = b = c= 0;
cout << "The parameters to abc were " << a << ", "
<< b << ", " << c << endl;
try {cout << abc(a,b,c) << endl;}
catch (int e)
{
if (e == 1)
cout << "All are < 0" << endl;
else
cout << "All are = 0" << endl;
}
a = 1; b = 2; c= 0;
cout << "The parameters to abc were " << a << ", "
<< b << ", " << c << endl;
try {cout << abc(a,b,c) << endl;}
catch (int e)
{
if (e == 1)
cout << "All are < 0" << endl;
else
cout << "All are = 0" << endl;
return 1;
}
cout << "No Exception" << endl;
return 0;
}


## Exercise 11

template <class T>
int count(T a[], int n, const T& value)
{// 返回数组 a[0:n-1] 中 value 出现的次数.
if (n < 1)
throw "n must be >= 1";

int theCount = 0;
for (int i = 0; i < n; i++)
if (a[i] == value)
theCount++;
return theCount;
}


## Exercise 12

template <class T>
void make2dArray(T ** &x, int numberOfRows, int* rowSize)
{// 创建一个二维数组

// 创建行指针
x = new T * [numberOfRows];

// 为每一行分配空间
for (int i = 0; i < numberOfRows; i++)
x[i] = new T [rowSize[i]];
}


## Exercise 13

template<class T>
void changeLength1D(T*& a, int oldLength, int newLength)
{
if (newLength < 0)
throw illegalParameterValue("new length must be >= 0");

T* temp = new T[newLength];              // 分配新数组
int number = min(oldLength, newLength);  // 复制 number
copy(a, a + number, temp);
delete [] a;                             // 释放旧空间
a = temp;
}


## Exercise 14

template<class T>
void changeLength2D(T**& a, int oldRows, int oldColumns, int newRows, int newColumns)
{
if (newRows < 0 || newColumns < 0)
throw illegalParameterValue("# of rows and columns must be >= 0");

T** temp;
make2dArray(temp, newRows, newColumns);
int rowsToCopy = min(oldRows, newRows);
int columnsToCopy = min(oldColumns, newColumns);
for (int i = 0; i < rowsToCopy; i++)
copy(a[i], a[i] + columnsToCopy, temp[i]);
delete2dArray(a, oldRows);    // 释放旧空间
a = temp;
}


## Exercise 15

• The data member dollar is of type long. The maximum value assignable to a variable of type unsigned long is 2^{32}-1. The maximum allowable value forcents is 99. Therefore, when the representation of Program 1.13 is used, the maximum permissible currency value is 2^{32} - 1 dollars and 99 cents.
Since we store the sign seprately, the minimum currency value is just the negative of the maximum value.

• The maximum value assignable to a variable of type int is 2^{31} - 1. The maximum allowable value for cents is 99. When the data type of dollars and cents is changed to int, the maximum permissible currency value is 2^{31} - 1 dollars and 99 cents.
Since we store the sign seprately, the minimum currency value is just the negative of the maximum value.

• To avoid an error in the conversion, the result (a1 and a2) should not exceed MAX_VALUE = 2^{32}-1. Therefore, the dollar amount should not exceed MAX_VALUE / 100. Even though the dollar amount may not exceed MAX_VALUE / 100, the method may not give the correct result. To assure a correct result, the sum of the dollar amounts should not exceed MAX_VALUE / 100.

• 数据成员 dollar 的类型为 long 。可分配给 unsigned long 类型的变量的最大值为 2 ^ {32}-1cent 的最大允许值为 99。因此，当使用程序 1.13 的表示形式时，允许的最大货币值为 2 ^ {32 }-1 dollar 和99 cent
由于我们将符号分开存储，因此最小货币值就是最大值的负数。

• 可分配给 int 类型的变量的最大值为 2 ^ {31}-1cent 的最大允许值为 99。当 dollarcent 的数据类型更改为 int 时，最大允许的货币值为 2 ^ { 31}-1 dollar 和 99 cent
由于我们分开存储符号，因此最小货币价值就是最大值的负数。

• 为避免转换错误，结果（a1a2）不应超过 MAX_VALUE = 2 ^ {32} -1。因此，dollar金额不应超过 MAX_VALUE /100。即使 dollar 金额可能不超过 MAX_VALUE / 100，该方法也可能无法给出正确的结果。为了确保结果正确，dollar 的总和不应超过 MAX_VALUE / 100

## Exercise 16

We have at least two options on how to proceed. The new functions can be placed directly into the class currency or we can place the new functions in a class enhancedCurrency which is derived from currency. We shall take the latter approach. Even here, we have the option of either changing the visibility modifer for the data members of currency from private to protected so that our new class can directly access these data members, or we can leave things the way they are and use the get and set functions of currency. We shall take the latter option. Our choices leave the original class currency unmodified.

class enhancedCurrency : public currency
{
public:
// 与super class相同的构造函数
enhancedCurrency(signType theSign = plus,
unsigned long theDollars = 0,
unsigned int theCents = 0) :
currency(theSign, theDollars, theCents) {}

// new instance methods
void input()
{
// 输入 double 类型的金额
cout << "Enter the currency amount as a real number" << endl;
double theValue;
cin >> theValue;

// 设定 value
setValue(theValue);
}

enhancedCurrency subtract(const enhancedCurrency& x)
{// 返回 *this - x.
// 将* this转换为 a long
long a1 = getDollars() * 100 + getCents();
if (getSign() == minus) a1 = -a1;

// 将 x 转换为a long
long a2 = x.getDollars() * 100 + x.getCents();
if (x.getSign() == minus) a2 = -a2;

long a3 = a1 - a2;

// 将结果转换为 EnhancedCurrency 对象
enhancedCurrency result;
signType theSign = plus;
if (a3 < 0)
{
theSign = minus;
a3 = -a3;
}
result.setValue(theSign, a3 / 100, a3 - a3 / 100 * 100);

return result;
}

enhancedCurrency percent(float x)
{// 返回 * this的 x 百分比。
long a1, a2;
// convert this to a long
a1 = getDollars() * 100 + getCents();
if (getSign() == minus) a1 = -a1;

a2 = (long) (a1 * x / 100);

// 将结果转换为 EnhancedCurrency 对象
enhancedCurrency result;
signType theSign = plus;
if (a2 < 0)
{
theSign = minus;
a2 = -a2;
}
result.setValue(theSign, a2 / 100, a2 - a2 / 100 * 100);

return result;
}

enhancedCurrency multiply(float x)
{// 返回 this * x.
long a1, a2;
// convert this to a long
a1 = getDollars() * 100 + getCents();
if (getSign() == minus) a1 = -a1;

a2 = (long) (a1 * x);

// 将结果转换为 EnhancedCurrency 对象
enhancedCurrency result;
signType theSign = plus;
if (a2 < 0)
{
theSign = minus;
a2 = -a2;
}
result.setValue(theSign, a2 / 100, a2 - a2 / 100 * 100);

return result;
}

enhancedCurrency divide(float x)
{// 返回 this / x.
long a1, a2;
// 将 x 转换为 a long
a1 = getDollars() * 100 + getCents();
if (getSign() == minus) a1 = -a1;

a2 = (long) (a1 / x);

// 将结果转换为 EnhancedCurrency 对象
enhancedCurrency result;
signType theSign = plus;
if (a2 < 0)
{
theSign = minus;
a2 = -a2;
}
result.setValue(theSign, a2 / 100, a2 - a2 / 100 * 100);

return result;
}
};


## Exercise 17

We have at least two options on how to proceed. The new functions can be placed directly into the class currency or we can place the new functions in a class enhancedCurrency which is derived from currency. We shall take the former approach.

void input()
{
//  //输入金额为 double
cout << "Enter the currency amount as a real number" << endl;
double theValue;
cin >> theValue;

// set the value
setValue(theValue);
}

currency subtract(const currency& x)
{// 返回 *this - x.
currency result;
result.amount = amount - x.amount;
return result;
}

currency percent(float x)
{// 返回 *this 的 x 百分比.
currency result;
result.amount = (long) (amount * x / 100);
return result;
}

currency multiply(float x)
{// 返回 this * x.
currency result;
result.amount = (long) (amount * x);
return result;
}

currency divide(float x)
{// 返回 this / x.
currency result;
result.amount = (long) (amount / x);
return result;
}


## Exercise 18

We have at least two options on how to proceed. The new functions can be placed directly into the class currency or we can place the new functions in a class enhancedCurrency which is derived from currency. We shall take the former approach.

class currency
{
friend istream& operator>>(istream&, currency&);
public:
// 构造函数
currency(signType theSign = plus,
unsigned long theDollars = 0,
unsigned int theCents = 0);
// 析构函数
~currency() {}
currency operator=(int theAmount)
{
amount = theAmount;
return *this;
}
currency operator=(float theAmount)
{
if (theAmount < 0)
amount = (long) ((theAmount - 0.001) * 100);
else
amount = (long) ((theAmount + 0.001) * 100);
return *this;
}
signType getSign() const
{if (amount < 0) return minus;
else return plus;}
unsigned long getDollars() const
{if (amount < 0) return (-amount) / 100;
else return amount / 100;}
unsigned int getCents() const
{if (amount < 0) return -amount - getDollars() * 100;
else return amount - getDollars() * 100;}
currency operator+(const currency&) const;
currency operator-(const currency&) const;
currency operator%(float) const;
currency operator*(float) const;
currency operator/(float) const;
currency& operator+=(const currency& x)
{amount += x.amount; return *this;}
void output(ostream&) const;
private:
long amount;
};

currency::currency(signType theSign, unsigned long theDollars,
unsigned int theCents)
{// 创建对象 currency.
if (theCents > 99)
// 美分太多
throw illegalParameterValue("Cents should be < 100");

amount = theDollars * 100 + theCents;
if (theSign == minus) amount = -amount;
}

currency currency::operator+(const currency& x) const
{// 加 x 和 *this.
currency result;
result.amount = amount + x.amount;
return result;
}

currency currency::operator-(const currency& x) const
{// 从 *this 添加 x.
currency y;
y.amount = amount - x.amount;
return y;
}

currency currency::operator%(float x) const
{// 返回 *this 的 x %.
currency y;
y.amount = (long) (amount * x) / 100;
return y;
}

currency currency::operator*(float x) const
{// 返回 x * (*this).
currency y;
y.amount = (long) (amount * x);
return y;
}

currency currency::operator/(float x) const
{// 返回 (*this) / x.
currency y;
y.amount = (long) (amount / x);
return y;
}

void currency::output(ostream& out) const
{// 将 value 值插入流中.
long theAmount = amount;
if (theAmount < 0) {out << '-';
theAmount = -theAmount;}
long dollars = theAmount / 100; // dollars
out << '$' << dollars << '.'; int cents = theAmount - dollars * 100; // cents if (cents < 10) out << '0'; out << cents; } // 重载 << ostream& operator<<(ostream& out, const currency& x) {x.output(out); return out;} // 重载 >> istream& operator>>(istream& in, currency& x) {// 输入货币金额 float y; cout << "Enter the currency amount as " << "a floating point number as in dd.cc or -dd.cc" << endl; in >> y; x = y; return in; }  ## Exercise 19 int factorial (int n) {// 返回 n!. if (n <= 1) return 1; int fact = 2; for (int i = 3; i <= n; i++) fact *= i; return fact; }  ## Exercise 20 1. public static int recursiveFibonacci(int n) { if (n == 0) return 0; if (n == 1) return 1; return recursiveFibonacci(n - 1) + recursiveFibonacci(n - 2); }  2. When computing F_3, for example, F_2 is computed twice. Notice that F_3 is computed as F2 + F_1. 例如，在计算F_3时，两次计算F_2。 请注意，F_3计算为F_2 + F_1$。

3. To compute the nth Fibonacci number nonrecursively, we compute the numbers in the order F_0, F_1, F_2, F_3, ...; F_2, F_3, ... may each be computed by summing the two preceding numbers in the sequence.

为了非递归地计算第n个斐波那契数，我们按 F_0,F_1,F_2,F_3，... 的顺序计算数字; F_2,F_3,...可以通过将序列中的两个前面的数字相加来计算。

public static int fibonacci(int n)
{
if (n == 0)
return 0;
if (n == 1)
return 1;
int secondLast = 0;  // 倒数第二个斐波那契数
// 到目前为止计算
int last = 1;        // 最后的斐波那契数
// 到目前为止计算
// 计算新数字
for (int i = 2; i <= n; i++)
{
// 计算第 i 个斐波那契数
int next = last + secondLast;
// 更新 last 和 secondLast
secondLast = last;
last = next;
}

return last;
}


## Exercise 21

f(5) = f(3 \times 5 + 1) = f(16) = 16 / 2 = 8.

f(7) = f(3 \times 7 + 1) = f(22) = 22 / 2 = 11.

The base component is f(n) = n/2, n is even and the recursive component is f(n) = f(3n + 1), n is odd.

When n is odd, one application of the recursive component transforms the occurrence of n on the right hand side to the base component because 3n + 1 is even whenever n is odd.

n为奇数时，递归组件的一个应用程序会将右侧的 n 的出现转换为基本组件，因为 3n + 1 在 任意 n 时都为奇数。

public static int recursiveF(int n)
{
return (n % 2 == 0) ? n / 2 : recursiveF(3 * n + 1);
}

public static int iterativeF(int n)
{
return (n % 2 == 0) ? n / 2 : (3 * n + 1) / 2;
}


## Exercise 22

A(1,2) = 2^2 = 4.

A(2,1) = A(1,2) = 4.

A(2,2) = A(1, A(2,1)) = A(1, 4) = 2^4 = 16.
The base component is A(i,j) = 2j for i = 1 and j = 1 and the recursive components are A(i,j) = A(i-1,2) for i >= 2 and j = 1 and A(i,j) = A(i-1,A(i, j-1)) for i,j>= 2.

cpp
/** 计算阿克曼函数
* @当 i 或 j <1时抛出 IllegalArgumentException */
public static int ackermann(int i, int j)
{
if (i < 1 || j < 1)
throw new IllegalArgumentException("i and j must be >= 1, they are "+ "i = " + i + " j = " + j);

<pre><code> return a(i, j);
</code></pre>

}

/** 计算阿克曼函数
*假设 i，j> = 1 */
private static int a(int i, int j)
{
if (i <span class="text-highlighted-inline" style="background-color: #fffd38;"> 1)
{// 计算 2^j
int ans = 2;
for (int k = 1; k < j; k++)
ans *= 2;
return ans;
}</span>

<pre><code> if (j == 1)
return a(i - 1, 2);

// i 和 j >= 2
return a(i - 1, a(i, j - 1));
</code></pre>

}



## Exercise 23

\gcd(20, 30) = \gcd(30, 20 \mod 30) = \gcd(30, 20) = \gcd(20, 30 \mod 20) = \gcd(20, 10) = \gcd(10, 20 \mod 10) = \gcd(10, 0) = 10.

\gcd(112, 42) = gcd(42, 112 \mod 42) = \gcd(42, 28) = \gcd(28, 42 \mod 28) = gcd(28, 14) = \gcd(14, 28\mod 14) = \gcd(14,0) = 0.

The base component is gcd(x, y) = x when y = 0 and the recursive component is gcd(x, y) = gcd(y, x mod y), y > 0.

A formal proof can be provided using induction. We provide an informal proof. When x < y, the first application of the definition gives us gcd(x, y) = gcd(y, x mod y) = gcd(y, x). Following this, the first parameter is > the second. So, we may consider only the case when x >= y.

When x = y, an application of the definition results in gcd(x,y) = gcd(y, x mod y) = gcd(y,0) which is an occurrence of gcd in the base component.

When x > y, an application of the definition results in gcd(x,y) = gcd(y, x mod y) = gcd(y,z), where 0 <= z < y. Each application of the recursive component decreases the second parameter. Therefore, after a sufficient number of applications (at most y), the second parameter will become 0 and we will have an occurrence of gcd which is in the base component.

x = y 时，定义的应用导致 gcd(x，y)= gcd(y，x mod y)= gcd(y，0) 。这是在基础组件中出现的 gcd

x > y时，定义的应用将导致gcd(x，y)= gcd(y，x mod y)= gcd(y，z)，其中0 <= z < y 递归组件的每次应用都会减少第二个参数。 因此，在足够数量的应用程序之后（最多为 y），第二个参数将变为 0 ，并且在基本组件中将出现 gcd

cpp
/** @返回 x 和 y 的 gcd
* @当 x 或 y < 0 时抛出 IllegalArgumentException
public static int gcd(int x, int y)
{
if (x < 0 || y < 0)
throw new IllegalArgumentException("x and y must be >= 0, " + "x = " + x + " y = " + y);

<pre><code> return rgcd(x, y);
</code></pre>

}

/** @return the gcd of x and y
* assumes x,y >= 0 */
private static int rgcd(int x, int y)
{
return (y <span class="text-highlighted-inline" style="background-color: #fffd38;"> 0) ? x : rgcd(y, x % y);
}



## Exercise 24

The code is given below. This code first compares a[n-1] and x. If they are equal, we are done. If they are not equal, the problem becomes one of determining whether x is one of a[0:n-2]. The recursion terminates when n is smaller than 1.

package applications;

import wrappers.*;
import utilities.*;

public class Exists
{
/** @ 如果 x 属于 a[0:n-1] ，返回 true */
public static boolean exists(Comparable [] a, Comparable x, int n)
{
if (n < 1)
return false;
if (a[n - 1].equals(x))
return true;
return exists(a, x, n - 1);
}
}


## Exercise 25

We may represent a subset of n elements by the one-dimensional array x[1:n], where x[j] is one if element j is included in the subset and x[j] is zero if element j is not included in the subset.

To output the subsets recursively, we define a method subsets(int i) which outputs all x[1:n] with preset values for x[1:i-1] and x[i:n] taking on all possible 0 and 1 values. The invocation subsets(1) will output all subsets.

/** 生成n个元素的所有子集 */

package applications;

public class AllSubsets
{
// 类数据成员
static int [] x;  // subset vector

/** 定义数组 x 并调用私有方法子集*/
public static void allSubsets(int n)
{
x = new int [n + 1];
// output all subsets of x[1:n]
subsets(1);
}

/** 输出 x[1：i-1]，后跟 x[i：x.length-1] 的所有子集 */
private static void subsets(int i)
{
if (i == x.length - 1)
{// x[x.length-1]可以为 0 或 1
// 输出没有最后一个元素的子集
x[x.length - 1] = 0;
for (int j = 1; j <= x.length - 1; j++)
System.out.print(x[j] + " ");
System.out.println();

// 输出带有最后一个元素的子集
x[x.length - 1] = 1;
for (int j = 1; j <= x.length - 1; j++)
System.out.print(x[j] + " ");
System.out.println();
return;
}

// 忽略元素 i
x[i] = 0;
// 生成所有排除 i 的子集
subsets(i + 1);

// 生成包含 i 的所有子集
x[i] = 1;
// generate all subsets with i included
subsets(i + 1);
}

/** 测试程序 */
public static void main(String [] args)
{
allSubsets(4);
}
}


## Exercise 26

g(4) = g(3), 4, g(3) = g(2), 3, g(2), 4, g(2), 3, g(2)
= g(1), 2, g(1), 3, g(1), 2, g(1), 4, g(1), 2, g(1), 3, g(1), 2, g(1)
= 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1.

The base component is g(n) = 1, for n = 1 and the recursive component is g(n) = g(n-1), n, g(n-1) for n >= 1.

A formal proof can be provided using induction. We provide an informal proof. When n = 1, we have an occurrence of the base component. When n > 1, one application of the recursive component yields two occurrences of g(n-1). Two additional applications of the recursive component will replace the two occurrences of g(n-1) by four occurrences of g(n-2), and so on. So, after 1 + 2 + 4 + 8 + ... + 2^n-2 applications of the recursive component, all remaining occurrences of g are base component occurrences.

/** @返回 n 位格雷码的位转换顺序
* @ n < 1 时抛出IllegalArgumentException */
private static String grayCode(int n)
{
if (n < 1)
throw new IllegalArgumentException(" n must be >= 1, it is "+ n);
return g(n);
}

/** @返回 n 位格雷码的位转换顺序 */
private static String g(int n)
{
if (n == 1)
return "1";

String left = g(n - 1);
return left + ", " + n + ", " + left;
}


## Exercise 45

The program has 4 execution paths and each execution path has at least one statement that is not on any other execution path. Therefore, any test set that provides statement coverage must follow all execution paths, and hence must provide execution path coverage coverage.

The program has 3 decisions. By examining the decisions needed to execute each of the 4 execution paths, we see that over these 4 execution paths, each of the 3 decisions takes on the truth values true and false. Hence execution path coverage implies decision coverage. Since we have already shown that statement coverage implies execution path coverage, it follows that any test set that provides statement coverage must also provide decision coverage.

## Exercise 46

When n = 3, the for loop is entered three times and there can be 2^3 = 8sequences of outcomes for the decision (a[pos].lessThan(a[i])). So there are 8 execution paths and 8 data sets are required for execution path coverage. Each execution path can be described by the truth value sequence for the decision. For example, FFF describes the path when (a[pos].lessThan(a[i])) is false on all three iterations of the for loop, and TFF describes the execution path when (a[pos].lessThan(a[i])) is true on the first iteration and false on the remaining two iterations of the for loop.

A sample array a[0:3] for each execution path is given below.

n = 3时，for循环被输入 3 次，并且可能有 2 ^ 3= 8 决策的结果序列(a[pos].lessThan(a[i]))。 因此，执行路径覆盖需要 8 条执行路径和 8 个数据集。 每个执行路径都可以由决策的真值序列描述。 例如，当 a[pos].lessThan(a[i]))for 循环的所有三个迭代中为 false 时，FFF 描述路径，而 TFF 描述执行 当 (a[pos].lessThan(a[i])) 在 for 循环的第一次迭代中为 true 且在其余两次迭代中为 false 时的路径。

Path Test set
FFF [6, 2, 3, 1]
TFF [2, 6, 3, 1]
FTF [6, 2, 8, 1]
TTF [2, 6, 8, 1]
FFT [6, 2, 3, 8]
TFT [2, 6, 3, 8]
FTT [6, 2, 8, 9]
TTT [2, 6, 8, 9]

## Exercise 47

For each value of n, Program 1.30 has exactly one execution path.

## Exercise 48

For each value of n, method rSum of Program 1.31 has exactly one execution path.