Despre acest subiect
iulie · Sesiunea iulie
Sursa documentelor: Facultatea de Informatică UAIC – subiecte anterioare. Verifică răspunsurile cu baremul după ce rezolvi subiectul.
Se încarcă profesorii disponibili…
Subiect și barem
Se deschide documentul PDF… Deschide PDF
Subiectul și baremul în format text
Text extras automat din documentul original. Pentru formule, tabele, imagini și așezarea răspunsurilor, verifică întotdeauna PDF-ul.
Subiect · 3 pagini
Subiect · pagina 1
Universitatea “Alexandru Ioan Cuza” din Ia¸si Admitere - studii de licent¸˘a Facultatea de Informatic˘a Sesiunea iulie 2016 Test la INFORMATIC ˘A Limbajul C/C++ Se acord˘a 10 puncte din oficiu. Timpul efectiv de lucru este de 3 ore. SUBIECTUL I (30 de puncte) Pentru itemul 1, scriet¸i pe foaia de examen litera corespunz˘atoare r˘aspunsului corect. 1. Un num˘ar natural n desemneaz˘a un an bisect dac˘a n este multiplu de 4, dar nu este multiplu de 100, cu except, ia numerelor multiplu de 400. De exemplu, 1600, 2000, 2004, 2016, 2400 sunt ani bisect, i, dar 2007, 1700, 1800, 2200 nu sunt ani bisect, i. Care dintre expresiile C/C++ de mai jos testeaz˘a dac˘a valoarea variabilei n desemneaz˘a un an bisect? (4p.) a. (n%100 != 0) && (n%4 == 0) c. (n%100 != 0) || (n%4 == 0) b. (n%4 == 0) && ((n%100 != 0) || (n%400 == 0)) d. (n%4 == 0) && ((n%100 != 0) && (n%400 == 0)) Scriet¸i pe foaia de examen r˘aspunsul pentru fiecare dintre cerint¸ele urm˘atoare. 2. Se consider˘a subprogramul recursiv F de mai jos, descris ˆın pseudocod. Subprogramul primes, te ca parametri dou˘a numere naturale u s, i v s, i ˆıntoarce un num˘ar natural. Operat, ia % reprezint˘a restul ˆımp˘art, irii, iar max(a,b) reprezint˘a maximul dintre a s, i b. a. Care este valoarea returnat˘a de sub- program pentru parametrii u = 42 s, i v = 35? (6p.) b. Dat, i exemplu de dou˘a numere na- turale u, v distincte s, i nenule astfel ˆıncˆat F(u, v) s˘a returneze 5. (4p.) c. Dac˘a u = 14, care este cea mai mare valoare strict mai mic˘a decˆat 100 pentru v, astfel ˆıncˆat F(u, v) s˘a returneze 7? (6p.) d. Scriet, i funct, ia C/C++ cores- punz˘atoare subprogramului al˘aturat. (10p.) subprogram F(u,v) (u, v - numere naturale) dac˘a u=v sau u=0 sau v=0 atunci returneaz˘a max(u,v) altfel dac˘a u%2=0 atunci dac˘a v%2=0 atunci returneaz˘a 2*F(u/2, v/2) altfel returneaz˘a F(u/2, v) altfel dac˘a v%2=0 atunci returneaz˘a F(u, v/2) altfel dac˘a u<v atunci returneaz˘a F(u, (v-u)/2) altfel returneaz˘a F((u-v)/2, v) SUBIECTUL al II-lea (30 de puncte) Pentru fiecare dintre itemii 1 ¸si 2, scriet¸i pe foaia de examen litera corespunz˘atoare r˘aspunsului corect. 1. Care este ˆın˘alt¸imea maxim˘a a unui arbore cu r˘ad˘acin˘a, avˆand 11 noduri, ¸stiind c˘a fiecare nod intern (care nu este r˘ad˘acin˘a sau frunz˘a) are mai multe noduri fiu decˆat p˘arintele s˘au? (In˘alt¸imea arborelui este num˘arul de muchii ale celui mai lung drum de la r˘ad˘acin˘a la o frunz˘a.) (4p.) a. 2 b. 4 c. 10 d. nu exist˘a un astfel de arbore
Subiect · pagina 2
2. Fie un graf neorientat ˆın care fiecare nod are un num˘ar par s, i nenul de vecini, astfel ˆıncˆat nu exist˘a
dou˘a noduri avˆand acela¸si num˘ar de vecini. Care dintre urm˘atoarele variante ar putea reprezenta
num˘arul de muchii ale unui astfel de graf? (6p.)
a. 10 b. 15 c. 16 d. nu exist˘a un astfel de graf
Scriet¸i pe foaia de examen r˘aspunsul pentru fiecare dintre cerint¸ele urm˘atoare.
3. Consider˘am un ¸sir oarecare format doar din caractere din mult¸imea { a, b }. Mult¸imea R = { r1:
aab → aaa, r2: aba → aab, r3: abb → aba, r4: baa → abb, r5: bab → aba, r6: bba → baa, r7:
bbb → bab} define¸ste regulile de transformare care pot fi aplicate unui astfel de ¸sir. Fiecare dintre
aceste transform˘ari, aplicat˘a unui ¸sir de caractere oarecare, va ˆınlocui prima aparit¸ie a sub¸sirului de
trei caractere din partea stˆang˘a a regulii, cu sub¸sirul din partea dreapt˘a. Pornind de la s, irul init¸ial,
vom aplica ˆın mod repetat oricare dintre transform˘arile din mult¸imea R, atˆat timp cˆat acest lucru
este posibil.
Exemplu: Pentru ¸sirul de caractere "abba", o secvent¸˘a posibil˘a de aplicare a regulilor este:
abba r3
Ð→ abaa r4
Ð→ aabb r1
Ð→ aaab r1
Ð→ aaaa.
a) Demonstrat¸i c˘a, indiferent de ¸sirul considerat init¸ial ¸si indiferent de ordinea de aplicare a regulilor
de transformare, dup˘a un num˘ar finit de pa¸si se va obt, ine un ¸sir ce cont¸ine pe fiecare pozit¸ie
doar caracterul a. (3p.)
b) Scriet¸i un program C/C++ care:
i) Cite¸ste de la tastatur˘a un ¸sir s format doar din caracterele a ¸si b. ˆIn cazul ˆın care ¸sirul
cont¸ine ¸si alte caractere, va fi afi¸sat mesajul "Date invalide". (1p.)
ii) Pornind de la s, irul s, aplic˘a regulile de transformare din mult¸imea R atˆat timp cˆat este
posibil ¸si afi¸seaz˘a num˘arul de aplic˘ari ale acestor reguli. (5p.)
iii) Verific˘a faptul c˘a ¸sirul rezultat ˆın final este format doar din caractere egale cu a. (1p.)
4. Fie S ¸si T dou˘a mult¸imi de simboluri, ambele avˆand acela¸si num˘ar de elemente n, unde n este un
num˘ar natural impar. Un (S,T)-p˘atrat este o matrice p˘atratic˘a de dimensiune n × n ce ˆındepline¸ste
urm˘atoarele condit¸ii:
(C1) fiecare element al matricii este o pereche (s,t) unde s∈S ¸si t∈T;
(C2) pentru orice dou˘a elemente (s,t) s, i (s’,t’) aflate pe pozit, ii diferite ˆın matrice dar pe aceea¸si
linie sau pe aceea¸si coloan˘a, avem s ~= s’ ¸si t ~= t’;
(C3) pentru orice dou˘a elemente (s,t) s, i (s’,t’) aflate pe pozit¸ii diferite ˆın matrice, avem s ~= s’
sau t ~= t’.
Exemplu: Pentru n=3, S={a,b,c} ¸si T={0,1,2}, un (S,T)-p˘atrat posibil este:
⎛
⎜
⎝
(a, 0) (b, 1) (c, 2)
(c, 1) (a, 2) (b, 0)
(b, 2) (c, 0) (a, 1)
⎞
⎟
⎠
a) Dat¸i un exemplu de (S,T)-p˘atrat pentru n=5, S={a,b,c,d,e} ¸si T={0,1,2,3,4}. (2p.)
b) Scriet¸i o funct¸ie C/C++ care prime¸ste ca argumente num˘arul natural impar n ¸si dou˘a tablouri de
caractere, reprezentˆand mult¸imile S ¸si T, ¸si construieste un (S,T)-p˘atrat. (6p.)
c) Argumentat¸i faptul c˘a p˘atratul construit de funct¸ia de la punctul b) ˆındepline¸ste condit¸iile (C1),
(C2) ¸si (C3). (2p.)Subiect · pagina 3
SUBIECTUL al III-lea (30 de puncte)
Pentru itemul 1, scriet¸i pe foaia de examen litera corespunz˘atoare r˘aspunsului corect.
1. Se consider˘a toate s, irurile de lungime 10 formate din 0 s, i 1. Cˆate dintre acestea au proprietatea
c˘a suma oric˘aror 5 elemente de pe pozit¸ii consecutive este 3? (4p.)
a. 10 b. 100 c. 120 d. 1024
Scriet¸i pe foaia de examen r˘aspunsul pentru fiecare dintre cerint¸ele urm˘atoare.
2. John McCarthy, unul dintre fondatorii domeniului inteligent, ˘a artificial˘a, a propus funct, ia F91,
definit˘a mai jos s, i numit˘a “funct, ia 91 a lui McCarthy”. Ce valoare va returna apelul F91(91)?(6p.)
int F91(int x) {
if (x > 100) { return x - 10; }
else { return F91(F91(x + 11)); }
}
3. Fie A o matrice de numere naturale cu N≥2 linii ¸si M≥2 coloane. O secvent, ˘a (i1,j1), (i2,j2),
..., (ik,jk) de pozit¸ii din A se nume¸ste progresiv˘a dac˘a s, irurile
– i1, i2, ..., ik
– j1, j2, ..., jk
– A[i1][j1], A[i2][j2], ..., A[ik][jk]
sunt progresii aritmetice cu rat¸ii nenule. De exemplu, ˆın matricea
⎛
⎜
⎜
⎜
⎜
⎝
22 35 30 37 25 34
26 8 44 23 41 10
38 23 14 20 49 11
35 20 3 2 24 13
⎞
⎟
⎟
⎟
⎟
⎠
este evident¸iat˘a secvent¸a progresiv˘a (1,2), (2,4), (3,6): indicii liniilor (1, 2, 3) sunt ˆın progresie
aritmetic˘a de rat, ie nenul˘a, indicii coloanelor (2, 4, 6) sunt ˆın progresie aritmetic˘a de rat, ie nenul˘a,
iar valorile (35, 23, 11) sunt ¸si ele ˆın progresie aritmetic˘a de rat, ie nenul˘a.
a) Pentru matricea de mai jos, scriet, i care este cea mai lung˘a secvent¸˘a progresiv˘a. Dac˘a sunt mai
multe astfel de secvent, e, aleget, i oricare dintre ele. (4p.)
⎛
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎝
1 1 1 9 1
1 1 6 1 1
1 3 7 1 1
1 1 2 1 1
1 5 1 1 9
1 1 1 1 1
3 1 1 3 1
⎞
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎠
b) Scriet¸i o funct¸ie C/C++ care prime¸ste ca parametri dimensiunile N s, i M ale matricii, matricea A
¸si primele dou˘a pozit, ii (i1,j1), (i2,j2) dintr-o secvent¸˘a progresiv˘a din A. Funct¸ia va returna
lungimea secvent¸ei progresive din A ce ˆıncepe cu (i1,j1), (i2,j2) s, i care are un num˘ar maxim
de elemente. (8p.)
c) Scriet¸i o funct¸ie C/C++ care prime¸ste ca parametri dimensiunile N s, i M ale matricii s, i matricea A.
Funct, ia va returna lungimea secvent¸ei progresive din A, care are un num˘ar maxim de elemente.
ˆIn rezolvare, putet, i apela funct, ia de la punctul b). (8p.)Barem · 3 pagini
Barem · pagina 1
Universitatea “Alexandru Ioan Cuza” din Ias, i Admitere – studii de licent, ˘a Facultatea de Informatic˘a Sesiunea iulie 2016 Proba scris˘a la INFORMATIC ˘A BAREM DE EVALUARE S¸I NOTARE comun pentru limbajele C/C++ ¸si Pascal ● Se puncteaz˘a oricare alte modalit˘at¸i de rezolvare corect˘a a cerint¸elor. ● Nu se acord˘a punctaje intermediare, altele decˆat cele precizate explicit prin barem. Nu se acord˘a fract¸iuni de punct. ● Se acord˘a 10 puncte din oficiu. Nota final˘a se calculeaz˘a prin ˆımp˘art¸irea punctajului total acordat pentru lucrare la 10. ☀ ˆIn cazul ˆın care r˘aspunsul final la o ˆıntrebare care nu necesit˘a justificare nu este corect dar exist˘a justific˘ari part¸ial corecte, punctajul se calculeaz˘a conform baremului afi¸sat. SUBIECTUL I (30 de puncte) 1. b 4p. 2. a. Valoarea returnat˘a este 7. 6p. ☀ 1. descrierea calculului 4p. 2. obt¸inerea rezultatului corect 2p. b. Orice dou˘a numere naturale u s, i v, nenule s, i diferite ˆıntre ele, al c˘aror cmmdc este 5 (exemplu: u = 10, v = 5). 4p. ☀ 1. identificarea propriet˘at¸ii de cmmdc 3p. 2. obt¸inerea unui exemplu corect 1p. c. Valoarea v = 91. 6p. ☀ 1. utilizarea propriet˘at, ilor de divizor/multiplu 3p. 2. obt¸inerea rezultatului corect 3p. d. Pentru funct, ia C/C++ corect˘a 10p. 1. structura corect˘a a funct, iei 3p. 2. folosirea corect˘a a instruct, iunilor de decizie 4p. 3. sintaxa corect˘a 3p.
Barem · pagina 2
SUBIECTUL al II-lea (30 de puncte) 1. R˘aspuns corect b 4p. ☀ 1. arbore care respect˘a condit, iile 2p. 2. identificarea r˘aspunsului corect 2p. 2. R˘aspuns corect d 6p. ☀ 1. folosirea propriet˘at, ii: suma gradelor = 2 × num˘ar muchii 2p. 2. calculul num˘arului maxim de muchii ˆıntr-un graf cu n noduri 2p. 3. identificarea r˘aspunsului corect 2p. 3. Pentru solut, ie corect˘a 10p. a. 1. Identificarea faptului c˘a s, irul descres, te lexicografic s, i ˆıs, i p˘astreaz˘a lungimea. 2p. 2. Identificarea faptului c˘a pentru orice s, ir care cont, ine cel put, in un b poate fi aplicat˘a o regul˘a. 1p. b.i citirea s, i validarea datelor de intrare 1p. b.ii 1. identificarea unei reguli care poate fi aplicat˘a s, irului curent 2p. 2. transformarea s, irului conform regulii 2p. 3. num˘ararea transform˘arilor 1p. b.iii verificarea faptului c˘a s, irul cont, ine doar caractere a 1p. 4. Pentru solut, ie corect˘a 10p. a construirea unui exemplu corect 2p. b 1. structura funct, iei 1p. 2. folosirea unei structuri de date adecvate pentru repre- zentarea p˘atratului 2p. 3. algoritm corect pentru construirea p˘atratului 3p. c argumentare corect˘a 2p.
Barem · pagina 3
SUBIECTUL al III-lea (30 de puncte) 1. R˘aspuns corect a 4p. ☀ 1. observarea faptului c˘a s, irul este determinat ˆın mod unic de oricare 5 elemente situate pe pozit, ii consecutive 3p. 2. calculul corect al num˘arului de combin˘ari 1p. 2. R˘aspuns corect 91 6p. ☀ 1. observarea faptului c˘a funct, ia este recursiv˘a 1p. 2. calculul recursiv (lista tuturor apelurilor recursive) 3p. 3. obt¸inerea rezultatului corect 2p. 3. a. R˘aspuns corect (7,1), (5,2), (3,3), (1,4) sau (1,4), (3,3), (5,2), (7,1) 4p. ☀ 1. identificarea unei secvent, e progresive de lungime i ip. b. Pentru solut, ie corect˘a 8p. 1. structura corect˘a a funct, iei 2p. 2. folosirea unei instruct, iuni repetitive pentru parcugerea secvent, ei progresive 3p. 3. verificarea corect˘a a condit, iilor 3p. c. Pentru solut, ie corect˘a 8p. 1. structura corect˘a a funct, iei 2p. 2. folosirea unor instruct, iuni repetitive pentru parcugerea tutoror perechilor de pozit, ii care pot reprezenta ˆınceputul unei secvent, e progresive 3p. 3. apelul corect al funct, iei de la punctul b. 2p. 4. tratarea cazului cˆand r˘aspunsul este 1 1p.
Continuă pregătirea
Vezi arhiva completăAlte subiecte de la aceeași facultate
Examen de admitere · 2017Informatică · Sesiunea iulieDeschide fișa Examen de admitere · 2017Matematică · Sesiunea iulieDeschide fișa Examen de admitere · 2015Informatică · Sesiunea iulieDeschide fișa Examen de admitere · 2018Informatică · Sesiunea iulieDeschide fișa Examen de admitere · 2018Matematică · Sesiunea iulieDeschide fișa Examen de admitere · 2014Informatică · Sesiunea iulieDeschide fișa
Răspunsuri directe
Ce trebuie să știi despre acest subiect?
Ce document de admitere este acesta?
Pagina prezintă examen de admitere din 2016 pentru Informatică, la Facultatea de Informatică. Documentul este etichetat după instituție, facultate, program și tipul probei folosind inventarul public verificat. Consultă metodologia actuală a instituției pentru condițiile examenului viitor.
Există și barem sau răspunsuri pentru acest subiect?
Da. Pagina include baremul sau răspunsurile publice asociate acestui subiect, afișate separat ori în același document atunci când sursa le publică împreună. Verifică fiecare rezolvare după ce ai terminat varianta și urmărește exact criteriile de punctare indicate de instituție.
Cum folosesc acest subiect în pregătirea pentru admitere?
Rezolvă documentul fără ajutor și respectă timpul prevăzut de metodologia examenului. Corectează cu baremul disponibil, marchează capitolele unde ai pierdut puncte și repetă exerciții similare. Compară apoi cu alte probe din aceeași facultate și confirmă programa curentă pe site-ul oficial al instituției.
