NEW
Font size
WorksheetsEstructura de datos B2
Total questions: 50
Worksheet time: 25mins
En términos computacionales, un árbol:
Puede tener varios nodos raíz, siempre y cuando no exista un nodo hijo común.
Podrá generar tantos nodos raíz como sean necesarios en la
aplicación.
Debe tener un solo nodo raíz, del cual se desprenderán todos los subárboles.
Aquellos nodos que no tienen descendientes son conocidos como:
Nodo raíz
Nodo hermano.
Nodo hoja.
Conocemos como “grado del árbol” a:
El máximo grado de todos los nodos del árbol.
El máximo número de niveles encontrado en el árbol
La sumatoria de todos los grados de los nodos del árbol.
Se conoce como nivel de un nodo a:
El número de arcos que deben ser recorridos para llegar a él.
El número de nodos hermanos que un nodo pueda tener.
El número de nodos por los cuales hay que pasar para llegar
La altura del árbol es:
El máximo número de niveles de todos los nodos del árbol.
Igual al promedio de las diferentes alturas de sus sub árboles.
El máximo número de nodos hijos que un nodo pueda ten
Entre los recorridos de los árboles binarios, tenemo
Anchura y profundidad
Preorden y posorden,
Ascendente y descendente.
El recorrido que sigue el orden de visita “izquierda, derecha, raíz”, es conocido con el nombre:
Anchura,
profundidad
posorden.
Un árbol de búsqueda binaria:
Puede permitir a un nodo tener más de dos hijos solo si se constituyen como nodos terminales u hojas.
No permite a ningún nodo tener más de dos hijos o sub árboles.
Es aquel que solamente guarda información como “unos” o “ceros”.
La estructura final de un árbol de búsqueda binaria:
Cambia de acuerdo al orden de inserción de elementos,
Siempre será igual, sin importar el orden de inserción de elementos.
Siempre mantendrá la misma imagen sin importar el ingreso de elementos
La estructura final de un árbol AVL:
Cambia de acuerdo al orden de inserción de elemento
Adaptan su forma de acuerdo al orden de inserción de elementos.
Siempre será igual, sin importar el orden de inserción de elementos
En el ámbito computacional, un grafo está compuesto por un conjunto de nodos y arcos relacionados entre sí.
FALSO
VERDADERO
Formalmente, un grafo se define como G = (n, c), siendo n un nodo dado del grafo y, c los caminos asociados al nodo.
VERDADERO
FALSO
Los grafos dirigidos, gráficamente son representados con aristas carentes de una dirección específica.
VERDADERO
FALSO
Se conoce al grado de entrada como al número de arcos que inciden sobre un nodo.
VERDADERO
FALSO
Se conoce como orden del grafo, a la secuencia de arcos y
vértices necesarios para alcanzar un nodo destino
VERDADERO
FALSO
Las matrices de adyacencia, requieren la utilización de n
espacios de memoria para la información de los grafos.
VERDADERO
FALSO
La implementación de listas de adyacencia, al igual que con las matrices de adyacencia, pueden requerir que haya una utilización innecesaria de memoria para el almacenamiento de información
VERDADERO
FALSO
Los recorridos en listas de adyacencia trabajan solamente sobre los vértices existentes en el grafo.
VERDADERO
FALSO
Las matrices dispersas, pueden contener tanta información como las matrices de adyacencia pero no ocupan tanta memoria como ellas.
VERDADERO
FALSO
Las matrices dispersas se apoyan en arreglos alternativos para poder representar solamente los enlaces existentes en el grafo.
VERDADERO
FALSO
Las estructuras jerárquicas, al igual que las listas enlazadas, están organizadas linealmente, de forma que hay solamente un elemento siguiente y un antecesor.
VERDADERO
FALSO
El acceso a los diferentes elementos que conforman un árbol se realiza por medio de índices previamente definidos.
VERDADERO
FALSO
Un árbol podría ser definido recursivamente como una colección de nodos, donde cada uno de ellos puede ser la raiz de otros sub árboles.
VERDADERO
FALSO
Es común en árboles que dependiendo de su programación, existan algunos nodos descendientes que apunten hacia el nodo raíz.
VERDADERO
FALSO
El recorrido de un árbol binario puede ser realizado en profundidad y en anchura.
VERDADERO
FALSO
¿Cuál de las siguientes opciones de código, permite en Java, definir una estructura tipo árbol binario?
public class Nodo {
int valor;
Nodo *izq;
Nodo *der;
}
public class Nodo {
public int valor;
public Nodo izq;
public Nodo der;
}
struct Nodo{
int valor
struct Nodo *izq;
struct Nodo *der;
}
typedef struct Nodo *ABB;
¿Cuál es el código correcto, para completar el método recursivo preOrden?
public void Preorden(Nodo actual){
if(actual != null){
}
}
System.out.print(actual.valor+" ");
Preorden(actual.izq);
Preorden(actual.der);
Preorden(actual.izq);
Preorden(actual.der);
System.out.print(actual.valor+" ");
Preorden(actual.izq);
System.out.print(actual.valor+" ");
Preorden(actual.der);
En un árbol, el camino hacia un nodo es una secuencia de nodos
que comparten el mismo nivel.
que empieza en la raíz y en el que cada nodo es adyacente al siguiente.
en el cual algunos de los nodos son adyacentes.
Los árboles binarios de búsqueda, presentan una característica que es considerada como una ventaja frente a los otros tipos de arboles binarios, esta ventaja es:
Facilita la localización de elementos al interior del árbol
Permiten almacenar mucho más información en el árbol
Facilita realizar los tres recorridos del árbol
La definición de "árbol en general" es:
Estructura de datos en la cual cada nodo puede tener un hijo izquierdo y un hijo derecho. No pueden tener más de dos hijos
Estructura de datos cuyos nodos están conectados en forma jerárquica
Aquel que cumple que el sub árbol izquierdo de cualquier nodo (si no está vacío) contiene valores menores que el que contiene dicho nodo, y el sub árbol derecho (si no está vacío) contiene valores mayores.
Un grafo está conformado por vértices y aristas.
VERDADERO
FALSO
Para representar un grafo a través de la matriz de adyacencia, etiquetamos las filas con los vértices y las columnas con las aristas.
VERDADERO
FALSO
Si el Grafo es no dirigido el Grado puede clasificarse en: Grado de entrada y Grado de salida.
VERDADERO
FALSO
Para representar un grafo mediante la matriz de incidencia, el grafo debe ser etiquetado.
VERDADERO
FALSO
Una matriz de adyacencia de G se forma al ubicar en las filas los vértices de G y en las columnas las aristas de G.
VERDADERO
FALSO
De acuerdo a la conceptualización de la teoría general de grafos, determine una de las formas más comunes para representar los grafos en el campo de la computación.
Matriz de adyacencia
Cola de adyacencia
Árbol n-ario de adyacencia
Árbol n-ario de adyacencia
un predecesor
uno o más predecesores y sucesores
ningún predecesor
Tipo de grafo donde las aristas son bidireccionales:
grafos dirigidos
grafos similares
grafos no dirigidos
De acuerdo a la conceptualización de la teoría general de grafos, la definición de Nodo es:
Es un par compuesto por dos conjuntos V y A, siendo V el conjunto de vértices y A el conjunto de pares de vértices.
Es la línea que une dos nodos.
Es el punto donde convergen uno o más arcos
De acuerdo a la conceptualización de la teoría general de grafos, la definición de Longitud de camino es:
Grafo en donde los arcos tienen dirección
Cantidad de nodos que contiene un camino incluidos el inicial y el final.
Grafo en donde los arcos no tienen dirección.
Para la creación de un árbol, primeramente se debe determinar el número máximo de
elementos que éste deberá contener.
VERDADERO
FALSO
Los árboles binarios, obtienen ese nombre por cuanto su programación se realiza
exclusivamente en código binario.
VERDADERO
FALSO
La colocación de elementos en un árbol binario de búsqueda debe realizarce con los
menores a la izquierda y los mayores a la derecha.
VERDADERO
FALSO
Los árboles AVL, son una variedad de ABB que permite minimizar los tiempos de acceso
a cada uno de los nodos del árbol.
VERDADERO
FALSO
R - X - A - B - Y - C - D
A - X - B - R - C - Y - D
R - X - Y - A - B - C - D
¿Cuál es el código correcto, para completar el método de inserción de un nuevo nodo en
un ABB?
public void Insertar(int _valor){
Nodo nuevo = new Nodo(_valor);
if(raiz == null)
raiz = nuevo;
else{
Nodo padre=null;
Nodo actual = raiz;
if(padre.valor > _valor)
padre.izq = nuevo;
else
padre.der = nuevo;
}
}
while(actual != null){
padre = actual;
if(actual.valor > _valor){
actual = actual.izq;
}else{
actual = actual.der;
}
}
if(actual.valor > _valor){
actual = actual.izq;
}else{
actual = actual.der;
}
for(padre = null; actual != null){
padre = actual;
if(actual.valor > _valor){
actual = actual.izq;
}else{
actual = actual.der;
}
padre=padre.der;
}
La definición de "árbol binario" es:
Estructura de datos en la cual cada nodo puede tener un hijo izquierdo y un hijo derecho. No pueden tener más de dos hijos
Aquel que cumple que el sub árbol izquierdo de cualquier nodo (si no está vacío) contiene
valores menores que el que contiene dicho nodo, y el sub árbol derecho (si no está vacío)
contiene valores mayores.
Estructura de datos cuyos nodos están conectados en forma jerárquica
{ C, D, E, G, H, I }
{ B, E, F }; { C, D }; { G, H, I }
{ A, B, F }
