Lista 2 Pilha, Fila e árvores

Prévia do material em texto

UNIVERSIDADE FEDERAL DE GOIÁS 
Departamento de Ciência da Computação – Regional Jataí 
Curso: Ciência da Computação Período: 3º Ano: 2017 Semestre: 01 
Disciplina: Estrutura de Dados 1 Avaliação: Lista de exercícios Valor: -- 
Professor (a): Franciny Medeiros Barreto Data: ___/___/___ 
Aluno (a): Matrícula: 
Lista de exercícios 1 – Pilha, fila e árvore. Nota: 
 
Instruções: 
- Todos os códigos devem ser desenvolvidos em linguagem C. 
- Escolha 4 exercícios da lista para fazer e submeter no SIGAA na data de hoje (23/08/2017) 
até o final da aula (15:10). 
- Os demais exercícios devem ser entregues na monitoria. 
 
1) Faça um programa que verifique se uma dada cadeia de caracteres é ou não 
palíndroma. Uma cadeia é palíndroma quando lida da esquerda para a direita e da direita 
para a esquerda são iguais. Por exemplo: “subinoonibus” é palíndroma. Para resolver o 
problema use a estrutura de dados de pilha. 
2) Seja S uma cadeia formada exclusivamente por caracteres “+” e “-“, seja N o número 
máximo de elementos que uma pilha pode conter. Codificar um programa que quando o 
caracter da cadeia for “+” empilhe (Push) e se for “-“ desempilhe. Indicar se ocorreu 
“Estouro de Pilha” ou “Pilha Vazia”. 
3) Seja A uma seqüência formada por 20 números inteiros. Codifique um programa que 
empilhe na pilha A os números pares e na pilha B os números impares. 
4) Dada duas pilhas de elementos inteiros codificar um algoritmo que crie a pilha P3 
intercalando os elementos da pilha P1 e P2. 
 
Exemplo: P1: [1, 2, 3, 4], 
P2: [5, 6, 7, 8], 
P3: [8, 4, 7, 3, 6, 2, 5, 1]. 
5) Elabore um programa que transforme um número decimal em binário. Usando a 
estrutura de pilha. 
6) Considere a implementação de filas usando arranjos circulares. Escreva uma função 
FuraFila(TipoFila* pFila, TipoItem x) que insere um item na primeira posição da fila. O 
detalhe é que seu procedimento deve ser O(1), ou seja, não pode movimentar os outros 
itens da fila. (observe que este neste caso, estaremos desrespeitando o conceito de FILA 
– primeiro a entrar é o primeiro a sair). 
7) Existem partes de sistemas operacionais que cuidam da ordem em que os programas 
devem ser executados. Por exemplo, em um sistema de computação de 
tempocompartilhadao (“time-shared”) existe a necessidade de manter um conjunto de 
processo em uma fila, esperando para serem executados. Escreva um programa que seja 
capaz de ler uma série de solicitações para: 
a) Incluir novos processos na fila de processo; 
b) Retirar da fila o processo com o maior tempo de espera; 
c) Imprimir o conteúdo da lista de processo em determinado momento. Assuma que 
cada processo é representado por um registro composto por um número identificador do 
processo. 
8) Como você implementaria uma fila de pilhas? Uma pilha de filas? Uma fila de filas? 
Escreva rotinas para implementar as operações corretas para cada uma destas estruturas 
de dados. 
9) Crie um algoritmo em pseudo-código para representar a criação e inserção de 
elementos em uma árvore binária. 
10) Crie um algoritmo em pseudo- código que calcula a profundidade de um nó em uma 
árvore binária A. Considere como dados de entrada a árvore binária A e o nó S.