zadania06

Mrona i z /

zadania z egzaminu komisyjnego MARZEC 2001

ŻAGANIA Z EGZAMINU KOMtSYJ^EGO MAJrAeC 2001

.*

1 .Liczby czalkowite różne od zera są zapisane w tablicy TAB o rozmiarze M za pomocą funkcji mieszającej o na2\vic 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) strukturę kopcajaki powstanie po wstawieniu do początkowo pusteco kopca liczb całkowitych w następującej kolejności 15,J^@@|/12,0

3.    Zdefiniuj kompletna klasę o nazwie FEFO 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, isEmpiy , isFull), wstawianie odbywa się na jej koniec zaś usuwany element jest pierwszy !

/ ;

4.    Napisz funkcję Traingular, która jako w^rynik zwraca wartość true. jeśli podana liczba jest trójkątną lub false w przeciwnym wypadku. Liczba n jest trójkątną, 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 nastapujaćy sposób

class TreeNooe { char data; TreeNode *left, *right; };

Zdefinuj rekurencyjna funkcje Traverse, która drukuje zawartość 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 wskazujć-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.    ¹    .

‘r    I *

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 [ j, int limit, int N ) { int index=0

while ((Vector [index] < limit) <Ł& (index<N)) index-H-; return indcx;

)

8.    Podaj jakie warunki muszą być spełnione, aby dwie poniższe funkcje zwracały jako wynik wartość true.

}

bool M1 (iru k) {

int n; bool flag=false; while (k>0) {

cir.» n;

f!ag=fiag && (n>=0);

k»;} ‘

return flag; }

bool M2 (int AQ, int size) { int k;

for (k=l; k<size; k++) if(A[k-l]>=A(k]) return false; return true;

9. Zaklądając, że użycie instrukcji switch (a także wyrażenia warunkowego W ? T : F) nie jest dozwolone, napisz w Ci— fragment programu równoważny poniższej instrukcji switch