Anúncios
1
Um dos exemplos de estrutura de dados é a lista encadeada simples. Com relação a esse tipo de lista, é correto afirmar
Possui a característica de que o último elemento da lista possui um ponteiro para o primeiro elemento da lista
É necessário definir o seu tamanho no momento da sua criação, pois se trata de uma estrutura de dados estática
Quando essa estrutura é utilizada, os elementos da lista sempre estarão armazenados sequencialmente na memória física
Na 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
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.
2
Sobre listas encadeadas, é INCORRETO afirmar que:
os dados são armazenados dinamicamente
possuem tamanho fixo
são acessadas pelo primeiro nó da lista
pilhas e filas podem ser implementadas como listas encadeada
o final da lista faz uma referência para nulo
3
Uma árvore de busca binária cheia tem, no 5º nível, uma quantidade de nós igual a
31
32
64
15
4
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 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
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 são importados de uma biblioteca padrão previamente estabelecida para cada tipo de símbolo
5
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
5013
15047
5021
6
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 é
4
7
8
5
6
7
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
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.
Considerando uma sequência qualquer, deve-se dividir o conjunto ao meio e verificar se o elemento procurado é igual ao elemento central
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
8
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
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
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 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
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
9
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?
2
1
0
3
4
10
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 7
3 e 16
3 e 15
4 e 7
5 e 16
11
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:
B
C
X
D
12
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) 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
não balanceada, em que, para qualquer nó de T, as alturas de suas duas subárvores (esquerda e direita) diferem exatamente de uma unidade
balanceada, em que, para qualquer nó de T, as alturas de suas duas subárvores (esquerda e direita) diferem de até uma unidade
13
Em uma árvore de busca binária, qual é o percurso que apresenta os nós em ordem crescente?
Iterativo
In-ordem
Pós-ordem
Pré-ordem
