Trabalho faltas fontes

Prévia do material em texto

1)Para armazenar os dados a serem utilizados por um sistema, o desenvolvedor pode utilizar uma entre 
várias estruturas de dados existentes, sendo cada qual adequada em determinados contextos. Sobre as 
estruturas de dados, marque a alternativa correta. 
 A 
A estrutura denominada fila circular é utilizada quando deseja-se estabelecer prioridade para os 
elementos que estão a mais tempo na fila. 
 B 
Em uma fila, utiliza-se o termo denominado LIFO (Last In First Out), onde o elemento mais novo 
na estrutura é o primeiro a ser retirado. 
 C 
Dado um conjunto de elementos inseridos em uma pilha, ao se remover sequencialmente esses 
elementos e imprimindo os seus valores obtém-se os elementos na ordem inversa da inicial. 
 D 
Para percorrer os elementos inseridos em uma lista duplamente encadeada, existe apenas um 
fluxo, pois os elementos possuem o ponteiro somente para o próximo elemento da lista. 
 E 
Nas estruturas de dados de lista, pilha e fila, as operações de inserção e remoção possuem 
complexidade de pior caso iguais, visto o comportamento similar adotado por essas estruturas. 
2) Considere uma pilha de latas de sardinhas na prateleira de um supermercado. 
Assinale a estrutura de dados que mais se assemelha ao modo como essas latas são manuseadas. 
 A 
Array. 
 B 
Binary tree. 
 C 
Hashing. 
 D 
Linked list. 
 E 
Stack. 
 
3) Considere a representação de uma lista duplamente encadeada que armazena 
os times de futebol que participam de um torneio. 
 
 
Assinale a ordem em que os times estão dispostos nessa lista. 
 A 
Barcelona, Chelsea, Bayern, Real Madrid, Roma. 
 B 
Chelsea, Bayern, Real Madrid, Roma, Barcelona. 
 C 
Real Madrid, Roma, Barcelona, Chelsea, Bayern. 
 D 
Barcelona, Bayern, Chelsea, Real Madrid, Roma 
 E 
Roma, Real Madrid, Bayern, Chelsea, Barcelona. 
4)Considere as estruturas de dados com as seguintes propriedades 
 
1) Inserção e remoção acontecem apenas na ‘cabeça’ da estrutura 
2) A inserção de um nó no meio da estrutura pode ser realizada com custo computacional 
constante 
3) Respeita a política FIFO: primeiro que entra é o primeiro que sai. 
As descrições acima se referem às estruturas, respectivamente, 
 
 
 
 A 
Fila, Pilha, Lista 
 B 
Lista, Pilha, Fila 
 C 
Pilha, Fila, Lista 
 D 
Pilha, Lista, Fila 
 E 
Lista, Fila, Pilha 
 
5) Considere a árvore AVL abaixo. 
 
 
 
Marque o item que contém o percurso em pré-ordem após a inserção de um nó contendo o 
valor 100. 
 A 
54, 63, 78, 82, 87, 96, 99, 100 
 B 
63, 54, 78, 100, 99, 96, 82, 87 
 C 
63, 78, 54, 87, 82, 96, 99, 100 
 D 
78, 63, 54, 100, 99, 96, 87, 82 
 E 
78, 54, 63, 96, 87, 82, 99, 100 
6) Sobre as árvores binárias, é correto afirmar: 
 A 
Uma árvore binária do tipo cheia é aquela onde todos os nós folhas estão no 
penúltimo e no último nível. 
 B 
Em uma árvore binária, todos os nós devem ter estritamente 0 ou 2 nós filhos, 
como forma de manter a árvore balanceada. 
 C 
Nas árvores binárias, uma árvore pode ter duas raízes simultâneas como forma de 
melhorar o desempenho nas operações realizadas sobre ela. 
 D 
As árvores binárias somente podem ser implementadas através de alocação 
dinâmica, devido à impossibilidade de determinar a quantidade de elementos que a 
árvore terá. 
 E 
Em uma árvore binária de busca, para cada nó da árvore, os valores menores do 
que o nó estão na sub-árvore esquerda e os valores maiores estão na sub-árvore 
direita. 
 
 
 
 
 
 
 
 
7)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: 
 A 
V, F e V. 
 B 
F, V e F. 
 C 
V, F e F. 
 D 
F, F e F. 
 E 
V, V e F. 
8)Considere uma árvore Patricia construída para armazenar as seguintes chaves: A = 
011001; B = 110010; C = 100101; D = 001011; E = 011010; F = 110101. A altura da árvore 
Patricia resultante, considerando-se sua raiz no nível zero, é 
 A 
dois. 
 B 
três. 
 C 
quatro. 
 D 
cinco. 
 E 
seis. 
9) Considere que os números 10, 11, 12, 13, 14 foram inseridos, nessa ordem, em uma 
fila. Esses mesmos números foram inseridos na mesma ordem em uma pilha. Nesse caso, 
 A 
o topo da pilha é o número 10. 
 B 
o primeiro elemento a ser removido da pilha é o número 10. 
 C 
o número 14 é o primeiro elemento a ser removido da fila. 
 D 
o último elemento a ser removido da fila é o número 14. 
10) Analise as seguintes afirmativas sobre estruturas de dados: listas, filas e pilhas. 
I. Em uma lista linear em alocação sequencial, cada nó é formado por campos que 
armazenam características distintas dos elementos da lista. Cada nó da lista pode possuir 
um identificador denominado chave, que deve ser único na lista para evitar 
ambiguidades. II. A fila é um caso particular de listas onde as inserções e as remoções são 
realizadas apenas em uma das extremidades da lista. III. A pilha é um caso particular de 
listas onde as inserções são realizadas em uma extremidade e as remoções na outra 
extremidade da lista. 
É correto afirmar que a(s) afirmativa(s) 
 A 
I é verdadeira. 
 B 
II é verdadeira. 
 C 
III é verdadeira. 
 D 
I e II são verdadeiras. 
 E 
I e III são verdadeiras. 
11) As estruturas de dados pilha e fila são essenciais em muitos aspectos dos sistemas 
computacionais. Sobre estas duas estruturas de dados, analise as seguintes afirmativas. 
I. A pilha é ocasionalmente chamada de FIFO (First-in, First-out – o primeiro a entrar é o 
primeiro a sair). II. A fila é uma lista LIFO (Last-in, First-out – o último a entrar é o primeiro 
a sair). III. O resultado de uma tentativa inválida de remover um elemento de uma fila vazia 
é chamado de underflow. IV. O resultado de uma tentativa inválida de desempilhar ou 
acessar um item de uma pilha vazia é chamado de undeflow. 
Assinale a alternativa CORRETA. 
 A 
Apenas as afirmativas I e II estão corretas. 
 B 
Apenas as afirmativas III e IV estão corretas. 
 C 
Apenas as afirmativas I e III estão corretas. 
 D 
Apenas as afirmativas II e IV estão corretas. 
12) José, técnico em informática do IFTO, construiu uma estrutura de dados do tipo fila e 
executou uma sequência de comandos sobre essa fila. Lembrando que a fila estava 
inicialmente vazia e que o comando Push representa a inserção de um elemento e o Pop 
representa a exclusão de um elemento na fila: 
Push 1, Push 4, Pop 4, Push 2, Push 3, Push 5, Push 6, Pop 3 
Após a execução da sequência desses comandos, escolha entre as alternativas abaixo a 
única que contém o conjunto de elementos resultantes na fila: 
 A 
1-2-3-4-5-6 
 B 
1-2-4-5-6 
 C 
3-4-5-6 
 D 
2-4-5-6 
 E 
1-2-5-6 
13)Considere que em uma tabela de dispersão (ou tabela hash) de comprimento m = 9, 
inicialmente vazia, que usa endereçamento aberto, técnica de tentativa linear para resolver 
colisões e função de dispersão h(k) = k mod m, onde k é a chave a ser inserida, foram 
inseridas as seguintes chaves: 3, 14, 15, 81, 65, 19, 35, 40 e 50 (nesta ordem). A tabela de 
dispersão após estas inserções é 
 A 
3-19-65-40-14-15-50-35-81. 
 B 
81-19-65-3-40-50-14-15-35. 
 C 
81-19-65-3-40-14-15-50-35. 
 D 
19-65-3-40-14-15-50-35-81. 
 E 
19-65-3-40-50-14-15-35-81. 
14) O Quicksort é um dos métodos de ordenação mais eficientes disponíveis e a técnica 
de busca por espalhamento ou hashing é muito utilizada em diversas aplicações. Em 
relação a estes métodos é correto afirmar: 
 A 
O método Quicksort é, essencialmente, uma aplicação do princípio“dividir para 
conquistar”. Para a ordenação, inicialmente o vetor é dividido em uma sublista da 
direita e uma da esquerda, de modo que todo elemento da sublista da esquerda 
seja menor que o da direita. Em seguida, ordenam-se, pelo mesmo processo, as 
duas sublistas de forma recursiva. 
 B 
Para o cálculo da complexidade do Quicksort, leva-se em consideração o número 
de vezes que n (número de elementos do vetor) pode ser dividido por 10 que é 
O(log10n), e em cada partição são feitas O(n) comparações. 
 C 
No Quicksort, o pivô é responsável pelo número de partições em que o vetor é 
dividido. Como o pivô não pode ser um elemento que esteja repetido no vetor, 
o Quicksort não funciona quando há elementos repetidos. 
 D 
Espalhamento ou hashing é o processo de transformação de uma chave em um 
endereço. O tempo gasto com buscas em uma tabela de espalhamento depende 
do tamanho da tabela, e aí reside sua grande vantagem: devem sempre ser 
usadas tabelas pequenas. 
 E 
O índice gerado pela função hash é chamado endereço efetivo e o endereço 
verdadeiro do registro é chamado endereço primário. Quando duas ou mais 
chaves possuem o mesmo endereço efetivo, dizemos que houve dispersão, e 
essas chaves são chamadas de homônimas. 
 
15) Funções hash são utilizadas por diversos protocolos de rede e possuem 
diversas aplicações, entre as quais a verificação de corretude de uma mensagem 
enviada. Sobre funções hash no contexto de redes, assinale a alternativa correta. 
 A 
Uma função hash requer mensagens de tamanho fixo. 
 B 
Não é necessário recalcular o valor hash de uma dada mensagem para autenticá-
la. 
 C 
É desejável ser computacionalmente viável inverter uma função hash, ou seja, 
dado um hash h, encontrar uma mensagem m tal que, aplicada na função 
de hash H, H(m) = h. 
 D 
Funções hash não são injetoras. 
 E 
Uma dada função de hash pode gerar valores de hash de diferentes tamanhos. 
 
15) Algoritmos de hash são bastante utilizados como elementos de garantia da segurança 
da informação. A propriedade da informação garantida pela utilização desses algoritmos é 
a: 
 A 
confidencialidade; 
 B 
disponibilidade; 
 C 
integridade; 
 D 
irretratabilidade; 
 E 
autenticidade. 
16) Considere uma tabela hash com as seguintes características: 
1. As chaves são as letras A,B,C,D,H.J,K,M,N,O,P,R,S,T,U; 
2. A tabela possui 11 posições, referenciadas pelos índices de 0 até 10; 
3. A função de hash é definida como hash(x)=posição(x) mod 11 onde x é a chave, e 
posição(x) é a posição da chave no alfabeto ABCDEFGHIJKLMNOPQRSTUVWXYZ, tal 
que posição(“A”) retorna 1 e posição(“Z”) retorna 26. 
Analise as afirmativas sobre a tabela após seu preenchimento com as chaves listadas 
acima. 
I. Nenhuma chave foi alocada à posição 6; 
II. A chave “K” foi alocada à posição zero; 
III. As chaves “B” e “N” colidiram na posição 3; 
IV.Apenas uma letra foi alocada à posição 9. 
Está correto somente o que se afirma em: 
 A 
I e II; 
 B 
I e IV; 
 C 
I, II e IV; 
 D 
II e III; 
 E 
II, III e IV. 
17) Numa tabela hash adequadamente dimensionada, com N chaves, o número médio de 
acessos para localização de uma chave situa-se entre: 
 A 
1 e 2 
 B 
N ÷ 2 e N 
 C 
lg(N) e N 
 D 
1 e N ÷ 2 
 E 
lg(N) e lg(N2 ) 
 
18) Um dos exemplos de estrutura de dados é a lista encadeada simples. Com relação a 
esse tipo de lista, é correto afirmar: 
 A 
Possui a característica de que o último elemento da lista possui um ponteiro para o 
primeiro elemento da lista. 
 B 
É necessário definir o seu tamanho no momento da sua criação, pois se trata de 
uma estrutura de dados estática. 
 C 
Quando essa estrutura é utilizada, os elementos da lista sempre estarão 
armazenados sequencialmente na memória física. 
 D 
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. 
 E 
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. 
19) Abaixo tem-se uma tabela que ilustra o conjunto de nós de uma lista duplamente 
encadeada, contendo o total de 5 nós. 
 
 
 
Ao imprimir a estrutura na ordem correta, o conteúdo apresentado será I – F – S – P – 2019, 
dessa forma, assinale a alternativa que contém os dados que preenchem, corretamente, a 
coluna “conteúdo”, de cima para baixo. 
 A 
P – I – S – 2019 – F 
 B 
2019 – P – S – F – I 
 C 
S – P – I – F – 2019 
 D 
S – I – F – 2019 – P 
20) __________ é um tipo específico de __________ em que os elementos só podem ser 
inseridos e retirados de uma das extremidades. Utilizamos uma __________ para 
armazenar dados segundo uma determinada chave de ordenação, que são submetidos 
com frequência à ___________ de elementos. 
Assinale a alternativa que preenche correta e respectivamente as lacunas do parágrafo 
acima. 
 A 
Lista – fila – árvore AVL – remoção 
 B 
Árvore AVL – árvore rubro-negra – lista – ordenação 
 C 
Lista linear – fila – árvore binária – alteração 
 D 
Árvore binária – árvore AVL – pilha – inserção 
 E 
Pilha – lista – árvore binária – pesquisa 
21) Na coluna I estão dispostos alguns conceitos relacionados à estrutura de dados. 
Estabeleça a correta correspondência com suas definições, conforme apresentado na 
coluna II. 
Coluna I 
1 Fila 
2 Pilha 
3 Lista Encadeada 
4 Árvore 
5 Vetor 
 
Coluna II 
( ) coleção de itens de dados. 
( ) primeiro a entrar é o primeiro a sair. 
( ) bidimensional. 
( ) último a entrar é o primeiro a sair. 
( ) estrutura de dados estática. 
A sequência correta, de cima para baixo, é: 
 A 
5, 1, 3, 2 e 4. 
 B 
1, 2, 5, 3 e 4. 
 C 
4, 1, 3, 2 e 5. 
 D 
2, 3, 4, 1 e 5. 
 E 
3, 1, 4, 2 e 5. 
22) Assinale a alternativa que indica corretamente o que ocorre quando um 
programador atribui um valor para uma posição além do tamanho do vetor. Por 
exemplo, suponha que um vetor VET foi definido com 10 posições e o programador 
tentou fazer a operação VET[15]=1. 
 A 
O compilador irá reportar um erro e o executável não será criado. 
 B 
O programa pode ser compilado, mas apresenta sempre um erro de execução 
imediatamente. 
 C 
O programa pode ser compilado, mas o compilador previne o problema e elimina a 
operação incorreta. 
 D 
O programa pode ser compilado e a atribuição do valor é realizada na última 
posição válida do vetor. 
 E 
O programa é compilado, mas quando executado pode apresentar resultados 
imprevistos ou abortar a execução. 
 
23) Considere o problema de ordenar em ordem crescente o array formado pelos números 
[67, 23, 11, 18, 87, 44] utilizando o Método da Seleção Direta. Assinale a alternativa que 
mostra o posicionamento dos números no array após ter sido realizada a primeira troca. 
 A 
[11, 23, 67, 18, 87, 44] 
 B 
[23, 67, 11, 18, 87, 44] 
 C 
[67, 11, 23, 18, 87, 44] 
 D 
[44, 23, 11, 18, 87, 67] 
 E 
[67, 23, 87, 18, 11, 44] 
24) Sabendo-se que a função retorna o número de elementos de um array e que L assume 
o tipo de um array de inteiros, indexados a partir de zero, analise o pseudocódigo a seguir. 
 
Esse algoritmo deveria ordenar os elementos do array em ordem crescente, mas há 
problemas no código que produzem resultados errôneos. 
Assinale a opção que indica o que é de fato printado ao final da execução do código 
mostrado. 
 A 
{10, 2, 40, 53, 28, 12} 
 B 
{2, 10, 12, 28, 40, 53} 
 C 
{53, 40, 28, 12, 10, 2} 
 D 
{2, 2, 12, 12, 12, 12} 
 E 
{2, 10, 10, 10, 10, 12} 
25) Considere o seguinte algoritmo 
Inteiro array[10] = {0,1,2,3,4,5,6,7,8,9} 
var i = 0 
Enquanto i < 10 Faça 
Inteiro temp = array[i] 
array[i] = array[9-i] 
array[9-i] = temp 
i = i + 1 
Fim enquanto 
 
Qual será o conteúdo do vetor ‘array’ após a execução do programa? 
 A 
9, 8, 7, 6,5, 4, 3, 2, 1, 0 
 B 
0, 1, 2, 3, 4, 9, 8, 7, 6, 5 
 C 
9, 8, 7, 6, 5, 0, 1, 2, 3, 4 
 D 
0, 1, 2, 3, 4, 5, 6, 7, 8, 9 
 E 
1, 0, 3, 2, 5, 4, 7, 6, 9, 8 
26) O algoritmo a seguir, descrito em pseudocódigo, pode ser utilizado para ordenar um 
vetor V[1..n] em ordem crescente. 
 
 
 
Este algoritmo é conhecido como: 
 A 
Insertion sort 
 B 
Selection sort 
 C 
Merge sort 
 D 
Quick sort 
 E 
Bubble sort 
27) Considere o problema de pesquisar por um número em um array ordenado contendo 
dez números. Se for utilizado o método da pesquisa binária, qual é o menor número de 
comparações que permite concluir que um número não está presente no array? 
 A 
4 
 B 
5 
 C 
2 
 D 
3 
 E 
6 
28) Observe abaixo a estrutura de dados, em forma de tabela. 
 
 
 
Nesta tabela, foram realizadas uma série de operações de inserção e retirada de 
elementos, conforme descrito e ilustrado abaixo. 
 
 
Pode-se deduzir, pelas operações realizadas, que tal estrutura é uma 
 A 
lista indexada. 
 B 
árvore. 
 C 
fila. 
 D 
fila duplamente encadeada. 
 E 
pilha.