Brainscape's Knowledge GenomeTM

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


See full index

PERSONAL (B2) > T3 - TAD (J) > Flashcards

T3 - TAD (J) 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.

PERSONAL (B2) (8 decks)

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