Lisboa, 3 de Julho de 1997
Nome: | Duração:
1 hora (sem consulta). Leia atentamente todo o enunciado antes de começar. Responda no próprio enunciado! Cotações: indicadas junto das questões. Notas: até 8 de Julho de 1997 (na vitrina). Revisão de provas: 8 de Julho de 1997, 9:00-13:30h. Local: Gabinete 9. |
Número: | |
Turma: | |
B. Identidade: |
[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:
[3] 2. b) O método de solução de colisões por encadeamento separado em tabelas de espalhamento consiste:
[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):
sétimo | oitavo e último |
primeiro | segundo | terceiro | quarto | quinto | sexto |
Página
concebida e mantida por Eng. Manuel Menezes de Sequeira (última actualização 1998/05/15) Copyright © 1996-2001 ISCTE |
![]() |