ESTRUTURA DE DADOS

Prévia do material em texto

ESTRUTURA DE DADOS 
 
 
AULA 01 – ESTRUTURA DE DADOS 
 
1. Qual a diferença entre dado e informação? 
Dados não têm significado de forma isolada e servem de base para a informação. A informação é fruto do 
processamento dos dados. 
 
2. O que é um índice? 
É uma referência utilizada normalmente em estrutura de dados, que facilita o trabalho quando é feita uma consulta 
que envolve vários dados. 
 
3. Qual a diferença entre estruturas de dados homogêneos e heterogêneos? 
Estruturas de dados homogêneas armazenam o mesmo tipo de dados, e estruturas heterogêneas armazenam tipos 
de dados diferentes. 
 
4. Quais são as estruturas de dados que representam o tipo de estrutura de dados homogêneos? 
Vetores e matrizes. 
 
5. Por que um vetor é uma estrutura unidimensional, e uma matriz é uma estrutura bidimensional? 
Porque o vetor armazena dados de forma sequencial, e a matriz armazena dados dispostos em linhas e colunas. 
 
 
 
AULA 02 – TIPOS ABSTRATOS DE DADOS 
 
1. Qual é a diferença entre tipo de dados e estrutura de dados? 
Tipo de dados é o tipo de valor que pode ser armazenado. Estrutura de dados é a maneira mais adequada de armazenar 
e organizar os dados, para que sejam usados de forma eficiente. 
 
2. Qual é a premissa básica de um tipo abstrato de dados (TAD)? 
O TAD tem como objetivo permitir que o programador trabalhe preocupando-se somente com as operações possíveis 
para uma estrutura de dados, e não com a forma como essas operações são implementadas. 
 
3. São características de um tipo abstrato de dados (TAD): 
Separação entre a parte conceitual e a implementação; encapsulamento da estrutura de dados do TAD. 
 
4. O que é a modularização do código de um programa que usa TAD? 
Significa separar o programa em arquivos que tratem, de forma independente, da prototipação das funções, da sua 
implementação e da declaração dos tipos de dados. 
 
5. Qual é o conceito de TAD conjunto? 
É um conjunto de elementos, todos diferentes entre si, onde cada um deles também é um conjunto. 
 
 
 
AULA 03 – MODULAÇÃO 
 
1. Observe as alternativas e assinale a que representa uma das vantagens de se usar a modularização. 
É mais fácil testar os módulos individualmente do que o programa completo. 
 
2. Sobre funções e procedimentos, assinale a alternativa correta. 
Uma função é um módulo que produz um único valor de saída, e um procedimento é um tipo de módulo usado para 
várias tarefas, não produzindo valores de saída. 
 
3. O algoritmo, a seguir, foi escrito para ler três números e retornar o maior deles. Dentre as alternativas a seguir, 
qual delas contém a linha de código com declaração de variável local? 
 
1. algoritmo "maior modularizado" 
2. var 
3. numero1, numero2, numero3: inteiro 
4. 
5.funcao maior(valor1, valor2, valor3: inteiro): inteiro 
6.var 
7.aux:inteiro 
8.inicio 
9.se (valor1 > valor2) e (valor1 > valor3) entao 
10.aux <- valor1 
11.senao 
12.se (valor2 > valor3) entao 
13.aux <- valor2 
14.senao 
15.aux <- valor3 
16.fimse 
17.fimse 
18.retorne aux 
19.fimfuncao 
20. 
21. 
22.inicio 
23. 
24.escreva("Digite o 1. número: ") 
25.leia(numero1) 
26. 
27.escreva("Digite o 2. número: ") 
28.leia(numero2) 
29. 
30.escreva("Digite o 3. número: ") 
31.leia(numero3) 
32. 
33.escreva("O maior é ", maior(numero1, numero2, numero3)) 
34. 
35.fimalgoritmo 
 
Linha 7 
 
4. Há duas maneiras de se passar argumentos ou parâmetros para funções: por valor e por referência. Sobre 
passagem de parâmetros por valor e por referência, assinale a alternativa correta. 
Na passagem por valor, o valor é copiado do argumento para o parâmetro formal da função. 
 
5. Baseado no que foi visto nesta Unidade de Aprendizagem sobre modularização, e analisando o algoritmo a seguir, 
 
algoritmo "triangulo" 
var 
 lado1, lado2, lado3:inteiro 
 tipo_triangulo: caracter 
 valido:logico 
 
procedimento lerDados() 
inicio 
 escreva("Digite o 1. lado: ") 
 leia(lado1) 
 escreva("Digite o 2, lado: ") 
 leia(lado2) 
 escreva("Digite o 3, lado: ") 
 leia(lado3) 
fimprocedimento 
 
funcao ehTriangulo(lado1, lado2, lado3: inteiro): logico 
inicio 
 se (lado1 < (lado2 + lado3)) e (lado2 < (lado1 + lado3)) e (lado3 < (lado1 + lado2)) entao 
 retorne verdadeiro 
 senao 
 retorne falso 
 fimse 
fimfuncao 
 
funcao qualTriangulo(lado1, lado2, lado3:inteiro): caracter 
inicio 
 se (lado1 = lado2) e (lado1 = lado3) e (lado2 = lado3) entao 
 retorne "equilátero" 
 senao 
 se (lado1 <> lado2) e (lado1 <> lado3) e (lado2 <> lado3) entao 
 retorne "escaleno" 
 senao 
 retorne "isósceles" 
 fimse 
 fimse 
fimfuncao 
 
inicio 
 lerDados() 
 valido <- ehTriangulo(lado1, lado2, lado3) 
 se (valido) entao 
 tipo_triangulo <- qualTriangulo(lado1, lado2, lado3) 
 escreval("Triângulo ", tipo_triangulo) 
 senao 
 escreval("Os lados informados não formam um triâgulo") 
 fimse 
fimalgoritmo 
 
marque a alternativa correta. 
O algoritmo compila e executa corretamente. 
 
 
 
AULA 04 – CALCULO DE ENDEREÇO DE MEMÓRIA 
 
1. De acordo com a imagem, quais os valores de x e y ao fim da execução de código? 
 
x= 3 e y = 4 
 
2. Qual o erro existente no seguinte código-fonte? 
 
Na linha 7, não pode ser atribuído a um ponteiro o valor de uma variável a. 
 
3. O seguinte código deve alocar dinamicamente o espaço para um vetor de inteiros. A quantidade de elementos do 
vetor é definida pela variável num_componentes. Qual instrução deve ser inserida na linha 13 para que esse completo 
esteja correto? 
 
ptr = (int*) malloc(num_componentes * sizeof(int)); 
 
4. Assinale a opção correspondente ao resultado que será impresso para a variável valor, após a execução do trecho 
de código a seguir: 
 
Valor : 2007 
Valor : 2008 
 
5. Qual o resultado da execução do programa a seguir? 
 
25 25 50 
 
 
 
AULA 05 – PILHAS 
 
1. No contexto estrutura de dados, pilha é: 
Um tipo de lista linear em que o último elemento a ser inserido é o primeiro retirado. 
 
2. Em estruturas de dados, é encontrada a estrutura pilha. Avalie as assertivas abaixo e identifique a alternativa 
correta. 
I. Para excluir (remover ou desempilhar) o elemento da pilha, basta excluir o elemento para o qual aponta o 
ponteiro de início. Esta operação permite recuperar o dado no topo da pilha, e também removê-lo. 
II. Uma das possíveis utilizações de uma pilha é a implementação da sequência de desfazer (Ctrl + Z) de um 
editor de texto. 
III. Na estrutura pilha, o último elemento a entrar também é o último a sair. 
IV. Na pilha, as operações de exclusão e inclusão são realizadas na mesma extremidade, chamada topo. 
V. As operações de exclusão e inclusão são realizadas em qualquer parte da pilha. 
Assinale a alternativa correta: 
Somente a II e IV 
 
3. Assinale a opção correta relativa às operações básicas suportadas por pilhas. 
PUSH coloca um elemento no topo da pilha. 
 
4. Considere os estados (inicial e final) da pilha a seguir, na qual top corresponde ao seu topo. 
 
Para atingir o estado final dessa pilha, deve-se usar a seguinte sequência de operações básicas: 
pop(), pop(), push(9), push(3). 
 
5. Considere que os itens W, X, Y, Z e K foram inseridos nessa ordem em uma pilha. Necessariamente, o último 
elemento é: 
K. 
 
 
 
AULA 06 – 
 
1. Uma das estrutudas de dados utilizadas na programação de computadores funciona conforme o princípio 
conhecido como FIFO - First In First Out e LIFO - Last In First Out. Essas estruturas são denominadas, 
respectivamente: 
Fila e pilha. 
 
2. Suponha o seguinte cenário: Uma fila FIFO foi criada, e um nodo foi inserido a cada minuto, chegando a um total 
de dez elementos (dez minutos depois da criação da fila). A partir desse momento, decide-se remover um nodo. 
Qual deles será removido? 
O primeiro (inserido no minuto 1). 
 
3. Considerando os conceitos de estrutura de dados, analise as afirmativas a seguir e marque verdadeiro (V) ou 
falso (F): 
( ) As filas são utilizadas paracontrolar o acesso de arquivos que concorrem a uma única impressora. 
( ) A pilha é uma estrutura de dados baseada no princípio LIFO, no qual os dados que foram inseridos primeiro 
na pilha serão os últimos a serem removidos. 
( ) Para gerenciar processos, sistemas operacionais utilizam filas para organizar processos que aguardam 
processamento. 
V, V, V 
 
4. Um conjunto ordenado de itens a partir do qual podem ser eliminados itens em uma extremidade e no qual 
podem ser inseridos itens na outra extremindade, é denominado: 
Filas 
 
5. Estrutura de Dados básicas como Fila são usadas em uma gama variada de aplicações computacionais. Marque a 
alternativa correta quanto a estas aplicações. 
Buffer para gravação de dados em mídia. 
 
 
 
AULA 07 – 
 
1. Baseando-se no conceito de lista estática, marque a alternativa correta em relação à inclusão de elementos. 
A inclusão de elementos pode ocorrer em qualquer posição da lista. 
 
2. Em relação às listas estáticas, leia as alternativas a seguir e indique a correta. 
Os itens estão dispostos em uma ordem sequencial, sem conter elementos nulos. 
 
3. Marque a alternativa correta em relação à interface de uma lista estática. 
Não existe uma definição de quais métodos devem ser implementados, embora alguns sejam esperados. 
 
4. Analise o seguinte pseudocódigo baseado na linguagem C e marque a alternativa que representa o significado da 
função xxxxx. 
 
typedef struct ｛ 
int dado[50]; //array de itens da lista 
int n; //total de elementos da lista 
｝ Lista; 
 
int xxxxx (Lista *L, int pos){ 
for (int i= pos; i <= (L->n)-1; i++) 
L->dado[i-1]= L->dado[i]; 
(L->n)--; 
} 
 
Remove o item da lista de posição igual a "pos" e reposiciona os demais. 
 
 
5. Analise o seguinte código baseado na linguagem C indique a alternativa que o define. 
 
typedef struct ｛ 
unsigned long CPF; 
char Ativo; 
｝ Documento; 
 
typedef struct { 
Documento Cadastro[1000]; 
int n; 
} Pessoas; 
 
Pessoas lista; 
Documento doc; 
 
Define uma lista para armazenar 1000 elementos do tipo Documento. 
 
 
 
AULA 08 – LISTAS ENCADEADAS 
 
1. Baseando-se no conceito de lista dinâmica encadeada, marque a alternativa correta em relação à inclusão de 
elementos: 
A inclusão de elementos deve ocorrer em qualquer posição da lista. 
 
2. Em relação às listas simplesmente encadeadas, leia as alternativas a seguir e indique a correta: 
Alocam apenas a memória necessária para armazenar os elementos da lista. 
 
3. Marque a alternativa correta em relação às vantagens de uma lista dinâmica: 
Permitem aumento e redução do tamanho da lista em tempo de execução. 
 
4. Analise o seguinte código baseado na linguagem C e marque a alternativa que representa o seu significado: 
 
nodo *item= (nodo *) malloc(sizeof(nodo)); 
nodo *no= L->prox; 
while(no->prox != NULL) ｛ 
no= no->prox; 
｝ 
no->prox = item; 
 
Adiciona um novo elemento no final da lista. 
 
5. Levando em consideração os conceitos de uma lista simplesmente encadeada, assinale a alternativa que melhor 
representa a sua utilização: 
Listas grandes, com muitas inserções e em qualquer posição. 
 
 
 
AULA 09 – LISTAS ENCADEADAS DUPLAS 
 
1. Listas encadeadas duplas são estruturas com características específicas. Baseando-se no conceito de lista 
encadeada dupla, marque a alternativa correta: 
Cada elemento apresenta dois atributos do tipo ponteiro da lista, usados para referenciar o elemento anterior e 
próximo. 
 
2. O duplo encadeamento em listas permite que façamos operações onde a navegação é feita nos dois sentidos, 
como em um reprodutor de música. Em relação às listas com encadeamento duplo, leia as alternativas a seguir e 
indique a correta: 
Alocam apenas a memória necessária para armazenar os elementos atuais da lista. 
 
3. Cada estrutura de dados apresenta métodos diferentes para a inserção e exclusão de elementos. Baseando-se no 
conceito de lista encadeada dupla. Marque a alternativa correta em relação à inclusão de elementos: 
A inclusão de elementos pode ocorrer em qualquer posição da lista. 
 
4. Listas duplamente encadeadas se diferenciam de outros tipos de lista por causa de algumas características 
específicas. Sobre lista duplamente encadeada. Marque a alternativa correta em relação às suas características: 
Os elementos podem conter variáveis de um tipo primitivo ou estruturas compostas. 
 
5. Para cada tipo de manipulação de itens em uma lista encadeada dupla, nós precisamos desenvolver diferentes 
métodos, por exemplo para inclusão e exclusão de elementos. 
Analise o seguinte método e marque a alternativa que representa o seu significado: 
 
struct Node｛ 
int numero; 
struct Node *ant; 
struct Node *prox; 
｝; 
typedef struct Node node; 
struct Descritor{ 
int n; 
struct Node *prim; 
struct Node *ult; 
}; 
typedef struct Descritor descritor; 
void metodo(descritor *desc, node *list) { 
node *u= desc->ult; 
node *p= u->ant; 
p->prox= NULL; 
desc->ult= p; 
free(u); 
desc->n--; 
} 
 
Remove o último elemento da lista. 
 
 
AULA 10 – ORDENAÇÃO DE DADOS – MÉTODO SIMPLES 
 
1. São métodos de ordenação simples que realizam o mesmo número de comparações, porém o primeiro realiza 
mais trocas que o segundo: 
Bubblesort e Selectionsort. 
 
2. Em relação ao método Bubblesort, assinale a alternativa correta: 
Realiza várias comparações e várias trocas a cada fase iterativa. 
 
3. Assinale a alternativa que explica corretamente a técnica utilizada pelo método Selectionsort: 
Realiza várias comparações e apenas uma troca a cada fase iterativa. 
 
4. Assinale a alternativa que representa as características do método de ordenação Insertionsort: 
Apresenta melhor desempenho que o Bubblesort e o Selectionsort em vetores pré-ordenados. 
 
5. Indique a que método de ordenação simples se refere a seguinte explicação: "realiza a comparação de cada 
elemento do vetor com todos os elementos posteriores, com o objetivo de encontrar o menor valor para realizar 
apenas uma troca de posição a cada fase de iteração. 
Selectionsort. 
 
 
 
AULA 11 – ORDENAÇÃO DE DADOS COM MÉTODOS EFICIENTES 
 
1. Que algoritmo de ordenação de dados utiliza um pivô, que é selecionado para dividir o vetor em dois outros? 
Quicksort 
 
2. Em que consiste a estratégia da divisão e conquista? 
Dividir um problema maior em vários problemas menores, que serão resolvidos até que o problema inicial possa ser 
solucionado. 
 
3. Por que o algoritmo Mergesort tem esse nome? 
Por causa da mistura dos dois últimos vetores auxiliares, que é feita após o resultado da divisão do vetor inicial em 
pares e da sua ordenação, de forma recursiva, e da sua reunião em vetores auxiliares. 
 
4. O que significa a recursividade na Ciência da Computação? 
Recursividade é a característica que uma função possui para fazer a chamada para si mesma. 
 
5. Os métodos de ordenação direta podem ser divididos em métodos simples e eficientes. Qual a diferença entre 
eles? 
Os métodos simples são melhores para ordenar listas pequenas e fazem mais comparações para ordenar o vetor. Já os 
métodos eficientes são melhores para ordenar listas grandes e fazem menos comparações para ordenar o vetor. 
 
 
 
AULA 12 – ÁRVORES 
 
1. Tratando-se de estruturas de dados em árvore, qual das opções abaixo representa o conceito de folha? 
Um nó que não possui sub-árvores. 
 
2. Dada a seguinte árvore, em relação ao nó 4 podemos afirmar que: 
 
O nó 4 é filho do nó 1 e pai dos nós 7, 8 e 9. 
 
3. Qual é a principal característica de uma árvore binária completa? 
Possuir todas folhas no mesmo nível. 
 
4. Que grau possui a árvore abaixo? 
 
 A árvore é grau 2. 
 
5. Quais são as folhas da árvore abaixo? 
 
D, G, H e I. 
 
 
 
AULA EXTRA 01 – ARVORES BINÁRIAS DE BUSCA 
 
1. Qual das características a seguir representa uma árvore binária de busca? 
A subárvore à direita possui valores maiores que a raiz. 
 
2. Uma das operações típicamente realizadas em árvores binárias de busca é a busca por um elemento da árvore. 
Na árvore a seguir, caso fosse necessário buscar o valor 8, quantas comparaçõesdeveriam ser realizadas até 
encontrá-lo? 
 
Três comparações. 
 
3. A árvore a seguir foi percorrida na seguinte sequência: DBGEHIFCA. Qual o tipo de percurso utilizado? 
 
Pós-ordem. 
 
4. Qual o principal objetivo da organização de dados em estruturas de árvores binária de busca? 
Facilitar a busca de um determinado valor. 
 
5. Quantas folhas existem na árvore a seguir? 
 
 Duas folhas. 
 
 
 
AULA EXTRA 02 – CAMINHAMENTO EM ÁRVORE 
 
1. Assinale a ordem de exibição se for executado o algoritmo de caminhamento em pré-ordem para a seguinte árvore: 
 
ABCDEFG. 
 
2. Qual a ordem de caminhamento que retorna os seus nós em ordem crescente para a árvore a seguir? 
 
Caminhamento in-ordem. 
 
3. Qual a diferença entre os caminhamentos pré-ordem, in-ordem e pós-ordem em uma árvore binária, levando em 
consideração a implementação feita em C e usando recursão? 
A ordem em que os nós são visitados. 
 
4. Qual a sequência de saída para a árvore a seguir se o algoritmo de pós-ordem for executado? 
 
3 7 6 12 24 15 8. 
 
5. Indique qual o tipo de caminhamento é implementado pelo strecho de código a seguir: 
 
Caminhamento em ordem. 
 
 
 
AULA EXTRA 03 – BALANCEAMENTO DE ÁRVORE 
 
1. Uma das principais vantagens das árvores binárias em relação às demais estruturas de dados é a sua eficiência 
no processo de realizar buscas. A árvore AVL é conhecida por ter um resultado muito eficiente durante a operação 
de busca, pois realiza uma distribuição homogênea dos dados. Qual a ideia central ao fazer o balanceamento em 
uma árvore? 
A ideia central do balanceamento é que, para cada novo elemento adicionado ou removido da árvore, seja realizado 
uma reorganização para que a distribuição dos elementos conforme sua subárvore, continue homogênea. 
 
2. As árvores AVL correspondem à família das árvores binárias, em que a distribuição dos elementos é feita de 
acordo com determinadas condições, as quais são necessárias para garantir o balanceamento da árvore. Em relação 
à altura de uma AVL, qual é a afirmação correta? 
A altura de uma árvore nula é igual a -1. 
 
3. Uma árvore AVL é uma árvore binária muito utilizada para armazenamento de dados em memória. Cada nó de 
uma árvore AVL necessita da informação de altura, pois é fundamental para o processo de balanceamento. Para um 
nó folha, que tem uma altura igual a 1, sendo que essa árvore AVL tem 7 nós. Qual é a altura máxima que essa 
árvore pode ter? 
3. 
 
4. Uma árvore AVL tem as funções básicas como inserção, remoção e busca, assim como uma árvore simples. 
Considere a seguinte árvore AVL. 
 
Qual das alternativas a seguir é a árvore AVL atualizada após a inserção de 70? 
 
 
5. No processo de realizar o balanceamento de uma árvore AVL, após a exclusão ou inclusão são realizadas 
operações para realizar o balanceamento. Quais das seguintes operações são usadas pelas árvores AVL? 
Rotação à esquerda e rotação à direita. 
 
 
 
AULA EXTRA 04 – GRAFOS 
 
1. Temos no contexto computacional diversas nomenclaturas e definições acerca dos conceitos e de suas respectivas 
aplicações. Assinale a alternativa que traz o conceito que define o que é um grafo. 
É um agrupamento formado por arestas e vértices. 
 
2. Os grafos, assim como outros elementos da estrutura de dados, têm diversos meios de representação. Assinale a 
alternativa que traz um exemplo prático de um grafo em nosso cotidiano. 
A cidade de São Paulo, a BR-116 e a cidade do Rio de Janeiro. 
 
3. As arestas podem ser definidas tanto como dirigidas/orientadas quanto como não dirigidas/não orientadas. 
Dessa forma, assinale a alternativa que traz as definições corretas destes conceitos. 
A orientação de um grafo é definida caso haja uma aresta de um ponto para outro indicando a direção da passagem 
do grafo. Enquanto um grafo não orientado pode ser definido apenas como sendo um grafo. 
 
4. A interligação dos vértices permite que haja diversas formas de acessá-los, uma delas possibilita que medidas 
sejam atendidas, como a marcação de vértices que foram ou não acessados. Assinale a alternativa que traz o tipo 
de estrutura de dados relacionado ao conceito citado. 
Algoritmo de busca por profundidade. 
 
5. Um grafo pode ser representado de forma adequada por meio de matrizes e listas, tendo cada uma delas uma 
maneira diferente de representação e acesso aos elementos. O armazenamento das arestas com um componente 
adicional acontece por meio de qual estrutura? 
Matriz de adjacência.