Cuestionario 3

1. ¿Clasificación de los tipos de datos?

 Dinámicos
 Estáticos
 El tipo cadena
 Estructurados
 Simples
 Ordinales
 No-ordinales

2. ¿Definir cada uno de los tipos de datos?

 Dinámicos:

Dentro de esta categoría entra solamente el tipo puntero. Este tipo te permite tener un mayor
control sobre la gestión de memoria en tus programas. Con ellos puedes manejar el tamaño de tus
variables en tiempo de ejecución, o sea, cuando el programa se está ejecutando.

 Estáticos:

Casi todos los tipos de datos son estáticos, la excepción son los punteros y no se tratarán debido a
su complejidad.

Que un tipo de datos sea estático quiere decir que el tamaño que ocupa en memoria no puede
variar durante la ejecución del programa. Es decir, una vez declarada una variable de un tipo
determinado, a ésta se le asigna un trozo de memoria fijo, y este trozo no se podrá aumentar ni
disminuir.

 El tipo cadena:

Con el tipo carácter puedes tener objetos que representen una letra, un número, etc. Es decir,
puedes usar variables o constantes que representen un valor alfanumérico. Pero ojo, cada
variable sólo podrá almacenar un carácter.

Sin embargo, con las cadenas de caracteres (strings) puedes contener en una sóla variable más de
un carácter. Por ejemplo, puedes tener en una variable tu nombre.

 Estructurados

Mientras que una variable de un tipo simple sólo referencia a un elemento, los estructurados se
refieren a colecciones de elementos.
Las colecciones de elementos que aparecen al hablar de tipos estructurados son muy variadas:
tenemos colecciones ordenadas que se representan mediante el tipo array, colecciones sin
orden mediante el tipo conjunto, e incluso colecciones que contienen otros tipos, son los
llamados registros.

 Simples

Como su nombre indica son los tipos básicos en Pascal. Son los más sencillos y los más fáciles de
aprender. Por todo esto, serán en los que nos centremos.

Los tipos simples más básicos son: entero, lógico, carácter y real. Y la mayoría de los lenguajes de
programación los soportan, no como ocurre con los estructurados que pueden variar de un
lenguaje a otro.

 Ordinales

Dentro de los tipos simples, los ordinales son los más abundantes. De un tipo se dice que es
ordinal porque el conjunto de valores que representa se puede contar, es decir, podemos
establecer una relación uno a uno entre sus elementos y el conjunto de los números naturales.

 No-ordinales

Simplificando, podríamos reducir los tipos simples no-ordinales al tipo real. Este tipo nos sirve para
declarar variables que pueden tomar valores dentro del conjunto de los números reales.

3. ¿Qué es el arreglo unidimensionales y en qué caso se usa?

Un arreglo unidimensional es un tipo de datos estructurado que está formado por una colección
finita y ordenada de datos del mismo tipo. Es la estructura natural para modelar listas de
elementos iguales. Los datos que se guarden en los arreglos todos deben ser del mismo tipo.

REPRESENTACION EN MEMORIA: Los arreglos guardan en memoria la cantidad de espacios que se

le indican en la declaración.

4. ¿Operaciones con Arreglos?

 Lectura
 Escritura
 Asignación
 Actualización
 Ordenación
 Búsqueda

5. ¿Definir las clasificaciones de operaciones con Arreglos?

 Lectura:
 Este proceso consiste en leer un dato de un arreglo y asignar un valor a cada uno de sus
componentes.
La lectura se realiza de la siguiente manera:
para i desde 1 hasta N haz
x<--arreglo[i]

 Escritura:

Consiste en asignarle un valor a cada elemento del arreglo.

La escritura se realiza de la siguiente manera:
para i desde 1 hasta N haz
arreglo[i]<--x

 Asignación:

No es posible asignar directamente un valor a todo el arreglo, por lo que se realiza de la manera
siguiente:
para i desde 1 hasta N haz
arreglo[i]<--algún_valor

 Actualización

Dentro de esta operación se encuentran las operaciones de eliminar, insertar y modificar datos. Para
realizar este tipo de operaciones se debe tomar en cuenta si el arreglo está o no ordenado.
Para arreglos ordenados los algoritmos de inserción, borrado y modificación son los siguientes:
1.- Insertar.

2.- Borrar.

3.- Modificar

6. ¿Matriz poco densa regular y sus clasificaciones definir?

Una matriz poco densa es aquella que está formada por elementos que en su mayoría son ceros. Este
tipo de matrices son matrices cuadradas que se dividen en los siguientes tipos:

 Matriz triangular superior:

En este tipo de matriz los elementos iguales a cero se encuentran debajo de la diagonal principal.

 Matriz triangular inferior:

En este tipo de matrices los elementos iguales a cero se encuentran por encima de la diagonal
principal.

 Matriz tridiagonal:
En ésta, los elementos diferentes de cero se encuentran en la diagonal principal ó en las diagonales
por debajo o encima de ésta.

7. ¿Ordenaciones en Arreglos?

La importancia de mantener nuestros arreglos ordenados radica en que es mucho más rápido tener
acceso a un dato en un arreglo ordenado que en uno desordenado.
Existen muchos algoritmos para la ordenación de elementos en arreglos, enseguida veremos algunos de
ellos.

8. ¿Selección directa y ejempló?

Este método consiste en seleccionar el elemento más pequeño de nuestra lista para colocarlo al inicio y
así excluirlo de la lista.
Para ahorrar espacio, siempre que vayamos a colocar un elemento en su posición correcta lo
intercambiaremos por aquel que la esté ocupando en ese momento.
El algoritmo de selección directa es el siguiente:
i <- 1
mientras i<= N haz
min <-i
j <- i + 1
mientras j <= N haz
si arreglo[j] < [min] entonces
min <-j
j <- j + 1
intercambia(arreglo[min],arreglo[i])
i <- i +1

9. ¿Ordenación por burbuja y ejemplo?

Es el método de ordenación más utilizado por su fácil comprensión y programación, pero es importante
señalar que es el más ineficiente de todos los métodos.
Este método consiste en llevar los elementos menores a la izquierda del arreglo ó los mayores a la
derecha del mismo. La idea básica del algoritmo es comparar pares de elementos adyacentes e
intercambiarlos entre sí hasta que todos se encuentren ordenados.

i <- 1
mientras i < N haz
j <- N
mientras j > i haz
si arreglo[j] < arreglo[j-1] entonces
intercambia(arreglo[j],arreglo[j-1])
j<j-1
i <- i +1
10. ¿Ordenación por mezcla y ejemplo?

Este algoritmo consiste en partir el arreglo por la mitad, ordenar la mitad izquierda, ordenar la mitad
derecha y mezclar las dos mitades ordenadas en un array ordenado. Este último paso consiste en ir
comparando pares sucesivos de elementos (uno de cada mitad) y poniendo el valor más pequeño en el
siguiente hueco.
procedimiento mezclar(dat,izqp,izqu,derp,deru)
inicio
izqa <- izqp
dera <- derp
ind <- izqp
mientras (izqa <= izqu) y (dera <= deru) haz
si arreglo[izqa] < dat[dera] entonces
temporal[ind] <- arreglo[izqa]
izqa <- izqa + 1
en caso contrario
temporal[ind] <- arreglo[dera]
dera <- dera + 1
ind <- ind +1
mientras izqa <= izqu haz
temporal[ind] <- arreglo[izqa]
izqa <- izqa + 1
ind <- ind +1
mientras dera <= deru haz
temporal[ind] <=dat[dera]
dera <- dera + 1
ind <- ind + 1
para ind <- izqp hasta deru haz
arreglo[ind] <- temporal[ind]
fin

11. ¿Búsquedas en Arreglos?

Una búsqueda es el proceso mediante el cual podemos localizar un elemento con un valor especifico
dentro de un conjunto de datos. Terminamos con éxito la búsqueda cuando el elemento es encontrado.
A continuación veremos algunos de los algoritmos de búsqueda que existen.

12. ¿Búsqueda Secuencial y ejemplo?

A este método también se le conoce como búsqueda lineal y consiste en empezar al inicio del conjunto
de elementos, e ir atreves de ellos hasta encontrar el elemento indicado ó hasta llegar al final de arreglo.
Este es el método de búsqueda más lento, pero si nuestro arreglo se encuentra completamente
desordenado es el único que nos podrá ayudar a encontrar el dato que buscamos.
ind <- 1
encontrado <- falso
mientras no encontrado y ind < N haz
si arreglo[ind] = valor_buscado entonces
encontrado <- verdadero
en caso contrario
ind <- ind +1

13. ¿Búsqueda binaria y ejemplo?

Las condiciones que debe cumplir el arreglo para poder usar búsqueda binaria son que el arreglo este
ordenado y que se conozca el numero de elementos.
Este método consiste en lo siguiente: comparar el elemento buscado con el elemento situado en la mitad
del arreglo, si tenemos suerte y los dos valores coinciden, en ese momento la búsqueda termina. Pero
como existe un alto porcentaje de que esto no ocurra, repetiremos los pasos anteriores en la mitad
inferior del arreglo si el elemento que buscamos resulto menor que el de la mitad del arreglo, o en la
mitad superior si el elemento buscado fue mayor.

La búsqueda termina cuando encontramos el elemento o cuando el tamaño del arreglo a examinar sea
cero.

encontrado <- falso

primero <- 1
ultimo <- N
mientras primero <= ultimo y no encontrado haz
mitad <- (primero + ultimo)/2
si arreglo[mitad] = valor_buscado entonces
encntrado <- verdadero
en caso contrario
si arreglo[mitad] > valor_buscado entonces
ultimo <- mitad - 1
en caso contrario
primero <- mitad + 1

14. ¿Búsqueda por Hash y ejemplo?

La idea principal de este método consiste en aplicar una función que traduce el valor del elemento
buscado en un rango de direcciones relativas. Una desventaja importante de este método es que puede
ocasionar colisiones.
funcion hash (valor_buscado)
inicio
hash <- valor_buscado mod numero_primo
fin
inicio <- hash (valor)
il <- inicio
encontrado <- falso
repite
si arreglo[il] = valor entonces
encontrado <- verdadero
en caso contrario
il <- (il +1) mod N
hasta encontrado o il = inicio
15. ¿Cuáles son las estructuras de las colas?

La particularidad de una estructura de datos de cola es el hecho de que sólo podemos acceder al
primer y al último elemento de la estructura. Así mismo, los elementos sólo se pueden eliminar por el
principio y sólo se pueden añadir por el final de la cola.

Ejemplos de colas en la vida real serían: personas comprando en un supermercado, esperando para
entrar a ver un partido de béisbol, esperando en el cine para ver una película, una pequeña peluquería,
etc. La idea esencial es que son todas líneas de espera.

16. ¿Cuándo se debe de usar la cola lineal?

Las condiciones a considerar en el tratamiento de colas lineales son las siguientes:

Overflow (cola llena), cuando se realice una inserción.

Underflow(cola vacía), cuando se requiera de una extracción en la cola.
Vacío

17. ¿Cuándo se debe de usar la cola circular?

Una cola circular o anillo es una estructura de datos en la que los elementos están de forma
circular y cada elemento tiene un sucesor y un predecesor. Los elementos pueden consultarse,
añadirse y eliminarse únicamente desde la cabeza del anillo que es una posición distinguida.
Existen dos operaciones de rotaciones, una en cada sentido, de manera que la cabeza del anillo
pasa a ser el elemento sucesor, o el predecesor, respectivamente, de la cabeza actual.

18. ¿Qué es la doble cola y sus usos?

La bicola o doble cola es un tipo de cola especial que permiten la inserción y eliminación de elementos
de ambos extremos de la cola.
Puede representarse a partir de un vector y dos índices, siendo su representación más frecuente una
lista circular doblemente enlazada.
Todas las operaciones de este tipo de datos tienen coste constante.

19. ¿Cola de Prioridades y sus elementos?

Una cola de prioridades es un tipo de dato abstracto similar a una cola en la que los elementos tienen
adicionalmente, una prioridad asignada. En una cola de prioridades un elemento con mayor prioridad
será desencolado antes que un elemento de menor prioridad. Si dos elementos tienen la misma
prioridad, se desencolarán siguiendo el orden de cola.
20. ¿Operaciones en colas y sus elementos?

#ifndef COLA
#define COLA // Define la cola
template <class T>
class Cola{
private:
struct Nodo{
T elemento;
struct Nodo* siguiente; // coloca el nodo en la segunda posición
}* primero;
struct Nodo* ultimo;
unsigned int elementos;
public:
Cola(){
elementos = 0;
}
~Cola(){
while (elementos != 0) pop();
}
void push(const T& elem){
Nodo* aux = new Nodo;
aux->elemento = elem;
if (elementos == 0) primero = aux;
else ultimo->siguiente = aux;
ultimo = aux;
++elementos;
}
void pop(){
Nodo* aux = primero;
primero = primero->siguiente;
delete aux;
--elementos;
}
T consultar() const{
return primero->elemento;
}
bool vacia() const{
return elementos == 0;
}
unsigned int size() const{
return elementos;
}
};
#endif

21. ¿Qué son las pilas y sus elementos?

Una pila (stack en inglés) es una lista ordenada o estructura de datos que permite almacenar y
recuperar datos, el modo de acceso a sus elementos es de tipo LIFO (del inglés Last In, First Out,
«último en entrar, primero en salir») . Esta estructura se aplica en multitud de supuestos en el
área de informática debido a su simplicidad y capacidad de dar respuesta a numerosos procesos.
22. ¿Qué son las notaciones INFIJA, POSTFIJA y PREFIJA?

Notación infija: La notación habitual. El orden es primer operando, operador, segundo operando.

Notación postfija: El orden es primer operando, segundo operando, operador.

Notación prefija: El orden es operador, primer operando, segundo.

23. ¿Qué son las Recursiones?

Recursión es, en ciencias de computación, una forma de atajar y solventar problemas. De hecho,
recursión es una de las ideas centrales de ciencia de computación. Resolver un problema mediante
recursión significa que la solución depende de las soluciones de pequeñas instancias del mismo
problema.

24. ¿Implementar Recursión usando pilas?

|
| 1 , N=0
Factorial <
| N*(n-1)!, N&gt0
|

sp <--0
mientras n <> 1 haz
push(pila,n)
n<--n-1
mientras sp <> 0 haz
factorial<--factorial*pop(pila)

|
| 0 , si a < b
Q <
| Q(a-b,b)+1, si a<=b
|

sp<--0
Q<--0
lee(a), lee(b)
mientras a>=b haz
push(pila,1)
a<--a-b
mientras sp< > 0 haz
Q<-- Q + pop(pila)
25. ¿Operaciones en pilas y Ejemplos de cada uno?

class Stack(object):
def __init__(self):
self.stack_pointer = None

def push(self, element):

self.stack_pointer = Node(element, self.stack_pointer)

def pop(self):
e = self.stack_pointer.element
self.stack_pointer = self.stack_pointer.next
return e

def peek(self):
return self.stack_pointer.element

def __len__(self):
i = 0
sp = self.stack_pointer
while sp:
i += 1
sp = sp.next
return i

class Node(object):
def __init__(self, element=None, next=None):
self.element = element
self.next = next

if __name__ == '__main__':
# small use example
s = Stack()
[s.push(i) for i in xrange(10)]
print [s.pop() for i in xrange(len(s))]