Programming I, Winter 2017-8
Practice Exam

Time limit: 60 minutes

Write your answers in a text editor. You may refer to the lecture notes or Pascal reference pages, but may use no other Web sites during this exam. Do not call any library functions. I will give partial credit for code that is not completely correct.

1. Write a function `words` that determines the number of words in a string. For this problem, words are sequences of non-space characters separated by one or more spaces. For example, `words(" big    yellow   hat")` = 3.

2. Write a function `ones` that takes an integer `i` and returns true iff there are any consecutive 1s in the binary representation of `i`. For example, `ones(5)` = false since 5 = 1012, and `ones`(6) = true since 6 = 1102.

3. Write a function `most` that takes two arguments: (1) an array of integers and (2) a function f from integers to booleans. `most` should return true if the function f returns true for most (at least half) of the elements in the array. For example, if `a` and `odd` are defined as

```var a: array[1..5] of integer = (3, 4, 5, 6, 7)

function odd(i: integer): boolean;
begin
exit(i mod 2 = 1);
end;```

then `most(a, @odd)` = true.

4. Write a function `sub` that takes two linked lists of integers `s` and `t` and returns true iff any subsequence of nodes in s is identical to t. For example, if `s` = 3 → 4 → 2 → 7 → 8 → `nil` and `t` = 2 → 7 → `nil` then ```sub(s, t)``` = true.

5. The height of a node in a binary tree is its distance in edges from the root node. The root node has height 0, its children have height 1, and so on. Write a function that determines the sum of the heights of all nodes in a binary tree.