ALGORITMI sI STRUCTURI DE DATE
Propunator: Lector MARIUS PETCU
1. Care din urmatoarele afirmatii este gresita?
a) Un algoritm este o lista de instructiuni care descriu un proces ce se desfasoara pas cu pas si care conduce la un rezultat.
b) Proprietatile fundamentale ale algoritmilor sunt finitudinea, determinismul si eficacitatea.
c) Un algoritm trebuie sa aiba o intrare si o iesire.
d) Un algoritm conceput pentru o anumita problema trebuie sa functioneze pentru orice intrari din domeniul problemei.
e) Orice metoda de calcul este un algoritm.
Raspuns : e
2. Care din urmatoarele afirmatii este gresita?
a) Algoritmii se pot reprezenta prin scheme logice, în pseudocod 232j912c , fie printr-un limbaj de programare.
b) O schema logica este o reprezentare grafica a unui circuit electric cu porti logice.
c) Avantajul reprezentarii prin schema logica este acela ca nu trebuie cunoscut un limbaj de programare pentru a reprezenta un algoritm.
d) O schema logica poate contine urmatoarele simboluri grafice: start, stop, intrare, iesire, atribuire, decizie si altele.
e) O schema logica este un graf orientat în care nodurile sunt simboluri grafice ale operatiilor pe care le efectueaza algoritmul iar arcele dau ordinea de efectuare a acestor operatii.
Raspuns : b ( ?)
3. Care din urmatoarele afirmatii este corecta?
a) O structura de prelucrare secventiala contine numai start, stop, citiri (intrari), tipariri (iesiri) si atribuiri.
b) O structura de prelucrare secventiala contine cel putin un bloc de decizie.
c) O structura de prelucrare secventiala contine cel putin un ciclu.
d) O structura de prelucrare secventiala trebuie sa contina cel putin o ramificatie.
e) Nici una din afirmatiile de mai sus nu este adevarata.
Raspuns : e
4. Care din urmatoarele afirmatii este gresita pentru structura while-repeat (cât timp-repeta)?
a) Corpul ciclului este parcurs cel putin o data.
b) Testarea conditiei se face la intrarea în ciclu.
c) Corpul ciclului se executa atât timp cât conditia este adevarata.
d) Se mai numeste si ciclu cu test initial.
e) Este acceptata de programarea structurata ca structura de baza.
Raspuns: a
5. Care din urmatoarele afirmatii este gresita pentru structura repeat-until (repeta-pâna când)?
a) Corpul ciclului este parcurs cel putin o data.
b) Testarea conditiei se face la iesirea din ciclu.
c) Se mai numeste si ciclu cu test initial.
d) Se mai numeste si ciclu cu test final.
e) Nici una din afirmatiile anterioare nu este gresita.
Raspuns: c
6. Etapele unui ciclu for (pentru) sunt în ordine:
a) initializarea, testarea, functionarea, modificarea;
b) initializarea, modificarea, functionarea, testarea;
c) testarea, initializarea, modificarea, functionarea;
d) initializarea, functionarea, modificarea, testarea;
e) nici una din variantele de mai sus.
Raspuns: a
7. Care din urmatoarele afirmatii este gresita pentru o structura repetitiva de tip for (pentru)?
a) Se mai numeste si ciclare cu numar prestabilit de pasi.
b) Iesirea se face pe baza testarii unei conditii asupra unei variabile întregi numita variabila ciclului sau contor.
c) Are doua forme: ascendenta, în care valoarea contorului creste si descendenta, în care valoarea contorului scade.
d) Poate fi înlocuita cu o structura while.
e) Este acceptata de programarea structurata ca structura de baza.
Raspuns: e
8. Care din urmatoarele afirmatii este gresita?
a) Un subprogram este o secventa de instructiuni care implementeaza un algoritm sau o parte a unui algoritm.
b) Un subprogram poate fi de tip procedura sau de tip functie.
c) O functie este un subprogram care returneaza un rezultat.
d) La apelarea unei functii, parametri formali sunt înlocuiti cu valorile parametrilor actuali din apel.
e) Un program poate contine cel mult un subprogram.
Raspuns: e
9. Care din urmatoarele afirmatii este gresita?
a) Orice schema logica este echivalenta cu o schema logica bine structurata.
b) Elementele (blocurile) de conectare au rolul de a lega diversele parti ale unei scheme logice.
c) Pe o schema logica nu se poate pune în evidenta diferenta dintre structura while si structura for.
d) Exista algoritmi care nu se pot reprezenta printr-o schema logica, ci numai în pseudocod.
e) Blocurile de decizie sunt singurele elemente ale unei scheme logice care au doua iesiri.
Raspuns: d
10. Care din urmatorii factori nu influenteaza timpul de executie al unui program?
a) Numarul n al datelor de intrare;
b) Performantele compilatorului.
c) Viteza procesorului.
d) Marimea hard-disk-ului.
e) Complexitatea de timp a algoritmului care sta la baza programului.
Raspuns: d
11. Fie un algoritm care lucreaza asupra a n date. stiind ca se efectueaza 2n+1 atribuiri, n-1 adunari, n-1 înmultiri, si n decizii, se cere complexitatea de timp T(n) a algoritmului. Se considera ca fiecare tip de operatie consuma acelasi timp.
a) O b) O(log2 n) c) O(n) d) O(n log2 n) e) O(n2)
Raspuns: c
12. Fie un algoritm care lucreaza asupra a n date. stiind ca se efectueaza 2n atribuiri, n-1 adunari, n+1 înmultiri, si (n-1 n+1) decizii, se cere complexitatea de timp T(n) a algoritmului. Se considera ca fiecare tip de operatie consuma acelasi timp.
a) O b) O(log2 n) c) O(n) d) O(n log2 n) e) O(n2)
Raspuns: e
13. Functia de locatii da informatii asupra:
a) spatiului de memorie ocupat de variabilele algoritmului.
b) complexitatii de timp a algoritmului.
c) spatiului de memorie ocupat de program.
d) performantelor compilatorului.
e) vitezei de executie a instructiunilor.
Raspuns: a
14. Se da schema logica:
Precizati ce va "tipari" executia ei.
a) 11 12 21 22 31 32 b) 11 12 13 21 22 23 c) 11 12 13 d)11 22 23 e) 3 2 1
Raspuns: a
15. Se da schema logica:
Precizati ce va "tipari" executia ei.
a) 1 2 3 4 b) 2 3 4 c) 1 2 3 d) 2 3 e) 3 2 1
Raspuns: b
16. Se da schema logica:
Precizati ce va "tipari" executia ei.
a) 1 2 2 3 3
b) 2 2 3 3 4 4
c) 2 3 4 4 5
d) 1 2 3 4 5
e) 2 3 3 4 4 5
Raspuns: e
17. Se da schema logica:
unde S reprezinta un bloc oarecare de instructiuni.
Precizati ce structura algoritmica este reprezentata.
a) structura alternativa simpla.
b) structura alternativa completa.
c) structura for (pentru) forma ascendenta.
d) o structura liniara.
e) structura for (pentru) forma descendenta.
Raspuns: c
18. Se da schema logica:
unde S reprezinta un bloc oarecare de instructiuni.
Precizati ce structura algoritmica este reprezentata.
a) structura alternativa simpla.
b) structura alternativa completa.
c) structura for (pentru) forma ascendenta.
d) o structura liniara.
e) structura for (pentru) forma descendenta.
Raspuns: e
19. Se da schema logica:
unde S reprezinta un bloc oarecare de instructiuni.
Precizati ce structura algoritmica este reprezentata.
a) structura do-repeat (repeta-pâna când).
b) structura alternativa completa.
c) structura for (pentru) forma ascendenta.
d) o structura liniara.
e) structura for (pentru) forma descendenta.
Raspuns: a
20. Se da schema logica:
Precizati câte decizii se iau la executia ei.
a) una b) doua c) trei d) patru e) nici una
Raspuns: d
21. Care din secventele de mai jos definesc un pointer p catre un nod al unei liste liniare simplu înlantuite de numere întregi?
a) typedef struct nod LNOD; } LNOD;
LNOD *p; LNOD *p;
c) typedef struct nod LNOD; } LNOD;
LNOD *p; LNOD p;
d) typedef nod LNOD;
LNOD *p;
Raspuns: c
22. Fie p un pointer catre primul nod al unei liste liniare simplu înlantuite de numere întregi. Spre al câtelea nod va pointa p în urma executiei secventei urmatoare:
i=1;
while(i<=4)
a) 3 b) 4 c) 5 d) 6 e) secventa este gresita.
Raspuns: c
23. Fie p un pointer catre primul nod al unei liste liniare simplu înlantuite de numere întregi. Spre al câtelea nod va pointa p în urma executiei secventei urmatoare:
i=1;
dowhile(i<=5);
a) 3 b) 4 c) 5 d) 6 e) secventa este gresita.
Raspuns: d
24. Fie p un pointer catre primul nod al unei liste liniare simplu înlantuite de numere întregi. Spre al câtelea nod va pointa p în urma executiei secventei urmatoare:
for(i=1;i<5;i++)
p=p->urm;
a) 3 b) 4 c) 5 d) 6 e) secventa este gresita.
Raspuns: c
25. Fie p un pointer catre primul nod al unei liste liniare simplu înlantuite de numere întregi cu elementele: 3,4,5,6. Ce valoare va returna functia urmatoare:
int functie(LNOD *p)
return s;
a) 3 b) 4 c) 8 d) 10 e) 18.
Raspuns: b
26. Fie p un pointer catre primul nod al unei liste liniare simplu înlantuite de numere întregi care contine în ordine:-1,6,5,6,-6,5. Precizati ce va afisa secventa urmatoare:
int i=0;
while(p)
printf("%d",i);
a) 0 b) 1 c) 2 d) 3 e) 4.
Raspuns: c
27. Fie p si q doi pointeri ce adreseaza doua noduri ale unei liste liniare simplu înlantuite. Care din urmatoarele instructiuni leaga nodul adresat de q în continuarea nodului adresat de p?
a) p=q;
b) q=p;
c) q->urm=p;
d)p->urm=q;
e) p->urm=q->urm;
Raspuns: d
28. Fie p un pointer catre primul nod al unei liste liniare simplu înlantuite de numere întregi. Care din functiile de mai jos va returna produsul numerelor continute de lista în urma apelului x=prod(p);
a) int prod(LNOD *p) }
return m; return m;
} }
c) int prod(LNOD *p)while(p); }while(p->urm);
return m; return m;
} }
e) nici una.
Raspuns: a
29. Fie p un pointer catre primul nod al unei liste liniare simplu înlantuite de numere întregi. Care din urmatoarele instructiuni afiseaza numarul continut de al treilea nod din lista?
a) printf("%d",p->urm->urm->info);
b) printf("%d",p->urm->urm->urm);
c) printf("%d",p->urm->info);
d) printf("%d",p->urm->urm->urm->info);
e) printf("%d",p->urm->info->info);
Raspuns: a
30. Fie p un pointer catre primul nod al unei liste liniare simplu înlantuite de numere întregi. Care este actiunea functiei urmatoare?
void functie(LNOD *p)
a) Afiseaza informatia continuta de lista, din toate nodurile.
b) Afiseaza informatia continuta de lista, mai putin ultimul nod.
c) Afiseaza informatia continuta de lista, mai putin primul nod.
d) Afiseaza numai elementele distincte din lista.
e) Nici una din actiunile de mai sus.
Raspuns: a
31. Fie p un pointer catre primul nod al unei liste liniare simplu înlantuite de numere întregi. Care este actiunea functiei urmatoare?
LNOD * func(LNOD *p)
a) Creaza un nod nou si îl adauga la sfârsitul listei, returnând adresa sfârsitului listei.
b) Creaza un nod nou si îl insereaza la începutul listei, returnând adresa începutului listei.
c) Modifica continutul primului nod al listei, adresa ramânând neschimbata.
d) Modifica adresa primului nod, continutul ramânând neschimbat.
e) Nici una din actiunile de mai sus.
Raspuns: b
32. Fie q un pointer catre ultimul nod al unei liste liniare simplu înlantuite de numere intregi. Care este actiunea functiei urmatoare?
LNOD * func(LNOD *q)
a) Creaza un nod nou si îl adauga la sfârsitul listei, returnând adresa sfârsitului listei.
b) Creaza un nod nou si îl insereaza la începutul listei, returnând adresa începutului listei.
c) Modifica continutul ultimului nod al listei, adresa ramânând neschimbata.
d) Modifica adresa ultimului nod, continutul ramânând neschimbat.
e) Nici una din actiunile de mai sus.
Raspuns: a
33. Fie p un pointer catre primul nod al unei liste liniare simplu înlantuite de numere întregi. Care este actiunea functiei urmatoare?
LNOD * func(LNOD *p, int k)
return q;
}
a) Cauta primul nod al listei si returneaza adresa sa.
b) Cauta nodul care contine valoarea k în câmpul info si returneaza adresa sa.
c) Cauta nodul urmator nodului ce contine valoarea k în câmpul info.
d) Cauta nodul de pe pozitia k si returneaza adresa sa.
e) Nici una din actiunile de mai sus.
Raspuns: b
34. Care din urmatoarele afirmatii este gresita?
a) O stiva este o lista la care toate operatiile se efectueaza la un singur capat numit vârf.
b) O stiva poate fi implementata fie static folosind tipul tablou, fie dinamic folosind alocarea dinamica.
c) Inaltimea stivei este numarul de noduri (înregistrari) din stiva.
d) Inaltimea maxima a unei stive implementata prin tipul tablou este limitata prin declaratia tabloului.
e) O stiva este o lista de tip "FIFO" (primul intrat, primul iesit).
Raspuns: e
35. Care din urmatoarele afirmatii este gresita?
a) O coada este o lista de tip "FIFO" (primul intrat, primul iesit).
b) O coada este o lista la care elementele sunt inserate la un capat (spate) si sunt suprimate la celalalt capat (fata).
c) O coada poate fi implementa fie static folosind tipul tablou (circular), fie dinamic folosind alocarea dinamica.
d) In implementarea dinamica, pentru coada se retin doi pointeri: unul care adreseaza primul element si unul care adreseaza ultimul element.
e) Toate afirmatiile anterioare sunt gresite.
Raspuns: e
36. Se considera definitia unei structuri pentru o lista liniara dublu înlantuita ca mai jos.
typedef struct tipnod LLNOD;
Care din urmatoarele afirmatii este gresita?
a) info este câmpul de informatie utila (un numar întreg).
b) prec este un pointer catre nodul precedent.
c) urm este un pointer catre nodul urmator în lista.
d) Existenta celor doi pointeri (prec si urm) permite parcurgerea listei în ambele sensuri.
e) O lista dublu înlantuita nu permite inserarea unui element nou decât pe la unul din capete.
Raspuns: e
37. Care din urmatoarele afirmatii este gresita?
a) Un arbore este o multime finita de elemente de acelasi fel numite noduri, care daca nu e vida, atunci are un nod radacina si fiecare din celelalte noduri sunt la rândul lor arbori.
b) Un nod care nu are fii se numeste nod terminal sau frunza.
c) Numarul fiilor unui nod se numeste gradul nodului.
d) Gradul maxim al nodurilor unui arbore se numeste gradul arborelui.
e) Nodurile unui arbore sunt întotdeauna ordonate.
Raspuns: e
38. Care din urmatoarele afirmatii este gresita?
a) Un nod al unui arbore nu poate fi în acelasi timp si stramos si descendent.
b) Lungimea unui drum la un nod este numarul de sageti ce trebuiesc parcurse pentru a ajunge din radacina la nodul respectiv.
c) Inaltimea unui arbore este cel mai lung drum la un nod terminal.
d) Inaltimea unui arbore este egala cu numarul de niveluri din arbore.
e) Radacina arborelui este singurul nod fara stramosi.
Raspuns: a
39. Care din urmatoarele afirmatii este corecta?
a) Un arbore binar este un arbore de gradul 2.
b) Un arbore binar este un arbore de înaltime 2.
c) Fiecare nod al unui arbore binar are doi descendenti.
d) Fiecare nod al unui arbore binar are doi stramosi directi.
e) Un arbore binar contine ca elemente numai numere în baza 2.
Raspuns: a
40. Care din urmatoarele afirmatii este gresita?
a) Un arbore binar poate fi traversat în oricare din urmatoarele moduri: in preordine, in inordine, in postordine.
b) Structura arborelui se modifica în functie de modul de traversare.
c) Traversarea in preordine presupune vizitarea nodului radacina apoi a nodului stâng si a nodului drept.
d) Traversarea in inordine presupune vizitarea nodului stâng, apoi a radacinii si a nodului drept.
e) Traversarea in postordine presupune vizitarea nodului stâng apoi a celui drept si la sfârsit nodul radacina.
Raspuns: b
41. Se da urmatoarea definitie de structura:
typedef struct pnod ANOD;
stiind ca tipul int se reprezinta pe 2 octeti si adresele de asemenea pe 2 octeti, precizati câti octeti vor fi alocati pentru variabila p declarata astfel:
ANOD *p;
a) 2 octeti b) 4 octeti c) 6 octeti d) 10 octeti e) nu se poate preciza
Raspuns: a
42. Se da urmatoarea definitie de structura:
typedef struct pnod ANOD;
stiind ca tipul int se reprezinta pe 2 octeti si adresele de asemenea pe 2 octeti, precizati câti octeti vor fi alocati pentru variabila p declarata astfel:
ANOD p;
a) 2 octeti b) 4 octeti c) 6 octeti d) 10 octeti e) nu se poate preciza
Raspuns: c
43. Se da arborele din figura:
Precizati ordinea de parcurgere a nodurilor la traversarea în preordine:
a) 1 2 3 4 5 6 b) 3 2 4 1 5 6 c) 3 4 2 6 5 1 d) 6 5 4 3 2 1 e) 1 4 2 5 3 6
Raspuns: a
44. Se da arborele din figura:
Precizati ordinea de parcurgere a nodurilor la traversarea în inordine:
a) 1 2 3 4 5 6 b) 3 2 4 1 5 6 c) 3 4 2 6 5 1 d) 6 5 4 3 2 1 e) 1 4 2 5 3 6
Raspuns: b
45. Se da arborele din figura:
Precizati ordinea de parcurgere a nodurilor la traversarea în postordine:
a) 1 2 3 4 5 6 b) 3 2 4 1 5 6 c) 3 4 2 6 5 1 d) 6 5 4 3 2 1 e) 1 4 2 5 3 6
Raspuns: c
46. Se da functia de mai jos în care valoarea initiala a pointerului p adreseaza nodul radacina al unui arbore binar. Precizati care este actiunea ei.
void functie(ANOD *p)
a) Realizeaza afisarea informatiilor din arbore în preordine;
b) Realizeaza afisarea informatiilor din arbore în inordine;
c) Realizeaza afisarea informatiilor din arbore în postordine;
d) Conduce la un ciclu infinit;
e) Functia contine erori de sintaxa.
Raspuns: a
47. Se da functia de mai jos în care valoarea initiala a pointerului p adreseaza nodul radacina al unui arbore binar. Precizati care este actiunea ei.
void functie(ANOD *p)
a) Realizeaza afisarea informatiilor din arbore în preordine;
b) Realizeaza afisarea informatiilor din arbore în inordine;
c) Realizeaza afisarea informatiilor din arbore în postordine;
d) Conduce la un ciclu infinit;
e) Functia contine erori de sintaxa.
Raspuns: b
48. Se da functia de mai jos în care valoarea initiala a pointerului p adreseaza nodul radacina al unui arbore binar. Precizati care este actiunea ei.
void functie(ANOD *p)
a) Realizeaza afisarea informatiilor din arbore în preordine;
b) Realizeaza afisarea informatiilor din arbore în inordine;
c) Realizeaza afisarea informatiilor din arbore în postordine;
d) Conduce la un ciclu infinit;
e) Functia contine erori de sintaxa.
Raspuns: c
49. Se da un vector v[n] cu n elemente
întregi. Carei metode de sortare îi corespunde urmatorul algoritm:
"se considera subtabloul v[i],.,v[n-1] care se parcurge de la dreapta la
stânga, comparând si interschimbând perechile de elemente alaturate
care nu satisfac relatia de ordine, procedeul repetându-se pentru i=1.n-
a) Sortarea prin interschimbare (bubblesort).
b) Sortarea prin insertie.
c) Sortarea prin selectie.
d) Sortarea prin numarare.
e) Sortarea prin interclasare.
Raspuns: a
50. Se da un vector v[n] cu n elemente întregi. Carei metode de sortare îi corespunde urmatorul algoritm: "Secventa v[0],.v[i-1] se considera ordonata si urmeaza ca v[i] sa fie inserat în aceasta secventa la locul potrivit, astfel încât secventa v[0],.,v[i-1],v[i] sa devina ordonata"?
a) Sortarea prin interschimbare (bubblesort).
b) Sortarea prin insertie.
c) Sortarea prin selectie.
d) Sortarea prin numarare.
e) Sortarea prin interclasare.
Raspuns: b
51. Se da un vector v[n] de elemente
întregi. Carei metode de sortare îi corespunde urmatorul algoritm:
"se considera subtabloul v[i],.v[n-1] si vom cauta elementul
minim din acest subtablou; facem apoi interschimbarea lui v[i] cu elementul
minim determinat. Repetam
procedeul pentru i=1.n-
a) Sortarea prin interschimbare (bubblesort).
b) Sortarea prin insertie.
c) Sortarea prin selectie.
d) Sortarea prin numarare.
e) Sortarea prin interclasare.
Raspuns: c
52. Se da un vector v[n] de elemente întregi. Carei metode de sortare îi corespunde urmatorul algoritm: "asociem vectorului v[n] un vector p[n] cu toate elementele 0; se compara pe rând fiecare element v[i] cu precedentele; la o comparatie cu v[k] se incrementeza valoarea lui p[i] daca v[i]>v[k] , respectiv p[k] daca v[i]<=v[k]; vectorul p[n] va contine în final ordinea elementelor lui v[n]"?
a) Sortarea prin interschimbare (bubblesort).
b) Sortarea prin insertie.
c) Sortarea prin selectie.
d) Sortarea prin numarare.
e) Sortarea prin interclasare.
Raspuns: d
53. Se da un vector v[n] de elemente întregi. Carei metode de sortare îi corespunde urmatorul algoritm: "se divide vectorul v[n] în subtablouri din ce în ce mai mici pâna când fiecare subtablou contine un singur element (deci sunt subtablouri ordonate); apoi se reunesc aceste subtablouri printr-o procedura care le pastreaza ordonate"?
a) Sortarea prin interschimbare (bubblesort).
b) Sortarea prin insertie.
c) Sortarea prin selectie.
d) Sortarea prin numarare.
e) Sortarea prin interclasare.
Raspuns: e
54. Care din urmatoarele afirmatii este gresita pentru sortarea prin amestecare (shakersort)?
a) Este o varianta a metodei bubblesort.
b) La fiecare parcurgere a subtabloului v[i],.,v[n-1] se memoreaza indicele k al ultimei interschimbari efectuate.
c) Se schimba alternativ sensul de parcurgere al subtablourilor pentru doua treceri consecutive.
d) Sensul de parcurgere al subtablourilor este totdeauna de la stânga la dreapta.
e) Complexitatea de timp a algoritmului este T(n)=O(n2).
Raspuns: d
55. Care din urmatoarele afirmatii este gresita pentru sortarea prin insertie binara?
a) Este o varianta a sortarii prin insertie.
b) Este o varianta a sortarii prin selectie.
c) Tabloul este vazut ca fiind format din doua subtablouri: unul care este ordonat si unul din care se extrag elemente pentru a fi introduse (la locul potrivit) în primul.
d) Cautarea locului de inserare se face prin cautare binara.
e) Complexitatea de timp a algoritmului este T(n)=O(n2).
Raspuns: b
56. Care din urmatoarele afirmatii este gresita?
a) Complexitatea de timp a algoritmului de traversare a unui vector v[n] este T(n)=O(n).
b) Complexitatea de timp a algoritmului de traversare a unui tablou v[n][n] este T(n)=O(n).
c) Complexitatea de timp a algoritmului de traversare a unui tablou v[n][n] este T(n)=O(n2).
d) Pentru calculul de complexitate de timp al unui algoritm se considera cazul cel mai defavorabil.
e) Algoritmul de traversare al unui tablou are comportare polinomiala în timp.
Raspuns: b
57. Ce va "tipari" urmatoarea secventa de pseudocod:
intregi: i,n
i
n
repeta
tipareste i
i i-1
pana cand i<n-1
a) 1 2 3 4 5 b) 1 2 3 4 c) 1 2 3 d) 1 2 e) 1
Raspuns: e
58. Ce va "tipari" urmatoarea secventa de pseudocod:
intregi: i,n
i
n
cat timp i<n-1
tipareste i
i i+1
repeta
a) 1 2 3 4 5 b) 1 2 3 4 c) 1 2 3 d) 1 2 e) 1
Raspuns: c
59. Ce va "tipari" urmatoarea secventa de pseudocod:
intregi: i,n
n
pentru i 1 pana la n-1 executa
tipareste i
sfarsit pentru
a) 1 2 3 4 5 b) 1 2 3 4 c) 1 2 3 d) 1 2 e) 1
Raspuns: b
60. Fie urmatorul "program" în pseudocod:
intregi: a, b, c
citeste a, b, c
daca a>b atunci aux a: a b: b aux
daca b>c atunci aux b: b c: c aux
daca a>b atunci aux a: a b: b aux
tipareste (a,b,c)
Precizati actiunea sa.
a) determina maximul între a,b,c
b) ordoneaza descrescator numerele a,b si c
c) ordoneaza crescator numerele a,b si c
d) determina minimul între a, b si c
e) nici una din actiunile anterioare
Raspuns: c
61. Fie urmatorul "program" în pseudocod:
intregi:i, n, ok
ok
citeste n
i
cat timp (ok SI i<=abs(sqrt(n)))
daca n MOD i = 0 atunci ok
altfel i i+1
sfarsit daca
repeta
daca ok atunci tipareste "este"
altfel tipareste "nu este"
sfarsit daca
Precizati actiunea sa.
a) determina daca n este par
b) determina daca n este impar
c) determina daca n este prim
d) determina daca n este patrat perfect
e) alta actiune.
Raspuns: c
62. Fie urmatorul "program" în pseudocod:
intregi: n
citeste n
daca n MOD 2 = 0 atunci tipareste "este"
altfel tipareste "nu este"
sfarsit daca
Precizati actiunea sa.
a) determina daca n este par
b) determina daca n este impar
c) determina daca n este prim
d) determina daca n este patrat perfect
e) alta actiune.
Raspuns: a
63. Fie urmatorul "program" în pseudocod:
intregi: a,b,c,m
citeste a,b,c
m a
daca m>b atunci m b
daca m>c atunci m c
tipareste m
Precizati actiunea sa.
a) determina maximul între a,b,c
b) ordoneaza descrescator numerele a,b si c
c) ordoneaza crescator numerele a,b si c
d) determina minimul între a, b si c
e) nici una din actiunile anterioare
Raspuns: d
64. Fie urmatorul "program" în pseudocod:
intregi: n,c,s
s
citeste n
cat timp (n>0)
c n MOD 10
s s+c
n n DIV 10
repeta
tipareste s
Precizati actiunea sa.
a) determina daca n este par
b) determina daca n este impar
c) determina produsul cifrelor lui n
d) determina suma cifrelor lui n
e) alta actiune.
Raspuns: d
65. Fie urmatorul "program" în pseudocod:
intregi: n,c,p
p
citeste n
cat timp (n>0)
c n MOD 10
p p*c
n n DIV 10
repeta
tipareste p
Precizati actiunea sa.
a) determina daca n este par
b) determina daca n este impar
c) determina produsul cifrelor lui n
d) determina suma cifrelor lui n
e) alta actiune.
Raspuns: c
66. Fie urmatorul "program" în pseudocod:
intregi: n
citeste n
daca sqrt(n)=abs(sqrt(n)) atunci tipareste "este"
altfel tipareste "nu este"
sfarsit daca
Precizati actiunea sa.
a) determina daca n este par
b) determina daca n este impar
c) determina daca n este prim
d) determina daca n este patrat perfect
e) alta actiune.
Raspuns: e
67. Fie urmatorul "program" în pseudocod:
intregi: N, M, i, v[N]
citeste N
citeste v[1]
M v[1]
pentru i 2 pana
citeste v[i]
daca M<v[i] atunci
M v[i]
sfarsit daca
sfarsit pentru
tipareste M
Precizati care este actiunea acestui program.
a) Citeste un vector de N întregi si tipareste elementul minim.
b) Citeste un vector de N întregi si tipareste elementul maxim.
c) Ordoneaza crescator elementele vectorului v[N].
d) Calculeaza suma elementelor vectorului v[N].
e) Calculeaza produsul elementelor vectorului v[N].
Raspuns: b
68. Fie urmatorul "program" în pseudocod:
intregi: N, M, i, v[N]
citeste N
M
pentru i 1 pana
citeste v[i]
M M*v[i]
sfarsit pentru
tipareste M
Precizati care este actiunea acestui program.
a) Citeste un vector de N întregi si tipareste elementul minim.
b) Citeste un vector de N întregi si tipareste elementul maxim.
c) Ordoneaza crescator elementele vectorului v[N].
d) Calculeaza suma elementelor vectorului v[N].
e) Calculeaza produsul elementelor vectorului v[N].
Raspuns: e
69. Fie urmatorul "program" în pseudocod:
intregi: N, M, i, v[N]
citeste N
M
pentru i 1 pana
citeste v[i]
daca v[i] mod 2 = 0 atunci
M M+v[i]
sfarsit daca
sfarsit pentru
tipareste M
Precizati care este actiunea acestui program.
a) Citeste un vector de N întregi si tipareste elementul minim.
b) Citeste un vector de N întregi si tipareste elementul maxim.
c) Ordoneaza crescator elementele vectorului v[N].
d) Calculeaza suma elementelor pare ale vectorului v[N].
e) Calculeaza produsul elementelor vectorului v[N].
Raspuns: d
70. Fie urmatorul "program" în pseudocod:
intregi: N, M, i, v[N]
citeste N
M
pentru i 1 pana
citeste v[i]
daca v[i] mod 2 <> 0 atunci
M M+v[i]
sfarsit daca
sfarsit pentru
tipareste M
Precizati care este actiunea acestui program.
a) Citeste un vector de N întregi si tipareste elementul minim.
b) Citeste un vector de N întregi si tipareste elementul maxim.
c) Calculeaza suma elementelor impare ale vectorului v[N].
d) Calculeaza suma elementelor pare ale vectorului v[N].
e) Calculeaza produsul elementelor vectorului v[N].
Raspuns: c
71. Fie urmatorul "program" în pseudocod:
intregi: N, i, j, v[N]
real: M
citeste N
M 0: j
pentru i 1 pana
citeste v[i]
daca v[i] mod 3 = 0 atunci
M M+v[i]
j j+1
sfarsit daca
sfarsit pentru
M M / j
tipareste M
Precizati care este actiunea acestui program.
a) Citeste un vector de N întregi si tipareste media aritmetica a elementelor divizibile cu 3.
b) Citeste un vector de N întregi si tipareste media aritmetica a elementelor sale.
c) Ordoneaza crescator elementele vectorului v[N].
d) Calculeaza suma elementelor vectorului v[N].
e) Citeste un vector de N întregi si tipareste media aritmetica a elementelor care nu sunt divizibile cu 3.
Raspuns: a
72. Fie urmatorul "program" în pseudocod:
intregi: N, i, v[N]
citeste N
pentru i 1 pana
citeste v[i]
v[i] v[i]+1
tipareste v[i]
sfarsit pentru
Precizati care este actiunea acestui program.
a) Citeste un vector de N întregi si tipareste elementele sale.
b) Citeste un vector de N întregi si tipareste maximul elementelor sale.
c) Citeste un vector de N întregi, creste valoarea elementelor sale cu o unitate si tipareste vectorul.
d) Calculeaza suma elementelor vectorului v[N].
e) Calculeaza produsul elementelor vectorului v[N].
Raspuns: c
73. Fie urmatorul "program" în pseudocod:
intregi: N, M, i, v[N]
citeste N
M
pentru i 1 pana
citeste v[i]
daca i mod 2 = 0 atunci
M M+v[i]
sfarsit daca
sfarsit pentru
tipareste M
Precizati care este actiunea acestui program.
a) Citeste un vector de N întregi si tipareste suma elementelor pare.
b) Citeste un vector de N întregi si tipareste suma elementelor impare.
c) Citeste un vector de N întregi si tipareste suma elementelor aflate pe pozitii pare.
d) Citeste un vector de N întregi si tipareste produsul elementelor aflate pe pozitii pare.
e) Calculeaza produsul elementelor vectorului v[N].
Raspuns: c
74. Fie urmatorul "program" în pseudocod:
intregi: N, M, i, v[N]
citeste N
M
pentru i 1 pana
citeste v[i]
daca v[i] mod 2 = 0 SI i mod 2 <> 0 atunci
M M * v[i]
sfarsit daca
sfarsit pentru
tipareste M
Precizati care este actiunea acestui program.
a) Citeste un vector de N întregi si tipareste minimul elementelor sale.
b) Citeste un vector de N întregi si tipareste maximul elementelor sale.
c) Citeste un vector de N întregi si tipareste produsul elementelor pare.
d) Citeste un vector de N întregi si tipareste suma elementelor impare.
e) Citeste un vector de N întregi si tipareste produsul elementelor pare aflate pe pozitii impare.
Raspuns: e
75. Fie urmatorul "program" în pseudocod:
intregi: N, M, i, v[N]
citeste N
M
pentru i 1 pana
citeste v[i]
daca v[i] mod 2 = 0 SI i mod 2 = 0 atunci
M M * v[i]
sfarsit daca
sfarsit pentru
tipareste M
Precizati care este actiunea acestui program.
a) Citeste un vector de N întregi si tipareste minimul elementelor sale.
b) Citeste un vector de N întregi si tipareste maximul elementelor sale.
c) Citeste un vector de N întregi si tipareste produsul elementelor pare aflate pe pozitii pare.
d) Citeste un vector de N întregi si tipareste suma elementelor impare.
e) Citeste un vector de N întregi si tipareste produsul elementelor pare aflate pe pozitii impare.
Raspuns: c
76. Fie urmatorul "program" în pseudocod:
intregi: N, M, i, v[N]
citeste N
pentru i 1 pana
citeste v[i]
sfarsit pentru
pentru i 2
pana
pentru j N pana la i cu pasul -1 executa
daca v[j-1]>v[j] atunci
M v[j-1]: v[j-1] v[j]: v[j] M
sfarsit daca
sfarsit pentru
sfarsit pentru
Precizati care este actiunea acestui program.
a) Citeste un vector de N întregi si tipareste minimul elementelor sale.
b) Citeste un vector de N întregi si tipareste maximul elementelor sale.
c) Citeste un vector de N întregi si tipareste produsul elementelor sale.
d) Citeste un vector de N întregi si tipareste suma elementelor sale.
e) Citeste un vector de N întregi si îl ordoneaza crescator prin interschimbare.
Raspuns: e
77. Fie urmatoarea secventa de pseudocod. Precizati actiunea ei.
reali: a,b,x
citeste a, b
daca a=0 atunci
daca b=0 atunci tipareste ("Ec. Nedet.")
altfel tipareste ("Ec. Imp.")
altfel
x -b/a
tipareste (x)
sfarsit daca.
a) rezolva o ecuatie de gradul I
b) rezolva o ecuatie de gradul II
c) rezolva o ecuatie diferentiala
d) calculeaza media aritmetica a numerelor a si b.
e) nici una dintre variantele anterioare.
Raspuns: a
78. Fie urmatoarea secventa de pseudocod:
intreg: a
a
a
tipareste a
tipareste a
Precizati ce va "tipari" aceasta secventa.
a) 6 7 b) 6 6 c) 7 7 d) 7 6 e) secventa este gresita.
Raspuns:
79. Care din urmatoarele afirmatii este gresita pentru metoda Backtracking?
a) Metoda Backtracking se foloseste la probleme care cauta o multime de solutii de forma unui n-uplu (x1,x2,.,xn) în care xi Mi, Mi - multimi finite.
b) Metoda Backtracking se foloseste la probleme care cer gasirea unei solutii (x1,x2,.,xn) care optimizeaza o functie criteriu.
c) n-uplelele (x1,x2,.,xn) care satisfac conditiile interne se numesc solutii posibile.
d) Conditiile interne stabilesc daca un element xi Mi este sau nu adaugat solutiei partial construite.
e) Conditiile de continuare stabilesc daca un element xi Mi este sau nu adaugat solutiei partial construite.
Raspuns: d
80. Care din urmatoarele afirmatii este gresita pentru metoda Backtracking?
a) Solutiile posibile care satisfac conditiile de continuare se numesc solutii rezultat.
b) Daca (x1,x2,.,xn) este o solutie, ea se construieste într-o stiva de înaltime n.
c) Metoda construieste toate combinatiile posibile si apoi selecteaza pe acelea care reprezinta solutii.
d) Metoda construieste solutia în mod progresiv prin adaugarea a câte unei componente xi la o solutie partial construita (x1,x2,.,xi-1).
e) Adaugarea unei componente xi la solutia partial construita (x1,x2,.,xi-1) se face numai daca (x1,x2,.,xi) satisface conditiile de continuare.
Raspuns: c
81. Se da problema celor n regine: "sa se plaseze n regine pe o tabla de sah cu n x n patrate, astfel încât sa nu se atace". Considerând ca liniile (i) si coloanele (x[i]) se numeroteaza de la 1 la n, care din urmatoarele expresii reprezinta conditiile de continuare pentru componenta k la rezolvarea prin metoda Backtracking?
a) x[k]!=x[i], "i=1..n.
b) x[k]!=x[i] && abs(x[k]-x[i])!=abs(k-i), "i=1..n
c) x[k]!=x[i] | | abs(x[k]-x[i])!=abs(k-i), "i=1..n
d) x[k]!=x[i] && x[k]-x[i]!=k-i, "i=1..n
e) k!=i && x[k]!=x[i], "i=1..n.
Raspuns: b
82. O solutie de forma (x1,x2,.,xn) este generata prin metoda Backtracking într-o stiva de înaltime n. Care din expresiile urmatoare poate reprezenta o conditie de tiparire a solutiei.
a) x[k]!=x[i];
b) k==i;
c) k==x[k];
d) k==n;
e) nici una dintre variantele anterioare.
Raspuns: d
83. Se considera urmatoarea procedura în pseudocod:
back(intreg: k)
pentru fiecare xk Mk executa
daca (x1,x2,.,xk) satisface cond. de continuare
daca k=n atunci tipar(x,n)
altfel back(k+1)
sfarsit daca
sfarsit daca
sfarsit pentru
sfarsit back;
Carei tehnici de programare îi este specifica aceasta procedura?
a) Greedy.
b) Backtracking recursiv.
c) Backtracking iterativ.
d) Divide et impera.
e) Nici una din variantele anterioare.
Raspuns: b
84. Backtracking elementar este denumirea data metodei atunci când:
a) se aplica unei probleme care implica o stiva având fiecare nivel format dintr-un singur element.
b) se aplica unei probleme care implica o stiva având fiecare nivel format din mai multe elemente.
c) se aplica unei probleme simple.
d) se aplica unei probleme ce implica recursivitate.
e) se aplica unei probleme ce implica rezolvare iterativa.
Raspuns: a
85. Backtracking generalizat este denumirea data metodei atunci când:
a) se aplica unei probleme care implica o stiva având fiecare nivel format dintr-un singur element.
b) se aplica unei probleme care implica o stiva având fiecare nivel format din mai multe elemente.
c) se aplica unei probleme generale.
d) se aplica unei probleme ce implica recursivitate.
e) se aplica unei probleme ce implica rezolvare iterativa.
Raspuns: b
86. Care din urmatoarele afirmatii este gresita pentru metoda Greedy?
a) Se mai numeste si metoda optimului local.
b) Se foloseste pentru probleme de optimizare.
c) Se mai numeste si metoda cautarii cu revenire.
d) Determina dintre solutiile posibile pe aceea care optimizeaza o functie obiectiv data.
e) Cauta o solutie optima.
Raspuns: c
87. Care din urmatoarele afirmatii este corecta pentru metoda Greedy?
a) Metoda se poate folosi pentru rezolvarea oricarei probleme, fiind foarte generala.
b) Elementele solutiei sunt alese într-o ordine oarecare fiind adaugate solutiei optime partial construite daca sunt îndeplinite conditiile de continuare.
c) Solutiile subproblemelor se combina pentru a gasi solutia întregii probleme.
d) Elementele solutiei sunt alese într-o ordine ce depinde de problema, folosind o functie de selectie.
e) Metoda construieste toate combinatiile posibile si apoi selecteaza pe acelea care reprezinta solutii.
Raspuns: d
88. Care din urmatoarele afirmatii este gresita pentru metoda Greedy?
a) La fiecare pas se cauta un optim local (se alege valoarea cea mai promitatoare).
b) Functia de selectie alege un element din multimea datelor A si îl sterge din A.
c) La fiecare pas se determina daca solutia partial construita împreuna cu elementul x ales din A da o solutie posibila.
d) Metoda determina toate solutiile posibile si apoi o alege pe cea optima.
e) Metoda încearca sa introduca direct un element x în solutia optima.
Raspuns: d
89. Care din urmatoarele afirmatii este gresita pentru metoda Greedy?
a) Fiind data o problema, exista totdeauna un algoritm de tip Greedy care gaseste solutia optima.
b) Algoritmul se termina, fie când a fost gasita solutia optima, fie când s-a constatat inexistenta acesteia.
c) Elementele solutiei sunt alese într-o ordine ce depinde de problema, folosind o functie de selectie.
d) La fiecare pas se determina daca solutia partial construita împreuna cu elementul x ales din A da o solutie posibila.
e) Tehnica Greedy se mai numeste si metoda optimului local.
Raspuns: a
90. Se da urmatoarea procedura în pseudocod:
procedura proc
intregi: n, i, A[n]
multime: sol
sol=
pentru i 1 pana la n
x=SELECT(A[n])
daca POSIBIL(sol, x) atunci sol=sol
sfarsit pentru
tipareste(sol)
Carei tehnici de programare îi este specifica aceasta procedura?
a) Backtracking iterativ.
b) Backtracking recursiv.
c) Greedy.
d) Divide et impera.
e) Branch and bound.
Raspuns: c
91. In cazul problemei continue a rucsacului functia de selectie va functiona astfel:
a) Va lua obiectele în ordinea crescatoare a utilitatii (valorii) lor.
b) Va lua obiectele în ordinea descrescatoare a utilitatii (valorii) lor.
c) Va lua obiectele în ordinea crescatoare a volumului lor.
d) Va lua obiectele în ordinea descrescatoare a volumului lor.
e) Va lua obiectele în ordinea descrescatoare a raportului dintre utilitate (valoare) si volum.
Raspuns: e
92. Se da urmatoarea procedura în pseudocod:
procedura proc(p,q)
intreg: m
daca MIC(p,q) atunci return G(p,q)
altfel
m DIVIDE(p,q)
return COMBINA(proc(p,m),proc(m+1,q))
sfarsit daca
Carei tehnici de programare îi este specifica aceasta procedura?
a) Backtracking iterativ.
b) Backtracking recursiv.
c) Greedy.
d) Divide et impera.
e) Branch and bound.
Raspuns: d
93. Care din urmatoarele afirmatii este corecta pentru metoda Divide et Impera?
a) Tehnica Divide et Impera presupune împartirea celor n date în k submultimi distincte care produc k subprobleme.
b) Tehnica Divide et Impera se mai numeste si metoda optimului local.
c) Tehnica Divide et Impera se mai numeste si metoda cautarii cu revenire.
d) Tehnica Divide et Impera se mai numeste si metoda Branch and Bound.
e) Tehnica Divide et Impera se aplica totdeauna la rezolvarea problemelor de divizibilitate.
Raspuns: a
94. Care din urmatoarele afirmatii este gresita pentru tehnica Divide et Impera?
a) Tehnica Divide et Impera presupune împartirea celor n date în k submultimi distincte care produc k subprobleme.
b) Daca subproblemele sunt înca mari si de aceeasi natura ele se pot rediviza.
c) Subproblemele cele mai mici se rezolva direct fara redivizare.
d) Solutiile subproblemelor se combina pentru a gasi solutia întregii probleme.
e) Fiecare solutie a fiecarei subprobleme este o solutie a întregii probleme.
Raspuns: e
95. Care din urmatoarele afirmatii este gresita pentru tehnica Divide et Impera?
a) Cel mai frecvent k=2 (problemele se împart în doua subprobleme, s.a.m.d.).
b) Functia MIC(p,q) din procedura recursiva asociata metodei Divide et Impera stabileste daca problema este suficient de mica pentru a fi rezolvata direct sau mai trebuie redivizata.
c) Functia MIC(p,q) din procedura recursiva asociata metodei Divide et Impera determina minimul dintre p si q.
d) Functia G(p,q) din procedura recursiva asociata metodei Divide et Impera rezolva direct subproblema fara redivizare.
e) Apelul recursiv al procedurii asociate metodei Divide et Impera se realizeaza prin functia care combina subsolutiile.
Raspuns: c
96. Care din urmatoarele afirmatii este gresita pentru tehnica Divide et Impera?
a) Daca marimile celor doua subprobleme sunt aproximativ egale, atunci timpul de calcul este descris de urmatoarea formula de recurenta:
b) g(n) este timpul necesar pentru rezolvarea directa a subproblemelor.
c) T(n) este timpul consumat de functie pentru rezolvarea întregii probleme.
d) f(n) este timpul consumat de functiile DIVIDE si COMBINA.
e) T(n/2) este timpul necesar rezolvarii a jumatate din problema.
Raspuns: e
97. Care din urmatoarele probleme nu are nimic în comun cu tehnica Divide et Impera?
a) Cautarea binara.
b) Sortarea prin interclasare.
c) Sortarea rapida (quick).
d) Sortarea prin numarare.
e) Problema turnurilor din Hanoi.
Raspuns: d
98. Se da urmatoarea secventa de pseudocod:
procedura proc(intreg: x)
intregi:i, s, m, ok, a[n]
i 1: s n: ok
cat timp i<s
m (i+s) / 2
daca x<a[m] atunci s m-1
altfel daca x>a[m] atunci i m+1
altfel
tipareste ("S-a gasit a[" + m + "]="+ x)
ok
sfarsit daca
sfarsit daca
repeta.
daca ok=0 tipareste ("Nu s-a gasit").
Care din urmatoarele probleme este implementata de acest algoritm?
a) Cautarea binara.
b) Sortarea prin interclasare.
c) Sortarea rapida (quick).
d) Sortarea prin numarare.
e) Problema turnurilor din Hanoi.
Raspuns: a
99. Se da urmatoarea descriere de algoritm: "se divide vectorul v[n] în subtablouri din ce în ce mai mici pâna când fiecare subtablou contine un singur element (deci sunt subtablouri ordonate); apoi se reunesc aceste subtablouri printr-o procedura care le pastreaza ordonate".
Care din urmatoarele probleme este implementata de acest algoritm?
a) Cautarea binara.
b) Sortarea prin interclasare.
c) Sortarea rapida (quick).
d) Sortarea prin numarare.
e) Problema turnurilor din Hanoi.
Raspuns: b
100. Care algoritm de sortare poate avea urmatoarea descriere: "se partitioneaza vectorul v[n] dupa elementul din mijloc x; se cauta în prima partitie elementele mai mari decât x si în a doua elementele mai mici decât x si se interschimba; operatia de partitionare, cautare si interschimbare se repeta pentru fiecare partitie, prin tehnica Divide et Impera".
a) sortarea prin interschimbare.
b) sortarea prin selectie.
c) quicksort.
d) sortarea prin interclasare.
e) sortarea prin insertie.
Raspuns: c
|
