arbori - informatica
Presentation
•
Computers, Science, Education
•
12th Grade
•
Hard
Emilia Felicia
Used 2+ times
FREE Resource
5 Slides • 4 Questions
1
ARBORI - informatica
Lecție de consolidare a cunoștințelor
2
Să ne reamintim
ARBORELE LIBER
Definiţia arborelui liber
Se numeşte arbore liber A un graf neorientat conex şi fără cicluri.
Observaţie.
De obicei se omite adjectivul „liber”, referirea la un graf conex aciclic făcându-se numai cu numele arbore.
Definiţie
Se numeşte subarbore al arborelui A=(X,U), orice arbore S=(Y,V) care are proprietatea: Y⊆X şi V⊆U.
3
Teorema
Următoarele definiţii sunt echivalente pentru un graf G cu n noduri şi m muchii:
(1) G este un arbore.
(2) G este un graf aciclic cu n-1 muchii.
(3) G este un graf conex cu n-1 muchii.
(4) G este un graf fără cicluri maximal (dacă în graful fără cicluri G unim două noduri oarecare neadiacente printr-o muchie, graful obţinut conţine un ciclu).
(5) G este un graf conex minimal (dacă în graful conex G suprimăm o muchie oarecare, graful obţinut nu mai este conex).
(6) Orice pereche de noduri este legată printr-un lanţ şi numai unul.
4
Arbore binar
Definiţia arborelui binar
Se numeşte arbore binar un arbore cu rădăcină poziţional care are proprietatea că fiecare nod are cel mult doi descendenţi direcţi (succesori).
Terminologie:
- Cei doi succesori ai unui nod (dacă există) se numesc succesor stâng (subarbore stâng) şi succesor drept (subarbore drept)
5
Multiple Choice
Pentru un arbore binar cu n niveluri, numărul maxim de noduri din arbore este:
n
2 ⋅ n
2n −1
2n-1
6
Multiple Choice
Parcurgerea în postordine presupune:
parcurgerea subarborelui stâng, a vârfului, apoi a subarborelui drept
parcurgrea vârfului, a subarborelui stâng după care a celui drept
parcurgerea subarborelui stâng, a subarborelui drept după care a vârfului
vizitarea rădăcinii, a nodurilor de pe nivelul 1, a nodurilor de pe nivelul doi etc.
7
Arbore binar strict
Definiţie
Se numeşte arbore binar stict un arbore care are proprietatea că fiecare nod, cu excepţia nodurilor terminale, are exact doi descendenţi (succesori).
Un arbore binar strict, care are n noduri terminale, are în total 2n-1 noduri.
Un arbore binar strict are un număr impar de noduri.
8
Multiple Choice
Care este tipul de parcurgere al unui arbore binar asociat unei expresii aritmetice pentru a obţine forma poloneză ?
inordine
preordine
postordine
lăţime
9
Multiple Choice
Dacă st şi dr sunt vectorii de reprezentare ai unui arbore binar, unde trebuie pusă instrucţiunea cout<< radacina; astfel încât parcurgerea să fie în inordine :
înaintea parcurgerii st si dr
între parcurgerile st și dr
după parcurgerea st și dr
nu conteaza unde se pune aceasta instrucțiune
ARBORI - informatica
Lecție de consolidare a cunoștințelor
Show answer
Auto Play
Slide 1 / 9
SLIDE
Similar Resources on Wayground
26 questions
IP versi 6
Presentation
•
10th Grade
31 questions
Forme majore de relief
Presentation
•
5th - 12th Grade
5 questions
KEANEKARAGAMAN
Presentation
•
1st - 6th Grade
42 questions
Cine sunt eu? Recapitulare sistemul cardiovascular
Presentation
•
11th Grade
7 questions
Dezvoltarea mobilitatii in karate
Presentation
•
1st Grade
14 questions
Belum Berjudul
Presentation
•
11th Grade
12 questions
Quotiēns?
Presentation
•
9th - 12th Grade
20 questions
Latin I Unit 1 Part 2 Nominatives and Accusatives Recap Lesson
Presentation
•
12th Grade
Popular Resources on Wayground
24 questions
PBIS-HGMS Day 10
Quiz
•
6th - 8th Grade
10 questions
HCS SCI 03 Summer School Review 3
Quiz
•
3rd Grade
11 questions
Home Scope
Quiz
•
7th - 8th Grade
15 questions
HCS SCI 05 Summer School Assessment 3 Review
Quiz
•
5th Grade
35 questions
Lufkin Road Middle School Student Handbook & Policies Assessment
Quiz
•
7th Grade
18 questions
Geo 11.3 Area of Circles and Sectors
Quiz
•
9th - 11th Grade