Algorytmy i struktury danych powtórzenie

Mamy posortowaną listę 128 nazwisk i chcemy ją przeszukać za pomocą algorytmu wyszukiwania binarnego. Ile maksymalnie prób zgadywania będzie trzeba wykonać?

• 3

• 6

• 7

• 14

Dane jest nazwisko i trzeba znaleźć numer telefonu osoby o tym nazwisku w książce telefonicznej, przedstaw czas wykonania algorytmu.

• O(log n)

• 17 minut

• Zależy od prędkości procesora

• O(n)

Wyobraźcie sobie, że tworzycie aplikację do przyjmowania zamówień od klientów w restauracji. Jedną z funkcji jest zapisywanie listy zamówień. Kelnerzy cały czas dodają zamówienia, a szefowie kuchni je pobierają i przygotowują potrawy. Czy do implementacji takiej kolejki wykorzystalibyście listę powiązaną, czy tablicę? Odpowiedź uzasadnij

(a)  

Answer explanation

Do struktury często trzeba wstawiać elementy (kelnerzy dodają zamówienia), a w tym listy powiązane są najlepsze. Nie trzeba niczego wyszukiwać ani mieć swobodnego dostępu do elementów (w czym najlepsze są tablice), ponieważ szefowie kuchni zawsze pobierają zamówienia po kolei

Programista przez przypadek napisał nieskończoną funkcję rekurencyjną. Dla każdego wywołania funkcji komputer przydziela pamięć na stosie. Co się dzieje ze stosem, gdy funkcja nigdy się nie kończy. Odpowiedź uzasadnij

(a)  

Answer explanation

Każdy program ma przydzieloną ograniczoną ilość miejsca na stosie wywołań. Kiedy program wyczerpie całą dostępną dla niego pamięć ulegnie awarii z powodu błędu przepełnienia stosu.

Czym jest stos?

(a)  

Answer explanation

Stos jest skończonym ciągiem elementów tego samego typu zorganizowanym według zasady LIFO

Czym jest kolejka

(a)  

Answer explanation

Kolejka jest skończonym ciągiem elementów tego samego typu zorganizowanym według zasady FIFO

Określ wagę najkrótszej drogi od startu do mety

(a)  

Answer explanation

8

Określ wagę najkrótszej drogi od startu do mety

(a)  

Answer explanation

60

Określ wagę najkrótszej drogi od startu do mety

(a)  

Answer explanation

Nie da się obliczyć najkrótszej drogi z powodu ujemnej wagi

Który z poniższych algorytmów jest zachłanny

• Sortowanie szybkie

• Wyszukiwanie binarne

• Algorytm Dijkstry