Atividades - Univesp - Semana 6 - Estrutura de Dados

Prévia do material em texto

18/09/2019 Teste: Atividade para avaliação - Semana 6
https://cursos.univesp.br/courses/2639/quizzes/8381/take 1/5
2 ptsPergunta 1
Os métodos "direita" e "esquerda" fazem a rotação direita e esquerda da árvore,
respectivamente. Os métodos "esquerdaDireita" e "direitaEsquerda" são mostrados a seguir
para evitar ambiguidades quanto às implementações.
 
PONT esquerdaDireita(PONT r) {
 r->esq = esquerda(r->esq);
 return(direita(r));
}
PONT direitaEsquerda(PONT r) {
 r->dir = direita(r->dir);
 return(esquerda(r));
}
PONT insere(PONT raiz, TIPOCHAVE ch) {
 if (!raiz) return(criaNo(ch));
 
 if (ch < raiz->chave) {
 raiz->esq = insere(raiz->esq,ch);
 if ((altura(raiz->esq) - altura(raiz->dir)) == 2) {
 if (ch < raiz->esq->chave) {
 raiz = ________________(raiz);
 }
 else {
 
 raiz = ________________(raiz);
 }
 }
 }
 else {
 if (ch > raiz->chave) {
 raiz->dir = insere(raiz->dir, ch);
 if ((altura(raiz->dir) - altura(raiz->esq)) == 2) {
18/09/2019 Teste: Atividade para avaliação - Semana 6
https://cursos.univesp.br/courses/2639/quizzes/8381/take 2/5
direita, esquerda, esquerdaDireita, direitaEsquerda
direita, direitaEsquerda, esquerda, esquerdaDireita
direita, esquerdaDireita, esquerda, direitaEsquerda
esquerda, direitaEsquerda, direita, esquerdaDireita
esquerda, esquerdaDireita, direita, direitaEsquerda
 if (ch > raiz->dir->chave) {
 raiz = ________________(raiz);
 }
 else {
 raiz = ________________(raiz);
 }
 }
 }
 }
 raiz->h = max(altura(raiz->esq),altura(raiz->dir))+1;
 return(raiz);
}
 
Qual das alternativas a seguir completa de forma correta o método "insere" de uma árvore de
busca AVL?
2 ptsPergunta 2
Uma maneira conveniente de imprimir uma árvore é usando a ordem "raiz - subárvore
esquerda - subárvore direita", como implementado no código a seguir:
 
void exibirArvore(PONT raiz){
 if (raiz != NULL) {
 printf("%d",raiz->chave);
 printf("(");
 exibirArvore(raiz->esq);
 exibirArvore(raiz->dir);
18/09/2019 Teste: Atividade para avaliação - Semana 6
https://cursos.univesp.br/courses/2639/quizzes/8381/take 3/5
76(45(27()75(60()))80(78(77()79())90(87(81())100())))
79(75(45(27()60())77(76()78()))90(81(80()87())100()))
77(75(45(27()60())76())80(79(78())90(87(81())100())))
76(60(27(45())75())80(78(77()79())90(87(81())100())))
77(75(45(27()60())76())87(79(78()81(80()))90(100())))
 printf(")");
 }
}
 
Uma dada árvore AVL, quando impressa pela função exibirArvore, devolve a seguinte string:
"79(75(45(27()60())76(78()))90(87(81())100()))". Qual das alternativas a seguir mostra a
impressão da árvore após a inserção dos elementos 77 e 80?
2 ptsPergunta 3
Assinale Verdadeiro ou Falso em relação aos algoritmos para gerenciamento de árvores AVL:
Falso A definição de árvore AVL prega que, em todos os nós, a diferença de altura
entre as subárvores esquerda e direita não pode ser maior que +2 ou menor que -2.
Falso Uma árvore AVL, após a inserção de um novo elemento, ficou
temporariamente com um único nó com fator de balanceamento -2, sendo este pai de
um único nó com fator de balanceamento -1. As propriedades de árvore AVL serão
restauradas após uma rotação à esquerda no nó filho, seguida da rotação à direita no nó pai.
Verdadeiro Ajustes nas árvores AVL precisarão ser feitos sempre que o módulo do fator
de balanceamento de um determinado nó for maior que ou igual a 2.
Falso Supondo que três nós ficaram com fator de balanceamento +2 após uma
inserção, o algoritmo de inserção realizará três rotações de qualquer tipo para restaurar as
propriedades de árvore AVL.
Verdadeiro Supondo que uma árvore AVL possui duzentos mil elementos, o algoritmo de
busca necessitará de menos do que 19 comparações para encontrar qualquer elemento.
18/09/2019 Teste: Atividade para avaliação - Semana 6
https://cursos.univesp.br/courses/2639/quizzes/8381/take 4/5
Verdadeiro Supondo que temos uma árvore AVL, a inserção de um único nó pode fazer
com que alguma propriedade seja violada, o que exige o monitoramento da árvore após cada
inserção para fazer os ajustes (rotações) necessários.
Verdadeiro Em uma árvore AVL, as buscas sempre serão feitas de forma eficiente, dado
que é garantido haver pouco desbalanceamento na árvore.
Verdadeiro Se uma rotação foi feita após uma inserção, não é mais necessário verificar a
necessidade de outras rotações, dado que o desbalanceamento terá sido corrigido em todos
os nós do ponto onde ocorreu a rotação até a raiz.
Verdadeiro O fator de balanceamento em uma árvore AVL pode ser definido como a
diferença de altura entre as subárvores da esquerda e da direita.
2 ptsPergunta 4
Assinale Verdadeiro ou Falso em relação às propriedades e definições em grafos:
Falso Em grafos não orientados, ciclos podem ter duas ou mais arestas.
Verdadeiro Se em um grafo não direcionado temos a aresta (u, v), podemos dizer que u é
adjacente a v e que v é adjacente a u.
Verdadeiro Um grafo não direcionado é dito conexo se houver um caminho conectando
cada par de vértice.
Falso A representação de um grafo por meio de matrizes de adjacência gera
matrizes simétricas no caso de grafos direcionados e matrizes não simétricas no caso de
grafos não direcionados.
Verdadeiro Em um grafo direcionado, o grau de um vértice é definido como número de
arestas que saem do vértice mais o número de arestas que chegam no vértice.
Falso Grafos ponderados (direcionados ou não) podem ser representados como
listas de adjacência, mas não como matrizes de adjacências, dado que estas não possuem a
capacidade de representar os pesos das arestas.
18/09/2019 Teste: Atividade para avaliação - Semana 6
https://cursos.univesp.br/courses/2639/quizzes/8381/take 5/5
Salvo em 22:44 
Verdadeiro Um grafo direcionado é dito fortemente conexo se para quaisquer vértices a e
b existe um caminho que vai de a até b e um caminho que vai de b até a.
Verdadeiro Um grafo direcionado é dito conexo se para quaisquer vértices a e b existe um
caminho que vai de a até b ou um caminho que vai de b até a.
Falso Um grafo direcionado é dito fracamente conexo se para quaisquer vértices a e
b existe um caminho que vai de a até b ou um caminho que vai de b até a.
2 ptsPergunta 5
Um ciclo acontece se pudermos encontrar um caminho que saia de um vértice e volte para ele mesmo. Nesse caso,
um self-loop em grafos direcionados é um ciclo.
O somatório dos graus de todos os vértices de um grafo não direcionado sempre retornará um número par.
Encontrar o predecessor de um determinado vértice é mais fácil com listas de adjacência do que com matrizes de
adjacência.
Um grafo acíclico, conexo e não direcionado é uma árvore.
Assinale a alternativa FALSA em relação aos conceitos de grafos:
Enviar teste