Arbori binari de căutare
R1
1. (2 puncte) Scrieţi un şir de 5 numere naturale ordonat strict crescător. Desenaţi doi arbori de căutare care au fiecare ca parcurgere inordine şirul scris de voi şi în plus aşezarea nodurilor în cei doi arbori să difere prin exact un nod. Este aşa ceva posibil?
2. (2 puncte) Considerăm un arbore de căutare iniţial vid. Desenaţi arborele de căutare obţinut prin inserarea pe rând a cheilor P,R,O,B,L,E,M,A,F,O,A,R,T,E,U,S,O,A,R,A.
3. (3 puncte) Scrieţi funcţia Nivele care primeşte ca parametru un pointer la rădăcina unui arbore binar de căutare memorat prin liste şi returnează numărul de nivele din arbore. Utilizând această funcţie, scrieţi funcţia AVL care primeşte ca parametru un pointer la rădăcina unui arbore binar de căutare şi returnează 1 dacă diferenţa dintre înălţimile subarborilor stâng şi drept este de cel mult 1, sau 0 în caz contrar.
4. (3 puncte) Considerăm un arbore binar de căutare memorat prin liste înlănţuite care în plus ştim că este complet şi are cel puţin 3 nivele complete. Dorim să efectuăm ştergerea din arbore a nodului rădăcină (astfel încât arborele să rămână arbore de căutare). Pentru aceasta abordăm următoarea strategie: luăm cheia dintr-un anumit nod terminal, o vom atribui rădăcinii şi apoi vom şterge nodul terminal. Explicaţi în cel mult două rânduri ce nod terminal trebuie să căutaţi, apoi scrieţi o funcţie care elimină nodul rădăcină după strategia de mai sus.
Notă: Se acordă 2 puncte din oficiu. Orice punctaj care depăşeşte 10 va fi asociat notei 10.
R2
1. (2 puncte) Scrieţi un şir de 5 numere naturale ordonat strict crescător. Desenaţi doi arbori de căutare care au fiecare ca parcurgere inordine şirul scris de voi şi în plus aşezarea nodurilor în cei doi arbori să difere prin exact un nod. Este aşa ceva posibil?
2. (2 puncte) Considerăm un arbore de căutare iniţial vid. Desenaţi arborele de căutare obţinut prin inserarea pe rând a cheilor E,S,T,E,U,N,A,R,B,O,R,E,D,E,C,A,U,T,A,R,E.
3. (3 puncte) Scrieţi funcţia Nivele care primeşte ca parametru un pointer la rădăcina unui arbore binar de căutare memorat prin liste şi returnează numărul de nivele din arbore. Utilizând această funcţie, scrieţi funcţia AVL care primeşte ca parametru un pointer la rădăcina unui arbore binar de căutare şi returnează 1 dacă diferenţa dintre înălţimile subarborilor stâng şi drept este de cel mult 1, sau 0 în caz contrar.
4. (3 puncte) Considerăm un arbore binar de căutare memorat prin liste înlănţuite care în plus ştim că este complet şi are cel puţin 3 nivele complete. Dorim să efectuăm ştergerea din arbore a nodului rădăcină (astfel încât arborele să rămână arbore de căutare). Pentru aceasta abordăm următoarea strategie: luăm cheia dintr-un anumit nod terminal, o vom atribui rădăcinii şi apoi vom şterge nodul terminal. Explicaţi în cel mult două rânduri ce nod terminal trebuie să căutaţi, apoi scrieţi o funcţie care elimină nodul rădăcină după strategia de mai sus.
Notă: Se acordă 2 puncte din oficiu. Orice punctaj care depăşeşte 10 va fi asociat notei 10.
Despre autor
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ă
