| Universidade Federal do Rio Grande do Sul Instituto de Informática |
Prof. Dennis G. Balreira Semestre 2026/2 — Turma C |
| Nome: | Cartão: |
Responda de forma breve e objetiva. Uma a três frases por questão são suficientes.
malloc/free) é essencial para implementar TADs como listas encadeadas? O que acontece se o programador não chamar free ao final do uso de um nodo?ListaEnc) e qual o papel do ponteiro ini.inserirInicio(ListaEnc *lista, Produto p) recebe o descritor por ponteiro em vez de por valor? O que ocorreria de errado se recebesse por valor?ant (anterior) em relação à lista simplesmente encadeada, especialmente na remoção?NULL para indicar o fim?PilhaEnc? Onde (início ou fim da lista interna) ocorrem push e pop, e por quê?FilaEnc, onde ocorre o enqueue e onde ocorre o dequeue? Por que manter um ponteiro fim é fundamental para a eficiência?Para todas as questões abaixo, considere os tipos e TADs definidos em aula:
typedef struct {
int cod; char nome[50]; float preco;
} Produto;
/* Lista simplesmente encadeada */
typedef struct str_Nodo Nodo;
struct str_Nodo { Nodo *prox; Produto dado; };
typedef struct { Nodo *ini; } ListaEnc;
/* TAD Pilha (implementada com lista encadeada) */
typedef struct str_NodoPilha NodoPilha;
struct str_NodoPilha { NodoPilha *prox; Produto dado; };
typedef struct { NodoPilha *topo; } PilhaEnc;
void inicializaPilha(PilhaEnc *p); /* p->topo = NULL */
int estaVaziaPilha(PilhaEnc *p); /* retorna 1 se vazia */
void push(PilhaEnc *p, Produto d); /* insere no topo */
Produto pop(PilhaEnc *p); /* remove e retorna topo */
/* TAD Fila (implementada com lista encadeada) */
typedef struct str_NodoFila NodoFila;
struct str_NodoFila { NodoFila *prox; Produto dado; };
typedef struct { NodoFila *ini; NodoFila *fim; } FilaEnc;
void inicializaFila(FilaEnc *f); /* f->ini = f->fim = NULL */
int estaVaziaFila(FilaEnc *f); /* retorna 1 se vazia */
void enqueue(FilaEnc *f, Produto d); /* insere no fim */
Produto dequeue(FilaEnc *f); /* remove e retorna ini */
/* Árvore Binária de Pesquisa */
typedef struct str_NodoArv NodoArv;
struct str_NodoArv { Produto dado; NodoArv *esq; NodoArv *dir; };
maiorPreco, que percorre a lista e retorna o produto de maior preco. Assuma lista não vazia.
Produto maiorPreco(const ListaEnc *lista);
somarPrecosImpares, que percorre a lista e retorna a soma dos preco dos produtos cujo cod seja ímpar. Retorne 0.0 para lista vazia.
float somarPrecosImpares(const ListaEnc *lista);
removerMenoresQuePreco, que remove da lista todos os produtos com preco estritamente menor que p. Libere cada nodo com free. Trate múltiplos consecutivos no início.
void removerMenoresQuePreco(ListaEnc *lista, float p);
concatenarListas, que concatena b ao final de a sem criar novos nodos (apenas redirecione ponteiros). Trate os casos em que a ou b estejam vazias.
void concatenarListas(ListaEnc *a, const ListaEnc *b);
inverterLista, que inverte a ordem dos nodos in-place, sem criar novos nodos. Use três ponteiros auxiliares para redirecionar os campos prox.
void inverterLista(ListaEnc *lista);
moverPrimeiroParaFim, que move o primeiro nodo da lista para o final sem criar ou destruir nodos. Não faça nada se a lista for vazia ou unitária.
void moverPrimeiroParaFim(ListaEnc *lista);
inserirAntesDeCod, que insere um novo produto imediatamente antes do primeiro nodo cujo cod seja igual ao parâmetro. Se o código não existir, insira o novo produto no final da lista.
void inserirAntesDeCod(ListaEnc *lista, Produto p, int cod);
segundoMaiorPreco, que percorre a lista e retorna o segundo maior preço distinto. Assuma preços não-negativos; retorne -1.0 se não houver segundo preço distinto.
float segundoMaiorPreco(const ListaEnc *lista);
maiorPrecoFila, que retorna o produto de maior preco da fila sem alterar a ordem dos elementos. Use apenas operações do TAD.
Produto maiorPrecoFila(FilaEnc *fila);
maiorPrecoPilha, que retorna o produto de maior preco da pilha sem alterar a ordem dos elementos. Use apenas operações do TAD.
Produto maiorPrecoPilha(PilhaEnc *pilha);
removerDaFilaPorCod, que remove da fila o primeiro produto cujo cod seja igual ao parâmetro, preservando a ordem dos demais. Use apenas operações do TAD.
void removerDaFilaPorCod(FilaEnc *fila, int cod);
removerDaPilhaPorCod, que remove da pilha o primeiro produto (do topo para a base) cujo cod seja igual ao parâmetro, preservando a ordem dos demais. Use apenas operações do TAD.
void removerDaPilhaPorCod(PilhaEnc *pilha, int cod);
separarParImpar, que separa os elementos de fila em duas novas filas: pares (cod par) e impares (cod ímpar), preservando a ordem original em cada fila. A fila original é consumida.
void separarParImpar(FilaEnc *fila, FilaEnc *pares, FilaEnc *impares);
somarPrecosImparesPreservando, que retorna a soma dos preco dos produtos com cod ímpar, preservando o conteúdo e a ordem da fila. Use apenas operações do TAD.
float somarPrecosImparesPreservando(FilaEnc *fila);
temConsecutivosIguais, que retorna 1 se existem dois produtos consecutivos com o mesmo cod na fila, e 0 caso contrário. A fila deve ser preservada. Use apenas operações do TAD.
int temConsecutivosIguais(FilaEnc *fila);
mesmasElementos, que retorna 1 se a pilha e a fila possuem a mesma quantidade de elementos e os mesmos cod na mesma ordem (topo da pilha corresponde à frente da fila), e 0 caso contrário. Ambas devem ser preservadas. Use apenas operações do TAD.
int mesmasElementos(PilhaEnc *pilha, FilaEnc *fila);
abpTodosPares, que retorna 1 se todos os produtos possuem cod par, e 0 se algum é ímpar. Retorne 1 para árvore vazia.
int abpTodosPares(const NodoArv *raiz);
abpContarComUmFilho, que retorna a quantidade de nodos com exatamente um filho (esquerdo ou direito, mas não ambos).
int abpContarComUmFilho(const NodoArv *raiz);
abpContarMenoresQue, que retorna a quantidade de produtos cujo cod é estritamente menor que x. Dica: use a propriedade da ABP para podar subárvores.
int abpContarMenoresQue(const NodoArv *raiz, int x);
abpMaiorCod, que retorna o maior cod aproveitando a propriedade da ABP (sem percorrer toda a árvore). Assuma árvore não vazia.
int abpMaiorCod(const NodoArv *raiz);
abpImprimirIntervalo, que imprime em ordem crescente todos os produtos com cod ∈ [minCod, maxCod]. Dica: use a propriedade da ABP para evitar subárvores fora do intervalo.
void abpImprimirIntervalo(const NodoArv *raiz, int minCod, int maxCod);
abpContarMaioresQue, que retorna a quantidade de produtos cujo cod é estritamente maior que x. Dica: use a propriedade da ABP para podar subárvores.
int abpContarMaioresQue(const NodoArv *raiz, int x);
abpExisteNoIntervalo, que retorna 1 se existir pelo menos um produto com cod ∈ [minCod, maxCod], e 0 caso contrário. Dica: use a propriedade da ABP para retornar antecipadamente.
int abpExisteNoIntervalo(const NodoArv *raiz, int minCod, int maxCod);
abpSomaCods, que retorna a soma de todos os cod armazenados na árvore. Retorne 0 para árvore vazia.
int abpSomaCods(const NodoArv *raiz);