AED Final

¿Cuáles de las siguientes propuestas generales son ciertas en relación al segmento de memoria conocido como Stack Segment?. a. El Stack Segment se utiliza como soporte interno en el proceso de invocación a funciones (con o sin recursividad): se va llenando a medida que se desarrolla la cascada de invocaciones, y se vacía a medida que se produce el proceso de regreso o vuelta atrás. b. El Stack Segment funciona como una pila (o apilamiento) de datos (modalidad LIFO: Last In - First Out): el último dato en llegar, se almacena en la cima del stack, y será por eso el primero en ser retirado. c. El Stack Segment se utiliza como soporte interno solamente en el proceso de invocación a funciones recursivas: se va llenando a medida que la cascada recursiva se va desarrollando, y se vacía a medida que se produce el proceso de regreso o vuelta atrás. d. El Stack Segment funciona como una cola (o fila) de datos (modalidad FIFO: First In - First Out): el primer dato en llegar, se almacena al frente del stack, y será por eso el primero en ser retirado.

¿Cuáles de las siguientes afirmaciones son ciertas en relación a conceptos asociados con la recursividad?. a. A medida que se desarrolla la cascada de invocaciones recursivas, el stack segment se va llenando para darle soporte a cada instancia recursiva, y luego, cuando una instancia logra finalizar y se produce el proceso de vuelta atrás, el stack segment comienza a vaciarse. b. Cada instancia recursiva que es ejecutada, almacena dos grupos de datos en el stack segment: la dirección de retorno (a la que se debe regresar cuando termine la ejecución de esa instancia) y las variables locales que esa instancia de la función haya creado. c. Una función recursiva no puede incluir más de una invocación a si misma en su bloque de acciones. d. Si una función es recursiva, entonces no debe incluir ningún ciclo en su bloque de acciones.

Suponga que se tiene una cola c en la cual se almacenaron ya una cierta cantidad de datos. ¿Cuál de las siguientes secuencias de instrucciones permite invertir la cola? (o sea: si la cola original c era: [3 - 4 - 6 - 7] (con el 3 al frente), ¿cuál de las siguientes permitiría dejar la cola c en el estado [7 - 6 - 4 - 3] (con el 7 al frente)?). a. # suponga que c2 y c3 son dos colas inicialmente vacías, y listas para usar while not c.is_empty(): c2.add(c2, c.remove()) while not c2.is_empty(): c2.add(c2.remove()) while not c3.is_empty(): c.add(c3.remove()). b. # suponga que p es una PILA vacía y lista para usar... while not c.is_empty(): p.push(c.remove()) while not p.is_empty(): c.add(p.pop()). c. # suponga que p1 y p1 son dos PILAS inicialmente vacías, y listas para usar while not c.is_empty(): p1.push(c.remove()) while not p1.is_empty(): p2.push(p1.pop()) while not p2.is_empty(): c.add(p2.pop()). d. # suponga que c2 es OTRA cola vacía y lista para usar... while not c.is_empty(): c2.add(c.remove()) while not c2.is_empty(): c.add(c2.remove()).

¿Cuántas comparaciones en el peor caso obliga a hacer una búsqueda secuencial en una lista ordenada (o en un arreglo ordenado) que contenga n valores?. a. Peor caso: O(n) comparaciones. b. Peor caso: O(n² ) comparaciones. c. Peor caso: O(1) comparaciones. d. Peor caso: O(log(n)) comparaciones.

¿Cuál es la principal característica de todos los métodos de ordenamiento conocidos como métodos simples o directos?. a. Tienen muy mal rendimiento en tiempo de ejecución, cualquiera sea el tamaño n del arreglo. b. Tienen muy mal rendimiento en tiempo de ejecución si el tamaño n del arreglo es grande o muy grande, y un rendimiento aceptable si n es pequeño. c. Tienen muy buen rendimiento en tiempo de ejecución, cualquiera sea el tamaño n del arreglo. d. Tienen muy mal rendimiento en tiempo de ejecución si el tamaño n del arreglo es pequeño, y un rendimiento aceptable si n es grande o muy grande.

a. 11. b. 12. c. 10. d. 0.

En la columna de la izquierda se muestra el código fuente en Python de diversos procesos sencillos. Para cada uno de ellos, seleccione de la lista de la derecha la expresión en notación Big O que mejor describa el tiempo de ejecución de cada proceso para el peor caso. (Aclaración: una expresión como n^2 debe entenderse como "n al cuadrado" o n² ). O(n^3). O(n). →O(1). O(n^2).

Considere el problema de las Ocho Reinas presentado en clases. ¿Cuáles de las siguientes afirmaciones son ciertas en relación a las diagonales del tablero en el cual deben colocarse la reinas, suponiendo que el tablero es el normal del ajedrez, de 8 * 8? (Más de una respuesta puede ser cierta, por lo que marque todas las que considere correctas...). a. En cada una de las diagonales que se orientan como la principal, es constante la resta entre el número de columna y el número de fila de cada uno de sus elementos. b. En general hay dos tipos de diagonales: las normales (orientadas en la misma forma que la diagonal principal) y las inversas (orientadas en la misma forma que la contra-diagonal o diagonal inversa). c. La cantidad total de diagonales que contiene el tablero (sumando todas las diagonales de todos los tipos posibles) es 30. d. En cada una de las diagonales que se orientan como la contra-diagonal o diagonal inversa, es constante la suma entre el número de columna y el número de fila de cada uno de sus elementos.

Una Cola de Prioridad es una cola en la cual los elementos se insertan en algún orden, pero tal que cuando se pide retirar un elemento se obtiene siempre el menor de los valores almacenados en la cola ¿Cuál de las siguientes estrategias podría ser una forma básica de implementar una Cola de Prioridad en las condiciones aquí expresadas?. a. Soporte: una variable de tipo list en Python. Inserción: ordenada de menor a mayor (mantener el arreglo siempre ordenado de menor a mayor: para insertar un valor x, recorrer el arreglo y al encontrar el primer mayor a x detener el ciclo y añadir allí a x con un corte de índices. Eliminación: siempre el primer elemento. b. Soporte: una varable de tipo list en Python. Inserción: siempre al frente. Eliminación: siempre el primer elemento. c. Soporte: una variable de tipo list en Python. Inserción: ordenada de mayor a menor (mantener el arreglo siempre ordenado de mayor a menor: para insertar un nuevo valor x, recorrer el arreglo y al encontrar el primer menor, a x detener el ciclo y añadir allí a x con un corte de índices. Eliminación: siempre el primer elemento. d. Soporte: una variable de tipo list en Python. Inserción: siempre al final. Eliminación: siempre el último elemento.

¿Cuáles de las siguientes afirmaciones son ciertas en referencia a las Estrategias de Resolución de Problemas que se citan? (Más de una respuesta puede ser cierta, por lo que marque todas las que considere correctas...). a. La estrategia de Fuerza Bruta se basa en aplicar ideas intuitivas y directas, simples de codificar, pero normalmente produce algoritmos de mal rendimiento en tiempo de ejecución y/o de espacio de memoria empleado. b. El empleo de la Recursividad para resolver un problema no es recomendable en ningún caso, debido a la gran cantidad de recursos de memoria o de tiempo de ejecución que implica. c. La estrategia de Backtracking es de base recursiva y permite implementar soluciones de prueba y error explorando las distintas soluciones y voviendo atrás si se detecta que un camino conduce a una solución incorrecta. cuando es aplicable, es más eficiente que la Fuerza Bruta, ya que permite eliminar caminos por deducción. d. La técnica de Programación Dinámica se basa en calcular los resultados de los subproblemas de menor orden o tamaño que pudieran aparecer, almacenar esos resultados en una tabla, y luego re-usarlos cuando vuelvan a ser requeridos en el cálculo del problema mayor.

Suponga que para un problema dado se ha planteado un algoritmo basado en divide y vencerás cuya estructura lógica esencial es la siguiente: proceso(partición): adicional() [O(n)] proceso(partición/3) proceso(partición/3) proceso(partición/3) ¿Cuál de las siguientes es la expresión en notación Big O del tiempo de ejecución para este proceso? (Aclaración: la base del logaritmcaso es relevante a los efectos del planteo conceptual de la pregunta).o no es esencial en una expresión en notación Big O, pero en este. a. O(n² * log₃ (n)). b.O(n² * log₂ (n)). c. O(n * log₃ (n)). d. O(n * log₂ (n)).

¿Cuál de las siguientes situaciones haría que el algoritmo Quicksort degenere en su peor caso en cuanto al tiempo de ejecución, de orden n² ?. a. Que el arreglo esté ya ordenado, pero al revés. b. Que el arreglo de entrada tenga sus elementos dispuestos de tal forma que cada vez que se seleccione el pivot en cada partición, resulte que ese pivot sea siempre el menor o el mayor de la partición que se está procesando. c. El algoritmo Quicksort no tiene un peor caso O(n² ). Su tiempo de ejecución siempre es O(n*log(n)). d. Que el arreglo esté ya ordenado, en la misma secuencia en que se lo quiere ordenar.

¿Cuáles de las siguientes son características correctas del algoritmo Shellsort? (Más de una puede ser cierta... marque TODAS las que considere válidas). a. Una muy buena serie de incrementos decrecientes a usar, es la serie h = {...16, 8, 4, 2, 1}. b. El algoritmo Shellsort consiste en una mejora del algoritmo de Inserción Directa (o Inserción Simple), consistente en armar subconjuntos ordenados con elementos a distancia h > 1 en las primeras fases, y terminar con h = 1 en la última. c. El algoritmo Shellsort consiste en una mejora del algoritmo de Selección Directa, basada en buscar iterativamente el menor (o el mayor) entre los elementos que quedan en el vector, para llevarlo a su posición correcta, pero de forma que la b;usqueda del menor en cada vuelta se haga en tiempo logarítmico. d. El algoritmo Shellsort es complejo de analizar para determinar su rendimientos en forma matemática, ya que ese rendimiento depende fuertemente de la serie de incrementos decreciente que se haya seleccionado.

Si los algoritmos de ordenamiento simples tienen todos un tiempo de ejecución O(n² ) en el peor caso, entonces: ¿cómo explica que las mediciones efectivas de los tiempos de ejecución de cada uno sean diferentes frente al mismo arreglo?. a. La notación Big O rescata el término más significativo en la expresión que calcula el rendimiento, descartando constantes y otros términos que podrían no coincidir en los tres algoritmos. b. Los tiempos deben coincidir. Si hay diferencias, se debe a errores en los intrumentos de medición o a un planteo incorrecto del proceso de medición. c. La notación Big O no se debe usar para estimar el comportamiento en el peor caso, sino sólo para el caso medio. d. La notación Big O no se usa para medir tiempos sino para contar comparaciones u otro elemento de interés. Es un error, entonces, decir que los tiempos tienen "orden n cuadrado".

Considere la función presentada en clases para calcular mediana entre el primero, el central y el último elemento de una partición del arreglo v delimitada por los elementos en las posiciones izq y der: def get_pivot_m3(v, izq, der): # calculo del pivot: mediana de tres... central = int((izq + der) / 2) if v[der] < v[izq]: v[der], v[izq] = v[izq], v[der] if v[central] < v[izq]: v[central], v[izq] = v[izq], v[central] if v[central] > v[der]: v[central], v[der] = v[der], v[central] return v[central] El tamaño de la partición analizada es entonces n = der - izq + 1 elementos. ¿Cuál es el tiempo de ejecución de esta función, expresado en notación O y de acuerdo a ese valor de n?. a. O(n² ). b. O(log(n)). c. O(1). d. O(n).

¿Cuáles de los siguientes son factores de eficiencia comunes a considerar en el análisis de algoritmos? (Más de una respuesta puede ser válida... marque todas las que considere correctas). a. El consumo de memoria. b. La calidad aparente de la interfaz de usuario. c. El tiempo de ejecución. d. La complejidad aparente del código fuente.

¿Cuál de los siguientes es el creador del famoso algoritmo de ordenamiento conocido como Quicksort?. a. Charles Antony Richard Hoare. b. Donald Shell. c. J. W. J. Williams. d. Edsger Wybe Dijkstra.

Considere el problema de las Ocho Reinas presentado en clases. Se ha indicado que se puede usar un arreglo rc de componentes, en el cual el casillero rc[col] = fil indica que la reina de la columna col está ubicada en la fila fil. ¿Cuáles de las siguientes configuraciones para el arreglo rc representan soluciones incorrectas para el problema de las Ocho Reinas? (Más de una respuesta puede ser cierta, por lo que marque todas las que considere correctas...). a. rc = [3, 5, 7, 0, 5, 1, 2, 4]. b. rc = [2, 0, 7, 4, 5, 1, 6, 3]. c. rc = [4, 7, 3, 0, 2, 5, 1, 6]. d. rc = [5, 3, 6, 0, 7, 1, 4, 2].

Para cada uno de los algoritmos o procesos listados en la columna de la izquierda, seleccione la expresión de orden que mejor describe su tiempo de ejecución en el peor caso. O(1). O(n). O(log(n)). O(n^2) (léase: "orden n al cuadrado"). O(n^3) (léase: "orden n al cubo").

¿Cuál de los siguientes esquemas simples de pseudocódigo representa a un algoritmo planteado mediante estrategia Divide y Vencerás, pero con tiempo de ejecución O(n*log(n))?. a. proceso(partición): adicional() [==> O(n² )] proceso(partición/2) proceso(partición/2). b. proceso(partición): adicional() [==> O(n³ )] proceso(partición/2) proceso(partición/2). c. proceso(partición): adicional() [==> O(n)] proceso(partición/2) proceso(partición/2). d. proceso(partición): adicional() [==> O(1)] proceso(partición/2) proceso(partición/2).

A lo largo del curso hemos visto la forma de plantear programas controlados por menú de opciones, y sabemos que esos programas incluyen un ciclo para el control del proceso. Pero también podríamos hacer un planteo basado en recursión, sin usar el ciclo, en forma similar a la que se muestra aquí: __author__ = 'Cátedra de AED' def menu(): print('1. Opcion 1') print('2. Opcion 2') print('3. Salir') op = int(input('Ingrese opcion:')) if op == 1: print('Eligio la opcion 1...') elif op == 2: print('Eligio la opcion 2...') elif op == 3: return menu() # script principal... menu() ¿Hay algún problema o contraindicación respecto al uso y aplicación de esta versión recursiva para la gestión de un menú ? Selecciona la respuesta que mejor describa este punto. La versión recursiva que se mostró no funciona. Sólo permite cargar una vez la opción elegida, e inmediatamente se detiene. No hay ningún problema ni contraindicación. Y no sólo eso: la versión recursiva es más simple y compacta que la versión basada en un ciclo, por lo cual es incluso preferible usarla. Esta versión recursiva es completamente equivalente a la versión iterativa. No hay ningún motivo para preferir la una sobre la otra. Esta versión recursiva posiblemente sea más simple y compacta que la versión basada en un ciclo, pero la versión recursiva pide memoria de stack cada vez que se invoca, por lo que es más conveniente la iterativa.

¿Qué elementos son necesarios para que una función recursiva se considere bien planteada?. a. La función debe tener al menos una invocación a si misma en su bloque de acciones, y antes de esas invocaciones debe tener una o más condiciones de control que permitan interrumpir el proceso recursivo si se ha llegado a alcanzar alguna de las situaciones triviales o base del problema. b. La función debe tener al menos una invocación a si misma en su bloque de acciones, y después de esas invocaciones debe tener una o más condiciones de control que permitan interrumpir el proceso recursivo si se ha llegado a alcanzar alguna de las situaciones triviales o base del problema. c. La función debe tener al menos un ciclo en su bloque de acciones, y ese ciclo debe estar planteado de tal forma que nunca entre en un lazo infínito. d. La función debe tener al menos una invocación a si misma en su bloque de acciones.

¿Cuál de las siguientes situaciones de programación es la principal aplicación de una Pila?. a. Procesar una secuencia de datos en orden de menor a mayor. b. Procesar una secuencia de datos en orden inverso al de su entrada. c. Procesar una secuencia de datos en orden aleatorio. d. Procesar una secuencia de datos en el mismo orden en el que ingresaron.

Típicamente (y por diversas razones) en un árbol binario de búsqueda no se acepta la inserción de claves o valores repetidos. Pero existen estrategias simples que pueden usarse para permitir esa repetición de claves. Una de ellas es la de relajar la regla de inserción de forma que los menores sigan yendo a la izquierda, pero ahora los mayores o iguales vayan a la derecha. ¿Cuáles de la siguientes afirmaciones son ciertas si en un árbol binario de búsqueda se cambia la regla de inserción para aplicar la regla relajada citada más arriba? (Más de una respuesta puede ser cierta, por lo que marque todas las que considere correctas). Seleccione una o más de una. a. Dos claves iguales quedarán siempre en el árbol como una hija derecha e inmediatamente de la otra. b. Si solo se insertan claves que sean iguales a la que contiene la raíz, el árbol tendrá estructura de una diagonal con todos los enlaces derechos nulos. c. Dos o más claves iguales podrán quedar separadas por dos o más niveles de distancia. d. Si solo se insertan claves que sean iguales a la que contiene la raíz, el árbol tendrá estructura de una diagonal con todos los enlaces izquierdos nulos.

¿Cuáles de la siguientes son características correctas del algoritmo Shellsort (Más de una puede ser cierta...marque TODAS las que considere válidas). a. El algoritmo Shellsort es complejo de analizar para determinar su rendimiento en forma matemática. Se sabe que para la serie de incrementos decrecientes usada la implementación vista en las clases de la asignatura, tiene un tiempo de ejecución para el peor caso de O(n¹⋅⁵). b. El algoritmo Shellsort consiste en una mejora del algoritmo de Inserción Directa( o Inserción Simple), consiste en armar subconjuntos ordenados con elementos a distancia h > 1 en las primeras fases, y terminar con h = 1 en la ultima. c. El algoritmo Shellsort consiste en una mejora del algoritmo de Selección directa, consiste en buscar iterativamente el menor(o el mayor) entre los elementos que quedan en el vector, para llevarlo a su posición correcta, pero de forma que la búsqueda del menor en cada vuelta se haga en tiempo logarítmico. d. En el caso promedio, el algoritmo Shellsort es tan eficiente como el Heapsort o el Quicksort, con el tiempo de ejecución O(n*log(n)).

¿Cuál es la principal característica de todos los métodos de ordenamiento conocidos como métodos simples o directos? Seleccione una. a. Tienen muy mal rendimiento en tiempo de ejecución, cualquiera sea el tamaño n del arreglo. b. Tienen muy mal rendimiento en tiempo de ejecución si el tamaño n del arreglo es pequeño, y un rendimiento aceptable si n es grande o muy grande. c. Tienen muy buen rendimiento en tiempo de ejecución, cualquiera sea el tamaño n del arreglo. Tienen muy mal rendimiento en tiempo de ejecución si el tamaño n del arreglo es grande o muy grande, y un rendimiento aceptable si n es pequeño.

a. Sí. Es correcto. b. No la propia definición previa del concepto de producto es incorrecta: un producto es la multiplicación, y no una suma... c. No. La última línea deberia decir return a + producto(a-1, b-1) en lugar de return a + producto(a, b-1). d. No la función sugerida siempre retornará 0, sean cuales fuesen los valores de a y b.

¿Cuál de la siguientes afirmaciones es FALSA respecto de los ciclos en un grafo? Seleccione una: a. Los ciclos no están permitidos en un grafo. b. Los ciclos pueden ser válidos o no, dependiendo del problema que se quiere resolver. c. Un ciclo es un camino que parte de un nodo y lleva de vuelta al mismo nodo. d. Es válido que un ciclo conste de un único arco que permita vincular a un nodo consigo mismo.

¿Cuál de las siguientes expresiones describe la forma de trabajo general de una Cola?. a. FIFO (First In - First Out). b. OIRO (Ordered In - Random Out). c. LIFO (Last In - First Out). d. OIFO (Ordered In - First Out).

Considere el problema de las Ocho Reinas presentado en clases. ¿ Cuáles de las siguientes afirmaciones son ciertas en relación a las diagonales inversas del tablero en el cual deben colocarse las reinas, suponiendo que el tablero es el normal del ajedrez, de 8 * 8? (más de una respuesta puede ser cierta, por lo que marque todas las que considere correctas...) Seleccione una o más de una: a. El valor de la suma entre el número de columna y el número de fila de cada componente de una diagonal inversa, es un número constante para cada diagonal, y los posibles valores están en el intervalo [0..14]. b. EL valor de la resta entre el número de columna y el número de fila de cada componente de una diagonal inversa, es un número constante para cada diagonal, y los posibles valores están en el intervalo [-7..7]. c. Las diagonales inversas pueden representarse con un arreglo qid de 15 componentes, en el que cada diagonal cuyos elementos tengan el mismo valor (col - fil), se haga coincidir el casillero qid[(col - fil) + 7]. d. Las diagonales inversas pueden representarse con un arreglo qid de 15 componentes, en el que cada diagonal cuyos elementos tengan el mismo valor ( col + fil), se haga coincidir el casillero qid[(col - fil)].

¿Qué se entiende (esencialmente) por una gráfica o figura fractal?. a. Es aquella que se compone de fragmentos distintos de diversas figuras, conformando una imagen sin un patrón definido ni obvio. b. Es aquella que se compone de versiones más simples y pequeñas de la misma figura original. c. Es aquella que se compone sólo por cuadrados, círculos y triángulos combinados. d. Es aquella que se compone a partir de la combinación de millares de pequeños puntos que al ser mirados desde cierta distancia producen en forma completa la imagen compuesta.

¿Cuál de las siguientes situaciones haría que el algoritmo Quicksort degenere en su peor caso en cuanto al tiempo de ejecución, de orden n²? Seleccione una: a. Que el arreglo esté ya ordenado, Pero al revés. b. Que el arreglo esté ya ordenado, en la misma secuencia en que se lo quiere ordenar. c. Que el arreglo de entrada tenga sus elementos dispuestos de tal forma que cada vez que seleccione el pivot en cada partición, resulte que ese pivot sea siempre el menor o el mayor de la partición que se está procesando. d. El algoritmo de Quicksort no tiene un peor caso O(n²). Su tiempo de ejecución siempre es O(n*log(n)).

¿Cuál es el problema si en el algoritmo Shellsort se elige una serie de incrementos decrecientes de la forma {...,16,8,4,2,1}? Seleccione una: a. El arreglo no quedará ordenado al final. b. Los subconjuntos analizados contendrán casi los mismos elementos cuando la distancia usada sea cada vez menor, sin garantías de lograr una buena organización del arreglo antes de la última pasada. c. Ningún problema: esa serie es tan buena como cualquier otra. d. no sólo no hay ningún problema, sino que esa serie es la mejor posible para el algoritmo Shellsort.

Suponga que se desea modelar con un grafo la estructura del plan de estudios de una carrera universitaria. El equipo de trabajo ha decidido que los vértices del grafo representen asignaturas y los arcos representen restricciones de correlativas previas. Así, el arco (x, y) que parte de la asignatura x y llega a la y indica que para cursar y debe estar regularizada x. Lo anterior implica además que el grafo debe ser dirigido. El equipo de trabajo ha determinado además algunas restricciones obvias que deben controlarse y validarse en todo momento en el sistema de gestión del plan. Indique cuáles de las siguientes situaciones no serían aceptables en el grafo propuesto, y deberían ser evitadas por procesos de validación (aclaración: más de una puede ser seleccionada): Seleccione una o más de una: a. La ocurrencia de algún tipo de relación transitiva explícita, es decir, que existan al mismo tiempo los arcos (x, y), (y, z) y (x, z). b. La ocurrencia de auto ciclos en cualquiera de sus vértices. c. La ocurrencia de ciclos en general en el grafo. d. Vértices aislados, es decir, vértices a los que no llega ningún arco de entrada y de los cuales tampoco hay arcos de salida. e. Vértices a los que no llega ningún arco de entrada (aunque podrían tener arcos de salida).

¿Qué significa decir que un algoritmo dado tiene un tiempo de ejecución O(n)? Seleccione una: a. El tiempo de ejecución es constante, sin importar la cantidad de datos. b. El proceso normalmente consiste en dos ciclos (uno dentro del otro) de aproximadamente n iteraciones cada uno, de forma que las operaciones críticas se aplican un número cuadrático de veces. c. El tiempo de ejecución es lineal: si aumenta el número de datos, aumenta el tiempo de en la misma proporción. d. A medida que aumenta el número de datos, aumenta el tiempo pero en forma muy suave: el conjunto de datos se divide en dos. se procesa una de las mitades, se desecha la otra y se repite el proceso hasta que no pueda volver a dividirse la mitad que haya quedado.

¿Por qué es considerada una mala idea tomar como pivot al primer elemento (o al último) de cada partición al implementar el algoritmo Quicksort? seleccione una: a. Porque de esa forma aumenta el riesgo de caer en el peor caso, o aproximarse al peor caso, si el arreglo estuviese completamente desordenado. b. No es cierto que sea una mala idea. Ambas alternativas son tan buenas como cualquier otra. c. Porque de esa forma aumenta el riesgo de caer en el peor caso, o aproximarse al peor caso, si el tamaño n del arreglo fuese muy grande. d. Porque de esa forma aumenta el riesgo de caer en el peor caso, o aproximarse al peor caso, si el arreglo estuviese ya ordenado o casi ordenado.

¿Cuál es la razón por la que es recomendable usar una pila como soporte al recorrer un árbol binario (y por lo tanto, cuál es la razón por la que es recomendable usar recursión para ese recorrido? Seleccione una: a. No es necesario ni usar una pila ni usar recursión. El árbol puede recorrerse simplemente con un ciclo que comience en la raíz y luego se desplace vuelta tras vuelta hacia el hijo izquierdo, hasta llegar a un hijo izquierdo nulo, momento en el cual el ciclo debe detenerse y el árbol queda completamente recorrido. b. No hay ninguna razón para usar una pila o para usar recursión. Un ciclo y una referencia de persecución serían siempre suficientes para hacer el recorrido completo. c. Porque una pila permite almacenar en orden LIFO las direcciones de los nodos que se acaban de visitar en el recorrido, y cuando se necesite regresar a ese nodo luego de procesar alguno de sus dos hijos, su dirección quedará en el tope de la pila y será accesible en forma directa. d. En realidad, es mejor usar una cola en lugar de una pila. Una cola permite almacenar en orden FIFO las direcciones de los nodos que se acaban de visitar en el recorrido, y cuando se necesite regresar a ese nodo luego de procesar alguno de sus dos hijos, su dirección quedará en el frente de la cola y será accesible en forma directa.

¿Cuál de las siguientes afirmaciones es falsa en relación a las Estrategias de Resolución de Problemas (o Estrategias de Planteo de Algoritmos)? Seleccione una: a. Son técnicas y recomendaciones para el planteo de problemas que garantizan que se encontrará una solución, empleando la estrategia correcta para cada problema que se enfrente. b. Un mismo problema podría ser resuelto en base a dos o más estrategias de resolución diferentes, dando lugar a distintos algoritmos para ese mismo problema. c. Se trata de un conjunto de técnicas diversas que podrían ayudar a encontrar una solución a un problema, pero sin garantía de éxito, y aún si se llega a una solución, tampoco se garantiza que esa solución sea eficiente. d. Se trata de un conjunto de técnicas diversas que podrían ayudar a encontrar la solución a un problema, pero sin garantía de éxito.

Se tiene un algoritmo que realiza cierta cantidad de procesos sobre un conjunto de n datos y un minucioso análisis matemático ha determinado que la cantidad de procesos que el algoritmo realiza en el peor caso viene descripto por la función f(n) = 3n³ + 5n² + 2n¹⋅⁵ ¿Cuál de las siguientes expresiones representa mejor el orden del algoritmo para el peor caso? Seleccione una: a. O(3n³ + 5n² + 2n¹⋅⁵). b. O(n¹⋅⁵). c. O(n³ + n²). d. O(n³).

¿Cuál de los siguientes esquemas simples de pseudocódigo representa a un algoritmo planteado mediante estrategia Divide y Vencerás pero con tiempo de ejecución O(n*log(n))? Seleccione una: a. proceso (partición): adicional () [ ==> O(n) ] proceso (partición/2) proceso (partición/2). b. proceso (partición): adicional () [ ==> O(1) ] proceso (partición/2) proceso (partición/2). c. proceso (partición): adicional () [ ==> O(n²) ] proceso (partición/2) proceso (partición/2). d. proceso (partición): adicional () [ ==> O(n³) ] proceso (partición/2) proceso (partición/2).

Suponga que se quiere plantear una definición recursiva del concepto de bosque. ¿Cuál de las siguientes propuestas generales es correcta y constituye la mejor definición? Seleccione una: a. Un bosque es un conjunto de árboles que puede estar vacío, o puede contener n árboles (con n > 0). b. Un bosque es un bosque. c. Un bosque es un conjunto de árboles que puede estar vacío, o puede contener uno o más árboles agrupados con otro bosque. d. Un bosque es un conjunto que puede contener uno o más árboles agrupados con otro bosque.

¿Qué elementos son necesarios para que una función recursiva se considere bien planteada? Seleccione una: a. La función debe tener al menos una invocación a si misma en su bloque de acciones, y antes de esas invocaciones debe tener una o más condiciones de control que permitan interrumpir el proceso recursivo si se ha llegado a alcanzar alguna de las situaciones triviales o base del problema. b. La función deben tener al menos una invocación a si misma en su bloque de acciones. c. La función debe tener al menos un ciclo en su bloque de acciones, y ese ciclo debe estar planteado de forma tal que nunca entre en un lazo infinito. d. La función debe tener al menos una invocación a si misma en su bloque de acciones, y después de esas invocaciones debe tener una o más condiciones de control que permitan interrumpir el proceso recursivo si se ha llegado a alcanzar alguna de las situaciones triviales o base del problema.

¿Cuál de las siguientes situaciones de programación es la principal aplicación de una Pila? Seleccione una: a. Procesar una secuencia de datos en orden de menor a mayor. b. Procesar una secuencia de datos en orden inverso al de su entrada. c. Procesar una secuencia de datos en orden aleatorio. d. Procesar una secuencia de datos en el mismo orden en el que ingresaron.

¿Cuáles de las siguientes son correctas en cuanto a los tiempos de ejecución de los algoritmos de ordenamiento clásicos? (Más de una puede ser cierta... marque TODAS las que considere válidas) Seleccione una o más de una: a. Algoritmos directos o simples: O(n²) en el peor caso para todos ellos. b. Algoritmo Quick Sort: O(n*log(n)) en el caso promedio, pero O(n²) en el peor caso. c. Algoritmo Heap Sort: O(n*log(n)) tanto para el caso promedio como para el peor caso. d. Algoritmo Shell Sort: O(n²) en el peor caso para la serie de incrementos decrecientes vista en clase.

¿Cuál es la principal característica de todos los métodos de ordenamiento conocidos como métodos simples o directos? Seleccione una: a. Tienen muy mal rendimiento en tiempo de ejecución, cualquiera sea el tamaño n del arreglo. b. Tienen muy mal rendimiento en tiempo de ejecución si el tamaño n del arreglo es grande o muy grande, y un rendimiento aceptable si n es pequeño. c. Tienen muy buen rendimiento en tiempo de ejecución, cualquiera sea el tamaño n del arreglo. d. Tienen muy mal rendimiento en tiempo de ejecución si el tamaño n del arreglo es pequeño, y un rendimiento aceptable si n es grande o muy grande.

a. 0. b. 11. c. 12. d. 10.

Para cada uno de los algoritmos o procesos listados en la columna de la izquierda, seleccione la expresión de orden que mejor describe su tiempo de ejecución en el peor caso. O(n^3) (léase: "orden n al cubo"). O(n). O(log(n)). O(1). O(n^2) (léase: "orden n al cuadrado").

¿Cuáles de las siguientes afirmaciones con correctas en relación a conceptos elementales del análisis de algoritmos? (Más de una respuesta puede ser válida, por lo que marque todas las que considere correctas). Seleccione una o más de una: a. La notación Big O se usa para expresar el rendimiento de un algoritmo en terminos de una función que imponga una cota inferior para ese algoritmo en cuanto al factor medido (tiempo o espacio de memoria). b. Los dos factores de eficiencia más comúnmente utilizados en el análisis de algoritmos son el tiempo de ejecución de un algoritmo y el espacio de memoria que un algoritmo emplea. c. El análisis del caso promedio es aquel en el cual se estudia el comportamiento de un algoritmo cuando debe procesar una configuración de datos que llegan en forma aleatoria. d. El análisis del peor caso es aquel en el cual se estudia el comportamiento de un algoritmo cuando debe procesar la configuración más desfavorable posible de los datos que recibe.

¿Cuál es la diferencia entre la abstracción de datos y la abstracción funcional? Seleccione una: a. Ninguna. Son sólo dos formas de referirse al mecanismo de abstracción. b. No existe un mecanismo de abstracción de datos ni un mecanismo de abstracción funcional. Existe sólo un mecanismo de abstracción, sin dividir en abstracción de datos y abstracción funcional. c. La abstracción de datos busca captar el conjunto de procesos relevante para el tipo abstracto que se quiere implementar, mientras que la funcional buscar determinar el conjunto de datos más relevante para implementar ese tipo. d. La abstracción de datos busca captar el conjunto de datos más relevante para representar un tipo abstracto, mientras que la funcional buscar determinar el conjunto de procesos relevante para esos datos.

Considere el problema de las Ocho Reinas presentado en clases. Se ha indicado que se puede usar un arreglo rc de componentes, en el cual el casillero rc[col] = fil indica que la reina de la columna col está ubicada en la fila fil. ¿Cuáles de las siguientes configuraciones para el arreglo rc representan soluciones incorrectas para el problema de las Ocho Reinas? (Más de una respuesta puede ser cierta, por lo que marque todas las que considere correctas...) Seleccione una o más de una: a. rc = [2, 0, 7, 4, 5, 1, 6, 3]. b. rc = [5, 3, 6, 0, 7, 1, 4, 2]. c. rc = [4, 7, 3, 0, 2, 5, 1, 6]. d. rc = [3, 5, 7, 0, 5, 1, 2, 4].

¿Cuáles de las siguientes son ciertas respecto de la estrategia de resolución de problemas conocida como Algoritmos Ávidos? Seleccione una o más de una: a. Se trata de un planteo basado en explorar y analizar cada camino posible para resolver un problema, de forma que si detecta que algún camino conduce a una solución incorrecta, se abandone ese camnio y se regrese para explorar otros posibles, hasta dar con la solución correcta. b. Normalmente, una ventaja de un algoritmo ávido es que, si la regla local aplicada es correcta, suele ser sencillo de plantear y de comprender, además de veloz para ejecutar. c. Normalmente, una ventaja de intentar aplicar un algoritmo ávido es que si bien la validez de la regla local debe ser demostrada formalmente, eso es comúnmente fácil de hacer. d. Se trata de un planteo basado en identificar una regla local que intuitivamente parece correcta, y aplicarla una y otra vez sin volver atrás ni analizar caminos alternativos, hasta llegar a la solución del problema global.

¿Cuál es la cantidad de niveles del árbol de invocaciones recursivas que se genera al ejecutar el Quicksort para ordenar un arreglo de n elementos, en el caso promedio? (Es decir: ¿Cuál es la altura de ese árbol en el caso promedio?) Seleccione una: a. Altura = n². b. Altura = n * log(n). c. Altura = n. d. Altura = log(n).

¿Cuál de los siguientes es el creador del famoso algoritmo de ordenamiento conocido como Quicksort? Seleccione una: a. Donald Shell. b. Charles Antony Richard Hoare. c. Edsger Wybe Dijkstra. d. J. W. J. Williams.

Analice el siguiente esquema de una función en Python: def procesar(n, m): for i in range(n+1): for j in range(m+1): # ... acciones sencillas a realizar... # ... suponga que no hay otro ciclo aquí... # ... y que sólo aparecen operaciones de tiempo constante... ¿Cuál de las siguientes expresiones de orden describe mejor el tiempo de ejecución de esta función en el peor caso? Seleccione una: a. O(n*n). b. O(n*m). c. O(n). d. O(m).

¿Por qué es considerada una mala idea tomar como pivot al primer elemento (o al último) de cada partición al implementar el algoritmo Quicksort? Seleccione una: a. No es cierto que sea una mala idea. Ambas alternativas son tan buenas como cualquier otra. b. Porque de esa forma aumenta el riesgo de caer en el peor caso, o aproximarse al peor caso, si el arreglo estuviese completamente desordenado. c. Porque de esa forma aumenta el riesgo de caer en el peor caso, o aproximarse al peor caso, si el tamaño n del arreglo fuese muy grande. d. Porque de esa forma aumenta el riesgo de caer en el peor caso, o aproximarse al peor caso, si el arreglo estuviese ya ordenado o casi ordenado.

¿Cuáles de las siguientes son características correctas del algoritmo Shellsort? (Más de una puede ser cierta... marque TODAS las que considere válidas) Seleccione una o más de una: a. El algoritmo Shellsort consiste en una mejora del algoritmo de Inserción Directa (o Inserción Simple), consistente en armar subconjuntos ordenados con elementos a distancia h > 1 en las primeras fases, y terminar con h = 1 en la última. b. El algoritmo Shellsort consiste en una mejora del algoritmo de Selección Directa, consistente en buscar iterativamente el menor (o el mayor) entre los elementos que quedan en el vector, para llevarlo a su posición correcta, pero de forma que la búsqueda del menor en cada vuelta se haga en tiempo logarítmico. c. El algoritmo Shellsort es complejo de analizar para determinar su rendimientos en forma matemática. Se sabe que para la serie de incrementos decrecientes usada en la implementación vista en las clases de la asignatura, tiene un tiempo de ejecución para el peor caso de O(n¹⋅⁵). d. En el caso promedio, el algoritmo Shellsort es tan eficiente como el Heapsort o el Quicksort, con tiempo de ejecución O(n*log(n)).

¿Cuál de las siguientes describe mejor la idea de funcionamiento en la que está basado el algoritmo conocido como ordenamiento por Selección Simple o Selección Directa para ordenar un arreglo de n componentes? Seleccione una: a. Suponer que el arreglo tiene un subconjunto inicialmente ordenado que contiene sólo al primer elemento, luego realizar n pasadas, de forma que en cada una agregue el siguiente elemento al grupo que está ordenado. b. Realizar n pasadas, de forma que en cada una se compare a cada elemento con el siguiente, logrando que en cada pasada los mayores vaya acomodándose al final del arreglo. c. Realizar n pasadas, de forma que en cada una se determine el menor de los elementos analizados, y llevar ese menor a la casilla pivot. d. Reacomodar los n elementos del arreglo en forma aleatoria, controlar si quedó ordenado, y en caso de negativo, volver a reacomodarlos en forma aleatoria, continuando así hasta que en algún momento se obtenga un arreglo ordenado...

¿Cuáles de las siguientes afirmaciones son ciertas en referencia a las Estrategias de Resolución de Problemas que se citan? (Más de una respuesta puede ser cierta, por lo que marque todas las que considere correctas...) Seleccione una o más de una: a. La estrategia de Fuerza Bruta se basa en aplicar ideas intuitivas y directas, simples de codificar, pero normalmente produce algoritmos de mal rendimiento en tiempo de ejecución y/o de espacio de memoria empleado. b. La técnica de Programación Dinámica se basa en calcular los resultados de los subproblemas de menor orden o tamaño que pudieran aparecer, almacenar esos resultados en una tabla, y luego re-usarlos cuando vuelvan a ser requeridos en el cálculo del problema mayor. c. La estrategia de Backtracking es de base recursiva y permite implementar soluciones de prueba y error explorando las distintas soluciones y volviendo atrás si se detecta que un camino conduce a una solución incorrecta. cuando es aplicable, es más eficiente que la Fuerza Bruta, ya que permite eliminar caminos por deducción. d. El empleo de la Recursividad para resolver un problema no es recomendable en ningún caso, debido a la gran cantidad de recursos de memoria o de tiempo de ejecución que implica.

¿Qué significa decir que un algoritmo dado tiene un tiempo de ejecución O(1)? Seleccione una: a. El tiempo de ejecución siempre es de un segundo, sin importar la cantidad de datos. b. El tiempo de ejecución es logarítmico: a medida que aumenta el número de datos, aumenta el tiempo pero en forma muy suave. c. El tiempo de ejecución es lineal: si aumenta el número de datos, aumenta el tiempo en la misma proporción. d. El tiempo de ejecución es constante, sin importar la cantidad de datos.

¿Cuál de las siguientes situaciones haría que el algoritmo Quicksort degenere en su peor caso en cuanto al tiempo de ejecución, de orden n²? Seleccione una: a. El algoritmo Quicksort no tiene un peor caso O(n²). Su tiempo de ejecución siempre es O(n*log(n)). b. Que el arreglo de entrada tenga sus elementos dispuestos de tal forma que cada vez que se seleccione el pivot en cada partición, resulte que ese pivot sea siempre el menor o el mayor de la partición que se está procesando. c. Que el arreglo esté ya ordenado, pero al revés. d. Que el arreglo esté ya ordenado, en la misma secuencia en que se lo quiere ordenar.