Preguntas Parcial Y Final Flashcards
La cursada fue hecha con Moscuzza
¿Para qué sirven los grafos?
Los grafos sirven para modernizar matemáticamente una estructura de datos.
Desarrolle el concepto de Grafo, utilización de tipos y representación computacional de los mismos.
Es una pareja G=(V,A), donde V es un conjunto de vértices (o nodos) y A es un conjunto de pares que une dichos vértices, llamadas aristas. Sirve para establecer relaciones. Pueden mantener o no jerarquía entre sí, y en caso de hacerlo, dicha jerarquía se representa poniendo un sentido al arco.
Los grafos pueden ser dirigidos o no dirigidos, y pueden ser restrictos o irrestrictos.
La representación computacional se puede dar por estructuras estáticas como dinámicas. Entre las estáticas se encuentran la matriz de adyacencia, y la matriz de incidencia. Entre las dinámicas se pueden representar por Listas, como PFlatz, Siklosy, o listas de adyacencias. La estructura estática es menos conveniente en casi todos los casos, porque ocupa más espacio (O(V2))y no es flexible para el crecimiento del grafo, pero tiene menos costo computacional. La estructura dinámica es más conveniente debido a que ocupa menos espacio (O(V+A)), pero tiene un costo computacional mayor.
Definición de maximal.
Conjunto de nodos desde los cuales no parte ningún arco hacia otro lado (los bucles no se tienen en cuenta).
Definición de minimal.
Conjunto de nodos desdes los cuales no llega ningún arco proveniente de otro
nodo (los bucles no se tienen en cuenta).
Definición de grafo restricto.
Son aquellos grafos los cuales solo pueden modelizar relaciones que no cumplan con las propiedades de reflexión, simetría y transitividad.
Definición de grafo irrestricto. Cómo se representa computacionalmente
Son aquellos grafos los cuales pueden modelizar relaciones sin importar si cumplen o no ciertas propiedades.
Para representarlo computacionalmente existen dos formas: una dinámica y otra estática.
En el caso de la dinámica, se puede crear una lista por cada nodo que indique las relaciones que tiene con los otros nodos. En el caso de la estática, se puede crear una matriz (vector de dos dimensiones) que almacene con un bit las relaciones entre los nodos.
Definición de grafo completo.
Grafo en el cual para cada par de nodos existe un arco que los une.
Tipos de representación computacional. Ventajas y desventajas.
Representación estática: matriz de adyacencia o matriz de incidencia.
Representación dinámica: listas enlazadas o representación de Pfaltz. Las listas enlazadas convienen para grafos dispersos.
Representación estática
Ventajas
Permite un acceso más fácil de forma directa por posición.
Desventajas
~ Puede llegar a ocupar espacio innecesario.
~ No permite guardar atributos.
Representación dinámica
Ventajas
~ Solo se ocupa el espacio necesario.
Desventajas
~ Para acceder a los datos hay que recorrer toda la lista.
Condiciones que tiene que cumplir un grafo para ser un arbol.
Un grafo G (P,E) es un árbol si cumple con las siguientes propiedades:
1) ACICLICO: El grafo no tiene ciclos
2) |P| = |E| + 1
3) Para todo a perteneciente a E => a es desconectante
4) Para todo x,y pertenecientes a P => Existe un walk único (x,y)
Un nodo solo puede ser un árbol.
VOF? Grafos / Árboles – Un grafo que posee un solo nodo siempre es un árbol.
Verdadera, porque cumple las 4 condiciones.
Definición de árbol completo.
Un árbol es completo cuando todos sus nodos no maximales (nodos
que no son hojas) tienen igual grado de salida.
Tipos de barridos.
Preorden (raíz - subárbol izq - der).
Simétrico (izq - raíz - der).
Postorden (izq - der - raíz).
Espacio desperdiciado de un árbol r-ario.
Para calcular el espacio desperdiciado se utiliza:
(r-1) * | P | + 1
Donde r = Grado del árbol y | P | = N° de nodos.
¿Para qué se utiliza la transformada de Knuth?
Se utiliza para transformar árboles r-arios en árboles binarios.
VOF? Knuth – Si un árbol n-ario tiene 2 niveles, entonces la profundidad máxima que puede alcanzar un nodo en la trasformada de Knuth es n.
Para mi falsa porque la profundidad puede ser mayor, por ejemplo en la carpeta yo tenia un arbol de grado 4 y que un nodo tiene una profundidad de 6, profundidad es la cantidad de arcos que hay de distancia entre la raiz y un cierto nodo.
VOF? Knuth: El barrido de pre orden del árbol r-ario original coincide con el pre orden del binario.
V
Definición de árbol balanceado.
Árbol que para todo nodo se cumple que la Cardinalidad del
subárbol izquierdo es igual a la Cardinalidad del subárbol derecho o difiere en 1.
Todo arbol balanceado es AVL. No todo árbol AVL es balanceado.
Definición de árbol AVL.
Arbol que para todo nodo se cumple que el nivel del subárbol izquierdo es
igual al nivel del subárbol derecho o difiere en 1.
Todo arbol balanceado es AVL. No todo árbol AVL es balanceado.
¿Para qué se utiliza la rotación y qué garantiza?
La rotación de arboles se utiliza para balancear un árbol en un punto critico determinado.
La rotación garantiza que el barrido simétrico del árbol rotado sea igual al barrido
simétrico del árbol original desbalanceado.
VOF? El barrido de pre orden se puede hacer en todo tipo de árboles pero el simétrico es solo para árboles binarios.
V. El barrido simétrico consiste en recorrer el árbol de la siguiente forma:
- Visitar el subárbol izquierdo.
- Informar la raíz.
- Visitar el subárbol derecho.
Conceptualmente que exista un nodo hijo izquierdo y derecho se produce porque el grado de todos los nodos es 2. Por lo tanto se trata de árboles binarios.
VOF? Un grafo que posee n nodos y ( n - 1 ) arcos siempre es un árbol.
es falso pero porque ademas de esta condicion se tienen que cumplir otras mas:
- arbol aciclico
- todo arco es desconectante
- existe walk unico para todo x, y (camino sin direccion entre x e y)
- sumatoria de nodos = sumatoria de arcos + 1
VOF? Arbol B- Al dar de alta una nueva clave, solo puede producirse un slip.
Falso. Solo hay slip si no hay punteros disponibles.
VOF? Arbol B- si el load factor es de 100% y la altura del árbol es mayor a 1, todas las hojas tienen la mitad de los punteros ocupados.
V
Explique en no más de 10 reglones la diferencia entre árbol completo y árbol lleno.
Un árbol completo es una estructura de datos cuyos nodos no maximales tienen el mismo grado de salida. Ej: O / \ O O / \ O O En cambio un árbol lleno es una estructura de datos en la que sus nodos maximales se encuentran en el mismo nivel. Es un caso particular de árbol completo. Ej: O / \ O O / \ / \ O O O O