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:
Não se podem inserir elementos na pilha.
A inserção e eliminação de elementos são feitas unicamente na base da pilha.
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.
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 diferentes ligados entre si.
Um conjunto de blocos de memória de características idênticas ligadas 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
Tempo de pesquisa de registos.
Otimização da memória principal necessária para o armazenamento 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 binária.
Recorrendo a qualquer um dos métodos de pesquisa estudados.
Usando apenas o método de pesquisa linear.
Recorrendo aos métodos de pesquisa binária e pesquisa por interpolação.
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:
Nenhuma das respostas anteriores está correta.
O método insere o novo elemento no fim da lista.
O método está errado porque não testa se a lista está vazia.
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:
Pesquisa na lista a ocorrência de um nó com o valor 1.
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.
10
As tabelas de dispersão são estruturas de dados que têm como objetivo:
Garantir um tempo de acesso mínimo à informação armazenada em computadores sem limitações de memória.
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.
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%?
29
25
19
18
12
Numa tabela de dispersão podem ocorrer situações designadas por colisões. Uma colisão surge quando:
A posição calculada para armazenamento de dois ou mais registos diferentes é a mesma.
Existem dois ou mais registos com a mesma chave.
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:
Encadeamento direto.
Duplo hashing.
Sondagem quadrática.
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( 1 ).
O( log n ).
O( n }.
O( n log n ).
17
A complexidade temporal do algoritmo de ordenação HeapSort é:
0( n log n ) em qualquer caso, 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, não 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ínimo 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.
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 que os valores armazenados na sub-árvore esquerda e menor que os valores armazenados na sub-árvore direita.
É maior ou igual que qualquer valor armazenado nas suas sub-árvores.
É menor 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.
20
Esta árvore pode ser classificada como:
Não balanceada.
Desequilibrada em altura.
Todas as respostas anteriores estão corretas.
Ordenada.
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
g, d, m, b, f, i, p, a, c, e, j, o, s
a, b, c, d, e, f, g, i, j, m, o, p, 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.
Na raiz.
No nó mais abaixo e mais à direita.
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 direito encontra-se na posição 2i.
O seu filho esquerdo encontra-se na posição 2i + 1.
24
Para representar implicitamente esta árvore obtinha-se um vector com valores na sequência:
16, 15, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1.
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15, 16.
15, 10, 8, 5, 3, 9, 1, 7, 16, 6, 4, 2, 13, 11, 12.
16, 11, 15, 8, 9, 6, 13, 5, 3, 1, 7, 4, 2, 10, 12.
25
A árvore representada na pergunta anterior é:
Nenhuma das respostas anteriores está correcta.
Uma árvore balanceada mas não equilibrada em altura.
Uma árvore ordenada.
Um heap.
26
Uma das estruturas de dados básica estudada é o array. Esta estrutura de dados caracteriza-se por:
Armazenar um conjunto de valores onde apenas é possível inserir e eliminar elementos num dos extremos.
Armazenar um conjunto de valores do mesmo tipo.
Nenhuma das respostas anteriores está correcta.
Armazenar um conjunto de valores obrigatoriamente de tipos diferentes.
27
O primeiro elemento de uma lista designa-se por:
Próximo elemento.
Índice da lista.
Cauda da lista.
Cabeça da lista.
28
O desenho seguinte representa uma estrutura de dados para armazenamento de valores inteiros. A estrutura representada é:
Lista circular duplamente ligada.
Pilha.
Lista ligada simples.
Lista circular.
29
Uma classe Java capaz de representar os nós da lista da pergunta anterior poderia ser:
class Node { int x; Node ant; Node prox; }
class Node { int x; Node prox; }
class Node { int x; Node prox; Node primeiro; }
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:
Pilha.
Lista linear simples.
Nenhuma das respostas anteriores está correta.
Lista duplamente ligada.
31
Numa lista simplesmente ligada circular:
O último nó guarda o endereço do primeiro nó.
O primeiro nó guarda o endereço do último nó.
O último nó guarda o endereço do seu antecessor.
Cada nó guarda o endereço do primeiro nó.
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%?
37
41
50
53
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:
Duplo hashing.
Encadeamento direto.
Sondagem quadrática.
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, uma sub-árvore.
Não possui raiz.
Não possui folhas.
Cada nó possui, no máximo, duas sub-árvores.
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 é menor.
Cada nó ocupa um espaço de memória menor.
A complexidade dos algoritmos de pesquisa de informação é maior.
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ó é a raiz; o nó tem as duas sub-árvores.
O nó é uma folha; o nó só tem uma sub-árvore.
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; o nó tem as duas sub-árvores.
38
Esta árvore pode ser classificada como:
Todas as respostas anteriores estão erradas.
Não balanceada.
Desequilibrada em altura.
Ordenada.
39
A árvore representada na pergunta anterior possui:
Possui 14 níveis.
Possui 4 níveis.
Possui 3 níveis.
Não possui níveis.
40
Qual a sequência de valores obtida se a árvore for visitada em ordem?
a, c, b, e, f, j, i, o, s, p, d, m, g
g, d, m, b, i, p, a, c, e, j, o, s
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
41
Em relação à árvore representada na pergunta anterior, o nó com o conteúdo s é:
Um nó folha.
Nenhuma das respostas anteriores está correcta.
O nó raiz.
Um nó sem ascendentes.
42
A árvore representada na pergunta 18 (anterior), é (tenha em conta a ordem alfabética dos caracteres):
Balanceada mas não é equilibrada em altura.
Um heap e não é balanceada.
Um heap e é balanceada.
Balanceada e ordenada.
43
Na representação implícita de uma árvore binária, com n elementos, o último nó com filhos está na posição:
2 * n.
Nenhuma das respostas anteriores está correta.
n
n / 2.
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:
Apenas se podem inserir elementos num extremo e retirá-los do outro extremo.
Podem-se retirar elementos arbitrariamente mas apenas se insere o elemento de maior prioridade.
Podem-se inserir elementos arbitrariamente mas apenas se retira o elemento de maior prioridade.
Apenas se pode inserir ou retirar o elemento de maior prioridade.
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:
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.
Está correcta desde que se garanta a sua aplicação sempre com um conjunto de dados aleatório.
Não está correcta porque a complexidade dos dois métodos, no caso médio, não é igual.
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.
