Pilhas Çistas Encadeadas

Pilhas, Filas e Listas

1. Explique como implementar duas pillhas em um único vetor de tamanho n, de tal

modo que nenhuma das pilhas sofra estouro positivo (rejeite uma nova inserção

por estar lotada), a menos que o número total de elementos em ambas as pilhas

juntas seja n. As operações PUSH e POP devem ser executadas no tempo O(1).

2. Enquanto uma pilha permite a inserção e a eliminação de elementos em apenas

uma extremidade e um fila permite a inserção em uma extremidade e a eliminação

na outra extremidade, uma deque (double-ended queue, ou fila de extremidade

dupla) permite a inserção e a eliminação em ambas as extremidades. Escreva

quatro procedimentos de tempo O(1) para inserir elementos e eliminar elementos

de ambas as extremidades de uma deque construída a partir de um vetor.

3. Mostre como implementar uma fila usando duas pilhas. Analise o tempo de

execução das operações sobre as filas.

4. Mostre como implementar uma pilha usando duas filas. Analise o tempo de

execução das operações sobre pilhas.

5. Implemente uma pilha usando uma lista simplesmente encadeada. As operações

PUSH e POP devem demorar o tempo O(1).

6. Implemente uma fila usando uma lista simplesmente encadeada. As operações

ENQUEUE e DEQUEUE devem demorar o tempo O(1).

7. Forneça um procedimento não recursivo de tempo Θ() que inverta uma lista

simplesmente encadeada de n elementos. Qualquer consumo de memória além do

espaço de armazenamento necessário para a própria lista deve ter tamanho O(1).

8. Explique como implementar listas duplamente encadeadas usando apenas um

valor de ponteiro np[x] por item, em lugar dos dois valores usuais (próximo e

anterior). Suponha que todos os valores de ponteiros possam ser interpretados

como inteiros de k bits e defina np[x] como np[x] = próximo[x] XOR anterior[x], o

“ou exclusivo” de k bits de próximo [x] e anterior[x].(O valor NULL é representado

por 0). Certifique-se de descrever as informações necessárias para obter acesso ao

início da lista. Mostre como implementar operações para inserir, remover e

recuperar elementos nesta lista. Mostre também como inverter a ordem dos

elementos nesta lista em tempo O(1).

9. Considere uma lista seqüencial definida pelas estruturas de dados abaixo:

typedef struct // registro de um aluno

{ char nome[41]; // nome do aluno

char matricula[11]; // matricula do aluno

float cr; // C.R. do aluno

} ALUNO;

typedef struct // lista de alunos

{ ALUNO aluno[200]; // registros dos alunos

int numAlunos; // numero de alunos na lista

} LISTA_ALUNOS; a. Calcule o tamanho (em bytes) dos tipos de dados ALUNO e

LISTA_ALUNOS, considerando que o tipo char tem tamanho de 1 byte e

os tipos int e float têm tamanho de 4 bytes.

b. Construa uma função que retorne a quantidade de alunos com coeficiente

de rendimento maior ou igual a 7.

Protótipo: int numAlunosCrAlto(LISTA_ALUNOS *pLista)

c. Construa uma função que receba a matrícula de um aluno e exclua este

aluno da lista. A função deve retornar o valor 0 caso a exclusão seja bem-

sucedida, ou o valor 1 caso o aluno não seja encontrado na lista.

Protótipo: int excluirAluno(LISTA_ALUNOS *pLista, char

*matricula)

10. Considere uma lista ordenada de itens disponíveis no almoxarifado de uma fábrica,

sendo que cada item é identificado por um código numérico exclusivo:

typedef struct // item do almoxarifado

{

int codItem; // código de identificação do item

char descricao[21]; // texto descritivo do item

int qtdEstoque; // quantidade disponível em estoque

} ITEM;

typedef struct // lista de itens

{

ITEM item[5000]; // registros dos itens

int numItens; // numero de itens na lista

} LISTA_ITENS;

a. Supondo que a lista não esteja ordenada, construa uma função que receba

um código de identificação de item e retorne a quantidade disponível em

estoque para o item correspondente (caso o item não exista na lista, deve

ser retornado o valor 0).

Protótipo: int pesquisar(LISTA_ITENS *pLista, int cod)

b. Supondo agora que a lista esteja ordenada, construa uma nova versão da

mesma função construída no item (a) utilizando pesquisa binária.

11. Nesta questão, você implementará uma