Pregătire cu un profesor

Universitatea “Alexandru Ioan Cuza”, Ia¸si Admitere - studii de licent¸˘a
Facultatea de Informatic˘a Sesiunea iulie 2013
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. Fie a cel mai mare num˘ar natural de patru cifre distincte ¸si b cel mai mic num˘ar
natural de patru cifre distincte. Precizat¸i care dintre expresiile C/C++ de mai jos este
adev˘arat˘a. (4p.)
a. (a / b == 8) || (a % b == 0)
b. (a / b == 9) && (a % b > 0)
c. (a % b == 8) || (a / b == 0)
d. (a % b == 9) && (a / b > 0)
2. Se consider˘a algoritmul al˘aturat, des-
cris ˆın pseudocod.
S-a notat cu |n| valoarea absolut˘a a num˘arului
ˆıntreg n.
a. Scriet¸i valoarea returnat˘a de algoritm dac˘a
num˘arul a citit este 1. (6p.)
b. Care este cea mai mic˘a valoare min pe care
o poate returna algoritmul ¸si pentru ce
valoare a parametrului de intrare a este
aceasta obt¸inut˘a? (6p.)
c. Scriet¸i ˆın pseudocod un algoritm care s˘a
nu foloseasc˘a structuri repetitive de tipul
pentru ¸si care s˘a fie echivalent cu cel dat
(pentru orice num˘ar natural nenul a citit
returneaz˘a aceea¸si valoare min ca ¸si algo-
ritmul dat). (4p.)
d. Scriet¸i programul C/C++ corespunz˘ator al-
goritmului al˘aturat. (10p.)
cites¸te a
(num˘ar natural nenul)
b ← 4*a
min ← -1
pentru x ← 1, b, 1 execut˘a
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
pentru y ← 1, b/x, 1 execut˘a
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
aux ← |x+y-a| + |x*y-b|
dac˘a min=-1 sau aux < min atunci
 min ← aux
returneaz˘a min

Subiect · pagina 2

SUBIECTUL al II-lea (30 de puncte)
Pentru fiecare dintre itemii 1 ¸si 2 scriet¸i pe foaia de examen litera cores-
punz˘atoare r˘aspunsului corect.
1. Un graf k-partit este un graf ale c˘arui vˆarfuri pot fi partit¸ionate ˆın k mult¸imi
disjuncte {U1, . . . , Uk} astfel ˆıncˆat s˘a nu existe nicio muchie cu ambele extremit˘at¸i ˆın
aceea¸si mult¸ime Ui, i = 1..k. Care este num˘arul maxim de muchii pe care ˆıl poate avea
un graf 4-partit, avˆand proprietatea SUiS ≤ i + 1, i = 1..4? (6p.)
a. 15 b. 46 c. 71 d. 120
2. Un graf neorientat cu 6 noduri are gradele nodurilor egale cu 2, 2, 2, 2, 2, x.
Pentru ce valoare a lui x graful este arbore? (4p.)
a. x=0 b. x=1 c. x=2 d. nicio valoare
Scriet¸i pe foaia de examen r˘aspunsul pentru fiecare dintre cerint¸ele
urm˘atoare.
3. O matrice este rar˘a dac˘a majoritatea elementelor sale sunt nule (egale cu zero).
O matrice rar˘a M, avˆand k elemente nenule, poate fi reprezentat˘a prin intermediul a
trei tablouri de numere ˆıntregi ro w, col ¸si val, avˆand fiecare k elemente, astfel ˆıncˆat
pentru orice linie i ¸si coloan˘a j: M[i][j]=a dac˘a ¸si numai dac˘a exist˘a p, 0 ≤ p ≤
k-1, astfel ˆıncˆat ro w[p]=i, col[p]=j ¸si val[p]=a. Scriet¸i un program C/C++ care:
 cite¸ste din fi¸sierul standard de intrare (tastatura) valorile ˆıntregi n,m,k;
 genereaz˘a aleator dou˘a matrici rare M1 ¸si M2 avˆand n linii, m coloane ¸si exact k
elemente nenule, reprezentate ˆın forma descris˘a mai sus;
 afi¸seaz˘a cele dou˘a matrici precum ¸si suma acestora sub form˘a de tablou (ˆın care
apar ¸si elementele nule).
(10p.)
4. Un text s de lungime 2n, unde n este un num˘ar natural par, este codificat ˆın
felul urm˘ator: se construie¸ste o matrice p˘atrat˘a de dimensiune n×n ˆın care primele n
caractere ale lui s se g˘asesc ˆın ordine, de sus ˆın jos, pe diagonala secundar˘a a matricii
iar urm˘atoarele n caractere ˆın ordine, de sus ˆın jos, pe diagonala principal˘a. Restul
caracterelor matricii sunt generate aleator. Matricea este apoi transformat˘a ˆıntr-un
¸sir de caractere cod(s) prin concatenarea ¸sirurilor de caractere reprezentate de liniile
acesteia (ˆın ordine, de sus ˆın jos).
Scriet¸i un program C/C++ care execut˘a operat¸ia de decodificare a procesului descris
mai sus. Aplicat¸ia cite¸ste din fi¸sierul standard de intrare (tastatura) ¸sirul de caractere
cod(s) ¸si extrage textul init¸ial s (care a fost codificat).
Exemplu: dac˘a la intrare s-a introdus TPQAREDSXMRYIUVE, atunci rezultatul este
ADMITERE, corespunz˘ator matricii de codificare:
T P Q A
R E D S
X M R Y
I U V E
(10p.)

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. In cadrul unei competit¸ii particip˘a 10 echipe care trebuie ˆımp˘art¸ite ˆın 2 grupe,
fiecare grup˘a avˆand 5 echipe. Ordinea echipelor ˆıntr-o grup˘a nu conteaz˘a ¸si nici
ordinea grupelor. ˆIn cˆate moduri pot fi create aceste grupe ? (4p.)
a. 55 b. 110 c. 220 d. 1024
Scriet¸i pe foaia de examen r˘aspunsul pentru fiecare dintre cerint¸ele
urm˘atoare.
2. Pentru funct¸ia F definit˘a al˘aturat,
ce valoare va returna apelul F(2,1) ?
(6p.)
int F(int m, int n) {
if (m > 0) {
if (n == 0) return F(m-1,1);
if (n > 0) return F(m-1, F(m, n-1));
}
return n+1;
}
3. Se consider˘a o mult¸ime de cuvinte care trebuie plasate (ˆıncruci¸sate) ˆıntr-o matrice
(careu) fie pe orizontal˘a, fie pe vertical˘a, o liter˘a a unui cuvˆant ocupˆand o celul˘a a
careului. Dou˘a cuvinte se pot suprapune sau intersecta ˆın careu doar dac˘a au acelea¸si
litere la pozit¸iile comune. In careu pot r˘amˆane celule neocupate.
In exemplul de mai jos, cuvintele {BUN, UNU, DOI, NOR} sunt corect ˆıncruci¸sate.
B U N U
- D O I
- - R -
a) Descriet¸i o solut¸ie pentru problema ˆın care mult¸imea de cuvinte este {INFO,
GREU, TEST, REN, JOC, FOC} iar careul are trei linii ¸si cinci coloane. (4p.)
b) Descriet¸i ˆın limbaj natural algoritmul pentru rezolvarea acestei probleme. (6p.)
c) Scriet¸i ˆın limbajul C/C++ o funct¸ie care:
 prime¸ste ca argumente tabloul cuvintelor ce trebuie plasate, num˘arul aces-
tora precum ¸si dimensiunile careului;
 returneaz˘a o matrice de caractere reprezentˆand o plasare corect˘a a cuvin-
telor.
Celulele careului care nu sunt ocupate de vreun cuvˆant vor fi completate cu
caracterul special minus (-). ˆIn cazul ˆın care problema nu are solut¸ie, matricea
va cont¸ine doar minusuri (-). (10p.)

Deschide documentul original

Barem · 3 pagini

Barem · pagina 1

   
    
  !"## 
$%&'()*+&,-.,/01*,0&,2+&3/4,21+.,+514&0&-/26,0&*/0&*+.,,*&01)+5&2/07
$8(9&,*/04.,'()*+,:&1)+&03&41,0&;,2+&2&4&*<,+*&2&'0&*1-,+&&='21*1+'01)>,0&378(9&,*/04.,
?0,*+51()14&'()*+7
$%&,*/04.,@A'()*+&41)/B*1(78/+,B),2.,9&*,2*(2&,-.,'01)<C3'.,0+510&,'()*+,:(2(1+/+,2,*/04,+
'&)+0(2(*0,0&2,@A7
$<D)*,-(2<C)*,0&0.,9'()9(2B),22,/<C)+0&>,0&*,0&)()&*&91+.,:(9+1B*,0&)(&9+&*/0&*+4,0&=19+.,
:(9+1B*.,01',0+51,2*/0&*+&;'()*+,:(29&*,2*(2&,-.,*/)?/03 >,0&3(2(1,B59,+7
  EFGHI
JK  LK
MK K N OK
PQ4&9*01&0&,*,2*(2(2(1 R'7
SQ/>+51)&0&,0&-(2+,+(2(1*/0&*+ T'7
K UVWXY OK
PQ14&)+1B*,0&,91+(,+51&1<C)*,0&Z[\]^_
`ab]c591`db]ec
T'7
SQ*,2*(2(29/2(+51&1<C)+0&f1 T'7
gQ/>+51)&0&,6,2/012/0Z[\]^hc]Pi T'7
K  j  LK
PQ ?/2/910&,()&19+0(*+(010&'&+1+16&
klcmm[Zn9,(opnpmqc
T'7
SQ9*01&0&,*/0&*+.,,,2f/01+3(2(1 T'7
HK  j  JGK
PQ9+0(*+(0,*/0&*+.,,'0/f0,3(2(1 T'7
SQ*1+10&,*/0&*+.,,',0,3&+0(2(1c @'7
gQ1)9+0(*+51()10&'&+1+16&*/0&*+& r'7
eQ1)9+0(*+51()&4&4&*1-1&*/0&*+., T'7
sQ*,2*(2,0&,*/0&*+.,,6,2/011Z[\ T'7

Barem · pagina 2

    
  
  
   
!"#$#%&'('$&)*%(&#+$%'%& ,-.
/!01+"$2#'(&%&$1%+'%&'&)&3&+$1)1#(&)'
*'+13#$4'-*5#$2#&6)#+#&7"*)*'+4'8'3'$%#"##
9-.
:!01+"$2#'(&;&+&%'%&')&'$*'%&'1+&#3'<
$%#"#
9-.
=!01+"$2#'(&'>2?'%&'1+&#3'$%#"# ,-.
@!01+"$2#'(&'(1+'%&'(*14'3'$%#"#%'%& 9-.
A!?$%1"$1%'"*%&"$4''-%*;%'31)1# 9-.
   
!"#$#%&'('$&)*%(&#+$%'%& ,-.
/!B&%#>"'%&')1+;#3##2?#%1)1#(&#+$%'%& ,-.
:!"%&'%&'3'$%#"##(&"*(#>"'%& C-.
=!#(&+$#>"'%&'2?#%1)1#"*(#>"'$ C-.
@!?$%1"$1%'"*%&"$4''-%*;%'31)1# 9-.

Barem · pagina 3

    
  

 !"#$%"&'( )
*+#,%$-$%.&/0".!"&102%&%
$%"$0-
34
5+"/"///02678 94
:+#,&10!%$%$%;/&&/0"#$%"& 74

 < ==>??@= 
A B C D E
F C G F H
I J K H L
M4
 < ==@N=O @= )
*+P%"$0%$%Q#P /0P%$"$R%$%
&10/0#/&100/#$
94
5+P%"$0%$%Q#P /0P%-/0P$%"S
-0!&%/#$/&%TU!"$%
34
:+ P%"$0%$% Q#P /0 P% "&S
/0;$%V$%& $$%"$%/0" $Q$%
/$00V$%&$R%$00 ! 0"-T!&
74
 < ==@N=O @= 
*+ "$%$%100!0&10/0;$%Q&$0"%0P%
"$"&%$%
34
5+"$%$%100!0&10/0;$%&$"&$00P%
P&%%!&$ "#!&#$0;$%$ !%$S
0/#$P%/0&%$%P0!"$%
34
:+ .!"&10P%-/0P$%/$00 ! 0
"-T!&TU!"$%
34
W+.!"&10P%"&/0;$%&$"&$0/#$
P%P&%" $Q$%/$00 ! 0"-T!&
34
X+.!"&10P%"&/0;$%&$"&$0/#$
P%P&%" $Q$% $%&$R%$00 ! 0
"-T!&
34
Y+ P%"$0%$% ! 0/R#$0&Q P%&0
,"Z&$"ZS0!R6 %"[0-/%!&8
94
\+0Q/%Q%!&$%"#$%"&/R#$0&Q S
/0
74
]^_^‘a‘bcd^cefc

Deschide documentul original

Continuă pregătirea

Vezi arhiva completă

Examen de admitere · 2014Informatică · Sesiunea iulieDeschide fișa Examen de admitere · 2015Informatică · Sesiunea iulieDeschide fișa Examen de admitere · 2016Informatică · Sesiunea iulieDeschide fișa Examen de admitere · 2017Informatică · Sesiunea iulieDeschide fișa Examen de admitere · 2017Matematică · Sesiunea iulieDeschide fișa Examen de admitere · 2018Informatică · 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 2013 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.

Pregătire cu un profesor

Subiect și barem

Examen de admitere · Informatică · 2013

Despre acest subiect

Subiectul și baremul în format text

Subiect · pagina 1