| Autor |
Mensaje |
Grima
Nivel 3
Edad: 34
Registrado: 15 Jul 2008
Mensajes: 43
Carrera: Informática
|
|
Acá dejo algo parecido a lo que tomó, basado en lo que me acuerdo:
1)Definir TDA conjunto.
Suponer que:
a) esta implementado con una lista circular, con un puntero al primero nada mas. Que
para hacer alta coloca el elemento al principio (y para la baja la recorre toda). Esta desordenada.
b) Un arbol ABB (con sus metodos de alta y baja).
1.1) Describir como implementaría para c/u las operaciones báscias del TDA conjunto. Y su orden
algorítmico.
1.2) Qué estructura utilizaría para obtener un orden logarítmico.
Dada esa estructura, definirla y agregar los numeros 3,2,7,3,1,7,8 (no me acuerdo exactamente, pero había un par repetidos).
Luego, borrar los numeros 3,7,1 (o algo así).
2) Definir arbol binario, arbol binario de búsqueda, arbol trie, arbol multivía.
Para un arbol de 3vías insertar los siguiente numeros: 111,123,321,231,221 (no me acuerdo pero eran conbinaciones de 123)
Lo mismo para un trie.
Describir el alta (de ambos).
3) Definir arbol de expansión y arbol de expansión de coste mínimo.
Para el siguiente grafo (nos daba un grafo) hallar el arbol de expansion de coste mínimo por
algún algoritmo, nombrarlo y explicarlo.
4) Definir arbol Heap, para qué lo usaría.
Insertar estos números (te daban numeros) en un heap de mínimos. Explicar el alta.
Las cuestiones para remarcar son, primero que el tiempo no te alcanza, mi final terminó pareciendo un jeroglífico, ya que donde dice "describir tal algoritmo" hay que poner el pseudocódigo, una locura innecesaria ( a mi gusto), sobre todo en el primer ejercicio, segundo, el arbol de m-vías fue algo que NO vimos, estaba el arbol eneario en el TP, pero creo q no es lo mismo, de hecho el N-ario nunca lo explicaron y nosotros no usamos un eneario, sino un B-tree en el tp (parecidos pero no iguales).
El final en general me pareció bien, no era fácil, pero si habías estudiado creo que podías hacer todo (a excepción del arbol m-vías), el tema era que no te le pongas 2 horas a explicar cada algoritmo en detalle porque no llegás.
|
|
|
|
_________________
Grima
|
|
   |
     |
|
thew0rldismin3
Nivel 7
Registrado: 18 Dic 2008
Mensajes: 437
Carrera: No especificada
|
|
Coincido con el tema del tiempo, es muy dificil aun sabiendo bien todo poder hacer algo medianamente prolijo en 2 horas, con 1 hora más sería mucho mejor. Respecto a lo del árbol de M-vías sí lo vimos en una clase, lo dio Calvo y lo explicó, y dijo que para mayor consulta leamos el libro de Kruse que ahi está el tema. Y en algunos otros libros libros también figura, quizas se pueda conseguir en español la explicación de ese tema.
Saludos!
|
|
|
|
|
|
 |
 |
|
ae77em
Nivel 2
Registrado: 18 Jul 2010
Mensajes: 12
Carrera: Sistemas
|
|
| Grima escribió:
|
Las cuestiones para remarcar son, primero que el tiempo no te alcanza, mi final terminó pareciendo un jeroglífico, ya que donde dice "describir tal algoritmo" hay que poner el pseudocódigo, una locura innecesaria ( a mi gusto), sobre todo en el primer ejercicio, segundo, el arbol de m-vías fue algo que NO vimos, estaba el arbol eneario en el TP, pero creo q no es lo mismo, de hecho el N-ario nunca lo explicaron y nosotros no usamos un eneario, sino un B-tree en el tp (parecidos pero no iguales).
|
Quería acotar algo...en ningún momento dice que haya que escribir seudocódigo...podés hacerlo si querés, pero no es necesario. Te pide que describas el algoritmo. Podés fijarte en el apunte de grafos, ahí los describe, y también pone seudocódigo...si no te morís de infeliz. Pienso que lo que les interesa es que sepas el concepto, porque en teoría a implementar ya aprendiste.
Por otro lado, en las guías de árboles hay tres apartados, y uno de ellos es de árboles de M-vías (yo no lo estudié de vago, sabía mas o menos el concepto, pero ni idea de como hacer un alta ja). Lo que sí critico de ese final es que se haya tomado algo que no aparece en ningún apunte, aunque la realidad es que si uno mira el cronograma de la materia y las lecturas que te ponen para cada clase, pues aparece cuate...hoy un pibe subió los temas al grupo yahoo así que ahí se puede mirar más o menos qué estudiar...si más o menos se fue siguiendo la materia es sólo agregar cosas a conceptos ya aprendidos...
|
|
|
|
|
|
| |
|
|
ae77em
Nivel 2
Registrado: 18 Jul 2010
Mensajes: 12
Carrera: Sistemas
|
|
| ae77em escribió:
|
Lo que sí critico de ese final es que se haya tomado algo que no aparece en ningún apunte, aunque la realidad es que si uno mira el cronograma de la materia y las lecturas que te ponen para cada clase, pues aparece cuate...
|
Acá me refería a el tema de estructuras Tries...
|
|
|
|
|
|
| |
|
|
Grima
Nivel 3
Edad: 34
Registrado: 15 Jul 2008
Mensajes: 43
Carrera: Informática
|
|
Bueno, sobre los tries recuerdo que Calvo los nombró y aclaró que los podía llegar a tomar en el final. Yo por suerte les pegué una leída del kruse.
No sabía que lo del arbol de m-vías apareciera en un apunte... ahí cambia un poco la cosa (aunque no recuerdo que lo hayan nombrado en clase).
Bueno, sobre lo del pseudocódigo, alguien de los q estaba rindiendo preguntó cómo tenía q describir los algoritmos, y Patricia le respondió que podía explicarlo con palabras pero tenía que estar detallado o podía usar pseudocódigo, entre ambas al final pensé q era más corto usar pseudocódigo, sobre todo en el caso del abb.
Igual, no me pareció que estuvo mal lo que tomó, solo remarqué esas cuestiones por si de alguna forma se podrían llegar a mejorar. O al menos que lo tenga en cuenta quien vaya a rendir.
|
|
|
|
_________________
Grima
|
|
| |
|
|
sistemas
Nivel 2
Edad: 37
Registrado: 26 Feb 2009
Mensajes: 19
|
|
hola,alguno sabe donde puedo conseguir apunte sobre
arbol de expacion y arbol de expancion de coste minimo, y si saben la diferencia entre arbol trie, arbol multivía me la dirian,ya que la curse el 2do cuatrimetre del 2009 y de estos temas el unico que nombro fue arbol multivía
|
|
|
|
|
|
  |
|
|
sistemas
Nivel 2
Edad: 37
Registrado: 26 Feb 2009
Mensajes: 19
|
|
aca les dejo el enunciado de un final que me pasaron
COLOQUIO 2010 (SUPONGO QUE ES EL DE 20/07)
1) Explique que es un método de ordenamiento interno, que es coste temporal, el coste espacial y la estabilidad. Elija un método de ordenación rápido, descríbalo con detalle o escriba el pseudocódigo o el código y muestre paso a paso como se lleva a cabo el ordenamiento de esta secuencia:
25, 15, 6, 87, 39, 24, 19, 2,7.
2) Definir el TDA cola ¿para que usaría este tda? Considerar una implementación del TDA Cola en un array circular. Describa detalladamente, o con pseudocódigo, como llevaría a cabo los algoritmos correspondientes a acolar y a desacolar. ¿Cuál es al coste temporal de los algoritmos que describo? Justifique, ejemplifique gráficamente.
3) Explique que es una estructura trie y para que usarla. Justifique su fin. ¿Qué ventajas y que desventajas tiene la estructura trie?
Considere un trie iniciativamente vacio en el cual se cargara claves que están formadas con estos elementos: {0, 1,2}.muestre como queda el trie luego de realizar el alta de:
012, 102, 120, 021,0223
4) Defina árbol binario, árbol binario de búsqueda, altura de un árbol, árbol balanceado por Su altura, árbol AVL ¿Qué implementaría con un árbol AVL? ¿Por qué?
Considere un AVL inicialmente vacio, en el que se ingresan estas claves:
20, 10, 23, 45, 8, 18, 28, 6, 3,2
Muestre gráficamente, paso a paso, la evolución del árbol para cada alta
Describa detalladamente el algoritmo de alta, o escriba su pseudocódigo.
Posteriormente se realizara el borrado de: 10, 8,2
Muestre gráficamente, paso a paso, la evolución del árbol para cada bajada
|
|
|
|
|
|
| |
|
|
lalosoft
Nivel 5
Edad: 37
Registrado: 31 Ago 2007
Mensajes: 145
Ubicación: Buenos Aires
Carrera: Sistemas
|
|
yo rendi ayer (20/07/10) y no es ese el enunciado..
1) te pedian que definas TDA Pila, TDA Cola y TDA Cola con prioridad...y los usos que se le pueden dar.
2)te pedian que explicaras la estrategia "divide y venceras" y algun algoritmo que la use.
3)definir recorrido topologico. Dado un grafo, te pedian que lo recorras topologicamente (profundidad o anchura).
4) dado un arbol, habia que recorrerlo en preorden,postorden y en amplitud.
5)Te daban unos numeros y tenias que hacer las altas en: ABB, AVL, trie, m-vias (te decian que tenia 3 punteros). Luego borrar un par de numeros.
Basicamente, ese fue el enunciado. No me acuerdo si era asi el orden, pero estos son los temas. De polimorfismo y herencia no tomo nada.
Espero que les sirva!
Saludos,
|
|
|
|
|
|
  |
|
|
lalosoft
Nivel 5
Edad: 37
Registrado: 31 Ago 2007
Mensajes: 145
Ubicación: Buenos Aires
Carrera: Sistemas
|
|
| |
|
|
eltesso10
Nivel 6
Edad: 35
Registrado: 10 Ago 2009
Mensajes: 268
Ubicación: MERCEDES
Carrera: Informática
|
|
| hola gente...queria preguntar de donde puedo estudiar tda conjunto, porque en la carpeta tengo media carilla nada mas..cuando te preguntan definirlo basta con decir que almacena un grupo de elementos del mismo tipo, sin posicion asignada a c/uno, y sin repeticiones??y decir en que puede ser implementado..obvio
|
|
|
|
_________________
PODRAN IMITARNOS, IGUALARNOS..JAMAS!
Jdor Nº12
|
|
 |
|
|
thew0rldismin3
Nivel 7
Registrado: 18 Dic 2008
Mensajes: 437
Carrera: No especificada
|
|
La verdad que cuando rendí puse más o menos eso que decís en el TDA Conjunto, y parece que me lo tomó como bien (todavía no lo pude ver el exámen pero se que está aprobado).
O sea, qué es, los axiomas que tiene que tener (que no pueden estar repetidos los elementos, etc) y las primitivas que tampoco son muchas. Después te podrá pedir alguna implementación o alguna que otra cosa.
Creo que en los posts anteriores describimos lo que nos tocó sobre Conjunto.
En cuanto a donde estudiarlo no puedo ayudarte, recuerdo haberlo visto en varios libros pero nose si estaban en inglés o español, y además nose hasta que punto será necesario que te embrolles con un libro que quizás te explica a muy bajo nivel, y no es necesario (para rendir).
Suerte!
|
|
|
|
|
|
| |
|
|
eltesso10
Nivel 6
Edad: 35
Registrado: 10 Ago 2009
Mensajes: 268
Ubicación: MERCEDES
Carrera: Informática
|
|
aaah joya gracias!!
quisiera saber si los que la rindieron, cuando le preguntan que detallen el alta o baja de un avl, explicaron como se maneja el factor de balance??porque la verda que me enriedo mucho en esa parte y quizas no es muy importante para el final
graciass
|
|
|
|
_________________
PODRAN IMITARNOS, IGUALARNOS..JAMAS!
Jdor Nº12
|
|
| |
|
|
lalosoft
Nivel 5
Edad: 37
Registrado: 31 Ago 2007
Mensajes: 145
Ubicación: Buenos Aires
Carrera: Sistemas
|
|
si, es importante porque es la clave que se diferencia el avl de los demas...yo grafique cada paso (aunque me llevo bastante)..tenes que medir el tiempo. Con definirlo al principio, yo creo que alcanza.
La rendi y me fue bien asi que esta bien como te lo digo...
|
|
|
|
|
|
| |
|
|
NutT
Nivel 2
Edad: 34
Registrado: 23 Ago 2009
Mensajes: 15
Carrera: Informática
|
|
hola que tal, acabo de volver del examen final de algo2 de calvo y me quedo una duda.
El primer ejercicio decia que entre otras cosas armar un arbol Heap con una lista de numeros y despues sacar 3 numeros.
el problema esta en que la lista de numeros que te daba para armar el arbol eran algo asi como
12, 32, 7, 24, 7, 32, 12, 27, 30
(noten que 3 de los numeros se repiten)
y yo tengo entendido que en el arbol heap no puede haber repeticiones porque si las hay puede que no se cumpla la regla de que en el caso de los arboles maximos, haya elementos que no tengan necesariamente menor valor que el del padre.
Sera que era un enunciado malintencionado? o hay algo que me perdi y no se?
Saludos gracias
|
|
|
|
|
|
  |
 |
|
thew0rldismin3
Nivel 7
Registrado: 18 Dic 2008
Mensajes: 437
Carrera: No especificada
|
|
Mirá a mi me surgió la misma duda cuando rendí, por esto mismo que mencionás. Se lo pregunte a la profesora cuando lo empecé a resolver, y me dijo que no importaba si estaban repetidos, y entonces seguí haciendo el ejercicio con los números repetidos (que quedaban consecutivos). No ahondé más en el tema después, pero si alguien más lo sabe bien, quizás te ayude un poco mejor.
Saludos!
|
|
|
|
|
|
| |
|
|
|
|
Ir a página Anterior 1, 2, 3 Siguiente
|
Ver tema siguiente
Ver tema anterior
Podés publicar nuevos temas en este foro
No podés responder a temas en este foro
No podés editar tus mensajes en este foro
No podés borrar tus mensajes en este foro
No podés votar en encuestas en este foro
No Podéspostear archivos en este foro
No Podés bajar archivos de este foro
|
Todas las horas son ART, ARST (GMT - 3, GMT - 2 Horas)
Protected by CBACK CrackerTracker365 Attacks blocked.
|
