rolisz's site

Subiect SDA

2012, doamna profesor Gabriela Czibula.

Prima lucrare a se­mes­tru­lui 2 :D/ It was kinda easy, doar că nu am mai prea lucrat pe tablouri, așa că sper că am făcut bine problema.

Enunț: TAD Mulțime - operația ștergere. Im­ple­mentare pe listă liniară dublu înlănțuită cu alocare statică pe tablou. Cerințe: 1) Speci­fi­care operației 2) Descrierea SD 3) Alegerea reprezen­tării 4) Im­ple­mentare 5) Com­plex­i­tatea operației

Rezolvare: [gview file="/static/images/2012/04/sda2.pdf"]

Andrei a pus o rezolvare la primul subiect pe siteul lui. Thanks! Mersi Istvan și Robi!

R9.

1. Scrieți un sub­al­go­ritm care să aibă timpul de execuție dat de următoarea recurență. Deduceți com­plex­i­tatea.

$ T(n) = be­gin{­cas­es} 0 & text{ daca } n=1 \ 4T(n/2) + O(n^2) & text{ altfel } end{cases} $ 2. Răspundeți la ur­mă­toarele cerințe:

2.1. Fie TD cu coliziuni rezolvate prin liste în­tre­pătrunse cu 13 locații, funcția de dispersie prin diviziune, rezultată în urma inserării cheilor 18, 31, 29, 28 26, 44, 39. Arătați tabela rezultată în urma ștergerii cheii 18. Gestiunea spațiului liber se face de la stânga la dreapta (de la 0 spre 12).

2.2 În ansamblul de mai jos construit cu relația $ \leq $, se aplică de două ori operația de ștergere. Indicați ansamblul rezultat (scrieți și pasul in­ter­me­di­ar după prima ștergere).

2.3 Ilustrați pe un exemplu concret operația de dublă rotație spre dreapta într-un arbore AVL.

3. Răspundeți la ur­mă­toarele întrebări, jus­ti­ficând rezultatul (rezul­tatele) ales (alese). 3.1 Un vector $ x_1, ... , x_n $ de numere întregi cuprinse în intervalul $ [10, 2000] $ pot fi sortate cresctător folosind BucketSort în:

a) O(n) b) $ \theta (n) $ c) $ \theta(n^2) $

3.2 În im­ple­mentarea Stivei folosind o listă înlănțuită, ce operații necesită timp liniar în cazul de­fa­vor­a­bil?

a) vidă b) accesare (operația element) c) ștergere d) adăugare e) nici una din operațiile anterioare

3.3 Care este valoarea următoare expresii în forma postfixată 6 3 2 4 + - *: a) o valoare între -15 și -100 b) o valoare între -5 și -15 c) o valoare între 5 și -5 d) o valoare între 5 și 15 e) o valoare între 15 și 100

3.4 Fie arborele de mai jos.

Care este preordinea arborelui?

a) 1 2 3 7 10 11 14 30 40 b) 1 2 3 14 7 10 11 40 30 c) 1 3 2 7 10 40 30 11 14 d) 14 2 1 3 11 10 7 30 40

3.5 Având un arbore binar de căutare cu n elemente, elementele acestuia se pot afișa în ordine crescă­toare în $ \theta(n) $

a) adevărat b) false

3.6 O TD cu coliziuni rezolvate prin liste în­tre­pătrunse are 512 locații. Care este numărul maxim de intrări care pot fi în tabelă?

a) 256 b) 511 c) 512 d) 1024 e) oricât

4. Să se trans­lateze o expresie aritmetică cu paranteze corectă din forma infixată în forma postifxată. Operanzii sunt numere întregi de la 0 la 9. Operatorii sunt binari: +, -, *, /,. Ex: (1+2)*3 => 1 2 + 3 *

5. Scrieți operația de dublă rotație spre stânga pentru re­echili­brare într-un Arbore Binar de Căutare. Arborele se reprezintă prin înlănțuire dinamică a nodurilor. Descrieți în Pseudocod sub­al­go­rit­mul. Precizați com­plex­i­tate operației.

Timpul a fost de 2 ore și 50 minute.

[gview file="/static/images/2012/06/subiect.pdf"]

Wow. Much harder decât ce am primit eu :-S