QUIZ AED EXAMENES

Comparar la implementación de la estructura interna de los árboles AVL y los árboles binarios ordinarios, los árboles B y B +. Ventajas de árboles B frente AVL.

Montículos. Organización de los datos y ejemplo de aplicación.

Recorrido en anchura de un grafo.

Ventajas y desventajas de usar lista de adyacencia o matriz de adyacencia.

Grafo dirigido. ¿Cómo saber si hay un camino entre CADA par de vértices?

Grafo dirigido. Cómo saber el camino mínimo entre cada par de vértices?

Grafo dirigido. ¿Cómo saber puntos críticos del grafo?

Tablas hash. ¿Qué es una colisión? Explicar la recolocación cuadrática.

Ramificación y poda. Estrategia de minimización de costes.

Decide las estructuras de datos más apropiadas (pilas, colas, listas, árboles, grafos) para simular los procesos que sigue un buscador de Internet para recopilar e indexar información de la web, y organizar la información para poder calcular el grado de autoridad de los sitios web.

Los buscadores de Internet, tipo Google, utilizan unos programas llamados robots web que se encargan de explorar la web recopilando datos de cada sitio web y navegando por los enlaces (links) que encuentran en cada página web. Cada cierto tiempo, los robots envían la información (contenidos de páginas web y enlaces con otras páginas) a un repositorio de datos que se encarga de organizar e indexar de forma óptima dicha información. Posteriormente, hay que aplicar un algoritmo de ránking que permita calcular el grado de importancia de cada sitio web. Estos algoritmos se basan en el concepto de autoridad, cada sitio web tiene el valor de autoridad que determina el número de sitios web que interactúan con él.

En concreto, define y justifica la elección de las estructuras de datos más empleadas para representar:

1. La información de los sitios web encontrados por los robots. Esta información tiene que guardarse temporalmente en memoria de la forma más eficiente teniendo en cuenta que los robots están enviando continuamente nuevas páginas que se van procesando para organizarlas e indexarlas.

2. La indexación de las páginas web. Hay que indexar los sitios web por orden alfabético de tal forma que la búsqueda de los mismos sea lo más rápida posible. Hay que seleccionar una estructura de datos para crear este indexador de tal forma que se permita la instrucción de sitios web nuevos conservando el orden alfabético y, si ya existen, actualizar el número de visitas que nuestro robot haya realizado.

3. Los enlaces entre los sitios web. Los robots almacenan los enlaces que salen de cada sitio web en un fichero. Decide cuál es la estructura más apropiada para guardar esta información de forma que permita poder calcular la autoridad de cada sitio web de forma sencilla.

Explica las ventajas y desventajas en cuanto a eficiencia (tiempo, espacio dealmacenamiento) en las operaciones de inserción, búsqueda y ordenación cuando se usa una tabla hash, un vector o una lista enlazada para almacenar un número dado de datos N. Indica qué diferencia habría entre usar una tabla hash con recolocación y una tabla hash con encadenamiento.

Explica el proceso de exploración del espacio de soluciones en la estrategia de ramificación y poda en un problema de optimización en el que el método utilizado para definir la solución óptima es la minimización del coste.

Algoritmo de Dijkstra

Dado el esquema general de un algoritmo voraz. Indica qué representan las siguientes variables o funciones:

C: S: x:

Solución(S): Seleccionar(C): Factible(S,x): Insertar(S,x): Objetivo(S):

Aplicar algoritmo de Prim/Kruskal

Relacionar pasos del algoritmo de Kruskal con las funciones de un algoritmo voraz genérico Solución(S), insertar(S,x), factible(S,x)...

Observa el siguiente grafo de conexiones entre todas la islas de la provincia de Tenerife. Para cada conexión (que puede ser de dirección única), además de saber la isla de origen y la isla destino, se conoce el coste del viaje

La estructura interna de un grafo puede representarse de dos formas, mediante estructuras estáticas o mediante estructuras dinámicas. Indica en este caso cuál de las dos usarías y explica por qué.
Para cada par de islas se desea saber cuál es el camino de coste mínimo que las une (siempre que exista alguno). Indica qué algoritmo usarías.
En caso de que todos los arcos fueran bidireccionales, indica qué buscarías para encontrar los puntos de la red que, si fallan, producen un fallo general de la red de comunicaciones.
En caso de que todos los arcos fueran bidireccionales, ¿cómo podríamos saber si podemos eliminar alguna de las conexiones minimizando el coste? ¿Qué algoritmo aplicarías?

{"name":"QUIZ AED EXAMENES", "url":"https://www.quiz-maker.com/QPREVIEW","txt":"Comparar la implementación de la estructura interna de los árboles AVL y los árboles binarios ordinarios, los árboles B y B +. Ventajas de árboles B frente AVL., Montículos. Organización de los datos y ejemplo de aplicación., Recorrido en anchura de un grafo.","img":"https://www.quiz-maker.com/3012/images/ogquiz.png"}