1
Uma estrutura de dados que possui dois campos: um ponteiro e campo de informação denomina-se:
lista encadeada simples
lista encadeada dupla
vetor
pilha
árvore binária
2
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 B
árvore AVL
árvore binária
lista encadeada
tabela hash
3
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?
2, 252, 401, 398, 330, 344, 397, 363
925, 202, 911, 240, 912, 245, 363
935, 278, 347, 621, 299, 392, 358, 363
2, 399, 387, 219, 266, 382, 381, 278, 363
994, 220, 911, 244, 798, 258, 362, 363
4
A busca binária é conhecida também como busca logarítmica. Sobre a busca binária, assinale a alternativa INCORRETA
Quando comparada com a busca sequencial, a busca binária, há uma redução logarítmica dos elementos a serem pesquisados
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
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
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
5
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 elementossão dispostos de acordo com uma hierarquia e existe um nó principal conhecido como raiz. As afirmativas I, II e III são, respectivamente:
F, V e F
F, F e F
V, F e V
V, F e F
V, V e F
6
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.
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
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
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
Listas, que podem ser classificadas como estrutura estática, consistem em uma coleção de elementos que aparecem em ordem combinatória
7
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 – 9 – 8 – 14 – 18 – 15 – 12 – 25 – 31 – 30 – 20
20 – 30 – 31 – 25 – 12 – 15 – 18 – 14 – 8 – 9 – 6
6 – 8 – 9 – 12 – 14 – 15 – 18 – 20 – 25 – 30 – 31
6 – 8 – 9 – 14 – 15 – 18 – 12 – 25 – 30 – 31 – 20
20 – 12 – 8 – 6 – 9 – 15 – 14 – 18 – 30 – 25 – 31
8
Sobre as estruturas de dados conhecidas como árvores, selecione a alternativa CORRETA.
As operações básicas sobre árvores são extrair-raiz e alterar-folha
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 é composta por duas raízes, sendo uma principal e a outra secundária
Uma árvore binária é aquela que tem como conteúdo somente valores binários
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
9
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
é completa
tem 3 níveis para armazenar os 7 nomes
possui como folhas os nomes Rui e Maria
requer no máximo 3 comparações para localizar qualquer um dos 7 nomes
10
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 é:
10, 7, 5, 8, 12, 11 e 13
5, 10, 12, 8, 7, 11 e 13
5, 7, 8, 10, 11, 12 e 13
10, 8, 5, 7, 12, 11 e 13
5, 8, 7, 11, 13, 12 e 10
11
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
concatenação
empilhamento
poda
desempilhamento
12
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 T3
T2 e T3
T1, T2 e T3
T1
T1 e T2
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 pré-ordem é:
10, 8, 5, 7, 12, 11 e 13
5, 10, 12, 8, 7, 11 e 13
10, 7, 5, 8, 12, 11 e 13
5, 8, 7, 11, 13, 12 e 10
5, 7, 8, 10, 11, 12 e 13
14
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:
de busca binária
hiberbólica
binária
AVL
ordenada
15
Pesquisar um valor que corresponda a um valor chave em uma árvore AVL com 128 elementos requer no máximo
seis comparações
quatro comparações
oito comparações
cinco comparações
sete comparações
