Sobre listas sequenciais e listas encadeadas, é correto afirmar que:
Em uma lista encadeada, a ordem lógica dos elementos não corresponde ao posicionamento destes em memória. Por conta disso, é possível fazer acesso a qualquer elemento da lista em tempo constante.
Um vetor alocado estaticamente pode ser chamado de lista linear sequencial, pois a ordem lógica é igual à ordem física. O mesmo não ocorre com vetores alocados dinamicamente, pois estes podem ter seus elementos em lugares diversos na memória.
Para a busca binária funcionar com desempenho em tempo O(log n), precisamos da propriedade de que cada elemento possa ser acessado em tempo constante dado o índice. Nesse caso, é requerida uma lista linear sequencial, não sendo interessante usar lista encadeada.
Quando temos uma lista encadeada, o acesso a cada elemento, dado o índice, ocorre em tempo constante.
Em um vetor alocado dinamicamente, podemos aumentar ou diminuir o número de elementos. Nesse caso, é mais fácil alocar vetores com "new" do que estaticamente.
Soluções para a tarefa
Respondido por
1
Resposta:
Para a busca binária funcionar com desempenho em tempo O(log n), precisamos da propriedade de que cada elemento possa ser acessado em tempo constante dado o índice. Nesse caso, é requerida uma lista linear sequencial, não sendo interessante usar lista encadeada.
Explicação:
Perguntas interessantes
Geografia,
5 meses atrás
História,
5 meses atrás
Ed. Física,
7 meses atrás
Inglês,
7 meses atrás
História,
11 meses atrás
Matemática,
11 meses atrás