GruDat 00 - Fiktiv Tenta

Uppgift 1

Antag att vi har en nxn-matris A med bara nollor och ettor som värden, där alla ettor kommer före nollorna på varje rad. Beskriv (med hjälp av pseudokod) en algoritm för att hitta vilken rad som innehåller flest ettor med en körtid som är O(n).

Uppgift 2

Vi har en enkellänkad lista där första elementet pekas ut av referensvariabeln head och varje element är av typen (klassen) Node. Node har en instansvariabel next som pekar ut listans nästa element och listan avslutas med en null-referens. Skriv ett kodavsnitt i Java som vänder listan baklänges.

Uppgift 3

Nämn en väsentlig fördel och en väsentlig nackdel med att använda dubbellänkade listor istället för enkellänkade.

Uppgift 4

Givet en vektor (array) deklarerad på detta sätt:

    String[] a;

Definiera en iterator-klass StringIterator i Java som kan användas för att stega igenom vektorn på följande sätt:

    Iterator iter = new StringIterator (a);
    while (iter.hasNext ()) {
      String s = (String) iter.next();
      System.out.println (s);
    }

Du behöver inte implementera Iterator-gränssnittets remove-metod utan bara de metoder som används i exemplet.

Uppgift 5

Antag att vi vill lagra ca 10000 namn i en hashtabell där kollisionerna hanteras med enkellänkade listor ("separate chaining").

a)
Hur många jämförelser behövs det i värsta fall för att hitta ett givet ord?
b)
Vad innebär det att en hashfunktion är bra?
c)
Skriv en bra hashfunktion som tar två parametrar: strängen och hashtabellens storlek (du kan förutsätta att denna är ett primtal).

Uppgift 6

Antag att vi har ett sorterat binärt träd. Beskriv hur man plockar bort en nod ur trädet, givet dess nyckel. Rita en exempelfigur som illustrerar de olika specialfall som kan uppträda.

Uppgift 7

Du har just fått anställning på statistikföretaget Kvartilen AB och ditt första uppdrag är att, för en reklamkampanjs räkning, ta reda på vem som är "Median-Svensson". Med detta menar man den person som har medianlönen bland alla som heter Svensson i efternamn. Företaget har hyrt in sig på en databastjänst med uppgifter om lönen för alla personer i Sverige, men man måste betala 99 öre för varje fråga man ställer till databasen. Programmet ställer frågor till databasen genom att anropa någon av funktionerna:

    getSize ()    // Ger antalet personer i databasen
    getName (i)   // Ger namnet på den i'te personen i databasen
    getSal (i)    // Ger lönen för den i'te personen
    getAdr (i)    // Ger adressen till den i'te personen

Posterna i databasen är sorterade i bokstavsordning efter efternamnet men därutöver finns det ingen bestämd ordning.

a)
Beskriv en algoritm för att få fram adressen till Median-Svensson som inte kostar onödigt mycket att köra.
b)
Din chef vill ha ett bättre kostnadsunderlag innan hon låter dig köra ditt program. Du inser att man måste ta reda på hur många personer som heter Svensson för att göra denna skattning. Beskriv (i pseudokodsform) en algoritm som gör detta på ett effektivt sätt.
c)
Berätta vilka argument du kan lägga fram för att övertyga din chef om att det kommer att vara väldigt billigt att köra ditt andra program.

Uppgift 8

IT-säkerhetsföretaget Paranoiddata säljer en tjänst som innebär att man letar igenom hela hårddiskar efter någon sträng som kunden tycker känns angelägen. Telefonaktiebolaget Petterson har beslutat sig för att sluta med en viss produktkategori och anlitar därför Paranoiddata för att hitta alla förekomster av strängen "mobiltelefon" på sina hårddiskar.

Föreslå en algoritm som Paranoiddata kan använda för detta uppdrag och beskriv hur algoritmen arbetar sig igenom strängen "växelsystemunderhållnummerskivalurmobilnät".