Atividade Avaliativa Especial - Prova 2

Prévia do material em texto

1/4
CENTRO UNIVERSITÁRIO DA GRANDE DOURADOS
Curso: Engenharia de Software
Semestre: 3º 
Disciplina: Estruturas de Dados I
ATIVIDADE AVALIATIVA ESPECIAL (AAE) 2 - referente as aulas 5 a 8
Professor: Marcos Alves Mariano
Observação:
Cada Atividade respondida de forma correta terá até 1 ponto por anotação correta
1º) 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.
c) Bubble-Sort.
d) Quick-Sort.
e) Selection-Sort.
2º) Assinale a alternativa que corresponde aos algoritmos de ordenação que adotam a estratégia de
divisão e conquista.
a) Merge-Sort e Quick-Sort.
b) Inserion-Sort e Selection-Sort.
c) Heap-Sort e Selection-Sort.
d) Insertion-Sort e Heap-Sort.
e) Quick-Sort e Heap-Sort.
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.
c) Heap-Sort.
d) Merge-Sort.
e) Quick-Sort.
 2/4
4º) 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.
d) Heap-Sort.
e) Merge-Sort
5º) Estruturas de dados básicas, como as pilhas e filas, são usadas em uma gama variada de
aplicações. As filas, por exemplo, suportam alguns métodos essenciais, como o:
a) enqueue(x), que insere o elemento x no fim da fila, sobrepondo o último elemento.
b) push(x), que insere o elemento x no topo da fila, sem sobrepor nenhum elemento.
c) pop(), que remove o elemento do início da fila e o retorna, ou seja, devolve o último elemento
inserido.
d) dequeue(), que remove e retorna o elemento do começo da fila; um erro ocorrerá se a fila
estiver vazia.
e) top(), que retorna o elemento do fim da fila sem removê-lo; um erro ocorrerá se a fila estiver vazia.
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
operações realizadas:
a) O - T - R - E - P
b) O - S - R - E - P
c) P - E - R - S - O
d) L - O - T - R - P
e) P - E - R - T - O
 3/4
7º) 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:
INSERE (2)
INSERE (3)
RETIRA ( )
INSERE (1)
RETIRA ( )
INSERE (4)
INSERE (5)
RETIRA ( )
a) 1 2 3 4 5
b) 2 3 1 4 5
c) 3 1 4
d) 4 5
e) 5
8º) Nas estruturas de dados:
a) devido às características das operações da fila, o primeiro elemento a ser inserido será o último a ser
retirado. Estruturas desse tipo são conhecidas como LIFO.
b) as pilhas são utilizadas para controlar o acesso de arquivos que concorrem a uma única impressora.
c) a fila é uma lista linear na qual as operações de inserção e retirada ocorrem apenas no início
da lista.
d) devido às características das operações da pilha, o último elemento a ser inserido será o último a ser
retirado. Estruturas desse tipo são conhecidas como FIFO.
e) a pilha é uma lista linear na qual as operações de inserção e retirada são efetuadas apenas no seu
topo.
9º) Ana precisa utilizar uma estrutura de dados para gerenciar trabalhos de impressão em uma
impressora compartilhada por vários computadores em uma rede. As regras dessa estrutura devem
permitir que os trabalhos sejam impressos na ordem em que forem enviados, ou seja, o primeiro a
enviar um pedido de impressão deve ser o primeiro a ter sua solicitação atendida. Não deve ser
permitido inserir pedidos de impressão no meio dos pedidos já realizados. A estrutura de dados mais
adequada para Ana utilizar é:
a) pilha.
b) lista ordenada.
c) lista desordenada.
d) fila.
 4/4
e) nenhuma das anteriores.
10º) Uma estrutura de dados que possui dois campos: um ponteiro e campo de informação denomina-
se:
a) lista encadeada dupla.
b) lista encadeada simples.
c) pilha.
d) fila.
e) vetor.