Estrutura de dados AS

Prévia do material em texto

Se eu te ajudei por favor clique no 👍!
Considere uma fila estática, implementada sobre um vetor de inteiros com tamanho igual a
sete. Suponha que as variáveis head e tail armazenam, respectivamente, os valores cinco e
sete. Nesse contexto, a operação Enqueue(3) resultaria
a. no armazenamento do valor 3 na posição 5.
b. em um erro de underflow.
c. em um erro de overflow.
d. no armazenamento do valor 5 na posição 7.
e. no armazenamento do valor 3 na posição 7.
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. Insere um elemento na pilha V.
b. Insere um elemento na fila V.
c. Remove um elemento na fila V.
d. Remove um elemento na pilha V.
e. Atualiza um elemento na pilha V.
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. programas; dados; algoritmo; programa; linguagem de programação; computador;
dados.
b. dados; programas; programa; algoritmo; linguagem de programação; computador;
dados.
c. dados; dados; programa; algoritmo; linguagem de programação; computador;
programas.
d. programas; dados; programa; computador; linguagem de programação; algoritmo;
dados.
e. dados; programas; algoritmo; programa; linguagem de programação; computador;
dados.
Considere as afirmações a seguir sobre alocação de memória.
I - A alocação estática de memória é feita de forma prévia, ou seja, antes da execução
propriamente.
II - A alocação de variáveis locais ou parâmetros de funções é denominada alocação
dinâmica.
III - A alocação estática reserva um espaço de memória contíguo (sequencial) com tamanho
previamente definido.
IV - A vantagem da alocação dinâmica está em não ser necessário especificar, de forma
prévia, a quantidade de memória que será necessária.
É CORRETO o que se afirma APENAS em:
a. II, III e IV.
b. I, III e IV.
c. I, II e IV.
d. I, II e III.
e. II e III.
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. [3, 10, 11, 1, 2]
b. [2, 3, 10, 11, 1]
c. [1, 2, 10, 11, 3]
d. [4, 10, 11, 1, 3]
e. [10, 11, 1, 2, 3]
Considere o seguinte algoritmo em pseudocódigo e assinale e a alternativa CORRETA.
ProcedimentoA(V,x)
1 - se !IsFull(V)
2 - V[tail]←x
3 - tail←tail+1
4 - senão
5 - erro overflow
a. Atualiza um elemento na pilha V.
b. Insere um elemento na pilha V.
c. Insere um elemento na fila V.
d. Remove um elemento na fila V.
e. Remove um elemento na pilha V.
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. Insere um elemento na pilha V.
b. Atualiza um elemento na pilha V.
c. Remove um elemento na fila V.
d. Insere um elemento na fila V.
e. Remove um elemento na pilha V.
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. Selection Sort.
b. Quick Sort.
c. Insertion Sort.
d. Bubble Sort.
e. Merge Sort.
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. Quick Sort.
b. Insertion Sort.
c. Selection Sort.
d. Merge Sort.
e. Bubble Sort.
O problema de ordenação consiste em transformar uma entrada em uma saída, ambas bem
especificadas. Nesse sentido, considere as afirmações a seguir.
I - A entrada de um algoritmo de ordenação é uma sequência ordenada de forma crescente
de n números [x1,x2,…,xn].
II - A saída de um algoritmo de ordenação é uma permutação da entrada [x1',x2',…,xn'].
III - A saída de um algoritmo de ordenação deve atender à restrição x1'>x2'>⋯>xn'.
IV - A entrada de um algoritmo de ordenação [4,3,2,1] produzirá a saída [1,2,3,4].
É CORRETO o que se afirma APENAS em:
a. II e III.
b. I e IV.
c. I e III.
d. II e IV.
e. I e II.
Considere o seguinte algoritmo e assinale a alternativa CORRETA.
Sort(V)
1 - para i←0 até |V|-1
2 - para j←|V|-1 até i+1
3 - se V[j]<V[j-1]
4 - trocar V[j] com V[j-1]
a. Refere-se ao algoritmo Merge Sort.
b. Refere-se ao algoritmo Bubble Sort.
c. Refere-se ao algoritmo Insertion Sort.
d. Refere-se ao algoritmo Selection Sort.
e. Refere-se ao algoritmo Quick Sort.
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. I e III.
b. I e IV.
c. I e II.
d. II e IV.
e. II e III.
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 __________.”
(Resposta)
O algoritmo de ordenação por mistura ou intercalação, mais conhecido como Merge Sort,
também considera a abordagem da divisão e conquista, assim como o seu correlato
Quick Sort. O princípio fundamental do Merge Sort está relacionado com a combinação de
dois subvetores ordenados em um único vetor ordenado.
a. por mistura ou intercalação; Merge Sort; da divisão e conquista; Quick Sort; a
combinação de dois subvetores; um único vetor ordenado.
b. Quick Sort; Merge Sort; por mistura ou intercalação; da divisão e conquista; da
combinação de dois subvetores; um único vetor ordenado.
c. da divisão e conquista; Quick Sort; por mistura ou intercalação; Merge Sort; da
combinação de dois subvetores; um único vetor ordenado.
d. Quick Sort; Merge Sort; da divisão e conquista; por mistura ou intercalação; da
combinação de dois subvetores; um único vetor ordenado.
e. da divisão e conquista; Merge Sort; por mistura ou intercalação; Quick Sort; da
combinação de dois subvetores; um único vetor ordenado.
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 zero até r-1 quatro
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. 1.
b. 3.
c. 4.
d. 2.
e. 0.
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. Nessecontexto, 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,3,7).
c. BuscaBinaria(2,V,0,9), BuscaBinaria(2,V,5,9).
d. BuscaBinaria(2,V,0,9), BuscaBinaria(2,V,0,5).
e. BuscaBinaria(2,V,0,9), BuscaBinaria(2,V,5,7).
Considere o texto a seguir e assinale a alternativa que completa CORRETA e
RESPECTIVAMENTE as lacunas.
“A __________ é uma __________ cujo objetivo é armazenar elementos de forma
sequencial. Nesse contexto, o __________ é armazenado em conjunto com o __________
para o próximo elemento. Esse conjunto é denominado _________.”
A lista ligada é uma estrutura dinâmica de dados cujo objetivo é armazenar elementos
de forma sequencial. Nesse contexto, o elemento da lista é armazenado em conjunto com
o endereço para o próximo elemento. Esse conjunto é denominado célula.
a. lista ligada; célula; elemento da lista; endereço; estrutura dinâmica de dados.
b. lista ligada; célula; endereço; elemento da lista; estrutura dinâmica de dados.
c. lista ligada; estrutura dinâmica de dados; elemento da lista; endereço; célula.
d. célula; estrutura dinâmica de dados; endereço; elemento da lista; lista ligada.
e. célula; estrutura dinâmica de dados; elemento da lista; endereço; lista ligada.
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 insere um elemento em uma lista duplamente ligada.
b. O algoritmo 2 remove um elemento em uma lista duplamente ligada.
c. O algoritmo 2 insere um elemento em uma lista ligada.
d. O algoritmo 2 move um elemento em uma lista ligada.
e. O algoritmo 2 remove um elemento em uma lista ligada.
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. O algoritmo retorna, na linha 4, o valor do elemento identificado.
b. A variável x recebe, na linha 1, o valor do primeiro elemento da lista.
c. A variável x recebe, na linha 3, o seu próprio endereço de memória.
d. A expressão relacional x≠Null é equivalente a x≠0.
e. O laço, na linha 2, compara o valor procurado com os valores na lista.
Analise o algoritmo descrito a seguir e assinale a alternativa que descreve
CORRETAMENTE sua operação.
Algoritmo1(L,k)
1 - p←L
2 - q←L.ponteiro
3 - enquanto q≠Null e q.valor≠k faça
4 - p←q
5 - q←q.ponteiro
6 - se q≠Null
7 - p.ponteiro←q.ponteiro
a. O algoritmo 1 remove um elemento em uma lista duplamente ligada.
b. O algoritmo 1 insere um elemento em uma lista ligada.
c. O algoritmo 1 insere um elemento em uma lista duplamente ligada.
d. O algoritmo 1 move um elemento em uma lista ligada.
e. O algoritmo 1 remove um elemento em uma lista ligada.
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 Pop.
b. O algoritmo 5 descreve a operação Dequeue.
c. O algoritmo 5 descreve a operação Enqueue.
d. O algoritmo 5 descreve a operação Push.
e. O algoritmo 5 descreve a operação Insertion.
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 Dequeue.
b. O algoritmo 4 descreve a operação Push.
c. O algoritmo 4 descreve a operação Insertion.
d. O algoritmo 4 descreve a operação Enqueue.
e. O algoritmo 4 descreve a operação Pop.
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 e posteriormente a respectiva frequência
acumulada, o estado de C como arranjo de frequências acumuladas de A para esse
exemplo é:
a. C=[0,2,3,6,6,6,8,9,10]
b. C=[1,2,3,6,6,6,8,9,10]
c. C=[0,1,2,3,4,6,8,9,10]
d. C=[0,2,3,4,5,6,8,9,10]
e. C=[1,2,3,4,5,6,8,9,10]
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 II, apenas.
b. É correto o que se afirma em I e III, apenas.
c. É correto o que se afirma em II e IV, apenas.
d. É correto o que se afirma em II e III, apenas.
e. É correto o que se afirma em I e IV, apenas
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 II e IV, apenas.
b. É correto o que se afirma em I e III, 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.
Considere um algoritmo cujo tempo de execução é descrito por T(n)=n³. Nesse contexto,
podemos afirmar que:
a. se o tamanho da entrada dobra, o número de instruções é multiplicado por 6.
b. se o tamanho da entrada dobra, o número de instruções é multiplicado por 4.
c. se o tamanho da entrada dobra, o número de instruções é multiplicado por 2.
d. se o tamanho da entrada dobra, o número de instruções é multiplicado por 8.
e. se o tamanho da entrada dobra, o número de instruções é multiplicado por 3.