1.
Estructuras lineal
a. Pilas:
Las pilas son estructuras lineales que utilizan arreglos unidimencionales o
listas enlazadas, en inglés se le conoce como LIFO, que quiere decir último en
entrar primero en salir del arreglo o lista enlazada.
La pila se puede representar se las siguientes formas tal como se muestra en
la figura
Las operaciones de Los ingresos, recuperaciones o borrados en la pila se
realiza por la cima o tope de la pila es decir por la parte superior
Las operaciones sobre las pilas son:
Creación o limpieza: Inicializa pila al estado vacío.
Pila vacía: Determina si la pila está vacía.
Pila llena: Determina si la pila está llena.
Apilamiento o ingreso (METER): Inserta un nuevo elemento a la pila (en
la cima).
Desapilamiento o borrado (SACAR): Elimina el elemento en la cima de
la pila.
Pseudocódigo de las operaciones apilamiento y desapilamiento
Apilamiento
Inicio
Leer X
Si tope ≥ N entonces
Escribir “Pila llena”
Sino
topetope+1
pila(tope) X
fin_si
Fin
Desapilamiento
Inicio
Si tope=0 entonces
Escribir “Pila vacía”
Sino
Elementopila(tope)
topetope-1
fin_si
Fin
Notaciones de expresiones aplicando pilas
Infija
Prefija
Posfija
b. Colas
Las colas es la otra estructura lineal que también utiliza los arreglos o listas
enlazadas, en ingles se le conoce como FIFO, es decir primero en entrar
primero en salir del arreglo o lista enlazada
Donde el ingreso es por la cima y la salida o borrado es por el otro extremo o
al inicio de la cola, tal como se muestra en la figura.
Las operaciones con la cola son las siguientes
Creación o limpieza: Inicializa cola al estado vacío.
Pila vacía: Determina si la cola está vacía.
Pila llena: Determina si la cola está llena.
Apilamiento o ingreso (METER): Inserta un nuevo elemento a la cola
(en la cima).
Desapilamiento o borrado (SACAR): Elimina el elemento en la cima de
la cola.
c. sw
2. Estructura no lineal
a. Arboles
b. Grafos
EJERCICIOS
Supongamos que un problema requiere de 2 pilas: A(n1) y B(n2). No disponemos de
mucha memoria y para evitar desbordamiento, es decir que la cantidad de elementos
de A sea mayor que n1 o que la cantidad de elementos de B sea mayor que n2.
Empleamos un solo array C con n1+n2 elementos con la particularidad que la pila A
mete sus datos por la izquierda desde el elemento 1 y la pila B mete sus datos por la
derecha desde el elemento n. Elabore las operaciones meter y sacar para este caso.
Desarrollar el algoritmo que lea una cadena de caracteres y determine si forma un
palindrome. Un palindrome es una secuencia de caracteres que se lee igual hacia
adelante que hacia atrás por ejemplo.
ABLE WAS I ERE I SAW ELBA
El carácter “.” (punto) termina la cadena. Escribir un mensaje indicando si la cadena es
un palindrome. Puede asumir que los datos son correctos y que el número máximo de
caracteres es 80.
Escriba el algoritmo de conversión de una expresión infija a prefija. Supongamos que EI
es una expresión aritmética escrita en notación infija. EI puede tener paréntesis
izquierdos y derechos, operandos (dígitos 0 – 9 y letras A - Z), operadores (^ =
potencia, * = multiplicación, / = división, + = suma, - = resta de acuerdo con sus
prioridades). Efectué la prueba de escritorio para la siguiente expresión: Z
=((((X+1)*2)-5)/Y)
Convertir un número decimal de horas en un número entero de horas, minutos y
segundos. El número de segundos se redondeara al entero más próximo.
Escribir un programa que cree una tabla de conversión de
Pulgadas a centímetros (1 pulgada = 2.54 cm.)
Pies a metros (1 pie = 0.3048 metros = 12 pulgadas)
Millas por hora a Kilometros por hora (50 m/h = 80 Km/h)
Grados a radianes (360 grados = 2π radianes, π =3.141592)
Construir un programa que imprima el calendario correspondiente a un mes y año
determinado. Considere años bisiestos y año julianos entre 1900 y 2020. Los días
domingos deben aparecer resaltados.
Suponiendo que A es un conjunto [1, 3, 5, 7], B es [2, 4, 6] y C es [ 1, 2, 3] . Elabore
un algoritmo y evalué las siguientes expresiones
A+(B+C)
A+(B*C)
A+B+C
C+(A+C)
C-(A-B)
(C-A)-B
Escriba un programa que lea un conjunto de enteros y determine, para cada uno de
ellos, si es primo o no. Pruebe su programa con los cuatro enteros 7, 17, 35, 96
Represente la siguiente expresión algebraica en árbol binario Escriba los recorridos
preorden, inorden y postorden
Elabore el algoritmo estructurado de recorrido inorden de un árbol binario,
empleando una pila.
Elabore el algoritmo que elimine un nodo que tiene 2 hijos de un árbol binario
Dado el siguiente bosque conviértalo a árbol binario
Un sistema operativo particular almacena los trabajos en unas colas de espera para
ejecutarlo de acuerdo con el siguiente esquema. Los usuarios que tengan prioridades
relativas basadas en su número de identificación. 1era prioridad: Ejecutivos ID: 0-99,
2da: Jefes ID: 100-199, 3era: Empleados ID: 200-299; operarios ID 300-399. Dentro
de cada grupo de prioridad los trabajos se ejecutan en el orden en que llegan al
sistema. Si hay un trabajo de prioridad más alta, ejecutarlo antes que otro trabajo de
prioridad más baja. Trabajo de prioridad más baja se ejecutara solo cuando no haya
trabajos de prioridad más alta en espera.
Escribir el algoritmo añadir trabajo que reciba el número de identificación del
usuario y un código del trabajo a ejecutar y añada el código a la cola adecuada para
el nivel de prioridad de dicho usuario.
Escribir el algoritmo obtenersiguientetrabajo, que devuelve el código del trabajo que
este en la cola de mayor prioridad para ejecución (debe quitar el código de la cola).
Suponga que lista es una lista enlazada almacenada en memoria y que contiene sol
valores numéricos. Escribir un algoritmo que determine:
El máximo valor contenido en la lista
Calcular la media de los valores de la lista
Elimine un nodo sucesor de uno determinado
Que inserte un dato después de un nodo especifico
Elabore el algoritmo para realizar una búsqueda binaria en un arreglo numérico A(i),
donde i va desde 1 hasta n. siendo n un numero par
Elabore el algoritmo para ordenar un arreglo numérico A(i), donde i va de 1 hasta n,
emplear el método Shell.
Una familia consta de cuatro hijos de 9, 8, 7 y 6 años de edad. Los padres los regalan
una computadora y un juego donde el factor más importante es el de la edad de los
jugadores las normas del juego son:
─ Es necesario que la suma de las edades de los que quieran jugar sea mayor
que la suma de las edades de los que no quieran.
─ En el caso de que la suma de las edades de los que quieran jugar sea igual a la
suma de las edades de los que no quieran hacerlo se hará lo que desee el de
mayor edad.
Además se imponen las siguientes restricciones:
─ No pueden jugar si solo desea hacerlo uno de los cuatro hijos
─ No pueden jugar si solo desean hacerlo los hijos de edades impares.
Los datos de entrada son la decisión de cada hijo de querer jugar o no . la salida será
la determinación de si jugaran o no (se debe entender que el juego necesita cuatro
jugadores). Elabore un algoritmo
Elabore el algoritmo que calcule la suma de los números pares e impares de los
números primos que estén comprendidos entre 1 y 5000
Elabore un algoritmo que imprima todos los bytes cuya suma de bits sean igual a 7
Elabore un algoritmo que calcule en forma recursiva los factores primos de un
numero N.
Empleando pseudocódigo, elaborar el algoritmo que cetermine las permutaciones de
los números 1, 2, …, n; utilizando un procedimiento recursivo. N es un entero
positivo que se introduce durante la ejecución del programa.
Elaborar elalgoritmo que permita ingresar una cantidad de nuevo soles como un
entero positivo, se debe calcular e imprimir el mejor desglose de moneda, es decir el
mínimo número de unidades monetarias a entregar. Considere las siguientes
unidades monetarias: 1000, 500, 100, 50, 10, 5, 2, 1 (Solución con arreglos)
Elabore el algoritmo que determine el valor mínimo de los valores máximos de cada
fila de la matriz numérica A(i,j)
Determinar si una matriz de 3 filas por 3 columnas es un cuadrado mágico, se
considera un cuadrado mágico aquel en el cual las filas, columnas y diagonales
suman la misma cantidad.
Dado el vector L(x), con n elementos, hallar la cantidad de números pares e impares,
así como la suma de pares e impares. Adicionalmente debe determinar el mayor y el
menor elemento del vector.
Construir un algoritmo para la expedición de facturas a los clientes de una empresa
de acuerdo con las siguientes hipótesis:
Los clientes deudores no tienen descuento.
─ Si un artículo se factura más de 5000 unidades se realizara un 10% de
descuento a los artículos del tipo M y un 5 % a los tipos N.
─ Solo en el caso de los artículos del tipo M, se añadirán al descuento del
apartado B un 5% más si la venta se realizó en la zona fronteriza de Tacna y
un 3% más para la zona fronteriza de tumbes.
