Exercises for Section 7.2

7.2.1

Suppose that the program of Fig.7.2 uses a partition function that always picks a[m] as the separator v. Also, when the array a[m], … , a[n] is reordered, assume that the order is preserved as much as possible. That is, first come all the elements less than v, in their original order, then all elements equal to v, and finally all elements greater than v, in their original order.

1. Draw the activation tree when the numbers 9,8,7,6,5,4,3,2,1 are sorted.
2. What is the largest number of activation records that ever appear together on the stack?

Answer

1. Draw the activation tree when the numbers 9,8,7,6,5,4,3,2,1 are sorted.

   

2. What is the largest number of activation records that ever appear together on the stack?

   9

7.2.2

Repeat Exercise 7.2.1 when the initial order of the numbers is 1,3,5,7,9,2,4,6,8.

7.2.3

In Fig. 7.9 is C code to compute Fibonacci numbers recur­sively. Suppose that the activation record for f includes the following elements in order: (return value, argument n, local s, local t); there will normally be other elements in the activation record as well. The questions below assume that the initial call is f(5).

int f(int n) {
    int t, s;
    if (n < 2) return 1;
    s = f(n-1);
    t = f(n-2);
    return s+t;
}

Figure 7.9: Fibonacci program for Exercise 7.2.3

1. Show the complete activation tree.
2. What dose the stack and its activation records look like the first time f(1) is about to return?
3. ! What does the stack and its activation records look like the fifth time f(1) is about to return?

Answer

1. Show the complete activation tree.

   

2. What dose the stack and its activation records look like the first time f(1) is about to return?

   

3. ! What does the stack and its activation records look like the fifth time f(1) is about to return?

   

7.2.4

Here is a sketch of two C functions f and g:

int f(int x){int i;...return i+1;...}
int g(int y) {int j;...f(j+1). ..}

That is, function g calls f. Draw the top of the stack, starting with the acti­vation record for g, after g calls f, and f is about to return. You can consider only return values, parameters, control links, and space for local variables; you do not have to consider stored state or temporary or local values not shown in the code sketch. However, you should indicate:

1. Which function creates the space on the stack for each element?
2. Which function writes the value of each element?
3. To which activation record does the element belong?

Answer

7.2.5

In a language that passes parameters by reference, there is a function f(x, y) that does the following:

x = x + 1; 
y = y + 2;
return x+y;

If a is assigned the value 3, and then f(a, a) is called, what is returned?

Answer

x = x + 1  ->  a = a + 1  ->  now a is 4
y = y + 2  ->  a = a + 2  ->  now a is 6
x + y  ->  a + a  ->  6 + 6  ->  12

f(a, a) is 12

7.2.6

The C function f is defined by:

int f(int x, *py, **ppz) {
    **ppz += 1;
    *py += 2;
    x += 3;
    return x+y+z;
}

Variable a is a pointer to b; variable b is a pointer to c, and c is an integer currently with value 4. If we call f(c, b, a) , what is returned?

Answer

f(c, b, a) is 21

view source code

mind that c is passed by value, so the process is:

sentence        x in f()   x out of f()  *py    **ppz

**ppz += 1;     4          5             5      5
*py += 2;       4          7             7      7
x += 3;         7          7             7      7