ZADANIA Z EGZAMINU KOMISYJNEGO MARZEC 2001
1.Liczby czałkowite różne od zera są zapisane w tablicy TAB o rozmiarze M za pomocą funkcji mieszającej o nazwie hash. Uzupełnij poniższą 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; }
2.W węzłach kopca binarnego przechowywane są liczby całkowite. Narysuj poniżej (w formie drzewa) strukture kopca jaki powstanie po wstawieniu do początkowo pustego kopca liczb całkowitych w następującej kolejności 15,7,11,3,10,10,8,12,5
3. Zdefiniuj kompletna klasę o nazwie FIFO tworzącą środowisko operowania na kolejce liczb całkowitych. Jako reprezentację kolejki przyjmij tablicę. Definicja klasy ma zawierać (poza podstawowymi strukturami danych , konstruktor , destruktor, insert, remove, isEmpty , isFull ), wstawianie odbywa się na jej koniec zaś usuwany element jest pierwszy !
4. Napisz funkcję Traingular, która jako wynik zwraca wartość true, jeśli podana liczba jest trojkatna lub false w przeciwnym wypadku. Liczba n jest trojkatna, jeżeli reprezentowane przez nią żetony można ułożyć w formie trójkąta równobocznego, np.: 1, 3, 6, 10.
5. Wierzchołki drzewa binarnego są opisane w nastapujacy sposób
class TreeNode { char data; TreeNode *left, *right; };
Zdefinuj rekurencyjna funkcje Traverse, która drukuje zawartosc wszystkich wierzchołków wskazanego drzewa binarnego (kolejność wyboru wierzchołków dowolna)
void Traverse (TreeNode *T) {
...............
6. Jednokierunkową listę cykliczną różni od list prezentowanych na wykładach tylko wartość wskaźnika ostatniego elementu, który w liście cyklicznej wskazuje na pierwszy element listy.
Wykorzystując mechanizmy klas list oraz link napisz definicjeę funkcji (bez używania narzędzi klasy iterator), która akceptuje jako element listę cykliczną (nie wskaźnik!)oraz zwraca jako wynik liczbę elementów taj listy.
7. Poniżej podano definicję funkcji Count, która powinna udostępniać liczbę elementów umieszczonych w uporządkowanej tablicy Vector i mających wartości mniejsze od zadanego progu limit. Rozmiar N tablicy podaje trzeci parametr funkcji. Niestety w pewnych sytuacjach wywołanie prowadzi funkcji prowadzi do błędu wykonania. Wskaż na czym polega ten błąd i w jaki sposób można go usunąć.
int Count (int Vector [ ], int limit, int N ) {
int index=0
while ((Vector [index] < limit) && (index<N)) index++;
return index;
}
8. Podaj jakie warunki muszą być spełnione, aby dwie poniższe funkcje zwracały jako wynik wartość true.
bool M1 (int k) { bool M2 (int A[], int size) {
int n; bool flag=false; int k;
while (k>0) { for (k=1; k<size; k++)
cin >> n; if (A[k-1]>=A[k])
flag=flag && (n>=0); return false;
k--; } return true;
return flag; } }
9. Zakłądając, że użycie instrukcji switch (a także wyrażenia warunkowego W ? T : F) nie jest dozwolone, napisz w C++ fragment programu równoważny poniższej instrukcji switch
switch (x) {
case 10: y = `a';
break;
case 20:
case 30: y= `b';
break;
default: y= `c';