Resolução da Segunda Frequência

ISCTE - IGE - Resolução da Segunda Frequência de

Programação II

Lisboa, 3 de Julho de 1997

[6] 1. Qual a diferença entre os conceitos de pilha e de fila?

Ambas são sequências de elementos. O que varia são as operações de inserção e remoção que suportam. No caso da pilha os elementos são retirados e inseridos sempre no mesmo extremo da sequência. No caso da fila os elementos são retirados dum extremo (sempre o mesmo) e inseridos no extremo oposto da sequência. Assim, numa fila o primeiro a entrar é o primeiro a sair, e numa pilha o último a entrar é o primeiro a sair.

[6] 2. Assinale as afirmações correctas:

[3] 2. a) O algoritmo de procura binária adequa-se sobretudo:

a estruturas de dados que permitem apenas acesso sequencial aos elementos.
a estruturas de dados que permitem também acesso aleatório aos elementos.

[3] 2. b) O método de solução de colisões por encadeamento separado em tabelas de espalhamento consiste:

na geração, através duma função, de novas posições na tabela até encontrar uma livre.
na utilização, em cada posição da tabela, duma lista para os elementos que nela colidirem.

[5] 3. Considere a seguinte definição do nó duma árvore ternária (i.e., onde cada nó tem no máximo três filhos [ou ramos, ou sub-árvores]) guardando valores inteiros:

typedef struct No {
    int valor;			/* valor guardado no no'. */
    struct No *esq, *cen, *dir; /* ponteiros para cada um dos tres ramos. */
} No;

Admita que quando um nó não tem algum dos filhos o respectivo ponteiro tem o valor NULL. Escreva uma função recursiva void mostra(No *raiz) que escreva no ecrã o valor de todos os nós da árvore ternária com origem no nó apontado por raiz (que, se a árvore estiver vazia, será NULL).

void mostra(No *raiz)
{
    if(raiz != NULL)
    {
        /* A ordem das 4 instrucoes abaixo e' irrelevante, excepto quanto
           `a ordem pela qual os valores sao mostrados: */
        printf("%d\n", raiz->valor);
        mostra(raiz->esq);
        mostra(raiz->cen);
        mostra(raiz->dir);
    }
}

[3] 4. Considere as seguintes definições associadas a filas com dimensão limitada implementadas com matrizes "circulares" (as filas guardam elementos que são valores inteiros):

typedef enum {Falso, Verdadeiro} Logico;
#define DIM 10 /* numero maximo de elementos na fila. */
typedef struct {
    int m[DIM]; /* matriz que guarda os elementos que estao na fila. */
    int i; /* indice na matriz do primeiro elemento da fila. */
    int f; /* indice da posicao na fila onde deve ser colocado o proximo elemento
	      a chegar (que será o ultimo). */
    int n; /* numero de elementos correntemente na fila. */
} Fila;

Lembre-se que quer para uma fila vazia quer para uma fila cheia se tem i == f, devendo-se portanto usar o valor de n para distinguir as duas situações. Admita que a fila, imediatamente depois de criada, tem i == f == n == 0.

Escreva uma função Logico Finsere(Fila *fila, int v) que insira o valor v na fila, devolvendo Verdadeiro em caso de sucesso e Falso em caso de erro (se a fila estiver cheia). Não esqueça que a matriz é circular, i.e., a fila vai rodando ao longo da matriz à medida que se inserem e removem elementos, podendo apresentar, por exemplo, a configuração seguinte (em que i = 4, f = 2 e n = 8):

sétimo

oitavo e
último

primeiro

segundo

terceiro

quarto

quinto

sexto

Logico Finsere(Fila *fila, int v)
{
    if(fila == NULL || fila->n == DIM)
        return Falso;
    fila->m[fila->f++] = v;
    if(fila->f == DIM)
        fila->f = 0;
    fila->n++;
    return Verdadeiro;
}

(Ver solução com matrizes dinâmicas na resolução dos exercícios da Aula 8.)