Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

TAI Private B2 > B2-T3 (Primera parte) TAD > Flashcards

B2-T3 (Primera parte) TAD Flashcards

1
Q

¿Que es un TAD?

A

Tipo Abstracto de Datos.Es una descripción teórica de una colección de datos y las operaciones que pueden realizarse sobre ellos.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

¿Que es una Estructura de datos?

A

Es una forma concreta de organizar y almacenar datos en la memoria de una computadora para que puedan ser usados de manera eficiente

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

¿Que es un Array (Arreglo)?

A

Contenedor de elementos de un mismo tipo almacenados en posiciones contiguas de memoria

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

¿Que es un Lista enlazada?

A

Estructura de datos compuesta de nodos donde cada nodo contiene un dato y una referencia (enlace) al siguiente nodo

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

¿Que es un Montículo (Heap)?

A

Estructura de árbol que satisface la propiedad de montículo (heap property). Donde el padre siempre es mayor o menor que sus hijos

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

¿Que es una Tabla hash?

A

Para mapear claves a posiciones en una tabla, permitiendo búsquedas, inserciones y eliminaciones eficientes.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

¿Que es un Árbol binario de búsqueda (BST)?

A

Árbol donde cada nodo tiene como máximo dos hijos y cumple con la propiedad de que el hijo izquierdo es menor y el derecho es mayor que el nodo.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

¿Que es un Grafo?

A

Representación de un conjunto de nodos (vértices) y las conexiones entre ellos (aristas).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

¿Que es una Pila (stack) ?

A

Colección de elementos con una política de acceso LIFO (Last In - First Out)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

¿Que es una Cola ?

A

colección de elementos con una política de acceso FIFO (First In - First Out)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

¿Que es Arrays Asociativos - Diccionario - Mapa?

A

Es una colección de pares clave-valor donde cada clave es única y está asociada a un valor.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Definición de tabla Hash

A

Es una estructura de datos que implementa un TAD, como un diccionario o un mapa, que puede almacenar pares de clave-valor y permite operaciones eficientes de búsqueda

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

¿Como se llaman los elementos en los que un hash guarda la información?

A

slots o buckets

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

¿Que es resolución de conflictos por encadenamiento en tablas hash?

A

Es una técnica utilizada para manejar colisiones que ocurren cuando dos o más elementos se asignan a la misma posición en una tabla hash.
En el encadenamiento- cada posición o índice de la tabla hash no almacena directamente un solo elemento, sino que apunta a una lista vinculada (o alguna otra estructura de datos como una lista dinámica) que contiene todos los elementos que han sido hash a esa misma posición.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

¿Que Técnicas existen para gestionar las colisiones?

A

Hashing Abierto y Hashing Cerrado

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

¿En que consiste la técnica de Hashing Abierto?

A

Cuando ocurre una colisión, el nuevo elemento se añade a la lista en la posición donde ha dado el conflicto

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

¿En que consiste la técnica de Hashing Cerrado?

A

cuando ocurre una colisión ,el nuevo elemento se coloca en otra posición de la tabla hash según una secuencia predefinida hasta encontrar una posición vacía.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

¿Como es el coste de una busqueda en tablas Hash?

A

constante

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

¿Cual es la complejidad en los monticulos para hacer insercción y borrados?

A

O(log(n))

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

¿Que es una cola de prioridad?

A

cada elemento en la cola tiene una prioridad asociada, y los elementos se extraen de la cola en orden de prioridad en lugar de en el orden en que se insertaron.

21
Q

Características de un árbol

A

-grafo acíclico
- conexo
-no dirigido

22
Q

¿Que es un en un árbol?

A

nodo que no tiene descendientes

23
Q

¿Que es Grado de un nodo en un árbol?

A

nº de descendientes directos de ese nodo

24
Q

¿Que es Nivel en un árbol?

A

número de ramas que hay que recorrer para llegar de la raíz a un nodo.

25
Q

¿Que es Altura de un nodo en un árbol?

A

Trayectoria más larga desde ese nodo a una hoja.

26
Q

¿Que es Anchura de un nodo en un árbol?

A

Es el mayor valor del número de nodos que hay en un nivel.

27
Q

¿Que es Factor de equilibrio (FE) de un nodo en un árbol?

A

Diferencia de altura entre subárbol izquierdo y derecho. Para un árbol AVL ,este valor debe ser -1 -0 o 1.

28
Q

¿Que es Orden Orden en un árbol?

A

Número máximo teórico de hijos que puede tener un nodo.

29
Q

¿Que es un árbol balanceado?

A

es una estructura de datos de árbol en la que la diferencia de altura entre los subárboles izquierdo y derecho de cualquier nodo no excede en más de una unidad

30
Q

¿Que es unÁrbol de recubrimiento mínimo?

A

es un subgrafo que conecta todos los nodos siguiendo un camino cuyo coste de la suma del valor de las aristas es mínimo

31
Q

¿Que es un Árbol Binario de búsqueda (ABB)?

A
  • los valores en el subárbol izquierdo de un nodo son menores que el valor del nodo.
  • Los valores en el subárbol derecho son mayores que el valor del nodo.
32
Q

¿Cual es el rendimiento en un rbol Binario de búsqueda (ABB)?

A

log(n)

33
Q

¿Que tipos de Árboles Equilibrados (auto-balanceable) conoces?

A
  • AA
  • rojo-negro
  • splay
  • árbol B
34
Q

¿Que es un árbol AVL?

A

árbol binario de búsqueda (ABB) autobalanceado

35
Q

¿Que es un Árbol B?

A

es una estructura de datos de árbol autoequilibrado en la que los nodos pueden tener más de dos hijos.

36
Q

¿Que complejidad tienen las insercciones y borrados en los árboles B?

A

log(n)

37
Q

¿Cuantas claves como mínimo tiene un arbol B?

A

m/2

38
Q

¿Que es un Árbol B+?

A
  • variante del árbol B
  • nodos intermedios solo contienen claves y punteros
  • nodos hojas están enlazados entre sí mediante una lista enlazada
39
Q

¿Que es un Árbol B*?

A

variación del árbol B
- mayor densidad de ocupación=Garantizan la densidad de ocupación (⅔ * t). t= grado mínimo del árbol.

40
Q

¿Que es un grafo dirigido o digrafo?

A

aquel en el que todas sus aristas tienen sentido o dirección

41
Q

¿Que es un grafo conexo?

A

Si es posible llegar desde cualquier nodo del grafo a cualquier otro nodo a través de una secuencia de aristas (conexiones) sin importar cuán larga sea esa secuencia.

42
Q

¿Que es un grafo Multigrafo?

A

Mas de una arista entre vertices

43
Q

¿Que es un grafo Completo?

A

es un grafo simple donde cada par de vértices está conectado por una arista.

44
Q

¿Que es un Un árbol recubridor mínimo?

A

subconjunto de las aristas que conecta todos los vértices sin ciclos y con el costo total más bajo posible.

45
Q

¿Que es el camino mínimo entre dos vértices en un grafo ponderado?

A

Se refiere a la ruta menor coste entre dos vértices específicos

46
Q

Listado de algoritmos sobre un árbol recubridor mínimo

A

PRIM - KRUSKAL

47
Q

Listado de algoritmos sobre un árbol camino mas corto

A

-DIJKSTRA
- BELLMAN-FORD
- JOHNSON
- FLOYD-WARSHALL
- Algoritmo A*

48
Q

¿Para que vale el algoritmo FORD-FULKERSON?

A

encontrar el flujo máximo en una red de flujo

49
Q

¿Para que vale el algoritmo VITERBI?

A

hallar la secuencia más probable de estados ocultos

TAI Private B2 (8 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions