Teză clasa a XI-a - Liste înlănţuite şi grafuri

Apărut la 6 septembrie 2015 în Teste de informatică   |   autor: Dan Pracsiu 0 comentarii

Notă: Problemele 1–4 sunt punctate cu 1,5 puncte, iar problema 5 cu 2 puncte. Se acordă 2 puncte din oficiu.

Rândul 1

1. Scrieţi funcţia InsertEnd care primeşte ca parametri un pointer la o listă simplu înlănţuită şi un întreg k, inserează la sfârşitul listei un nou nod care memorează valoarea k.

2. Explicaţi în ce constă operaţia de adăugare a unei informaţii într-o stivă implementată prin intermediul unei liste liniare simplu înlănţuite. Scrieţi apoi o funcţie Add care realizează această operaţie.

3. Scrieţi funcţia NrMuchii care primind ca parametri un întreg n şi matricea de adiacenţă asociată unui graf cu n vârfuri, returnează numărul muchiilor grafului.

4. Scrieţi funcţia CreateList care primeşte ca parametri matricea de adiacenţă a unui graf cu n vârfuri şi un întreg i, cu 1 £ i £ n, creează o listă liniară simplu înlănţuită care memorează nodurile din graf adiacente cu vârful i. Dacă vârful i nu are adiacenţi, lista va rămâne vidă.

5. Avem la dispoziţie funcţiile:
– Insert1(x) care inserează la începutul unei liste simplu înlănţuite un nod cu informaţia x
– Insert2(x) care inserează la sfârşitul unei liste simplu înlănţuite un nod cu informaţia x
Considerăm un vector v de lungime n care memorează o permutare a mulţimii {1,2,…,n}. Numerele memorate în vector pot fi luate doar în ordinea în care se află în vector şi depuse în listă apelând una din cele două funcţii. Se doreşte ca în acest fel să se obţină numerele ordonate crescător. De exemplu, pentru n=4 şi v=(2, 3, 1, 4) construim lista astfel:

Nu pentru orice permutare a mulţimii {1,2,…,n} se poate construi lista ordonată. De exemplu, permutarea {4,1,2,3}.
Cerinţa: Scrieţi funcţia CreateList care primind ca parametri n şi vectorul v, creează lista ordonată crescător apelând doar cele două funcţii. Dacă s-a reuşit construcţia listei, funcţia va returna 1. În caz contrar, funcţia va returna 0.

Rândul 2

1. Scrieţi funcţia Delete care primind ca parametri un pointer la o listă simplu înlănţuită şi un întreg k, elimină din listă primul nod care memorează valoarea k. Se presupune că în listă există cel puţin un nod cu informaţia k.

2. Explicaţi în ce constă operaţia de extragere a unei informaţii într-o coadă implementată prin intermediul unei liste liniare simplu înlănţuite. Scrieţi apoi o funcţie Extract care realizează această operaţie.

3. Scrieţi funcţia NrTerminale care primind ca parametri un întreg n şi matricea de adiacenţă asociată unui graf cu n vârfuri, returnează numărul vârfurilor terminale ale grafului.

4. Scrieţi funcţia MatAd care primeşte ca parametri un întreg i, cu 1 £ i £ n şi un pointer la o listă simplu înlănţuită care memorează vârfurile adiacente lui i dintr-un graf, completează în matricea de adiacenţă linia i.

5. Avem la dispoziţie funcţiile:
– Insert1(x) care inserează la începutul unei liste simplu înlănţuite un nod cu informaţia x
– Insert2(x) care inserează la sfârşitul unei liste simplu înlănţuite un nod cu informaţia x
Considerăm un vector v de lungime n care memorează o permutare a mulţimii {1,2,…,n}. Numerele memorate în vector pot fi luate doar în ordinea în care se află în vector şi depuse în listă apelând una din cele două funcţii. Se doreşte ca în acest fel să se obţină numerele ordonate crescător. De exemplu, pentru n=4 şi v=(2, 3, 1, 4) construim lista astfel:

Nu pentru orice permutare a mulţimii {1,2,…,n} se poate construi lista ordonată. De exemplu, permutarea {4,1,2,3}.
Cerinţa: Scrieţi funcţia CreateList care primind ca parametri n şi vectorul v, creează lista ordonată crescător apelând doar cele două funcţii. Dacă s-a reuşit construcţia listei, funcţia va returna 1. În caz contrar, funcţia va returna 0.

Număr de accesări: 4279

Dan Pracsiu deţinător www.dponline.ro
Profesor, Liceul Teoretic "Emil Racoviță" Vaslui
Membru în Comisia Naţională a Olimpiadelor de Informatică
Pasiuni: istoria, călătoriile, fotografia, muzica clasică