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_{2}, and `ones`

(6)
= true since 6 = 110_{2}.

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.