Buscar

estruturas de dados em python

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 3, do total de 7 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 6, do total de 7 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Prévia do material em texto

Uma das formas de implementar a multiplicação de dois números inteiros em um computador é reduzi-la a um 
problema de soma repetida. Por exemplo, 4×3 pode ser representado como 3+3+3+3. Considerando que a 
soma de dois números inteiros é uma operação unitária de tempo T, qual é a complexidade de melhor caso da 
multiplicação de dois números �×�, sendo �≤�? 
(a-1)T 
Como o número �―― é menor ou igual a �, a operação de melhor caso será somar � cópias de � entre si. 
Isso corresponde a (�−1) operações de soma de dois números inteiros, cada uma levando � de tempo. 
Portanto, a resposta correta é (�−1)�. Tomando como exemplo 4×8, pode-se resolver como 8+8+8+8, sendo 
assim três operações de soma. 
 
Uma função recursiva é aquela que se utiliza de chamadas a si mesma para solução de um problema. Entre os problemas a 
seguir, qual pode ser resolvido de forma recursiva? 
Verificar se o numero e palíndromo ( e igual quando lido da esquerda para direita e vice-versa) 
Para que um número seja palíndromo, o primeiro algarismo precisa ser igual ao último, o segundo igual ao penúltimo, e assim 
por diante. Você pode criar uma função que compara os dois extremos e depois chama a si mesmo, excluindo os dois 
algarismos extremos. Se todas as comparações forem verdadeiras, o número é palíndromo. 
Uma das formas de utilizar arrays em Python é o uso de list. Essa estrutura permite que você represente um vetor de três 
dimensões como uma única variável vetor. Qual é a opção que representa a forma correta de somar o valor de todas as 
dimensões de um vetor? 
soma=0 
For x in vetor: 
soma=soma+x 
A lista, quando usada para representar o array, pode ser iterada usando a estrutura “for x in vetor:”, representando uma ação 
posterior que será repetida para cada elemento x presente na lista vetor. Assim, o acumulador soma é inicializado com o valor 
0 e a ele é adicionado o valor de cada dimensão do vetor no laço iterativo “for... in … :”. 
 
O produto interno de dois vetores é calculado pelo somatório dos produtos par a par do valor de cada dimensão desses 
vetores. (�⋅�=�1�1+�2�2+…+����, para dois vetores de � dimensões). Qual das opções a seguir apresenta um 
procedimento para calcular o produto interno de dois vetores � e � (variável prod), já salvos como arrays em Python, usando 
a biblioteca numpy? 
prod=0 
for indice,item in enumerate(a): 
prod=prod+(a[indice]*b[indice]) 
A diagonal principal de uma matriz é o conjunto de elementos cujo índice de coluna é igual ao índice da linha. Assumindo que 
temos uma matriz quadrada salva como array na variável matriz, o código que imprime corretamente os elementos da 
diagonal principal é: 
For indice, valor in enumerate(matriz): 
Print (matriz[indice][indice]) 
 
O uso de enumerate permite controle dos índices da matriz para poder imprimir apenas os valores da diagonal principal (onde 
o índice da linha é o mesmo da coluna). 
 
 
Um array de 3 dimensões foi declarado com a linha: 
matriz =[[[1,2,3],[4,5,6],[7,8,9]],[[10,11],[12,13]],[[14,15]]] 
Para imprimir o valor de 10, o código correto é: 
Print(matriz[1][0][0]) 
O primeiro índice seleciona, na primeira dimensão matriz[1], o conjunto de 2 elementos ([10,11] e [12,13]). Na segunda 
dimensão, você escolhe entre esses elementos. Matriz[1][0] seleciona o par (10,11). Por fim, o terceiro índice seleciona entre 
esses dois. Matriz[1][0[0] seleciona o valor 10. 
 
O algoritmo bubblesort serve para resolver o problema de ordenação. Quanto a esse algoritmo, é correto afirmar que as suas 
complexidades de melhor e pior caso são, respectivamente, 
0(n) e 0(n2) 
A complexidade de melhor caso acontece com a lista de entrada já ordenada, caso no qual o algoritmo realiza apenas uma 
passagem comparando os valores consecutivos par a par. Isso se concretiza em complexidade linear ou 0(n). Já no pior caso, 
a lista precisa ser totalmente invertida, necessitando de n passagens e somatório de 1 a (n−1) trocas, o que resulta em uma 
complexidade quadrática, ou 0 (N2) 
O algoritmo bubblesort é executado em diversas passagens pela sequência desordenada, realizando trocas em 
elementos vizinhos, quando necessário. Com o objetivo de terminar com uma sequência em ordem crescente e 
uma sequência de entrada após a realização da primeira passagem do algoritmo, a sequência parcial é 
[12,22,23,4,25,30] 
 
O algoritmo bubblesort percorre a lista, comparando elementos par a par e trocando quando necessário. Na 
primeira passagem, 12 e 25 não precisa de troca, 25 por 22 há troca, 25 por 23 há troca, 25 por 4 há troca, e 25 
por 30 não há troca. Desse jeito, a lista termina parcialmente como [12,22,23,4,25,30]. 
Uma das formas de implementar uma lista linear é a alocação contígua. Podemos dizer que os elementos desse 
tipo de lista estão sempre 
Sequencialmente em memoria 
Como a alocação contígua reserva um espaço sequencial de memória para armazenar uma lista, os seus 
elementos estarão sempre sequencialmente em memória, ordenados ou não. 
Uma lista em alocação contígua contém n nós representando filmes, cada nó com os campos: chave, nome, 
data_de_lançamento. Essa lista é mantida ordenada pelo campo chave, em ordem crescente. A complexidade de 
pior caso da inserção de um elemento na lista é 
0(N). 
Para que um nó seja inserido, a posição correta deve ser buscada, levando x operações de comparação. Depois, todos os nós 
seguintes deverão ser empurrados em uma posição para abrir espaço para a inserção. Isso leva n−x atribuições. Portanto, 
somando, teremos n operações e, assim, a complexidade é 0(n). 
 
 
 
Quando utilizamos uma estrutura encadeada, os nós possuem ponteiros para outros nós. Em uma lista 
simplesmente encadeada, há apenas uma ligação entre os nós. Para garantir que a lista permaneça funcional ao 
remover um nó, você deve seguir quais passos? 
Apontar o ponteiro do no anterior ao removido para o no seguinte removido 
A remoção de um nó se dá fazendo com que o ponteiro do nó anterior a ele aponte para outro nó. Para não 
perder o encadeamento da lista, o ponteiro do nó anterior tem que apontar para o nó seguinte ao nó removido. 
 
Você possui uma lista ordenada, em ordem crescente de chaves, simplesmente encadeada, com cada nó da 
lista apontando para o seguinte. Nessa configuração, você pode apenas percorrer a lista em ordem crescente 
das chaves. Para que possa percorrer a lista em ordem decrescente, você pode utilizar as seguintes alterações 
Fazer o encadeamento duplo e manter variável guardando o ultimo no 
Com o uso da variável armazenando o último nó, você consegue iniciar o percurso da lista de trás para frente. 
Somando a isso o uso de encadeamento duplo, você consegue percorrer a lista de trás para frente, no sentido 
em que as chaves estarão ordenadas em ordem decrescente. 
 
A estrutura de dados de pilha é muito utilizada para programas de análise sintática. As suas complexidades de 
inserção, remoção e busca são, respectivamente 
0(1),0(1) e 0(n). 
A inserção só pode ocorrer no topo da pilha e leva tempo constante, ou 0(1). Da mesma forma, a remoção só pode ocorrer no 
topo da pilha, sendo 0(1). Já a busca necessita percorrer a pilha e, portanto, no pior caso, leva tempo 0(n). 
Você está utilizando uma estrutura de dados de fila em seu programa. Em determinado momento da execução, a fila 
apresenta a seguinte estrutura, representada pelas suas chaves: [5,11,15,20,25,36]. O nó de chave 5 é o início da estrutura. Os 
próximos três nós a serem consumidos são os nós de chave 
5,11,15 
A estrutura de fila só permite remoções no seu início. Portanto, as três remoções 
serão 5, 11 e 15. 
Uma lista circular duplamente encadeada é uma estrutura de dados que possui como principal característica 
Ausência de ponteiros nulos 
O fato de a lista ser duplamente encadeada permite que o percurso seja feito em ambos os sentidos: as 
operações de inserção e remoção são lineares. A característica principal da lista circular é que osponteiros 
sempre apontam para outros nós, nunca para ponteiros nulos. O último nó tem seu ponteiro próximo apontando 
para o nó inicial da lista. O ponteiro anterior do nó inicial, por sua vez, aponta para o último nó. 
Em um jogo digital, você quer implementar um elemento de uma máquina caça-níqueis, que mostra um número 
selecionado de um conjunto fixo de números a cada vez que um botão é apertado. Uma vez definida a ordem 
desses números, ela não mais se altera, não sendo possível inserir ou remover números, como se estes 
estivessem dispostos sobre o perímetro de um disco. Para implementar esse elemento, a estrutura ideal é 
Uma lista circular 
Como a sequência de números é fixa, e não são inseridos ou removidos números, o uso de pilhas, filas ou 
deques não é justificado, pois sua grande vantagem é a baixa complexidade nas inserções e remoções. Já a 
lista circular permite que diversos números sejam gerados de forma repetida, sem a necessidade de recomeçar 
do início da lista a cada aperto do botão. Portanto, a estrutura ideal é a lista circular. 
 
 
 
Assinale a alternativa correta acerca das estruturas de dados árvores e árvores binárias. 
Ao acessar uma arvore, deve-se acessar pela referência a sua raiz 
Representa-se uma árvore em memória por meio de alocação dinâmica. A árvore não é representada como um 
todo, mas uma referência para sua raiz, que guarda a chave (dado) e uma referência para a raiz das subárvores 
esquerda e direita. 
 
Considerando que a seguinte árvore é binária, assinale a alternativa correta. 
 
A quantidade de folhas da arvore e 4 
ou seja, são aqueles nós que possuem grau zero. 
 
Analise as imagens a seguir e assinale a letra da imagem que contém uma árvore binária de busca. 
 
 
Imagem c 
Em uma árvore binária de busca, os nós contidos na subárvore esquerda devem ser 
menores que a raiz e maiores na direita. Isso vale para todos os nós. 
Tomando como base os conceitos de busca, inserção e remoção em estruturas de dados, é correto afirmar que 
Em todas as estruturas de dados nas quais se realiza busca, inserção e remoção não são admitidas duplicidade de chaves 
isso também inclui as arvores binarias de busca 
Em uma árvore binária de busca, por definição, não são admitidas chaves em duplicidade. 
 
 
Dada a árvore a seguir, identifique o percurso em ordem simétrica: 
23,24,26,29,28,27,25 
O percurso é definido pela recursão: percorrer recursivamente à esquerda, visitar a raiz e percorrer recursivamente à direita da 
raiz considerada. 
Dada a árvore a seguir, identifique o percurso em pré-ordem: 
 
25,24,23,27,26,28,29 
O percurso é definido pela recursão, visita à raiz e percorrer recursivamente esquerda e direita da raiz considerada. 
 
Dada a árvore de expressões aritméticas a seguir, identifique, respectivamente, o percurso prefixo e pós-fixo: 
 
*+ABC/AB+C* 
O percurso prefixo é definido por raiz-esquerda-direita, o resultado é *+ABC; o 
percurso pós-fixo é definido por esquerda-direita-raiz e o resultado do percurso é 
AB+C*. 
Considere a seguinte expressão aritmética infixa A + B + C + D. A sua representação 
prefixa e pós-fixa, respectivamente, é: 
+++ABCD E AB+C+D+ 
O percurso prefixo é definido por raiz-esquerda-direita, o resultado é + + + A B C D; o percurso pós-fixo é definido por esquerda-
direita-raiz e o resultado do percurso é A B + C + D +. 
Marque a opção correta sobre árvores balanceadas: 
Toda árvore balanceada tem altura proporcional a log⁡N. 
 
Considerando que a seguinte árvore é binária, assinale a opção correta. 
A quantidade de folhas da arvore e 4 
, ou seja, são aqueles nós que possuem grau zero. 
Marque a opção correta relativa à inserção de uma nova chave em uma árvore AVL. 
Podemos sempre afirma que, após a aplicação de uma rotação, a altura da arvore avl e igual a altura da arvore 
antes da inserção da nova chave 
Após a rotação, a altura da subárvore que sofreu a alteração é preservada mesmo após sofrer rotação. Ou seja, isso 
corresponde à altura da árvore original antes da inserção da nova chave. 
Marque a opção correta sobre a remoção de um nó de uma árvore AVL. 
O pior caso da remoção de um no de uma arvore avl e a remoção da folha menos profunda de uma arvore de 
Fibonacci. Nesse caso, temos que fazer todas as rotações, do pai do no removido até a raiz. 
Uma das formas mais complicadas da remoção de um nó de uma árvore AVL é quando se remove a folha 
menos profunda de uma árvore de Fibonacci. Nesse caso, precisamos fazer todas as rotações, do pai do nó 
removido até a raiz. 
 
As árvores B são uma generalização das árvores binárias. Seus nós (chamados de página nas árvores B) podem carregar mais 
de uma chave e essa característica é conveniente, uma vez que 
As arvores b podem ser representadas tanto em memoria principal quanto em memoria secundaria porem a organização em 
paginas viabiliza o minimo desperdicio em alocação de espaço em memoria secundaria 
A opção "A" está errada, uma vez que a complexidade das operações citadas é O(log n). " B" e "C" estão erradas, pois as 
árvores B podem ser representadas tanto em memória principal quanto em secundária. "D" está correta pela característica da 
forma com que os blocos são alocados em memória secundária, normalmente em múltiplos de 512 bytes, sendo as páginas 
mais bem acomodadas nos blocos. "E" também está incorreta, uma vez que as árvores binárias têm grande desperdício de 
memória caso sejam representadas em memória secundária. 
Em uma árvore B, temos que: 
(i) Cada nó contém no mínimo m registros (m+1 descendentes) e no máximo 2m registros (e 2m+1 descendentes), exceto o 
nó raiz, que pode conter entre 1 e 2m registros. 
(ii) Todos os nós folhas aparecem no mesmo nível. 
Sobre árvores B, é correto afirmar: 
 
O particionamento de nós em uma árvore B ocorre quando um registro precisa ser inserido em um nó com 2m registros. 
Para a inserção de um registro, é necessário inserir um nó com 2m registros e ao mesmo tempo ocorre o particionamento de 
nós em uma árvore B. 
 
Marque a opção que apresenta corretamente a complexidade de espaço de execução do módulo sbbst: 
0(N) 
 
Sobre as classes de funções módulo sbbst, sejam as seguintes afirmativas: 
I. A classe sbbst. getMinVal () possui complexidade de tempo 0(log⁡N). 
II. A classe sbbst.kthsmallest (K) sempre retorna o maior elemento de uma árvore binária, balanceada ou 
não, independentemente do valor do parâmetro enviado. 
III. A classe sbbst.gettheightTree() possui complexidade de execução 0(N). 
Está(ão) correta(s) a(s) afirmativa(s): 
Somente 1 ,0 
A afirmativa II está errada, pois o retorno do maior elemento é baseado no parâmetro enviado (k), ou seja, o k-
ésimo valor, e a afirmativa III está errada porque sbbst.getHeightTree() possui complexidade de tempo 0(1). 
Logo, apenas a I está correta.

Outros materiais