Pytania na egzamin magisterski z informatyki



Pobieranie 4,56 Mb.
Strona1/55
Data18.11.2017
Rozmiar4,56 Mb.
  1   2   3   4   5   6   7   8   9   ...   55



PYTANIA NA EGZAMIN MAGISTERSKI
Z INFORMATYKI

OPRACOWANIE
Spis treści


1. Podstawowe typy danych (rozmiar w pamięci, zakres), wskaźniki. 5

2. Podstawowe instrukcje (for, while, do, if) złożone warunki (suma i iloczyn logiczny, zaprzeczenie) 8

3. Struktury oraz unie; dostęp do przechowywanych danych (także poprzez wskaźnik). Na czym polega różnica w traktowaniu struktur i unii w języku C i C++? 16

4. Tworzenie i inicjowanie tablic (statycznych, dynamicznych); zależność pomiędzy tablicami i wskaźnikami; tablice wielowymiarowe. 20

5. Reprezentacja łańcuchów w komputerze. 26

6. Funkcje; przeładowywanie (overloading) funkcji; funkcje statyczne; wartości domyślne argumentów; sposoby przekazywania danych do funkcji. 28

7. Operacje na bitach: przesuwanie bitowe, suma i iloczyn bitowy, maski. 37

8. Tworzenie klas; różnica pomiędzy sekcjami publicznymi, chronionymi oraz prywatnymi 39

9. Konstruktor: domyslny, kopiujący (kiedy są tworzone automatycznie? kiedy są automatycznie wywoływane?); lista inicjalizacyjna konstruktora; destruktor. 43

10. Statyczne składniki klas, sposoby odwoływania się do tych składników; funkcje statyczne. 46

11. Funkcje zaprzyjaźnione, klasy zaprzyjaźnione. 47

12. Mechanizm konwersji za pomocą konstruktora oraz operatora konwersji, jawne wywoływanie konwersji. 50

13. Przeładowywanie operatorów; przykłady operatorów jedno, dwu i wielo-argumentowych; priorytety. 56

14. Ocena złożoności obliczeniowej algorytmów i operacji na strukturach danych. 59

15. Listy jednokierunkowe i dwukierunkowe; posortowane i nieposortowane; z wartownikiem i bez wartownika; cykliczne. 63

16. Stos i kolejka (wykorzystanie tablicy oraz listy). 66

17. Algorytmy rekurencyjne (algorytmy zachłanne, strategia „dziel i rządź”, programowanie dynamiczne, metoda powrotów). 68

18. Wybrane metody sortowania (przez wstawianie, przez wybór, bąbelkowe, przez kopcowanie, szybkie). 70

19. Algorytmy na wyszukiwanie elementów 78

20. Słowniki i ich reprezentacje. 83

21. Kolejki priorytetowe. 86

22. Drzewa binarne; dodawanie, szukanie, usuwanie elementów; przechodzenie drzewa w głąb i wszerz, równoważenie drzewa. 88

23. Grafy nieskierowane i skierowane; reprezentacja w komputerze; przechodzenie grafu w głąb i wszerz; składowe spójne oraz słabe i silne spójne. 91

24. Model ISO/OSI. 94

25. Stos TCP/IP 97

26. Ramka Ethernet 99

27. Adresowanie IP – klasy, CIDR, maska sieci. 100

28. Urządzenia sieciowe – koncentrator, przełącznik, router. 103

29. Protokół TCP 105

Idea przesuwającego się okna (ang. Sliding window) 106

Stany otwarcia 107

30. Bezpieczeństwo sieci komputerowych – polityka bezpieczeństwa, technologie (VPN, NAT, Proxy, Firewall, IPSec, IDS, DMZ) 109

31. Podać definicje: zbiór identyfikujący relacji, klucz schematu relacji, klucz prosty i złożony, klucze potencjalne, klucz główny. Algorytm X-domkniętości. Przykład znajdowania klucza relcji. 127

32. Podać podstawowe modele baz danych. Na czym polegają różnice. Który z nich jest najbardziej rozpowszechniony wśród systemów zarządzania bazami danych (Database engines)? 132

33. Omówić podstawowe komendy SQL zaliczane do DML (data manipulation language) i do DDL (data definition language). Podać przykłady. 134

34. Określić czym są procedury składowane (stored procedures) i procedury wyzwalane (triggers). Na czym polega różnica między nimi? Podać przykłady. 137

35. Podać przykłady instrukcji (konstrukcji) SQL’a, które mogą być wykorzystywane w procedurach, a nie mogę się pojawić w zapytaniach wykonywanych w trybie interakcyjnym. 144

36. Kodowanie informacji – systemy liczbowe 145

37. Bramki logiczne, sumator wielobitowy 152

Rodzaje bramek 152

38. Język asembler 159

39. Architektura harwardzka a architektura von Neumana 161

40. Różnice między komputerami CISC a RISC 165




1. Podstawowe typy danych (rozmiar w pamięci, zakres), wskaźniki.



Typy danych

Najczęściej chyba używanym typem jest int (typ całkowity). Jest on poza tym domyślnym typem, jeżeli nie został podany. Skoncentrujemy się na razie na typach liczbowych.

Typ char jest typem znakowym (JEDEN znak!), ale również liczbowym całkowitym, obsługującym zakres od -128 do 127 (uwaga: ta informacja może być nieprawdziwa jeśli chodzi o liczby ujemne; patrz niżej).

Rozmiar (a więc i zakres) typu int zależy od implementacji, w przypadku systemów 32-bitowych ma on 4 bajty i obsługuje zakres -2147483648 do 2147483647. Jeśli masz ten tekst w edytorze `vim', możesz inkrementować lub dekrementować liczby na których stoi kursor klawiszami odpowiednio Control-a (pod screenem: Control-a a) i Control-x. Możesz sprawdzić, że dla tych liczb operacje te powodują "przekręcenie licznika".

Typ int może również posiadać modyfikatory: short oznacza liczbę krótką całkowitą (zazwyczaj 2 bajty), long długą (4 bajty). Podane wielkości jednak nie są standardowe, lecz zależne od implementacji. Wielkość danych konkretnego typu można sprawdzać za pomocą operatora sizeof:


  • sizeof (typ) - zwraca wielkość danej tego typu

  • sizeof dana - zwraca wielkość danej

Standard co do wielkości typów zakłada jedynie, że:

  • sizeof (char) == 1 (nie musi to oznaczać jednocześnie 8 bitów!)

  • sizeof (short int) < sizeof (long int)

  • sizeof (short int) <= sizeof (int) <= sizeof (long int)

Istnieje również w niektórych kompilatorach typ long long (np. w gcc i ma on wielkość 8 bajtów). Jest to jednak typ niestandardowy.

Modyfikator unsigned oznacza, że liczba tego typu nie obsługuje liczb ujemnych, tzn. np. typ unsigned char ma zakres od 0 do 255, podobnie unsigned short int (jeśli jest 2-bajtowy) ma zakres od 0 do 65535. Dla symetrii istnieje również słowo signed. Zaznaczam od razu, że istnieje też taki typ (już biblioteczny, ale po wczytaniu dowolnego pliku nagłówkowego można uważać, że jest dostępny) size_t. Standard zakłada, że jest to typ wyniku operatora sizeof, a jest najczęściej identyczny z unsigned int.

Tu uwaga co do typu char: istnieją w C++ dwa typy znakowe: signed char i unsigned char. Jest również typ char (bez modyfikatora) i jest on równoważny albo jednemu, albo drugiemu z nich (standard nie precyzuje, któremu) w związku z czym, nie należy zakładać nigdy sposobu, w jaki w danym kompilatorze wartości z zakresu -128 do -1 czy 128 do 255 będą traktowane przez typ char. W przypadku, gdy chce się używać zakresów typu char poza 0-127 należy jawnie określać char jako signed lub unsigned (lub dokonać ustawienia odpowiednich opcji kompilatora, nie będzie to jednak przenośne).

Jak napisałem wcześniej, typ int jest używany domyślnie w przypadku, gdyby nie był podany (ale - UWAGA! - tylko jeśli podano modyfikator typu, czyli short, long, signed lub unsigned), toteż wystarczy pisać np. long i będzie to oznaczało long int. Podobnie unsigned będzie oznaczać unsigned int.

W C++ istnieje też typ logiczny (lub inaczej `boolowski', ewentualnie niektórzy mówią "buliński" :), który nazywa się `bool'. Wartości tego typu to jedynie prawda i fałsz, które są dostępne pod literałami `true' i `false'. Jeśli ktoś nie wie, skąd się wzięła nazwa `boolowski' (ang. boolean), to wyjaśniam, że od nazwiska matematyka, który opracował algebrę dla wartości logicznych, George'a Boole'a. Zaznaczam od razu, że typ `bool' jest typem wartości przyjmowanej przez operatory `&&', `||' i `!' i zwracanym przez ==, != itd. Jednak ten typ nie jest tak restrykcyjnie pilnowany jak to ma miejsce np. w pascalu; może być dowolnie niejawnie konwertowany na typ int, z kolei na ten typ można konwertować każdą wartość konwertowalną na całkowitą (true jest konwertowane na 1).

Liczby rzeczywiste mogą być reprezentowane przez jeden z typów zmiennoprzecinkowych: float, double, long double, zajmujących odpowiednio 4, 8 i 10 bajtów pamięci (przynajmniej na aktualnie popularnych kompilatorach i systemach operacyjnych; zastrzegam wciąż, że te wielkości są specyficzne, mają one oznaczać jedynie typ zmiennoprzecinkowy pojedynczej, podwójnej i rozszerzonej precyzji; podane tu długości są zgodne z jakąś tam normą IEEE :*).

Wszystkie te wymienione typy nazywane są typami WBUDOWANYMI (ang. built-in) lub ŚCISŁYMI (ang. strict) - pewnie dlatego, że są to typy, które są tak ścisłe, że ściskać ich już nie ma potrzeby :*) (patrz przekazywanie argumentów do funkcji). Typy te należą również do grupy zwanej "POD" ("Plain ol' data"). Obiekty takich typów podpadają pod dość luźne reguły, a konkretnie pod takie, pod jakie podpadają obiekty w C (będzie o tym mowa przy właściwościach rozszerzonych).
Wskaźniki
Każdy obiekt, jako że ma swoją tożsamość, może zostać w jednoznaczny sposób zidentyfikowany. Referencja sama z siebie jeszcze do tego nie wystarczy. Referencja jest jedynie "typologicznym", że się tak wyrażę, interfejsem obiektu, ale jeszcze nie pozwala na stwierdzenie tożsamości. Dlatego z referencjami nieodłącznie związane są wskaźniki. Referencja nie może być pojmowana w ogóle jako wartość; jest to jedynie "stwierdzenie faktu", że to coś, do czego się odnosi, jest obiektem. Co innego wskaźnik. Wskaźnik jest konkretną, znaną wartością, podobnie jak wartość typu int, którą możemy sobie zapamiętywać i przechowywać, a nawet wykonywać na niej operacje. Referencje zaś mamy tylko dostępną w danej chwili i nie można jej przechować, zmienić, ani nic podobnego. Odnosząc się znów do języka Tcl - w Tclu odpowiednikiem wskaźników do zmiennych są po prostu napisy oznaczające nazwę zmiennej.

Wróćmy jednak do źródła, bo sądzę, że niektórym zaczyna się już mieszać. Otóż wiemy, że zmienna zadeklarowana jako "int x;" posiada jako wyrażenie typ int&. Referencja zatem reprezentuje obiekt, ale nie mamy możliwości (poza samą deklaracją) wpływania na to, do czego ta referencja referuje. Wskaźnik zaś jest wartością, którą można w dowolnym momencie pobrać i zapamiętać.



Typ wskaźnika oznaczamy gwiazdką; w tym wypadku oznaczylibyśmy przez "int*", a pobieramy go przy pomocy operatora... &.

Tzn. wyrażenie "&x" zwraca wartość typu int*, która to wartość jest wskaźnikiem na obiekt reprezentowany przez referencję oznaczoną nazwą "x".

Symetrycznie, jeśli użyjemy operatora * na wartości wskaźnika (int*), to typem takiego wyrażenia jest int&. Operację, którą wykonuje operator & nazywamy pobieraniem adresu (a operator operatorem adresu), natomiast operacje z użyciem jednoargumentowego operatora * nazywamy wyłuskaniem lub dereferencją. Popatrzmy:

int x;


int* px = &x; // wskaźnik
*px = 0; // powoduje, że x == 0
Czym jest zatem wskaźnik? Jest to (najczęściej, bo standard odnosi się do tego ostrożnie) implementowane jako liczba całkowita, która oznacza adres w pamięci, gdzie przechowywany jest ów obiekt. Przynajmniej załóżmy coś takiego na użytek naszych rozważań (nie można tego traktować zbyt dosłownie, gdyż adres ten nie tylko może być wirtualny, ale kompilator w celach optymalizacyjnych często lubi "tylko udawać, że tak jest").

Gdybyśmy jednak dla uproszczenia przyjęli, że mówimy o typach ścisłych, to wskaźnik na większości kompilatorów jest adresem w pamięci, pod którym znajduje się jego wewnętrzna reprezentacja. Operatorem sizeof możemy z kolei zbadać, ile bajtów zajmuje owa reprezentacja. Wskaźnik ten z kolei można zrzutować na typ unsigned char* i w ten sposób dostajemy się do owej reprezentacji (standard o czymś takim wspomina).

Przykładowo, na ostatnio modnych kompilatorach i systemach operacyjnych (choć 32-bitowe systemy już wychodzą z mody), taki typ int ma 4 bajty. Zatem sizeof (int) zwróci nam 4, a jej reprezentacja to tablica 4 bajtów (unsigned char), które pobieramy przez zrzutowanie wartości wskaźnika, pobranej przez operator &. Niestety radzę nie korzystać z tej wiedzy (mówię to tylko po to, żeby można było sobie wyobrazić, o czym mówię). Zakładając nawet, że na wystarczającej liczbie maszyn int ma 4 bajty, to jeszcze jest coś takiego jak endian, co oznacza, że dla int i = 1, wartość 1 może mieć na jednej maszynie pierwszy bajt, a na innej ostatni (a w niektórych przypadkach to nawet żaden :).



  1   2   3   4   5   6   7   8   9   ...   55


©operacji.org 2019
wyślij wiadomość

    Strona główna