Linguagens e Teoria da Computação
Terça-Feira 11 de Fevereiro de 2020
1
Qual é o objectivo de definir uma estrutura de dados para um programa de computador?
Definir na memoria RAM uma estrutura de representação da informação a que esse programa vai aceder
Definir o formato com que a informação acedida pelo programa ira tomar em memoria secundaria
Nenhuma das respostas anteriores
Indicar aos utilizadores a forma de organização da informação acedida pelo programa
2
Uma pilha é uma estrutura de dados que pode ser implementada através de um vector e onde apenas se pode:
Inserir valores mas não é possível eliminá-los.
Inserir e eliminar valores numa posição arbitrária.
Inserir valores num extremo e eliminar valores no outro extremo.
Inserir e eliminar valores num dos extremos
3
Uma pilha é uma estrutura de dados do tipo LIFO (Last In, First Out). Isto significa que:
Só se podem eliminar elementos na base da pilha.
A inserção e eliminação de elementos são feitas unicamente no topo da pilha.
A inserção e eliminação de elementos são feitas unicamente na base da pilha.
Não se podem inserir elementos na pilha.
4
Uma fila é uma estrutura de dados do tipo FIFO (First In, First Out). Isto significa que:
Só se podem eliminar elementos num dos extremos da lista.
A inserção e eliminação de elementos são feitas unicamente no fim da lista.
A inserção e eliminação de elementos são feitas unicamente no início da lista.
Não se podem inserir elementos na lista.
5
Uma lista ligada caracteriza-se por ser:
Não se podem inserir elementos na lista.
Um conjunto de blocos de memória de características idênticas em posições sequenciais de memória.
Um conjunto de blocos de memória de características idênticas ligadas entre si.
Um conjunto de blocos de memória de características diferentes ligados entre si.
6
Uma estrutura de dados do tipo lista ligada tem vantagem sobre os vetores no que diz respeito a:
Nenhuma das respostas anteriores está correta
Otimização da memória principal necessária para o armazenamento de registos.
Tempo de pesquisa de registos.
Espaço ocupado por um registo.
7
De que forma pode ser feita a pesquisa de um elemento numa lista ligada?
Usando apenas o método de pesquisa linear.
Recorrendo a qualquer um dos métodos de pesquisa estudados.
Recorrendo aos métodos de pesquisa binária e pesquisa por interpolação.
Usando apenas o método de pesquisa binária.
8
Considere a classe java seguinte para representar nós de uma lista simples ligada: Class Node { public int x; public Node próximo} O método seguinte insere um novo nó, referenciado por novo na lista cujo primeiro elemento é referenciado por inicio. Public static Node m1(Node inicio, Node novo) { Novo.proximo = inicio; Return novo;} Este método:
O método está errado porque não testa se a lista está vazia.
Nenhuma das respostas anteriores está correta.
O método insere o novo elemento no fim da lista.
O método insere um novo elemento no início da lista.
9
Considere o método seguinte que usa a mesma classe da pergunta anterior: public static Node int m2 (Node inicio){ if (inicio == null ) return 0; else return 1 + m2 ( inicio.proximo ); } Este método:
Não faz nada porque está errado.
Verifica se a lista está vazia ou se possui uma cauda.
Retorna o número de nós existente na lista.
Pesquisa na lista a ocorrência de um nó com o valor 1.
10
As tabelas de dispersão são estruturas de dados que têm como objetivo:
Garantir um método que seja um bom compromisso entre tempo de pesquisa e espaço de armazenamento de informação.
Estabelecer uma estrutura de dados que minimize o tempo de acesso à informação armazenada.
Otimizar a utilização da memória disponível para armazenamento de registos à custa do tempo de pesquisa.
Garantir um tempo de acesso mínimo à informação armazenada em computadores sem limitações de memória.
11
Qual deverá ser a dimensão de um tabela de dispersão com sondagem linear na qual se pretende armazenar um conjunto de 20 registos garantindo que o fator de carga da tabela não ultrapassa 80%?
19
18
29
25
12
Numa tabela de dispersão podem ocorrer situações designadas por colisões. Uma colisão surge quando:
Existem dois ou mais registos com a mesma chave.
A posição calculada para armazenamento de dois ou mais registos diferentes é a mesma.
O tempo de acesso a dois ou mais registos diferentes é o mesmo.
As respostas b) e c) estão correctas.
13
Uma das formas de resolver as colisões que possam ocorrer numa tabela de dispersão consiste em recorrer a um vector de apontadores para listas ligadas onde são armazenados os registos com o mesmo valor da função de hash. Este método designa-se por:
Duplo hashing.
Sondagem quadrática.
Encadeamento direto.
Sondagem linear.
14
A complexidade temporal da pesquisa de um elemento numa tabela de dispersão é de:
0(1) no caso médio e 0(n) no pior caso.
0(n) no caso médio e 0(1) no pior caso.
0(n), se for usado o método de sondagem linear e 0(1), se for usado o método de duplo hashing.
0(1) em qualquer caso.
15
A pesquisa de um nó numa árvore binária balanceada e ordenada é de complexidade:
O( log n ).
0( 1 ).
O( n! ).
O( n ).
16
Numa fila com prioridade implementada com um heap representado implicitamente, a operação de localizar o elemento de maior prioridade possui uma complexidade de:
O( n log n ).
O( n }.
O( log n ).
O( 1 ).
17
A complexidade temporal do algoritmo de ordenação HeapSort é:
0( n log n ) em qualquer caso, não necessitando de memória adicional.
0( n log n ) no caso médio e 0( n2 ) no pior caso, não necessitando de memória adicional.
0( n log n ) em qualquer caso, necessitando de memória adicional.
0( log n ) em qualquer caso, não necessitando de memória adicional.
18
Diz-se que uma árvore binária é balanceada (perfeitamente equilibrada) se, para cada nó:
Nenhuma das respostas anteriores está correcta.
A diferença entre o número de nós das sub-árvores esquerda e direita é no máximo igual a 1.
A diferença entre o número de nós das sub-árvores esquerda e direita é no mínimo igual a 1.
A diferença entre o número de nós folha das sub-árvores esquerda e direita é no máximo igual a 1.
19
Para uma árvore binária ordenada verifica-se que o valor da chave armazenada em cada nó:
É maior ou igual que qualquer valor armazenado nas suas sub-árvores.
É maior que os valores armazenados na sub-árvore esquerda e igual aos valores armazenados na sub-árvore direita.
É menor que qualquer valor armazenado nas suas sub-árvores.
É maior que os valores armazenados na sub-árvore esquerda e menor que os valores armazenados na sub-árvore direita.
20
Esta árvore pode ser classificada como:
Desequilibrada em altura.
Ordenada.
Não balanceada.
Todas as respostas anteriores estão corretas.
21
Qual a sequência de valores obtida se a árvore for visitada em pós-ordem?
a, c, b, e, f, d, j, i, o, s, p, m, g
a, b, c, d, e, f, g, i, j, m, o, p, s
g, d, m, b, f, i, p, a, c, e, j, o, s
a, c, b, e, f, j, i, o, s, p, d, m, g
22
Numa árvore binária do tipo heap, representada graficamente, o maior valor encontra-se:
Nenhuma das respostas anteriores está correcta.
No primeiro nó folha.
No nó mais abaixo e mais à direita.
Na raiz.
23
Na representação implícita de uma árvore binária, verifica-se que, para um dado nó na posição i, com i < n/2 (n é o número de nós):
O seu filho direito encontra-se na posição 2i +1.
Nenhuma das respostas anteriores está correcta.
O seu filho esquerdo encontra-se na posição 2i + 1.
O seu filho direito encontra-se na posição 2i.
24
Para representar implicitamente esta árvore obtinha-se um vector com valores na sequência:
16, 11, 15, 8, 9, 6, 13, 5, 3, 1, 7, 4, 2, 10, 12.
16, 15, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1.
15, 10, 8, 5, 3, 9, 1, 7, 16, 6, 4, 2, 13, 11, 12.
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15, 16.
25
A árvore representada na pergunta anterior é:
Um heap.
Uma árvore ordenada.
Uma árvore balanceada mas não equilibrada em altura.
Nenhuma das respostas anteriores está correcta.
26
Uma das estruturas de dados básica estudada é o array. Esta estrutura de dados caracteriza-se por:
Nenhuma das respostas anteriores está correcta.
Armazenar um conjunto de valores obrigatoriamente de tipos diferentes.
Armazenar um conjunto de valores onde apenas é possível inserir e eliminar elementos num dos extremos.
Armazenar um conjunto de valores do mesmo tipo.
27
O primeiro elemento de uma lista designa-se por:
Cabeça da lista.
Próximo elemento.
Cauda da lista.
Índice da lista.
28
O desenho seguinte representa uma estrutura de dados para armazenamento de valores inteiros. A estrutura representada é:
Lista ligada simples.
Pilha.
Lista circular duplamente ligada.
Lista circular.
29
Uma classe Java capaz de representar os nós da lista da pergunta anterior poderia ser:
class Node { int x; Node prox; Node primeiro; }
class Node { int x; Node prox; }
class Node { int x; Node ant; Node prox; }
class Node { Node x; int ant; int prox; }
30
Considere a classe Java seguinte: class Lst { int x; Lst ant; Lst prox; } Esta classe é adequada para implementar listas de números inteiros do tipo:
Lista duplamente ligada.
Nenhuma das respostas anteriores está correta.
Pilha.
Lista linear simples.
31
Numa lista simplesmente ligada circular:
O primeiro nó guarda o endereço do último nó.
Cada nó guarda o endereço do primeiro nó.
O último nó guarda o endereço do primeiro nó.
O último nó guarda o endereço do seu antecessor.
32
Qual deverá ser a dimensão de um tabela de dispersão com sondagem linear na qual se pretende armazenar um conjunto de 40 registos garantindo que o factor de carga da tabela não ultrapassa 80%?
53
50
41
37
33
Uma das formas de resolver as colisões que possam ocorrer numa tabela de dispersão consiste em procurar a primeira posição livre após a posição que resultou em colisão. Este método designa-se por:
Sondagem quadrática.
Encadeamento direto.
Duplo hashing.
Sondagem linear.
34
Uma árvore binária é do tipo AVL se:
A diferença entre o número de níveis das sub-árvores esquerda e direita é no mínimo igual a 1.
A diferença entre o número de nós das sub-árvores esquerda e direita é no mínimo igual a 1.
A diferença entre o número de níveis das sub-árvores esquerda e direita é no máximo igual a 1.
A diferença entre o número de nós das sub-árvores esquerda e direita é no máximo igual a 1.
35
Uma árvore binária degenerada é uma árvore que:
Cada nó possui, no máximo, duas sub-árvores.
Não possui folhas.
Cada nó possui, no máximo, uma sub-árvore.
Não possui raiz.
36
Uma vantagem de uma estrutura do tipo árvore binária balanceada e ordenada em relação a uma lista ligada simples é:
A complexidade dos algoritmos de pesquisa de informação é maior.
Cada nó ocupa um espaço de memória menor.
A complexidade dos algoritmos de pesquisa de informação é menor.
Nenhuma das respostas anteriores está correta.
37
Quando se implementa um algoritmo para eliminação de um nó numa árvore binária ordenada, que situações são necessárias ter em conta, relativamente ao nó a eliminar?
O nó é uma folha; o nó só tem uma sub-árvore; o nó tem as duas sub-árvores.
O nó é uma folha; o nó é a raiz; o nó tem as duas sub-árvores.
O nó é a raiz; o nó só tem uma sub-árvore; o nó tem as duas sub-árvores.
O nó é uma folha; o nó só tem uma sub-árvore.
38
Esta árvore pode ser classificada como:
Todas as respostas anteriores estão erradas.
Ordenada.
Desequilibrada em altura.
Não balanceada.
39
A árvore representada na pergunta anterior possui:
Possui 14 níveis.
Não possui níveis.
Possui 3 níveis.
Possui 4 níveis.
40
Qual a sequência de valores obtida se a árvore for visitada em ordem?
a, b, c, d, e, f, g, i, j, m, o, p, s
g, d, m, b, i, p, a, c, e, j, o, s
a, c, b, e, f, j, i, o, s, p, d, m, g
a, c, b, e, f, d, j, i, o, s, p, m, g
41
Em relação à árvore representada na pergunta anterior, o nó com o conteúdo s é:
Um nó sem ascendentes.
Nenhuma das respostas anteriores está correcta.
O nó raiz.
Um nó folha.
42
A árvore representada na pergunta 18 (anterior), é (tenha em conta a ordem alfabética dos caracteres):
Balanceada e ordenada.
Balanceada mas não é equilibrada em altura.
Um heap e é balanceada.
Um heap e não é balanceada.
43
Na representação implícita de uma árvore binária, com n elementos, o último nó com filhos está na posição:
n / 2.
Nenhuma das respostas anteriores está correta.
n
2 * n.
44
Considere o método Java seguinte que permite inserir um novo valor (x) num heap com N nós, representado implicitamente por um vector de dimensão DIM. O método upHeap destina-se à reconstrução do heap após a inserção de um novo valor. public void insert( int []a, int x ) { if( N <= DIM ){ a[++N] = x; upHeap ( a, N); } } Tendo em conta uma representação gráfica do heap e de acordo com o método acima, o novo valor é inserido:
Criando um novo nó na posição mais abaixo e mais à direita, respectivamente.
No nó raiz.
Numa posição arbitrária.
A seguir ao último nó com filhos.
45
Uma fila com prioridade é uma estrutura da dados para armazenamento de uma colecção de elementos, na qual:
Podem-se inserir elementos arbitrariamente mas apenas se retira o elemento de maior prioridade.
Podem-se retirar elementos arbitrariamente mas apenas se insere o elemento de maior prioridade.
Apenas se pode inserir ou retirar o elemento de maior prioridade.
Apenas se podem inserir elementos num extremo e retirá-los do outro extremo.
46
O facto de o HeapSort e o QuickSort apresentarem a mesma complexidade no caso médio significa que é indiferente a utilização de qualquer um destes dois métodos de ordenação. Esta afirmação:
Está correcta desde que se garanta a sua aplicação sempre com um conjunto de dados aleatório.
Não está correcta porque os dois métodos não são comparáveis dado que o HeapSort se destina a vectores que representam implicitamente uma árvore binária do tipo heap.
Não está correcta porque a complexidade apenas indica a forma como evolui o tempo de execução em função dos dados de entrada e não fornece informação sobre o tempo real de execução num determinado ambiente.
Não está correcta porque a complexidade dos dois métodos, no caso médio, não é igual.
