Zárthelyi dolgozatok 

1. feladat:

 

Adott a háromjegyű bináris számok következő sorozata: 001, 100, 111, 011, 110, 010. Rendezzük a számokat a "RADIX előrefelé" rekurzív algoritmusú edényrendezéssel! Minden csere után adjuk meg a tömb állapotát (tartalom + edényhatárok)!

 

2. feladat:

 

a)         Nyílt címzéssel a h(k) = k mod 11 hasító függvény segítségével és négyzetes próbálással helyezzük el a következő sorozatot az a[0..10] elemű tömbbe:

18,28,36,17,62,48,50,16.

A négyzetes próbálás azt jelenti, hogy kulcsütközés esetén a következő sorozat felhasználásával próbálja az elhelyezést: S=0,1,-1,4,-4,9,-9,…,

Tehát a pontos hasító függvény: (h(k)-s_i) mod 11.

b)         Írjuk le, hogy milyen lépésekben dől el, hogy a 40-es kulcs nincs a tömbben!

 

 

3. feladat:

 

            Szemléltessük a Dijkstra algoritmus működését az alábbi gráfon!

           

            Szülő    Gyerek    Költség

               A          B            3

               A          C            5

               B          C            1

               B          D            4

               C          D            2

               C          E            2

               D          E            3

 

            A startcsúcs legyen az A! Adjuk meg a d és π  tömbök sorozatát, ahogy az egyes csúcsokat  kiterjesztjük (gyerekeit feldolgozzuk).

 

4. feladat:

 

Adott egy láncoltan ábrázolt irányított gráf. Kiegészítjük a csúcspontokat tartalmazó rekordot egy hivatkozas numerikus mezővel. Készítsünk olyan programot, amely, az inputban definiálatlan hivatkozas mezőkbe minden csúcsra beírja az illető csúcsot közvetlenül megelőző csúcsok számát. (Az  A  csúcs közvetlenül megelőzi  B -t, ha  A -ból  B -be irányított él mutat.)

--------------------------------------------------------------------------------------------

1. feladat:

 

Adott a háromjegyű bináris számok következő sorozata: 011, 001, 100, 111, 110, 010. Rendezzük a számokat a "RADIX előrefelé" rekurzív algoritmusú edényrendezéssel! Minden csere után adjuk meg a tömb állapotát (tartalom + edényhatárok)!

 

2. feladat:

 

a)         Nyílt címzéssel a h(k) = k mod 11 hasító függvény segítségével és négyzetes próbálással helyezzük el a következő sorozatot az a[0..10] elemű tömbbe:

17,27,35,16,61,47,49,15.

A négyzetes próbálás azt jelenti, hogy kulcsütközés esetén a következő sorozat felhasználásával próbálja az elhelyezést: S=0,1,-1,4,-4,9,-9,…,

Tehát a pontos hasító függvény: (h(k)-s_i) mod 11.

b)         Írjuk le, hogy milyen lépésekben dől el, hogy a 36-es kulcs nincs a tömbben!

 

 

3. feladat:

 

            Szemléltessük a Dijkstra algoritmus működését az alábbi gráfon!

           

            Szülő    Gyerek    Költség

               A          B            3

               A          C            2

               B          C            1

               B          D            2

               C          D            4

               C          E            2

               D          E            3

 

            A startcsúcs legyen az A! Adjuk meg a d és π  tömbök sorozatát, ahogy az egyes csúcsokat  kiterjesztjük (gyerekeit feldolgozzuk).

 

4. feladat:

 

Adott egy láncoltan ábrázolt irányítatlan gráf. Kiegészítjük a csúcspontokat tartalmazó rekordot egy fokszam numerikus mezővel. Készítsünk olyan programot, amely az inputban definiálatlan fokszam mezőkbe minden csúcsra beírja , hogy mennyi él tartozik a csúcshoz.

 

------------------------------------------------------------

1. feladat:

            Adott egy gráf költségmátrixa, azaz C[i,j]=x jelentése, ha ∞>x>0, akkor vezet él i-ből j-be és az él költsége x, illetve x=∞, ha nem. Tegyük fel, hogy a gráf csúcsai városokat jelölnek és a költségek a városokat összekötő utak hosszát jelentik.

            Bellman-Ford algoritmusával oldjuk meg a következő problémát.

Egy magadott város és egy megadott szomszédja esetén döntsük el, hogy van-e a szomszédhoz rövidebb út más város(ok)on keresztül, és ha igen, akkor adjuk meg, hogy mely városok érintésével.

 

 

2. feladat:

            Szemléltessük Floyd algoritmusát az alábbi gráfon a D^(k) (k Є [0,n] ) mátrixok megadásával!

1

4

3

2

 

                                                      1                                   4

 

 

                                                                              2

                                                     2                                            1

 

 

 

 

 

3. feladat:

            Szemléltessük Prim algoritmusát az alábbi gráfon a d és Π vektorok tartalmának lépésenkénti megadásával! A kezdő csúcs legyen az A csúcs!

A

E

D

B

C

F

 

                                                                    5

                                            1                                                      6

 

 

                                                      2                                 1

                                                               4                5

                                           3                                                           4

 

                                                                       1

4. feladat:

            Adjunk algoritmust, amely megadja egy irányított gráf  egy tovább már nem szűkíthető generátor halmazát!

(Generátor halmaznak nevezzük a gráf csúcsainak olyan részhalmazát, amelyből az összes csúcs elérhető.)

(Útmutatás: Használjuk a mélységi bejárást és koncentráljunk a csúcsok színére!)

 

--------------------------------------------------------

1. feladat:

            Def.: Generátor halmaznak nevezzük a gráf csúcsainak olyan részhalmazát, amelyből az összes csúcs elérhető.

Írjunk eljárást, amely egy irányított gráf  egy tovább már nem szűkíthető generátor halmazát számítja ki!  (Javaslat: Használjuk a mélységi bejárást és fontoljuk meg az egyes csúcsok színének jelentését!)

 

 

2. feladat:

            Szemléltessük Floyd algoritmusát az alábbi gráfon a D^(k) (k Є [0,n] ) mátrixok megadásával!

1

4

3

2

 

                                                      1                                   1

 

 

                                                                              3

                                                     5                                            1

 

 

 

 

 

3. feladat:

            Szemléltessük Prim algoritmusát az alábbi gráfon a d és Π vektorok tartalmának lépésenkénti megadásával! A kezdő csúcs legyen az A csúcs!

A

E

D

B

C

F

 

                                                                    5

                                            7                                                      4

 

 

                                                      2                                 2

                                                               4                5

A honlap ára 78 500 helyett MOST 0 Ft.

Honlapkészítés ingyen:
Ez a weblapszerkesztő alkalmas
ingyen weboldal,
ingyen honlap készítés...

Weblap látogatottság számláló:

Mai: 4
Tegnapi: 1
Heti: 16
Havi: 54
Össz.: 15 052

Látogatottság növelés