Actividad evaluativa est datos PDF

Preview

Summary

EntregaMódulo Teórico-PrácticoMódulo####### Estructuras de datosNombre de la entrega####### Ejercicios de aplicación de las estructuras de datosNivel académico####### Técnico, Tecnólogo, ProfesionalTipo de entrega####### Entrega de ejercicios para aplicar y reforzar los ejes temáticos desarrollados ...

Description

Entrega Módulo Estructuras de datos

Nombre de la entrega Ejercicios de aplicación de las estructuras de datos

Nivel académico Técnico, Tecnólogo, Profesional

Tipo de entrega Entrega de ejercicios para aplicar y reforzar los ejes temáticos desarrollados en los módulos.

INSTRUCCIONES PARA

REALIZAR LA ENTREGA Nota

Tenga en cuenta que el tutor le indicará qué herramienta requiere y qué estrategia deberá desarrollar para evidenciar su participación individual en un trabajo colaborativo.

La realización de este taller de ejercicios requiere de la lectura previa de todos los documentos y la revisión de todos los recursos didácticos contenidos en el escenario actual y anteriores. Adicionalmente, apoyarse en material bibliográfico extra es recomendable. El tutor estará atento a resolver las dudas que pudiesen llegar a originarse y que sean comunicadas por medio de los canales sincrónicos y asincrónicos disponibles en el aula. El primer paso para desarrollar este taller es conformar un equipo de trabajo de tres personas. Todos los integrantes de un equipo deben pertenecer al mismo curso, es decir, deben pertenecer al grupo de un mismo tutor. Únicamente un integrante del equipo debe subir el trabajo al aula virtual, pero, debe incluir los nombres completos de todos los integrantes; no hacerlo implicará que a los estudiantes no incluidos no se les asignará calificación. El plazo y el medio de entrega de esta actividad son los indicados en el aula virtual. Toda entrega hecha después de la fecha y/o por un canal distinto al especificado será invalidada.

POLITÉCNICO GRANCOLOMBIANO

2

ENTREGA PREVIA 1

SEMANA 3

Desarrolle los siguientes ejercicios propuestos. Para el caso de los ejercicios que requieren implementación en Java, usted deberá desarrollarlos en un archivo con extensión .java. Para el caso de los ejercicios que no requieren implementación, usted deberá desarrollarlos en un archivo con extensión .docx (de MS Word). Comprima todos los archivos en un solo archivo de extensión .zip. Ese es el archivo que usted debe entregar. Atención: asegúrese que el archivo .zip funciona y que incluye todos los puntos desarrollados; si el archivo no funciona, la nota será cero; si faltan puntos por desarrollar, la nota será penalizada. 1. Implemente una función en lenguaje java que, dado un arreglo de enteros, A, calcule y retorne el número que más veces se repite en A. En caso de empate, la función puede retornar cualquiera de los números más frecuentes. 2. Investigue acerca del algoritmo de ordenamiento por inserción y: a. Reproduzca un ejemplo (eso significa que usted debe seleccionar un conjunto de números desordenado y mostrar paso a paso cuál es el efecto de aplicar el algoritmo de ordenamiento por inserción sobre él). b. Responda ¿en qué consistiría el peor caso y por qué implica una complejidad algorítmica de O(n2)? c. Implemente en Java una función que ordene un arreglo de números enteros usando el algoritmo de ordenamiento por inserción.

POLITÉCNICO GRANCOLOMBIANO

3

ENTREGA PREVIA 2

SEMANA 5

Desarrolle los siguientes ejercicios propuestos. Para el caso de los ejercicios que requieren implementación en Java, usted deberá desarrollarlos en un archivo con extensión .java. Para el caso de los ejercicios que no requieren implementación, usted deberá desarrollarlos en un archivo con extensión .docx (de MS Word). Comprima todos los archivos en un solo archivo de extensión .zip. Ese es el archivo que usted debe entregar. Atención: asegúrese que el archivo .zip funciona y que incluye todos los puntos desarrollados; si el archivo no funciona, la nota será cero; si faltan puntos por desarrollar, la nota será penalizada. 1. .Un árbol binario tiene el siguiente recorrido en posorden: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]. ¿Es posible reconstruir el árbol a partir de solamente su recorrido en posorden? Si la respuesta es afirmativa, dibuje el árbol. En caso contrario, explique por qué no es posible. 2. Reconstruya (dibuje) el árbol binario ordenado cuyo recorrido en preorden está representado por la lista [8, 7, 3, 2, 1, 4, 6, 5, 9, 13, 12, 10, 11, 14, 15]. 3. Implemente un método recursivo en Java que determine si un valor está o no contenido en un árbol y calcule su complejidad algorítmica. Supuestos y sugerencias para realizar el trabajo:

• El método estará contenido dentro de la clase VEDArbin. • El encabezado del método sería: •

public boolean nombre_metodo (E valor){ ... }

POLITÉCNICO GRANCOLOMBIANO

4

ENTREGA FINAL

SEMANA 7

Desarrolle los siguientes ejercicios propuestos. Para el caso de los ejercicios que requieren implementación en Java, usted deberá desarrollarlos en un archivo con extensión .java. Para el caso de los ejercicios que no requieren implementación, usted deberá desarrollarlos en un archivo con extensión .docx (de MS Word). Comprima todos los archivos en un solo archivo de extensión .zip. Ese es el archivo que usted debe entregar. Atención: asegúrese que el archivo .zip funciona y que incluye todos los puntos desarrollados; si el archivo no funciona, la nota será cero; si faltan puntos por desarrollar, la nota será penalizada. 1. Implemente un método que, dado un árbol binario ordenado y un valor, retorne el sucesor del valor en el árbol. Calcule la complejidad temporal del método. 2. Investigue en qué consiste cada una de las siguientes estrategias de resolución de colisiones en tablas hash y para cada una de ellas proponga un ejemplo: a. Sondeo lineal b. Sondeo cuadrático c. Doble hash 3. Escriba una función java que, dados dos arreglos de enteros S = [s0, s1, …, sm-1] y T = [t0, t1, …, tn-1], decida si S ⊆ T en tiempo esperado O(m + n).

POLITÉCNICO GRANCOLOMBIANO

5...