Estrutura de Dados UN-2

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Exercícios Estrutura de Dados (Unidade 3)
1. Existem diferentes estrutu ras de dados que podem ser usadas para estruturar algoritmos que resolvam problemas relacionados a containers de dados, e a escolha d e qual usar depende d o problema a ser resolvi do. Entre as opções a seguir, qual delas melhor define uma deque?
R. Uma estrutura com inserção/exclusão possível nos extremos frontal e traseiro da fila
2. Usando a biblioteca Collections, é possível aproveitar alguns métodos já prontos para a manipu lação de d eques. Após executar o código abaixo, qual seria o resultado esperado na impressão? import col lections d = collections.deque('abcd') d.appendleft('d') print (d)
R.Inclusão do ‘d’ à esquerda. 
3. Entre os métodos já implementados n a biblioteca Coll ections, estão método s para remoção do s elementos em uma deque. Consi dere que in icializamos uma deque da seguinte forma: d = collections.deque('6598732') Qual comando utilizamos para remover o elemento 2? 
R. d.pop().
4. A linguagem d e prog ramação Python facilita a manipulação de estruturas de dados a partir do uso de bi bliotecas com comando s que, em poucas li nhas, ajudam a inserir, remover, fazer consultas, entre outras funcionali dades. Utilizando a biblioteca Collections, qual seria a deq ue resultante da seguinte sequência de operações? import col lections d = collections.deque() .extend('abcd') d.pop() d.append('j') d.appendleft('z') d.pop() print (d) 
R. deque(['z', 'a', 'b', 'c'])
5. A computação simula o mundo real, criand o ambientes e estruturas baseados no funcionamento de processos já existentes no di a a dia. Qual dos seguin tes cenários do mundo real v ocê associaria a uma estrutu ra de dados do tipo deque? 
R. Check-in de embarque em um voo nacional.
6. A busca sequencial é uma técnica simples e intuitiva para buscar elementos em vetores ou listas. Tendo a informação de que os d ados estão ordenados de forma crescente, qual otimização você pode aplicar na busca sequencial?
R. Parar a execução e informar que o valor não existe, quando o v alor atual for maior que o buscado
7. A busca binária é uma técnica eficiente p ara buscar elementos em vetores ou listas. A ú nica restrição desse método é qu e o vetor ou a lista estejam ordenados. Das seguintes sequências de acessos em um vetor, qu al é váli da em uma execução d e busca binária? 
R. 5, 2, 1.
8. Tabelas h ash são estruturas muito eficientes utilizadas por diversas linguagens de programação e serviços. Entender seu funcionamento é crucial para o desenvolvedor, o qual deverá decidir o tamanho d a tabela e a função h ash que otimiza o desempenho de determinada aplicação. Considere uma tabela hash de 5 posições (de 1 a 5, aceitando repetições) e uma função hash q ue representa a i-ésima letra do alfabeto com o número i. Quantas colisões ocorrem após a inserção das chaves: A, B, A, C, A, E ? 
 
R. 2. 
9. Método s de busca são muito uti lizados em milhares d e sistemas e aplicações reais. O proj etista e o desenvolvedor devem ter muito con hecimento sobre seu funcion amento e também sobre as vantagens e de svantagens de cada método . Para uma apl icação qu e realiza mui tas in serções e atuali zações nos dados, qual é o método mais indicado? 
R. Tabela hash implementada com vetores e listas para tratar colisões
10. Uma das maneiras de avaliar o melhor método para uma aplicação é analisar a complexidade de pior e melhor caso dos método s e constatar com as entradas da aplicação-alvo. Para tanto, é necessário conhecimento sobre ordens assintóticas. Nesse sentido, qual é a complexidade de pior caso das buscas sequencial, binária e na tabela hash, respectivamente? 
R. O(n), O(log2 n), O(K)
11. O algoritmo de o rdenação p or bo lha é o mais simples e in tuitivo. O seu funcion amento se b aseia em comparar todo s os elementos, dois a d ois, do inicio ao fi m da lista ou vetor. Essa op eração é re petida enq uanto ocorrerem trocas entre elementos. Dado o vetor [22, 11, 7, 46, 29], após duas rodadas de execução d o algoritmo de ordenação por bo lha, ordenando de forma decrescente, qual será o estado do vetor? 
R. 22, 46, 29, 11, 7
12. A ideia principal do algoritmo d e ordenação por inserção é como em u m j ogo de cartas. Qu ando você recebe uma no va carta, já o rdena ela d e alguma maneira. Vamos assumir q ue v ocê está jog ando cartas e tem a seguinte l ista de cartas na mão: [Q, J, Q, J]. 
Quantas trocas serão feitas caso v ocê ordene as cartas de forma ascendente, baseando-se no alg oritmo de ordenação por inserção? 
R. 3
13. A ordenação po r seleção busca o menor elemento da parte não ordenada do vetor em cada iteração e o coloca na sua posição co rreta. Quantas comparações e trocas são necessárias para ordenar o vetor [1, 5, 3, 9, 6] de forma crescente? 
R. 10 e 2.
14. Você foi contratado como consultor por uma empresa de desenvo lvimento de sistemas. Um dos cli entes solicitou o desenvolvimento de uma nova funcion alidade que p ermite ordenar os clientes p or idade e renda. Essa funcion alidade será util izada diversas v ezes ao dia, o qu e indica que após uma ordenação, as outras só serão necessárias caso atualizações tenham sido feitas no banco de dados. Quantas comparações serão feitas pelo algoritmo de ordenação p or b olha, caso a entrada s eja uma lista de 10 elementos já ordenados? 
R. 9
15. Uma das maneiras de avaliar o melhor algoritmo de o rdenação para determinada aplicação é an alisando a sua complexidade de tempo. Você foi contratado para fazer essa análise. A primeira per gunta qu e seu chefe fez foi qual seria a complexidade de melhor e pior caso do alg oritmo d e ordenação em seleção, caso ele fosse executado M vezes consecutivas. O qu e você responderia? 
R. O(M * N2) e O(M * N2). 
16. O algoritmo de o rdenação rápida uti liza um pivô para recursiv amente ordenar o vetor. Em cada chamada d a fu nção d e p artição, os elementos meno res q ue o pivô são colo cados na esquerda e os maiores que o pivô na direita. Essa operação é repetida até que reste apenas um elemento . Dado o vetor [13, 87, 63, 91, 55] e o pivô 55, qu al das o pções a seguir é válida após a primeira execução da fu nção partição?
R. [13, 55, 63, 91, 87].
17. A complexidade de tempo de melhor caso da ordenação rápida ocorre quando o elemento escolhido como pivô divide o vetor exatamente ao meio. No exemplo [M, Q, S, I , B], qual elemento escolhido como pivô resultaria no melhor caso de execução d a ordenação rápida? 
R. M
18. A ordenação por mistura ordena, de forma recursiva, sequências a partir de subsequências j á ordenadas. Na fase de di visão, o s elementos são recursivamente d ivididos. 
Dado o v etor [7, 4, 9, 5, 1], quantas chamadas recursivas serão feitas na fase de divisão?
R. 8
19. O melhor e o pior caso da ordenação por mistura é o mesmo, O(n log2 n). Dado um v etor to talmente desordenado [8, 7, 6, 5, 4, 3, 2, 1], qual será o estado d o vetor após duas execuções da função merge?
R. [7, 8, 5, 6, 4, 3, 2, 1].
20. A i mplementação dos algoritmos eficientes tem como base a técnica de divisão e conquista. Em ambas as ordenações, por mistura e rápida, o ponto -chave é a complexidade de tempo das funções de partição e de merge. Qual é a complexidade de tempo dessas fu nções quando executadas N vezes para um vetor de N posições? 
R. O(N2)