Anúncios
1
Dada a árvore abaixo, apresente quais são os nós folhas da árvore.
2,5,5
2,5,7
2
Uma estrutura de dados que possui dois campos: um ponteiro e campo de informação denomina-se:
árvore binária
vetor
lista encadeada simples
lista encadeada dupla
pilha
3
A estrutura de dados que consiste no armazenamento de cada elemento em um endereço calculado a partir da aplicação de uma função sobre a chave de busca denomina-se:
árvore AVL
árvore B
lista encadeada
árvore binária
tabela hash
4
Suponha que temos números entre 1 e 1000 em uma árvore de pesquisa binária e queremos procurar pelo número 363. Quais das sequências a seguir não poderia ser uma sequência de nós examinados?
925, 202, 911, 240, 912, 245, 363
935, 278, 347, 621, 299, 392, 358, 363
2, 399, 387, 219, 266, 382, 381, 278, 363
2, 252, 401, 398, 330, 344, 397, 363
994, 220, 911, 244, 798, 258, 362, 363
5
A busca binária é conhecida também como busca logarítmica. Sobre a busca binária, assinale a alternativa INCORRETA
Em uma sequência ordenada de forma crescente, caso o elemento procurado seja menor que o elemento do meio, continua-se a busca com o subconjunto da direita. Em caso contrário, com o subconjunto da esquerda
Para um conjunto de 15 elementos, ocorreria, no mínimo, 1 comparação e, no máximo, 4 comparações
Considerando uma sequência qualquer, deve-se dividir o conjunto ao meio e verificar se o elemento procurado é igual ao elemento central
Quando comparada com a busca sequencial, a busca binária, há uma redução logarítmica dos elementos a serem pesquisados
Se o elemento procurado estiver entre os últimos ou não estiver no conjunto, a busca linear poderá ser mais lenta do que a busca binária
6
Em relação a estrutura de dados árvore, avalie se são verdadeiras (V) ou falsas (F) as afirmativas a seguir. I O número de nível mais alto de uma árvore é conhecido como grau de uma árvore. II Quando um nó possui grau zero, diz-se que ele é um nó terminal ou folha. III Árvores são estruturas de dados estáticas em que os dados possuem uma ordem pré-definida, os elementos são dispostos de acordo com uma hierarquia e existe um nó principal conhecido como raiz. As afirmativas I, II e III são, respectivamente:
V, V e F
V, F e F
F, F e F
V, F e V
F, V e F
7
Três aspectos são fundamentais no que se refere a estruturas de dados: a abstração, a distinção entre estruturas estáticas e dinâmicas e o conceito de ponteiro. A partir dessa informação, assinale a opção correta.
Listas, que podem ser classificadas como estrutura estática, consistem em uma coleção de elementos que aparecem em ordem combinatória
As pilhas, conhecidas como estruturas FIFO (first-in, first-out), possuem duas principais operações, denominadas push e pop; a primeira insere um elemento na estrutura, a segunda remove um elemento da estrutura
Na estrutura do tipo fila, as inserções e remoções são executadas por uma única extremidade da estrutura, de modo que o último elemento a entrar na estrutura é o primeiro a ser removido
Em uma tabela hash os elementos são mapeados por meio de uma função de dispersão. Na situação em que dois o mais elementos são mapeados para uma mesma posição na tabela, situação denominada de colisão, há necessidade de se aplicar um tratamento
A estrutura do tipo matriz é conhecida como um arranjo retangular chamado arranjo homogêneo ou matriz, em que o termo homogêneo significa que todos os elementos do arranjo são de tipos diferentes
8
A sequência de chaves 20 – 30 – 25 – 31 – 12 – 15 – 8 – 6 – 9 – 14 – 18 é organizada em uma árvore binária de busca. Em seguida, a árvore é percorrida em pré-ordem. Qual é a sequência de nós visitados?
6 – 8 – 9 – 12 – 14 – 15 – 18 – 20 – 25 – 30 – 31
6 – 8 – 9 – 14 – 15 – 18 – 12 – 25 – 30 – 31 – 20
6 – 9 – 8 – 14 – 18 – 15 – 12 – 25 – 31 – 30 – 2
20 – 30 – 31 – 25 – 12 – 15 – 18 – 14 – 8 – 9 – 6
20 – 12 – 8 – 6 – 9 – 15 – 14 – 18 – 30 – 25 – 31
9
Sobre as estruturas de dados conhecidas como árvores, selecione a alternativa CORRETA
O percurso de uma árvore binária, conhecido como pré-ordem, visita a raiz, depois a sub-árvore esquerda e depois a sub-árvore direita
Uma árvore binária é aquela que tem como conteúdo somente valores binários
Uma árvore é composta por duas raízes, sendo uma principal e a outra secundária
As operações básicas sobre árvores são extrair-raiz e alterar-folha
O percurso de uma árvore binária, conhecido como pós-ordem, visita a sub-árvore direita, depois a raiz e depois a subárvore esquerda
10
Qual número de níveis da árvore de busca binária formada pela inserção das chaves 4, 1, 0, 5, 3, 7, 2, 6, 9 e 8 (nesta ordem)?
4 níveis
5 níveis
11
Na construção de uma árvore AVL a partir da inserção das chaves 20, 10, 5, 30, 25, 27 e 28 9 (nesta ordem), quais são as rotações necessárias aplicadas para que a árvore se mantenha balanceada?
rotação in ordem
.
12
Considere que a empresa "Manausprev" armazena os nomes dos beneficiários de aposentadorias em uma Árvore de Busca Binária. Ao se armazenar, nesta ordem, os nomes Marcos, José, Carolina, Paula, Rui, Pedro e Maria, a Árvore de Busca Binária resultante
requer no máximo 4 comparações para localizar qualquer um dos 7 nomes
requer no máximo 3 comparações para localizar qualquer um dos 7 nomes
é completa
possui como folhas os nomes Rui e Maria
tem 3 níveis para armazenar os 7 nomes
13
Seja T uma árvore balanceada do tipo AVL vazia. Supondo que os elementos 5, 10, 12, 8, 7, 11 e 13 sejam inseridos nessa ordem em T, a sequência que corresponde a um percurso de T em pós-ordem é:
5, 8, 7, 11, 13, 12 e 10
5, 10, 12, 8, 7, 11 e 13
10, 7, 5, 8, 12, 11 e 13
5, 7, 8, 10, 11, 12 e 13
10, 8, 5, 7, 12, 11 e 13
14
Em uma árvore de busca binária do tipo AVL, as alturas das duas sub-árvores de um nó qualquer diferem em no máximo 1. A construção de uma árvore desse tipo, inicialmente vazia, por meio da inserção sucessiva de nós, utiliza uma certa operação para manter o balanceamento desejado quando necessário. Essa operação é:
rotação
empilhamento
desempilhamento
poda
concatenação
15
Sejam [3, 1, 2, 7, 5, 4, 6], [3, 1, 2, 6, 4, 5, 7] e [4, 2, 1, 3, 6, 5, 7] as sequências produzidas pelo percurso em pré-ordem das árvores binárias de busca T1, T2 e T3, respectivamente, é correto afirmar que é(são) árvore(s) balanceada(s) do tipo AVL
T1 e T2
T1 e T3
T1, T2 e T3
T1
T2 e T3
16
Seja T uma árvore balanceada do tipo AVL vazia. Supondo que os elementos 5, 10, 12, 8, 7, 11 e 13 sejam inseridos nessa ordem em T, a sequência que corresponde a um percurso de T em pré-ordem é:
10, 7, 5, 8, 12, 11 e 13
10, 8, 5, 7, 12, 11 e 13
5, 7, 8, 10, 11, 12 e 13
5, 8, 7, 11, 13, 12 e 10
5, 10, 12, 8, 7, 11 e 13
17
Uma estrutura de dados onde cada nó mantém uma informação adicional, chamada fator de balanceamento, que indica a diferença de altura entre as subárvores esquerda e direita, é conhecida por árvore:
binária
ordenada
de busca binária
hiberbólica
AVL
18
Dada a árvore de busca binária abaixo, assinale a alternativa que representa o seu percurso in-ordem
9, 12, 14, 17, 19, 23, 50, 54, 67, 72, 76
76, 72, 67, 54, 50, 23, 19, 17, 14, 12, 9
9, 14, 12, 19, 23, 17, 67, 54, 76, 72, 50
50, 17, 72, 12, 23, 54, 76, 9, 14, 19, 67
50, 17, 12, 9, 14, 23, 19, 72, 54, 67, 76
19
Pesquisar um valor que corresponda a um valor chave em uma árvore AVL com 128 elementos requer no máximo:
cinco comparações
quatro comparações
oito comparações
sete comparações
seis comparações
20
Um dos exemplos de estrutura de dados é a lista encadeada simples. Com relação a esse tipo de lista, é correto afirmar:
É necessário definir o seu tamanho no momento da sua criação, pois se trata de uma estrutura de dados estática
Possui a característica de que o último elemento da lista possui um ponteiro para o primeiro elemento da lista
Na inserção de um novo elemento, é necessário realizar a atualização dos ponteiros dos elementos envolvidos, não sendo necessário realizar o deslocamento físico dos elementos
a recuperação de qualquer elemento da lista, não é necessário percorrer os outros elementos. Dessa forma, o elemento buscado é acessado diretamente na posição onde se encontra
Quando essa estrutura é utilizada, os elementos da lista sempre estarão armazenados sequencialmente na memória física
21
Sobre listas encadeadas, é INCORRETO afirmar que
possuem tamanho fixo
os dados são armazenados dinamicamente
o final da lista faz uma referência para nulo
são acessadas pelo primeiro nó da lista
pilhas e filas podem ser implementadas como listas encadeadas
22
Uma árvore de busca binária cheia tem, no 5º nível, uma quantidade de nós igual a
15
64
32
31
23
O algoritmo de Huffman, comumente utilizado em procedimentos para compressão de dados, baseia-se na utilização de códigos de tamanho
fixo, que são importados de uma biblioteca padrão previamente estabelecida para cada tipo de símbolo
variável, que dependem da ordenação lógica de todos os possíveis símbolos de entrada
fixo, que estabelecem uma espécie de índice, que é associado a cada possível símbolo de entrada
fixo, que dependem da probabilidade de ocorrência de cada possível símbolo de entrada
variável, que dependem da probabilidade de ocorrência de cada possível símbolo de entrada
24
Uma certa tabela de dispersão (hash) em um programa de computador utiliza a função de espalhamento h(k) = k mod m, em que k é a chave e m é o tamanho de um vetor de listas ligadas indexado por h(k). Para m = 5013, o índice obtido para k = 10034 é:
2
8
5021
15047
5013
25
A altura de um nó em uma árvore binária é a distância entre o nó e o seu descendente mais afastado. A altura de uma árvore binária é a altura da raiz da árvore. Se a árvore possui somente o nó raiz, então sua altura é 0 (zero). Dentre as árvores binárias que possuem sete nós, a maior altura de árvore possível é:
8
7
4
5
6
26
Uma lista ligada é uma estrutura que corresponde a uma sequência lógica de entradas ou nós. Cada nó armazena a localização do próximo elemento na sequência, ou seja, de seu nó sucessor. Nessa estrutura,
a existência de um ponteiro apontando para o 1º elemento e outro para o fim da lista permite que a inserção ou deleção de dados de um nó que esteja no meio da lista seja rapidamente executada
enquanto a entrada que determina o topo da lista é mantida em um nó descritor dessa lista, a entrada que marca o fim da lista é mantida fora do descritor
para estabelecer a ligação entre um nó já pertencente a uma lista e um novo nó, basta fazer com que o novo nó referencie no, campo next, o nó que anteriormente era referenciado pelo nó original, desde que esse campo não tenha o valor nulo
o armazenamento de uma lista não requer uma área contígua de memória. Como listas são estruturas dinâmicas, normalmente são definidos procedimentos que permitem criar e remover nós na memória
o armazenamento de uma lista requer uma área contígua de memória para permitir a otimização no processamento de criação e remoção de nós da lista
27
Considere uma tabela de espalhamento (tabelas hash) de comprimento igual a 11, na qual a técnica de resolução de colisões utilizada é a de encadeamento. Nessa tabela, as posições são numeradas (indexadas) com os valores 0, 1, 2, ..., 10, o mapeamento de chaves para posições usa a função hash definida por h(k) = k mod 11, onde k é o valor da chave, e mod é o operador de módulo, e os números 1, 5, 18, 20, 4, 12, 10, 34, 15, 28 e 17 foram as chaves inseridas, nessa ordem, nessa tabela de espalhamento que estava inicialmente vazia. Qual a quantidade de posições em que houve colisão durante as inserções das chaves?
3
0
4
1
2
28
Considere as definições a seguir. I. O nível do nó raiz de uma árvore é 1. II. O nível de qualquer nó subsequente é igual ao nível do seu nó pai mais 1. III. A profundidade de uma árvore é igual ao maior nível encontrado dentre todos os seus nós. Partindo-se das premissas acima, a menor e a maior quantidade de nós, respectivamente, que poderiam existir em uma árvore binária de profundidade 3 são
3 e 15
4 e 7
5 e 16
3 e 7
3 e 16
29
O caminhamento com percurso pós-ordem em uma árvore binária resultou na sequência “A X K D C J B”, em que cada caractere refere-se a um nó visitado. Nesse caso, o nó raiz refere-se ao caractere:
X
D
B
C
30
Considere uma estrutura de dados T como sendo uma árvore binária do tipo AVL. Como característica, essa estrutura de dados é uma árvore binária:
não balanceada, em que, para qualquer nó de T, as alturas de suas duas subárvores (esquerda e direita) são sempre idênticas
não balanceada, em que, para qualquer nó de T, as alturas de suas duas subárvores (esquerda e direita) são sempre idênticas
não balanceada, em que, para qualquer nó de T, as alturas de suas duas subárvores (esquerda e direita) diferem de até uma unidade
balanceada, em que, para qualquer nó de T, as alturas de suas duas subárvores (esquerda e direita) são sempre idênticas
balanceada, em que, para qualquer nó de T, as alturas de suas duas subárvores (esquerda e direita) diferem de até uma unidade
31
Em uma árvore de busca binária, qual é o percurso que apresenta os nós em ordem crescente?
Pré-ordem
Recursivo
In-ordem
Iterativo
Pós-ordem
