Informatică #061 · Model admitere MateInfo UB

Question 1

Graful neorientat cu 7 noduri are muchiile [1,2], [1,3], [2,3], [2,4], [3,5], [4,5], [4,6], [5,7], [6,7]. Câte noduri au gradul par?

Accepted Answer

F) 3. Gradele sunt: 1→2, 2→3, 3→3, 4→3, 5→3, 6→2, 7→2. Au grad par nodurile 1, 6, 7. (Verificare: suma gradelor, 18, este dublul numărului de muchii.)

Answer

7

Answer

2

Answer

4

Answer

0

Answer

5

Question 2

Care este scrierea în baza 16 a numărului 2026?

Accepted Answer

E) `7EA`. 2026=7·256+234, iar 234=14·16+10. Cifrele sunt 7, 14 (`E`) și 10 (`A`): `7EA`.

Answer

`7AE`

Answer

`AE7`

Answer

`7DA`

Answer

`6EA`

Answer

`7E10`

Question 3

Ce afișează secvența alăturată?

Accepted Answer

E) 100. Pentru fiecare i bucla interioară face lfloor√(i)rfloor pași: 1 pentru i=1..3, 2 pentru i=4..8, 3 pentru i=9..15, 4 pentru i=16..24, 5 pentru i=25..30. Total 3+10+21+36+30=100 (în general O(nsqrt n)).

Answer

90

Answer

110

Answer

150

Answer

30

Answer

465

Question 4

O broască trebuie să ajungă de pe prima pe ultima dintre 6 pietre așezate în linie, cu înălțimile 10,30,40,20,50,30. Dintr-o piatră sare fie pe următoarea, fie peste una, iar un salt costă diferența în modul dintre înălțimile celor două pietre. Care este costul total minim?

Accepted Answer

F) 40. Cu d_i=min(d_i-1+|h_i-h_i-1|, d_i-2+|h_i-h_i-2|) și d_1=0 se obțin pe rând 0,20,30,30,40,40. Un drum optim: 10→30→20→30 peste pietre, cu costurile 20+10+10=40.

Answer

50

Answer

30

Answer

60

Answer

100

Answer

45

Question 5

Un arbore binar are parcurgerea în inordine `H D B E A F I C G` și parcurgerea în postordine `H D E B I F G C A`. Care este parcurgerea lui în preordine?

Accepted Answer

C) `A B D H E C F I G`. Rădăcina este ultimul nod din postordine, `A`; în inordine, `H D B E` formează subarborele stâng, iar `F I C G` pe cel drept. Repetând: stânga are rădăcina `B` (cu `D`, care îl are pe `H` ca fiu stâng, și `E`), dreapta are rădăcina `C` (cu `F`, al cărui fiu drept e `I`, și `G`). Preordinea: `A B D H E C F I G`.

Answer

`A B E D H C F I G`

Answer

`A B D H E C I F G`

Answer

`A B D E H C F G I`

Answer

`A D H B E C F I G`

Answer

`A B H D E C F I G`

Informatică #061 · Model admitere MateInfo UB

Alte subiecte de informatică

Ai deja cont?

Cum funcționează

Seturi la întâmplare