Prova de Estruturas de Dados

Prévia do material em texto

GABARITO
Protocolo: 884049
Página 1 - 11/06/2024 às 16:29
Substitutiva
Data de aplicação: 29/05/2024
Curso: Engenharia de Software
Disciplina: Estruturas de Dados I
Ano: 20241 / Semestre: 3
RGM: 123.1736 / Aluno: NATANIELI LIMA LINCH
PROVA 01
Questão 1
uais serão os valores de x, y e p ao final do trecho de código abaixo?
 
 int x, y, *p; 
 y = 0;
 p = &y;
 x = *p;
 x = 4;
 (*p)++;
 --x;
 (*p) += x;
Resposta do aluno:
Questão 2
 
Analise o programa abaixo, verifique se está correto ou incorreto. Caso esteja incorreto, aponte o erro.
 
main ( )
{
 int x, *p;
 x = 10;
 p = x;
 cout<<*p;
}
 
Resposta do aluno: { INT X, *P; X= 10; P= &X; cout<<*p; }
Parecer do professor: Corrigida!
Questão 3
Dois vetores ordenados, contendo, cada um deles, n números inteiros, precisam ser unidos em outro vetor
maior, que conterá os 2n números, que também serão armazenados de forma ordenada. A complexidade de
tempo de melhor caso desse processo será, então:
a) O(1), pois se precisa fazer apenas uma cópia simples de cada um dos elementos originais.
b) O(log n), pois se usa a busca binária para determinar qual será o próximo elemento copiado para o vetor de
destino.
c) O(nlog n), pois se precisa fazer uma busca de cada elemento para depois inseri-lo no vetor de destino.
d) O(n), pois se precisa fazer uma cópia de cada um dos elementos originais, o que implica uma varredura
GABARITO
Protocolo: 884049
Página 2 - 11/06/2024 às 16:29
completa de cada vetor de origem. (correta)
e) O(n^2), pois, como há dois vetores, precisa-se fazer dois laços de forma aninhada (um dentro do outro),
gerando uma multiplicação das quantidades de elementos.
Questão 4
No desenvolvimento de um sistema de análise financeira, um programador utilizou um algoritmo cuja
complexidade de tempo, no pior caso, é igual a O(n^2). Outro programador aponta um algoritmo de melhor
complexidade igual a:
a) O(n^4).
b) O(n log n). (correta)
c) O(n^3).
d) O(2^n).
e) O(n!).
Questão 5
Quais os algoritmos de ordenação abaixo possuem tempo no pior caso proporcional a O(n^2)?
a) Quick Sort e Merge Sort.
b) Selection Sort e Insertion Sort. (correta)
c) Merge Sort e Insertion Sort.
d) Heap Sort e Selection Sort.
e) Merge Sort e Heap Sort.
Questão 6
Seja n o tamanho da entrada de um algoritmo para um problema P. Cada alternativa, que corresponde a um
algoritmo distinto, apresenta o número de operações necessárias para resolver P. Considerando-se a análise
assintótica (O notation), qual algoritmo possui maior complexidade?
a) 2 + logn
b) n + 3n^2
c) 1000 + 2n^3
d) 5n + 128
e) 4^n (correta)
Questão 7
Qual das instruções abaixo é correta para declarar um ponteiro para inteiro? 
a) *int pti;
b) *pti;
c) &i;
d) int_pti pti;
e) int *pti; (correta)
Questão 8
Observe o código abaixo, que busca o maior elemento de um vetor v[0..n -1], e assinale a sua complexidade.
GABARITO
Protocolo: 884049
Página 3 - 11/06/2024 às 16:29
a) O(n) (correta)
b) O(logn)
c) O(nlogn)
d) O(1)
e) O(n^2)
Questão 9
A busca binária é conhecida também como busca logarítmica. Sobre a busca binária, assinale a alternativa
INCORRETA. 
a) Para um conjunto de 15 elementos, ocorreria, no mínimo, 1 comparação e, no máximo, 4 comparações.
b) Quando comparada com a busca sequencial, a busca binária, há uma redução logarítmica dos elementos a
serem pesquisados .
c) 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.
(correta)
d) Considerando uma sequência qualquer, deve-ser dividir o conjunto ao meio e verificar se o elemento
procurado é igual ao elemento central.
e) 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.
Questão 10
Seja a seguinte sequência de instruções em um programa C/C++:
 
 int *pti;
 int i = 10;
 pti = &i;
 
Qual afirmativa é falsa?
 
a) pti armazena o endereço de i
b) *pti é igual a 10
c) ao se executar *pti = 20, i passará a ter o valor 20
d) ao se alterar o valor de i, *pti será modificado
e) pti é igual a 10 (correta)
PROVA 02
Questão 1
Simule a execução do algoritmo de ordenação Selection-Sort com a seguinte entrada [5, 2, 9, 4, 1, 8].
Resposta do aluno:
GABARITO
Protocolo: 884049
Página 4 - 11/06/2024 às 16:29
Questão 2
Simule a execução do algoritmo de ordenação Bubble-Sort com a seguinte entrada [5, 2, 9, 4, 1, 8].
Resposta do aluno:
Questão 3
O algoritmo de ordenação que busca o maior elemento do vetor e o insere na última posição do vetor e que,
posteriormente, busca o segundo maior valor do vetor e o coloca na penúltima posição do vetor, e assim
sucessivamente, até que todo o vetor esteja ordenado, denomina-se:
a) Inserion-Sort
b) Selection-Sort (correta)
c) Heap-Sort
d) Merge-Sort
e) Quick-Sort
Questão 4
Sobre listas encadeadas, é INCORRETO afirmar que:
a) os dados são armazenados dinamicamente.
b) são acessadas pelo primeiro nó da lista.
c) o final da lista faz uma referência para nulo.
d) possuem tamanho fixo. (correta)
e) pilhas e filas podem ser implementadas como listas encadeadas.
Questão 5
Uma das estratégias de ordenação consiste no seguinte processo: uma coleção desordenada de elementos é
dividida em duas metades e cada metade é utilizada como argumento para a reaplicação recursiva do
procedimento. Os resultados das duas reaplicações são, então, combinados pela intercalação dos elementos de
ambas, resultando em uma coleção ordenada. Qual algoritmo emprega essa estratégia?
a) Insertion-Sort
b) Merge-Sort (correta)
c) Bubble-Sort
d) Quick-Sort
e) Selection-Sort
Questão 6
Dada a seguinte sequencia de operações em uma Pilha:
 
PUSH P
PUSH E
PUSH R
PUSH T
PUSH O
POP
POP
PUSH S
PUSH O
PUSH L
POP
 
Considerando que o topo da pilha está à esquerda, assinale a alternativa que corresponde ao final das
GABARITO
Protocolo: 884049
Página 5 - 11/06/2024 às 16:29
operações realizadas:
a) O - T - R - E - P
b) P - E - R - S - O
c) L - O - T - R - P
d) O - S - R - E - P (correta)
e) P - E - R - T - O
Questão 7
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) 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.
b) 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.
c) 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.
d) 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. (correta)
e) 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.
Questão 8
Qual o algoritmo de ordenação abaixo possui tempo de complexidade no melhor caso proporcional a O(n)?
a) Selection-Sort
b) Quick-Sort
c) Insertion-Sort. (correta)
d) Heap-Sort.
e) Merge-Sort
Questão 9
Considere uma estrutura de fila (disciplina FIFO) de números inteiros com duas operações: INSERE (n) e RETIRA
( ). Considere, também, que a representação do estado da fila em um instante qualquer é realizada listando os
elementos, de forma que o primeiro elemento, da esquerda para a direita, é o mais antigo presente na fila. A
execução das operações a seguir levará uma fila ao estado:
a) 1 2 3 4 5
b) 2 3 1 4 5
c) 3 1 4
d) 4 5 (correta)
e) 5
GABARITO
Protocolo: 884049
Página6 - 11/06/2024 às 16:29
Questão 10
Observando o código abaixo, a função apresentada é a implementação de que algoritmo de ordenação?
a) Merge-Sort
b) Bubble-Sort
c) Insertion-Sort
d) Selection-sort (correta)
e) Quick-Sort