ASD ITN e! 06 2002 B v2 2

ty’.- intyć)- (c_V,t) e .    - {:KS l- [Cy) ' ^ ¹

10. Jaka jest zawartość kolejki q po wykonaniu programu

(q:= in(q,2); e:= frrst(q); q:= in(q,3); q:= in(in(q,e),5):}, jeśli na początku kolejka była pusta? Wskazać początek kolejki. Odp.:

~ Cfy 3)

11.    Niech D będzie drzewem BST. które otrzmano przez kolejne wkładanie, przy pomocy operacji insert,

następujących elementów: 5„3. 2. 8. 4, 9, 7, ó do początkowo pustego drzewa. Wypisz elementy drzewa w porządku inorder.    5\    - „

Odp,'    3 ' iSv    „

^,‘1,

12.    Który z następującymi ciągów jest ciągiem etykiet pewnego drzewa BST odczytanym w porządku preorder?

-*+5.2. 1,3, 4, 6, 7, 8'    ‘    ,^_f

— 1,4,2,6, 7,3,8    '    Z. k-,

^A K%

13. Co jest etykietą korzenia drzewa AVL. do którego włożono kolejno elementy 3. 4, 5, 7, 8. 9 , stosując algorytm insert?

Odp.:    "^A

A

14. Jaka jest minimalna, a jaka maksymalna wysokość drzewa AVL o 7 wierzchołkach?/\ S\ S

^0dp" Wl<\x “"J) YYlirt - 2 ,

15. Jaka jest wysokość drzewa-kopca. jeśli odpowiadająca mu tablica-kopiec ma 512 elementów? Odp.:

16. Jakie warunki muszą spełniać elementy tablicy T, jeśli została ona użyta jako reprezentacja kopca? Odp.:

17. Majac kod Huffmana a=00, b=01. c=l odszyfruj tekst: 0000001101. Odp.:

18. Czy- każdy graf pełny ma ścieżkę Hamiltona? Odp.:

19.    Jaką metodę konstrukcji algorytmu zastosoyyano w rozyyiązaniu problemu kompresji danych metodą Huffmana?

-    metodę zachłanną

-    programowanie dynamiczne

-    metodę dziel i rządź

20.    Czv problem stopu dla algorytmów jest problemem rozstrzygalnym?

Odr.: * podpis studenta.