Font size
WorksheetsQuiz sobre Estructura de Datos: Grafos
Total questions: 50
Worksheet time: 29mins
¿Qué representan los grafos?
Relaciones entre objetos
Funciones matemáticas
Datos numéricos
Estructuras jerárquicas
¿Cuál de las siguientes aplicaciones no es un uso de los grafos?
Modelado de redes eléctricas
Geografía
Química
Contabilidad
¿Qué es un vértice en un grafo?
Un objeto que representa un nodo
Una relación entre nodos
Un ciclo en el grafo
Un camino entre dos nodos
¿Qué tipo de grafo tiene un sentido en sus aristas?
Grafo no dirigido
Grafo dirigido
Grafo cíclico
Grafo ponderado
¿Qué es una arista en un grafo no dirigido?
Un nodo aislado
Un vértice de entrada
Un arco que conecta dos vértices
Un ciclo cerrado
¿Qué se entiende por 'grado' de un vértice en un grafo no dirigido?
Número total de vértices
Número de aristas que contiene el vértice
Número de ciclos en el grafo
Número de vértices adyacentes
¿Qué es un ciclo en un grafo?
Una arista sin dirección
Un vértice aislado
Una lista de nodos
Un recorrido que vuelve al nodo de partida
¿Cuál es la representación estática de un grafo?
Lista de adyacencia
Conjunto de arcos
Matriz de adyacencia
Conjunto de vértices
¿Qué operación se utiliza para añadir un nuevo vértice a un grafo?
void BorrarVertice
void Union
void AñadirVertice
void BorrarArco
¿Qué tipo de recorrido busca caminos desde un nodo de salida hasta que ya no es posible avanzar más?
Cíclico
En anchura
Aleatorio
En profundidad
¿Qué es un grafo conexo?
Un grafo que tiene ciclos
Un grafo donde existe un camino entre cualquier par de nodos
Un grafo que no tiene aristas
Un grafo que tiene un solo vértice
¿Qué representa el factor de peso en un grafo?
El valor asociado a un arco
El número de aristas
La longitud del grafo
El número de vértices
¿Qué se utiliza para conocer si dos vértices son adyacentes?
void Union
void AñadirVertice
void BorrarArco
bool EsAdyacente
¿Qué tipo de grafo no tiene restricciones para formar aristas?
Grafo cíclico
Grafo ponderado
Grafo no dirigido
Grafo dirigido
¿Qué es un grafo?
Estructura dinámica lineal que relaciona información.
Estructura dinámica no lineal que permite modelar relaciones entre objetos.
TDA dinámica que relaciona información de forma jerarquica.
Partes de un grafo
Nodos, ramas, peso
Vértices, lineas
Vértices, aristas, peso
Un grafo se representa por:
G=(V,A) V=Vértices A=Aristas
G=(1,2,3,4)
(a,b) (b,c) (c,b)
Ejemplos de grafos:
red de transporte, red de carreteras, intranet, internet, sistema de navegabilidad....
árbol genealógico, circuitos eléctricos, matrimonio, estados de ánimo...
decisiones, teléfonos, red de agua potable, enfermedades...
¿Qué es un digrafo?
Un grafo que tiene definido el origen y destino de cada una de las relaciones.
Un grafo que no tiene dirección
Un grafo con 2 vértices
Identifica el siguiente grafo:
Ninguno de los anteriores
V = {C, D, E, F, H}, A = {(C, D,), (D, F), (E, H), (H, E), (E, C)}
V ={1,4,5,7,9} A = {(1,4), (4,1), (5,1), (1, 5), (7,9), (9,7), (7,5), (5,7), (4,9),(9,4)}
Magnitud especifica de la relación entre vértices:
nodo
peso
vértice
Un grafo que contiene pesos en sus aristas se denomina:
dirigido
convexo
ponderado
Empieza y termina en el mismo nodo, debe tener más de un arco.
vuelta
bidireccional
ciclo
¿Qué es un grafo conexo?
Un grafo no dirigido donde existe un camino entre cualquier par de nodos.
Un grafo donde existe al menos un par de nodos sin relación con los demás.
Grafo que tiene un arco para cualquier par de vértice.
Un grafo se puede representar a través de una matriz o lista de adyacencia.
Verdadero
Falso
¿Qué representan los ceros en una matriz de adyacencia?
carece de relación
relaciones simples
bidireccionales
Ventaja de las listas de adyacencias:
Es más fácil ver si es bidireccional
No desperdicia espacio en la representación de relaciones.
Faltan los ceros
La codificación de un vertice contiene los siguientes elementos:
Int Dato, Vertice *Sig, Arista *Adyacencia
Char Dato, int Peso, Vertice *Sig
Char Peso, Arista *Sig, Vertice Dato
¿Qué clase tiene los siguientes atributos?
int peso;
Arista *siguiente;
Vertice *adyacente;
Vertice
Arista
Grafo
¿Qué clase tiene los siguientes métodos?
Vertice(char);
~Vertice();
friend class Grafo;
friend class Arista;
Arista
Nodos
Vertice
A qué clase pertenecen los siguientes atributos:
Vertice *inicio;
Vertice *fin;
Grafo
Vertice
Arista
¿Qué significa el siguiente código?
origen->adyacente=nueva;
nueva->adyacente=destino;
Creación de la primer arista
Creación y enlazado de aristas
Creación de vertices
¿Qué parámetros necesita la función de insertar_aristas?
Char Dato, int peso, int *Vertice
Char Dato
Vertice *origen, Vertice *destino, int peso
¿Qué significa el siguiente código?
if(inicio==NULL)
{
return true;
}
else
{
return false;
}
grafo vacío
No hay vértices
No hay aristas
¿Cuál es la diferencia entre un grafo dirigido y un grafo no dirigido?
En un grafo dirigido, todas las aristas tienen una dirección, mientras que en un grafo no dirigido, las aristas no tienen dirección.
En un grafo no dirigido, todas las aristas tienen una dirección, mientras que en un grafo dirigido, las aristas no tienen dirección.
No hay diferencia, representan lo mismo.
En un grafo dirigido, todos las vértices tienen una dirección, mientras que en un grafo no dirigido, los vértices no tienen dirección.
¿Cuál es el número mínimo de aristas necesarias para conectar un grafo con N vértices?
1
N-1
N
N+1
¿Cuál es el número máximo de aristas posibles en un grafo no dirigido con N vértices?
N-1
N
(N*(N-1))/2
N*N
¿Cuál es el número máximo de aristas posibles en un grafo dirigido con N vértices?
N*(N-1)/2
(N-1)*(N-1)
N*N
N*(N-1)
¿Qué es un árbol?
Un grafo dirigido conexo y sin ciclos.
Un grafo no dirigido conexo y con ciclos.
Un grafo no dirigido conexo y sin ciclos.
Un grafo dirigido conexo y con ciclos.
¿Cuál es la definición de un camino en un grafo?
Una secuencia de vértices no consecutivos, donde cada vértice está conectado al siguiente por una arista.
Una secuencia de vértices consecutivos, donde cada vértice está conectado al siguiente por una arista.
Una secuencia de aristas consecutivas, donde cada arista conecta dos vértices consecutivos que y no pasa dos veces por el mismo vértice
Una secuencia de aristas no consecutivas, donde cada arista conecta dos vértices consecutivos.
¿Cuál es la definición de un circuito en un grafo?
Un recorrido que comienza y termina en el mismo vértice
Un camino que comienza y termina en el mismo vértice
Un vértice que esta conectado consigo mismo.
Un camino que recorre todos los vértices.
¿Cuál es la definición de la distancia entre dos vértices en un grafo?
El número de aristas en el camino más corto que conecta los vértices.
El número total de vértices en el camino más corto que conecta los vértices.
La suma de los pesos de todas las aristas en el camino más corto que conecta los vértices.
La diferencia de los índices de los vértices en una lista ordenada.
¿Qué es la matriz de adyacencia de un grafo?
Una matriz que indica si dos vértices están conectados por una arista.
Una matriz que indica la dirección de las aristas en un grafo dirigido.
Una matriz que indica la distancia entre dos vértices en un grafo ponderado.
Una matriz que indica si dos aristas son incidentes a un mismo vértice.
¿Qué es un grafo bipartito?
Un grafo en el que cada vértice tiene un grado par.
Un grafo en el que se pueden separar los vértices en dos conjuntos disjuntos, de manera que cada arista conecta un vértice de un conjunto con un vértice del otro conjunto.
Un grafo en el que no hay ciclos
Un grafo en el que todos los vértices tienen el mismo grado
¿Qué es un grafo completo?
Un grafo en el que cada vértice tiene un grado mínimo.
Un grafo en el que cada vértice tiene un grado máximo.
Un grafo en el que hay una arista entre cada par de vértices.
Un grafo en el que no hay aristas.
Indica todos los camino de A a G
ADEEBFG
ABFHG
ADCBFG
ABFG
ABCBFG
Cual de los grafos es isomorfo al de arriba a la izquierda?
A
B
C
D
Qué vértices son vecinos de E?
B y C
B, C, D, y A
B
A, B, C, D, F, G
Cual de los siguientes es un loop?
BC
EE
AB
BF
none
¿Cuál es la definición formal de un grafo?
Un grafo G es un par (V, E), donde V es un conjunto finito de vértices y E es un conjunto de pares no ordenados de vértices (aristas)
Un grafo G es un par (V, E), donde V es un conjunto de pares no ordenados de vértices (aristas) y E es un conjunto finito de vértices
Un grafo G es un par (V, E), donde V es un conjunto finito de vértices y E es un conjunto de listas de vértices adyacentes a cada vértice de V.
Un grafo G es un par (V, E), donde V es un conjunto finito de vértices y E es un conjunto de pares ordenados de vértices (aristas)
