ASD ep 06 2003 2

30. Rozważmy tekst: aakkkkkttttorrmT

a.    Narysuj drzewo kodowe Huffinana odpowiadające temu tekstowi

b.    Odkoduj przy jego pomocy następujący ciąg: I00000II0001 .—

c.    Ile liści ma drzewo kodowe Huffinana odpowiadające tekstowi

zawierającemu dokładnie 10 różnych symboli? .......................

31.    Niech A będzie algorytmem o złożoności T(n) = 3”. Wykonanie tego algorytmu dla danych rozmiaru n=12

na pewnym komputerze zajmuje lm 2ls. Jaki jest maksymalny rozmiar zadania, które można rozwiązać przy pomocy tego algorytmu, na tym samym komputerze w ciągu 9s?.....................................

32.    Jaki jest koszt optymalnego algorytmu równoczesnego wyszukiwania elementu największego i najmniejszego w ciągu n elementowym?

0(lgn)    n²    (3/2)n-2    0(n lg n)    2n-3

33.    Oszacuj koszt wyszukiwania drugiego co do wielkości elementu w ciągu 64-elementowym algorytmem

Turniej? .................................................

34.    Dane są dwa stosy sl i s2 o n i m elementach odpowiednio.

a.    Jaki jest koszt połączenia stosów sl i s2 w jeden stos, jeśli do dyspozycji mamy jedynie operacje

charakterystyczne dla stosu: push, pop, top?..................................

b.    Zaznacz, które z wymienionych zdań jest prawdziwe w strukturze stosów?

i.    -.ernpty (pop(push(e,s))) => -iempty(s)

ii.    -.empty(s) => push(e,pop(s))= pop(push(e,s))

35.    Które z wymienionych problemów są nierozstrzygalne?

a.    znalezienie cyklu Hamiltona w grafie niezorientowanym

b.    problem stopu

c.    problem spełnialności formuły zdań

d.    problem komiojażera

36.    Rozważmy graf G (obok).

a.    Narysuj minimalne drzewo rozpinające grafu G stosując algorytm Kruskala.

b.    Ile krawędzi ma minimalne drzewo rozpinające grafu o 20 wierzchołkach?..............

37.    Dla grafu G z poprzedniego zadania wypisz kolejność w jakiej akceptowane są wierzchołki

grafu w algorytmie Dijkstry, jeśli źródłem jest wierzchołek A.......................................

38.    Wypisz wierzchołki podanego obok drzewa z zadania 25a w porządku

a.    inoreder..........................................

b.    preorder.........................................

39.    Zaznacz te zdania, które są Twoim zdaniem prawdziwe:

a.    Algorytm MergeSort i algorytm radixSort są oparte o zasadę dziel i zwyciężaj.

b.    Algorytm Kruskala minimalnego drzewa rozpinającego i algorytm konstruowania kodu Huffinana należą do klasy algorytmów zachłannych.

40.    Wskaż formuły, które są niezmiennikami pętli w następującym algorytmie :

{i:=0; s:=l; while i < n do s:=s*2; i:=i+l;od}

a.    i < n

b.    s = 2i + 1

c.    i < n+2

d.    s = 2'

******************************************************************

podpis studenta

4