Testangabe
Results 1 to 4 of 4

Thread: Testangabe

  1. #1

    Title
    Principal
    Join Date
    Feb 2002
    Location
    wien
    Posts
    59
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Testangabe

    für alle, die nicht da waren:
    testangaben, soweit ich sie mir gemerkt hab:

    1.a) zeigen oder widerlegen:
    f(n) = O(g(n)²) => f(n) = Omega(g(n)

    1.b) f(n) = { n³ - 0.3n² + 2.7n für n >= 1000
    n^4 für n<1000
    zeigen oder widerlegen: f(n) = Theta(n³)


    2.a) <12,55,3,66,54,552> (kA, beliebige folge eben)
    selection sort durchführen

    2.b1) gegeben: absteigend soriterte folge
    ist insertion oder merge sort bessser, wenn die ausgabe auch absteigend sortiert sein soll? angabe mittels Theta
    2.b2) gesucht: av.Zeitaufwand für insert&merge

    3.a) gegeben: absteigend sortierte doppelt verkettete zyklische liste.
    gesucht: algo zum einfügen eines elementes incl. skizze

    3.b) Theta notation für diesen algorithmus im best, worst und av. case

    a.A.o.G

    lg peter

  2. #2
    Zentor's Avatar
    Title
    CO-Administrator
    Join Date
    Dec 2001
    Location
    Wien???
    Posts
    1,156
    Thanks
    2
    Thanked 9 Times in 6 Posts
    bei meiner Gruppe wars:
    1.a) Zeige/wiederlege
    f(n) = Theta(n^4)
    f(n) = n^4________für n prim
    _____n^4-nlogn___für n nicht prim
    1.b) Zeige/wiederlege aus f(n) = Sigma(g(n)) folgt f(n) = O(2g(n))
    2.a) irgendeine Folge mittels Insertionsort sortieren
    2.b) Was bedeutet stabil bei Sortierverfahren, sind Quicksort und Selectionsort stabil/warum ja/nicht
    3.a) einfügen eines Elementes an die richtige Stelle in einer aufsteigend sortierten eínfach verketteten Liste in Pseudocode schreiben
    3.b) Laufzeit davon für Bestcase/WorstCase/AvgCase in Theta Notation
    Last edited by Zentor; 17-04-2002 at 17:25.

  3. #3
    #!/usr/bin/perl's Avatar
    Title
    Elite
    Join Date
    Jan 2002
    Posts
    291
    Thanks
    0
    Thanked 1 Time in 1 Post
    meinst du nicht einfach verkettet statt einelementig?
    this is Unix land. In silent nights, you can hear Windows machines reboot...

  4. #4
    Zentor's Avatar
    Title
    CO-Administrator
    Join Date
    Dec 2001
    Location
    Wien???
    Posts
    1,156
    Thanks
    2
    Thanked 9 Times in 6 Posts
    oh, natürlich, sorry habs schon oben ausgebessert
    mfg Zentor

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •