581325-0 Data strukturer, första deltenten 12.3.2001/AW

1. Förklara exakt och åskådliggör vad som menas med funktionsklasserna O(f(n)) och hur de kan användas för att beskriva algoritmers exekveringstid. Ge exempel på algoritmer som tillhör klasserna O(1), O(log n), O(n), O(n²) och O(2ⁿ). Motivera ditt svar.

                                                                 (7 poäng)
   
   

2. Ett tåg presenteras som en dubbel-länkad lista. Lokomotivet och vagnarna är strängar. Programmera klassen Tåg med operationerna:
   • public Tåg(String lok)
     skapar ett tåg med endast loket
   • public void tilläggBaktill(String vagn)
     lägger till en vagn bakom loket
   • public Tåg fäst(Tåg till)
     fäster ett annat tågs vagnar efter tåget; det andra tågets vagnar lösgörs från det gamla loket; metoden ger ett längre tåg; loket tas alltså inte med från det gamla tåget.
   • public Tåg lösgörÄnda(int vagnNummer, String lok)
     lösgör slutändan av tåget, med början från vagnNummer nummer vagn, som blir ett eget tåg vars lok ges som parameter; metoden ger värdet av tåget inklusive loket, som har lösgjorts från slutändan; även det ursprungliga tåget förändras alltså.
   • public int vilken(String vagn, int varifrånFramåt)
     ger som sitt värde ordningstalet för tågets första vagn om man börjar sökningen från den vagn vars ordningstal ges som parameter; vagnarna är numrerade med början från ett.
   • public int längd()
     antalet vagnar i tåget
   • public String toString()
     skapar tågets teckensträngpresentation

   Specifiera hur metoderna beter sig även i händelse av fel.

   Skapa med hjälp av klassen Tåg biblioteksklassen Redskap åt förmannen på stationen. Klassen bör innehålla följande redskap:

   • räkna antalet vagnar av ett visst namn i tåget (t.ex. "sovvagn")
   • ta ut vagnar av ett givet namn från tåget (t.ex. "container")
   • byt om ordningen på vagnarna till den motsatta (för återresan... :-)
   OBS: redskapen skall implementeras endast med hjälp av de publika metoderna ovan.

                                                                 (7 poäng)
   
   

3. Specifiera begreppen lista, stack och kö som abstrakta datatyper.

                                                                 (4 poäng)
   
   
   

4. Ett binärträd föreställer ett släktträd där roten består av 'jag'. Rotens subträd är 'mamma', 'pappa' osv. Specifikationen av trädet börjar så här:

      public class FamiljeTrad {
   
        private class Slaktning {
          private String namn;
          private int födelseår;
          private Slaktning mamma, pappa;
        }
   
        private Slaktning rot;;
   
        public FamiljeTrad() {
          rot = null;
        }
        ...
   
   

   Programmera klassens metoder (specifiera funktionen också vid fel).
   • public int äldstaAnor() ger värdet av den längsta sökvägen mellan 'jag' och en anfader eller -anmoder.
   • public String släktskap(String namn) ger släktförhållandet mellan 'jag' och anfadern eller -moderni i formen "mors fars fars mors mors fars mors mor". Du kan utgå ifrån att personerna i trädet har unika namn.
   • public void utmata ÄldstaFöderskan() utmatar namnet på den anmoder som har varit äldst då hon fött sitt barn. Om personen inte är unik matas alla de äldsta ut.

                                                                 (7 poäng)