ASD ITN e! 06 2002 A v2 2

2.

Z ^M T 7 3    «

G / \    2,3 3 3 3 355:

^ ®

9yVV jakiej kolejności odwiedzane są wierzchołki drzewa D, o którym mowa w zadaniu 11. jeśli zastosowano

10J Jaka jest zawartość stosu s po wykonaniu programu

(s:= push(s.2); e:= top(s); s:= push(s,e); s:= push(s.5);J, jeśli na początku stos był pusty? Wskazać szczyt stosu.

11. Niech D będzie drzewem BST, które otrzmano przez kolejne wkładanie, przy pomocy operacji insert, następujących elementów: 2. 5. 9, 8. 4, 3, 7. 6 do początkowo pustego drzewa. Wypisz elementy drzewa w

porządku inorder. Odp.:

Z    7

^z /³\

12. Który z następujących ciągów jest ciągiem etykiet drzewa BST odczytanym w porządku preorder? — 10, 8, 7, 9, 11, 2, 15-^>0 • 1, 5. 4, 2, 8, 12 - y

3

/

/

13. Co jest etykietą korzenia drzewa AVL. do ktorego włożono kolejno elementy 1.2.3.4,5.6. stosując algorytm /

insert?

Odp.:

Z-pr    -A

L

V

c

15.    Jeśli drzewo-kopiec ma 15 wierzchołków wewnętrznych, to iie ma liści?

Odp.:

14. Oszacuj z góry koszt utworzenia drzewa AVL o n węzłach? Odp.:

16.    Podaj przykład własności, która jest prawdziwa w każdej strukturze stosów ale nie jest prawdziwa w strukturze kolejek?

Odp.:

17. Jaki jest optmalny kod Huffinana dla następującego zbioru częstości występowania liter w pewnym tekście: a:20 b:50 c:40 d:7o’ e: 190?

Odp.:

18. Czy graf. który jest drzewem ma ścieżkę Hamiltona? Odp.:

19.    Jaką metodę konstrukcji algorytmu zastosowano w rozwiązaniu problemu najkrótszych ścieżek metodą Dijksty?

-    metodę 'zachłanną'

-    programowanie dynamiczne

-    metodę 'dziel i zwyciężaj'

20.    Czy istnieje algorytm wielomianowy sprawdzania, czy formuła achunku zdań jest tautologią?

Odp.: podpis snidenta.