Pag. 1 Fecha: 17/AGO/2011 Hora: 15:48 hrs. INSTITUTO TECNOLOGICO DE NUEVO LAREDO ING. EN SISTEMAS COMPUTACIONALES ING. BRUNO LOPEZ TAKEYAS <<< P R E G U N T A S >>> =============================================================================== Unidad Folio Pregunta =============================================================================== ------------------------------------------------------------------------------- MD MATEMATICAS DISCRETAS 6 . 1 En este recorrido de grafos, los estados descendientes son almacenados y removidos por la derecha de la estruc tura abierta; es decir, dicha estructura se comporta como una pila a) Busqueda forward b) Busqueda backward c) Busqueda en profundidad d) Busqueda en anchura 6 . 2 Tipo de recorrido de grafos que se basa en la experien cia o intuicion para encontrar una solucion a) Busqueda heuristica b) Busqueda backward c) Busqueda en profundidad d) Busqueda en anchura 6 . 3 Tipo de algoritmo que recorre todos los posibles nodos del grafo a) Busqueda heuristica b) Busqueda exhaustiva c) Busqueda best first d) Ninguna de las anteriores 6 . 4 Tipo de algoritmo que requiere que se le proporcionen el o los objetivos del problema y encuentra los nodos originales a) Busqueda heuristica b) Busqueda exhaustiva c) Busqueda forward d) Busqueda backward 6 . 5 Esta busqueda tambien se conoce como guiada por datos el o los objetivos del problema y encuentra los nodos originales a) Busqueda heuristica b) Busqueda exhaustiva c) Busqueda forward d) Busqueda backward 6 . 6 En esta busqueda los estados descendientes son agrega- dos por la derecha y removidos por la izquierda de la Pag. 2 Fecha: 17/AGO/2011 Hora: 15:48 hrs. INSTITUTO TECNOLOGICO DE NUEVO LAREDO ING. EN SISTEMAS COMPUTACIONALES ING. BRUNO LOPEZ TAKEYAS <<< P R E G U N T A S >>> =============================================================================== Unidad Folio Pregunta =============================================================================== estructura abierta; es decir, la estructura se comporta como una cola a) Busqueda forward b) Busqueda backward c) Busqueda en profundidad d) Busqueda en anchura 6 . 7 Estructura utilizada en algoritmos de busqueda de solu- ciones para almacenar los nodos pendientes de analizar a) Abierta b) Cerrada c) SL d) DE 6 . 8 En esta busqueda los estados descendientes son agrega- dos por la derecha y removidos por la izquierda de la estructura abierta; es decir, la estructura se comporta como una cola a) Busqueda forward b) Busqueda backward c) Busqueda en profundidad d) Busqueda en anchura 6 . 9 Estructura utilizada en algoritmos de busqueda de solu- ciones para reconstruir la trayectoria solucion a) Abierta b) Cerrada c) SL d) DE 6 . 10 Se pueden representar los nodos de un grafo como un conjunto de elementos a) Verdadero b) Falso 6 . 11 Se pueden representar los arcos de un grafo como un conjunto de tuplas a) Verdadero b) Falso 6 . 12 Los arcos de un grafo tambien pueden ser consideradas relaciones entre los nodos a) Verdadero b) Falso Pag. 3 Fecha: 17/AGO/2011 Hora: 15:48 hrs. INSTITUTO TECNOLOGICO DE NUEVO LAREDO ING. EN SISTEMAS COMPUTACIONALES ING. BRUNO LOPEZ TAKEYAS <<< P R E G U N T A S >>> =============================================================================== Unidad Folio Pregunta =============================================================================== 6 . 13 Los nodos tambien son conocidos como aristas a) Verdadero b) Falso 6 . 14 Los arcos de un grafo tambien se conocen como vertices a) Verdadero b) Falso 6 . 15 Los nodos de un grafo representan las reglas o movimien tos permitidos en un problema a) Verdadero b) Falso 6 . 16 Los arcos de un grafo representan las reglas o movimien tos permitidos en un problema a) Verdadero b) Falso 6 . 17 Los grafos dirigidos tambien se conocen como digrafos a) Verdadero b) Falso 6 . 18 Todos los grafos son dirigidos a) Verdadero b) Falso 6 . 19 El juego del gato puede representarse mediante grafos a) Verdadero b) Falso 6 . 20 El juego del cubo de Rubik puede representarse mediante grafos a) Verdadero b) Falso 6 . 21 Los grafos tambien son conocidos como graficas a) Verdadero b) Falso 6 . 22 Se puede utilizar cualquier esquema de representacion de relaciones para definir los arcos de un grafo a) Verdadero b) Falso 6 . 23 Se puede representar un grafo como una matriz Pag. 4 Fecha: 17/AGO/2011 Hora: 15:48 hrs. INSTITUTO TECNOLOGICO DE NUEVO LAREDO ING. EN SISTEMAS COMPUTACIONALES ING. BRUNO LOPEZ TAKEYAS <<< P R E G U N T A S >>> =============================================================================== Unidad Folio Pregunta =============================================================================== a) Verdadero b) Falso 6 . 24 Tipo de busqueda cuando la estructura Abierta se repre- senta mediante una Pila a) Busqueda forward b) Busqueda backward c) Busqueda en profundidad d) Busqueda en anchura 6 . 25 Tipo de busqueda cuando la estructura Abierta se repre- senta mediante una Cola a) Busqueda forward b) Busqueda backward c) Busqueda en profundidad d) Busqueda en anchura 6 . 26 En el algoritmo de recorrido en profundidad y anchura, la estructura Abierta se utiliza para almacenar ... a) Nodos en espera de ser analizados b) Nodos que forman parte de la trayectoria solucion c) Nodos que fallaron en ser la solucion d) El nodo actual 6 . 27 En el algoritmo de recorrido en profundidad y anchura, la estructura Cerrada se utiliza para almacenar ... a) Nodos en espera de ser analizados b) Nodos analizados c) El nodo actual d) Ninguno de los anteriores 6 . 28 En el Algoritmo de Profundidad y Anchura, cuando se llega a un nodo terminal (hoja) y no se encuentra la solucion, se realiza un retroceso para asegurarse bus-- car otra rama del espacio de estados a) Verdadero b) Falso 6 . 29 El Algoritmo en Profundidad y Anchura analiza los nodos tanto de ida como de vuelta a) Verdadero b) Falso 6 . 30 Que significa que un algoritmo sea exhaustivo a) Que utiliza heuristica Pag. 5 Fecha: 17/AGO/2011 Hora: 15:48 hrs. INSTITUTO TECNOLOGICO DE NUEVO LAREDO ING. EN SISTEMAS COMPUTACIONALES ING. BRUNO LOPEZ TAKEYAS <<< P R E G U N T A S >>> =============================================================================== Unidad Folio Pregunta =============================================================================== b) Que recorre todas las posibilidades c) Que sea sistematico d) Que encuentra la mejor solucion 6 . 31 Que significa que un algoritmo sea determinista a) Que utiliza heuristica b) Que recorre todas las posibilidades c) Que sea sistematico d) Que encuentra la mejor solucion 6 . 32 El Algoritmo de Busqueda en Profundidad y en Anchura es exhaustivo a) Verdadero b) Falso 6 . 33 El Algoritmo de Busqueda en Profundidad y en Anchura es determinista a) Verdadero b) Falso 6 . 34 El Algoritmo de Busqueda en Profundidad y en Anchura es optimo; es decir, garantiza encontrar la mejor solucion disponible a) Verdadero b) Falso 6 . 35 El Algoritmo de Busqueda en Profundidad y Anchura ana-- liza nodos que previamente fueron analizados a) Verdadero b) Falso 6 . 36 El Algoritmo de Busqueda en Profundidad y Anchura puede encontrar un camino mas corto que el que tiene almace-- nado en su Estructura Cerrada a) Verdadero b) Falso 6 . 37 El Algoritmo de Busqueda en Profundidad y Anchura puede cambiar drasticamente de rama durante un recorrido si detecta que va por un camino equivocado a) Verdadero b) Falso 6 . 38 En el Algoritmo de Busqueda en Profundidad y Anchura, si se tiene la estructura Abierta como una PILA y se Pag. 6 Fecha: 17/AGO/2011 Hora: 15:48 hrs. INSTITUTO TECNOLOGICO DE NUEVO LAREDO ING. EN SISTEMAS COMPUTACIONALES ING. BRUNO LOPEZ TAKEYAS <<< P R E G U N T A S >>> =============================================================================== Unidad Folio Pregunta =============================================================================== insertan primero los descendientes derechos se trata de un algoritmo ... a) En profundidad por la derecha b) En profundidad por la izquierda c) En anchura por la derecha d) En anchura por la izquierda 6 . 39 En el Algoritmo de Busqueda en Profundidad y Anchura, si se tiene la estructura Abierta como una PILA y se insertan primero los descendientes izquierdos se trata de un algoritmo ... a) En profundidad por la derecha b) En profundidad por la izquierda c) En anchura por la derecha d) En anchura por la izquierda 6 . 40 En el Algoritmo de Busqueda en Profundidad y Anchura, si se tiene la estructura Abierta como una COLA y se insertan primero los descendientes izquierdos se trata de un algoritmo ... a) En profundidad por la derecha b) En profundidad por la izquierda c) En anchura por la derecha d) En anchura por la izquierda 6 . 41 En el Algoritmo de Busqueda en Profundidad y Anchura, si se tiene la estructura Abierta como una COLA y se insertan primero los descendientes derechos se trata de un algoritmo ... a) En profundidad por la derecha b) En profundidad por la izquierda c) En anchura por la derecha d) En anchura por la izquierda 6 . 42 El Algoritmo de Busqueda en Profundidad y Anchura elimi na el nodo de la lista de espera cuando cambia de nodo actual a) Verdadero b) Falso 6 . 43 El Algoritmo de Busqueda en Profundidad y Anchura nunca analiza nuevamente un nodo que ya fue analizado en una etapa anterior a) Verdadero b) Falso Pag. 7 Fecha: 17/AGO/2011 Hora: 15:48 hrs. INSTITUTO TECNOLOGICO DE NUEVO LAREDO ING. EN SISTEMAS COMPUTACIONALES ING. BRUNO LOPEZ TAKEYAS <<< P R E G U N T A S >>> =============================================================================== Unidad Folio Pregunta =============================================================================== 6 . 44 El Algoritmo de Busqueda en Profundidad y Anchura nunca analiza nuevamente un nodo que ya estaba almacenado en la estructura de nodos en espera a) Verdadero b) Falso 6 . 45 El Algoritmo de Prof y Anch elimina los nodos en espera de ser analizados hasta que detecta que fallaron en conducir al nodo objetivo a) Verdadero b) Falso 6 . 46 Cuantas variantes de operacion tiene el Algoritmo de la Busqueda en Profundidad y Anchura ? a) 1 b) 2 c) 3 d) 4 6 . 47 El criterio para determinar si un Algoritmo se comporta en Profundidad o Anchura es ... a) El orden de analisis de los nodos en la trayectoria b) El orden de analisis de los nodos que fallaron c) La administracion de los nodos en espera d) El orden de insercion de los nodos en espera 6 . 48 El criterio para determinar si un Algoritmo de Profun-- didad o Anchura se recorre por la derecha o por la iz-- quierda es ... a) El orden de analisis de los nodos en la trayectoria b) El orden de analisis de los nodos que fallaron c) La administracion de los nodos en espera d) El orden de insercion de los nodos en espera 6 . 49 En algunos casos, el Algoritmo Busqueda en profundidad y anchura primero analiza el descendiente central del nodo actual a) Verdadero b) Falso 6 . 50 La matriz booleana que representa los arcos directos entre los nodos de un grafo se llama ... a) Matriz de caminos b) Matriz de arcos Pag. 8 Fecha: 17/AGO/2011 Hora: 15:48 hrs. INSTITUTO TECNOLOGICO DE NUEVO LAREDO ING. EN SISTEMAS COMPUTACIONALES ING. BRUNO LOPEZ TAKEYAS <<< P R E G U N T A S >>> =============================================================================== Unidad Folio Pregunta =============================================================================== c) Matriz de adyacencia d) Matriz booleana 6 . 51 La matriz de adyacencia que representa un grafo siempre es una matriz cuadrada a) Verdadero b) Falso 6 . 52 Que es una matriz cuadrada ? a) Se representa por un cuadrado b) Tiene el mismo numero de renglones que columnas c) Se representa por una cuadricula d) Es de 1`s y 0`s 6 . 53 Los renglones de la matriz de adyacencia representan los nodos origen a) Verdadero b) Falso 6 . 54 Las columnas de la matriz de adyacencia representan los nodos origen a) Verdadero b) Falso 6 . 55 La matriz de adyacencia representa la matriz de caminos de tamano 1 a) Verdadero b) Falso 6 . 56 El Algoritmo de Warshall sirve para detectar la ruta para desplazarse de un nodo i a un nodo j a) Verdadero b) Falso 6 . 57 Si se desea saber si existe un camino para desplazarse de un nodo i a un nodo j, entonces se recomienda apli-- car el Algoritmo de Warshall a) Verdadero b) Falso 6 . 58 La formula del Algoritmo de Warshall es ... a) Pk(i,j) = Pk(i,j) OR [ Pk(i,k) AND Pk(k,j) ] b) Pk-1(i,j) = Pk(i,j) OR [ Pk(i,j) OR Pk(k,j) ] c) Pk(i,j) = Pk-1(i,j) OR [ Pk-1(i,k) AND Pk-1(k,j) ] d) Pk(i,j) = Pk-1(i,j) OR [ Pk-1(i,k) OR Pk-1(k,j) ] Pag. 9 Fecha: 17/AGO/2011 Hora: 15:48 hrs. INSTITUTO TECNOLOGICO DE NUEVO LAREDO ING. EN SISTEMAS COMPUTACIONALES ING. BRUNO LOPEZ TAKEYAS <<< P R E G U N T A S >>> =============================================================================== Unidad Folio Pregunta =============================================================================== 6 . 59 El principio del Algoritmo de Warshall indica que puede encontrarse un camino del nodo i al nodo j si existe un arco del nodo i al nodo j o bien un camino con escalas del nodo i al nodo k y del nodo k al nodo j a) Verdadero b) Falso 6 . 60 Que es el orden de un grafo a) La cantidad de arcos b) La cardinalidad del conjunto de nodos c) La cantidad de ciclos d) La representacion ordenada de los nodos 6 . 61 En la formula del Algoritmo de Warshall, Que representa la variable k ? a) El orden del grafo b) La cantidad de arcos del grafo c) Los nodos origen d) Los nodos destino 6 . 62 En la formula del Algoritmo de Warshall, Que representa la variable i ? a) El orden del grafo b) La cantidad de arcos del grafo c) Los nodos origen d) Los nodos destino 6 . 63 En la formula del Algoritmo de Warshall, Que representa la variable j ? a) El orden del grafo b) La cantidad de arcos del grafo c) Los nodos origen d) Los nodos destino 6 . 64 Cuantos ciclos anidados tiene el Algoritmo de Warshall si se tiene un grafo de orden 4 ? a) 1 b) 3 c) 4 d) 12 6 . 65 Cuantas matrices de caminos calcula el Algoritmo de Warshall si se tiene un grafo de orden 4 ? a) 1 Pag. 10 Fecha: 17/AGO/2011 Hora: 15:48 hrs. INSTITUTO TECNOLOGICO DE NUEVO LAREDO ING. EN SISTEMAS COMPUTACIONALES ING. BRUNO LOPEZ TAKEYAS <<< P R E G U N T A S >>> =============================================================================== Unidad Folio Pregunta =============================================================================== b) 3 c) 4 d) 12 6 . 66 El Algoritmo de Warshall es capaz de desplegar la se -- cuencia de nodos por los que pasa para encontrar una ruta en particular a) Verdadero b) Falso 6 . 67 Aplicando la formula del Algoritmo de Warshall, Cuando calcula la matriz P3, se requieren los datos de la ma-- triz P2 ? a) Verdadero b) Falso 6 . 68 Aplicando la formula del Algoritmo de Warshall, Para calcular los datos de una matriz de caminos P, siempre se requieren los datos de la matriz anterior ? a) Verdadero b) Falso 6 . 69 El Algoritmo de Floyd sirve para detectar la ruta mas corta para desplazarse de un nodo i a un nodo j a) Verdadero b) Falso 6 . 70 Si se desea saber la secuencia de nodos en un camino pa ra ir de un nodo i a un nodo j, entonces se recomienda aplicar el Algoritmo de Floyd a) Verdadero b) Falso 6 . 71 La formula del Algoritmo de Floyd es ... a) Qk(i,j) = MINIMO [ Qk(i,j), Qk(i,k) + Qk(k,j) ] b) Qk-1(i,j) = MINIMO [ Qk(i,j), Qk(i,j) + Pk(k,j) ] c) Qk(i,j) = MINIMO [ Qk-1(i,j), Qk-1(i,k) + Qk-1(k,j) ] d) Qk(i,j) = MINIMO [ Qk-1(i,j), Qk-1(i,k) + Qk-1(k,j) ] 6 . 72 El principio del Algoritmo de Floyd indica que puede encontrarse el camino mas corto del nodo i al nodo j ya sea por el peso del arco directo del nodo i al nodo j o bien por la suma de los pesos del camino del nodo i al nodo k y del nodo k al nodo j a) Verdadero Pag. 11 Fecha: 17/AGO/2011 Hora: 15:48 hrs. INSTITUTO TECNOLOGICO DE NUEVO LAREDO ING. EN SISTEMAS COMPUTACIONALES ING. BRUNO LOPEZ TAKEYAS <<< P R E G U N T A S >>> =============================================================================== Unidad Folio Pregunta =============================================================================== b) Falso 6 . 73 En la formula del Algoritmo de Floyd, Que representa la variable k ? a) El orden del grafo b) La cantidad de arcos del grafo c) Los nodos origen d) Los nodos destino 6 . 74 En la formula del Algoritmo de Floyd, Que representa la variable i ? a) El orden del grafo b) La cantidad de arcos del grafo c) Los nodos origen d) Los nodos destino 6 . 75 En la formula del Algoritmo de Floyd, Que representa la variable j ? a) El orden del grafo b) La cantidad de arcos del grafo c) Los nodos origen d) Los nodos destino 6 . 76 Cuantos ciclos anidados tiene el Algoritmo de Floyd si se tiene un grafo de orden 5 ? a) 1 b) 3 c) 5 d) 15 6 . 77 Cuantas matrices de caminos minimos calcula el Algorit- mo de Floyd si se tiene un grafo de orden 5 ? a) 1 b) 3 c) 5 d) 15 6 . 78 El Algoritmo de Floyd es capaz de desplegar la se -- cuencia de nodos por los que pasa para encontrar una ruta en particular a) Verdadero b) Falso 6 . 79 Aplicando la formula del Algoritmo de Floyd, Cuando calcula la matriz Q4, se requieren los datos de la ma- Pag. 12 Fecha: 17/AGO/2011 Hora: 15:48 hrs. INSTITUTO TECNOLOGICO DE NUEVO LAREDO ING. EN SISTEMAS COMPUTACIONALES ING. BRUNO LOPEZ TAKEYAS <<< P R E G U N T A S >>> =============================================================================== Unidad Folio Pregunta =============================================================================== triz Q3 ? a) Verdadero b) Falso 6 . 80 Aplicando la formula del Algoritmo de Floyd, Para calcular los datos de una matriz de caminos minimos Q, siempre se requieren los datos de la matriz anterior ? a) Verdadero b) Falso 6 . 81 El Algoritmo de Warshall se basa en una matriz booleana a) Verdadero b) Falso 6 . 82 El Algoritmo de Floyd se basa en una matriz booleana a) Verdadero b) Falso 6 . 83 En el Algoritmo de Warshall, la primera matriz se llama Matriz de Pesos a) Verdadero b) Falso 6 . 84 En el Algoritmo de Floyd, la primera matriz se llama Matriz de Pesos a) Verdadero b) Falso 6 . 85 El Algoritmo de Floyd, calcula la Matriz de Camino Minimo a) Verdadero b) Falso 6 . 86 La primera matriz del Algoritmo de Warshall se llama Matriz de Adyacencia a) Verdadero b) Falso 6 . 87 La primera matriz del Algoritmo de Floyd se llama Matriz de Pesos a) Verdadero b) Falso =============================================================================== TOTAL: 87 PREGUNTAS