|
1.
|
În orice
graf neorientat cu n noduri notate
1, 2, ..., n, cu m muchii şi cu gradele nodurilor
notate d(1), d(2), ..., d(n)
există relaţia: |
||||||||||||
|
a.
|
d(1)=d(2)=...=d(n) |
b.
|
d(1)+d(2)+...+d(n)=2m |
|
|||||||||
|
c.
|
d(1)+d(2)+...+d(n)=m |
d.
|
d(1)+d(2)+...+d(n)=m+n |
|
|||||||||
|
2.
|
Considerând
un graf neorientat având nodurile notate cu 1, 2, 3, 4, 5, corespunzător
liniilor matricei de adiacenţă date, stabiliţi dacă
nodurile 1 şi 3: |
0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 1 0 1 0 1 0 |
|||||||||||
|
a.
|
sunt noduri izolate |
b.
|
sunt conectate printr-un lanţ |
|
|||||||||
|
c.
|
aparţin aceleiaşi componente
conexe |
d.
|
sunt noduri adiacente |
|
|||||||||
|
3.
|
Se
consideră un graf neorientat cu 7 noduri şi 3 muchii. Numărul
de componente conexe din care poate fi format graful este: |
||||||||||||
|
a.
|
exact 4 |
b.
|
cel puţin 5 |
c.
|
4 sau 5 |
d.
|
3 sau 4 |
|
|||||
|
4.
|
Se
consideră un graf orientat cu 6
noduri etichetate cu numere de la 1 la 6 şi 6 arce astfel încât
există un arc de la fiecare nod cu eticheta i către un nod cu
eticheta i*2 dacă există
un astfel de nod sau către nodul cu eticheta i –1 în caz contrar. Care
este lungimea drumului de la 1 la 5
(lungimea drumului=numărul arce) |
||||||||||||
|
a.
|
2 |
b.
|
4 |
c.
|
5 |
d.
|
3 |
|
|||||
|
5.
|
Considerând
un graf orientat având matricea de adiacenţă alturată,
stabiliţi câte dintre nodurile grafului au gradul interior (intern) egal
cu gradul exterior (extern): |
0 1 0 1 0 0 0 0 0 1 0 1 0 0 0 0 1 1 0 0 0 1 0 1 0 |
|||||||||||
|
a.
|
2 |
b.
|
1 |
c.
|
3 |
d.
|
0 |
|
|||||
|
6.
|
Se
consideră un arbore cu următoarele proprietăţi:
rădăcina este nodul 1 (considerat de nivel 1) şi fiecare
nod i (cu 1Ł i Ł 3) aflat pe
nivelul j are ca descendenţi nodurile i+j şi i+2*j. Nodurile i cu
(cu i > 3) sunt
noduri terminale (frunze). Stabiliţi care dintre vectorii următori
este vectorul de taţi (sau de predecesori) corespunzător arborelui: |
||||||||||||
|
a.
|
0 1 1 2 2 3 3 |
b.
|
0 1 1 2 3 2 3 |
|
|||||||||
|
c.
|
0 –1 1 –1 –1 1 1 |
d.
|
0 1 2 2 1 3 3 |
|
|||||||||
|
7.
|
Orice graf
neorientat cu n noduri şi n–1 muchii |
||||||||||||
|
a.
|
este aciclic şi neconex |
b.
|
este conex şi conţine un
ciclu |
|
|||||||||
|
c.
|
este conex dacă şi numai dacă este aciclic |
d.
|
este un arbore |
|
|||||||||
|
8.
|
Care
dintre următoarele matrice poate fi matricea de adiacenţă a
grafului din figura alăturată? |
|
|||||||||||
|
a.
|
1 1 0 1 1 1 0 1 0 0 1 1 1 1 1 1 |
b.
|
0 1 1 1 1 0 0 0 1 0 1 0 1 0 1 0 |
c.
|
0 1 0 1 1 0 1 0 0 1 0 1 1 0 1 0 |
d.
|
0 1 0 1 1 0 0 1 0 0 0 1 1 1 1 0 |
|
|||||
|
9.
|
Se
consideră graful neorientat având
nodurile notate cu 1, 2, 3, 4, 5, corespunzător liniilor matricei de
adiacenţă alăturate. Stabiliţi
care dintre următoarele propoziţii este adevărată. |
0 0 1 0 0 0 0 0 1 1 1 0 0 0 0 0 1 0 0 1 0 1 0 1 0 |
|||||||||||
|
a.
|
orice muchie s-ar elimina graful
devine aciclic |
b.
|
graful este aciclic |
|
|||||||||
|
c.
|
orice nouă muchie s-ar
adăuga graful devine conex |
d.
|
graful este conex |
|
|||||||||
10. Fie arborele
binar din figura urmatoare:
a)Care este sirul de date de intrare necesar
generarii grafului?
b) Parcurgeti arborele prin cele 3 metode
specifice arborilor binari
11. Intr-un
fisier sunt memorate numele a n persoane. Intre cele n persoane se
stabileste o relatie de ierarhie (in varful ierarhiei exista o singura
persoana) . In fisier sunt scrie pe prima linie n, pe linia a doua cele n nume
iar pe linia a treia vectorul de tip tata asociat.
a) sa se afiseze persoanele care nu au subordonati
b)sa se afiseze persoana din varful ierarhiei
c) sa se afiseze toti sefii (directi sau indirecti ai unei personei)
Barem de corectare:
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
Oficiu |
total |
|||
|
0.5 |
0.5 |
0.5 |
0.5 |
0.5 |
0.5 |
0.5 |
0.5 |
0.5 |
a |
b |
a |
b |
c |
1p |
|
|
|
|
|
|
|
|
|
|
|
0.5 |
1 |
0.75 |
0.75 |
1.5 |
|
|