2ª prova - Estrutura de dados Flashcards
conceitos de estrutura de dados para as provas
Quais as três operações fundamentais na maioria das estruturas de armazenamento?
Inserção, busca e exclusão
Qual é a estrutura de dados mais comumente utilizada?
Arrays
Quais são os dois tipos principais de arrays?
não-ordenada e ordenada
Quais são as principais vantagem dos arrays não ordenados em relação aos ordenados?
a implementação é mais fácil, e a inserção e exclusão também são mais fáceis
Quais são as principais vantagens dos arrays ordenados em relação aos não-ordenados?
Mais eficiente para buscas e para realizar o acesso
Verdadeiro ou falso: arrays (em java) devem ter o tamanho determinado durante sua criação, e os espaços estarão sempre ocupados, mesmo se não forem utilizados.
Verdadeiro. Em Java, arrays são estruturas de dados estáticas com tamanho definido no momento da criação. Isso significa que o array terá um número fixo de elementos que não poderá ser alterado durante a execução do programa.
Lembrete: você tem que entender do assunto e ver os códigos pois vamos ter códigos a corrigir, só ficar lendo esses flashcards não vai te garantir nada.
Pode colocar que entendeu perfeitamente e, se não quiser estudar, bem, eu avisei!
Qual ocupa mais espaço na memória (considerando o mesmo número de elementos em cada uma), arrays ou lists?
Arrays ocupam menos memória do que listas, pois não precisam armazenar informações adicionais sobre a estrutura da lista.
Quais as vantagens de uma list em relação a uma array?
maior flexibilidade de tamanho, gerenciamento automático de memória e
Para inserir um elemento no meio de uma lista ou um array, qual é mais eficiente?
Em geral, inserir um elemento no meio de uma lista é mais eficiente do que em um array.
verdadeiro ou falso: é possível acessar elementos de uma list aleatoriamente através do índice, da mesma forma que ocorre com arrays
Falso. Listas geralmente não permitem acesso direto a elementos por índice. Em vez disso, você precisa iterar sobre a lista para encontrar o elemento desejado.
Como as duplicadas afetam o desempenho das arrays?
Encontrar um elemento específico em uma lista ou array com duplicatas pode ser mais lento, pois o algoritmo de busca precisa verificar cada elemento, mesmo se já tiver encontrado algum resultado, pois vai precisar de todos, isso se você procurar todos os itens que batam com o termo buscado, e não apenas o primeiro.
Como funciona o bubble sort?
- Ele compara dois itens;
- Se o da esquerda é maior, troca eles;
- Move uma posição para a direita para reiniciar o passo a passo.
Qual a vantagem do selection sort em relação ao bubble sort?
Ele é melhor ao reduzir o número de troca de elementos. O número de comparações é igual.
Como o selection sort funciona?
- Compara dois itens;
- Armazena o número do maior deles;
- Passa para a direita e para para comparar o número maior armazenado, com o próximo, repetindo o processo, até comparar todos, sabendo que o maior número de todos está armazenado;
- Move o maior para a última posição, reinicia o passo a passo com os restantes.
Como funciona o insertion sort?
- Considere o primeiro elemento ordenado.
- Pegue o próximo elemento e compare esse com todos os ordenados à sua esquerda.
- Se for menor, mova os elementos maiores para a direita para abrir espaço.
- Insira o elemento na posição correta.
olhe no https://visualgo.net/en/sorting como funciona, é mais fácil vendo
Qual a diferença entre swapping e moving em elementos?
swap é como se vc estivesse numa fila, e troca de lugar com alguém que está logo na sua frente ou atrás, como ocorre com o bubble e selection sort, enquanto moving é se pedirem para abrirem espaço na fila pra alguém entrar no meio dela, vc não necessáriamente sai do seu lugar pra isso ocorrer, é como ocorre no insertion sort (mas swapping tbm ocorre no insertion sort)
O que é a invariant no selection sort?
a invariante é que os itens à esquerda da posição atual sempre estão ordenados entre si
O que significa o “parcialmente ordenado” no insertion sort?
é quando alguns elementos já estão onde deveriam estar na sequência ordenada, mas ainda existem elementos que precisam ser movidos para suas posições corretas conforme novos elementos são inseridos e o processo de ordenação continua
Qual a diferença fundamental entre uma pilha e uma fila?
enquanto pilha é lifo, last in first out, uma fila é fifo, first in, first out,
qual a diferença entre uma fila comum e uma com prioridade?
A principal diferença em relação a uma fila normal é que, ao remover elementos da priority queue, o elemento com a maior (ou menor) prioridade é retirado primeiro, independentemente da ordem de chegada. Útil para sistemas de gerenciamento
