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 = 101₂, and ones(6) = true since 6 = 110₂.

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.