1. Zdefiniować jednym zdaniem następujące pojęcia:

1. Informatyka - jest to dziedzina wiedzy zajmująca się gromadzeniem, przetwarzaniem, przechowywaniem, wykorzystywaniem informacji.

2. Drzewo binarne - występuje wtedy gdy każdy węzeł posiada maksymalnie dwóch synów. Wyróżnia się synów: lewego i prawego.

3. Kopiec - pełne lub prawie pełne drzewo binarne.

4. Złożoność pamięciowa algorytmu - jest to pamięć potrzebna na wykonanie algorytmu w funkcji rozmiaru zadania.

5. Algorytm zachłanny - algorytm optymalizacyjny wybiera opcje optymalne wierząc, że wynik będzie optymalny.

2. Zakodować (wszystkie obliczenia powinny znaleźć się w pracy):

1. wartość 1875,1875 dziesiętną na kod binarny i szesnastkowy (kod koprocesora).

1875	1
937	1
468	0
234	0
117	1
58	0
29	1
14	0
7	1
3	1
1	1
0

0	1875
0	375
0	75
1	5
1	0

11101010011,0011 - kod binarny

1,11010100110011 * 2¹⁰

C - P = 10

C = 127 + 10

C = 137

S = 0

137	1
68	0
34	0
17	1
8	0
4	0
2	0
1	1

10001001 - cecha binarnie

0|10001001|11010100110011000000000 - kod koprocesora

S C M

0100|0100|1110|1010|0110|0110|0000|0000 44EA6600 - kod szesnastkowy

3. Proszę wykonać operację dodawania na ośmiu bitach wartości -45 i -99. Skomentuj uzyskany wynik.

45	1
22	0
11	1
5	1
2	0
1	1

99	1
49	1
24	0
12	0
6	0
3	1
1	1
0

00101101 45

11010010 01100011 99

+ 1 10011100

11010011 - 45 + 1

10011101 - 99

11010011

10011101

+

101110000 - 144

Komentarz: Dodanie tych dwóch wartości wykracza poza operacje na ośmiu bitach.

4. Pokaż etapy pomnożenia dwóch liczb (-9 * 9) w kodzie U2:

9 - 1001

-9 - 0111

0001001

0111

01111001

00111100

0000

00111100

00011110

0000

00011110

00001111

0111

01111111

00111111

0111 +

10101111 = -81 

5. Wymień rodzaje drukarek oraz charakterystyczne charakterystyczne parametry tych urządzeń:

a) Drukarka igłowa - Głowica posiada 7, 9 lub 24 igły. Przesuwa się poziomo wzdłuż

papieru. układy elektroniczne drukarki wypychają do przodu niektóre

igły. Te zaś dociskają taśmę barwiącą do papieru i pozostawiają na

nim maleńkie punkciki

b) Drukarka atramentowa - Obraz na papierze powstaje tak samo jak w drukarkach

igłowych, ale zamiast igieł i taśmy barwiącej drukarka atramentowa posiada dysze,

z których atrament wytryskiwany jest bezpośrednio na papier.

c) Drukarka laserowa - drukuje poprzez umieszczanie na papierze cząstek tonera. Wałek

selenowy jest elektryzowany, następnie naświetlany światłem laserowym. Następnie

toner z wałka przenoszony jest na papier. Na końcu prowadzony jest proces utrwalania

wydruku.

6. Co to są półsumatory i z jakich bramek powstają?

Półsumatorem nazywamy układ posiadający dwa wejścia (x1 i x2) oraz dwa wyjścia -

sumę (Y) oraz przeniesienie. Wykonuje działania dodawania na układzie liczb

binarnych. Tworzy się go z bramek XOR oraz AND.

7.

8. Stosując algorytmy: sortowania przez scalanie pokazać kolejne etapy działania algorytmu.

3; 0; 10; -5; 12; 4; 8; 11





3; 0; 10; -5 12; 4; 8; 11







3; 0 10; -5 12; 4 8; 11













3 0 10 -5 12 4 8 11













0; 3 -5; 10 4; 12 8; 11



-5; 0; 3; 10 4; 8; 11; 12

-5; 0; 3; 4; 8;10; 11; 12

9. Działając na tablicy z poprzedniego przykładu proszę pokazać (obliczenia) działanie algorytmu wyszukiwania binarnego przy poszukiwaniu wartości x = 3.

A 1 2 3 4 5 6 7 8

-5

0

3

4

8

10

11

12

K = 3 (szukany)

Left = 1;

Right = 8;

Left ≤ Right

Mid = (left + right)/2

Mid = (1+8)/2 = 4

A[mid] = 4 ≠ K

A[mid] < K NIE

Right = mid - 1 = 3

A 1 2 3

-5

0

3

Left ≤ Right

Mid = (1+3)/2 = 2

A[mid] = 0 ≠ K

A[mid] < K TAK

Left = mid + 1 = 3

A 3

3

Left ≤ Right TAK

Mid = (3+3)/2 = 3

A[mid] = 3 = K TAK ZWRÓĆ MID = 3

10. Stosując znany algorytm kompresji danych (kody Huffmana) utwórz kody dla liter a, b, c, d . Częstość występowania liter jest następująca: a50, b10, c14, d26. Oblicz jaki będzie zysk dla zakodowania 10000 znaków w/w kodem i kodem o stałej długości.

a)

A50, b10, c14, d26 b10, c14, d26, a50

24 d26, a50





b10 c14



50 ,a50

• 
  
  d26

b10 c14



100

0 1



A50 50

0 1

• 
  
  d26

0 1

b10 c14

Kody dla poszczególnych liter:

A - 0

B - 100

C - 101

D - 11

b)

Kod o stałej długości (dla 10000 znaków) 3 bity na znak 3*10000 (znaków) = 30000 bitów

Kod o zmiennej długości (dla 10000 znaków) [1*50+3*10+3*14+2*26]*100 = 17400 bitów

12.

#include <stdio.h>

#define a 5

void main(void){

int p,n,i=1;

scanf("%d",&p);

while(i<p){

n+=i;

i++;

}

printf("n=%d",n);

13.

#include <stdio.h>

int podzielna(int a,b);

void main(void)

{

do{

scanf("%d",&x);

scanf("%d",&y);

if(podzielna(x,y))printf("Liczba %d jest podzilna przez %d",x,y);else printf("Liczba %d nie jest podzilna przez %d",x,y)

}while(x==0||y==0);

}

int podzielna(int a,b)

{

if(a%b)return 0;else return 1;

}

14.

RELACJA X
U	V	W
A B C	Z D Q	5 3 5

RELACJA Y
R	S
3 4	J K

PROJECT U from X to ABC

SELECT from X where W<5 to BD3

JOIN X and Y where X.W>Y.R to AZ53J, CQ53J?, AZ54K?, CQ54K?