# Exercícios MT2 Questões de exames antigos de Algoritmos e Estruturas de Dados, com resolução. Página: https://resumos.rgo.pt/cadeiras/aed/exercicios-mt2/ ## Estruturas lineares Estrutura para procurar um elemento ou o imediatamente anterior Teste 2, 2018/19 Qual é a estrutura de dados linear mais adequada (eficiente em tempo e espaço) quando se pretende procurar, num conjunto de elementos, um determinado elemento $X$ ou, no caso deste não existir, o imediatamente anterior? Solução 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. Estrutura para o botão "voltar" de um browser Teste 2, 2018/19 Qualquer browser possui a funcionalidade de retorno à página visitada anteriormente. Na implementação desta funcionalidade, que estrutura de dados é mais adequada (eficiente em tempo e espaço)? Solução 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. Operações em O(1) numa lista simplesmente ligada com referências para o início e o fim Teste 2, 2018/19 Considere uma lista implementada por uma lista simplesmente ligada com referências para o início e o fim (primeiro e último nó). Quais destas operações podem ser realizadas em tempo $O(1)$? I. Inserir um elemento no início da lista II. Inserir um elemento no fim da lista III. Remover o primeiro elemento (início) da lista IV. Remover o último elemento (fim) da lista Solução 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)$. Estrutura para encaixotar itens pela ordem temporal da encomenda Teste 2, 2018/19 No fim do processo produtivo de uma fábrica, todos os itens (objetos da classe `Item`) são encaixotados para envio aos clientes, respeitando a ordem temporal da encomenda. Que estrutura melhor representa este cenário? Solução `queue>`. 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>`.** O vetor não garante a disciplina FIFO de expedição das encomendas. * **`list>`.** A lista não retira primeiro a encomenda mais antiga. * **`queue>`.** A fila processa as encomendas por ordem de chegada (FIFO) e cada encomenda é uma pilha de itens encaixotados. * **`stack>`.** 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. O que testa a função mistério sobre uma fila? Teste 2, 2018/19 A função `misterio` retorna verdadeiro se: ```cpp template bool misterio(queue &f1) { stack s1; int k = f1.size()/2; for (int i = 1; i <= k; i++) { s1.push(f1.front()); f1.pop(); } if (f1.size() > k) f1.pop(); for (int i = 1; i <= k; i++) { if (f1.front() != s1.top()) return false; f1.pop(); s1.pop(); } return true; } ``` Solução 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. Gestão de pacientes para recolha de sangue Teste 2, 2017/18 Qual é a estrutura de dados mais adequada na gestão de pacientes de um laboratório de análises, que vão efetuar a recolha de sangue num determinado dia? Solução 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 mais adequada quando a inversão é frequente Teste 2, 2018/19 Numa aplicação que usa uma lista ligada para guardar os elementos, a operação de inversão da lista é frequente. Que implementação de lista é mais adequada (eficiente em tempo e espaço): lista simplesmente ligada ou lista duplamente ligada? Explique. Solução 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ó. Confere a tua resposta: * A resposta escolhe a lista duplamente ligada. * A justificação indica que a inversão se faz em $O(n)$ trocando os ponteiros de cada nó (ou percorrendo a lista nos dois sentidos). * A justificação compara com o custo espacial da lista simplesmente ligada. ## Ordenação Ordenação por seleção consoante o estado inicial do vetor Teste 2, 2016/17 Usando o algoritmo de ordenação por seleção, pretende-se ordenar um vetor por ordem crescente. Em qual destas situações a ordenação do vetor é realizada em menor tempo? Solução É 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. Complexidade do merge sort com divisão em três partes Teste 2, 2016/17 O algoritmo merge sort divide o vetor em duas partes de igual tamanho, que ordena recursivamente. Se o algoritmo dividisse o vetor em três partes de igual tamanho, qual seria a complexidade temporal? Solução $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. Pivot usado num passo de partição do quick sort Teste 2, 2016/17 No quick sort, após um passo de partição, o vetor apresenta a configuração $[5, 1, 7, 3, 10, 12, 20, 11, 15]$. Qual foi o elemento pivot usado nesse passo? Solução 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. Pivot do quick sort após o primeiro passo Teste 2 (CI2), 2015/16 Estava a verificar a implementação do quick sort que ordena um vetor por ordem ascendente. Após o primeiro passo, o conteúdo do vetor é $[3, 9, 1, 8, 17, 24, 22, 20]$. Qual foi o pivot usado nesse passo? Solução 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. Complexidade do insertion sort com pesquisa binária Teste 2 (CI2), 2015/16 O insertion sort mantém os primeiros $k$ elementos ordenados e insere o elemento $k+1$ na posição correta, usando pesquisa sequencial nessa procura. Se uma variante usar pesquisa binária nesse passo, qual é a complexidade temporal do algoritmo resultante? Solução $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. ## Pesquisa Quando a pesquisa sequencial vence a binária Teste 2, 2016/17 Considere a pesquisa de um elemento $X$ num vetor ordenado. Em que situação a pesquisa sequencial é realizada em menor tempo que a pesquisa binária? Solução 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. Pesquisa numa lista duplamente ligada ordenada Teste 2, 2016/17 Uma lista duplamente ligada mantém os elementos ordenados por ordem crescente. Usando o algoritmo de pesquisa mais adequado para essa lista, qual é a complexidade temporal da operação de pesquisa? Solução $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. ## Complexidade Tempo de execução de um algoritmo O(N^1/2) para N=1000 Teste 2 (CI2), 2015/16 Suponha um algoritmo de complexidade temporal $O(N^{1/2})$. Para $N=100$, o seu tempo de execução é de 1 minuto. Qual é o tempo aproximado de execução para $N=1000$? Solução 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. Confere a tua resposta: * A resposta usa a proporcionalidade com $\sqrt{N}$. * A resposta indica cerca de 3 minutos ($\sqrt{10}\approx 3{,}16$ minutos). Complexidade da função methodX Teste 2 (CI2), 2015/16 Indique a complexidade temporal da função: ```cpp int methodX(int n) { int s = 0; while (n > 1) { n = n/2; s++; } return s; } ``` Solução $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. Vetores e listas da STL em inserções e remoções Teste 2, 2017/18 Considere as implementações de vetores (`vector`) e listas (`list`) da STL. Sobre a eficiência temporal, o que é correto afirmar sobre as operações de inserção e remoção? Solução 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.