Opracowane by Piotr Kurowski T5.

Zestaw 1.

Zad. 1

Niech zmienne P i K mają odpowiednio wartość α i β. Jakie wartości będą miały te same zmienne po wykonaniu funkcji Compute (P, K).

void Compute (int &x, int &y){

x ^= y;

y ^= x;

x ^= y;

}

A. P = α, K = β

B. P = β, K = α

C. P = α, K = α

D. P = 0, K = 0

E. P = β, K = β

Zad. 2

Do tablicy znakowej o rozmiarze M=10 dostęp odbywa się za pomocą funkcji mieszającej 11k mod M, gdzie k jest numerem porządkowym litery w alfabecie angielskim (k=0, …, 25). Jaka jest zawartość, początkowo pustej, tablicy po wprowadzeniu do niej kolejno znaków EASYQUTION, jeżeli kolizje rozwiązano za pomocą sondowania liniowego:

A. AUINEYQOST

B. EASYQUTION

C. AUEIQYSOT

D. NOITUQYSAE

E. ESQTOAYUIN

Zad. 3

Napisano funkcję, która realizuje przeszukiwanie binarne uporządkowanej tablicy o rozmiarze 5. Funkcja zwraca wartość true lub false w zależności od tego czy w tablicy znajduje się wartość będąca parametrem funkcji. Jakie są najmniejsze, (czyli w najlepszym przypadku) liczby elementów tej tablicy, jakie należy sprawdzić, aby funkcja zwróciła odpowiednio wartości true i false?

A.1 element dla true, 1 dla false

B. 1 element dla true, 2 dla false

C. 2 elementy dla true, 1 dla false

D. 1 element dla true, 2 dla false

E. 5 element dla trude, 1 dla false

Zad. 4

Zdefiniowana niżej funkcji Mount powinna zwracać liczbę elementów umieszczonych w uporządkowanej tablicy Victor i mających wartość mniejszą od zadanego progu limit. Rozmiar N tablicy podaje trzeci parametr funkcji. Które z poniższych stwierdzeń najlepiej oddaje zachowanie funkcji Count:

int Count (int Vector[], int limit, int N) {

int index = 0;

while ( (Vector[index] < limit) && (index < N))index++;

return index; }

A. Funkcja zawsze zwraca wartość zero, ponieważ tablica nie jest przekaza przez referencję

B. Funkcja zawsze zwraca poprawną wartość o ile limit > 0

C. Funkcja zawsze zwraca poprawną wartość o ile liczba elementów mniejszych od limit jest równa co najwyżej N-1

D. Funkcja może zwrócić wartość niepoprawną, gdyż zmienna index jest wykorzystywana jednocześnie jako licznik pomocniczy

E. Funkcja zawsze zwraca wartość niepoprawną ze względu na źle zapisane warunki pętli Chile

Zad. 5

Złożoność obliczeniowa operacji sprawdzającej czy w kopcu binarnym o rozmiarze n występuje wskazany element jest rzędu:

A. O (I) B. O(lg n) C. (n lg n) D. O(n) E. O(n^2)

Zestaw 2.

Zad. 1

Podana niżej instrukcja wyświetli napis OK. pod warunkiem, że zmienna całkowita Z przyjmie wartość.

if (Z & 077 == 0) cout << ”OK”;

A. 0 B. 7 C. 63 D. 64 E. nie ma takiej wartości

Zad. 2

Zdefiniowano trzy następujące funkcję:

int f (int i) { return ++i; }

int g ( int &i){ return ++i;}

int h (int &i){ return i++;}

int a = 0, b = 0, c = 0; a += f(g(a)); b+= f(f(a)); c += f (h(c));

cout << a << b << c;

A. 3, 2, 2 B. 2, 2, 2 C. 2, 3, 4 D. 3, 4, 5 E. 3, 5, 2

Zad. 3

Liczby całkowite różne od zera są zapisywane w tablicy TAB o rozmiarze M za pomocą funkcji mieszającej hash. Którą ze wskazanych niżej instrukcji należy uzupełnić definicją funkcji insert wstawiający nowy element data do tablicy metodą sondowania liniowego. Zakładamy, że przepełnienie tablicy nigdy nie nastąpi.

void insert (int data) { int k = hash (data, M); . . . . . . . . . . . . . . . . . . . TAB[k] = data; }

while (TAB[k]) k = (k+1) % M; for (k; TAB[k] != 0; k++); do (k = (k+1) %M;) while (TAB[k]); while (TAB[k] != 0) k++; if (TAB[k] > 0) k = (k+1) % M;

Zad. 4

Rozważmy dwie funkcję Magic1 oraz Magic2 pokazane poniżej. Dla jakich wartości wartości parametru wejściowego x obydwie funkcje zwracają ten sam wynik

int Magic1 (int x){ int y=x; switch (y){ case 0: y=1; break; case 1: y=3; default: y=3;} return y;}

int Magic2 (int x){ int y=x; if (y==0) y=1; if (y==1) y=2; else y=3; return y; }

1. Dowolnych wartości

2. Nie ma takich wartości

3. Wszystkie z wyjątkiem 0

4. Wszystkie z wyjątkiem 0 i 1

5. Tylko wartości 0 i 1

Zad. 5

Która z poniższych struktur jest kopcem binarnym?

A. B. C. D.

10 40 40 13

20 58 20 16 20 16 23 26

35 15 22 15 13 42 20

E.

13

• 
  
  
  26

42 20 32

Zestaw 3.

Zad. 1

Wartość zmiennej z po wykonaniu poniższego fragmentu programu będzie równa:

int z = 0; int i = 32; while(i) { z |= i; i>>=2; }

A. 42 B. 31 C. 20 D. 16 E. 10

Zad. 2

Patrz zestaw nr 2. Zad 2

Zad. 3

Patrz zestaw nr 2. Zad 3

Zad. 4

Patrz zestaw nr 2. Zad 4

Zad. 5

Wartość zmiennej z po wykonaniu poniższego fragmentu programu będzie równa:

for (int i=0, z=25; i<5; i++)

for (int j=0; j<i; j++) --z;

A. 10 B. 15 C. 19 D. 20 E. 22

Zestaw nr 4.

Zad. 1

Patrz zestaw nr 1. zad nr 1.

Zad. 2

Patrz zestaw nr 1. zad nr 2.

Zad. 3

Wartość zmiennej z po wykonaniu poniższego programu będzie równa:

int z=0

for (int k=25; k; k >>=1){

int N=31;

while (N--) if (N & 2)z++;

}

A. z=75 B. z=775 C. z=155 D. z=25 E. z=80

Zad. 4

Poniżej zdefiniowano funkcję Mystery. Zakładając, że użyta tam funkcja pomocnicza swap zamienia miejsca parametrów, które z poniższych stwierdzeń prawidłowo opisują sytuację jaka powstaje każdorazowo w chwili kiedy program wykonuje instrukcje cout << k;

void Mystery (int A[], int N){

int j, k;

for (k=0; k < N; k++){

for (j=k+1; j<N; j++)

if(A[j] < A[k]) swap (A[k], A[j]);

cout << k;

}

1. Tablica A jest posortowana rosnąco

2. Tablica A jest posortowana rosnąco od pozycji k do N-1

3. Tablica A jest posortowana malejąco od pozycji k do N-1

4. Tablica A jest posortowana rosnąco od pozycji 0 do k

5. Tablica A jest posortowana malejąco od pozycji 0 do k

Zad. 5

Jaka jest złożoność algorytmu usuwającego z kopca binarnego o rozmiarze n dowolny element jest rzędu

A. O(I) B. O(lg n) C. (n log n) D. O(n) E. O (n^2)

---