Ex.	PREGUNTA	R	etiqueta	Orden1	Orden2	MirokV	SOLUCION
121		A	0_Grafo	1	26	A, hay que hacer el ARM y ver cada nodo si puede llegar a un nodo anterior mediante una arista borrada.
121		B	111	2	57	B: p=1---0-2-2-2-2-2-2-2-2--- p=3---0-2-2-5-7-7-7-7-7--- p=4---0-2-2-5-10-12-12-15-15--- p=5---0-2-2-5-10-14-16-16-19--- p=7---0-2-2-5-10-14-16-16-19---
121		B	0_Grafo	3	31	B- pag 74 del libro
121		C	111	4	53	C- se cogen los ultimos 4 objetos, de los que los 3 ultimos iran enteros y el otro fraccionado. Hay que darse cuenta de que los objetos estan ordenados de menor a mayor beneficio/peso.
121		A	0_Grafo	5	19	A.- en cuanto se dibuja se ve: 6 5 5 2 5 5 3 2 2
121		B	Esquema	6	114	B.- Se consigue coste logaritmico, este ejercicio sale mucho tambien, o al menos parecido
122		B	Algoritmo	7	69	B.- Hay una explicacion larga y tendida de porque en los ejercicios resueltos
122		A	Esquema	8	101	A.- Voraz
122		C	0_Grafo	9	11	C.-a-b-d; c-e; f-g-h
122		C	0_Grafo	10	25	C.- En realidad pone respuesta D, pero bueno, yo veo este orden A,C,D,B,F,E. En las respuestas del Equipo Docente pone la A, ni idea de porque.
122	No es un error. Viene así en el examen.		111	11	52	ERRATA.- En la primera invocacion solo separa el pivote. Despues va ordenando el resto para finalmente separarlo en 2 mitades y poner el pivote en medio. Aqui hay errata realmente porque la C corresponderia a la eleccion del pivote, la A ccorresponde a las 2 mitades, pero falta el pivote. Cuando se va a invocar la primera recursividad hay 3 conjuntos, el pivote [5], los elementos menores que el pivote [3,4,1] y los mayores [6,9]
122	No es un error. Viene así en el examen.	A	111	12	50	A.- Otra vez la mochila
123		D	0_Grafo	13	16	D.- Seria:{11,7,10,4,3,1,7}
123		A	Esquema	14	107	A.-Voraz
123		A	Coste	15	93	Dice el Equipo docente que A
123		C	Coste	16	78	C.- Tabla pagina 17
123		A	esquema	17	104	A
123		A	0__Hash	18	4	A.- Obviamente, sino seria una colision constante
124		B	Algoritmo	19	68	B
124		D	0_Grafo	20	42	A- Falsa, es NO dirigido B- Falsa, Un ciclo es un camino SIMPLE que empieza y termina en el mismo vertice C- Falsa, Si un grafo tiene pocas aristas las listas de adyacencia resultan una estructura MENOS costosa D-Correcta
124		C	111	21	56	C-Correcta. Por definición del libro hará menos calculos.
124		A	esquema	22	110	A-Voraz, busca el elemento mas frecuente y le asigna el menor numero de bits.
124		B	0_Grafo	23	17	B- V[9] debe ser flotado: 2 3 12 3 12 12 12 3 (2)
124		B	Coste	24	82	B, En grafos disperos es mejor usar lista de adyacencia.
131		D	0__Hash	25	1	D.- El recorrido cuadratico permite mayor dispersion. Si el factor de carga es 1 se puede resolver doblando el tamaño de la tabla con hashing abierto. Doble hashing es en hashing cerrado.
131		A	Esquema	26	97	A.- Segun el equipo docente
131		D	Esquema	27	112	D.- Habiendo mas de una solucion hay que explorarlas todas, y eso lo hace VA
131		C	0_Grafo	28	38	C.- Se leen las filas completas de arriba hacia abajo (recorrido en anchura)
131		A	0_Grafo	29	48	A
131		B	Esquema	30	94	B.- Divide y venceras, se va dividiendo el vector y se comprueba el elemento central entre ambas mitades. En caso de T[i]= x<I se elige la mitad derecha, sino la izquierda
132		A	Esquema	31	103	A.-Creo que ya ha salido antes
132		B	111	32	55	B.- Prim parte de un nodo raiz y son igual de eficientes
132		B	esquema	33	95	B.- Visto varias veces ya ejercicios de este tipo, para repartir algo por partes iguales hay que usar VA
132		C	3	34	65	C.- Es teoría
132		B	0_Grafo	35	12	respuesta B b-c forma una componente y a-e-d otra
132		A	0_Grafo	36	24	A.- Dijkstra busca la arista de menor peso que conecte lo que ya tenemos conectado con un nodo nuevo.
133		C	0_Grafo	37	21	C.- Claramente, el monticulo queda asi: 2 6 4 12 7 5 8
133			coste	38	83	B.-Eso dice el ED
133		C	111	39	58	C.- Se obtiene la siguiente tabla: 1.-0-1-1-1-1-1-1-1-1-1-1-1--- 2.-0-1-6-7-7-7-7-7-7-7-7-7--- 5.-0-1-6-7-7-18-19-24-25-25-25-25--- 6.-0-1-6-7-7-18-22-24-28-29-29-40--- 7.-0-1-6-7-7-18-22-28-29-34-35-40---
133		C	0_Grafo	40	30	C.- Primero une 1 con 3, despues con 4, cuando une con 3 ya tiene visibilidad a todos los nodos.
133		C	0__Hash	41	5	C.- Si la A fuese cierta, no existiria el hashing cerrado. Sobre la B, el hashing lineal es el que mayor probabilidad de colisiones tiene. La D...nunca las he visto iguales. La C, se podria garantizar que se recorren todos los elementos si el tamaño de la tabla es numero primo, pero no estoy seguro.
133		A	Esquema	42	111	A.- Voraz obviamente, pero solo porque las monedas son multiplos unas de otras. Sino habria que usar programacion dinamica.
134		D	0_Grafo	43	33	C- Recorrido en anchura: 1-2-3-4-5-7-6
134		A	Esquema	44	116	A-Voraz, viene en el libro
134		D	3	45	66	D es falsa, no se solapan las soluciones, sino que se combinan
134		B	coste	46	89	B- k=0; i=2; d=1 T(n)=O(i^(n/d)) T(n)=O(2^n)
134		C	0_Grafo	47	37	C- Con prim se busca la arista de menor tamaño que puede conectar con alguno de los nodos ya incluidos, en este caso: 1-5 = 10 5-4 = 10 4-3 = 2 3-2 = 8 4-6 = 50
134		C	111	48	54	C- Lo que hace Quicksort es elegir pivote y despues empezar a buscar a la derecha del pivote el primer numero menor que el pivote, y a la izquierda del pivote, el primer numero mayor, intercambiando sus posiciones. OJO que si el pivote esta al principio o al final del vector a la derecha del pivote buscara un numero mayor y a la izquierda un numero mayor, finalmente colocaria el pivote en medio.
141		A	0__Hash	49	9	A.- n/M
141		B	0_Grafo	50	29	B.- OJO que es el penultimo caso
141		A	coste	51	74	A.- Logaritmico con divide y venceras!!
141		B	Coste	52	72	B.- Si siempre eliges el pivote de menor valor, o si el vector esta ordenado de menor a mayor y siempre coges el primer elemento; obtendras coste N^2
141		D	0_Grafo	53	10	D.- Es el numero de aristas
141			0_Grafo	54	39	C.- ERRATA obviamente, esta pregunta se ha anulado en el examen, pero si lo consideramos como indica el apartado B, entonces la unica falsa es C, porque al insertar un elemento hay que restaurar la propiedad monticulo y esto se hace con flotar, coste logn
142		C	Coste	55	87	C.- Eso sucede cuando el vector esta ordenado y cogemos como pivote el primer elemento
142		D	0_Grafo	56	13	D.- En concreto: (b-e-d-c);(a);(f);(g)
142		B	esquema	57	99	B.- Se puede encontrar no significa que siempre se encuentre....Aver quien cae aqui con vuelta atras, que se nos mueren los soldados!!
142		C	Coste	58	86	C.- Yo lo que haria seria ordenar el vector, luego despreciar todos los casos de numeros que n>S. Entonces Separo el vector que me queda a la mitad, y aqui ya usar pues en otro vector almacenar los valores de S- cada elemento de la primera mitad, y comparar con los elementos de la segunda mitad mediante divide y venceras por ejemplo para ver si tengo coincidencia. Daria aproximadamente NlogN
142		B	0_Grafo	59	35	B.- Elige primero la arista de peso 2, despues la de peso 4,5,6,10
142		D	Coste	60	88	D.---A es falsa porque lo primero seria un recorrido en profundidad y segundo en cuanto descarta una opcion no sigue examinandola. La B es N^3(pag148). La C no tiene porque ser verdad. Y la D es cierta, ya se ven en el libro casos en los que voraz no da la solucion optima.
143		A	Esquema	61	119	A.-Voraz
143		A	0_Grafo	62	20	A.- Repetido
143		D	esquema	63	117	D.- Si no son totalmente fraccionables voraz no da la solucion optima.
143		A	0_Grafo	64	45	A.-
143		C	Coste	65	84	C.- Es falsa porque borrar Arista es O(n); lo que si es O(n+a) es borrar Vertice....como van a pillar...
143		B	0_Grafo	66	43	B.- Repetida...solo cambia camino compuesto por simple, en cuyo caso B es cierta...esta es a pillar tambien xD
144		C	0_Grafo	67	27	C. Kruskal busca la arista de menor peso, en este caso 2-3 con peso 1, despues la siguiente de menor peso, 2-5 con peso 2.
144		B	coste	68	90	B- Se observa el elemento central, si coincide, se busca en la segunda mitad, sino en la primera. Asi hasta encontrar un elemento que no coincida y el que esta en la posicion anterior si, este ultimo sera el ultimo que coincida, a partir de alli no coincidira ninguno
144		C	Coste	69	91	C.
144			0_Grafo	70	44	C-D debe de haber una errata porque ninguno de los 2 es monticulo de minimos
144		C	coste	71	75	C Comprobar si un vertice es adyacente a otro tiene complejidad O(1) usando matriz de adyacencia
144		D	0__Hash	72	3	C Por mayoria, La funcion hash marca un patrón
151		C	111	73	49	Opción C. Sustituir 7 por 2 Se cruzan los recorridos(1-8) y se cambia el pivote por el menor(el 1). Quedando los vectores argumentos: [1,2,2,3] y [8,7,6,9]
151		A	0_Grafo	74	23	A.- Clarisimo, Dijkstra coge las aristas de menor peso que se unen al conjunto ya descubierto
151		D	Esquema	75	113	D.- Yo diria ramificacion y poda. no tengo respuestas para este examen asique no se si es cierto
151		C	3	76	63	A. E(2,4) = Caso 1= A2(A3*A4) = A2(2x3*3x2) = A2(5X1) ##Operacion1(2x3x2)## = = 5x2*2,2 ##Operacion2(5x2x2) = (5,2) Suma operaciones = 32 E(2,4) = Caso2 = (A2A3)A4 = (5x2*2x3)A4 ##Operacion1(5x2x3)## = (5x3*3x2) ##Operacion2(5x3x2)## = (5,2) Suma operaciones= 60 Se elige el caso con menores operaciones. Coincide con la opción C. A tener en cuenta: Ejemplo multiplicación matrices (2x4)*(4x2) = (2,2)
151		C	3	77	64	C.- Programación dinámica
151			coste	78	71	C y D ambas falsas
152		C	Esquema	79	96	C.- Vuelta atras, todos los de dividir empresas o sociedades son vuelta atrás
152		A	3	80	62	A. E(2,4) = Caso 1= A2(A3*A4) = A2(5X3*3X1) = A2(5X1) ##Operacion1(5x3x1)## = 2x5*5x1 ##Operacion2(2x5x1) = (2x1) Suma operaciones = 25 E(2,4) = Caso2 = (A2A3)A4 = 2x5*5x3 ##Operacion1(2x5x3)## = 2x3*3x1 ##Operacion2(2x3x1)## = (2x1) Suma operaciones= 36 Se elige el caso con menores operaciones. Coincide con la opción A. A tener en cuenta: multiplicación matrices (2x4)*(4x2) = (2,2)
152		D	0_Grafo	81	14	D.- Se busca la que no aparece. Las que aparecen son: {4,10,2,inf,8,inf,inf} {4,10,2,4,3,7,inf}(aparece 2 veces) {4,9,2,4,3,7,inf}(aparece 3 veces){4,9,2,4,3,7,19}Quizas una estrategia para resolverlo mas rapido es ver que la D seria una respuesta posterior a la C, porque tiene ya encontrados todos los caminos. Y viendo que el camino al nodo 3 en C es 9, y en D es 10, solo hay que mirar el camino mas corto que se encuentra para llegar el nodo 3 y despreciar el resto. En cuanto ves que es 9, esta claro que la respuesta final no puede ser 10.
152		A	111	82	51	Opción A Se debe hacer pivotar. Por tanto: Sustituir 6 por 5 Sustituir 12 por 2 Sustituir 7 por 3 Sustituir 9 por 1 Se puede observar que ya se cruzan los recorridos (3-7) por lo que se sustituye el pivote por el menor(el 3). Quedando así los vectores argumentos: [3,5,2,1,3,1] y [7,9,11,7,12,8,6,6,9]
152		B	Coste	83	81	B.- Pag 120 del libro
152		B	111	84	61	B.- esta cogiendo siempre casos "gratuitos" de valor 0. A mi me entro la duda de si se podian seleccionar los de valor 0, pero vienen en todas las respuestas asi que supongo que si.
153		D	Coste	85	70	D.- Kruskal esta en =(alogn). Prim con lista tambien es (alogn)(pag69). Quicksort en el caso peor es con el vector ordenado y coste cuadratico n^2
153		A	0_Grafo	86	47	A.- hay que ir mirando las aristas de menor valor...1 se encuentra en 5-7; 2 en 2-4; 3 en 4-6; 4 en 2-4; 5 en 2-3 y con esto ya nos da la solucion A. OJO si por lo que sea hubiesemos encontrado una arista que llevase a 3 antes, esta no seria solucion válida, sino la B. Espero que no pongan trampas de ese tipo
153		D	0__Hash	87	2	D.- Cuadratico permite mayor dispersión. El factor de carga se usa en hashing abierto y dobla el tamaño de la tabla. El doble hashing se usa en hashing cerrado.
153		A	Esquema	88	98	A.- Lo hemos comentado por telegram. Pero me sigue extrañando que pueda mejorar la estimacion optimista....Pregunta repetida
153		A	0_Grafo	89	36	A.- Bueno, esta creo que esta cantada...va buscando el camino mas corto entre 1 y el resto de nodos.
153		C	0_Grafo	90	15	C.- Hay que dibujarlo para no liarse. Resulta un monticulo completo en todos sus niveles, por lo que el 6 se inserta debajo del nodo de la izquierda del todo. Se flota 1 vez nada mas. Queda asi: 10 6 3 6 2 3 2 5
154		A	Esquema	91	105	A-Esto hay que tenerlo claro que sale mucho
154		C	0_Grafo	92	41	C- n log n
154		A	Esquema	93	102	A Voraz, es lo que hemos hecho en la PED1
154		B	Coste	94	73	B Quicksort llega hasta n^2 en casos peores.
154		B	Esquema	95	120	B Vuelta atras, punto 6.5 del libro es identico.
154		B	0_Grafo	96	32	B Kruskal busca el nodo de menor peso
161		D	0_Grafo	97	46
161		A	Coste	98	85
161		A	0_Grafo	99	18
161		B	111	100	60
161		B	Esquema	101	108
161		D	Coste	102	92
162		C	Coste	103	79
162		D	3	104	67
162		C	0__Hash	105	8
162		D	Esquema	106	115
162		C	Esquema	107	118
162		D	Esquema	108	100
163		C	0_Grafo	109	40
163		B	0__Hash	110	7
163		D	Coste	111	80
163		A	Esquema	112	109
163		A	0_Grafo	113	22
163		B	Coste	114	76
164		B	Esquema	115	106
164		C	0__Hash	116	6
164		B	Coste	117	77
164		D	0_Grafo	118	34
164		D	0_Grafo	119	28
164		C	111	120	59