24.01.2014, 14:54
1. Jaka jest głębokość wywołań rekurencyjnych w algorytmie sortowania przez scalanie, zastosowanym do ciągu o 24 elementach?
a ) 10
b ) 4
c ) 6
d ) 5
2. Co to jest wartownik?
a ) Element na początku ciągu, który kontroluje dostęp do ciągu.
b ) Zmienna w programie, która służy do przeglądania wszystkich instrukcji w programie.
c ) Element, który służy do zatrzymywania przeszukiwania na końcu ciągu.
d ) Zmienna, która pilnuje końca programu.
3. Jaka jest najmniejsza liczba porównań potrzebnych do uporządkowania 4 liczb?
a ) 6
b ) 5
c ) 3
d ) 4
4. Ile porównań wykonuje algorytm porządkowania przez wybór, zastosowany do ciągu uporządkowanego, złożonego z 1000 elementów?
a ) 999
b ) żadnego
c ) tyle, ile wykonuje na ciągu nieuporządkowanym
d ) 1000
5. Ile porównań zostanie wykonanych podczas scalania następujących dwóch ciagów:
1 2 5 7 12 15 20 30
4 6 10 11
a ) 13
b ) 10
c ) 8
d ) 12
6. Jaką wartość będzie miała zmienna s po wykonaniu następującego ciągu instrukcji:
int s = 0;
int z = - 1;
for(int i = 1; i< 100; i++)
if (z > 0){ s = s + i; z = - z; }
else z = - z;
a ) s będzie sumą liczb nieparzystych między 1 i 100
b ) s = 0
c ) s będzie sumą wszystkich liczb między 1 i 100
d ) s będzie sumą liczb parzystych między 1 i 100
7. Ile porównań należy wykonać, aby znaleźć największą liczbę wśród 100 uporządkowanych niemalejąco liczb?
a ) 99
b ) 1
c ) 100
d ) 0
8. Jaką wartość będzie miała zmienna s po wykonaniu następującego ciągu instrukcji:
int s = 0;
for (int i = 1; i < 10; i++) s = i - s;
a ) s = 0
b )s = 10
c ) s = 5
d )s = 15
9. Która z poniższych metoda sortowania wykonuje w najgorszym przypadku mniej niż n2 porównań, gdzie n jest liczbą sortowanych elementów.
a ) Sortowanie przez scalanie
b ) Sortowanie szybkie
c ) Sortowanie przez wybór
d ) Algorytm bąbelkowy.
10. Która z metod sortowania, do wykonywania obliczeń potrzebuje dodatkowej pamięci, o wielkości zbliżonej do długości porządkowanego ciagu, na przechowywanie wyników pośrednich ?
a ) MergeSort
b ) BubbleSort
c ) SelectionSort
d ) QuickSort
11. Który z poniższych algorytmów nie jest algorytmem optymalnym, czyli nie jest możliwie najszybszym algorytmem dla problemu, który rozwiązuje?
a ) Porządkowanie przez wybór.
b ) Przeszukiwanie zbioru uporządkowanego metodą połowienia.
c ) Algorytm jednoczesnego znajdowania minimum i maksimum.
d ) Algorytm znajdowania najmniejszej liczby w ciągu liczb.
12. Ile wynosi suma kolejnych liczb naturalnych od 1 do 50?
a ) 2500
b ) 1500
c ) 1275
d ) 500
13. Jaka jest najmniejsza liczba porównań wykonywanych przez najszybszy algorytm porządkowania ciagów uporządkowanych w przypadku, gdy ciąg jest uporządkowany i ma n elementów?
a ) n
b ) 2n
c ) 0
d ) n - 1
14. Jaka jest najmniejsza liczba porównań potrzebnych do znalezienia danej liczby w uporządkowanym zbiorze złożonym z 250 liczb?
a ) 8
b ) 10
c ) 12
d ) 7
15. Jak będzie wyglądał następujący ciag elementów po zastosowaniu do niego pierwszego kroku szybkiego algorytmu sortowania. Zakładamy, że pierwszy element tego ciagu służy do podziału tego ciagu na dwa podciagi:
6 5 7 9 2 4 10 1 8
a ) 2 5 7 9 6 4 10 1 8
b ) 1 2 4 5 6 9 7 10 8
c ) 2 5 1 4 6 9 10 7 8
d ) 1 2 4 5 6 7 8 9 10
16. Jaką wartość będzie miała zmienna k po wykonaniu następującego ciągu instrukcji:
for(int i = 1; i < 100; i++)
if (i == a[i])k = i;
a ) k = 0
b ) k może być nieokreślone
c ) k będzie równe ostatniemu elementowi w ciągu a, który jest równy swojemu indeksowi
d ) k = 100
17. Ile pytań wystarczy zadać, by w grze w odgadywanie liczby odnaleźć liczbę ukrytą w przedziale [125, 182]?
a ) 12
b ) 8
c ) 5
d ) 6
18. Jaka jest najmniejsza liczba meczów, jaką musi rozegrać 16 tenisistów, aby wyłonić najlepszego i drugiego najlepszego zawodnika turnieju?
a ) 17
b ) 18
c ) 29
d ) 16
19. Który z Polskich matematyków inicjował prace dotyczące poszukiwania i porządkowania elementów?
a ) Jan Łukasiewicz
b ) Hugo Steinhaus
c ) Donald Knuth
d ) Stanisław Ulam
20. Jaka jest najmniejsza liczba porównań wykonywanych przez najszybszy algorytm porządkowania ciagów uporządkowanych w przypadku, gdy ciąg jest uporządkowany i ma n elementów?
a ) 2n
b ) 0
c ) n - 1
d ) n
21. Jaka jest najmniejsza liczba porównać potrzebnych do znalezienia jednocześnie najmniejszej i największej liczby wśród 35 nieuporządkowanych liczby?
a ) 67
b ) 70
c ) 51
d ) 36
a ) 10
b ) 4
c ) 6
d ) 5
2. Co to jest wartownik?
a ) Element na początku ciągu, który kontroluje dostęp do ciągu.
b ) Zmienna w programie, która służy do przeglądania wszystkich instrukcji w programie.
c ) Element, który służy do zatrzymywania przeszukiwania na końcu ciągu.
d ) Zmienna, która pilnuje końca programu.
3. Jaka jest najmniejsza liczba porównań potrzebnych do uporządkowania 4 liczb?
a ) 6
b ) 5
c ) 3
d ) 4
4. Ile porównań wykonuje algorytm porządkowania przez wybór, zastosowany do ciągu uporządkowanego, złożonego z 1000 elementów?
a ) 999
b ) żadnego
c ) tyle, ile wykonuje na ciągu nieuporządkowanym
d ) 1000
5. Ile porównań zostanie wykonanych podczas scalania następujących dwóch ciagów:
1 2 5 7 12 15 20 30
4 6 10 11
a ) 13
b ) 10
c ) 8
d ) 12
6. Jaką wartość będzie miała zmienna s po wykonaniu następującego ciągu instrukcji:
int s = 0;
int z = - 1;
for(int i = 1; i< 100; i++)
if (z > 0){ s = s + i; z = - z; }
else z = - z;
a ) s będzie sumą liczb nieparzystych między 1 i 100
b ) s = 0
c ) s będzie sumą wszystkich liczb między 1 i 100
d ) s będzie sumą liczb parzystych między 1 i 100
7. Ile porównań należy wykonać, aby znaleźć największą liczbę wśród 100 uporządkowanych niemalejąco liczb?
a ) 99
b ) 1
c ) 100
d ) 0
8. Jaką wartość będzie miała zmienna s po wykonaniu następującego ciągu instrukcji:
int s = 0;
for (int i = 1; i < 10; i++) s = i - s;
a ) s = 0
b )s = 10
c ) s = 5
d )s = 15
9. Która z poniższych metoda sortowania wykonuje w najgorszym przypadku mniej niż n2 porównań, gdzie n jest liczbą sortowanych elementów.
a ) Sortowanie przez scalanie
b ) Sortowanie szybkie
c ) Sortowanie przez wybór
d ) Algorytm bąbelkowy.
10. Która z metod sortowania, do wykonywania obliczeń potrzebuje dodatkowej pamięci, o wielkości zbliżonej do długości porządkowanego ciagu, na przechowywanie wyników pośrednich ?
a ) MergeSort
b ) BubbleSort
c ) SelectionSort
d ) QuickSort
11. Który z poniższych algorytmów nie jest algorytmem optymalnym, czyli nie jest możliwie najszybszym algorytmem dla problemu, który rozwiązuje?
a ) Porządkowanie przez wybór.
b ) Przeszukiwanie zbioru uporządkowanego metodą połowienia.
c ) Algorytm jednoczesnego znajdowania minimum i maksimum.
d ) Algorytm znajdowania najmniejszej liczby w ciągu liczb.
12. Ile wynosi suma kolejnych liczb naturalnych od 1 do 50?
a ) 2500
b ) 1500
c ) 1275
d ) 500
13. Jaka jest najmniejsza liczba porównań wykonywanych przez najszybszy algorytm porządkowania ciagów uporządkowanych w przypadku, gdy ciąg jest uporządkowany i ma n elementów?
a ) n
b ) 2n
c ) 0
d ) n - 1
14. Jaka jest najmniejsza liczba porównań potrzebnych do znalezienia danej liczby w uporządkowanym zbiorze złożonym z 250 liczb?
a ) 8
b ) 10
c ) 12
d ) 7
15. Jak będzie wyglądał następujący ciag elementów po zastosowaniu do niego pierwszego kroku szybkiego algorytmu sortowania. Zakładamy, że pierwszy element tego ciagu służy do podziału tego ciagu na dwa podciagi:
6 5 7 9 2 4 10 1 8
a ) 2 5 7 9 6 4 10 1 8
b ) 1 2 4 5 6 9 7 10 8
c ) 2 5 1 4 6 9 10 7 8
d ) 1 2 4 5 6 7 8 9 10
16. Jaką wartość będzie miała zmienna k po wykonaniu następującego ciągu instrukcji:
for(int i = 1; i < 100; i++)
if (i == a[i])k = i;
a ) k = 0
b ) k może być nieokreślone
c ) k będzie równe ostatniemu elementowi w ciągu a, który jest równy swojemu indeksowi
d ) k = 100
17. Ile pytań wystarczy zadać, by w grze w odgadywanie liczby odnaleźć liczbę ukrytą w przedziale [125, 182]?
a ) 12
b ) 8
c ) 5
d ) 6
18. Jaka jest najmniejsza liczba meczów, jaką musi rozegrać 16 tenisistów, aby wyłonić najlepszego i drugiego najlepszego zawodnika turnieju?
a ) 17
b ) 18
c ) 29
d ) 16
19. Który z Polskich matematyków inicjował prace dotyczące poszukiwania i porządkowania elementów?
a ) Jan Łukasiewicz
b ) Hugo Steinhaus
c ) Donald Knuth
d ) Stanisław Ulam
20. Jaka jest najmniejsza liczba porównań wykonywanych przez najszybszy algorytm porządkowania ciagów uporządkowanych w przypadku, gdy ciąg jest uporządkowany i ma n elementów?
a ) 2n
b ) 0
c ) n - 1
d ) n
21. Jaka jest najmniejsza liczba porównać potrzebnych do znalezienia jednocześnie najmniejszej i największej liczby wśród 35 nieuporządkowanych liczby?
a ) 67
b ) 70
c ) 51
d ) 36