PYTANIA
1. Dane są funkcje sortujące
void sort1 (Item a[], int l, int r)
{
for(int i=l;i<r;i++)
{
int min=i;
for (j=i+1;j<=r;j++)
{
if(a[j]<a[min])
{
min=j;
exch(a[i],a[min];
}
}
}
}
void sort2 (Item a[], int l, int r)
{
int i;
for (i=r;i>l;i--)
{
compexch(a[i-1],a[i])
}
for (i=l+2;i<=r;i++)
{
int j=i;
Item v=a[i];
while (v<a[j-1])
{
a[j]=a[j-1];
j--;
}
a[j]=v;
}
}
void sort3 (Item a[], int l, int r)
{
for (int i=l;i<r;i++)
{
for(int j=r;j>i;j--)
{
compexch(a[j-1],a[j]);
}
}
}
exch(a,b) zamienia a i b
compexch(a,b) wywołuje exch(a,b) gdy a>b
zamiana elementów = 3 przypisania
1.1 Dane są dwa n-elementowe ciągi
a) 2,2,2,...,2,1 (n-1 2 i 1 na końcu)
b) n,1,2,3,...,n-1
Podać liczbę porównań i przypisań dla obydwu ciągów przy użyciu każdej z
metod sortowania.
1.2 Podać minimalną i maksymalną liczbę porównań elementów w metodach.
1.3 Które z metod są stabilne, czy quicksort jest stabilny.
1.1-1.2 n^2
1.3 Mojim zdaniem stabilne są -sort2( sortowanie przez wstawianie) i sort3 (bubblesort). Quicksort nie jest stabilny.
2. Dane jest drzewo
2.1 Wypisać kolejność wierzchołków przy przeszukiwaniu drzewa
a) w głąb
b) w szerz
2.2 Dodać węzeł o wartości 5,zrównoważyć przy jaknajmniejszej
liczbie rotacji, narysować, podac pary węzłów które uległy rotacji i wypisać kierunki rotacji
2.3 Dodać węzeł o wartości 9,zrównoważyć przy jaknajmniejszej liczbie rotacji, narysować, podac pary węzłów które uległy rotacji i wypisać kierunki rotacji
Wysokośc drzewa to:
2.Drzewa.
2.2
Węzeł zawędruje na prawą stronę po 4 i mojim zdaniem te drzewo jest już zrównoważone
W 2.2 myślę, że treba sobie przerysować drzewo, dodać wskazany węzeł tak, jak się dodaje w BST, a później zrównoważyć sposobem - wykład 8 slajd 16, np. lewo(x,y), to jest drzewo AVL - nie ma tej informacji w teście na forum.
moje odpowiedzi do 2:
2.1
a) w głąb - 3, 2, 1, 2, 3, 6, 4, 6, 8, 7, 8, 10, 8, 6, 3
b) w szerz - 3, 2, 6, 1, 4, 8, 7, 10
2.2 węzeł "5" umieszczamy z prawej strony "4" - w BST dodawane węzły zawsze są liścmi(liściami?)
i jesz od razu zównoważone
2.3 "9" dodajemy z lewej strony "10", i rotacja lewo(3,6) - "6" staje się korzeniem
wysokość po zrównoważeniu = 3
3. Dany jest graf
3.1 Wypisać kolejność wierzchołków przy przeszukiwaniu grafu
a)w głąb
b) w szerz
3.2 Stosując algorytm Kruskala wyznaczyć (w odpowiedniej kolejności)
krawędzie minimalnego drzewa rozpinającego.
Sumaryczna waga drzewa wynosi ...
3.3 Zastosować algorytm Dijkstry w celu wyznaczenia odległości wierzchołka
A od pozostałych.
3.4 Dla węzłów B÷G podaj węzły poprzedzające je w najkrótszej ścieżce z A:
P[B]= P[C]= P[D]= P[E]= P[F]= P[G]=
zad 3 Grafy
z 3.1 //wyklad 9 Smolczyka slajdy 10-15 ( dla wyjasniania)
a) w głąb A B C E D F D G E C B A
A B C E D F D G D E C B A
Tu jest chyba błąd. Zobacz czy nie powinno być A B C E D F D G D E C B A.
Stos:
A
AB
ABC
ABCE
ABCED
ABCEDF
ABCED
ABCEDG
ABCED
ABCE
ABC
AB
A
b) w szerz A B G C D F E
z 3.2 //wykład 6 Smolczyka slajdy 12-14
|CB| |EF| |CE| |DF| |AB| |AG|
Sumaryczna waga drzewa wynosi: i tu nie jestem pewien czy chodzi o ilość gałęzi czyli 6 czy sumę kosztów ze wszystkich 6 gałęzi, może ktoś z Gwardji się wypowie;) Mi się wydaje że chodzi chyba właśnie o tą sumę czyli 12,5
z 3.3 //to może być źle wiec sprawdźcie to dokladnie -wykład 6 Smolczyka slajdy 18- 19
T |
D[A] |
D[B] |
D[C] |
D[D] |
D[E] |
D[F] |
D[G] |
{B,C,D,E,F,G} |
0 |
2 |
∞ |
∞ |
∞ |
∞ |
4 |
{C,D,E,F,G} |
0 |
2 |
3 |
10 |
∞ |
7 |
4 |
{D,E,F,G} |
0 |
2 |
3 |
10 |
5 |
6 |
4 |
{D,E,F} |
0 |
2 |
3 |
10 |
5 |
6 |
4 |
{D,F} |
0 |
2 |
3 |
10 |
5 |
6 |
4 |
{D} |
0 |
2 |
3 |
8 |
5 |
6 |
4 |
{} |
0 |
2 |
3 |
8 |
5 |
6 |
4 |
z 3.4
P[B]=0(nic) P[C]=B P[D]=B,C,F P[E]=B,C P[F]=B,C P[G]=0(nic)
3.4 moim zdaniem P[B] = A, P[G] = A
najkrótsza ścieżka z A do B to droga prosto z A do B, a węzłem porzedzający B jest A, a nie 0/nic jak piszesz, bo to by wskazywało, że go nie ma.
4. Notacje
4.1 Zapisz w odwrotnej notacji polskiej (RPN) wyrażenie:
((a+t)*((b+(a+c))^(c+a)))
4.2 Zapisz w notacji infiksowej i oblicz wartość wyrażenia zapisanego w
odwrotnej notacji polskiej
3 4 2 * 5 1 - 2 ^ / +
4.1 Zapisz w odwrotnej notacji polskiej (RPN) wyrażenie:
((a+t)*((b+(a+c))^(c+a)))
Odp. at+bac++ca+^*
4.2 Zapisz w notacji infiksowej i oblicz wartość wyrażenia zapisanego w
odwrotnej notacji polskiej
3 4 2 * 5 1 - 2 ^ / +
Odp.3+4*2/(5-1)^2
5. Zastosuj rozszerzony algorytm Euklidesa w celu wyznaczenia najwiekszego wspolnego dzielnika podanych liczb oraz przedstawienia go jako całkowitoliczbowej kombinacji tych liczb:
NWD(123,321)= 3 = 47*123+(-18)*321
NWD(63,77)= 7 = 5*66+(-4)*77
Wyszukiwarka