(a) catenate(S1, S2)
      if first[S1] = NIL
         then first[S1] <- first[S2]
         else if first[S2] != NIL
                 then p <- first[S1]
                      while next[p] != NIL do
                         p <- next[p]
                      next[p] <- first[S2]
      first[S2] <- NIL

aika O(|S1|), tila O(1)
(merkintä |S1| tarkoittaa S1:n pituutta eli merkkien lukumäärää)

Yleisimpiä virheitä: ei varauduta siihen, että S1 on tyhjä; mennään
S1:n viimeisen alkion ohi. Huom. S2:n alkioita ei tarvitse kopioida.

(b) add(S, i, x)
      if i = 1
         then m <- uusi Merkkisolmu
              merkki[m] <- x
              next[m] <- first[S]
              first[S] <- m
              return true
         elseif first[S] = NIL or i <= 0
         then return false
         else p <- first[S]
              while next[p] != NIL and i > 2 do
                 p <- next[p]
                 i <- i-1
              if i > 2
                 then return false
                 else m <- uusi Merkkisolmu
                      merkki[m] <- x
                      next[m] <- next[p]
                      next[p] <- m
                      return true

aika O(|S|), tila O(1)

Yleisimpiä virheitä: ei varauduta siihen, että S on tyhjä; tapaus i=1
ei onnistu; lisäys ei osu kohdalleen; loppuun ei voi lisätä; mennään
S:n viimeisen alkion ohi.

(c) replace(S, x, y)
      p <- first[S]
      while p != NIL do
         if merkki[p] = x
            then merkki[p] <- y
         p <- next[p]

aika O(|S|), tila O(1)

Yleisimpiä virheitä: ei varauduta siihen, että S on tyhjä; viimeistä
merkkiä ei tutkita.

Pisteytys (max): pseudokoodit (a) 1, (b) 3, (c) 1; aika- ja
tilavaativuudet 1
(yhteensä 6 pistettä).

Erityishuomautus aikavaativuuksista: hyvin monessa vastauksessa
vaativuuksiksi oli ilmoitettu O(n) kertomatta, mikä "n" on. Näin ei
saisi tehdä, sillä eihän "O(n)" tarkoita yhtään mitään, jos ei
tiedetä, mitä "n" tarkoittaa. Jos siis sanoo "aikavaativuus on O(n)",
niin pitää sanoa myös, mitä "n" tarkoittaa, esim. kohdassa (c):
"... missä n on merkkijonon S merkkien lukumäärä".