ZADANIA Z EGZAMINU PODSTAWY INFORMATYKI– 30.01.2002
1. Rozpatrzmy poniższy program:
int k, p; double One(int), Two(int), Three(int), result;
double (*Mystery [3]) (int) = {One, Two, Three};
cin >> k; cin >> p;
result = (*Mystery [k]) (p);
Napisz program o identycznej funkcjonalności, ale bez posługiwania się tablicą Mystery.
2. Podaj jakie warunki muszą być spełnione, aby funkcje zracały wartość true:
bool M1 (int k) {
int n; bool flag = false;
while (k>0) {
cin >> n;
flag = flag && (n>=0);
k--; }
return flag; }
bool M2 (int A[], int size) {
int k;
for (k=1; k<size; k++)
if (A[k-1] >= A[k])
return false;
return true;
}
3. Dziesiętna liczba automorficzna, to liczba całkowita, która znajduje się na końcu swego kwadratu, np.: 52=25, 252=625. Napisz program, który drukuje liczby automorficzne od 1 do 1000.
4. Liczby całkowite różne od 0 są zapisywane w tablicy TAB o rozmiarze M za pomocą funkcji mieszającej hash. Uzupełnij definicję funkcji insert wstawiającej nowy element data do tablicy TAB 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; }
5. Podano fragment definicji klasy rational umożliwiającej operowanie na ułamkach właściwych:
class rational {
int top, bottom; //licznik i mianownik
public:
rational (int, int);
....................................
} X, Y, Z; X=Y+Z
Podaj nizbędne oprogramowanie, które gwarantuje poprawność instrukcji X=Y+Z.
6. W jednokierunkowej liście cyklicznej wskaźnik ostatnim elemencie skazuje na pierwszy element listy. Wykorzystując mechanizmy klas list oraz link napisz definicję funkcji count (bez używania klasy interator), która zwraca liczbę elementów listy będącej argumentem tej funkcji.
7. Węzły drzewa poszukiwań binarnych zdefiniowano następująco:
class TreeNode {double data; TreeNode *left, *right;};
W kolejnych węzłach drzewa zapisano wartości rzeczywiste. Napisz funkcję rekurencyjną Tree_Sum, która zraca jako wynik sumę wartości związanych z wszytkimi węzłami tego drzewa. Jaka jest złożoność obliczeniowa procesu obliczenia takiej sumy w funkcji liczby n wierzchołków drzewa?