Alg Test Sol

DE

SED MARIBUS

CI Ê

AR DO M

DECEM

E

CA BO

RE

SU P

ENG EN HA R IA

CA

R DE

PÚ

DE LI

IAS

B

VE

I NSTI T UTO

OR RI

C N

E

UNA

Instituto Superior de Engenharia e Ciências do Mar Departamento de Engenharia Electrónica e Computação

Algorítmos e Estruturas de Dados Primeiro Teste 2006/2007 Questão Cotação

1.a) 1

1.b) 1

1.c) 1

1.d) 1

2 2

3 2

4 2

5 2

6 2

7 2

8.a) 1

8.b) 1

8.c) 1

8.d) 1

GRUPO I 1. Considera a seguinte definição para a estrutura de dados necessária à implementação dinâmica de uma lista de inteiros em Linguagem C: struct no { int valor; struct no *seguinte; }; typedef struct no elemento; typedef elemento * lista; Implementa em linguagem C as seguintes funções/procedimentos sobre listas: a) int ValorUltElemento (lista p) – que recebe uma lista e retorna o valor do elemento da última posição da lista. Se a lista for vazia o valor retornado será -1. SOLUÇÃO: int ValorUltElemento(lista p){ lista q = (lista)malloc(sizeof(elemento)); q = p; if(q==NULL) return -1; while(q->seguinte!=NULL) { q = q->seguinte; } return q->valor; } b) void RemoveElemento (lista p, int n) – que dada uma lista e um inteiro n, remove o primeiro elemento com valor igual a n da lista. Se não existir nenhum nó com valor n, nenhum nó será removido. SOLUÇÃO: void RemoveElemento(lista p, int n){ lista q = (lista)malloc(sizeof(elemento)); lista r = (lista)malloc(sizeof(elemento));

DE

SED MARIBUS

CI Ê

AR DO M

DECEM

E

CA BO

RE

SU P

ENG EN HA R IA

CA

R DE

PÚ

DE

LI

IAS

B

VE

I NSTI T UTO

OR RI

C N

E

UNA

Instituto Superior de Engenharia e Ciências do Mar Departamento de Engenharia Electrónica e Computação

q = p; r = p; while(r!=NULL) { if(q->valor==n) { q->seguinte = r->seguinte; free(r); } q = r; r = r->seguinte; } } c) void InsereNoInicio (lista p, elemento x) – que, recebendo uma lista e um elemento x, insere x na primeira posição da lista. SOLUÇÃO: void InsereNoInicio(lista p, elemento x) { lista q = (lista)malloc(sizeof(elemento)); q = p; if(p==NULL) { p = &x; p->seguinte = NULL; } else { x.seguinte = p; p = &x; } } d) int ValorMaximo (lista p) – que retorna o maior valor de entre os valores de todos os elementos da lista. SOLUÇÃO: int ValorMaximo(lista p) { int max = -1; lista q = (lista)malloc(sizeof(elemento)); q = p; while(q!=NULL){ if(q->valor > max){ max = q->valor; } q = q->seguinte; } return max; }

DE

SED MARIBUS

CI Ê

AR DO M

DECEM

E

CA BO

RE

SU P

ENG EN HA R IA

CA

R DE

PÚ

DE

LI

IAS

B

VE

I NSTI T UTO

OR RI

C N

E

UNA

Instituto Superior de Engenharia e Ciências do Mar Departamento de Engenharia Electrónica e Computação

GRUPO II 2. Considera a seguinte expressão: 2 18 7 – 4 11 * 20 5 * + *. Calcula o valor numérico desta expressão com recurso a uma pilha e às operações de push e pop. Apresenta, para cada passo do processo de cálculo, as operações efectuadas e o conteúdo da pilha. SOLUÇÃO: A seguir apresenta-se o conjunto de operações executadas sobre a pilha para calcular o valor da expressão. Apresenta-se o estado da pilha logo após a execução de cada operador.

É claro que a expressão não foi calculada completamente, uma vez que falta pelo menos um operador. O importante era aplicar os operadores sobre os elementos da pilha pela mesma ordem de prioridade em que aparecem na expressão. 3. Considera que foram inseridas numa pilha, inicialmente vazia, a seguinte sequência de valores, por esta ordem: 22 81 54 73 98 21 29 10 3 45 60. Apresenta o conjunto mínimo de operações necessárias para retirar o valor 81 da pilha. Justifica. SOLUÇÃO: Dada a sequência de valores inseridos na pilha, a pilha se encontra no seguinte estado:

DE

SED MARIBUS

CI Ê

AR DO M

DECEM

E

CA BO

RE

SU P

ENG EN HA R IA

CA

R DE

PÚ

DE

LI

IAS

B

VE

I NSTI T UTO

OR RI

C N

E

UNA

Instituto Superior de Engenharia e Ciências do Mar Departamento de Engenharia Electrónica e Computação

Antes de retirar o valor 81 da pilha é necessário retirar todos os elementos que se encontram acima do 81 ou seja, todos os valores inseridos antes do 81. Uma vez que estão 9 valores acima do 81, serão necessários 10 operações de pop() para retirar o valor 81 da pilha (9 para retirar os valores que se encontram acima e 1 para retira o valor 81).

GRUPO III 4. O que entende por uma árvore binária balanceada? SOLUÇÃO: Árvore em que cada nó tem no máximo dois filhos e que, para cada nó, o módulo da diferença entrte o número de descendentes à esquerda e o número de descendentes à direita nunca é superior a um. 5. Dá exemplo de uma árvore binária de profundidade 5, cujos nós têm os seguintes valores: 31 70 44 19 20 8 15 69 14 60 54 16 81 4. SOLUÇÃO: Eis um exemplo:

Foi pedido um exemplo de uma árvore binária de profundidade 5. Então, o objectivo é povoar a árvore, fazendo-a crescer, de modo que um nó nunca tenha mais de dois filhos ( árvore binária) e atinja a profundidade 5 (não deve ultrapasar essa profundidade). Não era necessário ordenar os nós nem

DE

SED MARIBUS

CI Ê

AR DO M

DECEM

E

CA BO

RE

SU P

ENG EN HA R IA

CA

R DE

PÚ

DE

LI

IAS

B

VE

I NSTI T UTO

OR RI

C N

E

UNA

Instituto Superior de Engenharia e Ciências do Mar Departamento de Engenharia Electrónica e Computação

equilibrar a árvore. Aliás, quem equilibrou a árvore de certeza que não conseguiu alcançar a profundidade 5 e, como é óbvio, o exemplo de nada valeu. 6. Percorre em Pos-Ordem a seguinte árvore binária, apresentando a sequência de saída resultante. Recorda-se o algorítmo de percurso em Pos-Ordem: • Se árvore vazia, fim • Percorrer em Pos-Ordem a subárvore esquerda • Percorrer em Pos-Ordem a subárvore direita • Visitar o nó raiz

SOLUÇÃO: A sequência de saída resultante é a seguinte: ABDCGFIHE 7. Que alterações faria ao algoritmo de percurso em Pos-Ordem de modo a gerar a seguinte sequência de saída: IHGFEDCBA? Apresenta o algoritmo modificado. SOLUÇÃO: Designando o novo algorítmo de Nova-Ordem: • Se árvore vazia, fim • Percorrer em Nova-Ordem a subárvore direita • Visitar o nó raiz • Percorrer em Nova-Ordem a subárvore esquerda

GRUPO III 8. Faz uma simulação dos seguintes algoritmos de ordenação sobre as respectivas sequências de valores inteiros. Lembra-se de apresentar as sequências resultantes para cada passo do algoritmo. a) SelectionSort (22 19 35 60 11 7 9 25) SOLUÇÃO:

DE

SED MARIBUS

CI Ê

AR DO M

DECEM

E

CA BO

RE

SU P

ENG EN HA R IA

CA

R DE

PÚ

DE

LI

IAS

B

VE

I NSTI T UTO

OR RI

C N

E

UNA

Instituto Superior de Engenharia e Ciências do Mar Departamento de Engenharia Electrónica e Computação

b) HeapSort (77 24 58 35 60 11 49 22 0 20) SOLUÇÃO: Para este exercício, os interessados terão de procurar a solução em livros ou outras fontes, uma vez que se trata de uma matéria que seria dada numa aula que não cehgou a decorrer. Aliás, numa aula anterior a essa foi feita uma introdução esta matéria.

c) BubbleSort (44 23 60 11 9) SOLUÇÃO:

DE

SED MARIBUS

CI Ê

AR DO M

DECEM

E

CA BO

RE

SU P

ENG EN HA R IA

CA

R DE

PÚ

DE

LI

IAS

B

VE

I NSTI T UTO

OR RI

C N

E

UNA

Instituto Superior de Engenharia e Ciências do Mar Departamento de Engenharia Electrónica e Computação

d) InsertionSort (20 80 7 32 0 15) SOLUÇÃO: