Programming I, Winter 2017-8
Practice Exam - Solutions

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.

// iterative solution

function words(s: string): integer;
var
  i, n: integer;
begin
  if s = '' then exit(0);
  if s[1] = ' ' then n := 0 else n := 1;

  for i := 1 to length(s) - 1 do
    if (s[i] = ' ') and (s[i + 1] <> ' ') then
      n := n + 1;
  words := n;
end;

// recursive solution

function words(s: string): integer;
var
  w: integer;
  
begin
  if length(s) = 1 then
    if s[1] = ' ' then exit(0) else exit(1);
    
  w := words(s[2 .. length(s)]);
  if (s[1] <> ' ') and (s[2] = ' ')
    then exit(w + 1) else exit(w);
end;

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₂.

// iterative solution

function ones(i: integer): boolean;
begin
  while i > 0 do
    begin
      if i mod 4 = 3 then exit(true);
      i := i div 2;
    end;
  exit(false);
end;

// recursive solution

function ones(i: integer): boolean;
begin
  if i = 0 then exit(false);
  exit((i mod 4 = 3) or ones(i div 2));
end;

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.

// iterative solution

type
  cond = function(i: integer): boolean;

function most(a: array of integer; c: cond): boolean;
var
  count: integer = 0;
  i: integer;
begin
  for i in a do
    if c(i) then count := count + 1;
  exit(count * 2 >= length(a));
end;

// recursive solution

type
  cond = function(i: integer): boolean;

function count(a: array of integer; c: cond): integer;
var
  i: integer;
begin
  if c(a[0]) then i := 1 else i := 0;
  
  if length(a) = 1 then exit(i)
  else exit(i + count(a[1 .. high(a)], c));
end;  

function most(a: array of integer; c: cond): boolean;
begin
  exit(count(a, c) * 2 >= length(a));
end;

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.

// iterative solution

type
node = record
  i: integer;
  next: ^node;
end;
pnode = ^node;

function startsWith(p, q: pnode): boolean;
begin
  while q <> nil do
    begin
      if (p = nil) or (p^.i <> q^.i) then
        exit(false);
      p := p^.next;
      q := q^.next;
    end;
  exit(true);
end;

function sub(p, q: pnode): boolean;
begin
  while true do
    begin
      if startsWith(p, q) then
        exit(true);
      if p = nil then exit(false);
      p := p^.next;
    end;
end;

// recursive solution

type
  node = record
    i: integer;
    next: ^node;
  end;
  pnode = ^node;

function startsWith(p: pnode; q: pnode): boolean;
begin
  if q = nil then exit(true);
  exit((p <> nil) and (p^.i = q^.i) and startsWith(p^.next, q^.next));
end;

function sub(p: pnode; q: pnode): boolean;
begin
  exit(startsWith(p, q) or ((p <> nil) and sub(p^.next, q)));
end;

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.

type
  treeNode = record
    i: integer;
    left, right: ^treeNode;
  end;
  pTreeNode = ^treeNode;

function height1(t: pTreeNode; h: integer): integer;
begin
  if t = nil then exit(0);
  exit(h + height1(t^.left, h + 1) + height1(t^.right, h + 1));
end;

function height(t: pTreeNode): integer;
begin
  exit(height1(t, 0));
end;