Exercícios MT2

Lista ordenada simplesmente ligada.

Para devolver $X$ ou o seu predecessor basta uma pesquisa sequencial numa lista ordenada: quando se ultrapassa o valor procurado, o nó anterior é o imediatamente anterior. Uma lista ordenada simplesmente ligada é suficiente e é a que ocupa menos espaço.

• Lista ordenada simplesmente ligada. Numa lista ordenada, a pesquisa do predecessor de $X$ faz-se durante a própria pesquisa, em $O(n)$ no pior caso, e a representação simplesmente ligada poupa o espaço extra do ponteiro para o nó anterior.
• Lista ordenada duplamente ligada. Também funciona, mas gasta mais memória por elemento (ponteiro extra) sem melhorar o tempo de pesquisa.
• Lista desordenada simplesmente ligada. Numa lista desordenada é preciso percorrer todos os elementos e não se identifica o predecessor de $X$ de forma direta.
• Lista desordenada duplamente ligada. A desordenação impede a pesquisa eficiente e a dupla ligação só acarreta custo de espaço.
• Nenhuma das possibilidades anteriores. Há uma estrutura adequada entre as enumeradas.

Pilha (stack).

O retorno à página anterior segue a ordem inversa das visitas (LIFO). Numa pilha, tanto a consulta da página atual (top) como a entrada numa nova página (push) e o retorno (pop) são operações em $O(1)$.

• Pilha. A página "anterior" é sempre a última que foi visitada (disciplina LIFO), que é precisamente o comportamento de uma pilha, com push/pop em $O(1)$.
• Fila. Uma fila retira primeiro a página mais antiga, não a visitada imediatamente antes.
• Lista simplesmente ligada. Funciona, mas não exprime a disciplina LIFO de forma tão direta e económica.
• Lista duplamente ligada. Gasta mais espaço sem vantagem para este cenário.
• É indiferente o uso de qualquer das estruturas enumeradas. A pilha é claramente a mais adequada e económica.

I, II e III apenas.

Inserir no início (I) e remover o primeiro elemento (III) acedem diretamente ao primeiro nó. Inserir no fim (II) é direto porque existe referência para o último nó. Remover o último elemento (IV) exige o penúltimo nó, que numa lista simplesmente ligada só se alcança percorrendo a lista: $O(n)$.

• I e II apenas. Falta a remoção no início, que também é $O(1)$.
• I e III apenas. Operação II (inserir no fim) também é $O(1)$, por causa da referência para o último nó.
• I, II e III apenas. Com referências para o primeiro e o último nó, inserir no início, inserir no fim e remover o primeiro elemento são $O(1)$. Remover o último exige chegar ao penúltimo nó, logo é $O(n)$.
• I, II e IV apenas. Remover o último elemento não é $O(1)$ numa lista simplesmente ligada.
• Nenhuma das anteriores. Há operações em $O(1)$.

queue<stack<Item>>.

As encomendas devem ser enviadas pela ordem em que chegam: disciplina FIFO, que é a de uma fila (queue). Dentro de cada encomenda, os itens são encaixotados numa pilha (stack). Assim, a estrutura correta é uma fila de pilhas.

• vector<vector<Item>>. O vetor não garante a disciplina FIFO de expedição das encomendas.
• list<stack<Item>>. A lista não retira primeiro a encomenda mais antiga.
• queue<stack<Item>>. A fila processa as encomendas por ordem de chegada (FIFO) e cada encomenda é uma pilha de itens encaixotados.
• stack<queue<Item>>. A pilha retiraria primeiro a encomenda mais recente, violando a ordem temporal.
• É indiferente o uso de qualquer das estruturas enumeradas. A ordem temporal da encomenda exige uma fila de encomendas.

f1 contém um palíndromo.

O ciclo inicial passa os primeiros $k = \lfloor n/2 \rfloor$ elementos para a pilha (ficando na ordem inversa no topo) e, se o número de elementos é ímpar, descarta o elemento do meio. Depois compara o resto da fila com o topo da pilha: a igualdade elemento a elemento com a primeira metade invertida caracteriza um palíndromo.

• f1 contém um número ímpar de elementos. A função não testa a paridade do número de elementos.
• f1 contém um palíndromo (a sequência é igual quando vista nos dois sentidos). A primeira metade da fila é empilhada e depois comparada, elemento a elemento, com a segunda metade na ordem inversa: é o teste clássico de palíndromo.
• f1 contém duas sequências iguais nas suas metades. A comparação é feita com a pilha, ou seja, com a primeira metade invertida.
• f1 contém uma sequência ordenada. A ordenação não é verificada.
• Nenhuma das anteriores. Há uma resposta correta.

Fila (queue).

A recolha de sangue deve atender os pacientes pela ordem em que chegam. A fila garante a disciplina FIFO (primeiro a entrar, primeiro a ser atendido), com atendimento e saída em $O(1)$.

• Pilha. Atenderia primeiro o último paciente a chegar, o que não é justo nem habitual.
• Fila. Os pacientes são atendidos pela ordem de chegada (FIFO), que é a disciplina de uma fila, com as operações principais em $O(1)$.
• Lista. A lista não impone a ordem de chegada por si só.
• Lista ordenada. Não há critério de ordenação dos pacientes; basta a ordem de chegada.
• Indiferente. A fila é claramente a mais adequada.

Lista duplamente ligada. A inversão pode ser feita em $O(n)$ trocando, em cada nó, os ponteiros next e prev (a lista passa a ser percorrida no sentido contrário).

Numa lista duplamente ligada cada nó conhece o anterior e o seguinte, pelo que a inversão é uma troca local de ponteiros em todos os nós, em tempo linear, e a estrutura suporta naturalmente o percurso nos dois sentidos. Numa lista simplesmente ligada também é possível inverter em $O(n)$ re-ligando os nós, mas a lista duplamente ligada é a opção mais adequada quando essa operação é frequente. O custo é um ponteiro extra por nó.

É indiferente.

A ordenação por seleção percorre, em cada passo, todos os elementos que faltam para encontrar o mínimo e trocá-lo com a primeira posição livre. Esse número de comparações é sempre da ordem de $n^2$, independentemente de o vetor já estar ordenado ou não.

• O vetor está ordenado por ordem decrescente. A ordenação por seleção não tira partido de nenhuma ordenação prévia.
• O vetor está ordenado por ordem crescente. Mesmo já estando ordenado, o algoritmo continua a procurar o mínimo em cada passo.
• O vetor está desordenado. O estado inicial não altera o número de comparações.
• O vetor está ordenado (por ordem crescente ou decrescente). Nenhuma ordenação prévia reduz o trabalho do selection sort.
• É indiferente. O selection sort faz sempre $\Theta(n^2)$ comparações, qualquer que seja o estado inicial do vetor.

$O(n\log n)$.

Dividir em três partes dá a recorrência $T(n)=3T(n/3)+cn$. Pelo teorema mestre (ou somando os níveis da árvore de recursão), cada nível custa $O(n)$ e há $O(\log n)$ níveis, pelo que $T(n)=O(n\log n)$. A base do logaritmo altera apenas a constante.

• $O(n)$. Há trabalho linear por nível de recursão, mas existem vários níveis.
• $O(n\log n)$. A recorrência $T(n)=3T(n/3)+O(n)$ resolve-se em $O(n\log n)$ (a base do logaritmo muda, mas não a classe de crescimento).
• $O(n^2)$. Não há ciclos aninhados proporcionais a $n$.
• $O(n^3)$. Muito acima do custo real.
• Nenhuma das anteriores. Há uma resposta correta.

O pivot foi 10.

Depois de um passo de partição, o pivot fica na sua posição definitiva: à sua esquerda só há valores menores e à sua direita só há valores maiores. No vetor dado, isso acontece com o 10 (esquerda: 5, 1, 7, 3; direita: 12, 20, 11, 15).

• 7. Há elementos maiores que 7 à sua direita na configuração dada (10, 12, 20, 11, 15), logo 7 não ficou na posição final.
• 5. O primeiro elemento foi o pivot inicial, mas a configuração dada já é a do fim do passo.
• 10. Todos os elementos à esquerda de 10 são menores que 10 e todos os à direita são maiores: 10 é o pivot colocado na posição final.
• 15. Há elementos menores que 15 à sua direita (11), logo não está na posição final.
• Nenhuma das anteriores. O pivot está identificado.

O pivot foi 17.

Após a partição, o pivot fica na posição correta: $[3, 9, 1, 8 \,|\, 17 \,|\, 24, 22, 20]$. Todos os elementos à esquerda de 17 são menores que 17 e todos os à direita são maiores, confirmando que 17 foi o pivot.

• 17. À esquerda de 17 estão apenas valores menores (3, 9, 1, 8) e à direita apenas valores maiores (24, 22, 20): 17 é o pivot.
• 8. Há valores maiores que 8 à esquerda de 8 na configuração final (9).
• 24. Há valores menores que 24 à direita (22, 20).
• 1. O elemento 1 não está na posição de partição.
• Nenhuma das anteriores. O pivot está identificado.

$O(n^2)$.

Com pesquisa binária, localizar a posição de inserção passa a custar $O(\log k)$ em vez de $O(k)$. Porém, depois de encontrada a posição, é necessário deslocar os elementos maiores para abrir espaço, o que custa $O(k)$ em cada inserção. Somando sobre todas as inserções, o custo dominante continua a ser $O(n^2)$.

• $O(n\log n)$. A pesquisa binária reduz o número de comparações, mas não o número de deslocamentos.
• $O(n)$. O algoritmo continua a deslocar elementos em cada inserção.
• $O(\log n)$. Cada inserção individual não é de tempo constante.
• $O(n^2)$. Encontrar a posição custa $O(\log k)$ com pesquisa binária, mas inserir o elemento desloca em média $k/2$ elementos: o total continua $O(n^2)$.
• Nenhuma das anteriores. Há uma resposta correta.

Quando $X$ é o primeiro elemento do vetor.

A pesquisa sequencial compara os elementos pela ordem, pelo que encontra o primeiro elemento com uma única comparação. A pesquisa binária, qualquer que seja a posição de $X$, realiza sempre cerca de $\log_2 n$ comparações. Assim, só quando $X$ está no início (ou muito próximo dele) a sequencial pode ser mais rápida.

• O elemento $X$ não existe no vetor. Se $X$ não existe, a sequencial percorre o vetor todo ($O(n)$), enquanto a binária termina em $O(\log n)$.
• O elemento $X$ é o primeiro elemento do vetor. A sequencial encontra $X$ na primeira comparação ($O(1)$), ao passo que a binária precisa de cerca de $\log n$ comparações.
• O elemento $X$ encontra-se no meio do vetor. No meio, a binária encontra $X$ em poucas comparações; a sequencial precisa de cerca de $n/2$.
• Nunca. Há situações em que a sequencial é mais rápida.
• Sempre. No caso geral a binária é muito mais rápida.

$O(n)$.

Numa lista ligada (simples ou dupla) não existe acesso indexado em $O(1)$ ao elemento central, condição necessária para a pesquisa binária. O melhor algoritmo é a pesquisa sequencial, que no pior caso percorre todos os $n$ nós: $O(n)$.

• $O(n)$. Numa lista ligada não há acesso direto ao elemento do meio, pelo que a pesquisa binária não é eficiente; a pesquisa sequencial é $O(n)$.
• $O(\log n)$. A pesquisa binária exige acesso em $O(1)$ a qualquer posição, o que uma lista ligada não oferece.
• $O(1)$. Não é possível aceder diretamente a um elemento arbitrário.
• $O(n\log n)$. É pior do que o custo real da pesquisa sequencial.
• Nenhuma das anteriores. Há uma resposta correta.

Cerca de 3 minutos ($\sqrt{1000}/\sqrt{100}=\sqrt{10}\approx 3{,}16$ minutos).

Como o tempo é proporcional a $N^{1/2}$, passar de $N=100$ para $N=1000$ multiplica o tempo por $\sqrt{1000}/\sqrt{100}=\sqrt{10}\approx 3{,}16$. Logo o tempo rondará os $3{,}16$ minutos, ou seja, cerca de 3 minutos.

$O(\log n)$.

O ciclo repete-se enquanto $n>1$, dividindo $n$ por 2 em cada passo: $n, n/2, n/4, \dots, 1$. O número de iterações é, portanto, aproximadamente $\log_2 n$, pelo que a complexidade é $O(\log n)$.

• $O(n\log n)$. Não há dois fatores que cresçam ambos com $n$.
• $O(n)$. O valor de $n$ não diminui um número constante de vezes; antes é dividido por 2.
• $O(\log n)$. Em cada iteração $n$ passa a metade, pelo que o ciclo corre cerca de $\log_2 n$ vezes.
• $O(n^2)$. Muito acima do número real de iterações.
• Nenhuma das anteriores. Há uma resposta correta.

Listas são geralmente mais eficientes que vetores nas operações de inserção e remoção

Numa list, inserir ou remover um elemento numa posição conhecida é apenas uma religação de ponteiros, em $O(1)$. Num vector, essas operações de inserção e remoção no meio do vetor obrigam a deslocar todos os elementos seguintes, em $O(n)$. O vetor continua vantajoso no acesso por índice ($O(1)$) e na pesquisa binária.

• Vetores e listas são igualmente eficientes nas operações de inserção e remoção. Inserir ou remover no meio de um vetor exige deslocar elementos ($O(n)$).
• Listas são geralmente mais eficientes que vetores nas operações de inserção e remoção. Numa lista, basta religar ponteiros ($O(1)$ conhecida a posição); num vetor é preciso deslocar todos os elementos seguintes ($O(n)$).
• Vetores são geralmente mais eficientes do que listas nas operações de inserção e remoção. O acesso por índice torna o vetor melhor na pesquisa, não na inserção/remoção no meio.
• Listas são geralmente mais eficientes que vetores na inserção, mas não na remoção. A remoção numa lista também é $O(1)$ conhecida a posição.
• Nenhuma das anteriores. Há uma resposta correta.