Informatică 2018

Ministerul Educaţiei Naționale Centrul Naţional de Evaluare şi Examinare Examenul de bacalaureat naţional 2018 Proba E. d) Informatică Limbajul C/C++ Varianta 9 Filiera teoretică, profilul real, specializările: matematică-informatică matematică-informatică intensiv informatică Filiera vocaţională, profilul militar, specializarea matematică-informatică • Toate subiectele sunt obligatorii. Se acordă 10 puncte din oficiu. • Timpul de lucru efectiv este de 3 ore. • În rezolvările cerute, identificatorii utilizaţi trebuie să respecte precizările din enunţ (bold), iar în lipsa unor precizări explicite, notaţiile trebuie să corespundă cu semnificaţiile asociate acestora (eventual în formă prescurtată). • În programele cerute, datele de intrare se consideră corecte, validarea acestora nefiind necesară. SUBIECTUL I (30 de puncte) Pentru itemul 1, scrieţi pe foaia de examen litera corespunzătoare răspunsului corect. 1. Variabila x este de tip întreg. Indicați o expresie care are valoarea 1 x<=3 || x>10 dacă și numai dacă expresia C/C++ alăturată are valoarea 1. (4p.) a. !(x<3 && x<10) b. x>=3 && !(x>=10) c. !(x<3 || x<=10) d. !(x>3) || !(x<=10) 2. Algoritmul alăturat este reprezentat în pseudocod. citeşte n,a S-a notat cu a%b restul împărţirii numărului natural a la (numere naturale nenule) numărul natural nenul b şi cu [a] partea întreagă a nr 0 numărului real a. i 1 ┌cât timp i≤n execută a) Scrieţi valoarea afişată dacă se citesc, în această | citeşte b ordine, numerele 5, 3, 9, 206, 200, 80, 24. (6p.) | (număr natural nenul) b) Dacă pentru variabila n se citeşte numărul 4, iar | c 0 pentru variabila a se citeşte numărul 2, scrieţi un set │┌cât timp b%2=0 execută de numere distincte din intervalul [10,99] care pot ││ b [b/2] fi citite în continuare astfel încât, în urma executării || c c+1 algoritmului, să se afișeze valoarea 4. (4p.) │└■ │┌dacă c=a atunci c) Scrieţi în pseudocod un algoritm echivalent cu cel ││ nr nr+1 dat, înlocuind adecvat prima structură cât │└■ timp...execută cu o structură de tip │ i i+1 pentru...execută. (6p.) └■ d) Scrieţi programul C/C++ corespunzător algoritmului scrie nr dat. (10p.) Probă scrisă la informatică Varianta 9 Limbajul C/C++ Filiera teoretică, profilul real, specializările: matematică-informatică, matematică-informatică intensiv informatică Filiera vocaţională, profilul militar, specializarea matematică-informatică 1 din 3  Ministerul Educaţiei Naționale Centrul Naţional de Evaluare şi Examinare SUBIECTUL al II-lea (30 de puncte) Pentru fiecare dintre itemii 1 şi 2 scrieţi pe foaia de examen litera corespunzătoare răspunsului corect. 1. Un arbore cu 9 noduri, numerotate de la 1 la 9, este reprezentat prin vectorul de „taţi” (3, 3, 0, 5, 2, 5, 2, 5, 8). Descendenții direcți (“fii”) ai nodului cu eticheta 5 sunt: (4p.) a. 2 7 b. 2 8 c. 3 3 0 d. 4 6 8 2. Numărul de noduri ale unui graf neorientat fără cicluri, cu 26 de muchii și 12 componente conexe este: (4p.) a. 18 b. 28 c. 38 d. 48 Scrieţi pe foaia de examen răspunsul pentru fiecare dintre cerinţele următoare. 3. Variabila d, declarată alăturat, memorează în câmpul mic struct divizor cel mai mic divizor, strict mai mare decât 1, al numărului { int nr, mic; natural din intervalul [2,102], memorat în câmpul nr. } d; Scrieţi o secvență de instrucțiuni în urma executării căreia, pentru numărul memorat în câmpul nr al variabilei d, se afișează pe ecran mesajul prim, dacă numărul este prim, mesajul patrat dacă numărul este pătratul unui număr prim, sau două numere naturale, separate printr-un spațiu, reprezentând cel mai mic și cel mai mare dintre divizorii proprii pozitivi ai săi. Divizorii proprii pozitivi ai unui număr sunt divizori pozitivi diferiţi de 1 şi de el însuşi. Exemplu: dacă în câmpul nr se memorează numărul 12, iar în câmpul mic se memorează numărul 2, se afișează pe ecran 2 6 iar dacă în câmpul nr se memorează numărul 9, iar în câmpul mic se memorează numărul 3, se afișează pe ecran mesajul patrat (6p.) 4. Variabilele i şi j sunt de tip întreg, iar variabila a memorează 1 1 1 1 1 1 1 1 1 un tablou bidimensional cu 9 linii şi 9 coloane, numerotate de 1 2 2 2 2 2 2 2 2 la 1 la 9, având iniţial toate elementele nule. 1 2 3 3 3 3 3 3 3 Fără a utiliza alte variabile, scrieţi secvenţa de instrucţiuni de 1 2 3 4 4 4 4 4 4 mai jos, înlocuind punctele de suspensie astfel încât, în urma 1 2 3 4 5 5 5 5 5 executării secvenţei obţinute, variabila a să memoreze tabloul 1 2 3 4 5 6 6 6 6 1 2 3 4 5 6 7 7 7 alăturat. for(i=1;i<=9;i++) 1 2 3 4 5 6 7 8 8 for(j=1;j<=9;j++) 1 2 3 4 5 6 7 8 9 .................. (6p.) 5. Un text are cel mult 100 de caractere și este format din cuvinte, numere naturale şi spaţii. Cuvintele sunt formate numai din litere mici ale alfabetului englez. Cuvintele şi numerele sunt separate prin câte un spaţiu, ca în exemplu. Scrieţi un program C/C++ care citeşte de la tastatură un text de tipul menţionat mai sus şi afişează pe ecran numărul din text care începe cu cea mai mare cifră, ca în exemplu. Dacă există mai multe astfel de numere, se afișează doar unul dintre acestea, iar dacă textul nu conține niciun număr, se afișează pe ecran mesajul nu exista. Exemplu: pentru textul am 190 de nuci si 70 de castane se afişează 70 (10p.) Probă scrisă la informatică Varianta 9 Limbajul C/C++ Filiera teoretică, profilul real, specializările: matematică-informatică, matematică-informatică intensiv informatică Filiera vocaţională, profilul militar, specializarea matematică-informatică 2 din 3  Ministerul Educaţiei Naționale Centrul Naţional de Evaluare şi Examinare SUBIECTUL al III-lea (30 de puncte) Pentru itemul 1, scrieţi pe foaia de examen litera corespunzătoare răspunsului corect. 1. Subprogramele f1 şi f2 sunt definite mai jos. int f1 (int x, int y) int f2 (int x, int y) { if(x%2!=0 || y%2!=0)return 1; { if (x==y) return x; else return 2*f1(x/2,y/2); else } if(x>y) return f2(x-y,y); else return f2(x, y-x); } Cel mai mare divizor comun al lui 30 și 50 se obține în urma apelului: (4p.) a. f1(30,50) b. f2(30,50) c. f1(30/2,50) d. f2(30/2,50) Scrieţi pe foaia de examen răspunsul pentru fiecare dintre cerinţele următoare. 2. Utilizând metoda backtracking, se generează toate posibilitățile de a forma cutii cu bomboane de tipuri distincte din mulțimea {fondante, caramele, dropsuri, acadele}. Într-o cutie sunt cel puțin două tipuri de bomboane, dar nu pot fi și dropsuri și acadele simultan. Două cutii sunt distincte dacă ele conțin cel puțin un tip diferit de bomboane. Primele patru soluţii generate sunt, în această ordine, (fondante, caramele), (fondante, caramele, dropsuri), (fondante, caramele, acadele), (fondante, dropsuri). Scrieţi a cincea și a șasea soluție, în ordinea generării acestora. (6p.) 3. Un număr natural este numit echilibrat dacă suma cifrelor sale de pe poziții pare este un număr par, iar suma cifrelor sale de pe poziţii impare este un număr impar. Pozițiile cifrelor sunt numerotate de la dreapta la stânga, astfel: cifra unităților este pe poziția 0, cifra zecilor este pe poziția 1 ș.a.m.d. Subprogramul echilibrat are un singur parametru, n, prin care primeşte un număr natural (n∈∈[10,109]). Subprogramul returnează valoarea 1 dacă n este echilibrat sau valoarea 0 în caz contrar. Scrieţi definiţia completă a subprogramului. Exemplu: dacă n=25163912, subprogramul returnează valoarea 1, iar dacă n=11211, subprogramul returnează valoarea 0. (10p.) 4. Numim secvență încadrată a unui șir de numere naturale un subșir al acestuia, format din termeni aflați pe poziții consecutive în șirul dat, subșir care începe și se termină cu aceeași valoare. Lungimea secvenței este egală cu numărul de termeni ai acesteia. Fișierul bac.txt conține un șir de cel puțin două și cel mult 106 numere naturale din intervalul [0, 9]. Numerele sunt separate prin câte un spațiu. În șir există cel puțin doi termeni egali. Se cere să se determine secvențele încadrate din acest șir care au lungime maximă și să se afișeze pe prima linie a ecranului lungimea maximă determinată, iar pe următoarea linie, pentru fiecare astfel de secvenţă, valoarea primului său termen. Numerele de pe a doua linie sunt afişate în ordine strict crescătoare, separate prin câte un spaţiu. Proiectați un algoritm eficient din punctul de vedere al timpului de executare. Exemplu: dacă fişierul bac.txt conţine numerele 3 1 5 2 4 5 5 2 5 9 5 7 4 6 8 0 8 atunci pe ecran se afișează valorile: 9 4 5 a) Descrieţi în limbaj natural algoritmul proiectat, justificând eficienţa acestuia. (2p.) b) Scrieţi programul C/C++ corespunzător algoritmului descris. (8p.) Probă scrisă la informatică Varianta 9 Limbajul C/C++ Filiera teoretică, profilul real, specializările: matematică-informatică, matematică-informatică intensiv informatică Filiera vocaţională, profilul militar, specializarea matematică-informatică 3 din 3