ISCTE - IGE - 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?

[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).

[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):

Página concebida e mantida por Eng. Manuel Menezes de Sequeira (última actualização 1998/05/15) Copyright © 1996-2001 ISCTE