Udajove struktury a algoritmy

skorec1 · 17.06.2009, 08:17:58

Verzia 1, v pripade nejakej nezhody mozte dat vediet

Známky: 1
Hašovanie je technika vhodná pre efektívne vykonávanie operácií:
Vyberte aspon jednu odpoved.
   **a. INSERT
   b. MIN
   **c. DELETE
   d. FIND
**e.Member

2
Známky: 1
Pre metódu Divide-and-conquer je charakteristické:
Vyberte aspon jednu odpoved.
   a. Použitie rekurzie
   b. Postup zhora-nadol (Od problému k elemntárnym podproblémom)
   c. Použitie iterácie

   d. Casté použitie aritmetickej operácie delenia
   e. Postup zdola-nahor (Od elementárnych podproblémov k celkovému problému)

3
Známky: 1
O(n.log n) najhoršiu zložitost majú triediace algoritmy:
Vyberte aspon jednu odpoved.
   a. QuickSort
   b. BubbleSort
   c. MergeSort
   d. InsertionSort
   **e. HeapSort???

4
Známky: 1
Lineárny model RAM neobsahuje tieto inštrukcie:
Vyberte aspon jednu odpoved.
   **a. HALT
   b. STORE
   c. MUL
   d. READ???
write

Známky: 1
Použitie metódy Divide-and-conquer je typické pre triediace algoritmy:
Vyberte aspon jednu odpoved.
   **a. QuickSort
   b. RadixSort
   c. HeapSort
   d. BubbleSort
   **e. MergeSort

6
Známky: 1
Ktoré z uvedených operácií nie sú operáciami ADT nat?
Vyberte aspon jednu odpoved.
   **a. CAT
   **b. MAKE
   c. SUCC
   d. MUL

vypracovany:
1
Známky: 1
Hašovanie je technika vhodná pre efektívne vykonávanie operácií:
Vyberte aspon jednu odpoved.
   **a. INSERT
   b. MIN
   **c. DELETE
   d. FIND

2
Známky: 1
Pre metódu Divide-and-conquer je charakteristické:
Vyberte aspon jednu odpoved.
   **a. Použitie rekurzie
   **b. Postup zhora-nadol (Od problému k elemntárnym podproblémom)
   c. Použitie iterácie???
   d. Casté použitie aritmetickej operácie delenia
   e. Postup zdola-nahor (Od elementárnych podproblémov k celkovému problému)

3
Známky: 1
O(n.log n) najhoršiu zložitost majú triediace algoritmy:
Vyberte aspon jednu odpoved.
   a. QuickSort
   b. BubbleSort
   c. MergeSort
   d. InsertionSort
   **e. HeapSort

4
Známky: 1
Lineárny model RAM neobsahuje tieto inštrukcie:
Vyberte aspon jednu odpoved.
   **a. HALT
   b. STORE
   c. MUL
   d. READ

5
Známky: 1
Použitie metódy Divide-and-conquer je typické pre triediace algoritmy:
Vyberte aspon jednu odpoved.
   **a. QuickSort
   b. RadixSort
   c. HeapSort
   d. BubbleSort
   **e. MergeSort

6
Známky: 1
Ktoré z uvedených operácií nie sú operáciami ADT nat?
Vyberte aspon jednu odpoved.
   **a. CAT
   **b. MAKE
   c. SUCC
   d. MUL

7

Známky: 1
Operáciu Member je na ÚŠ zoznam (s n prvkami) možné vykonat v case:
Vyberte aspon jednu odpoved.
   **a. O(n)
   b. Žiadna z uvedených možností
   c. O(1)
   d. O(log n)

8
Známky: 1
Ktoré zo stratégií oznacovania (prechádzania) stromov možno aplikovat aj na iné ako binárne stromy?
Vyberte aspon jednu odpoved.
   **a. Postorder
   **b. Preorder
   c. Inorder

9
Známky: 1
Dobrá hašovacia funkcia by mala mat tieto vlastnosti:
Vyberte aspon jednu odpoved.
   a. vysoká miera kolízií
   **b. nízka miera kolízií
   c. vysoká zložitost výpoctu
   **d. nízka zložitost výpoctu

10
Známky: 1
Aká je logaritmická cena inštrukcie ADD *i stroja RASP umiestnenej v pamäti od adresy j?
Vyberte aspon jednu odpoved.
   **a. žiadna z uvedených
   b. l(j)+l(c(i))+l(c(c(i)))
   c. l(c(0))+l(i)+l(c(i))+l(c(c(i)))
   d. l(c(0))+l(i)+l(c(i))
Cas zostávajúci do ukoncenia testu

USA_TEST1

1
Známky: 1
Hašovanie je technika vhodná pre efektívne vykonávanie operácií:
Vyberte aspon jednu odpoved.
   **a. INSERT
   b. MIN
   **c. DELETE
   d. FIND

2
Známky: 1
Pre metódu Divide-and-conquer je charakteristické:
Vyberte aspon jednu odpoved.
   **a. Použitie rekurzie
   **b. Postup zhora-nadol (Od problému k elemntárnym podproblémom)
   c. Použitie iterácie???
   d. Casté použitie aritmetickej operácie delenia
   e. Postup zdola-nahor (Od elementárnych podproblémov k celkovému problému)

3
Známky: 1
O(n.log n) najhoršiu zložitost majú triediace algoritmy:
Vyberte aspon jednu odpoved.
   a. QuickSort
   b. BubbleSort
   c. MergeSort
   d. InsertionSort
   **e. HeapSort

4
Známky: 1
Lineárny model RAM neobsahuje tieto inštrukcie:
Vyberte aspon jednu odpoved.
   **a. HALT
   b. STORE
   c. MUL
   d. READ

5
Známky: 1
Použitie metódy Divide-and-conquer je typické pre triediace algoritmy:
Vyberte aspon jednu odpoved.
   **a. QuickSort
   b. RadixSort
   c. HeapSort
   d. BubbleSort
   **e. MergeSort

6
Známky: 1
Ktoré z uvedených operácií nie sú operáciami ADT nat?
Vyberte aspon jednu odpoved.
   **a. CAT
   **b. MAKE
   c. SUCC
   d. MUL

7
Známky: 1
Operáciu Member je na ÚŠ zoznam (s n prvkami) možné vykonat v case:
Vyberte aspon jednu odpoved.
   **a. O(n)
   b. Žiadna z uvedených možností
   c. O(1)
   d. O(log n)

8
Známky: 1
Ktoré zo stratégií oznacovania (prechádzania) stromov možno aplikovat aj na iné ako binárne stromy?
Vyberte aspon jednu odpoved.
   **a. Postorder
   **b. Preorder
   c. Inorder

9
Známky: 1
Dobrá hašovacia funkcia by mala mat tieto vlastnosti:
Vyberte aspon jednu odpoved.
   a. vysoká miera kolízií
   **b. nízka miera kolízií
   c. vysoká zložitost výpoctu
   **d. nízka zložitost výpoctu

10
Známky: 1
Aká je logaritmická cena inštrukcie ADD *i stroja RASP umiestnenej v pamäti od adresy j?
Vyberte aspon jednu odpoved.
   **a. žiadna z uvedených
   b. l(j)+l(c(i))+l(c(c(i)))
   c. l(c(0))+l(i)+l(c(i))+l(c(c(i)))

   d. l(c(0))+l(i)+l(c(i))
Cas zostávajúci do ukoncenia testu


USA_TEST1
Musíte mať nainštalovanú podporu JavaScriptu, aby ste mohli pokračovať ďalej!

1
Známky: 1
Pri použití hašovania je vloženie n prvkov (operácia INSERT), najhoršom prípade vykonané v čase:
Vyberte aspoň jednu odpoveď.

a. T(n) = O(log n)

b. T(n) = O(n)

c. T(n) = O(n logn)

**d. T(n) = O(n2)

2
Známky: 1
Medzi triediace algoritmy využívajúce operáciu porovnaia triedených prvkov nepatria:
Vyberte aspoň jednu odpoveď.

a. Heap sort

**b. Radix sort

**c. Merge sort

d. Quick sort

e. Bubble sort

3
Známky: 1
Lineárny model RAM neobsahuje tieto inštrukcie:
Vyberte aspoň jednu odpoveď.

**a. HALT

b. READ

c. STORE

d. MUL

4
Známky: 1
Aká je logaritmická cena opernadu 'i' stroja RAM?
Vyberte aspoň jednu odpoveď.

a. l(i)+l(c(i))+l(c(c(i)))

b. žiadna z uvedených

**c. l(i)+l(c(i))

d. l(i)

5
Známky: 1
Binárny vyhľadávací strom (BVS) je usporiadaný stratégiou:
Vyberte aspoň jednu odpoveď.

**a. Inorder

b. Postorder

c. inou

d. Preorder

6
Známky: 1
ÚŠ zoznam (smerníkovo-reprezentovaný) nemôže nikdy:
Vyberte aspoň jednu odpoveď.

**a. vypísať svoj obsah v čase O(1)

b. byť prázdny

c. byť utriedený

d. mať smerníky na predchádzajúci aj nasledujúci prvok zoznamu

7
Známky: 1
Veta o povahe a význame dekompozície, ak a = c:

Vyberte aspoň jednu odpoveď.

a. T(n) = O(n)

**b. T(n) = O(n.logn)

c. T(n) = O(nlogca)

8
Známky: 1
Ktoré z uvedených operácií sú operáciami ADT stack?
Vyberte aspoň jednu odpoveď. (prednaska č3 8 strana)

**a. TOP

b. CUT

c. FRONT

**d. POP

9
Známky: 1
Medzi triediace algoritmy využívajúce operáciu porovnaia triedených prvkov patria:
Vyberte aspoň jednu odpoveď.

**a. Quick sort

**b. Bubble sort

**c. Heap sort

d. Merge sort

e. Radix sort

10
Známky: 1
Pri INORDER prechode daným binárnym stromom (na obrázku) budú vypísané hodnoty v poradí:

Vyberte aspoň jednu odpoveď.

/krasny obrazok, v kazdom pripade bol koren stromu 9, takze b | d /

a. 9,3,4,2,8

b. 3,2,9,4,8

c. 3,2,4,8,9

d. 2,3,9,8,4

e. 2,3,8,4,9

Čas zostávajúci do ukončenia testu

USA_TEST1
Musíte mať nainštalovanú podporu JavaScriptu, aby ste mohli pokračovať ďalej!

1
Známky: 1
Pri použití hašovania je vloženie n prvkov (operácia INSERT), najhoršom prípade vykonané v čase:
Vyberte aspoň jednu odpoveď.

a. T(n) = O(log n)

b. T(n) = O(n)

c. T(n) = O(n logn)

**d. T(n) = O(n2)    **

2
Známky: 1
Medzi triediace algoritmy využívajúce operáciu porovnaia triedených prvkov nepatria:
Vyberte aspoň jednu odpoveď.

a. Heap sort

**b. Radix sort    **

**c. Merge sort    **

d. Quick sort

e. Bubble sort

3
Známky: 1
Lineárny model RAM neobsahuje tieto inštrukcie:
Vyberte aspoň jednu odpoveď.

a. HALT    **

b. READ

c. STORE

d. MUL

4
Známky: 1
Aká je logaritmická cena opernadu 'i' stroja RAM?
Vyberte aspoň jednu odpoveď.

a. l(i)+l(c(i))+l(c(c(i)))

b. žiadna z uvedených

c. l(i)+l(c(i))    **

d. l(i)

5
Známky: 1
Binárny vyhľadávací strom (BVS) je usporiadaný stratégiou:
Vyberte aspoň jednu odpoveď.

a. Inorder    **

b. Postorder

c. inou

d. Preorder

6
Známky: 1
ÚŠ zoznam (smerníkovo-reprezentovaný) nemôže nikdy:
Vyberte aspoň jednu odpoveď.

a. vypísať svoj obsah v čase O(1)    **

b. byť prázdny

c. byť utriedený

d. mať smerníky na predchádzajúci aj nasledujúci prvok zoznamu

7
Známky: 1
Veta o povahe a význame dekompozície, ak a = c:

Vyberte aspoň jednu odpoveď.

a. T(n) = O(n)

**b. T(n) = O(n.logn)

c. T(n) = O(nlogca)

8
Známky: 1
Ktoré z uvedených operácií sú operáciami ADT stack?
Vyberte aspoň jednu odpoveď.

a. TOP    **

b. CUT

c. FRONT

d. POP    **

9
Známky: 1
Medzi triediace algoritmy využívajúce operáciu porovnaia triedených prvkov patria:
Vyberte aspoň jednu odpoveď.

a. Quick sort    **

b. Bubble sort    **

c. Heap sort    **

d. Merge sort

e. Radix sort

10
Známky: 1
Pri INORDER prechode daným binárnym stromom (na obrázku) budú vypísané hodnoty v poradí:

Vyberte aspoň jednu odpoveď.

/krasny obrazok, v kazdom pripade bol koren stromu 9, takze b | d /

a. 9,3,4,2,8

b. 3,2,9,4,8    ??

c. 3,2,4,8,9

d. 2,3,9,8,4    ??

e. 2,3,8,4,9

Čas zostávajúci do ukončenia testu

USA_TEST1
Musíte mať nainštalovanú podporu JavaScriptu, aby ste mohli pokračovať ďalej!

1
Známky: 1
Medzi fundamentálne operácie na ADT množina patria:
Vyberte aspoň jednu odpoveď. (prednaska č8 1strana)

**a. SPLIT???

b. CUT

c. MAX

**d. FIND

2
Známky: 1
Ktoré zo stratégií označovania (prechádzania) stromov možno aplikovať aj na iné ako binárne stromy?
Vyberte aspoň jednu odpoveď.

**a. Preorder

b. Inorder

**c. Postorder

3
Známky: 1
Pri použití hašovania je vloženie n prvkov (operácia INSERT), najhoršom prípade vykonané v čase:
Vyberte aspoň jednu odpoveď.

a. T(n) = O(n)

b. T(n) = O(n logn)

c. T(n) = O(log n)

**d. T(n) = O(n2)

4
Známky: 1
Aká je logaritmická cena inštrukcie LOAD *i stroja RAM?
Vyberte aspoň jednu odpoveď.

a. l(c(0))+l(i)+l(c(i))+l(c(c(i)))

b. l(c(0))+l(i)+l(c(i))

c. l(i)+l(c(i))

**d. l(i)+l(c(i))+l(c(c(i)))

5
Známky: 1
Pri PREORDER prechode daným binárnym stromom (na obrázku) budú vypísané hodnoty v poradí:

Vyberte aspoň jednu odpoveď.

a. 9,3,8,4,2

b. 9,3,4,8,2

c. 8,3,9,4,2

d. 8,3,2,4,9

e. 3,8,9,2,4

6
Známky: 1
Medzi triediace algoritmy využívajúce operáciu porovnaia triedených prvkov nepatria:
Vyberte aspoň jednu odpoveď.

a. Bubble sort

**b. Merge sort

c. Heap sort

**d. Radix sort

e. Quick sort

7
Známky: 1
Rozhodovací strom pre usporiadanie 3 prvkov a,b,c (na obrázku) obsahuje v liste označenom (4) postupnosť v tvare:

Vyberte aspoň jednu odpoveď.

a. a < c < b

b. a < b < c

c. c < a < b

d. b < a < c

8
Známky: 1
Operáciu Cat je na ÚŠ zoznam (s n prvkami) možné vykonať v čase:
Vyberte aspoň jednu odpoveď.

**a. O(1)

b. O(log n)

c. Žiadna z uvedených možností

d. O(n)

9
Známky: 1
Ktoré z uvedených sú korektné definície operácií (Opns) ADT string?
Vyberte aspoň jednu odpoveď. (3 prednaksa a 8strana)

a. MAKE:string -> alph

**b. MAKE:alph -> string

c. CAT:alph alph -> string

**d. EMPTY:-> string

10
Známky: 1
Aká je logaritmická cena opernadu 'i' stroja RAM?
Vyberte aspoň jednu odpoveď.

a. l(i)+l(c(i))+l(c(c(i)))

**b. l(i)+l(c(i))

c. žiadna z uvedených

d. l(i)

Čas zostávajúci do ukončenia testu

USA_TEST1
Musíte mať nainštalovanú podporu JavaScriptu, aby ste mohli pokračovať ďalej!

1
Známky: 1
Medzi fundamentálne operácie na ADT množina patria:
Vyberte aspoň jednu odpoveď. (prednaska č8 1strana)

a. SPLIT **

b. CUT

c. MAX

d. FIND **

2
Známky: 1
Ktoré zo stratégií označovania (prechádzania) stromov možno aplikovať aj na iné ako binárne stromy?
Vyberte aspoň jednu odpoveď.

a. Preorder **

b. Inorder

c. Postorder **

3
Známky: 1
Pri použití hašovania je vloženie n prvkov (operácia INSERT), najhoršom prípade vykonané v čase:
Vyberte aspoň jednu odpoveď.

a. T(n) = O(n)

b. T(n) = O(n logn)

c. T(n) = O(log n)

d. T(n) = O(n2) **

4
Známky: 1
Aká je logaritmická cena inštrukcie LOAD *i stroja RAM?
Vyberte aspoň jednu odpoveď.

a. l(c(0))+l(i)+l(c(i))+l(c(c(i)))

b. l(c(0))+l(i)+l(c(i))

c. l(i)+l(c(i))

d. l(i)+l(c(i))+l(c(c(i))) **

5
Známky: 1
Pri PREORDER prechode daným binárnym stromom (na obrázku) budú vypísané hodnoty v poradí:

Vyberte aspoň jednu odpoveď.

a. 9,3,8,4,2

b. 9,3,4,8,2

c. 8,3,9,4,2

d. 8,3,2,4,9

e. 3,8,9,2,4

6
Známky: 1
Medzi triediace algoritmy využívajúce operáciu porovnaia triedených prvkov nepatria:
Vyberte aspoň jednu odpoveď.

a. Bubble sort

**b. Merge sort

c. Heap sort

**d. Radix sort

e. Quick sort

7
Známky: 1
Rozhodovací strom pre usporiadanie 3 prvkov a,b,c (na obrázku) obsahuje v liste označenom (4) postupnosť v tvare:

Vyberte aspoň jednu odpoveď.

a. a < c < b

b. a < b < c

c. c < a < b

d. b < a < c **(asi)

8
Známky: 1
Operáciu Cat je na ÚŠ zoznam (s n prvkami) možné vykonať v čase:
Vyberte aspoň jednu odpoveď.

a. O(1) **

b. O(log n)

c. Žiadna z uvedených možností

d. O(n)

9
Známky: 1
Ktoré z uvedených sú korektné definície operácií (Opns) ADT string?
Vyberte aspoň jednu odpoveď.

a. MAKE:string -> alph

b. MAKE:alph -> string    **

c. CAT:alph alph -> string

d. EMPTY:-> string **

10
Známky: 1
Aká je logaritmická cena opernadu 'i' stroja RAM?
Vyberte aspoň jednu odpoveď.

a. l(i)+l(c(i))+l(c(c(i)))

b. l(i)+l(c(i)) **

c. žiadna z uvedených

d. l(i)

Kuko · 17.06.2009, 19:12:29

Tak v spolupraci s skorec1 je na svete verzia 1.1 z screenov (fotene mobilom ) uz su oznacene vsetky otazky

http://www.upnito.sk/download.php?dwToken=1c29db5dcdf155fdc345faa25a15973e

Dante · 17.06.2009, 21:07:07

Neviete kolko roznych testov je ? lebo nepredpokladam ze by tie screeny boli jedina skupina, alebo hej ?

skorec1 · 17.06.2009, 21:10:32

ake testy? ved to moodle generuje nahodne otazky...

skorec1 · 17.06.2009, 21:30:20

Quote from: Kuko on 17.06.2009, 19:12:29
Tak v spolupraci s skorec1 je na svete verzia 1.1 z screenov (fotene mobilom ) uz su oznacene vsetky otazky

http://www.upnito.sk/download.php?dwToken=1c29db5dcdf155fdc345faa25a15973e

10 otazka: UŠ typu Zlučovateľná halda (Mergeable heap - INSERT, DELETE, UNION, MIN)
10 prednaska 4strana (lazy pdf)

19 otazka: Technika dynamicke programovanie relaizuje (výpočet riešení všetkých subproblémov)
5 prednaska strana 1 (lazy pdf)

Sxx · 17.06.2009, 22:08:30

Tak mam tu zopar otazok z mobilu ktore som v screenoch doteraz alebo dominule tych txt nevidel....niektore uz mozno su zodpovedane. Bol by som rad keby ich niekto doveryhodny vypracoval ja sa za takeho nepovazujem

)), potom sem mozem hodit aj spravne oznacene screeny ak by ste este chceli

1 ) ADT podla narokov na pamet rozdelujeme na
a) dynamicke
b) neohranicene
c) jednoduche
d) staticke
e) zlozene

2) Procedura SELECTrealizuje delenie postupnosti S na 3 casti (S1 S2 S3) vzhladom na median m. Maximalny rozmer postupnosti S1 (respektive S3) je?
a) (2/3)n
b) (1/4)n
c) (1/2)n
.... mozno viac konci screen

3) Casova zlozitost je definovana ako pocet jednotiek casu potrebnych na spracovanie vstupu velkosti ak jednotka casu n je 1ms, vstup akeho najvecsieho rozmeru spracuje algoritmus s casovou zlozitostou T(n)=2^n za 1 sekundu?
a) 9
b) 8
c) 10
d) 11

4) Procedura BUILDTREE() pre konstrukciu optimalneho BVS vyuziva techniku.
a) Balancing
b) rekurzia
c) dynamicke programovanie

5) Sucastou alebraickej specifikacie ADT su
a) sorts:zoznam prvkov
b) elm:zoznam elementov
c) fncs:definicia funkcii
d) axms:definicia axiom
e) opns:definicia operacii
f) eqns:definicia axiom

6) Pri pouziti metody separatneho retazenia pre riesenie kolizii hasovania su jednotlivee kluce umiestnene.
a) v samotnej hasovacej tabulke
b) v zoznamoch zodpovedajucich hodnote hasovacej funkcie

7) front ako variant US zoznam-operacie odoberania a vkladania prvkov su realizovane na
a) rovnakej strane zoznamu
b) roznych stranach zoznamu

8 ) Sekundarny index moze byt
a) husty
b) riedky

9) majme binarny strom reprezentovany polom A=(2,3,4,0,5,6,7,0,0,8,9) kde A[1] je koren stromu a lavy potomok ...(cas na screene zavadzal :/ ) je vzdy A[2i], pravy A[2i+1]. Ak A=0 znamena to ze na danej pozicii v strome uzol nieje. Ktory z nasledujucich je vypisom uzlov stromu strategiou postorder
a) 8,9,5,3,4,6,7,2
b) 3,8,5,9,2,6,4,7
c) 2,3,5,8,4,6,9,7
d) 8,9,5,3,6,7,4,2
e) 3,8,5,7,2,4,6,9
f) 2,3,5,6,7,8,9,4
g) 2,3,5,8,9,4,6,7
h) 8,9,5,4,2,3,6,7
i) 3,8,5,2,6,4,9,7

10) Aka je logaritmicka cena operandu "*i" stroja RAM?
a) I(i)
b) I(i)+I(c(i))+I(c(c(i)))
c) ziadna z uvedenych
d) I(i)+I(c(i))

Sxx · 17.06.2009, 23:16:36

Tieto otazky su viac krat ale raz tak a raz tak ale jak to ma byt spravne?

Lineárny model RAM neobsahuje tieto inštrukcie:
Vyberte aspoň jednu odpoveď.

a. HALT
b. READ
c. STORE
d. MUL

Pri použití hašovania je vloženie n prvkov (operácia INSERT), najhoršom prípade vykonané v čase:
Vyberte aspoň jednu odpoveď.

a. T(n) = O(log n)
b. T(n) = O(n)
c. T(n) = O(n logn)
d. T(n) = O(n2)

Veta o povahe a význame dekompozície, ak a = c: T(n) = O(n)

Kuko · 17.06.2009, 23:18:17

Tieto otazky su viac krat ale raz tak a raz tak ale jak to ma byt spravne?

Lineárny model RAM neobsahuje tieto inštrukcie:
Vyberte aspoň jednu odpoveď.

a. HALT **
b. READ
c. STORE
d. MUL

Pri použití hašovania je vloženie n prvkov (operácia INSERT), najhoršom prípade vykonané v čase:
Vyberte aspoň jednu odpoveď.

a. T(n) = O(log n)
b. T(n) = O(n)
c. T(n) = O(n logn)
d. T(n) = O(n2) **

Veta o povahe a význame dekompozície, ak a = c: T(n) = O(n) ---> O(n.log n)

Kuko · 18.06.2009, 00:02:10

tu som spravil toto co som vedel

1 ) ADT podla narokov na pamet rozdelujeme na (prednaska 2 strana8)
a) dynamicke **
b) neohranicene
c) jednoduche
d) staticke **
e) zlozene

2) Procedura SELECT realizuje delenie postupnosti S na 3 casti (S1 S2 S3)

vzhladom na median m. Maximalny rozmer postupnosti S1 (respektive S3) je?
a) (2/3)n
b) (1/4)n
c) (1/2)n
.... mozno viac konci screen Smiley

3) Casova zlozitost je definovana ako pocet jednotiek casu potrebnych na

spracovanie vstupu velkosti ak jednotka casu n je 1ms, vstup akeho

najvecsieho rozmeru spracuje algoritmus s casovou zlozitostou T(n)=2^n za

1 sekundu?
a) 9
b) 8
c) 10
d) 11

4) Procedura BUILDTREE() pre konstrukciu optimalneho BVS vyuziva techniku.
(Pr 9 strana 3)
a) Balancing
b) rekurzia
c) dynamicke programovanie **

5) Sucastou alebraickej specifikacie ADT su (prednsaka 3 strana 7 (hore))
a) sorts:zoznam prvkov **
b) elm:zoznam elementov
c) fncs:definicia funkcii
d) axms:definicia axiom
e) opns:definicia operacii **
f) eqns:definicia axiom ***

6) Pri pouziti metody separatneho retazenia pre riesenie kolizii
hasovania su jednotlivee kluce umiestnene. (pr8 str 7)
a) v samotnej hasovacej tabulke
b) v zoznamoch zodpovedajucich hodnote hasovacej funkcie ** asi

7) front ako variant US zoznam-operacie odoberania a vkladania prvkov su
realizovane na
a) rovnakej strane zoznamu
b) roznych stranach zoznamu

8 ) Sekundarny index moze byt (pr12 str

a) husty **
b) riedky

primarny index je aj husty aj riedky

9) majme binarny strom reprezentovany polom A=(2,3,4,0,5,6,7,0,0,8,9) kde

A[1] je koren stromu a lavy potomok ...(cas na screene zavadzal :/ ) je

vzdy A[2i], pravy A[2i+1]. Ak A=0 znamena to ze na danej pozicii v strome

uzol nieje. Ktory z nasledujucich je vypisom uzlov stromu strategiou

postorder
a) 8,9,5,3,4,6,7,2
b) 3,8,5,9,2,6,4,7
c) 2,3,5,8,4,6,9,7
d) 8,9,5,3,6,7,4,2
e) 3,8,5,7,2,4,6,9
f) 2,3,5,6,7,8,9,4
g) 2,3,5,8,9,4,6,7
h) 8,9,5,4,2,3,6,7
i) 3,8,5,2,6,4,9,7

10) Aka je logaritmicka cena operandu "*i" stroja RAM?
a) I(i)
b) I(i)+I(c(i))+I(c(c(i))) **
c) ziadna z uvedenych
d) I(i)+I(c(i))

skorec1 · 18.06.2009, 02:17:08

9) majme binarny strom reprezentovany polom A=(2,3,4,0,5,6,7,0,0,8,9) kde

A[1] je koren stromu a lavy potomok ...(cas na screene zavadzal :/ ) je

vzdy A[2i], pravy A[2i+1]. Ak A=0 znamena to ze na danej pozicii v strome

uzol nieje. Ktory z nasledujucich je vypisom uzlov stromu strategiou

postorder
a) 8,9,5,3,4,6,7,2
b) 3,8,5,9,2,6,4,7
c) 2,3,5,8,4,6,9,7
d) 8,9,5,3,6,7,4,2
e) 3,8,5,7,2,4,6,9
f) 2,3,5,6,7,8,9,4
g) 2,3,5,8,9,4,6,7
h) 8,9,5,4,2,3,6,7
i) 3,8,5,2,6,4,9,7

mas pole A=(2,3,4,0,5,6,7,0,0,8,9)
A[1] je prvy prvok.
A[1]= 2
lavy potomok A[1] je A[2]=3 a pravy A[3]=4
koren je A, lavy potomok A[2i] a pravy potomok A[2i+1]
A[2] ma laveho potomka A[4] (lebo 2*2 = 4) a praveho A[5] (lebo 2*2 + 1 = 5)
keby si mal A[10] tak lavy bude A[20] a pravy A[21]
A[2] = 3
A[11] = 9

3 ma laveho potomka 0 (takze nema ziadneho) a praveho 5
takze ak riesis napriklad uzol A[4], tak lavy bude A[8] a pravy A[9]
tie cisla v hranatych zatvrokach za A su indexy pola
to nie su hodnoty uzla

2
/ \
3 4
/ \ / \
0 5 6 7
/ \ /\
0 0 8 9

tie 0ky nepiste to su len pre prehladnost!
8,9,5,3,6,7,4,2

Inorder Ľ,K,P
Preorder K,Ľ,P
Postorder Ľ,P,K

no a potom pouzijeme postorder
8,9,5,3,6,7,4,2 takye vyslo Dcko, pripadne ma opravte!

thx stjopa

Kuko · 18.06.2009, 02:49:03

Dalsia sada otazok mali by byt spravne urobene
http://www.upnito.sk/download.php?dwToken=88472ec20169183bcd82e7a05c1ec039

skorec1 · 18.06.2009, 02:50:07

jak mali? ved musia nie!:D

Kuko · 18.06.2009, 03:09:42

Quote from: skorec1 on 18.06.2009, 02:50:07
jak mali? ved musia nie!:D

musia by mozno povedl ujo Simonak keby ich opravoval

skorec1 · 18.06.2009, 06:39:05

Lineárny model RAM neobsahuje tieto inštrukcie:
Vyberte aspon jednu odpoved.
   **a. HALT
   b. STORE
   c. MUL
   d. READ

v prednaskach je napisane ze sa predpoklada ze udaje su uz v pamati čiže read sa nepouziva tiez...