Logo Passei Direto
Buscar

Outros

Outros
Qual 0 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
User badge image
CuriosidadesGerais

há 8 horas

User badge image
CuriosidadesGerais

há 8 horas

prova metodologia
8 pág.

prova metodologia

Respostas

User badge image

Ed Verified user icon

há 8 horas

Vamos analisar os algoritmos e seus tempos de complexidade no melhor caso: a) Selection-Sort: sempre tem complexidade O(n²), mesmo no melhor caso. b) Quick-Sort: no melhor caso, tem complexidade O(n log n). c) Insertion-Sort: no melhor caso (quando o array já está ordenado), tem complexidade O(n). d) Heap-Sort: sempre tem complexidade O(n log n), mesmo no melhor caso. e) Merge-Sort: sempre tem complexidade O(n log n), mesmo no melhor caso. Portanto, o algoritmo que possui tempo de complexidade no melhor caso proporcional a O(n) é o Insertion-Sort. Resposta correta: c) Insertion-Sort.

Essa resposta te ajudou?

0
Dislike0

Ainda não achou a resposta?

  • Integrado com os principais modelos de IA do mercado
  • Respostas em segundos
  • IA treinada para estudantes brasileiros.
PasseIA logoEvolua sua forma de estudar

Cadastre-se ou realize login

Ainda com dúvidas?

Envie uma pergunta e tenha sua dúvida de estudo respondida!

Essa pergunta também está no material:

prova metodologia
8 pág.

prova metodologia

Mais perguntas desse material

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.
c) Merge Sort e Insertion Sort.
d) Heap Sort e Selection Sort.
e) Merge Sort e Heap Sort.

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) 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á próximo elemento copiado para 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, que implica uma varredura completa de cada vetor de origem.
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.

Simule a execução do algoritmo de ordenação Insertion-Sort com a seguinte entrada [5,2,9,4,1,8].

Algoritmo de ordenação que busca 0 maior elemento do vetor e insere na última posição do vetor e que, posteriormente, busca 0 segundo maior valor do vetor e coloca na penúltima posição do vetor, e assim sucessivamente, até que todo o vetor esteja ordenado, denomina-se:
Qual o nome do algoritmo?
a) Inserion-Sort
b) Selection-Sort
c) Heap-Sort
d) Merge-Sort
e) Quick-Sort

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, primeiro a enviar um pedido de impressão deve ser 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
e) nenhuma das anteriores

Nas estruturas de dados,
Assinale a alternativa correta:
a) devido às características das operações da fila, primeiro elemento a ser inserido será último a ser retirado. Estruturas desse tipo são conhecidas como LIFO.
b) as pilhas são utilizadas para controlar 0 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) a pilha é uma lista linear na qual as operações de inserção e retirada são efetuadas apenas no seu topo.
e) devido às características das operações da pilha, último elemento a ser inserido será último a ser retirado. Estruturas desse tipo são conhecidas como FIFO.

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.

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.

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
Assinale a alternativa correta sobre métodos essenciais das filas:
a) enqueue(x), que insere elemento X no fim da fila, sobrepondo o último elemento.
b) push(x), que insere elemento X no topo da fila, sem sobrepor nenhum elemento.
c) pop(), que remove elemento do início da fila e retorna, ou seja, devolve 0 último elemento inserido.
d) dequeue(), que remove e retorna elemento do começo da fila; um erro ocorrerá se a fila estiver vazia.
e) top(), que retorna 0 elemento do fim da fila sem removê-lo; um erro ocorrerá se a fila estiver vazia.

Mais conteúdos dessa disciplina