Recuperación Primer Parcial 6/6/2012 (2012)

Examen Español
Universidad Universidad Politécnica de Valencia (UPV)
Grado Ingeniería Informática - 2º curso
Asignatura Estructura de Datos y Algoritmos
Año del apunte 2012
Páginas 2
Fecha de subida 27/11/2014
Descargas 3
Subido por

Descripción

Resolución de la Recuperación del Primer Parcial de EDA (6/6/2012)

Vista previa del texto

Resolución de la Recuperación del Primer Parcial de EDA (6/6/2012) 1.-La clase LEGPila es una implementación de la interfaz Pila mediante una lista enlazada. Se ha diseñado una nueva clase, LEGPilaDeEnteros, a la que se quiere añadir un nuevo método, moverPrimeroAlFinal, que sitúa al final de una pila de enteros su primer nodo siempre que el dato que éste contenga sea menor que el del último nodo. El método devuelve true si se ha movido el primer nodo y false en caso contrario o si la pila está vacía.
Se pide completar el código del método moverPrimeroAlFinal.
public class LEGPilaDeEnteros extends LEGPila<Integer> { public boolean moverPrimeroAlFinal(){ boolean mover = false; NodoLEG<Integer> aux = tope; if ( aux!=null ){ while ( aux.siguiente!=null ) aux = aux.siguiente; if ( tope.dato.compareTo(aux.dato)<0 ){ mover = true; aux.siguiente = tope; tope = tope.siguiente; aux.siguiente.siguiente = null; } } return mover; } } (3.5 puntos) public classLEGPila<E> implements Pila<E>{ protected NodoLEG<E> tope; … } classNodoLEG<E>{ E dato; NodoLEG<E> siguiente; … } 2.-Sea v un array de int ordenado ascendentemente y sin elementos repetidos; se quiere comprobar si el par de int x e y, tal que x<y, ocupa posiciones consecutivas dentro del array v. Para ello se pide completar el código del método recursivo hayPar usando de la estrategia Divide y Vencerás para obtener una implementación lo más eficiente posible.
(3.5 puntos) public static boolean hayPar(int[] v,int x,int y){ return buscarPar(v,x,y,0,v.length–1); } private static boolean hayPar(int[] v, int x, int y, int izq, int der){ if ( izq>=der ) return false; else{ int mitad= (izq+der)/2; if ( v[mitad]==x ) return ( v[mitad+1]==y ); else if ( v[mitad]<x ) return hayPar(v, x, y, mitad+1, der); else return hayPar(v, x, y, izq, mitad); } } 3.- Se desea analizar el coste Temporal del siguiente método recursivo: (3 puntos) private static boolean comparar(int[] a, int[] b, int inicio, int fin){ if ( inicio>fin ) return true; int mitad = (fin+inicio)/2; boolean res = ( a[mitad]==b[mitad] ); if (res){ res = comparar(a, b, inicio, mitad–1); if (res) res = comparar(a, b, mitad+1, fin); } return res; } Para ello se pide: a) Expresar la talla del problema en función de los parámetros del método: (0.5 puntos) x = fin-inicio+1 b) Indicar si existen instancias significativas para una talla dada y por qué; en caso y por qué; en caso afirmativo describir cada una de ellas: (0.5 puntos) Sí hay instancias significativas, pues se comprueba si a y b son iguales con una Búsqueda de la primera componente de a que ocupando idéntica posición que una de b no sea igual a ella.
Mejor de los Casos: las componentes centrales de a y b a comparar no son iguales ya en la llamada más alta (con inicio=0 y fin=a.length-1=b.length-1). Así, en tiempo constante res se evalúa a false.
Peor de los Casos: los arrays a y b a comparar sí son iguales, i.e. contienen ya en la llamada más alta las mismas componentes en el mismo orden. Así, res siempre se evalúa a true y se alcanza el caso base del método tras haber realizado tantas llamadas recursivas como componentes tenga a (o b) c) Escribe las relaciones de recurrencia que definan el coste del método: (1 punto) Mejor de los Casos: no hay Relación de Recurrencia asociada al no producirse llamada alguna en el cuerpo de comparar. TcompararM(x>0) = k1 Peor de los Casos: TcompararP(x=0) = k2; TcompararP(x>0) = 2 * Tcompararp(x/2) + k3 d) Resuelve las relaciones de recurrencia del apartado anterior y escribe el coste temporal asintótico del método: (1 punto) Peor de los Casos: por T3 con a=c=2 y sobrecarga constante, TcompararP (x)∈Θ(x) TcompararM (x)∈Θ(1) Mejor de los Casos: Por tanto, Tcomparar(x)∈O(x) y Tcomparar(x)∈Ω(1) Teorema 1: f(x) = a·f(x - c) + b, con b ≥ 1 • si a=1, f(x) ∈ Θ(x); • si a>1, f(x) ∈ Θ(ax/c) Teorema 2: f(x) = a·f(x - c) + b·x + d, con b y d≥1 • si a=1, f(x) ∈ Θ(x2); • si a>1, f(x) ∈ Θ(ax/c) Teorema 3: f(x) = a·f(x/c) + b, con b ≥ 1 • si a=1, f(x) ∈ Θ(logcx); • si a>1, f(x) ∈ Θ(xlogca) Teorema 4: • si • si • si f(x) = a·f(x/c) + b·x + d, con b y d≥1 a<c, f(x) ∈ Θ(x); a=c, f(x) ∈ Θ(x·logcx); a>c, f(x) ∈ Θ(xlogca) ...