際際滷

際際滷Share a Scribd company logo

E d informatica_2020_sp_mi_c_var_test_04

Ovidiu Dumitrescu
Ovidiu Dumitrescu

Pregtire bacalaureat informatic

1 of 2
Download to read offline
Ministerul Educa釘iei i Cercetrii Centrul Na釘ional de Evaluare i Examinare Prob scris la informatic Testul 4 Limbajul C/C++ Filier teoretic, profil real, specializare matematic-informatic / matematic-informatic intensiv informatic Filier voca釘ional, profil militar, specializare matematic-informatic Pagina 1 din 2 Examenul de bacalaureat na釘ional 2020 Proba E. d) Informatic Limbajul C/C++ Testul 4 Filier teoretic, profil real, specializare matematic-informatic / matematic-informatic intensiv informatic Filier voca釘ional, profil militar, specializare matematic-informatic Toate subiectele sunt obligatorii. Se acord 10 puncte din oficiu. Timpul de lucru efectiv este de 3 ore. Identificatorii utiliza釘i 樽n rezolvri trebuie s respecte precizrile din enun釘 (bold), iar 樽n lipsa unor precizri explicite, nota釘iile trebuie s corespund cu semnifica釘iile asociate acestora (eventual 樽n form prescurtat). Datele de intrare se consider corecte, validarea lor nefiind necesar. n grafurile din cerine oricare arc/muchie are extremiti distincte i oricare dou arce/muchii difer prin cel puin una dintre extremiti. SUBIECTUL I (20 de puncte) Pentru fiecare dintre itemii de la 1 la 5, scrie釘i pe foaia de examen litera corespunztoare rspunsului corect. Fiecare rspuns corect se noteaz cu 4 puncte. 1. Variabile x, y i z sunt de tip 樽ntreg. Indicai o expresie C/C++ care are valoarea 1 dac i numai dac x, y i z au valori identice. a. x==y && x==z b. x==y==z c. !( x!=y && x!=z) d. !(x!=y!=z) 2. Subprogramul f este definit alturat. Pentru apelul f(20,2020), funcia se execut de: int f(int x, int y) { if(x<=1 || y<=1) return 0; if(x>y) return 1+f(f(x/y,y),y); return 1+f(x,f(x,y/x)); } a. 5 ori b. 9 ori c. 11 ori d. 20 de ori 3. Utiliz但nd metoda backtracking, se genereaz toate modalitile de a pregti cltite, folosind, 樽ntr-o anumit ordine, toate ingredientele din mulimea {fin, lapte, ou} pentru aluat, apoi unul dintre ingredientele din mulimea {ciocolat, dulcea, urd} pentru umplutur, i, la final, unul dintre ingredientele din mulimea {cacaval, mrar, fric} pentru ornare, av但nd 樽n vedere urmtoarele restricii: frica se poate folosi numai 樽mpreun cu ciocolata i dulceaa, iar mrarul i cacavalul numai 樽mpreun cu urda. Primele cinci soluii generate sunt, 樽n aceast ordine: (fin, lapte, ou, ciocolat, fric), (fin, lapte, ou, dulcea, fric), (fin, lapte, ou, urd, cacaval), (fin, lapte, ou, urd, mrar), (fin, ou, lapte, ciocolat, fric). Indicai a aptea soluie generat. a. (ou, lapte, fin, urd, mrar) b. (lapte, fin, ou, ciocolat, fric) c. (fin, ou, lapte, dulcea, fric) d. (fin, ou, lapte, urd, cacaval) 4. Numim 樽nl釘ime a unui arbore cu rdcin numrul de muchii traversate de cel mai lung lan釘 elementar cu una dintre extremit釘i 樽n rdcina arborelui. Un arbore cu rdcin, cu 8 noduri, numerotate de la 1 la 8, este reprezentat prin vectorul de ta釘i (6,6,5,3,0,5,8,4). Indicai 樽nlimea arborelui: a. 2 b. 3 c. 4 d. 5 5. Un graf neorientat are 10 noduri, numerotate de la 1 la 10, i muchiile [1,2], [1,3], [1,10], [3,10], [4,5], [4,6], [4,8], [5,7], [5,9], [6,8], [6,9], [7,9], [8,9]. Indicai numrul minim de muchii care trebuie adugate pentru ca graful obinut s aib cel puin un lan eulerian (lan care traverseaz toate muchiile grafului). a. 1 b. 2 c. 3 d. 4
Ministerul Educa釘iei i Cercetrii Centrul Na釘ional de Evaluare i Examinare Prob scris la informatic Testul 4 Limbajul C/C++ Filier teoretic, profil real, specializare matematic-informatic / matematic-informatic intensiv informatic Filier voca釘ional, profil militar, specializare matematic-informatic Pagina 2 din 2 SUBIECTUL al II-lea (40 de puncte) 1. Algoritmul alturat este reprezentat 樽n pseudocod. S-a notat cu a%b restul 樽mpr釘irii numrului natural a la numrul natural nenul b i cu [c] partea 樽ntreag a numrului real c. citete n (numr natural) repet c1n%10; n[n/10]; c2n%10 dac c1>c2 atunci c2c1; c1n%10 c但t timp c1<c2 execut scrie c1 c2[c2/2] p但n c但nd n9 a. Scrie釘i ce se afieaz 樽n urma executrii algoritmului dac se citete numrul 49335. (6p.) b. Scrie釘i trei numere de patru cifre care pot fi citite astfel 樽nc但t, pentru fiecare dintre acestea, 樽n urma executrii algoritmului, valoarea afiat s fie 1100. (6p.) c. Scrie釘i programul C/C++ corespunztor algoritmului dat. (10p.) d. Scrie釘i 樽n pseudocod un algoritm, echivalent cu cel dat, 樽nlocuind adecvat structura c但t timp...execut cu o structur repetitiv de alt tip. (6p.) 2. Variabila p memoreaz date despre un poliedru regulat: numrul de v但rfuri, lungimea muchiei i dou unghiuri specifice (dintre o fa i o muchie, respectiv dintre dou fee). tiind c expresiile C/C++ de mai jos au ca valori un numr natural reprezent但nd numrul de v但rfuri ale poliedrului, i numerele reale reprezent但nd lungimea muchiei, respectiv cele dou unghiuri specifice, scriei definiia unei structuri cu eticheta poliedru, care permite memorarea datelor precizate, i declarai corespunztor variabila p. p.NrVarfuri p.Muchie p.Unghi.FataMuchie p.Unghi.FataFata (6p.) 3. Variabilele i i j sunt de tip 樽ntreg, iar variabila s poate memora un ir de cel mult 20 de caractere. Scriei irul memorat de variabila s 樽n urma executrii secvenei de mai jos. strcpy(s,"optsprezece"); i=0; j=strlen(s)-1; while(i<j) { if(strchr("aeiou",s[i])==NULL && strchr("aeiou",s[j])!=NULL) { s[i]=s[i]+1; s[j]=s[j]-1;} i=i+1;j=j-1; } (6p.) SUBIECTUL al III-lea (30 de puncte) 1. Dou numere a i b sunt numite generatoare ale unui numr natural n dac ab+[a/b]=n, unde s-a notat cu [c] partea 樽ntreag a numrului real c. Subprogramul generatoare are un singur parametru, n, prin care primete un numr natural (n[2,109]). Subprogramul afieaz pe ecran toate perechile distincte de numere naturale cu proprietatea c sunt generatoare ale lui n i c primul numr din pereche este par. Numerele din fiecare pereche sunt separate prin simbolul minus (-), iar perechile sunt separate prin c但te un spaiu. Dac nu exist astfel de perechi, se afieaz pe ecran mesajul nu exista. Scriei definiia complet a subprogramului. Exemplu: dac n=2020 se afieaz pe ecran 2-1010 4-505 10-202 20-101 96-21 200-10 606-3 808-2 1010-1 (10p.) 2. ntr-un tablou bidimensional, cu elemente av但nd valori numai 樽n mul釘imea {0,1}, numim coloane complementare dou coloane cu proprietatea c oricare dou elemente ale acestora, aflate pe aceeai linie, sunt diferite. Scrie釘i un program C/C++ care citete de la tastatur dou numere naturale din intervalul [2,20], m i n, i elementele unui tablou bidimensional cu m linii i n coloane, numere naturale din mul釘imea {0,1}. Programul afieaz pe ecran numrul de coloane ale tabloului care sunt complementare" cu prima coloan a acestuia. Exemplu: dac m=3, n=6, pentru tabloul alturat se afieaz pe ecran 3. (10p.) 1 1 0 0 1 0 0 1 1 1 1 1 1 0 0 0 1 0 3. Fiierul bac.txt con釘ine, 樽n ordine descresctoare, cel pu釘in dou i cel mult 106 numere naturale din intervalul [0,109], separate prin c但te un spa釘iu. Se cere s se afieze pe ecran, 樽n ordine strict descresctoare, separate prin c但te un spa釘iu, numai numerele care apar 樽n fiier de exact dou ori. Dac nu exist niciun astfel de numr, se afieaz pe ecran mesajul nu exista. Proiectai un algoritm eficient din punctul de vedere al memoriei utilizate i al timpului de executare. Exemplu: dac fiierul con釘ine numerele 100 50 50 50 49 49 36 16 16 12 10 10 9 7 7 pe ecran se afieaz, 樽n aceast ordine, numerele 49 16 10 7 a. Scriei programul C/C++ corespunztor algoritmului proiectat. (8p.) b. Descriei 樽n limbaj natural algoritmul proiectat, justific但nd eficiena acestuia. (2p.)

More Related Content

E d informatica_2020_sp_mi_c_var_test_04

  • 1. Ministerul Educa釘iei i Cercetrii Centrul Na釘ional de Evaluare i Examinare Prob scris la informatic Testul 4 Limbajul C/C++ Filier teoretic, profil real, specializare matematic-informatic / matematic-informatic intensiv informatic Filier voca釘ional, profil militar, specializare matematic-informatic Pagina 1 din 2 Examenul de bacalaureat na釘ional 2020 Proba E. d) Informatic Limbajul C/C++ Testul 4 Filier teoretic, profil real, specializare matematic-informatic / matematic-informatic intensiv informatic Filier voca釘ional, profil militar, specializare matematic-informatic Toate subiectele sunt obligatorii. Se acord 10 puncte din oficiu. Timpul de lucru efectiv este de 3 ore. Identificatorii utiliza釘i 樽n rezolvri trebuie s respecte precizrile din enun釘 (bold), iar 樽n lipsa unor precizri explicite, nota釘iile trebuie s corespund cu semnifica釘iile asociate acestora (eventual 樽n form prescurtat). Datele de intrare se consider corecte, validarea lor nefiind necesar. n grafurile din cerine oricare arc/muchie are extremiti distincte i oricare dou arce/muchii difer prin cel puin una dintre extremiti. SUBIECTUL I (20 de puncte) Pentru fiecare dintre itemii de la 1 la 5, scrie釘i pe foaia de examen litera corespunztoare rspunsului corect. Fiecare rspuns corect se noteaz cu 4 puncte. 1. Variabile x, y i z sunt de tip 樽ntreg. Indicai o expresie C/C++ care are valoarea 1 dac i numai dac x, y i z au valori identice. a. x==y && x==z b. x==y==z c. !( x!=y && x!=z) d. !(x!=y!=z) 2. Subprogramul f este definit alturat. Pentru apelul f(20,2020), funcia se execut de: int f(int x, int y) { if(x<=1 || y<=1) return 0; if(x>y) return 1+f(f(x/y,y),y); return 1+f(x,f(x,y/x)); } a. 5 ori b. 9 ori c. 11 ori d. 20 de ori 3. Utiliz但nd metoda backtracking, se genereaz toate modalitile de a pregti cltite, folosind, 樽ntr-o anumit ordine, toate ingredientele din mulimea {fin, lapte, ou} pentru aluat, apoi unul dintre ingredientele din mulimea {ciocolat, dulcea, urd} pentru umplutur, i, la final, unul dintre ingredientele din mulimea {cacaval, mrar, fric} pentru ornare, av但nd 樽n vedere urmtoarele restricii: frica se poate folosi numai 樽mpreun cu ciocolata i dulceaa, iar mrarul i cacavalul numai 樽mpreun cu urda. Primele cinci soluii generate sunt, 樽n aceast ordine: (fin, lapte, ou, ciocolat, fric), (fin, lapte, ou, dulcea, fric), (fin, lapte, ou, urd, cacaval), (fin, lapte, ou, urd, mrar), (fin, ou, lapte, ciocolat, fric). Indicai a aptea soluie generat. a. (ou, lapte, fin, urd, mrar) b. (lapte, fin, ou, ciocolat, fric) c. (fin, ou, lapte, dulcea, fric) d. (fin, ou, lapte, urd, cacaval) 4. Numim 樽nl釘ime a unui arbore cu rdcin numrul de muchii traversate de cel mai lung lan釘 elementar cu una dintre extremit釘i 樽n rdcina arborelui. Un arbore cu rdcin, cu 8 noduri, numerotate de la 1 la 8, este reprezentat prin vectorul de ta釘i (6,6,5,3,0,5,8,4). Indicai 樽nlimea arborelui: a. 2 b. 3 c. 4 d. 5 5. Un graf neorientat are 10 noduri, numerotate de la 1 la 10, i muchiile [1,2], [1,3], [1,10], [3,10], [4,5], [4,6], [4,8], [5,7], [5,9], [6,8], [6,9], [7,9], [8,9]. Indicai numrul minim de muchii care trebuie adugate pentru ca graful obinut s aib cel puin un lan eulerian (lan care traverseaz toate muchiile grafului). a. 1 b. 2 c. 3 d. 4
  • 2. Ministerul Educa釘iei i Cercetrii Centrul Na釘ional de Evaluare i Examinare Prob scris la informatic Testul 4 Limbajul C/C++ Filier teoretic, profil real, specializare matematic-informatic / matematic-informatic intensiv informatic Filier voca釘ional, profil militar, specializare matematic-informatic Pagina 2 din 2 SUBIECTUL al II-lea (40 de puncte) 1. Algoritmul alturat este reprezentat 樽n pseudocod. S-a notat cu a%b restul 樽mpr釘irii numrului natural a la numrul natural nenul b i cu [c] partea 樽ntreag a numrului real c. citete n (numr natural) repet c1n%10; n[n/10]; c2n%10 dac c1>c2 atunci c2c1; c1n%10 c但t timp c1<c2 execut scrie c1 c2[c2/2] p但n c但nd n9 a. Scrie釘i ce se afieaz 樽n urma executrii algoritmului dac se citete numrul 49335. (6p.) b. Scrie釘i trei numere de patru cifre care pot fi citite astfel 樽nc但t, pentru fiecare dintre acestea, 樽n urma executrii algoritmului, valoarea afiat s fie 1100. (6p.) c. Scrie釘i programul C/C++ corespunztor algoritmului dat. (10p.) d. Scrie釘i 樽n pseudocod un algoritm, echivalent cu cel dat, 樽nlocuind adecvat structura c但t timp...execut cu o structur repetitiv de alt tip. (6p.) 2. Variabila p memoreaz date despre un poliedru regulat: numrul de v但rfuri, lungimea muchiei i dou unghiuri specifice (dintre o fa i o muchie, respectiv dintre dou fee). tiind c expresiile C/C++ de mai jos au ca valori un numr natural reprezent但nd numrul de v但rfuri ale poliedrului, i numerele reale reprezent但nd lungimea muchiei, respectiv cele dou unghiuri specifice, scriei definiia unei structuri cu eticheta poliedru, care permite memorarea datelor precizate, i declarai corespunztor variabila p. p.NrVarfuri p.Muchie p.Unghi.FataMuchie p.Unghi.FataFata (6p.) 3. Variabilele i i j sunt de tip 樽ntreg, iar variabila s poate memora un ir de cel mult 20 de caractere. Scriei irul memorat de variabila s 樽n urma executrii secvenei de mai jos. strcpy(s,"optsprezece"); i=0; j=strlen(s)-1; while(i<j) { if(strchr("aeiou",s[i])==NULL && strchr("aeiou",s[j])!=NULL) { s[i]=s[i]+1; s[j]=s[j]-1;} i=i+1;j=j-1; } (6p.) SUBIECTUL al III-lea (30 de puncte) 1. Dou numere a i b sunt numite generatoare ale unui numr natural n dac ab+[a/b]=n, unde s-a notat cu [c] partea 樽ntreag a numrului real c. Subprogramul generatoare are un singur parametru, n, prin care primete un numr natural (n[2,109]). Subprogramul afieaz pe ecran toate perechile distincte de numere naturale cu proprietatea c sunt generatoare ale lui n i c primul numr din pereche este par. Numerele din fiecare pereche sunt separate prin simbolul minus (-), iar perechile sunt separate prin c但te un spaiu. Dac nu exist astfel de perechi, se afieaz pe ecran mesajul nu exista. Scriei definiia complet a subprogramului. Exemplu: dac n=2020 se afieaz pe ecran 2-1010 4-505 10-202 20-101 96-21 200-10 606-3 808-2 1010-1 (10p.) 2. ntr-un tablou bidimensional, cu elemente av但nd valori numai 樽n mul釘imea {0,1}, numim coloane complementare dou coloane cu proprietatea c oricare dou elemente ale acestora, aflate pe aceeai linie, sunt diferite. Scrie釘i un program C/C++ care citete de la tastatur dou numere naturale din intervalul [2,20], m i n, i elementele unui tablou bidimensional cu m linii i n coloane, numere naturale din mul釘imea {0,1}. Programul afieaz pe ecran numrul de coloane ale tabloului care sunt complementare" cu prima coloan a acestuia. Exemplu: dac m=3, n=6, pentru tabloul alturat se afieaz pe ecran 3. (10p.) 1 1 0 0 1 0 0 1 1 1 1 1 1 0 0 0 1 0 3. Fiierul bac.txt con釘ine, 樽n ordine descresctoare, cel pu釘in dou i cel mult 106 numere naturale din intervalul [0,109], separate prin c但te un spa釘iu. Se cere s se afieze pe ecran, 樽n ordine strict descresctoare, separate prin c但te un spa釘iu, numai numerele care apar 樽n fiier de exact dou ori. Dac nu exist niciun astfel de numr, se afieaz pe ecran mesajul nu exista. Proiectai un algoritm eficient din punctul de vedere al memoriei utilizate i al timpului de executare. Exemplu: dac fiierul con釘ine numerele 100 50 50 50 49 49 36 16 16 12 10 10 9 7 7 pe ecran se afieaz, 樽n aceast ordine, numerele 49 16 10 7 a. Scriei programul C/C++ corespunztor algoritmului proiectat. (8p.) b. Descriei 樽n limbaj natural algoritmul proiectat, justific但nd eficiena acestuia. (2p.)