Exercicio Estrutura de dados

Prévia do material em texto

Exercício
 avalie sua aprendizagem
O uso de funções recursivas pode facilitar a implementação de diversos algoritmos. Toda recursão depende
de dois elementos: o caso base e o passo recursivo. Dentre as opções a seguir, a que apresenta um passo
recursivo é:
ESTRUTURA DE DADOS
Lupa  
 
DGT1335_202301218446_TEMAS
Aluno: ROSANA SILVA SANTOS Matr.: 202301218446
Disc.: ESTRUTURA DE DADOS  2023.3 EAD (G) / EX
Prezado (a) Aluno(a),
Você fará agora seu EXERCÍCIO! Lembre-se que este exercício é opcional, mas não valerá ponto para sua
avaliação. O mesmo será composto de questões de múltipla escolha.
Após responde cada questão, você terá acesso ao gabarito comentado e/ou à explicação da mesma. Aproveite
para se familiarizar com este modelo de questões que será usado na sua AV e AVS.
7390ALGORITMOS E A LINGUAGEM PYTHON
 
1.
�b(n)=n-1 + n-2
fat(n)=n*fat(n-1)
fat(1)=1
par(n)=par(n)
f(n)=g(n-1)
Data Resp.: 23/10/2023 12:30:45
Explicação:
O passo recursivo é o elemento que faz o cálculo da função recursiva mover-se em direção ao resultado.
Deve envolver a chamada da própria função com um valor diferente de entrada. Isso só acontece na
resposta correta: fat(n)=n*fat(n-1) , passo recursivo da função de cálculo de fatorial.
fat(1)=1  é o caso base dessa mesma função. par(n)=par(n)  é uma tautologia, e não uma recursão. As
demais respostas são funções que não chamam a si mesmas, não podendo ser passos recursivos.
javascript:voltar();
javascript:voltar();
javascript:voltar();
javascript:voltar();
javascript:diminui();
javascript:diminui();
javascript:aumenta();
javascript:aumenta();
Ao usar a biblioteca numpy para criar arrays, existem diversas facilidades que um programador pode
utilizar, como funções especí�cas para somar todos os elementos, encontrar valores mínimo e máximo dos
elementos, entre outros.
Entretanto uma desvantagem de usar array da biblioteca numpy é:
Dada a seguinte matriz M, inicializada com o código:
M=[[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]]
O código em Python para imprimir cada elemento da coluna iniciada pelo elemento 3 é:
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
 
2.
Todos os elementos devem ter o mesmo tamanho.
Não é possível remover elementos do array.
Não é possível adicionar novos elementos ao array.
Os índices passam a ser contados a partir de 1.
Diminuição no tempo de programação.
Data Resp.: 23/10/2023 12:31:03
Explicação:
A desvantagem é que os elementos do array devem ocupar o mesmo espaço de memória, então devem
ser de mesmo tamanho. Isso não permite que você crie arrays com elementos de tamanho assimétricos.
Os índices continuam sendo contados a partir de 0 e as operações de inserção e remoção continuam
sendo possíveis. A diminuição no tempo de programação é uma vantagem.
 
3.
print(M[2])
for linha in M:
            print(linha[2])
for linha in M:
            print(linha)
for linha in M:
            print(linha[3])
for coluna in M:
            print(coluna)
Data Resp.: 23/10/2023 12:31:38
Explicação:
O laço deve percorrer uma coluna, iterando linha a linha e extraindo dela o seu terceiro elemento, ou seja
linha[2]. A resposta correta itera pelas linhas e imprime o elemento  [2] de cada uma.
Uma Deque é uma estrutura de dados mais generalista que as pilhas e �las. Para implementá-la de forma
e�ciente, você pode usar:
Em uma implementação da estrutura de dados do tipo �la, você possui um espaço de memória contíguo a
ela alocada com capacidade para M nós. A variável da �la é F, e duas variáveis guardam os índices do início e
�nal da �la (inicioF e �nalF).  Em uma implementação otimizada de F, como podemos identi�car que a �la
está cheia?
Dentre as respostas erradas, apenas escrever ¿print(linha)¿ imprimirá cada linha como um todo,
resultando na impressão de toda a matriz, linha a linha.
A resposta "print(coluna)" terá o mesmo resultado pois para o código linha e coluna são apenas nomes
escolhidos pelo programador. Poderia ser i, aux ou qualquer outra variável escolhida.
Já "print(linha[3])" está com o índice errado, imprimindo os elementos da coluna iniciada por 4. E
¿print(M[2])¿ imprime toda a linha iniciada por 9.
7391LISTAS, PILHAS, FILAS E DEQUES
 
4.
Lista contígua com 1 variável: início.
Lista simplesmente encadeada com nó cabeça.
Lista duplamente encadeada com 2 variáveis: início e �nal.
Fila com 2 variáveis: início e �nal.
Pilha com 1 variável: topo.
Data Resp.: 23/10/2023 12:32:00
Explicação:
Para implementar uma deque e�cientemente, você precisa ter um ponteiro para o início e o �nal da
deque, permitindo inserções e remoções em ambas as pontas com complexidade O(1) , sem  a
necessidade de percorrer a estrutura, o que seria O(n).
Além disso, a �la é uma especialização da deque. Ou seja, toda �la é um deque, mas nem toda deque é
uma �la. Podemos assim eliminar a resposta contendo �la. A resposta restante que possui 2 variáveis é a
correta. Lista duplamente encadeada. Ela permite a inserção e remoção nas extremidades com
complexidade O(1).
A lista contígua e a simplesmente encadeada com nó cabeça levariam a operação de inserção e remoção
ao �nal da �la terem complexidade O(n) por precisarem percorrer toda a estrutura, sendo também
descartadas.
 
5.
InicioF==�nalF + 1
InicioF== �nalF
InicioF==(�nalF+1)mod M
FinalF== M
InicioF = M
Data Resp.: 23/10/2023 12:32:38
Suponha que você está implementando um programa que precisa armazenar dados ordenados em uma
estrutura para serem tratados posteriormente, na ordem inversa à que foram recebidos. Haverá uma
grande quantidade de recebimentos e tratamento de dados, mas o tamanho esperado da estrutura não
deve variar muito. Qual tipo de estrutura de dados é a melhor nessa situação?
Seja a seguinte função em Python para percurso em uma árvore binária implementada em Python. Marque
a opção correta de qual percurso em árvores se trata essa função:
Explicação:
Em uma implementação otimizada da �la, é usado um sistema modular, onde o início e o �nal da �la se
movem a cada inserção e remoção. A cada inserção, �nalF aumenta em 1, até o máximo M, depois volta
para 0 e assim por diante. A cada remoção inícioF aumenta em 1, até o máximo M e depois volta a 0.
dessa forma a �la está cheia quando (�nalF+1)modM é igual a inicio.
 
6.
Lista duplamente encadeada.
Lista em alocação contígua.
Fila.
Lista simplesmente encadeada.
Pilha.
Data Resp.: 23/10/2023 12:32:55
Explicação:
A pilha permite o tratamento de nós usando a política requerida, FILO ¿ ¿�rst in last out¿ -. Além disso, as
operações de inserção e remoção são O(1), ou seja, de complexidade constante, a melhor possível. Isso
condiz com o requisito de que haverá muitas operações desse tipo. Por �m, o fato de a estrutura não
variar muito em tamanho permite o uso de uma alocação contígua e otimizada para a pilha. A �la não
obedece a lógica FILO e as listas têm complexidade de inserção e remoção O(n) sendo muito piores que a
pilha, principalmente quando o número desses tipos de operação é grande.
7408ÁRVORES EM PHYTON
 
7.
Percurso Anti simétrico
Percurso Pré-ordem
Percurso Pós-ordem
Percurso Em-ordem
Percurso raiz-folha
Seja a seguinte árvore de expressões aritméticas abaixo.
O resultado da visita em pre�xo dessa árvore é:
Data Resp.: 23/10/2023 12:33:18
Explicação:
Para realizar o percurso em pré-ordem, são necessários três acessos ao nó. No caso da pré-ordem, no
primeiro, executamos a visita (print(raiz.chave)), no segundo, chamamos recursivamente o algoritmo
para a sub-árvores esquerda (Visita(raiz.esquerda)) e, no terceiro, ocorre a chamada do percurso em pré-
ordem do ramo direito (Visita(raiz.direita)).
 
8.
A + ( B * C )
A * B + C
A + * B C
+ A * B C
A + B * C
Data Resp.: 23/10/2023 12:33:52
Explicação:
O percurso em pre�xo é de�nido recursivamente. A partir da raiz r da árvore de expressões aritméticas
T, percorre-se a árvore de da seguinte forma:
1 - visita-se a raiz;
2 - percorre-se a sub-árvores esquerda de T, em pre�xo e
3 - percorre-se a sub-árvores direita de T, empre�xo.
O resultado da visita é representado abaixo:
Considere a seguinte estrutura de árvore. Marque a alternativa correta:
7392ÁRVORES DE BUSCA
 
9.
A árvore da �gura se trata de árvore binária de busca.
A árvore acima é conhecida como árvore zig zag balanceada.
É necessário executar O(n2)  passos para deletar um elemento da árvore acima.
Remover o nó 36 irá deixar a árvore com as propriedades de árvore binária de busca.
Pode-se a�rmar que o número de passos para buscar um elemento na árvore acima é, no máximo,
O(log n).
Data Resp.: 23/10/2023 12:34:36
Explicação:
Existem vários tipos diferentes de árvores de busca, como árvores binárias, AVL e árvores B. Nesse sentido,
marque a opção correta sobre os procedimentos de rotação em árvores AVL:
Apesar de que a árvore considerada não é árvore binária de busca, observa-se que os nós estão dispostos
de forma balanceada e em níveis, portanto o número de passos para buscar um elemento na árvore
acima é, no máximo, 0(log n).
 
10.
Uma rotação simples à esquerda de um nó x acontece quando um desbalanceamento de x acontece à
esquerda.
Uma rotação simples à esquerda de um nó x acontece quando um desbalanceamento de x acontece à
direita.
Uma rotação dupla à esquerda de um nó x acontece quando um desbalanceamento de x acontece à
esquerda.
Uma rotação simples à direita de um nó x acontece quando um desbalanceamento de x acontece à
direita.
Uma rotação dupla à direita de um nó x acontece quando um desbalanceamento de x acontece à
direita.
Data Resp.: 23/10/2023 12:36:15
Explicação:
Em uma árvore AVL, uma rotação simples à esquerda de um nó acontece quando um desbalanceamento
de  acontece à direita. Se um nó  desbalanceia para um lado, ele deve rotacionar de forma inversa para
�car balanceado.
    Não Respondida      Não Gravada     Gravada
Exercício inciado em 23/10/2023 12:30:12.