Przykładowe pytania egzaminacyjne

Wstęp do informatyki (kierunek: Informatyka, I rok)

Zagadnienia wstępne z informatyki:

1. Przedstaw uogólnioną, logarytmiczną miarę informacji według Shannona (wzór, wraz z objaśnieniami symboli).

2. Wymień trzy różne jednostki informacji, bazujące na uogólnionej mierze informacji według Shannona i wyjaśnij różnice pomiędzy nimi.

3. Wymień jednostki informacji wykorzystywane w systemach komputerowych, funkcjonujących z wykorzystaniem logiki boolowskiej. Wyjaśnij relacje zachodzące pomiędzy jednostkami.

4. Przedstaw na rysunku budowę oktetu.

5. Co oznaczają skróty LSB i MSB.

6. Przedstaw słownie i skrótem wielokrotności bajtów 10⁰, 10³ ... 10¹².

7. Przedstaw tabele prawdy dla koniunkcji, alternatywy, alternatywy wykluczającej i negacji.

8. Przedstaw tabele prawdy dla dysjunkcji, binegacji, implikacji, verum, falsum, asercji.

9. Wymień z nazwy i zapisz w postaci formuły 5 praw algebry Boole'a.

10. 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:

11. Przedstaw uogólnioną formułę konwersji liczby z systemu liczbowego o podstawie R do systemu dziesiętnego.

12. Przedstaw dopuszczalny zakres wartości liczby naturalnej w systemie liczbowym o podstawie R, zapisanej w N-cyfrowym rejestrze.

13. 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.

14. Przedstaw dopuszczalny zakres wartości liczby dziesiętnej, zapisanej w systemie NKB w N-bitowym rejestrze.

15. 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).

16. Przedstaw dopuszczalny zakres wartości liczby dziesiętnej, zapisanej w systemie U2 w N-bitowym rejestrze.

17. 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).

18. Opisz (w jednym, dwóch zdaniach) zasady powiększania rozmiaru N-bitowego rejestru liczby w systemach NKB i U2.

19. Opisz (w jednym, dwóch zdaniach) algorytm zmiany znaku liczby w systemach NKB i U2.

20. Opisz (w jednym, dwóch zdaniach) algorytm konwersji liczby z systemów NKB lub U2 do systemów: ósemkowego lub szesnastkowego.

Podstawowe typy danych:

21. Wymień 5 rodzajów podstawowych typów danych i jednym zdaniem opisz jakie dane reprezentują.

22. Podaj definicję zmiennej i stałej.

23. Przedstaw słowa kluczowe wykorzystywane do reprezentacji 8-, 16- i 32-bitowej liczby naturalnej w różnych językach programowania.

24. Przedstaw słowa kluczowe wykorzystywane do reprezentacji 32- i 64-bitowej liczby rzeczywistej w różnych językach programowania.

25. Przedstaw słowa kluczowe wykorzystywane do reprezentacji wartości logicznej w różnych językach programowania.

26. Podaj rozmiary bitowe następujących typów danych: byte, char, shortint, longint, integer, single, double w różnych językach programowania.

27. 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.

28. 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ę 2^N, dzielenie (część całkowita oraz reszta z dzielenia) przez liczbę 2^N, sprawdzanie parzystości liczby, sprawdzanie znaku liczby.

29. Przedstaw budowę rejestru bitowego 32-bitowej liczby rzeczywistej w standardzie IEEE-754.

30. 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:

31. Wymień rodzaje złożonych typów danych.

32. Przedstaw w postaci graficznej reprezentację bitową uogólnionego przypadku jednowymiarowej
    N-elementowej tablicy, zawierającej dane o rozmiarze S B, umieszczonej pod adresem bazowym BA_HEX. Na rysunku przedstaw adresy, indeksy i numery elementów tablicy.

33. 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 BA_HEX. Na rysunku przedstaw adresy, indeksy i numery elementów tablicy.

34. Przedstaw formułę wyznaczającą adres i-tego elementu tablicy jednowymiarowej, N-elementowej.

35. 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).

36. Wyjaśnij (w jednym, dwóch zdaniach) różnicę pomiędzy rekordem, a unią.

37. Wymień rodzaje abstrakcyjnych typów danych.

38. 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).

39. Wyjaśnij (w jednym, dwóch zdaniach) czym jest tzw. wskaźnik.

40. 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 BA_HEX. Na rysunku przedstaw adresy, indeksy i numery elementów tablicy.

Projektowanie algorytmów metodą graficzną:

41. Przedstaw symbole graficzne (co najmniej 10) wykorzystywane w diagramach przepływu do projektowania algorytmów.

42. Wyjaśnij (w jednym, dwóch zdaniach) zasady graficznego projektowania pojedynczej instrukcji.

43. 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).

44. Przedstaw w postaci graficznej następujące instrukcje sterujące: jednokrotnego wyboru warunkowego (2 warianty) i wielokrotnego wyboru warunkowego (2 warianty).

45. 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:

46. Podaj definicję złożoności obliczeniowej algorytmów.

47. 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).

48. Podaj definicję asymptotycznego tempa wzrostu i wyjaśnij matematycznie (formuły, wraz z opisem symboli) pojęcie notacji „duże O”.

49. Podaj formułę na oszacowanie asymptotycznego tempa wzrostu według notacji „duże O”.

50. Przedstaw własności notacji "duże O", w postaci formuł matematycznych i graficznie (co najmniej 3 własności).

51. Przedstaw w postaci graficznej (wraz z objaśnieniami symboli i elementów charakterystycznych rysunku) konstrukcję maszyny Turinga. Wymień elementy składowe maszyny.

52. Przedstaw uogólnioną postać instrukcji maszynowej dla maszyny Turinga. Wyjaśnij różnice w konstrukcji programów dla maszyny Turinga deterministycznej i niedeterministycznej.

53. Opisz warianty maszyny Turinga (po jednym, dwa zdania na każdy wariant).

54. Wymień podstawowe klasy zadań algorytmicznych i podaj ich definicje.

55. Przedstaw graficznie (na przykładzie) i opisz (w kilku zdaniach) funkcjonowanie algorytmu wykorzystującego strategię „wędruj i sprawdzaj”.

56. Przedstaw graficznie (na przykładzie) i opisz (w kilku zdaniach) funkcjonowanie algorytmu wykorzystującego strategię „dziel i zwyciężaj”.

57. Przedstaw graficznie (na przykładzie) i opisz (w kilku zdaniach) funkcjonowanie algorytmu wykorzystującego strategię zachłanną.

58. Przedstaw graficznie (na przykładzie) i opisz (w kilku zdaniach) funkcjonowanie algorytmu wykorzystującego tzw. programowanie dynamiczne.

59. Przedstaw graficznie (na przykładzie) i opisz (w kilku zdaniach) funkcjonowanie algorytmu wykorzystującego przeszukiwanie probabilistyczne.

60. Wymień i opisz (w jednym, dwóch zdaniach) trzy dowolne techniki pomiaru czasu (np. czasu pracy algorytmu) w programach komputerowych.