b2t3 - Árboles y Estructura de datos Flashcards

1
Q

Qué es un Tipo Abstracto de Datos (TAD) y en qué se diferencia de una estructura de datos?

A

Modelo matemático para definir tipos de datos (primitivas = comportamientos)

La estructura de datos es la implementación de un TAD

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Qué primitivas tiene el TAD pila (stack)?

Qué otras operaciones se pueden ver?

Qué concepto maneja?

A

push y pop.

A veces, menos oficialmente se usa peek o top, que es consultar el último campo de la pila, pero sin sacarlo, sólo consulta.

size → Consultar el tamaño

empty → devuelve true si está vacía y false si no

Concepto LIFO

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Qué primitivas tiene el TAD cola(queue)?

Qué otras operaciones se pueden ver?

Qué concepto maneja?

A

queue y dequeue

A veces, menos oficialmente se usa top, que es consultar el último campo de la cola, pero sin sacarlo, sólo consulta.

size → Consultar el tamaño

isEmpty → devuelve true si está vacía y false si no

Concepto FIFO

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Qué primitivas tiene el TAD lista ?

A

insertarDeltante y insertarDetrás,

head → te da el primer elemento

tail → te da todos los elementos menos el head

isEmpty → devuelve true si está vacía y false si no

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Qué implementaciones tienen las siguientes TAD? (no demasiado preguntable)

List (secuencia)

set / multiset

Queue / Double queue

Priority Queue (heap)

Tree

Graph

Associative Array (diccionario, mapa) (clave valor)

A

List (secuencia) → Array, Lista enlazada

set / multiset → Array, Rojo-negro, tabla hash

Queue / Double queue → Array, Lista enlazada / lista doblemente enlazada

Stack → Array, Lista enlazada

Priority Queue (heap) → Montículo (propiedad)

Tree

Graph → Matriz, Array de Listas enlazadas

Associative Array (diccionario, mapa) (clave valor) → Tabla hash

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Cómo es la función hash que se usa en las tablas hash para generar la key?

A

[valor a guardar] mod 250 → Esto da como resultado el resto de dividir el valor / 250.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Qué es el concepto de colisión en una tabla hash?

A

Cuando se cargan más de 250 elementos en la tabla hash y por tanto varios elementos pueden dar el mismo resultado de” [valor elemento] mod 250” y por tanto la misma key

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Qué es un MONTÍCULO?

A

Estructura basada en árbol, que cumple la propiedad del montículo:

max heap → el nodo raiz es el mayor de todo el árbol. Igualmente, cada nodo es el mayor de sus nodos hijos.

min heap → el nodo raiz es el menor de todo el árbol. Igualmente, cada nodo es el menor de sus nodos hijos.

Si se implementa con un árbol binario se llama montículo binario

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Explica los siguientes concetos de los ÁRBOLES

Raíz

Rama

Hoja

Nivel

Profundidad

Altura del árbol

Altura de un nodo

Peso

Orden

Grado

Árbol binario

Árbol binario lleno

Árbol binario perfecto

A

Raíz → Nodo sin padres

Rama → Los nodos que tienen al menos un hijo y no son la raíz

Hoja → Nodo sin hijos

Nivel → El nivel vertical donde está el nodo, o los saltos desde la raíz. La raíz en casi todos los sitios se dice que es 0 y en otros 1

Peso → Nº de nodos del árbol

Altura del árbol → nº de saltos (aristas) en la trayectoria más larga de la raiz nodo hasta una hoja

Altura de un nodo → la trayectoria más larga del nodo hasta una hoja (ojo, las hojas son altura =0, aunque no sea la hoja a más profunidad!)

Profundidad → Nº de saltos (aristas) desde el nodo hasta la raíz

Orden → Nº máximo teórico de hijos que puede tener un nodo potencialmente, aunque no los tenga. En árbol binario el orden es 2

Grado → Nº de nodos hijos máximo concreto que tiene uno de los nodos del árbol

Árbol binario → Árbol donde el nº máximo de hijos de un nodo es 2, es decir, es de orden 2

Árbol binario lleno → Árbol binario en el que la raíz y todas las ramas tiene 2 hijos. Otra forma de decirlo es que todos los nodos salvo la raíz tiene 2 o 0 hijos

Árbol binario perfecto → Árbol binario donde todas las hojas están al mismo nivel

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

En los árboles, qué es el FE o Factor de equilibrio?

A

Factor de equilibrio (FE) → diferencia de altura entre el subárbol izquierdo y el derecho de -1, 0 o +1

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Qué tipos de árboles equilibrados o autobalanceables más importantes hay?

A

AVL (rotación)

AA

Rojo-Negro

Splay

Árbol B

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Con qué concepto se consigue el equilibrio en los árboles AVL (balanceables o equilibrados)?

A

Con la rotación de nodos

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Qué tipos de árboles binarios más importantes hay?

A

Árbol binario de búsqueda → Recorrido In Orden (IRD) → elementos ordenados

Árbol de Fibonacci → caso particular de AVL

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Qué tipos de recorridos de árboles en profundidad hay?

A

RID → Pre Orden

IRD → In Orden

IDR → Post Orden

(La raiz es la que se mueve en las siglas, como truco nemotécnico)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Cuál es la lógica para aplicar los recorridos en profundidad PreOrden, InOrden y PostOrden?

A

Se visita (escribe) lo que indican las siglas, siempre que no se pueda navegar más. Es decir que cuando al ir a I o D, ese nodo tiene hijos, se aplica de nuevo las siglas del algoritmo a ese nuevo subárbol. “Se aplica el algoritmo recursivamente a cada subárbol”

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Cómo se pueden identificar dado un recorrido si es PreOrden, InOrden y PostOrden?

A

En PreOrden, la raíz es la primera, en Post-Orden es la última. En InOrden quedará ni el primero ni el último

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

En una pregunta de examen te pueden dar dos recorridos (uno será siempre el InOrden) y tener que sacar el tercero. Cómo es la lógica deductiva?

https://youtu.be/s5XRtcud35E

https://youtu.be/cGlNehp57Y0

A
  1. Identificar la raiz: En PreOrden, la raíz es la primera, en Post-Orden es la última. En InOrden quedará ni el primero ni el último.
  2. Identificar subárbol izquierdo y derecho de esa raíz: En InOrden, todo lo de la izquierda de la R es el subárbol izquierdo y todo lo de la derecha de R es el subárbol derecho
  3. Volver a identificar la raíz de cada subárbol: del subconjunto de nodos de cada subárbol, la raíz será la primera o la última en el PreOrden o PostOrden respectivamente.
  4. Volver a identificar los subárboles izquierdo y derecho de cada raíz
  5. … así recursivamente hasta terminar
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

En una pregunta de algortimos de pseudocódigo puede ser resolver qué parámetro hay que pasarle a una función recursiva para que salga un resultado determinado.

HACER EJECERCICIO ÚLTIMO EXAMEN PARA PRACTICAR

Para resolverla, hacer la siguiente estrategia:

  1. Seleccionar una de las posibles respuestas y usarla para probar con ella a ver si da el resultado
  2. Dibujar el árbol de llamadas, pero sólo una rama hasta el final
  3. Usar los resultados de las iteraciones de la primera rama cuando se repitan en otras ramas, para ahorrarnos dibujarlos otra vez ya que van a dar lo mismo y ya sabemos el resultado
A

Para resolverla, hacer la siguiente estrategia:

  1. Seleccionar una de las posibles respuestas y usarla para probar con ella a ver si da el resultado
  2. Dibujar el árbol de llamadas, pero sólo una rama hasta el final
  3. Usar los resultados de las iteraciones de la primera rama cuando se repitan en otras ramas, para ahorrarnos dibujarlos otra vez ya que van a dar lo mismo y ya sabemos el resultado
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Cómo funciona el tipo de recorrido en profundidad de árboles Pre-Orden (RID)?

A

Completar———–

Se visita cada nodo al caer en él

1º Se empieza a navegar por la Raíz, y se

2º Subárbol izquierdo (siempre que se pueda ir a la izquierda, se va)

3º Subárbol derecho

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Cómo funciona el tipo de recorrido en profundidad de árboles In-Orden (IRD)?

A

Se visita (imprime) cada nodo sólo cuando no se puede seguir navegando en esa dirección

1º Cuando no se pueda bajar más, se coge ese subárbol se visita primero I, luego la R de ese árbol, y luego D

2º Se sube un paso arriba, y se coge el siguiente subárbol por arriba. Ahora en este se visita R (porque I ya se ha visitado en el paso 1) y luego R

3º Así sucesivamente

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Cómo funciona el tipo de recorrido en profundidad de árboles Post-Orden (IDR)?

A

Completar

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

Explicación de recorridos RID, IRD, IDR

https://en.wikipedia.org/wiki/Tree_traversal

https://www.oscarblancarteblog.com/2014/08/22/estructura-de-datos-arboles/

A

https://en.wikipedia.org/wiki/Tree_traversal

https://www.oscarblancarteblog.com/2014/08/22/estructura-de-datos-arboles/

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

Qué es un Árbol B?

A

Un árbol multicamino, en el que en cada nodo, en vez de un dato, hay más de uno.

Cada nodo puede tener n hijos

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

Qué tipos de un Árbol B hay y en qué consisten?

A

Árbol B → Árbol multimcamino. Cada nodo puede tener n hijos

Árbol B+ → Los nodos hoja están enlazados entre si y los datos solo están en los nodos hoja (en resto de nodos contiene claves)

Árbol B* → garantiza una ocupación de ⅔

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

Explica los siguientes concetos de los GRAFOS

Vértice

Arista

Arco

Dirigido / no dirigido

Grafo conexo

Multigrafo

Etiquetado o ponderado

Orden del grafo

A

Vértice → Nodo

Arista → Línea entre dos nodos

Arco → Relación entre dos nodos, se expresa (nodo a, nodo b)

No dirigido / Dirigido → Si se puede navegar entre dos nodos en los dos sentidos o solo en un sentido

Grafo conexo → Sin ciclos

Multigrafo → más de una arista entre dos vértices (más de un camino entre dos nodos)

Etiquetado o ponderado → Peso numérico en las aristas

Orden del grafo → Nº de vértices

Grado de un vértice → Nª de arcos incidentes

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

Con qué estructuras de datos se pueden representar los GRAFOS?

A
  • Listas de adyacencia (array de vértices + listas enlazadas)
  • Matrices de adyacencia (desperdicia memoria) → Se ponen todos los vértices en los dos ejes de una matriz y se marca en cada cruce con 1/0 si están enlazados o no en cada sentido
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

Qué 3 algoritmos de encontrar el camino mínimo en grafos se usan en protocolos TCP/IP de encaminamiento de routers?

A

Dijkstra (OSPF)

Bellman-Ford (RIP)

Floyd-Warshall (es como Dijkstra, pero en lugar de devolver el camino mínimo entre 2 nodos dados, devuelve todos los caminos mínimos del grafo)

A*

28
Q

Qué significa un algoritmo de recubrimiento mínimo? Qué algoritmos hay? Utilizados por los algoritmos de Spanning Tree de switches

A

Recorrer todos los nodos de un grafo de la forma más rápida

Kruskal (en grafo conexo y ponderado)

PRIM

29
Q

Para qué sirven los algoritmos de de grafos TARJAN y FORD-FULKERSON?

A

TARJAN → Grupos conexos (permite determinar los componentes fuertemente conectados de un grafo dirigido)

FORD-FULKERSON → Caminos para maximizar el flujo

30
Q

Qué tres tipos de accesos a ficheros hay?

A
  • Secuencial (las cintas por ejemplo)
  • Acceso directo
    • Por la clave del registro que sea la posición en el archivo
    • Aplicando una función sobre la clave que te de la posición en el archivo
  • Acceso indexado (hay un fichero con los datos + fichero de índice)
    • Se busca la clave sobre el índice ordenado y esto te da la posición en el archivo
31
Q

Qué dos tipos de ordenación externa sobre ficheros hay, cuando no se ordenaban en memoria?

A
  • Mezcla directa
  • Mezcla natural
32
Q

Cómo se identificaría un fichero binario como JPG,GIF, …

A

Por el magic number o signature: n digitos por el que empieza el fichero binario que indica el formato del fichero

33
Q

Cómo interpreta un navegador el tipo de información que le llega?

A

Con el mimetipe : tipo/subtipo

  • image/gif
  • text/xml
  • text/html
  • application/javascript
  • video/mpeg
  • application/pdf
  • image/svg+xml
34
Q

Indica características de los siguientes tipos de ficheros de imagen (compresión, colores, transparencia, animación)

JPG/JPEG

WebP

PNG

GIF

TIFF

BMP

SVG

A

JPG/JPEG (Joint Photographic Expert Group) → Compresión con pérdida → Existen variantes sin pérdida

WebP -> Compresión con pérdida y transparencia como GIF. Es de Google

PNG (Portable Network Graphics) → Compresión sin pérdida / Transparencias / True Color 24bits / No animación / Compresión deflación sin pérdida

GIF (Graphic Interchange Format) → 256 colores / animación y transparencia / compresión LZW sin pérdida)

TIFF (Tagged Image File Format) → Compresión sin pérdida multipágina

BMP (Windows Bitmap) → Compresión RLE (Run Lenght Encoding) sin pérdida

SVG (Scalable Vector Graphics) → en html5 se incrusta en html de forma nativa / mimetipe image/svg+xml

35
Q

Falta las preguntas de la ficha de tipos de fichero de audio y vídeo, codecs, …. Dani lo va a ampliar y a hacer una ficha nueva

A
36
Q

Cuál es la diferencia entre codec y contenedor? Algunos ejemplos de cada

A

El códec es el formato en el que está codificada la información de audio o vídeo (mp3, wma, wav …

El contenedor es el que contiene la pista de audio y/o video (.avi, .mov, mpg,.asf, .mkv …)

37
Q

Qué es mp3, qué tipo de compresión tiene y para qué vale su etiqueta ID3?

A

mp3 = mpeg-(1/2) audio layer III

(mpeg = moving picture experts group)

Compresión con pérdida

ID3 → etiqueta con la información de autor, título, etc… que se usa para su catalogación

38
Q

Lista los principales tipos de fichero de audio

A

mp3 (mpeg-1(o 2) layer III)

wav (sin compresión)

wma (windows media audio)

ac3 → dolby

FLAC (Free Lossless audio codec)

39
Q

Lista los principales tipos de contenedor de fichero de video

A
  • avi (audio video interface) → es de microsoft
  • mov → es de apple, extensión QT (reproductor quicktime)
  • .mpg → usa los codecs MPEG-1 (VHS-CD), MPEG2 (DVD), MPEG-4 (HD, deriva en xvid)
  • asf
  • mkv
40
Q

Qué es formato docx, xlsx, pptx, etc .. y a partir de qué año lo adoptó Microsoft?

A

Es el formato OOXML (Office Open XML) recogido en el estandar ECMA 376 para esos tipos de ficheros.

Es un fichero zip que dentro tiene varios xml

Microsoft cambió a partir de 2007

41
Q

Indica qué significa los siguientes formatos de archivos de Microsoft

doc

dot

docx

docm

dotx

dotm

rtf

xlsx

xlsm

xltx

xlsb

pptx

pptm

potx

potm

ppsx

ppsm

A

doc → word

dot → plantilla para word

docx → word formato ooxml

docm → macro word

dotx → plantilla para word formato ooxml

dotm → plantilla con macro para word

rtf → texto enriquecido

xlsx → excel formato ooxml

xlsm → macro para excel

xltx → excel con plantilla formato ooxml

xlsb → libro binario de excel

pptx → power point

pptm → power point con macros visual basic

potx → plantilla para power point formato ooxml

potm → plantilla para power point con macro

ppsx → power point solo diapositivas

ppsm → diapositivas con macro

42
Q

Indica qué significa los siguientes formatos de archivos de Open Office

ODT

OTT

ODS

ODP

ODG

ODC

ODF

ODI

ODM

ODB

A

ODT → open document text → texto

OTT → plantilla de texto

ODS → spreadsheet → hoja de cálculo

ODP → presentation → presentación

ODG → gráphics → dibujo

ODC → charts → gráficas

ODF → formula

ODI → image

ODM → documento maestro

ODB → database

43
Q

Qué iso es el estandar de PDF?

Qué es PDF/A?

A

ISO 32000-1:2008

Para guardado a largo plazo de documentos electrónicos. Elimina algunas características como audio, vídeo, cifrado, … para que siga siendo compatible y no se rompa)

44
Q

Qué es el formato PS?

A

Un archivo PS es una imagen guardada en el lenguaje PostScript. Puede contener gráficos de vector, gráficos de trama, y ​​el texto, e impreso por una impresora PostScript sin ser abierto en una aplicación.

45
Q

Qué es el formato PCL?

A

PCL (Printing Control Language) es un lenguaje de descripción de páginas (Page Description Language – PDL) que fue desarrollado por Hewlett-Packard para impresoras láser. Fue creado en 1980 como alternativa más simple, rápida y económica para las impresoras láser basadas en el lenguaje PostScript.

46
Q

Indica qué son los siguientes tipos de ficheros variados

exe

msi

dmg / pkg

deb

rpm

tar.gz

vcf

p12/ptx

cer

eml/msg

mbox

pst/ost

nsf

apk

csv

swf

epub

aab

A

exe → ejecutable de microsoft

msi (microsoft installer) → instalable de microsoft

dmg / pkg → instalable de mac

deb → instalable de linux debian y derivados como ubuntu

rpm → instalable de redhat y derivados como centos

tar.gz → comprimido básico de linux

vcf → vcard file

p12/ptx → certificado 509 con su clave privada

cer → certificado 509 sin su clave privada

eml/msg → formato de un correo, eml es la rfc2822

mbox → contenedor de mails, es la rfc 4155

pst/ost → buzones de outlook

nsf → buzones de lotus

apk → instalable android

csv → texto formateado con puntos y coma

swf → fichero con película flash

epub → libro electrónico

aab → publicación android que se abstrae de la plataforma

47
Q

A qué corresponde esta definción?

Conjunto de reglas que, aplicada sistemáticamente a unos datos de entrada apropiados, resuelven un problema en un número finito de pasos elementales

A

Algoritmo

48
Q

Qué tipo de algoritmo son las búsquedas binarias, ya sea sobre un array ordenado o un árbol binario de búsqueda, etc … es decir donde la búsqueda consiste en ir descartando mitades cada vez?

A

Algoritmo → logn

49
Q

Qué tipo de algoritmo son las búsquedas en listas no ordenadas, es decir que se usan bucles para recorrerla?

A

Algoritmo → n

50
Q

Qué tipo de algoritmo son las búsquedas en listas no ordenadas que tienen dos bucles anidados?

A

Algoritmo → n^2

Por ejemplo, el bubble sort, selection sort, insertio sort …

51
Q

En el análisis de algoritmos se usa la notación “Big O notation” ¿en qué consiste?

A

Analiza la complejidad espacial y temporal, mediante un cota superior asintótica

52
Q

Técnicas de diseño de algoritmos: en qué consisten?

  • Divide y vencerás
  • Voraces
  • Probabilísticos
  • Backtracking
  • Ramificación y poda
  • Programación dinámica
A
  • Divide y vencerás → como las búsquedas binarias (T(n/2))
  • Voraces → (opción óptima en cada paso. Dijkstra, Prim, Kruskal
  • Probabilísticos → Las Vegas, Montecarlo
  • Backtracking → Explora todo el árbol de soluciones
  • Ramificación y poda → Optimiza las anteriores poniendo marcas para no pasar varias veces por el mismo sitio
  • Programación dinámica → (bottom-up + memorización): Después de hacer un divide y vencerás, combina subproblemas óptimos. En lugar de ser top-down, es bottom-up. Se empieza con problemas pequeños y se van combinando. Además memoriza la resolución de problemas, por si vuelven a surgir no volver a resolverlos
53
Q

Ordena de más eficientes a menos los siguientes algoritmos

O(n^c)

O(c^n)

O(n^2)

O(1)

O(nlogn)

O(logn)

O(n)

A

O(1)

O(logn)

O(n)

O(nlogn)

O(n^2)

O(n^c)

O(c^n)

54
Q

Qué tres medios de expresión de logaritmos hay?

A

Diagramas de flujo (ISO)

Pseudocódigo

Sistemas formales (matemáticos)

55
Q

En qué consistena alto nivel los siguientes tipos de algoritmos de ordenación?

Exchange sort

Selection sort

Insertion sort

Merge sort

Distribution sort

A

Exchange sorts → Intercambiar elementos. Burbuja, QuickSort, Cocktail o burbuja bidireccional

Selection sorts → Para cada posición, va a buscar qué elemento corresponde y lo selecciona. Heap Sort. Selection Sort

Insertion sorts → Para cada elemento, mira en qué posición tendría que ir y lo inserta. ShellSort (inserción con pasos más grandes para encontrar el sitio de Xi). Insertion Sort

Merge sortsMerge sort

Distribution sort → distribuye entre distintas clasificaciones. Bucket sort o Bin sort, Radix sort

56
Q

En qué consiste el algoritmo de ordenación de tipo Exchange, BURBUJA?

Qué complejidad Big O tiene?

A

O(n^2), salvo que ya esté ordenado o todos los elementos sean iguales, que sería (O(n))

Va desplazando el nº más grande que nos encontramos a base de comparaciones e intercambios hasta el final o su posición. Hará una pasada por cada elemento desordenado.

57
Q

En qué consiste el algoritmo de ordenación de tipo Insertion, INSERCIÓN?

Qué complejidad Big O tiene?

A

O(n^2)

Por cada elemento (Xi) busca la posición que le corresponde, desplaza los elementos necesarios para hacerle el hueco y lo inserta

58
Q

En qué consiste el algoritmo de ordenación de tipo Insertion, INSERCIÓN DIRECTA?

Qué complejidad Big O tiene?

A

O(n^2)

Por cada elemento (Xi) busca la posición que le corresponde, desplaza los elementos necesarios para hacerle el hueco y lo inserta

59
Q

En qué consiste el algoritmo de ordenación de tipo Exchange, QUICK SORT?

Qué complejidad Big O tiene?

A

O(n log n), aunque en el caso peor, si el pivote se selecciona en un extremo, es peor, es O(n^2)

Fija un pivote y por cada elemento, compara con el pivote y lo inserta en uno de los lados.

Después repite la operación en cada uno de los dos segmentos, fijando nuevos pivotes, hasta que el array queda ordenado

60
Q

En qué consiste el algoritmo de ordenación de tipo Merge, MERGE SORT?

Qué complejidad Big O tiene?

A

O(n log n)

  1. Se divide la lista en sublistas hasta llegar al caso trivial (recursividad)
  2. Mezcla (mergea) dos sublistas para obtener una lista ordenada
61
Q

En qué consiste el algoritmo de ordenación de tipo Merge, HEAP SORT o MONTÍCULO?

Qué complejidad Big O tiene?

A

O(n log n)

Consiste en meter todos los elementos del array en un montículo MAX y luego realizar N veces llamada a eliminar_max(). Entre llamada y llamada hay que reconstruir el montículo

62
Q

En qué consiste el algoritmo de ordenación de tipo Selection, SELECTION?

Qué complejidad Big O tiene?

A

O(n^2)

Se busca el minimo y se pone en la 1º posición

Luego se busca el mínimo a partir del 1er elemento para la 2º posición y así sucesivamente

63
Q

En qué consiste el algoritmo de ordenación de tipo Distribution, RADIX SORT?

Qué complejidad Big O tiene?

A

O(n*k)

Hay dos versiones

LSD (usa el dígito menos significativo)

MSD (esa el dígito más significativo)

Hay unas colas o buckets del 0 al 9, y inserta los elementos en cada una analizando que el último dígito de cada uno sea igual al nº de cola

Después los saca y los vuelve a meter pero analizando el penúltimo dígito. Al meterlos de nuevo los mete ordenados.

Así sucesivamente

64
Q

En qué consiste el algoritmo de ordenación de tipo Distribution, BUCKET SORT o BIN SORT?

Qué complejidad Big O tiene?

A

O(n)

Hay unos buckets con rangos de números, y inserta los elementos en cada uno según a qué rango corresponda.

Luego te dice que ordenes cada bucket con otro algoritmo que quieras

65
Q

Qué es un algoritmo de ordenación natural?

A

Es aquel que cuando se le da una secuencia ya ordenada, tardará la menor cantidad de tiempo posible.