Quin ordre d'accés utilitza una cua i quins costos solen tenir les seves operacions?

FIFO: s'afegeix pel final i s'extreu pel principi. Amb enllaços als dos extrems o un buffer circular de capacitat fixa, totes dues operacions costen O(1); desplaçar un vector fa que extreure costi O(n).

Ordena aquests creixements de menor a major quan n → ∞: n!, n, 1, n², log n, 2ⁿ, n log n.

Asimptòticament: 1 < log n < n < n log n < n² < 2ⁿ < n!.

Per què una llista doblement enllaçada pot eliminar un node donat en O(1)?

Els enllaços anterior i següent permeten reconnectar directament els veïns. Cal actualitzar el cap i la cua quan pertoqui; no cal buscar el predecessor.

Què és el factor de càrrega d'una taula de dispersió i per què es pot redimensionar?

α = n/m: n entrades i m cubetes o posicions. Superar el llindar de la implementació pot provocar una ampliació i una nova dispersió de les entrades; 0,75 no és universal.

Quines regles de color mantenen equilibrat un BST roig-negre?

Els nodes són roigs o negres; l'arrel i les fulles NIL són negres. Cap node roig té fills roigs. Tots els camins d'un node a una fulla NIL descendent tenen el mateix nombre de nodes negres. Això fita l'alçada a O(log n).

Quines dues propietats defineixen un monticle binari de mínims?

És un arbre binari complet i la clau de cada pare no supera les dels seus fills. Per tant, l'arrel conté un mínim.

Com visita un arbre binari el recorregut per nivells?

Utilitza una cua FIFO per visitar un nivell de profunditat cada vegada. Encola el fill esquerre abans que el dret per obtenir l'ordre d'esquerra a dreta.

On són el pare i els fills del node i en un vector de monticle de longitud n indexat des de zero?

Pare: ⌊(i−1)/2⌋ si i>0. Fills: 2i+1 i 2i+2, només si aquests índexs són menors que n. L'índex 0 no té pare.

Com depenen de l'alçada h la cerca, la inserció i l'eliminació en un BST?

Costen O(h). Un arbre equilibrat té h = O(log n); una cadena, h = O(n). El cost esperat O(log n) requereix hipòtesis com un ordre d'inserció aleatori.

En què es diferencien la compressió de camins, la unió per rang i la unió per mida?

La compressió redirigeix els nodes visitats a l'arrel. Per rang, l'arrel de rang menor queda sota la de rang major; per mida, el conjunt menor queda sota el major. El rang no ha de coincidir amb l'alçada actual.

En què es diferencien O, Ω i Θ?

Donen fites asimptòtiques superior, inferior i ajustada, respectivament. Descriuen una funció de cost concreta; O no significa per si sola «pitjor cas».

Què fan find i union en una estructura de conjunts disjunts?

find(x) retorna el representant del conjunt de x. union(x,y) fusiona els conjunts si són diferents; si ja són el mateix, la partició no canvia.

Com resol les col·lisions l'encadenament separat en una taula de dispersió?

Cada cubeta conté una col·lecció d'entrades amb aquell índex, sovint una llista enllaçada. Les claus diferents que comparteixen cubeta continuen sent entrades separades.

Quant costa construir un monticle de baix a dalt a partir de n elements?

O(n). La majoria de nodes són prop de les fulles i requereixen pocs descensos; sumar el treball segons l'alçada del node dona un total lineal.

Què és un trie i quan costa O(L) cercar-hi una clau de L caràcters?

És un arbre de prefixos que desa claus en camins de caràcters, amb marques de clau completa. La cerca costa O(L) si cada transició al caràcter següent costa O(1).

Com es corregeix un desequilibri esquerra-dreta causat per una inserció AVL?

Primer es rota el fill esquerre cap a l'esquerra; després, el node desequilibrat cap a la dreta.

Quin invariant d'ordre defineix un arbre binari de cerca (BST) amb claus diferents?

A cada node, totes les claus del subarbre esquerre són menors i totes les del dret són majors. La regla s'aplica recursivament.

En què es diferencien el sondeig lineal i el quadràtic en l'adreçament obert?

Les entrades romanen al vector. Amb mida m i índex inicial h, es proven (h+i) mod m i (h+c₁i+c₂i²) mod m, respectivament. El sondeig quadràtic requereix paràmetres adequats.

Com evita una cua circular en un vector desplaçar elements després d'extreure'n un?

Els índexs inicial i final avancen mòdul la capacitat. L'extracció avança l'índex inicial i permet reutilitzar posicions lliures sense moure els altres elements.

Per a funcions no negatives f i g, què significa f(n) ∈ O(g(n))?

Hi ha constants c > 0 i n₀ ≥ 0 tals que f(n) ≤ c·g(n) per a tot n ≥ n₀.

Quins són els costos esperats i de pitjor cas en una taula de dispersió amb encadenament separat?

Amb càrrega fitada, bona dispersió i operacions sobre claus de cost constant, cercar i eliminar tenen cost esperat O(1). Amb creixement geomètric, inserir té cost amortitzat esperat O(1). Una cadena de n claus en col·lisió pot causar O(n).

Per què l'accés per índex en un vector de mida fixa costa O(1)?

Les posicions, de la mateixa mida, són contigües: adreça(i) = base + i·mida_posició. Se suposa que calcular adreces costa temps constant.

Quant costen inserir, eliminar l'arrel i consultar l'arrel en un monticle binari?

O(log n), O(log n) i O(1), respectivament, si no cal redimensionar el vector. Redimensionar-lo pot costar O(n).

Si la capacitat es duplica, quin cost amortitzat té afegir al final d'un vector dinàmic?

O(1) per inserció. Redimensionar pot costar O(n), però n insercions al final des d'un vector buit costen O(n) en total.

Quines respostes pot donar un filtre de Bloom que només admet insercions?

Un resultat negatiu indica que l'element no s'ha inserit; un de positiu, que potser sí. Les funcions de dispersió activen bits d'un vector: pot haver-hi falsos positius, però no falsos negatius si l'estat és intacte.

Què produeix el recorregut en inordre d'un BST amb claus diferents?

Totes les claus en ordre estrictament creixent, visitant n nodes en O(n).

Quines propietats ha de tenir una funció de dispersió per cercar en una taula?

Ha de ser determinista i distribuir bé les claus esperades. Calcular la dispersió de claus de mida fixa pot costar O(1); la d'una cadena nova de L caràcters sol costar O(L).

Quin cost amortitzat té union/find amb compressió de camins i unió per rang?

O(α(n)) per operació, on α és la inversa d'Ackermann i n el nombre d'elements. Inicialitzar costa O(n); la fita concerneix una seqüència, no un cost constant de pitjor cas per a cada crida.

Compara la inserció al principi i l'accés per índex en una llista simplement enllaçada i un vector dinàmic.

Llista: inserció inicial O(1), accés per índex O(n). Vector: inserció inicial O(n), accés per índex O(1); inserir al principi desplaça elements.

Quins són els ordres dels recorreguts en preordre, inordre i postordre d'un arbre binari?

Preordre: node → esquerra → dreta. Inordre: esquerra → node → dreta. Postordre: esquerra → dreta → node.

Quina és la condició d'equilibri AVL?

A cada node, alçada(esquerra) − alçada(dreta) ∈ {−1, 0, 1}. L'arbre també compleix l'invariant d'ordre d'un BST.

Com funciona una pila i quan costen O(1) les seves operacions?

LIFO: l'últim element inserit surt primer. Al cap d'una llista enllaçada, inserir, extreure i consultar costen O(1); redimensionar un vector pot fer que una inserció costi O(n).

Estructures de Dades, Anàlisi de Complexitat (Big-O) i Algorismes Clau

Repàs universitari que requereix programació bàsica: 32 targetes sobre vectors, llistes, dispersió, arbres, monticles, tries, Union–Find, filtres de Bloom i complexitat.

Level: basic
Languages: ca → ca
Cards: 32
Markdown: Estructures de Dades, Anàlisi de Complexitat (Big-O) i Algorismes Clau (.md)

Flashcards (32)

#	Front (Term / Question)	Back (Definition / Answer)
1	Quin ordre d'accés utilitza una cua i quins costos solen tenir les seves operacions?	FIFO: s'afegeix pel final i s'extreu pel principi. Amb enllaços als dos extrems o un buffer circular de capacitat fixa, totes dues operacions costen O(1); desplaçar un vector fa que extreure costi O(n).
2	Ordena aquests creixements de menor a major quan n → ∞: n!, n, 1, n², log n, 2ⁿ, n log n.	Asimptòticament: 1 < log n < n < n log n < n² < 2ⁿ < n!.
3	Per què una llista doblement enllaçada pot eliminar un node donat en O(1)?	Els enllaços anterior i següent permeten reconnectar directament els veïns. Cal actualitzar el cap i la cua quan pertoqui; no cal buscar el predecessor.
4	Què és el factor de càrrega d'una taula de dispersió i per què es pot redimensionar?	α = n/m: n entrades i m cubetes o posicions. Superar el llindar de la implementació pot provocar una ampliació i una nova dispersió de les entrades; 0,75 no és universal.
5	Quines regles de color mantenen equilibrat un BST roig-negre?	Els nodes són roigs o negres; l'arrel i les fulles NIL són negres. Cap node roig té fills roigs. Tots els camins d'un node a una fulla NIL descendent tenen el mateix nombre de nodes negres. Això fita l'alçada a O(log n).
6	Quines dues propietats defineixen un monticle binari de mínims?	És un arbre binari complet i la clau de cada pare no supera les dels seus fills. Per tant, l'arrel conté un mínim.
7	Com visita un arbre binari el recorregut per nivells?	Utilitza una cua FIFO per visitar un nivell de profunditat cada vegada. Encola el fill esquerre abans que el dret per obtenir l'ordre d'esquerra a dreta.
8	On són el pare i els fills del node i en un vector de monticle de longitud n indexat des de zero?	Pare: ⌊(i−1)/2⌋ si i>0. Fills: 2i+1 i 2i+2, només si aquests índexs són menors que n. L'índex 0 no té pare.
9	Com depenen de l'alçada h la cerca, la inserció i l'eliminació en un BST?	Costen O(h). Un arbre equilibrat té h = O(log n); una cadena, h = O(n). El cost esperat O(log n) requereix hipòtesis com un ordre d'inserció aleatori.
10	En què es diferencien la compressió de camins, la unió per rang i la unió per mida?	La compressió redirigeix els nodes visitats a l'arrel. Per rang, l'arrel de rang menor queda sota la de rang major; per mida, el conjunt menor queda sota el major. El rang no ha de coincidir amb l'alçada actual.
11	En què es diferencien O, Ω i Θ?	Donen fites asimptòtiques superior, inferior i ajustada, respectivament. Descriuen una funció de cost concreta; O no significa per si sola «pitjor cas».
12	Què fan find i union en una estructura de conjunts disjunts?	find(x) retorna el representant del conjunt de x. union(x,y) fusiona els conjunts si són diferents; si ja són el mateix, la partició no canvia.
13	Com resol les col·lisions l'encadenament separat en una taula de dispersió?	Cada cubeta conté una col·lecció d'entrades amb aquell índex, sovint una llista enllaçada. Les claus diferents que comparteixen cubeta continuen sent entrades separades.
14	Quant costa construir un monticle de baix a dalt a partir de n elements?	O(n). La majoria de nodes són prop de les fulles i requereixen pocs descensos; sumar el treball segons l'alçada del node dona un total lineal.
15	Què és un trie i quan costa O(L) cercar-hi una clau de L caràcters?	És un arbre de prefixos que desa claus en camins de caràcters, amb marques de clau completa. La cerca costa O(L) si cada transició al caràcter següent costa O(1).
16	Com es corregeix un desequilibri esquerra-dreta causat per una inserció AVL?	Primer es rota el fill esquerre cap a l'esquerra; després, el node desequilibrat cap a la dreta.
17	Quin invariant d'ordre defineix un arbre binari de cerca (BST) amb claus diferents?	A cada node, totes les claus del subarbre esquerre són menors i totes les del dret són majors. La regla s'aplica recursivament.
18	En què es diferencien el sondeig lineal i el quadràtic en l'adreçament obert?	Les entrades romanen al vector. Amb mida m i índex inicial h, es proven (h+i) mod m i (h+c₁i+c₂i²) mod m, respectivament. El sondeig quadràtic requereix paràmetres adequats.
19	Com evita una cua circular en un vector desplaçar elements després d'extreure'n un?	Els índexs inicial i final avancen mòdul la capacitat. L'extracció avança l'índex inicial i permet reutilitzar posicions lliures sense moure els altres elements.
20	Per a funcions no negatives f i g, què significa f(n) ∈ O(g(n))?	Hi ha constants c > 0 i n₀ ≥ 0 tals que f(n) ≤ c·g(n) per a tot n ≥ n₀.
21	Quins són els costos esperats i de pitjor cas en una taula de dispersió amb encadenament separat?	Amb càrrega fitada, bona dispersió i operacions sobre claus de cost constant, cercar i eliminar tenen cost esperat O(1). Amb creixement geomètric, inserir té cost amortitzat esperat O(1). Una cadena de n claus en col·lisió pot causar O(n).
22	Per què l'accés per índex en un vector de mida fixa costa O(1)?	Les posicions, de la mateixa mida, són contigües: adreça(i) = base + i·mida_posició. Se suposa que calcular adreces costa temps constant.
23	Quant costen inserir, eliminar l'arrel i consultar l'arrel en un monticle binari?	O(log n), O(log n) i O(1), respectivament, si no cal redimensionar el vector. Redimensionar-lo pot costar O(n).
24	Si la capacitat es duplica, quin cost amortitzat té afegir al final d'un vector dinàmic?	O(1) per inserció. Redimensionar pot costar O(n), però n insercions al final des d'un vector buit costen O(n) en total.
25	Quines respostes pot donar un filtre de Bloom que només admet insercions?	Un resultat negatiu indica que l'element no s'ha inserit; un de positiu, que potser sí. Les funcions de dispersió activen bits d'un vector: pot haver-hi falsos positius, però no falsos negatius si l'estat és intacte.
26	Què produeix el recorregut en inordre d'un BST amb claus diferents?	Totes les claus en ordre estrictament creixent, visitant n nodes en O(n).
27	Quines propietats ha de tenir una funció de dispersió per cercar en una taula?	Ha de ser determinista i distribuir bé les claus esperades. Calcular la dispersió de claus de mida fixa pot costar O(1); la d'una cadena nova de L caràcters sol costar O(L).
28	Quin cost amortitzat té union/find amb compressió de camins i unió per rang?	O(α(n)) per operació, on α és la inversa d'Ackermann i n el nombre d'elements. Inicialitzar costa O(n); la fita concerneix una seqüència, no un cost constant de pitjor cas per a cada crida.
29	Compara la inserció al principi i l'accés per índex en una llista simplement enllaçada i un vector dinàmic.	Llista: inserció inicial O(1), accés per índex O(n). Vector: inserció inicial O(n), accés per índex O(1); inserir al principi desplaça elements.
30	Quins són els ordres dels recorreguts en preordre, inordre i postordre d'un arbre binari?	Preordre: node → esquerra → dreta. Inordre: esquerra → node → dreta. Postordre: esquerra → dreta → node.
31	Quina és la condició d'equilibri AVL?	A cada node, alçada(esquerra) − alçada(dreta) ∈ {−1, 0, 1}. L'arbre també compleix l'invariant d'ordre d'un BST.
32	Com funciona una pila i quan costen O(1) les seves operacions?	LIFO: l'últim element inserit surt primer. Al cap d'una llista enllaçada, inserir, extreure i consultar costen O(1); redimensionar un vector pot fer que una inserció costi O(n).