Estrutura de Dados A2

Prévia do material em texto

A2 – ESTRUTURA DE BANCO DE DADOS UVA – 3º SEMESTRE 
Considere o algoritmo que implementa o seguinte processo: uma coleção desordenada de elementos é dividida em duas metades e cada metade é utilizada como argumento para a reaplicação recursiva do procedimento. Os resultados das duas reaplicações são, então, combinados pela intercalação dos elementos de ambas, resultando em uma coleção ordenada. Qual a complexidade desse algoritmo?
Alternativas
A)
o(n)
B) Marcada pelo aluno
o(n * log n)
C)
o(n²)
D)
o(log n * log n)
E)
o(2n)
A fila é uma estrutura de dados dinâmica que admite a inserção e remoção de elementos, a partir da técnica conhecida como FIFO. A inserção ocorre no início da fila e a remoção ocorre no final da fila. 
Neste contexto, assinale a afirmativa correta sobre a técnica FIFO.
Alternativas
A)
Os elementos de uma fila são ligados por uma linha denominada, tecnicamente, aresta.
B)
FIFO é a técnica de fila em que o primeiro elemento a entrar na fila será o último elemento a ser removido dessa fila.
C)
Na estrutura de dados fila, tanto a inserção como a remoção de elementos ocorre pelo topo da fila.
D)
O processo de inserção de elementos na fila é tecnicamente denominado push, e o processo de remoção de elementos da fila é tecnicamente denominado pop.
E) Marcada pelo aluno
A técnica utilizada na estrutura de dados fila afirma que o primeiro elemento a entrar na fila será o primeiro elemento a sair dela.
Como se sabe, tudo o que acontece em um computador (ou quase tudo) se passa na memória. Quando falamos de memória, normalmente falamos em memória RAM. É na memória RAM que são carregados os nossos programas, jogos, processadores de texto etc. É também na RAM que são armazenadas as variáveis que fazem parte dos nossos programas. De fato, a memória RAM pode ser vista como um enorme vetor de bytes consecutivos. Sempre que declaramos uma variável, temos que indicar qual o seu tipo e qual o seu nome: "char ch;". Os ponteiros conseguem trabalhar diretamente com endereços da memória, facilitando o processo de manipulação dos dados. 
 
DAMAS, L. Linguagem C. 10. ed. São Paulo: Grupo GEN, 2006 (adaptado).
 
Considerando o texto apresentado, analise o caso a seguir.
 
Carlos está participando de um projeto de construção de uma assistente virtual que auxilia os usuários em operações matemáticas. O código dessa assistente está sendo implementado na linguagem C, utilizando o conceito de ponteiros. Considere o código de teste a seguir.
Analisando esse código, assinale a alternativa que apresenta corretamente uma função que utiliza o conceito de ponteiro para calcular o quadrado de um número.
Alternativas
A)
void potencia(int %num){
%num = pot(%num, 2);
}
B)
int potencia(int &num){
&num = pow(&num, 2);
}
C)
void potencia(int *num){
num = sqrt(num, 2);
}
D) Marcada pelo aluno
void potencia(int *num){
*num = pow(*num, 2);
}
E)
void potencia(int &num){
&num = sqrt(&num, 2);
}
O conceito implementado pela pilha é o de “Last-in, First-out” (também chamado LIFO ou FILO, de first-in, last-out, que tem o mesmo sentido prático) ou “Último a entrar, Primeiro a sair”. Imagine, por exemplo, que você esteja organizando vários pratos. Inicialmente, você organiza todos uns sobre os outros, formando uma pilha de pratos. Logo após, você irá retirar um a um para organizar no seu devido local. Perceba que o primeiro prato removido foi o último a ser inserido na pilha, aquele que ficou na parte superior. Enquanto isso, o primeiro prato inserido na pilha, aquele que está abaixo de todos, será o último removido.
 
RODRIGUES, Joel. Queue e Stack – Trabalhando com os modelos FIFO e LIFO em .NET. DevMedia, Rio de Janeiro, 2012. Disponível em: https://www.devmedia.com.br/queue-e-stack-trabalhando-com-os-modelos-fifo-e-lifo-em-net/25579. Acesso em: 14 maio 2021 (adaptado).
 
Dado o exposto, considere a situação a seguir.
 
Paulo está criando um jogo no qual os artefatos encontrados por último devem ser utilizados primeiro. Ou seja, caso encontre um artefato do "A", guarde e depois encontre um artefato do "B", somente poderá utilizar o artefato do "A" quando tiver utilizado o artefato do "B". Portanto, uma das regras principais do jogo é a utilização obrigatória dos artefatos a respeito da política de uma pilha  (LIFO – Last-in, First-out).
 
Considerando o jogo que está sendo construído na situação apresentada, avalie as afirmações a seguir.
I. Esse jogo pode armazenar os artefatos em uma estrutura de pilha e utilizar os métodos padrões de “push” para guardar o artefato e “pop” para utilizar o artefato.
II. A estrutura utilizada é semelhante a uma fila de prioridades, em que a prioridade maior é sempre do último artefato encontrado.
III. A estrutura utilizada nesse jogo sempre deve inserir e remover os artefatos pela mesma extremidade considerada topo.
É correto o que se afirma em
Alternativas
A)
II, apenas.
B)
I e III, apenas.
C)
III, apenas.
D) Gabarito da questão
I, II e III.
E)
I e II, apenas.
Toda informação que manipulamos dentro de um programa (esteja ela guardada em uma variável, array, estrutura etc.) obrigatoriamente está armazenada na memória do computador. Quando criamos uma variável, o computador reserva um espaço de memória onde podemos guardar o valor associado a ela. Ao nome que damos a ela o computador associa o endereço do espaço que ele reservou na memória para guardá-la. De modo geral, interessa ao programador saber o nome das variáveis. Já o computador precisa saber onde elas estão na memória, ou seja, precisa dos seus endereços. Ponteiros são um tipo especial de variáveis que permitem armazenar endereços de memória em vez de dados numéricos (como os tipos int, float e double) ou caracteres (como o tipo char).
 
BACKES, André. Linguagem C: completa e descomplicada. 2. ed. Rio de Janeiro: LTC, 2021 (adaptado).
 
Dado o exposto, considere a situação hipotética a seguir.
 
Pedro, analista de sistemas, está liderando um projeto para a área de arte, que irá utilizar diversos cálculos para avaliar a simetria entre várias obras de arte. Inicialmente, neste projeto que está sendo desenvolvido na linguagem C, Pedro precisa criar uma função que altere através do uso de ponteiro o valor de duas variáveis inteiras. A chamada da função é feita com o código a seguir.
 
muda(&v1,&v2);
 
Um possível código para a função, que deve ser elaborado por Pedro, é
Alternativas
A)
void muda(int &v1, int &v2){
*temp = &v2;
&v1=&v2;
&v2=*temp;
}
B) Marcada pelo aluno
void muda(int *v1, int *v2){
int temp = *v1;
*v1=*v2;
*v2=temp;
}
C)
int muda(int &v1, int &v2){
*temp = &v2;
&v1=&v2;
return temp;
}
D)
int muda(int *v1, int *v2){
*temp = *v2;
*v1=*v2;
return temp;
}
E)
int muda(int &v1, int &v2){
&temp = &v1;
&v1=&v2;
&v2=&temp;
}
De acordo com Boente (2003), "a alocação dinâmica de memória em tempo de execução é realizada na linguagem C, por meio de ponteiros ou apontadores, utilizando, para isso, a função malloc( )". 
(Fonte: BOENTE, A. N. P. Aprendendo a programar em linguagem C: do básico ao avançado. Rio de Janeiro: Brasport, 2003.)
Neste contexto, analise o código-fonte a seguir, escrito em linguagem C, e marque a alternativa correta.
#include <stdio.h>
#include <malloc.h>
#include <dos.h>
void main (  )
{
     int
          *ptr;
ptr = ( int * ) malloc( sizeof( int ));
*ptr = 3;
     system(“CLS”);
     printf (“Conteudo do ponteiro: %dnn”, *ptr);
    system(“PAUSE”);
}
Alternativas
A) Gabarito da questão
Imprime o conteúdo de dado 3, armazenado no apontador ptr.
B)
Não executa função alguma, pois existe um erro na linha de código ptr = ( int * ) malloc( sizeof( int ));.
C)
Permite que o apontador *ptr aponte para a próxima informação que está contida na posição 3 de memória.
D)
Permite que o apontador *ptr aponte para o próximo endereço de memória que está contido na posição 3.
E)
Imprime o valor do próximo endereço dinâmico de memória em que *ptr é igual a 3.
De acordo com Puga e Risseti (2009), "as estruturas indexadas, que necessitam de mais de um índice para identificar um de seus elementos,são chamadas de matriz de dimensão n, sendo que n representa o número de índices requeridos". 
(Fonte: PUGA, S.; RISSETI, G. Lógica de programação e estrutura de dados com aplicações em Java. 3. ed. São Paulo: Pearson Prentice Hall, 2009.)
Neste contexto, defina matriz sucintamente.
Resposta do aluno
Uma matriz é uma estrutura de dados bidimensional que armazena elementos em uma grade retangular. Cada elemento na matriz é acessado por um par de índices, representando a linha e a coluna em que o elemento está localizado.
Sabe-se que as pilhas são uma lista na qual é aplicada a disciplina de acesso antagônica denominada UEPS (o último a entrar é o primeiro a sair, ou, em inglês, LIFO — Last In First Out). Isso significa que qualquer elemento que entrar na pilha somente sairá quando todos que entraram depois dele saírem.
Escreva, em linguagem C, o trecho de programa que realize o processo de empilhar elementos na estrutura de dados pilha, descrevendo, também, a struct da pilha utilizada.
Resposta do aluno
#include <stdio.h>
 #include <stdlib.h>
 #define MAX_SIZE 10 
struct Pilha { 
int dados [ MAX_SIZE];
 int topo;
 };
 void inicializarPilha(struct Pilha*pilha) {
 pilha->topo = -1; 
} 
int pilhaCheia(const struct Pilha*pilha) {
 return pilha->topo == MAX_SIZE - 1;