Estrutura de Dados - Atividades Semana 3

Prévia do material em texto

2 pts Pergunta 1
A linguagem C deixa a cargo do programador todas as operações necessárias para o 
gerenciamento das estruturas de dados e permite a manipulação de estruturas e ponteiros de 
maneira explícita. Sobre essa linguagem, preencha as lacunas escolhendo a alternativa 
correta:
Para alocar memória na linguagem C, podemos usar a função malloc , que recebe 
como parâmetro o número de bytes que se deseja alocar e retorna o endereço inicial do bloco 
de bytes alocado. Esse retorno tem o tipo void* . Para sabermos quantos bytes 
queremos alocar, a função sizeof recebe como parâmetro um tipo e retorna o tamanho 
em número de bytes.
Na linguagem C, há uma distinção bastante explícita entre um tipo e um endereço para aquele 
tipo. Na declaração de uma variável, usamos * após o identificador do tipo, para 
indicar que estamos nos referindo a um endereço para aquele tipo.
2 pts Pergunta 2
Em um projeto de programação, os alunos devem implementar uma estrutura de dados para 
armazenar uma lista de pessoas. Um grupo de alunos decidiu organizar a lista em uma 
estrutura de dados sequencial implementada em um arranjo. A lista sempre é mantida 
ordenada pelo CPF da pessoa. Com relação à solução desse grupo, assinale verdadeiro ou 
falso:
Falso A busca de um registro usando o nome da pessoa pode ser feita com 
o algoritmo de busca binária.
•
Verdadeiro As inserções exigem o deslocamento de outros elementos para que 
haja espaço liberado para o elemento a ser inserido.
•
Verdadeiro A busca de um registro usando o CPF da pessoa pode ser feita com o 
algoritmo de busca binária.
•
Falso A busca de um registro usando o CPF exigirá que os registros 
anteriores a ele na lista sejam percorridos sequencialmente.
•
Verdadeiro Um registro pode ser acessado diretamente se o índice deste na 
sequência for conhecido.
•
Verdadeiro A remoção de um registro pode alterar a posição de memória dos 
registros restantes.
•
Falso A alocação de memória para adicionar novos registros é feita sob 
demanda, não precisamos "gastar" memória que não estamos usando.
•
Verdadeiro A reinicialização da lista não exige a desalocação de memória de 
todos os elementos.
•
Verdadeiro A ordem lógica dos elementos na lista (a ordem vista pelo usuário) é a 
mesma da ordem física (em memória principal).
•
2 pts Pergunta 3
Não. Em listas ligadas não é possível a implementação de algoritmos para obter um elemento a partir do índice do 
mesmo na sequência. A consulta por um elemento deverá ser feita com alguma chave de busca como critério.
Não. Mesmo tendo o índice do elemento, teremos que começar a busca a partir do primeiro elemento e utilizar os 
ponteiros para percorrer a lista até a posição do índice. No pior caso, o índice do último elemento foi dado e teremos 
que percorrer todos para obtê-lo.
Sim. Podemos usar a informação do índice para decidir se vamos percorrer a lista na ordem ascendente dos índices 
ou na ordem descendente. Em outras palavras, se o índice for menor que a metade do número de elementos, 
percorremos em ordem ascendente.
Sim. Se assumirmos que os índices de qualquer estrutura linear estão ordenados (o primeiro antes do segundo, que 
está antes do terceiro, e assim por diante), então podemos acessar qualquer índice por meio de uma busca binária.
Sim. À medida em que temos um índice ao invés de uma chave como critério para obter o elemento, podemos 
acessar o registro correspondente diretamente, em tempo constante, sem a necessidade de percorrer os outros 
elementos.
Em uma lista ligada com n elementos, cada elemento possui um registro e um ponteiro para o 
próximo elemento da lista. Uma busca usando uma chave pode exigir que se percorra todos os 
n elementos até que se encontre aquele que corresponde à chave. Assumindo que já 
conhecemos o índice do elemento que queremos obter, é possível desenvolver um algoritmo 
que acesse esse elemento sem que, no pior caso, tenhamos que percorrer todos os 
elementos?
2 pts Pergunta 4
Uma lista ligada foi implementada de maneira estática (registros são armazenados em um 
arranjo). As inserções e remoções de elementos ocorrem de modo a garantir que a lista se 
mantenha ordenada pelo valor da chave. Em um determinado momento da execução, os 
elementos contidos no arranjo estão na seguinte configuração:
Identifique se são verdadeiras ou falsas as alternativas a seguir:
Falso Na estrutura de dados do enunciado, a procura por um elemento 
usando a chave como critério pode ser feita de forma eficiente com a busca binária. 
Isso ocorre porque os elementos estão em um arranjo (podem ser acessados 
diretamente) e ordenados pelo valor da chave.
•
Verdadeiro Após a inserção da chave 8 na primeira posição disponível, 
obteremos a configuração:
•
Falso A remoção de um dado elemento irá exigir o deslocamento de todos 
os elementos maiores que ele na lista, para preenchimento do espaço vazio.
•
Verdadeiro A partir da configuração inicial, a remoção do elemento de chave 3 
(primeiro elemento do arranjo) gera a configuração:
•
2 pts Pergunta 5
Assinale verdadeiro ou falso para as características que estão totalmente relacionadas a pilhas:
Falso Remoções ocorrem na base da pilha.
•
Verdadeiro Inserções ocorrem no topo da pilha.
•
Verdadeiro É um tipo de estrutura linear.
•
Falso Inserções exigem o deslocamento de outros elementos na memória 
principal.
•
Verdadeiro Inserções e remoções são feitas de forma eficiente.
•
Salvo em 22:59
Falso Remoções exigem o deslocamento de outros elementos na memória 
principal.
•
Verdadeiro O último elemento a ser inserido é obrigatoriamente o primeiro a ser 
removido.
•
Verdadeiro Uma pilha pode ser implementada de forma estática com os registros 
sendo armazenados em um arranjo.
•
Falso O algoritmo para remoção de um elemento exige um laço de 
repetição (while, for, ...)
•
Enviar teste