ESTRUTURA DE DADOS EM C

Prévia do material em texto

ESTRUTURAS DE DADOS 
 
1 
 Questão 
Pontos: 1,25 / 1,25 
 
A maioria dos softwares de aplicação possui comandos de "Desfazer" e 
"Refazer". O primeiro desfaz a última operação ou texto 
digitado, enquanto que, o segundo refaz uma operação ou texto 
desfeito, conforme sugerem os nomes dos comandos. 
Internamente, nos softwares, podem ser usadas duas estruturas de 
dados que armazenam as sucessivas operações de "Desfazer" e 
"Refazer", de modo que o próximo "Refazer" sempre recupera o último 
"Desfazer". Os tipos de estrutura de dados que podem ser usados para 
"Desfazer" e "Refazer" são, respectivamente: 
 
 Fila e Pilha 
 Pilha e Fila duplamente encadeada 
 Pilha e Fila 
 Pilha e Pilha 
 Fila e Fila 
 
 
2 
 Questão 
Pontos: 1,25 / 1,25 
 
Considere uma lista circular simplesmente encadeada com 
"n" elementos. Após "n - 1" remoções realizadas no final da 
lista podemos afirmar que: 
 
 O primeiro elemento estará apontando para o nulo. 
 O primeiro elemento estará apontando para si mesmo. 
 A lista restante será duplamente encadeada. 
 A lista estará vazia. 
 A lista restante não será mais uma lista circular. 
 
 
3 
 Questão 
Pontos: 1,25 / 1,25 
 
O acesso ao elemento de uma estrutura de dados tipo pilha se restringe ao mais 
recente na pilha. Já o acesso a um elemento de uma estrutura tipo fila ocorre ao dado 
há mais tempo na fila. Sobre pilhas e filas, avalie as assertivas a seguir: 
I - Uma forma de evitar o desperdício de memória numa fila em alocação sequencial é 
utilizar-se lista circular. 
II - Em uma pilha em alocação encadeada, a complexidade da remoção é O(n). 
III - Pilhas têm a propriedade de inverter a ordem de cadeias, enquanto as filas 
mantêm a ordem. 
 A opção que contém todas as assertivas corretas é: 
 
 
II e III. 
 
II. 
 I e III. 
 
I. 
 
I e II. 
 
 
4 
 Questão 
Pontos: 1,25 / 1,25 
 
Uma pilha segue a regra: "o ultimo a chegar é o primeiro a sair". Já as filas obedecem à 
regra: o primeiro a chegar é o primeiro a sair. Com base nesses argumentos, 
Uma pilha P e uma fila F originalmente com n elementos cada (n > 5), onde suas 
operações são: 
empilha(P, elemento): insere elemento na pilha P; 
desempilha(P): remove da pilha P e retorna o elemento removido; 
enfileira(F, elemento): insere elemento na fila F; 
desenfileira(F): remove da fila F e retorna o elemento removido; 
para i = 1 até n, faça 
empilha(P, desempilha(P)) 
enfileira(F, desenfileira(F)) 
fim-para 
Ao final da execução do pseudocódigo, os estados finais de P e F serão 
respectivamente: 
 
 elementos em ordem original e elementos em ordem original. 
 
elementos em ordem inversa e elementos em ordem original. 
 
elementos em ordem inversa e elementos em ordem inversa. 
 
elementos em ordem original e elementos em ordem inversa. 
 
Ambas as estruturas estarão vazias. 
 
 
5 
 Questão 
Pontos: 0,00 / 1,25 
 
Uma das formas de se representar um conjunto de dados com alocação dinâmica na 
memória são as listas ligadas ou encadeadas. Possuem em cada nó da lista ponteiros 
que indicam a ligação com outros demais nós da lista. Podemos diferenciar as listas 
simplesmente encadeadas das listas duplamente encadeadas pelo fato de 
 
 
os nós da lista duplamente encadeada formarem um anel com o último 
elemento ligado ao primeiro da lista. 
 
os nós da lista duplamente encadeada devem possuir um ponteiro nulo para o 
início e o fim da lista. 
 os nós da lista simplesmente encadeada formarem um anel com o último 
elemento ligado ao primeiro da lista. 
 
na lista duplamente encadeada seus nós possuem apenas um ponteiro 
indicando o nó anterior da lista. 
 na lista simplesmente encadeada seus nós possuem apenas um ponteiro 
indicando o próximo nó da lista. 
 
 
6 
 Questão 
Pontos: 1,25 / 1,25 
 
Um programa que foi passado para você implementa uma pilha, que é uma estrutura 
de dados linear com itens do mesmo tipo. A informação adicional é que as operações 
possíveis são: inserção - push(novo valor) ou remoção - pop(). 
Considerando as operações possíveis de uma estrutura pilha, se realizarmos a 
seguinte sequência de operações: 
push(A), push(B), push(C), pop(), pop(), push(D), pop(), pop(). 
Pode-se dizer que o interior da pilha se apresenta: 
 
 
com os dados A e D 
 
apenas com o dado A 
 vazio 
 
apenas com o dado D 
 com os dados A e B 
 
 
7 
 Questão 
Pontos: 1,25 / 1,25 
 
FIFO, uma abreviatura do inglês First-In-First-Out (primeiro a entrar, primeiro a sair), é 
um método para lidar com estruturas de dados onde o primeiro elemento é processado 
primeiro e o elemento mais novo é processado por último, também chamado de FILA. 
Considere uma função insere(x) que recebe como parâmetro um número inteiro e o 
insere em uma FILA. Considere também a função remove(), que retira um valor de uma 
FILA. 
Dada a Fila [4-6-8-11-13], cujos elementos mais a esquerda foram inseridos primeiro, 
executam-se os comandos na ordem: insere(5), insere(7), remove(). 
Após a execução desses comandos, qual será a Fila resultante? 
 
 
[4-6-8-11-13] 
 
[5-4-6-8-11-13] 
 
[4-6-8-11-13-5] 
 [6-8-11-13-5-7] 
 
[7-5-4-6-8-11] 
 
 
8 
 Questão 
Pontos: 1,25 / 1,25 
 
A tabela abaixo mostra as operações para a manipulação de uma pilha. 
 
Utilizando as definições acima, a seqüência de instruções a seguir foi implementada 
para avaliar o resultado de uma expressão, sendo A, B, C, D e E os operandos desta 
expressão. O resultado da avaliação é acumulado em F. 
PUSH A 
PUSH B 
SUB 
PUSH C 
PUSH D 
PUSH E 
MPY 
ADD 
DEC 
DIV 
POP F 
Com base no que foi exposto acima, se A, B, C, D e E apresentarem, respectivamente, 
os valores 9, 3, 2, 1 e 1, o valor a ser armazenado em F após a execução da instrução 
POP F será igual a: 
 
 
 
6. 
 
2. 
 3. 
 
5. 
 
4.