Maco

Enviado por Programa Chuletas y clasificado en Otras materias

Escrito el en español con un tamaño de 20,87 KB

 

Cuestionario de Estudio

Organización de Archivos – Universidad Politecnica de Honduras

Ing. Welbyn J. Espinal

Organizaciones Indexadas

1) ¿Para que son útiles las Organizaciones Indexadas?

R. Para mejorar la eficiencia en acceso a través de claves de búsqueda en el

almacenamiento auxiliar en forma de índices. Con esta práctica se habrá de

implementar al menos un índice, y tantos como se estime oportuno.

2) ¿De que consta cada entrada y que son los índices?

R. Los índices son archivos que se componen de entradas. Cada entrada consta de:

- Entrada de datos: valor de la clave de indización para esa entrada

- Referencia al registro: puntero, que puede ser físico o lógico, según el caso

3) ¿Cómo se clasifican los índices?

R. Podemos clasificar los índices en dos tipos principales:

§Primarios: las claves de las entradas tienen valores únicos.

§Secundarios: la clave de indexación tendrá valores repetidos, y será

necesario contemplar esto en las operaciones del índice.

4) ¿Cuales son las operaciones básicas de la indexación y como funciona?

§a. Crear índice: recibe la clave de indización (campos a indexar) y construye el

índice. Si el campo ya estuviera indexado la operación se abortaría ya que no

deberíamos tener el mismo índice sobre una misma clave.

§b.- borrar índice: borra el índice (destruye el archivo)

Ordenamiento de Archivos

5) ¿Qué implica el Ordenamiento de Archivos?

R. Implica una mejora de la eficiencia en la búsqueda de los archivos.

6) ¿Cuáles son las técnicas básicas de Ordenamiento?

R. Ordenamientos internos y Ordenamientos Externos

7) ¿Cuándo se aplica el ordenamiento interno?

R. Se aplican cuando el conjunto de datos a clasificar es lo suficientemente pequeño,

de tal forma que pueda caber en memoria principal.

8) Son métodos de Ordenamiento interno

- Ordenamiento por Burbuja

- Ordenamiento por Inserción

- Ordenamiento por Selección

- Ordenamiento por MergeSort

- Ordenamiento por QuickSort

- Ordenamiento por HeapSort

9) ¿En que consiste el ordenamiento por burbuja?

R. En comparar pares de valores de llaves e intercambiarlos si no están en sus

posiciones relativas correctas.

10) ¿En que consiste el ordenamiento por inserción?

R. Es básicamente tomar la siguiente llave de una lista no clasificada e insertarla en

su posición relativa correspondiente en una lista creciente de datos clasificados.

11) ¿En que consiste el ordenamiento por MergeSort?

R. Consiste en tomar la lista de llaves, dividirla en dos partes y ordenarlas en forma

independiente.

12) ¿En que consiste el ordenamiento por QuickSort?

R. Consiste en escoger una llave aleatoriamente como referencia y se ordena a partir

de esta llave. En el peor de los casos, la llave aleatoria seleccionada que seria la del

extremo quicksort funciona correctamente.

13) ¿En que consiste el ordenamiento por HeapSort?

R. Se comporta mejor en los peores casos y se basa en el uso de un árbol binario

llamado apilamiento.

Organizaciones Basadas en Árboles

14) ¿Qué es un Árbol en Informática?

R. un árbol es una estructura de datos ampliamente usada que imita la forma de un

árbol (un conjunto de nodos conectados). Un nodo es la unidad sobre la que se

construye el árbol y puede tener cero o más nodos hijos conectados a él.

15) ¿Cuales son los tipos de Árboles?

- Árboles Binarios

- Árbol de búsqueda binario auto-balanceable

- Árboles B,

- Árboles Multicamino

16) ¿Qué es un Árbol binario?

R. Un árbol binario es una estructura de datos en la cual cada nodo siempre tiene

un hijo izquierdo y un hijo derecho. No pueden tener más de dos hijos (de ahí el

nombre "binario").

17) ¿ Qué es un árbol binario auto-balanceable

R. Un árbol binario de búsqueda auto-balanceable o equilibrado es un

árbol binario de búsqueda que intenta mantener su altura, o el número de niveles de

nodos bajo la raíz, tan pequeños como sea posible en todo momento,

automáticamente.

18) Cuales son los Arboles B

R. Son estructuras de datos de árbol que se encuentran comúnmente en las

implementaciones de bases de datos y sistemas de archivos. Los árboles B

Representa una colección de datos ordenados de manera que se permite una

inserción y borrado eficientes de elementos. Es un índice, multinivel, dinámico, con

un límite máximo y mínimo en el número de claves por nodo y varian en Arbol B+ y

Arbol B*

19. Arbol B +

R. Un árbol-B+ es una variación de un árbol-B. En un árbol-B+, en contraste

respecto un árbol-B, toda la información se guarda en las hojas.

20. Arbol B *

R. Es una variante de Árbol-B que requiere que los nodos no raíz estén por lo menos

a 2/3 de ocupación en lugar de 1/2.

Transformación de Claves (Hashing)

21. ¿Qué significa la Transformación de Claves (Hashing)?

R. Es un método que permite aumentar la velocidad de búsqueda sin necesidad de

tener los elementos ordenados. Trabaja basándose en una función de transformación

o función hash (h) que convierte una clave dada en una dirección(índice) dentro del

arreglo.

22. Qué debe hacer la función hash (h)

R. La función hash debe generar posiciones diferentes dadas dos claves diferentes. Si

esto no ocurre hay una colisión.

23) Qué es una colisión

R. Una colisión se define como la asignación de una misma dirección a dos o más

claves distintas.

23. Cuales son los métodos para resolver colisiones.

R.

• Reasignación

• Arreglos Anidados

• Encadenamiento

24. Qué es un buckets (compartimiento) y cuales son sus ventajas?

R. Es un bloque de registros que se extraen en un acceso a disco cuando comparten

la misma dirección y sus ventajas son:

§Minimiza el número de colisiones

§Minimiza el tiempo de acceso a las claves y el espacio utilizado en el

Almacenamiento.

§El tamaño de la tabla Hash es menor.

Entradas relacionadas: