Programming I, Winter 2017-8
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
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")
2. Write a function
ones that takes an
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
= true since 6 = 1102.
3. Write a function
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
var a: array[1..5] of integer = (3, 4, 5, 6, 7) function odd(i: integer): boolean; begin exit(i mod 2 = 1); end;
most(a, @odd) = true.
4. Write a function
sub that takes two
linked lists of integers
returns true iff any subsequence of nodes in s is identical to t. For
s = 3 → 4 → 2 → 7 → 8 →
t = 2 → 7 →
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.