Informatyka UJ forum

Azhag

wiadomo juz kiedy bedzie??

ma ktos jakies inne egzaminy/ przyklady ?

ASD 2.
Przykładowe pytania testowe

W rekurecjyjnie wywołującej się procedurze (mamy na myśli standardowe algorytmy zamiany na iterację)
(a) może być tylko jedna rekurencja ogonowa
(b) może być wiele rekurencji ogonowych, ale tylko jedną można zamienić na iterację ze stosem
(c) może być wiele rekurencji ogonowych, ale tylko jedną można zamienić na iterację bez stosu
(d) może być wiele rekurencji ogonowych, ale tylko dwie można zamienić: jedną na iterację ze stosem, drugą bez stosu
(e) żadne z pozostałych nie jest prawdziwe
==odp: e.

Graf niezorientowany ma następującą reprezentację listową:
L[a]=(c,b), L[b]=(d,e,c,a), L[c]=(a,b), L[d]={e,b), L[e]=(b,d)
Wykonujemy algorytm znajdowania dwuspójnych składowych - start od a, kolejność rozpatrywania jak w listach.
Funkcja Low[v] dla wiechołków a,b,c,d,e przyjmie ostateczne wartości odpowiednio:
(a) 1,3,2,4,5
(b) 1,1,1,3,3
(c) 1,1,1,1,1
(d) 5,4,3,2,1
(e) 1,1,2,3,4
odp: b.

Podczas obliczania wartości funkcji KMP[11] dla wzorca p=abababababc iteracja j:=KMP[j] wykona się
(a) 1 (b) 2 (c) 4 (d) 5 (e) 10 razy.
odp: d.

W metodzie programowania dynamicznego rozwiązanie dowolnego podzadania
(a) obliczane jest tylko raz i wykorzystywane co najwyżej raz
(b) obliczane jest na ogół wielokrotnie i nie zawsze wykorzystywane
(c) obliczane jest tylko raz i wykorzystywane dowolnie wiele razy
(d) modyfikowane jest podczas rozwiązywania większego podzadania
(e) może pozostać nieoptymalne do końca obliczeń
odp.: c.

Problem NP-zupełny to problem
(a) najłatwiejszy w klasie NP
(b) dla którego nie ma algorytmu
(c) który transformuje się wielomianowo do każdego innego problemu w NP
(d) tak samo trudny obliczeniowo jak problem komiwojażera
(e) tak samo trudny obliczeniowo jak sortowanie
odp. d.
-------------------------------------------------

hansu

7 lutego w srode na kampusie o 8:30.

Te przykladowy egzamin troche chyba nie teges, bo sa na przyklad pytania o dwuspojne skladowe, a to bylo na ASD1. Poza tym mam wrazenie ze nie wszystkie odpowiedzie sa poprawne :]

kafex

Fidel