Domeniul III. Analiza şi elaborarea algoritmilor: Tipuri de date structurate. Subprograme. Structuri dinamice de date. Tehnici de programare.

16:29 0 Comments

Elaborarea modelelor informatice a obiectelor, sistemelor şi proceselor frecvent întâlnite în activitatea cotidiană.
 Aplicarea metodelor de algoritmizare, de formalizare, de analiză, de sinteză şi de programare pentru soluţionarea problemelor legate de prelucrarea automatizată a informaţiei.
 Translarea algoritmilor frecvent utilizaţi într-un limbaj de programare de nivel înalt.
 Recunoaşterea şi utilizarea formulelor metalingvistice şi a diagramelor sintactice ale declaraţiilor de tipuri de date în studiu.
 Prelucrarea datelor_structurate.
 Alegerea structurii de date, adecvate rezolvării unei probleme.
6.1. Să utilizeze diagramele sintactice şi formulele metalingvistice pentru verificarea corectitudinii definirii tipurilor de date structurate.
6.2. Să definească tipuri de date structurate.
6.3. Să determine corectitudinea utilizării operaţiilor de prelucrare a datelor structurate.
6.4. Să explice modul de referire a componentelor tablourilor, şirurilor de caractere, articolelor.
6.5. *Să precizeze mulţimea de valori şi operaţiile admise pentru tipul de date mulţime.
6.6. Să utilizeze fişierele text.
6.7. *Să clasifice fişierele după tipul operaţiilor permise şi modul de acces
7.1. Să utilizeze diagramele sintactice şi formulele metalingvistice pentru scrierea şi verificarea corectitudinii instrucţiunilor limbajului de programare de nivel înalt.
7.2. Să elaboreze programe de calculator, destinate prelucrărilor de date ce apar în procesul de studiere a disciplinelor şcolare şi de soluţionare a problemelor frecvent întîlnite în activitatea cotidiană:
- identificarea şi calcularea numărului de elemente cu anume proprietăţi ale structurilor de date (de exemplu, valoarea maximă, valoarea minimă, număr prim etc.);
- operaţii cu elementele Aprobată la Comisia Naţională de Examene Proces-verbal nr. 9 din 27 decembrie 2012
Validată prin Ordinul Ministrului Educaţiei nr. 1042 din 27 decembrie 2012
Programa pentru examenul de bacalaureat, 2013 INFORMATICA
Ministerul Educaţiei Agenţia de Evaluare şi Examinare
9
structurilor de date (adăugarea, excluderea, afişarea, reordonarea, modificarea);
- operaţii de totalizare/ selecţie/ ordonare (suma elementelor, media aritmetică, ordonarea elementelor după un criteriu anume etc.);
- citirea datelor de la tastatură şi afişarea datelor pe ecranul monitorului;
- scrierea şi citirea datelor în fişierele text.
 Prelucrarea datelor cu ajutorul subprogramelor predefinite şi a subprogramelor elaborate de către utilizator.
 Organizarea comunicării între programul / subprogramul apelant şi subprogramul apelat.
 Proiectarea structurală a algoritmului şi a programului.
 *Utilizarea recursiei pentru rezolvarea problemelor.
8.1 Să identifice legăturile informaţionale (date) şi de control (apeluri) între programul principal şi subprogramele apelate.
8.2. Să utilizeze diagramele sintactice şi formulele metalingvistice pentru scrierea şi verificarea corectitudinii declaraţiilor şi a instrucţiunilor de apel de subprograme.
8.3 Să utilizeze funcţiile şi procedurile predefinite ale unui limbaj de programare de nivel înalt.
8.4 Să elaboreze programe, care utilizează subprograme predefinite şi subprograme definite de utilizator.
8.5 *Să elaboreze subprograme recursive.
 *Utilizarea structurilor dinamice de date pentru soluţionarea problemelor întâlnite în activitatea cotidiană.
 *Implementarea şi gestionarea structurilor dinamice de date frecvent utilizate.
 *Gestionarea memoriei interne a calculatorului
9.1. *Să identifice corectitudinea operaţiilor de creare, de utilizare şi de distrugere a variabilelor dinamice.
9.2. *Să elaboreze programe în care se utilizează variabile dinamice.
9.3. *Să explice modul de alocare a memoriei operative în cazul utilizării variabilelor statice şi variabilelor Aprobată la Comisia Naţională de Examene Proces-verbal nr. 9 din 27 decembrie 2012
Validată prin Ordinul Ministrului Educaţiei nr. 1042 din 27 decembrie 2012
Programa pentru examenul de bacalaureat, 2013 INFORMATICA
Ministerul Educaţiei Agenţia de Evaluare şi Examinare
10
dinamice.
9 .4 *Să utilizeze liste, stive, cozi şi arbori binari pentru stocarea şi prelucrarea datelor.
 *Estimarea complexităţii algoritmilor.
 *Utilizarea tehnicilor de programare la rezolvarea problemelor din diferite domenii.
 *Alegerea tehnicii de programare adecvate problemei.
10.1. *Să estimeze complexitatea temporală a algoritmilor şi a programelor elaborate.
10.3. *Să estimeze volumul de memorie, cerut de algoritmii şi programele elaborate.
10.3. *Să rezolve problemele frecvent întîlnite în activitatea cotidiană folosind tehnicile de programare: iteraţia, recursia, trierea, metoda Greedy, metoda reluării.
Exemple de itemi
Itemul 1.
Fie date următoarele declaraţii:
const n=40; type Elev = record Nume : string; Prenume : string; NotaMedie : real end; ListaElevi = array[1..n] of Elev; var A: ListaElevi; E: Elev; i:integer; a) Scrieţi tipurile de date declarate de către utilizator: _____________________________________________________________________ b) Scrieţi identificatorii ce reprezintă denumiri de cîmpuri: _____________________________________________________________________
c) Pentru fiecare din instrucţiunile din coloana stângă a tabelului ce urmează determinaţi, dacă acestea sînt corecte sau greşite, şi bifaţi opţiunea respectivă:
A[i]:=E;
 Corect  Greşit
Readln(E);
 Corect  Greşit
Elev.NotaMedie:=8.5;
 Corect  Greşit
E.Nume:=A[n].Nume;
 Corect  Greşit
Itemul 2.
Se consideră următorul program Pascal: Aprobată la Comisia Naţională de Examene Proces-verbal nr. 9 din 27 decembrie 2012
Validată prin Ordinul Ministrului Educaţiei nr. 1042 din 27 decembrie 2012
Programa pentru examenul de bacalaureat, 2013 INFORMATICA
Ministerul Educaţiei Agenţia de Evaluare şi Examinare
11
program p6; { nivel 0 } var n:integer; function ppp(n : integer) : boolean; { nivel _____ } var i:integer; begin {ppp} ppp:=true; for i:=2 to n-1 do if n mod i=0 then ppp:=false end; {ppp} procedure pp; { nivel _____ } var j : integer; begin {pp} for j:=2 to n do if ppp(j) then Write(j,’ ’); end; { pp } begin n:=10; pp; end.
a) Subliniaţi în textul programului parametrii formali ai subprogramelor.
b) Stabiliţi valoarea de adevăr a afirmaţiei:
c)
Funcţia ppp(n) returnează valoarea TRUE pentru orice număr impar n, transmis ca parametru actual.  Adevărat  Fals
d) Scrieţi ce se va afişa pe ecarn în urma executării programului p6:
_____________________ _____________________
e) Înscrieţi în spaţiile libere ale comentariilor din programul de mai sus nivelul de imbricare a fiecărui bloc în structura de bloc al programului.
Itemul 3.
La parcurgerea în inordine a arborelui binar din imaginea alăturată, nodurile acestuia au fost vizitate în următoarea ordine:
ZAQWNSEHKPR
A. Înscrieţi în nodurile libere de pe desen simbolurile ce le corespund conform informaţiei despre ordinea parcurgerii arborelui.
B. Scrieţi numărul de niveluri ale arborelui din imagine:
__________
C. Scrieţi simbolul ce notează rădăcina arborelui: _________
Itemul 4.
Aprobată la Comisia Naţională de Examene Proces-verbal nr. 9 din 27 decembrie 2012
Validată prin Ordinul Ministrului Educaţiei nr. 1042 din 27 decembrie 2012
Programa pentru examenul de bacalaureat, 2013 INFORMATICA
Ministerul Educaţiei Agenţia de Evaluare şi Examinare
12
Fie date următoarele declaraţii Pascal:
type t=record nume: string; varsta :integer; end; q=array[1..10] of t; z=array[1..10]of string; var n,i : integer; a: ^q; b: z;
Stabiliţi valorile de adevăr ale următoarelor propoziţii:
A. Valorile elementelor tabloului a vor fi stocate în zona heap a memoriei.
 Adevăr  Fals
B. Variabilele declarate vor ocupa în segmentul de date a memoriei 2584 octeţi.
 Adevăr  Fals
C. Pentru a aloca memorie variabilei a, în program va fi necesară instrucţiunea new(a)
 Adevăr  Fals
D. Memoria alocată variabilei a nu va putea fi eliberată pe parcursul întregii execuţii a programului
 Adevăr  Fals
E. Atribuirea a[5].nume:=’Ion’; este corectă.
 Adevăr  Fals
F. Atribuirea a^[7].nume:=b[8]; este corectă.
 Adevăr  Fals
G. Atribuirea a^[8].varsta:= ^n; este corectă.
 Adevăr  Fals
Itemul 5.
Instituţia de învăţămînt are N (N ≤ 200) studenţi. Se cere elaborarea unei liste de M studenţi, care vor primi bursă. Lista viitorilor studenţi bursieri se elaborează în baza reuşitei acestora.
Scrieţi un program care citeşte de la tastatură numele, prenumele şi nota medie generală ale fiecărui student şi formează lista bursierilor, sortând studenţii respectivi în ordinea descreşterii notei medii generale. Lista astfel formată trebuie înscrisă în fişierul text DATE.OUT.
Intrare: De la tastatură se introduc valorile întregi N – numărul de studenţi şi M – numărul de burse disponibile. În continuare, pentru fiecare student se citesc două şiruri de caractere  numele şi prenumele şi un număr real  nota medie generală.
Ieşire: Fişierul DATE.OUT conţine M linii. În fiecare linie se conţine numele, prenumele şi nota medie generală a studenţilor-bursieri, separate prin spaţiu. Lista se afişează în ordinea descreşterii notelor medii.
Notă: Rezolvarea va fi apreciată pentru: declararea tipurilor de date şi a variabilelor; operarea cu fişierele text; citirea şi scrierea datelor; organizarea algoritmului de sortare