Faculdade

Estrutura de Dados - 1o. per´ ıodo de 2013 Primeira Avalia¸˜o ` Distˆncia ca a a 1. (1,0) Classifique as seguintes fun¸˜es em ordem crescente de complexidade assint´tica: co o √ 2 1/3 n 3 5 3 2 n, n log n, n , n + log n, log n, (1/3) , n, n − n + 7n , n , (log n) , n/ log n, (3/2)n , 2n , n! , log log n, 6. 2. (1,5) Para cada item abaixo, responda “certo”, “errado” ou “nada se pode concluir”. Justifique. a. Se um limite inferior para um problema P ´ n2 , ent˜o existe um algoritmo ´timo e a o 2 para P de complexidade de pior caso O(n ). b. Se um limite inferior para um problema P ´ n2 , ent˜o nenhum algoritmo ´timo para e a o P pode ter complexidade de pior caso O(n log n). c. Se um limite inferior para um problema P ´ n2 , ent˜o todo algoritmo ´timo para P e a o 2 tem complexidade de pior caso Ω(n ). 3. (1,5) Determinar a complexidade m´dia de uma busca n˜o ordenada de 10 chaves, em e a e c que a probabilidade de busca da chave i ´ igual a um ter¸o da probabilidade de busca da chave i − 1, para i = 2, ...10. Supor, ainda, que a probabilidade de a chave procurada se encontrar na lista ´ igual a 50%. e 4. (1,5) Sejam L1 e L2 duas listas ordenadas, simplesmente encadeadas com n´-cabe¸a. o c Apresentar um algoritmo que construa uma lista ordenada contendo os elementos que pertencem exclusivamente a L1 ou exclusivamente a L2 (isto ´, os elementos que pertencem e a ambas as listas devem ser descartados). 5. (1,0) Adapte o m´todo iterativo de ordena¸˜o por bolha, tornando-o recursivo. e ca 6. (1,5) Escreva um algoritmo eficiente que verifique se uma cadeia de caracteres ´ da forma e xCx, onde x ´ uma cadeia qualquer formada por caracteres A ou B. Dica: utilize uma e fila auxiliar. 7. (1,0) O percurso em altura de uma ´rvore bin´ria ´ aquele em que os n´s s˜o dispostos em a a e o a ordem n˜o decrescente de suas alturas. Descrever um algoritmo para efetuar um percurso a em altura de uma ´rvore bin´ria. a a 8. (1,0) Prove ou desprove a seguinte afirma¸˜o: Em toda ´rvore