Atividades - Estruturas de Dados

Prévia do material em texto

AI Estruturas de dados lineares
PERGUNTA 1
Considere o texto a seguir e assinale a alternativa que preencha as lacunas CORRETA e RESPECTIVAMENTE.
“O computador armazena os __________ que serão manipulados pelos __________ em uma memória principal. Veja que um __________ de computador é a implementação de um __________, em uma __________ específica. Desse modo, é possível para o programador instruir o __________ sobre como ele deve processar os __________ que serão recebidos; além disso, o computador deve ser capaz de armazenar os dados, temporariamente, durante todo o processamento.”
	
	a.
	dados; programas; algoritmo; programa; linguagem de programação; computador; dados.
	
	b.
	dados; programas; programa; algoritmo; linguagem de programação; computador; dados.
	
	c.
	programas; dados; algoritmo; programa; linguagem de programação; computador; dados.
	
	d.
	dados; dados; programa; algoritmo; linguagem de programação; computador; programas.
	
	e.
	programas; dados; programa; computador; linguagem de programação; algoritmo; dados.
PERGUNTA 2
Considere uma fila estática de tamanho igual a dez, parcialmente preenchida com os valores 1, 2, 3 e 4. Os valores armazenados nas variáveis head e tail são, respectivamente, zero e quatro. Suponha que as seguintes operações foram realizadas em ordem:
I - Enqueue(10);
II - Enqueue(11);
III - Enqueue(Dequeue());
IV - Dequeue();
V - Enqueue(Dequeue()).
Assim, o estado da fila estática após a execução das operações anteriores é:
	
	a.
	[4, 10, 11, 1, 3]
	
	b.
	[2, 3,  10, 11, 1]
	
	c.
	[1, 2, 10, 11, 3]
	
	d.
	[3, 10, 11, 1, 2]
	
	e.
	[10, 11, 1, 2, 3]
PERGUNTA 3
A pilha é uma estrutura de dados na qual as operações são realizadas em um único ponto. Além disso, a pilha considera uma regra de acesso específica. Nesse contexto, assinale a alternativa que apresenta CORRETAMENTE a sigla referente à regra de acesso de uma pilha.
	
	a.
	LIFI.
	
	b.
	FILO.
	
	c.
	FIFO.
	
	d.
	LIFA.
	
	e.
	LIFO.
PERGUNTA 4
Considerando o conceito pertinente a uma fila estática, analise as afirmações a seguir.
I - Uma fila, considerada sobre um vetor, apresenta dois pontos de acesso.
II - Um ponto de acesso é a cabeça da fila, denominado tail, e é a partir desse ponto que os elementos são retirados da fila.
III - Outro ponto de acesso é o final da fila, denominado head, onde os elementos entram na fila.
IV - Cada um dos pontos de acesso referencia uma posição na fila (ou, nesse caso, um vetor) utilizando os indexadores.
É CORRETO o que se afirma APENAS em:
	
	a.
	I e IV.
	
	b.
	II, III e IV.
	
	c.
	I, III e IV.
	
	d.
	I, II e IV.
	
	e.
	I, II e III.
PERGUNTA 1
Considere o seguinte algoritmo em pseudocódigo e assinale a alternativa CORRETA.
FunçãoA(V)
1 - se !IsEmpty()
2 -    x←V[head]
3 -    head←head+1
4 -    retorna x
5 - senão
6 - erro underflow
	
	a.
	Remove um elemento na fila V.
	
	b.
	Insere um elemento na fila V.
	
	c.
	Atualiza um elemento na pilha V.
	
	d.
	Remove um elemento na pilha V.
	
	e.
	Insere um elemento na pilha V.
PERGUNTA 4
Considere o seguinte algoritmo em pseudocódigo e assinale a alternativa CORRETA.
ProcedimentoB(x,V)
1 - se !IsFull(V)
2 -    V[topo]←x
3 -    topo←topo+1
4 - senão
5 - erro overflow
	
	a.
	Remove um elemento na pilha V.
	
	b.
	Remove um elemento na fila V.
	
	c.
	Atualiza um elemento na pilha V.
	
	d.
	Insere um elemento na pilha V.
	
	e.
	Insere um elemento na fila V.
AS II 
PERGUNTA 1
Considere o seguinte algoritmo e assinale a alternativa CORRETA.
Sort(V)
1 - para j←1 até |V|-1
2 -     chave←V[j]
3 -      i←j-1
4 -     enquanto i≥0 e V[i]>chave
5 -        V[i+1]←V[i]
6 -         i←i-1
7 -      V[i+1]←chave
	
	a.
	Refere-se ao algoritmo Insertion Sort.
	
	b.
	Refere-se ao algoritmo Quick Sort.
	
	c.
	Refere-se ao algoritmo Merge Sort.
	
	d.
	Refere-se ao algoritmo Bubble Sort.
	
	e.
	Refere-se ao algoritmo Selection Sort.
PERGUNTA 2
O algoritmo de ordenação clássico que seleciona um valor, o qual divide o vetor em dois vetores parciais, um ordenado à esquerda e outro desordenado à direita, e compara o valor selecionado com os valores à esquerda até que encontre a posição correta, é denominado algoritmo
	
	a.
	Selection Sort.
	
	b.
	Quick Sort.
	
	c.
	Bubble Sort.
	
	d.
	Merge Sort.
	
	e.
	Insertion Sort.
PERGUNTA 3
O algoritmo de ordenação que armazena a posição do menor elemento de um vetor, atualiza essa posição à medida que o vetor é percorrido e realiza a troca de posições caso seja necessário é denominado algoritmo
	
	a.
	Bubble Sort.
	
	b.
	Insertion Sort.
	
	c.
	Selection Sort.
	
	d.
	Merge Sort.
	
	e.
	Quick Sort.
PERGUNTA 4
Considere o seguinte texto e assinale a alternativa que preenche CORRETA e RESPECTIVAMENTE as lacunas existentes.
“[...] é possível verificar que podemos ter __________ que realizam a mesma __________, como é o caso dos __________, mas fazem isso de maneiras diferentes. Essas diferenças entre __________, consideradas pelos algoritmos, impactam no tempo que será necessário para __________.”
	
	a.
	algoritmos; tarefa; algoritmos de ordenação; as estratégias; a execução da tarefa.
	
	b.
	as estratégias; tarefa; algoritmos de ordenação; algoritmos; a execução da tarefa.
	
	c.
	algoritmos; tarefa; algoritmos de execução; as estratégias; a execução da tarefa.
	
	d.
	as estratégias; execução da tarefa; algoritmos de ordenação; algoritmos; a tarefa.
	
	e.
	as execuções da tarefa; tarefa; algoritmos de ordenação; as estratégias; os algoritmos.
AS III
PERGUNTA 1
Considere o vetor V=[9,4,3,5,1,2] e o procedimento Partition() descrito a seguir. Após a execução do procedimento, assinale a alternativa que apresenta CORRETAMENTE o valor retornado pelo procedimento.
Partition(V,p,r)
1 - x←V[r]
2 - i←p-1
3 - para j←p até r-1
4 -    se V[j]≤x
5 -       i←i+1
6 -       trocar V[i] e V[j]
7 -       trocar V[i+1] e V[r]
8 - retornar i+1
	
	a.
	4.
	
	b.
	2.
	
	c.
	0.
	
	d.
	3.
	
	e.
	1.
PERGUNTA 2
Considere o algoritmo em pseudocódigo a seguir e assinale a alternativa CORRETA a respeito de sua descrição.
Quicksort(V,p,r)
1 - se p<q
2 -   q←Partition(V,p,r)
3 -   Quicksort(V,p,q-1)
4 -   Quicksort(V,q+1,r)
	
	a.
	O algoritmo identifica a posição no vetor que será utilizada para desmembrá-lo em dois subvetores.
	
	b.
	A chave para essa divisão está descrita pelo procedimento Quicksort().
	
	c.
	O algoritmo verifica se o vetor não é vazio; veja que se os indexadores p e r forem iguais, isso indica que não existe elemento no vetor e, dessa forma, ele já se encontra ordenado.
	
	d.
	Após a divisão, cada subvetor obtido será submetido, recursivamente, ao procedimento Partition().
	
	e.
	O algoritmo recebe como parâmetros de entrada o vetor V, que será ordenado; o inteiro p, que é o valor da primeira posição do vetor; e o inteiro r, que indica o valor da última posição do vetor.
PERGUNTA 3
Considere o vetor V=[9,4,3,5,1,2] e o procedimento Partition() descrito a seguir. Após a execução do procedimento, assinale a alternativa que descreve CORRETAMENTE o novo estado do vetor.
Partition(V,p,r)
1 - x←V[r]
2 - i←p-1
3 - para j←p até r-1
4 -    se V[j]≤x
5 -      i←i+1
6 -      trocar V[i] e V[j]
7 -  trocar V[i+1] e V[r]
8 - retornar i+1
	
	a.
	[9, 2, 3, 4, 1, 5].
	
	b.
	[9, 1, 2, 4, 3, 5].
	
	c.
	[1, 4, 3, 5, 9, 2].
	
	d.
	[1, 2, 3, 4, 5, 9].
	
	e.
	[1, 2, 3, 5, 9, 4].
PERGUNTA 4
Considere as seguintes afirmações.
I - A ideia fundamental por trás de um algoritmo recursivo é a transformação do problema (instância) original em outro menor ou mais simples, de modo que seu tamanho ou sua simplicidade permita uma nova chamada recursiva.
II - A condição de parada de um algoritmo recursivo é denominada de caso base.
III - Todo algoritmo recursivo terá uma versão baseada na abordagem da divisão e conquista para executar a mesma tarefa.
IV - Os algoritmos recursivos são mais simples de compreender e apresentam um número menor de instruções.
É CORRETO o que se afirma APENAS em:
	
	a.
	II e IV.
	
	b.
	I e IV.
	
	c.
	I e III.d.
	I e II.
	
	e.
	II e III.
PERGUNTA 1
1. Considere o texto a seguir e assinale a alternativa que preenche CORRETA e RESPECTIVAMENTE as lacunas.
“As desvantagens de se utilizar __________ estão ligadas ao __________. É muito comum que __________ acabem por consumir muita memória, por conta do __________ de cada chamada realizada. Além disso, os algoritmos recursivos são mais difíceis de serem depurados.”
	
	a.
	empilhamento; consumo de recursos; instâncias muito grandes; algoritmo recursivo.
	
	b.
	empilhamento; algoritmo recursivo; instâncias muito grandes; consumo de recursos.
	
	c.
	consumo de recursos; algoritmo recursivo; instâncias muito grandes; empilhamento.
	
	d.
	consumo de recursos; empilhamento; instâncias muito grandes; algoritmo recursivo.
	
	e.
	um algoritmo recursivo; consumo de recursos; instâncias muito grandes; empilhamento.
PERGUNTA 3
Considere o texto a seguir e assinale a alternativa que preenche CORRETA e RESPECTIVAMENTE as lacunas.
“O algoritmo de ordenação __________, mais conhecido como __________, também considera a abordagem __________, assim como o seu correlato __________. O princípio fundamental do Merge Sort está relacionado com __________ ordenados em __________.”
	
	a.
	Quick Sort; Merge Sort; da divisão e conquista; por mistura ou intercalação; da combinação de dois subvetores; um único vetor ordenado.
	
	b.
	da divisão e conquista; Quick Sort; por mistura ou intercalação; Merge Sort; da combinação de dois subvetores; um único vetor ordenado.
	
	c.
	por mistura ou intercalação; Merge Sort; da divisão e conquista; Quick Sort; a combinação de dois subvetores; um único vetor ordenado.
	
	d.
	da divisão e conquista; Merge Sort; por mistura ou intercalação; Quick Sort; da combinação de dois subvetores; um único vetor ordenado.
	
	e.
	Quick Sort; Merge Sort; por mistura ou intercalação; da divisão e conquista; da combinação de dois subvetores; um único vetor ordenado.
PERGUNTA 4
Considere o seguinte vetor V=[1,2,3,4,5,6,7,8,9,10] e o algoritmo BuscaBinaria() descrito em seguida. Suponha que o valor a ser pesquisado é x=2. Nesse contexto, assinale a alternativa que descreve CORRETAMENTE a sequência das chamadas realizadas até a identificação de x.
	
	a.
	BuscaBinaria(2,V,0,9), BuscaBinaria(2,V,0,3).
	
	b.
	BuscaBinaria(2,V,0,9), BuscaBinaria(2,V,0,5).
	
	c.
	BuscaBinaria(2,V,0,9), BuscaBinaria(2,V,5,7).
	
	d.
	BuscaBinaria(2,V,0,9), BuscaBinaria(2,V,5,9).
	
	e.
	BuscaBinaria(2,V,0,9), BuscaBinaria(2,V,3,7).
AS IV
PERGUNTA 1
Analise o algoritmo descrito a seguir e assinale a alternativa que descreve CORRETAMENTE sua operação.
Algoritmo5(P)
1 - se !IsEmpty()
2 -   x←P.ponteiro.valor
3 -   P.ponteiro←P.ponteiro.ponteiro
4 -   retorna x
5 - senão
6 -   erro underflow
	
	a.
	O algoritmo 5 descreve a operação Enqueue.
	
	b.
	O algoritmo 5 descreve a operação Pop.
	
	c.
	O algoritmo 5 descreve a operação Insertion.
	
	d.
	O algoritmo 5 descreve a operação Dequeue.
	
	e.
	O algoritmo 5 descreve a operação Push.
PERGUNTA 2
Analise o algoritmo descrito a seguir e assinale a alternativa que descreve CORRETAMENTE sua operação.
Algoritmo4(F)
1 -   se !IsEmpty(F)
2 -   x←F.head.valor
3 -   F.head←F.head.ponteiro
4 -   se F.head=Null
5 -       F.tail←Null
6 -    retornar x
7 - senão
8 -     erro underflow
	
	a.
	O algoritmo 4 descreve a operação Enqueue.
	
	b.
	O algoritmo 4 descreve a operação Pop.
	
	c.
	O algoritmo 4 descreve a operação Dequeue.
	
	d.
	O algoritmo 4 descreve a operação Insertion.
	
	e.
	O algoritmo 4 descreve a operação Push.
PERGUNTA 3
Questão anulada, selecione uma das opções para receber a pontuação referente a esta pergunta.
Assinale a alternativa que preenche CORRETA e RESPECTIVAMENTE as lacunas no texto a seguir.
“Uma ________ armazena elementos de acordo com uma _______ específica. A __________define a regra de acesso para uma fila como o primeiro elemento que entra será o primeiro a sair da fila. Como em outras estruturas de dados, a fila suporta __________ para a __________ de seus elementos.”
	
	a.
	fila; regra de acesso; manipulação; algumas operações; sigla FIFO (First In First Out).
	
	b.
	manipulação; fila; sigla FIFO (First In First Out); algumas operações; regra de acesso.
	
	c.
	fila; regra de acesso; sigla FIFO (First In First Out); algumas operações; manipulação.
	
	d.
	manipulação; regra de acesso; sigla FIFO (First In First Out); algumas operações; fila.
	
	e.
	fila; operação; sigla FIFO (First In First Out); regra de acesso; manipulação.
PERGUNTA 4
As listas ligadas pertencem à categoria dos conjuntos dinâmicos, os quais são manipulados por algoritmos e podem aumentar ou diminuir de tamanho e sofrer mudanças em relação aos elementos que o compõem. Nesse contexto, analise as seguintes afirmações.
I - Nesse sentido, os conjuntos estáticos suportam operações que são categorizadas como operações de consulta ou modificadoras.
II - As operações de consulta são aquelas que retornam informações a respeito do conjunto, tais como: (i) busca, por um determinado elemento, identificar o (ii) menor ou (iii) maior valor no conjunto e retornar o (iv) sucessor ou o (v) predecessor de um determinado elemento.
III - As operações modificadoras são aquelas que alteram a composição do conjunto. Essas operações se referem a (i) inserção ou (ii) remoção de um determinado elemento do conjunto.
É CORRETO o que se afirma APENAS em:
	
	a.
	I.
	
	b.
	II.
	
	c.
	I e II.
	
	d.
	II e III.
	
	e.
	III.
PERGUNTA 2
Analise o algoritmo descrito a seguir e assinale a alternativa que descreve CORRETAMENTE sua operação.
Algoritmo3(q)
1 - se q.anterior=Null
2 -    L←q.posterior
3 -    q.posterior.anterior←Null
4 - senão
5 -    p←q.anterior
6 -    p.posterior←q.posterior
7 -    se q.posterior≠Null
8 -         q.posterior.anterior←p
	
	a.
	O algoritmo 3 remove um elemento em uma lista ligada.
	
	b.
	O algoritmo 3 remove um elemento em uma lista duplamente ligada.
	
	c.
	O algoritmo 3 insere um elemento em uma lista ligada.
	
	d.
	O algoritmo 3 move um elemento em uma lista ligada.
	
	e.
	O algoritmo 3 insere um elemento em uma lista duplamente ligada.
PERGUNTA 3
Considere a algoritmo BuscaLigada(), descrito a seguir e com base no algoritmo assinale a alternativa CORRETA.
BuscaLigada(L,k)
1 - x←L
2 - enquanto x≠Null e x.valor≠k faça
3 -     x←x.ponteiro
4 - retornar x
	
	a.
	A variável x recebe, na linha 1, o valor do primeiro elemento da lista.
	
	b.
	O algoritmo retorna, na linha 4, o valor do elemento identificado.
	
	c.
	O laço, na linha 2, compara o valor procurado com os valores na lista.
	
	d.
	A variável x recebe, na linha 3, o seu próprio endereço de memória.
	
	e.
	A expressão relacional x≠Null é equivalente a x≠0.
PERGUNTA 4
Analise o algoritmo descrito a seguir e assinale a alternativa que descreve CORRETAMENTE sua operação.
Algoritmo2(L,k)
1 - nova←endereço de uma nova célula
2 - nova.valor←k
3 - nova.posterior←L
4 - nova.anterior←Null
5 - se L≠Null
6 -     L.anterior←nova
7 - L←nova
	
	a.
	O algoritmo 2 move um elemento em uma lista ligada.
	
	b.
	O algoritmo 2 insere um elemento em uma lista ligada.
	
	c.
	O algoritmo 2 remove um elemento em uma lista ligada.
	
	d.
	O algoritmo 2 insere um elemento em uma lista duplamente ligada.
	
	e.
	O algoritmo 2 remove um elemento em uma lista duplamente ligada.
AS V
PERGUNTA 1
Sobre o desempenho de algoritmos de ordenação, avalie as afirmações abaixo e selecione a alternativa correta dentre as disponíveis.
I - O algoritmo Bucket Sort tem melhor desempenho que o algoritmo Bubble Sort.
II - O algoritmo Insertion Sort tem melhor desempenho que o algoritmo Counting Sort.
III - O algoritmo Counting Sort tem melhor desempenho que o algoritmo Insertion Sort.
IV - O algoritmo Bubble Sort tem melhor desempenho que o algoritmo Counting Sort.
	
	a.
	É correto o que se afirma em I e II, apenas.
	
	b.
	É correto o que se afirma em II e IV, apenas.
	
	c.
	É correto o que se afirma em I e III, apenas.
	
	d.
	É correto o que se afirmaem II e III, apenas.
	
	e.
	É correto o que se afirma em I e IV, apenas.
PERGUNTA 2
O algoritmo de ordenação por contagem, ou Counting Sort, executa um número de instruções proporcional a n. A premissa para esse algoritmo é que a entrada seja um arranjo de inteiros maiores ou iguais a 0 e menores ou iguais a k. Nesse sentido, é preciso que se conheça previamente o maior valor no arranjo. Nesse contexto, considere o seguinte arranjo de entrada A
A=[1,3,8,7,6,3,2,1,6,3], 
considerando que o algoritmo Counting Sort utiliza um arranjo auxiliar C que, inicialmente, armazenará a frequência dos valores de A, o estado inicial de C para esse exemplo é:
	
	a.
	C=[0,1,2,3,4,0,4,2,1]
	
	b.
	C=[1,2,3,3,0,0,2,1,1]
	
	c.
	C=[1,2,2,3,1,1,2,1,1]
	
	d.
	C=[0,3,2,2 1,1,2,1,1]
	
	e.
	C=[0,2,1,3,0,0,2,1,1]
PERGUNTA 3
Considere o seguinte trecho de algoritmo, representado em pseudocódigo:
1 - para i←1 até n faça
2 -     para j←1 até n faça
3 -        V[i][j]←i+j.
Nesse contexto, avalie as afirmações a seguir e selecione a alternativa correta dentre as disponíveis.
I - O número de instruções executadas pelo trecho de algoritmo é exatamente 2n2+2n+1.
II - Quando o tamanho da instância de entrada dobra, o número de instruções executadas é multiplicado por dois.
III - Sob a ótica da análise da eficiência assintótica, o tempo de execução do trecho de algoritmo é proporcional a T(n)=n2.
IV - Pode-se classificar o tempo de execução do trecho de algoritmo como linear no tamanho da entrada.
	
	a.
	É correto o que se afirma em I e II, apenas.
	
	b.
	É correto o que se afirma em II e III, apenas.
	
	c.
	É correto o que se afirma em I e III, apenas.
	
	d.
	É correto o que se afirma em II e IV, apenas.
	
	e.
	É correto o que se afirma em I e IV, apenas.
PERGUNTA 4
Considere o seguinte arranjo:
A=[0.12;0.23;0.85;0.47;0.21;0.33;0.60;0.41;0.15;0.10].
Considere, ainda, que o arranjo anterior será submetido, como instância de entrada, ao algoritmo Bucket Sort. Nesse contexto, avalie as afirmações a seguir e selecione a alternativa correta dentre as disponíveis.
I - A lista em B[4] tem dois elementos.
II - A lista em B[5] é vazia.
III - A lista em B[6] tem dois elementos.
IV - A lista em B[7] tem um elemento.
	
	a.
	É correto o que se afirma em I e III, apenas.
	
	b.
	É correto o que se afirma em II e IV, apenas. 
	
	c.
	É correto o que se afirma em II e III, apenas.
	
	d.
	É correto o que se afirma em I e II, apenas.
	
	e.
	É correto o que se afirma em I e IV, apenas.
PERGUNTA 3
Considere o seguinte arranjo:
A=[0.12;0.23;0.85;0.47;0.21;0.33;0.60;0.41;0.15;0.10].
Considere, ainda, que o arranjo anterior será submetido, como instância de entrada, ao algoritmo Bucket Sort. Nesse contexto, avalie as afirmações a seguir e selecione a alternativa correta dentre as disponíveis.
I - A lista em B[0] é vazia.
II - A lista em B[1] tem dois elementos.
III - A lista em B[2] tem três elementos.
IV - A lista em B[3] tem um elemento.
	
	a.
	É correto o que se afirma em I e III, apenas.
	
	b.
	É correto o que se afirma em I e IV, apenas.
	
	c.
	É correto o que se afirma em II e III, apenas.
	
	d.
	É correto o que se afirma em II e IV, apenas.
	
	e.
	É correto o que se afirma em I e II, apenas.
PERGUNTA 4
1. Sobre o algoritmo Bucket Sort, avalie as afirmações abaixo e selecione a alternativa correta dentre as disponíveis.
I - O Bucket Sort considera que a instância de entrada tem valores no intervalo [0,1].
II - O Bucket Sort considera que a instância de entrada tem valores distribuídos uniformemente.
III - Se A é o arranjo de entrada do algoritmo Bucket Sort então B é o número de buckets.
IV - O arranjo de saída B contém |A| buckets representados como listas inicialmente vazias.
	
	a.
	É correto o que se afirma em I e IV, apenas.
	
	b.
	É correto o que se afirma em II e III, apenas.
	
	c.
	É correto o que se afirma em II e IV, apenas.
	
	d.
	É correto o que se afirma em I e II, apenas.
	
	e.
	É correto o que se afirma em I e III, apenas.