Programacion orientada a objetos y estructuras de datos

ASIGNATURA: PROGRAMACION ORIENTADA A OBJETOS Y ESTRUCTURAS DE DATOS
PROFESORA: LORETO YÁNEZ ROJAS
Alumno: René Salas
TALLER Nº2

EJERCICIO 1

1. Cual de las operaciones sobre TDA Grafo es incorrecta:
a) recorrer(grafo,tipoRecorrido), borrarArista(grafo,arista) y
borrarVertice(grafo,
referenciaVertice)
b) crearGrafo (grafo),
insertarArista(grafo, vertice1, vertice2)c)
insertarVertice(grafo, vertice), crearGrafo (grafo),
insertarArista(grafo, vertice1, vertice2)
d) recorrerpostorder(grafo,vertice) y recorrerinorder(grafo,vertice)
e) borrarArista(grafo,arista) y insertarArista(grafo, vertice1, vertice2)

2. Un árbol tal que, para cada nodo, el número de nodos del subárbol izquierdo y el
número de nodos del subárbol derecho difieren comomáximo en una unidad, entra
dentro de la(s) siguiente(s) clase(s) de los árboles:

a) Binarios de búsqueda
b) Binarios de búsqueda perfectamente equilibrados.
c) AVL.
d) Árboles n-arios
e) Árboles no balanceados

3. Indique cuáles de las siguientes afirmaciones son correctas respecto de los árboles
AVL:

a) El factor de equilibrio debe recalcularse en todoslos nodos ascendentes a aquél en que se inserta o se borra.
b) Al insertar un nodo en la rama izquierda de otro nodo que tenía factor de equilibrio –1 antes de insertar, y tras reequilibrar el árbol, no es necesario seguir propagando la variación del factor de equilibrio.
c) Al insertar en un árbol AVL no vacío, hay que actualizar el factor de equilibrio sólo del nodo que se convierte enpadre, sin necesidad de propagar la variación más arriba en el árbol.
d) Tras borrar un nodo en un árbol AVL no vacío y producir un desequilibrio, éste se soluciona tras aplicar una sola operación de rotación, simple (D-D o I-I) o doble (D-I o I-D).
e) Ninguna de las anteriores.

4. ¿Qué secuencia de valores se obtiene al recorrer el siguiente árbol en preorden ypostorden?



a) preorden=[1-2-4-7-8-5-9-3-6-0-11] y postorden=[7-4-8-2-5-9-1-10-6-11-3]
b) preorden=[7-4-8-2-5-9-1-10-6-11-3] y postorden=[7-8-4-9-5-2-10-11-6-3-1]
c) preorden=[1-2-4-7-8-5-9-3-6-10-11] y postorden=[7-8-4-9-5-2-10-11-6-3-1]
d) El árbol no es un ABB, luego no se pueden aplicar esos algoritmos de recorrido

5. La siguiente grafica de un árbol representa:a) Rotación I-D Simple
b) Rotación D-D Simple
c) Rotación D-D Doble
d) Rotación I- I Doble
e) Rotación doble izquierda y doble derecha
6. Seleccione las afirmaciones que considere verdaderas:

a) Un árbol perfectamente equilibrado puede no estar equilibrado en altura.
b) Un árbol perfectamente equilibrado también está equilibrado en altura.
c) Unárbol equilibrado en altura puede no estar perfectamente equilibrado.
d) Un árbol equilibrado en altura está también perfectamente equilibrado.
e) Ninguna de las anteriores.

7. Dados los siguientes algoritmos sobre grafos, indique cuáles de las afirmaciones que
se muestran a continuación es (son) correcta(s):

a) En el algoritmo de Dijkstra, el grafo ha de ser acíclico.b) El algoritmo de Dijsktra sirve para calcular distancias mínimas entre un nodo y todos los demás de un grafo, aunque éste no sea conexo.
c) Tanto el algoritmo de Dijsktra como el de Kruskal sirven para realizar el recorrido de un grafo.
d) Algoritmo válido para grafos dirigidos y no dirigidos
e) Ninguna de las anteriores.

8. Dado un árbol ABB de altura p,¿Cuál es elnumero máximo de nodos que puede tener el árbol?

a) 2p + 1
b) 2p – 1
c) 2p - 1
d) 2p + 1
e) 2p

9. Indique la alternativa incorrecta:

a) Un árbol general se puede representar en forma natural utilizando la siguiente correspondencia: Hermano a la derecha es Hijo a la derecha, Hijo izquierdo es Hijo a la izquierda
b) En el recorrido postorden, el nodo raiz...