❧

Exercises

1.1. Assume that the cardinalities of the standard types integer, real, and char are denoted by $c_I$ , $c_R$ , and $c_C$ . What are the cardinalities of the following data types defined as examples in this chapter: sex, Boolean, weekday, letter, digit, officer, row, alfa, complex, date, person, coordinate, charset, tapestatus?

1.2. How would you represent variables of the types listed in Exercise 1.1:

(a) In the store of your computer?
(b) In FORTRAN?
(c) In your favorite programming language?

1.3. Which are the instruction sequences (on your computer) for the following:

(a) Fetch and store operations for elements of packed records and arrays?
(b) Set operations, including the test for membership?

1.4. Can the correct use of variant records be checked at run time? Can it even be verified at compile time?

1.5. What are the reasons for defining certain sets of data as sequential files instead of arrays?

1.6. Assume that you are to implement sequential files as defined in Sec. 1.11 on a computer with a very large primary store. You are allowed to impose the restriction that files will never exceed a certain length $L$ . Hence, you can represent files in terms of arrays.

Describe a possible implementation, including the chosen data representation and procedures for the elementary file operators get, put, reset, and rewrite, which are defined by a set of axioms in Sec. 1.11.

1.7. Apply Exercise 1.6 to the case of segmented files.

1.8. Given is a railway timetable listing the daily services on several lines of a railway system. Find a representation of these data in terms of arrays, records, or files, which is suitable for lookup of arrival and departure times given a certain station and desired direction of the train.

1.9. Given a text $T$ in the form of a file, and lists of a small number of words in the form of two arrays $A$ and $B$ . Assume that words are short arrays of characters of a small and fixed maximum length.

Write a program that transforms the text $T$ into a text $S$ by replacing each occurrence of a word $A_i$ by its corresponding word $B_i$ .

1.10. Which adjustments—redefinition of constants, etc.—are necessary to adapt Programs 1.3 and 1.4 to your available computer?

1.11. Write a procedure similar to Program 1.4 whose heading is

procedure writereal (var f: text; x: real; n,m: integer);

It is supposed to transform the value $x$ into a sequence of at least $n$ characters (to be appended to file $f$ ) representing $x$ in decimal, fixed-point form54 with $m$ digits following the decimal point. If necessary, the number is to be preceded by a suitable number of blanks and/or a sign.

1.12. Rewrite the text editor of Sec. 1.11.4 in the form of a complete program.

1.13. Compare the following three versions of the binary search with (1.17). Which of the three programs are correct? Which ones are more efficient? We assume the following variables, and a constant $N > 0$ :

var i,j,k: integer;
    a: array[1 .. N] of T;
    x: T

Program A:

i := 1; j := N;
repeat k := (i+j) div 2;
   if a[k] < x then i := k else j := k
until (a[k]=x) ∨ (i≥j)

Program B:

i := 1; j := N;
repeat k := (i+j) div 2;
   if x ≤ a[k] then j := k-1;
   if a[k] ≤ x then i := k+1
until i > j

Program C:

i := 1; j := N;
repeat k := (i+j) div 2;
   if x < a[k] then j := k else i := k+1
until i ≥ j

Hint: All programs must terminate with $a[k] = x$ , if such an element exists, or $a[k] \neq x$ , if there exists no element with value $x$ .

1.14. A company organizes a poll to determine the success of its products. Its products are records and tapes of hits, and the most popular hits are to be broadcast in a hit parade. The polled population is to be divided into four categories according to sex and age (say, less or equal to 20, and older than 20). Every person is asked to name five hits. Hits are identified by the numbers 1 to $N$ (say, $N = 30$ ). The results of the poll are represented by a file.

type hit = 1 .. N;
   sex = (male, female);
   response =
      record name, firstname: alfa;
             s: sex;
             age: integer;
             choice: array [1 .. 5] of hit
      end ;
var poll: file of response

55 Hence, each file element represents a respondent and lists his name, first name, sex, age, and his five preferred hits according to priority. This file is the input to a program which is supposed to compute the following results:

A list of hits in the order of their popularity. Each entry consists of the hit number and the number of times it was mentioned in the poll. Hits that were never mentioned are omitted from the list.
Four separate lists with the names and first names of all respondents who had mentioned in first place one of the three hits most popular in their category.

The five lists are to be preceded by suitable titles.