Exercicio - Estrutura de Dados

Prévia do material em texto

23/09/2023, 12:41 Estácio: Alunos
https://simulado.estacio.br/alunos/ 1/6
Exercício
 avalie sua aprendizagem
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 é:
ESTRUTURA DE DADOS
Lupa  
 
DGT1335_202301141494_TEMAS
Aluno: THÁRSIS EMANUELLE DOS SANTOS CASIMIRO Matr.: 202301141494
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.
Os índices passam a ser contados a partir de 1.
Não é possível adicionar novos elementos ao array.
Não é possível remover elementos do array.
Diminuição no tempo de programação.
Todos os elementos devem ter o mesmo tamanho.
Data Resp.: 23/09/2023 12:27:45
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.
 
2.
javascript:voltar();
javascript:voltar();
javascript:voltar();
javascript:voltar();
javascript:diminui();
javascript:diminui();
javascript:aumenta();
javascript:aumenta();
23/09/2023, 12:41 Estácio: Alunos
https://simulado.estacio.br/alunos/ 2/6
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
O método de ordenação da bolha, ou Bubblesort (BS) tem complexidade de pior caso O(n2) e melhor caso O(n).
Suponha que exista um algoritmo de ordenação MS que tem complexidade de melhor caso O(nlog n) e de pior caso
O(nlog n). Podemos a�rmar que:
for linha in M:
            print(linha)
for linha in M:
            print(linha[2])
for linha in M:
            print(linha[3])
for coluna in M:
            print(coluna)
print(M[2])
Data Resp.: 23/09/2023 12:28:46
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.
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.
 
3.
Para um grande conjunto de entradas variadas de tamanho grande, MS executará em menos tempo que BS,
em média.
Para um grande conjunto de entradas variadas de tamanho grande, BS executará em menos tempo que MS,
em média.
MS e BS são igualmente e�cientes em ordenar elementos, independente da entrada ou seu tamanho.
Para uma única entrada de tamanho grande, BS executará em menos tempo que MS.
Para uma única entrada de tamanho grande, MS executará em menos tempo que BS.
Data Resp.: 23/09/2023 12:29:48
Explicação:
Pela natureza do tratamento de complexidade de algoritmos e o uso da notação O, a única a�rmativa verdadeira
é a de que em média, com um grande número de entradas distintas e de tamanho grande, MS executará mais
rápido que BS pois sua complexidade assintótica O(nlogn) é melhor que a de BS O(n2).
A a�rmação inversa está errada pelo mesmo argumento, O(nlogn) é melhor que O(n2).
As a�rmações que tratam de uma única entrada são falsas, pois você sempre pode escolher uma entrada que
seja de melhor caso para um dos algoritmos e seja ruim para o outro.
Por �m, a a�rmação de que ambos são igualmente e�cientes é desmentida pelo pior caso.
23/09/2023, 12:41 Estácio: Alunos
https://simulado.estacio.br/alunos/ 3/6
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?
Uma Deque é uma estrutura de dados mais generalista que as pilhas e �las. Para implementá-la de forma e�ciente,
você pode usar:
Uma lista circular é uma estrutura de dados contínua, permitindo que seja iterada sobre ela de forma in�nita. Uma
das suas aplicações em jogos digitais é:
7391LISTAS, PILHAS, FILAS E DEQUES
 
4.
InicioF==�nalF + 1
InicioF = M
InicioF==(�nalF+1)mod M
InicioF== �nalF
FinalF== M
Data Resp.: 23/09/2023 12:31:20
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.
 
5.
Lista contígua com 1 variável: início.
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.
Lista simplesmente encadeada com nó cabeça.
Data Resp.: 23/09/2023 12:31:05
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.
 
6.
Em jogos competitivos, para garantir que não há scripts ou bots rodando no computador.
Em jogos multijogador para garantir que apenas um dos jogadores jogue todas as vezes.
Em jogos multijogador em turnos, permitindo ceder o controle a um jogador por vez.
Em jogos de um jogador para armazenar um conjunto �xo de elementos.
Em jogos mobile, para armazenar o número do telefone do jogador.
Data Resp.: 23/09/2023 12:34:34
23/09/2023, 12:41 Estácio: Alunos
https://simulado.estacio.br/alunos/ 4/6
As operações de busca, remoção e inserção de nós em uma árvore binária de busca levam determinado tempo de
execução de seus algoritmos. Esses tempos são dados pela alternativa:
A raiz é o ponto de partida para acessar todos os elementos de uma árvore. Marque a opção correta acerca dos
principais conceitos de árvore binária de busca:
Explicação:
A grande virtude das listas circulares é o fato delas poderem ser percorridas um elemento por vez, de forma
in�nita. Apenas quando todos os elementos forem percorridos uma vez, começarão a ser percorridos pela
segunda vez, na mesma ordem. Essa disposição é excelente para a implementação de políticas ¿Round robin¿, ou
seja, onde cada jogador tem a sua vez de jogar e as vezes são igualmente distribuídas entre os jogadores.
Por isso a resposta correta éem jogos multijogador em turnos, permitindo ceder o controle a um jogador por
vez.
7408ÁRVORES EM PHYTON
 
7.
Busca: O(n) / Remoção: O(n) / Inserção: O(n)
Busca: O(1) / Remoção: O(log n) / Inserção: O(log n)
Busca: O(n) / Remoção: O(log n) / Inserção: O(log n)
Busca: O(n) / Remoção: O(n) / Inserção: O(log n)
Busca: O(log n) / Remoção: O(n) / Inserção: O(log n)
Data Resp.: 23/09/2023 12:35:08
Explicação:
No pior caso uma árvore binária de busca com n chaves tem n níveis. Assim, o pior caso da busca, é buscar o nó
mais profundo da árvore que demandará n comparações. Como a busca é subrotina da inserção e da remoção,
então as três operações terão complexidade de pior caso de O(n).
 
8.
Novas chaves maiores que a raiz sempre serão inseridas à esquerda.
Qualquer nó pode ter um número arbitrário de nós, sempre maior que 2.
O objetivo principal da estrutura de dados árvore binária de busca é ordenar uma lista sem a preocupação de
implementar de forma e�cientemente.
Dado um nó qualquer da árvore binária, todos os nós à direita dele são menores ou iguais a ele.
Em todas as estruturas de dados onde se realiza busca, inserção e remoção não são admitidas duplicidade de
chaves. Isto também inclui as árvores binárias de busca.
Data Resp.: 23/09/2023 12:38:36
Explicação:
O grau máximo de um nó em uma árvore binária é 2. A unicidade de chave é um pressuposto para estruturas de
busca. O objetivo principal de uma árvore binária de busca é implementar os algoritmos de busca, inserção e
remoção de forma otimizada. Chaves maiores que a raiz devem ser inseridas à direita. Dado qualquer nó de uma
árvore binária de busca, deve valer recursivamente a propriedade de que as chaves contidas à esquerda são
menores que a raiz e a direita maiores.
7392ÁRVORES DE BUSCA
23/09/2023, 12:41 Estácio: Alunos
https://simulado.estacio.br/alunos/ 5/6
As árvores AVL constituem uma importante estrutura de dados que disponibilizam operações de busca, inserção e
remoção. Classi�que como verdadeiro ou falso as a�rmativas abaixo:
I - As árvores de Fibonacci são as árvores de altura máxima h com número mínimo do nós n e altura proporcional a
log n.
II - As árvores completas são árvores AVL.
III - É possível construir uma topologia de uma árvore AVL que não seja nem completa nem de Fibonacci com altura
proporcional a log n.
IV - Uma vez que a altura das árvores AVL é proporcional a log n, podemos garantir que a busca ocorre numa
complexidade de O(log n).
V - Na remoção, pode ser necessário realizar todas as rotações, no pior caso, do pai de uma folha que está sendo
removida até a raiz. Por esta razão, a complexidade da remoção é maior que O(log n).
Seja a seguinte árvore AVL abaixo. Com a inserção da chave 90, marque a opção que indica exatamente o que
acontecerá com a árvore resultante após essa inserção:
 
9.
I-V, II-F, III-F, IV-V, V-V.
I-V, II-V, III-V, IV-V, V-F.
I-V, II-V, III-F, IV-V, V-F.
I-F, II-F, III-V, IV-F, V-F.
I-F, II-F, III-F, IV-V, V-V.
Data Resp.: 23/09/2023 12:39:45
Explicação:
Nem sempre é necessário realizar todas as operações, visto que a remoção pode eliminar uma folha e não causar
desbalanceamento na árvore.
 
10.
A árvore resultante irá desbalancear à direita do nó de chave 40.
A árvore resultante irá desbalancear à esquerda do nó de chave 60.
A árvore resultante irá desbalancear à esquerda do nó de chave 10.
A árvore resultante irá desbalancear à direita do nó de chave 80.
A árvore resultante irá manter o balanceamento geral da árvore.
Data Resp.: 23/09/2023 12:40:18
Explicação:
Ao inserir o nó de chave 90, ele é maior que o nó 80, sendo assim, inserido ao lado direito de 80, causando
desbalanceamento do nó 60 que tem altura da subárvore direita 2 e esquerda 0.
23/09/2023, 12:41 Estácio: Alunos
https://simulado.estacio.br/alunos/ 6/6
    Não Respondida      Não Gravada     Gravada
Exercício inciado em 23/09/2023 12:23:58.