Desenvolvimento (No Code) Flashcards
- (Instituto Cidades - 2012 - TCM-GO - Auditor de Controle Externo - Informática) São exemplos de algoritmos de ordenação, exceto:
a) Bubble Sort
b) Select Sort
c) Shell Sort
d) Busca Sequencial;
e) Quick Sort;
Conforme vimos em aula, a Busca Sequencial não é um algoritmo de ordenação! Na verdade, ele é um método de pesquisa sobre estruturas de dados.
- BubbleSort(Troca)(Bolhas subindo cada vez menos): Repetidamente troca elementos adjacentes se estiverem na ordem errada.
- InsertionSort(Inserção)(Baralho): Insere cada elemento na posição correta dentro da parte ordenada da lista.
- SelectionSort(Seleção): Seleciona o menor (ou maior) elemento e o coloca na posição correta.
- QuickSort(Troca): Ordena dividindo a lista em sublistas ao redor de um pivô.
- MergeSort(Intercalação): Divide a lista em sublistas, ordena recursivamente e mescla as sublistas.
- HeapSort(Seleção): Constrói um heap (árvore binária) e extrai repetidamente o maior elemento para ordenar a lista.
- ShellSort(Inserção): Ordena elementos comparando e movendo incrementos de distância decrescentes.
Gabarito: D
- (FUMARC - 2012 - TJ-MG - Técnico Judiciário - Analista de Sistemas – I) Quicksort divide um conjunto de itens em conjuntos menores, que são ordenados de forma independe, e depois os resultados são combinados para produzir a solução de ordenação do conjunto maior.
Conforme vimos em aula, está perfeito! Sendo um algoritmo do tipo Dividir Para Conquistar, ele reparte o conjunto de dados em conjuntos menores, que são ordenados independentemente e depois combinados em uma solução maior.
- BubbleSort(Troca)(Bolhas subindo cada vez menos): Repetidamente troca elementos adjacentes se estiverem na ordem errada.
- InsertionSort(Inserção)(Baralho): Insere cada elemento na posição correta dentro da parte ordenada da lista.
- SelectionSort(Seleção): Seleciona o menor (ou maior) elemento e o coloca na posição correta.
- QuickSort(Troca): Ordena dividindo a lista em sublistas ao redor de um pivô.
- MergeSort(Intercalação): Divide a lista em sublistas, ordena recursivamente e mescla as sublistas.
- HeapSort(Seleção): Constrói um heap (árvore binária) e extrai repetidamente o maior elemento para ordenar a lista.
- ShellSort(Inserção): Ordena elementos comparando e movendo incrementos de distância decrescentes.
Gabarito: C
- (CESPE - 2012 - MPE-PI - Analista Ministerial - Informática - Cargo 6) O heapsort é um algoritmo de ordenação em que a quantidade de elementos armazenada fora do arranjo de entrada é constante durante toda a sua execução.
Inicialmente, insere-se os elementos da lista em um heap.
Em seguida, fazemos sucessivas remoções do
menor elemento do heap, colocando os elementos removidos do heap de volta na lista – a lista estará então em ordem crescente.
O heapsort é um algoritmo de ordenação em que a sua estrutura auxiliar de armazenamento fora do arranjo de entrada é constante durante toda a sua execução.
Essa questão é polêmica. O arranjo tem tamanho constante, mas a quantidade de elementos é variável.
Diferente de outros algoritmos de ordenação que tem uma estrutura auxiliar de tamanho variável (assim como seus elementos), o Heap Sort tem uma estrutura auxiliar de tamanho fixo (porém a quantidade de elementos é variável).
Como é dito por Neil Dale: “A heapsort is just as efficient in terms of space; only one array is used to store the data. The heap sort requires only constante extra space”. No entanto, a questão foi dada como correta!
- BubbleSort(Troca)(Bolhas subindo cada vez menos): Repetidamente troca elementos adjacentes se estiverem na ordem errada.
- InsertionSort(Inserção)(Baralho): Insere cada elemento na posição correta dentro da parte ordenada da lista.
- SelectionSort(Seleção): Seleciona o menor (ou maior) elemento e o coloca na posição correta.
- QuickSort(Troca): Ordena dividindo a lista em sublistas ao redor de um pivô.
- MergeSort(Intercalação): Divide a lista em sublistas, ordena recursivamente e mescla as sublistas.
- HeapSort(Seleção): Constrói um heap (árvore binária) e extrai repetidamente o maior elemento para ordenar a lista.
- ShellSort(Inserção): Ordena elementos comparando e movendo incrementos de distância decrescentes.
Gabarito: C
- (CESPE - 2010 - ABIN - Oficial Técnico de Inteligência - Área de Suporte a Rede de Dados) A eficácia do método de ordenação rápida (quicksort) depende da escolha do pivô mais adequado ao conjunto de dados que se deseja ordenar. A situação ótima ocorre quando o pivô escolhido é igual ao valor máximo
ou ao valor mínimo do conjunto de dados.
Alguns autores consideram a divisão em três subconjuntos, sendo o terceiro contendo valores iguais ao pivô.
O Melhor Caso ocorre quando o conjunto é dividido em subconjuntos de mesmo tamanho;
o Pior Caso ocorre quando o pivô corresponde a um dos extremos (menor ou maior valor). Alguns o consideram um algoritmo frágil e não-estável, com baixa tolerância a erros.
Conforme vimos em aula, a questão se refere ao pior caso!
Gabarito: E
- (CESPE - 2010 - ABIN - Oficial Técnico de Inteligência - Área de Suporte a Rede de Dados)
A estabilidade de um método de ordenação é importante quando o conjunto de dados já está parcialmente ordenado.
Na imagem acima, foi colocado um sinal de aspas simples e duplas apenas para diferenciá-los, mas trata-se do mesmo número.
Um algoritmo estável ordena todo o restante e não perde tempo trocando as posições de elementos que possuam chaves idênticas.
Já um algoritmo instável ordena todos os elementos, inclusive aqueles que possuem chaves idênticas (sob algum outro critério).
Conforme vimos em aula, a estabilidade é irrelevante com dados parcialmente ordenados ou não!
A estabilidade é importante quando se deseja ordenar um conjunto de dados por mais de um critério (Ex: primeiro pelas chaves e segundo por índices). Se esse não for o caso (e a questão não disse que era!), a estabilidade “não fede nem cheira”. O fato de os dados estarem parcialmente ordenados não fará diferença em termos de ordenação – ambos serão ordenados da mesma maneira.
Gabarito: E
- (CESPE - 2010 - Banco da Amazônia - Técnico Científico - Tecnologia da Informação - Administração de Dados)
A classificação interna por inserção é um método que realiza a ordenação de um vetor por meio da inserção de cada elemento em sua posição correta dentro de um subvetor classificado.
Conforme vimos em aula, trata-se do InsertionSort!
- BubbleSort(Troca)(Bolhas subindo cada vez menos): Repetidamente troca elementos adjacentes se estiverem na ordem errada.
- InsertionSort(Inserção)(Baralho): Insere cada elemento na posição correta dentro da parte ordenada da lista.
- SelectionSort(Seleção): Seleciona o menor (ou maior) elemento e o coloca na posição correta.
- QuickSort(Troca): Ordena dividindo a lista em sublistas ao redor de um pivô.
- MergeSort(Intercalação): Divide a lista em sublistas, ordena recursivamente e mescla as sublistas.
- HeapSort(Seleção): Constrói um heap (árvore binária) e extrai repetidamente o maior elemento para ordenar a lista.
- ShellSort(Inserção): Ordena elementos comparando e movendo incrementos de distância decrescentes.
Gabarito: C
- (FCC - 2009 - TRT - 15ª Região - Analista Judiciário - Tecnologia da Informação) São algoritmos de classificação por trocas apenas os métodos:
a) SelectionSort e InsertionSort.
b) MergeSort e BubbleSort.
c) QuickSort e SelectionSort.
d) BubbleSort e QuickSort.
e) InsertionSort e MergeSort.
- BubbleSort(Troca)(Bolhas subindo cada vez menos): Repetidamente troca elementos adjacentes se estiverem na ordem errada.
- InsertionSort(Inserção)(Baralho): Insere cada elemento na posição correta dentro da parte ordenada da lista.
- SelectionSort(Seleção): Seleciona o menor (ou maior) elemento e o coloca na posição correta.
- QuickSort(Troca): Ordena dividindo a lista em sublistas ao redor de um pivô.
- MergeSort(Intercalação): Divide a lista em sublistas, ordena recursivamente e mescla as sublistas.
- HeapSort(Seleção): Constrói um heap (árvore binária) e extrai repetidamente o maior elemento para ordenar a lista.
- ShellSort(Inserção): Ordena elementos comparando e movendo incrementos de distância decrescentes.
Gabarito: D
- (CESGRANRIO - 2011 - PETROBRÁS – Analista de Sistemas – I)
O tempo de pior caso do algoritmo QuickSort é de ordem menor que o tempo médio do algoritmo Bubblesort.
Tempo: O(n) < O(n log n) < O(n²)
Métodos Estáveis: BIM - Bub, Ins e Mer
São iguais: O(n²).
Gabarito: E
- (CESGRANRIO - 2011 - PETROBRÁS – Analista de Sistemas – II)
O tempo médio do QuickSort é O(nlog2n), pois ele usa como estrutura básica uma árvore de prioridades.
Tempo: O(n) < O(n log n) < O(n²)
Métodos Estáveis: BIM - Bub, Ins e Mer
Conforme vimos em aula, de fato, ele tem tempo médio O(n log n), mas ele usa como estrutura básica uma lista ou um vetor!
Gabarito: E
- (CESGRANRIO - 2011 - PETROBRÁS – Analista de Sistemas – III)
O tempo médio do QuickSort é de ordem
igual ao tempo médio do MergeSort.
Tempo: O(n) < O(n log n) < O(n²)
Métodos Estáveis: BIM - Bub, Ins e Mer
Conforme vimos em aula, ambos têm tempo O(n log n).
Gabarito: C
- (CESGRANRIO - 2012 - CMB – Analista de Sistemas – III)
Em uma reunião de análise de desempenho de um sistema WEB, um programador apontou corretamente que a complexidade de tempo do algoritmo bubblesort, no pior caso, é:
a) O(1)
b) O(log n)
c) O(n)
d) O(n log n)
e) O(n2)
Tempo: O(n) < O(n log n) < O(n²)
Métodos Estáveis: BIM - Bub, Ins e Mer
Conforme vimos em aula, trata-se de O(n²)!
Gabarito: E
- (CESPE - 2010 – INMETRO – Analista de Sistemas) Se f é uma função de complexidade para um algoritmo F, então O(f) é considerada a complexidade assintótica ou o comportamento assintótico do algoritmo F.
Assinale a opção que apresenta somente algoritmos que possuem complexidade assintótica quando f(n) = O(n log n).
a) HeapSort e BubbleSort
b) QuickSort e InsertionSort
c) MergeSort e BubbleSort
d) InsertionSort
e) HeapSort, QuickSort e MergeSort
Tempo: O(n) < O(n log n) < O(n²)
Métodos Estáveis: BIM - Bub, Ins e Mer
Conforme vimos em aula, trata-se da última opção. Vejam que ele não utilizou, nessa questão, o Pior Caso.
Gabarito: E
- (FGV - 2013 – MPE/MS – Analista de Sistemas) Assinale a alternativa que indica o algoritmo de ordenação capaz de funcionar em tempo O(n) para alguns conjuntos de entrada.
a) Selectionsort (seleção)
b) Insertionsort (inserção)
c) Merge sort
d) Quicksort
e) Heapsort
Tempo: O(n) < O(n log n) < O(n²)
Métodos Estáveis: BIM - Bub, Ins e Mer
Conforme vimos em aula, trata-se da segunda opção.
Gabarito: B
- (CESGRANRIO - 2010 – BACEN – Analista de Sistemas)
Uma fábrica de software foi contratada para desenvolver um produto de análise de riscos. Em determinada funcionalidade desse software, é necessário realizar a ordenação de um conjunto formado por muitos números inteiros.
Que algoritmo de ordenação oferece melhor complexidade de tempo (Big O notation) no pior caso?
a) Merge sort
b) Insertion sort
c) Bubble sort
d) Quick sort
e) Selection sort
Tempo: O(n) < O(n log n) < O(n²)
Métodos Estáveis: BIM - Bub, Ins e Mer
Conforme vimos em aula, trata-se da primeira opção!
Gabarito: A
- (CESPE - 2011 – FUB – Analista de Sistemas) Os métodos de ordenação podem ser classificados como estáveis ou não estáveis. O método é estável se preserva a ordem relativa de dois valores idênticos.
Alguns métodos eficientes como shellsort ou quicksort não são estáveis, enquanto alguns métodos pouco eficientes, como o método da bolha, são estáveis.
Tempo: O(n) < O(n log n) < O(n²)
Métodos Estáveis: BIM - Bub, Ins e Mer
Métodos Instáveis: SelectionSort, QuickSort,
HeapSort e ShellSort.
Portanto, item perfeito!
Gabarito: C
- (CESPE - 2012 – BASA – Analista de Sistemas) O método de classificação Shellsort iguala-se ao método Quicksort em termos de complexidade temporal, porém é mais eficiente para quantidades pequenas a moderadas de dados.
Tempo: O(n) < O(n log n) < O(n²)
Métodos Estáveis: BIM - Bub, Ins e Mer
Não há correlação direta entre complexidade de custo e complexidade temporal, logo eu não posso usar a função de um para calcular o outro.
Gabarito: E
- (CESPE - 2012 – BASA – Analista de Sistemas) O método de classificação Quicksort é estável e executado em tempo linearmente dependente da quantidade de dados que estão sendo classificados.
Tempo: O(n) < O(n log n) < O(n²)
Métodos Estáveis: BIM - Bub, Ins e Mer
QuickSort é instável e não possui complexidade temporal linear!
Gabarito: E
- (CESPE - 2012 – BASA – Analista de Sistemas)
No método de ordenamento denominado shellsort, as comparações e as trocas são feitas conforme determinada distância entre dois elementos, de modo que, uma distância igual a 6 seria a comparação entre o primeiro elemento e o sétimo, ou entre o segundo elemento e o oitavo, e assim sucessivamente, repetindo-se esse processo até que as últimas
comparações e trocas tenham sido efetuadas e a distância tenha diminuído até chegar a 1.
É o algoritmo mais eficiente dentre os de ordem quadrática. Nesse método, as comparações e as trocas são feitas conforme determinada distância (gap) entre dois elementos, de modo que, se gap = 6, há comparação entre o 1º e 7º elementos ou entre o 2º e 8º elementos e assim sucessivamente, repetindo até que as últimas
comparações e trocas tenham sido efetuadas e o gap tenha chegado a 1.
Conforme vimos em aula, a questão descreveu perfeitamente o mecanismo de ordenação do Shellsort.
Gabarito: C
- (FGV - 2008 – PETROBRÁS – Analista de Sistemas) Sobre o algoritmo de ordenação heapsort, assinale a afirmação correta.
a) Utiliza ordenação por árvore de decisão, ao invés de ordenação por comparação.
b) A estrutura de dados que utiliza, chamada heap, pode ser interpretada como uma árvore binária.
c) Seu desempenho de pior caso é pior do que o do algoritmo quicksort.
d) Seu desempenho de pior caso é o mesmo da ordenação por inserção.
e) Seu desempenho de pior caso é menor do que o da ordenação por intercalação.
Tempo: O(n) < O(n log n) < O(n²)
Métodos Estáveis: BIM - Bub, Ins e Mer
(a) Utiliza ordenação por seleção;
(b) Perfeito;
(c) Não, é melhor que o QuickSort;
(d) Não, é melhor que o InsertionSort;
(e) Não, é idêntico ao MergeSort.
Gabarito: B
- (CESGRANRIO – 2009 – BASA – Analista de Sistemas)
Com relação aos algoritmos quicksort e mergesort, o tempo de execução para o:
a) pior caso do quicksort é (n lg n).
b) pior caso do mergesort é (n2).
c) pior caso do mergesort é (n lg n).
d) caso médio do mergesort é O(lg n).
e) caso médio do quicksort é O(n2).
Tempo: O(n) < O(n log n) < O(n²)
Métodos Estáveis: BIM - Bub, Ins e Mer
Conforme vimos em aula, trata-se da terceira opção. Gabarito: C
- (CESPE – 2009 – UNIPAMPA – Analista de Sistemas)
O algoritmo quicksort, que divide uma instrução em quatro blocos diferentes de busca, é um exemplo de estrutura de ordenação de dados.
Conforme vimos em aula, são dois blocos diferentes de busca.
Gabarito: E
- (CESPE - 2013 – CPRM – Analista de Sistemas)
No algoritmo de ordenação denominado quicksort, escolhe-se um ponto de referência, denominado pivô, e separam-se os elementos em dois grupos: à esquerda, ficam os elementos menores que o pivô, e à direita ficam os maiores. Repete-se esse processo para os grupos de elementos formados (esquerda e direita) até que todos os elementos estejam ordenados.
Esse algoritmo divide um conjunto de itens em conjuntos menores, que são ordenados de forma independente, e depois os resultados são combinados para produzir a solução de ordenação do conjunto maior.
Trata-se, portanto, de um algoritmo do tipo Divisão-e-Conquista, i.e., repartindo os dados em subgrupos, dependendo de um elemento chamado pivô.
Neste método, a lista é dividida em parte esquerda e parte direita, sendo que os elementos da parte esquerda são todos menores que os elementos da parte direita. Essa fase do processo é chamada de
partição.
Em seguida, as duas partes são ordenadas recursivamente (usando o próprio QuickSort). A lista está, portanto, ordenada corretamente!
Conforme vimos em aula, é exatamente assim!
Gabarito: C
- (CESPE - 2013 – MPU – Analista de Sistemas)
Entre os algoritmos de ordenação e pesquisa bubble sort, quicksort e heapsort, o quicksort é considerado o mais eficiente, pois se caracteriza como um algoritmo de dividir-para-conquistar, utilizando operações de particionamento.
Conforme vimos em aula, o HeapSort é o mais eficiente no pior caso!
Gabarito: E
- (CESPE - 2013 – TRT/9 – Analista de Sistemas)
No método Quicksort, o pivô é responsável pelo número de partições em que o vetor é dividido. Como o pivô não pode ser um elemento que esteja repetido no vetor, o Quicksort não funciona quando há elementos repetidos.
O pivô não é responsável pelo número de partições em que o vetor é dividido. Ademais, ele pode sim ser um elemento que esteja repetido no vetor!
Gabarito: E
" . $e->getMessage(); } $conn = null; Considerando o uso de PHP Data Objects, para que o comando UPDATE seja executado corretamente a lacuna I deve ser preenchida com a) mysqli_query($conn, $sql); b) $conn.execute($sql); c) $st = $conn.prepare($sql); $st.exec(); d) $conn->query($sql); e) $st = $conn->prepare($sql); $st->execute();