Centro Universitário Barão de Mauá

NOTA FINAL
CURSO DE CIÊNCIA DA COMPUTAÇÃO
Aluno:
Componente Curricular: Estrutura de Dados

Professor (es): Felipe Carvalho Pellison

Período: 202402 Turma: Data: 04/10/2024

ED-TA-N1-2Sem-2024

RELATÓRIO DE DEVOLUTIVA DE PROVA

PROVA 17722 - CADERNO 005

1ª QUESTÃO
Enunciado:

Suponha que você está implementando um sistema que gerencia uma pilha com informações
sobre coordenadas de latitude (do tipo float) adquiridas em um mapeamento geográfico.
Considere que a implementação adotada da pilha é estática e contígua e o seguinte trecho de
código do arquivo de cabeçalho (.h):

const int MaxStack = 100;

class Stack{

public:

Stack();

void Push(float x);

void Pop(float &x);

//... demais métodos

private:

int top;

float Entry[MaxStack+1];

};

Escreva os códigos de implementação em C++ (referentes ao arquivo .cpp da classe Stack) dos
métodos:

a) Construtor da pilha – inicializa a pilha vazia.

b) Push – insere o elemento x na pilha.

c) Pop – remove elemento da pilha e atribui seu valor a x.

Obs.: Se desejar, fique à vontade para implementar outros métodos de suporte. Lembre-se
das boas práticas de programação. Faça as suposições que julgar necessárias.

Alternativas:
--

Pgina 1 de 8
Resposta comentada:

a) Stack::Stack()
{
top = 0;
}

b) void Stack::Push(float x)
{ if (Full())
{ cout << “Pilha Cheia”;
abort();
}
top++;
Entry[top] = x;
}

c)void Stack::Pop(float &x)

{ if (Empty())
{ cout << “Pilha Vazia”;
abort();
}
x = Entry[top] ;
top = top - 1;
}

2ª QUESTÃO
Enunciado:

Durante a prática profissional, você foi convidado a desenvolver um módulo de um projeto que
usará a estrutura de dados Fila. Com base nas características da estrutura, avalie as asserções
a seguir e a relação proposta entre elas.

I. Filas são listas lineares com disciplina de acesso FILO (first in, last out).

PORQUE

II. O comportamento de fila é obtido armazenando-se a posição das extremidades da estrutura e

permitindo entradas apenas na extremidade “fim” e retiradas apenas na extremidade “início”.

A respeito dessas asserções, assinale a opção correta.

Pgina 2 de 8
Alternativas:
(alternativa A)
As asserções I e II são falsas.

(alternativa B)
A asserção I é uma proposição verdadeira e a II é uma proposição falsa.

(alternativa C)
As asserções I e II são verdadeiras, mas a II não é uma justificativa correta da I.

(alternativa D)
As asserções I e II são verdadeiras, e a II é uma justificativa correta da I.

(alternativa E) (CORRETA)
A asserção I é uma proposição falsa e a II é uma proposição verdadeira.

Resposta comentada:
Filas são listas lineares com disciplina de acesso FIFO (first in, first out).

3ª QUESTÃO
Enunciado:

Suponha que você está implementando uma aplicação que gerencia uma lista linear de valores
numéricos inteiros. Considere que a implementação adotada da lista linear é dinâmica e o
seguinte trecho de código do arquivo de cabeçalho (.h):

Pgina 3 de 8
class List{

public:

void SetPosition(int p, ListPointer &current);

void Retrieve(int p, int &x);

void Replace(int p, int x);

//... demais métodos

private:

struct ListNode

{ int Entry;

ListNode *NextNode;

};

typedef ListNode *ListPointer;

ListPointer head;

int count;

};

Fonte: Elaborado pelo autor.

Escreva os códigos de implementação em C++ (referentes ao arquivo .cpp da classe List)

de cada um dos métodos identificados em I, II e III, logo abaixo. Se desejar, fique à vontade
para implementar outros métodos de suporte. Lembre-se das boas práticas de programação.
Faça as suposições que julgar necessárias.

I. SetPosition – retorna o endereço do p-ésimo elemento da lista em current.

II. Retrieve – retorna o valor p-ésimo elemento da lista em x.

III. Replace – substitui o p-ésimo elemento da lista pelo valor de x.

Alternativas:
--

Pgina 4 de 8
Resposta comentada:

a) void List::SetPosition(int p, ListPointer &current)

// pré-condição: p é uma posição válida na lista
// pós-condição: o ponteiro current aponta para o nó na lista
// com posição p
{ int i;
if (p < 1 || p > count+1)
{ cout << “Posição inválida”;
abort();
}
current = head;
for(i=2; i<=p; i++)
current = current->NextNode;
}

b) void List::Retrieve(int p, int &x)

{ ListPointer q;
if(p < 1 || p > count)
{ cout << “Posição inválida”;
abort();
}
SetPosition(p,q);
x = q->Entry;
}

c) void List::Replace(int p, int x)

{ ListPointer q;
if(p < 1 || p > count)
{ cout << “Posição inválida”;
abort();
}
SetPosition(p,q);
q->Entry = x;
}

4ª QUESTÃO
Enunciado:

Durante a prática profissional, você foi convidado a desenvolver um módulo de um projeto que
usará a estrutura de dados Pilha. Com base nas características da estrutura, avalie as asserções
a seguir e a relação proposta entre elas.

I. Pilhas são listas lineares com disciplina de acesso FIFO (first in, first out).

PORQUE

II. A pilha armazena apenas a posição de uma de suas extremidades (chamada topo), que é o
único local onde são realizadas todas as operações de entrada e saída.

A respeito dessas asserções, assinale a opção correta.

Pgina 5 de 8
Alternativas:
(alternativa A)
As asserções I e II são verdadeiras, e a II é uma justificativa correta da I.

(alternativa B)
A asserção I é uma proposição verdadeira e a II é uma proposição falsa.

(alternativa C) (CORRETA)
A asserção I é uma proposição falsa e a II é uma proposição verdadeira.

(alternativa D)
As asserções I e II são verdadeiras, mas a II não é uma justificativa correta da I.

(alternativa E)
As asserções I e II são falsas.

Resposta comentada:
Pilhas são listas lineares com disciplina de acesso LIFO (last in, first out).

5ª QUESTÃO

Pgina 6 de 8
Enunciado:

Duas pilhas de implementação estática que não necessitam de toda sua capacidade
simultaneamente podem ser representadas economicamente em um único vetor compartilhado.
As pilhas são posicionadas nas extremidades do vetor e crescem em direção ao centro.
Supondo-se um vetor com posições indexadas de 0 até MAX-1, o topo da primeira pilha é
inicializado com -1 e o topo da segunda é inicializado com MAX, correspondendo as situações de
pilha vazia de cada estrutura. As duas pilhas estão simultaneamente cheias quando não há mais
posições livres entre elas, ou seja, quando (topo2 - topo1 == 1).

//Arquivo de cabeçalhos (.h)

class PilhaDupla{ //Arquivo de implementação (.cpp)

public: PilhaDupla::PilhaDupla(){
PilhaDupla(); topo1=-1;
int tamanhoPilhaDupla(); topo2=MAX;
/*restante dos métodos*/ }
private: int PilhaDupla::tamanhoPilhaDupla(){
int topo1; return /*instrução que retorna o tamanho
int topo2; das duas pilhas juntas*/;

int Entry[MAX]; }

};

Considere o texto, as estruturas e códigos, escolha a alternativa que contém a implementação da

instrução correta para o método tamanhoPilhaDupla que retorna o tamanho de duas pilhas
juntas.

Alternativas:
(alternativa A)
topo1 + topo2

(alternativa B)
2*MAX + 1

(alternativa C)
topo1 + MAX + topo2 + 1

(alternativa D)
topo1 + MAX

(alternativa E) (CORRETA)
topo1 + 1 + MAX - topo2

Pgina 7 de 8
Resposta comentada:
A instrução topo1 + 1 + MAX - topo2 reflete corretamente a quantidade de elementos pois utiliza-
se dos limites definidos do vetor para realizar o cálculo da quantidade de elementos totais.

6ª QUESTÃO
Enunciado:

Diferenciar e aplicar as estruturas de dados corretamente aos desafios do dia a dia é tarefa
corriqueira do profissional da área de ciência da computação. A escolha correta entre os diversos
algoritmos e como são implementados, contribui para a qualidade do produto final.

Considerando as informações do texto, avalie as afirmações a seguir.

I. O nó sentinela, criado ao final de uma lista, é usado para armazenar a chave de busca e assim
acelerar o respectivo algoritmo, uma vez que reduz o número de comparações necessárias.

II. A única diferença significativa entre as implementações estática e dinâmica de listas ligadas
está no fato de que a implementação estática “simula” uma lista ligada em vetor, e nos obriga a
gerenciar as posições livres e ocupadas. Isso deixa de ser necessário no caso da alocação
dinâmica “real”.

III. Em uma lista ligada de implementação dinâmica, não há mais uso de vetores. Cada elemento
da lista é uma estrutura do tipo Node, que contém os dados de cada elemento (Entry) e um
ponteiro NextNode para o próximo nó da lista.

É correto o que se afirma em:

Alternativas:
(alternativa A) (CORRETA)
I, II e III.

(alternativa B)
I, apenas.

(alternativa C)
I e II, apenas.

(alternativa D)
III, apenas.

(alternativa E)
II e III, apenas.

Resposta comentada:
Todas as afirmações estão corretas.

Pgina 8 de 8