Lekcja_05 - podstawowe struktury danych1. Stosy i Kolejki2. DrzewaWyjścieSTRUKTURA STOSÓW1.(1p) W której strukturze operacje wstawiania i usuwania można wykonywać przemiennie.w strukturze stosóww strukturze kolejek2. (1p) Która z wymienionych formuł jest prawdziwa w strukturze stosów?empty(push(x,s)) top(push(top(s),s)) = enot empty(s) =>push(e, pop(s)) = snot empty(s) => top(pop(push(e,s))) = top(s)3. (1p) Która z wymienionych formuł nie jest prawdziwa w strukturze kolejek?out(in(x,q)) = qempty(q) => first(in(x,in(y,q))) = y 4. (1p) Do kolejki q1 włożono kolejno liczby 1,2,3,..., n , a do kolejki q2 - kolejno elementy n+1, n+2,..., n+m. Jaki jest minimalny koszt utworzenia kolejki zawierającej wszystkie elementy 1,2,..., n, n+1,...,n+m w takim właśnie porządku (tzn. liczba n+m jest na końcu kolejki wynikowej)? W algorytmie wolno użyć tylko operacji in, out, first, empty struktury kolejek. rzędu m operacji in, out, first, empty co najmniej m+n operacji in, out, first, empty dokładnie m*n operacji in, out, first, empty 5.(1p) Do stosu s1 włożono kolejno liczby 1,2,3,..., n , a do stosu s2 - kolejno liczby n+1, n+2,..., n+m. Jaki jest minimalny koszt utworzenia stosu zawierającego wszystkie elementy 1,2,..., n, n+1,...,n+m w takim właśnie porządku (tzn. liczba n+m jest na dnie stosu wynikowego, a 1 jest na szczycie stosu)? W algorytmie wolno użyć tylko operacji push, pop, top, empty struktury kolejek. co najwyżej m operacji push, pop, top,dokładnie 3(n+m) operacji push, pop, top,rzędu n*m operacji push, pop, top,6.(1p) Oszacuj wielkość stosu argumentów w algorytmie obliczania wartości wyrażenia algebraicznego, jeśli zastosowano go do poprawnego wyrażenia zawierającego 20 nawiasów otwierających? Stos zawierać może co najwyżej 10 argumentówStos musi zawierać 2*20 elementówStos zawiera co najwyżej 21 elementówWysokość stosu nie zależy od liczby nawiasów otwierającychStos zawiera co najwyżej 20 argumentówOdpowiedzi do pytań:  Wyniki