Przykładowe pytania egzaminacyjne
Wstęp do informatyki (kierunek: Informatyka, I rok)
Zagadnienia wstępne z informatyki:
Przedstaw uogólnioną, logarytmiczną miarę informacji według Shannona (wzór, wraz z objaśnieniami symboli).
Wymień trzy różne jednostki informacji, bazujące na uogólnionej mierze informacji według Shannona i wyjaśnij różnice pomiędzy nimi.
Wymień jednostki informacji wykorzystywane w systemach komputerowych, funkcjonujących z wykorzystaniem logiki boolowskiej. Wyjaśnij relacje zachodzące pomiędzy jednostkami.
Przedstaw na rysunku budowę oktetu.
Co oznaczają skróty LSB i MSB.
Przedstaw słownie i skrótem wielokrotności bajtów 100, 103 ... 1012.
Przedstaw tabele prawdy dla koniunkcji, alternatywy, alternatywy wykluczającej i negacji.
Przedstaw tabele prawdy dla dysjunkcji, binegacji, implikacji, verum, falsum, asercji.
Wymień z nazwy i zapisz w postaci formuły 5 praw algebry Boole'a.
Wymień z nazwy i zapisz w postaci formuły 5 własności algebry Boole'a, wynikających bezpośrednio z praw algebry Boole'a.
Systemy liczbowe:
Przedstaw uogólnioną formułę konwersji liczby z systemu liczbowego o podstawie R do systemu dziesiętnego.
Przedstaw dopuszczalny zakres wartości liczby naturalnej w systemie liczbowym o podstawie R, zapisanej w N-cyfrowym rejestrze.
Przedstaw formułę (wraz z objaśnieniami symboli) wyznaczającą minimalną liczbę cyfr, jaką należy użyć do zapisania liczby dziesiętnej M w systemie liczbowym o podstawie R.
Przedstaw dopuszczalny zakres wartości liczby dziesiętnej, zapisanej w systemie NKB w N-bitowym rejestrze.
Przedstaw na rysunku N-bitowy rejestr zawierający liczbę w systemie NKB. Opisz wagi poszczególnych bitów rejestru (ich wartości bezwzględne) i przedstaw formułę do konwersji wartości liczby z systemu NKB do systemu dziesiętnego (wraz z objaśnieniami symboli).
Przedstaw dopuszczalny zakres wartości liczby dziesiętnej, zapisanej w systemie U2 w N-bitowym rejestrze.
Przedstaw na rysunku N-bitowy rejestr zawierający liczbę w systemie U2. Opisz wagi poszczególnych bitów rejestru (ich wartości bezwzględne) i przedstaw formułę do konwersji wartości liczby z systemu U2 do systemu dziesiętnego (wraz z objaśnieniami symboli).
Opisz (w jednym, dwóch zdaniach) zasady powiększania rozmiaru N-bitowego rejestru liczby w systemach NKB i U2.
Opisz (w jednym, dwóch zdaniach) algorytm zmiany znaku liczby w systemach NKB i U2.
Opisz (w jednym, dwóch zdaniach) algorytm konwersji liczby z systemów NKB lub U2 do systemów: ósemkowego lub szesnastkowego.
Podstawowe typy danych:
Wymień 5 rodzajów podstawowych typów danych i jednym zdaniem opisz jakie dane reprezentują.
Podaj definicję zmiennej i stałej.
Przedstaw słowa kluczowe wykorzystywane do reprezentacji 8-, 16- i 32-bitowej liczby naturalnej w różnych językach programowania.
Przedstaw słowa kluczowe wykorzystywane do reprezentacji 32- i 64-bitowej liczby rzeczywistej w różnych językach programowania.
Przedstaw słowa kluczowe wykorzystywane do reprezentacji wartości logicznej w różnych językach programowania.
Podaj rozmiary bitowe następujących typów danych: byte, char, shortint, longint, integer, single, double w różnych językach programowania.
Wyjaśnij (w jednym, dwóch zdaniach) zasady konstruowania masek bitowych dla następujących operacji bitowych na liczbach całkowitych: zerowanie bitów, ustawianie bitów, negacja bitów i sprawdzanie stanu bitów.
Podaj właściwe operatory bitowe i maski bitowe (jeżeli są konieczne) dla następujących operacji arytmetycznych na liczbach całkowitych: mnożenie przez liczbę 2N, dzielenie (część całkowita oraz reszta z dzielenia) przez liczbę 2N, sprawdzanie parzystości liczby, sprawdzanie znaku liczby.
Przedstaw budowę rejestru bitowego 32-bitowej liczby rzeczywistej w standardzie IEEE-754.
Podaj kody (numery) znaków ASCII (odpowiednie zakresy lub pojedyncze wartości) należące do następujących grup znaków: specjalnych, podstawowych, dodatkowych. Wyjaśnij (w jednym, dwóch zdaniach) jaką rolę pełnią znaki ASCII należące do tych trzech grup.
Złożone typy danych:
Wymień rodzaje złożonych typów danych.
Przedstaw w postaci graficznej reprezentację bitową uogólnionego przypadku jednowymiarowej
N-elementowej tablicy, zawierającej dane o rozmiarze S B, umieszczonej pod adresem bazowym BAHEX. Na rysunku przedstaw adresy, indeksy i numery elementów tablicy.
Przedstaw w postaci graficznej reprezentację bitową uogólnionego przypadku dwuwymiarowej
M×N -elementowej tablicy typu złożonego, zawierającej dane o rozmiarze S B, umieszczonej pod adresem bazowym BAHEX. Na rysunku przedstaw adresy, indeksy i numery elementów tablicy.
Przedstaw formułę wyznaczającą adres i-tego elementu tablicy jednowymiarowej, N-elementowej.
Przedstaw formułę wyznaczającą adres i,j-tego elementu tablicy dwuwymiarowej, M×N -elementowej typu złożonego (przyjąć, że i jest indeksem wiersza tablicy).
Wyjaśnij (w jednym, dwóch zdaniach) różnicę pomiędzy rekordem, a unią.
Wymień rodzaje abstrakcyjnych typów danych.
Wyjaśnij (w kilku zdaniach) różnice pomiędzy złożonym, a abstrakcyjnym typem danych (m.in. sposób organizacji danych w pamięci, wady i zalety obu typów).
Wyjaśnij (w jednym, dwóch zdaniach) czym jest tzw. wskaźnik.
Przedstaw w postaci graficznej reprezentację bitową uogólnionego przypadku dwuwymiarowej
M×N -elementowej tablicy typu abstrakcyjnego, zawierającej dane o rozmiarze S B, umieszczonej pod adresem bazowym BAHEX. Na rysunku przedstaw adresy, indeksy i numery elementów tablicy.
Projektowanie algorytmów metodą graficzną:
Przedstaw symbole graficzne (co najmniej 10) wykorzystywane w diagramach przepływu do projektowania algorytmów.
Wyjaśnij (w jednym, dwóch zdaniach) zasady graficznego projektowania pojedynczej instrukcji.
Przedstaw różnice pomiędzy algorytmami rekurencyjnymi, a iteracyjnymi (uwzględnij takie cechy algorytmów jak: szybkość działania, liczba iteracji, przejrzystość implementacji, liczba instrukcji, liczba zmiennych).
Przedstaw w postaci graficznej następujące instrukcje sterujące: jednokrotnego wyboru warunkowego (2 warianty) i wielokrotnego wyboru warunkowego (2 warianty).
Przedstaw w postaci graficznej następujące instrukcje sterujące: pętlę iteracyjną (3 warianty) i skoku warunkowego (2 warianty).
Złożoność obliczeniowa algorytmów:
Podaj definicję złożoności obliczeniowej algorytmów.
Przedstaw w postaci graficznej (wraz z opisem symboli i elementów charakterystycznych rysunku) typowe funkcje złożoności obliczeniowej algorytmów (co najmniej 7).
Podaj definicję asymptotycznego tempa wzrostu i wyjaśnij matematycznie (formuły, wraz z opisem symboli) pojęcie notacji „duże O”.
Podaj formułę na oszacowanie asymptotycznego tempa wzrostu według notacji „duże O”.
Przedstaw własności notacji "duże O", w postaci formuł matematycznych i graficznie (co najmniej 3 własności).
Przedstaw w postaci graficznej (wraz z objaśnieniami symboli i elementów charakterystycznych rysunku) konstrukcję maszyny Turinga. Wymień elementy składowe maszyny.
Przedstaw uogólnioną postać instrukcji maszynowej dla maszyny Turinga. Wyjaśnij różnice w konstrukcji programów dla maszyny Turinga deterministycznej i niedeterministycznej.
Opisz warianty maszyny Turinga (po jednym, dwa zdania na każdy wariant).
Wymień podstawowe klasy zadań algorytmicznych i podaj ich definicje.
Przedstaw graficznie (na przykładzie) i opisz (w kilku zdaniach) funkcjonowanie algorytmu wykorzystującego strategię „wędruj i sprawdzaj”.
Przedstaw graficznie (na przykładzie) i opisz (w kilku zdaniach) funkcjonowanie algorytmu wykorzystującego strategię „dziel i zwyciężaj”.
Przedstaw graficznie (na przykładzie) i opisz (w kilku zdaniach) funkcjonowanie algorytmu wykorzystującego strategię zachłanną.
Przedstaw graficznie (na przykładzie) i opisz (w kilku zdaniach) funkcjonowanie algorytmu wykorzystującego tzw. programowanie dynamiczne.
Przedstaw graficznie (na przykładzie) i opisz (w kilku zdaniach) funkcjonowanie algorytmu wykorzystującego przeszukiwanie probabilistyczne.
Wymień i opisz (w jednym, dwóch zdaniach) trzy dowolne techniki pomiaru czasu (np. czasu pracy algorytmu) w programach komputerowych.