FACULDADE LOURENÇO FILHO
ENADE 2011
Prof. Ricardo Viana
DATA: 01/10/2011
Algoritmos e Estruturas de Dados (Desenvolvimento e Complexidade de Algoritmos,
Estruturas de Dados Lineares e Não Lineares, Pesquisa e Ordenação, Grafos).
QUESTÃO 1
Um programador propôs um algoritmo não-recursivo para o percurso em pré-ordem
de uma árvore binária com as seguintes características.
- Cada nó da árvore binária é representado por um registro com três campos: chave,
que armazena seu identificador; esq e dir, ponteiros para os filhos esquerdo e direito,
respectivamente.
- O algoritmo deve ser invocado inicialmente tomando o ponteiro para o nó raiz da
árvore binária como argumento.
- O algoritmo utiliza push() e pop() como funções auxiliares de empilhamento e
desempilhamento de ponteiros para nós de árvore binária, respectivamente.
A seguir, está apresentado o algoritmo proposto, em que λ representa o ponteiro nulo.
Procedimento preordem (ptraiz : PtrNoArvBin)
Var ptr : PtrNoArvBin;
ptr := ptraiz;
Enquanto (ptr ≠ λ) Faça
escreva (ptr↑.chave);
Se (ptr↑.dir ≠ λ) Então
push(ptr↑.dir);
Se (ptr↑.esq ≠ λ) Então
push(ptr↑.esq);
ptr := pop();
Fim_Enquanto
Fim_Procedimento
Com base nessas informações e supondo que a raiz de uma árvore binária com n nós
seja passada ao procedimento preordem(), julgue os itens seguintes.
I. O algoritmo visita cada nó da árvore binária exatamente uma vez ao longo do
percurso.
II. O algoritmo só funcionará corretamente se o procedimento pop() for projetado
de forma a retornar λ caso a pilha esteja vazia.
III. Empilhar e desempilhar ponteiros para nós da árvore são operações que
podem ser implementadas com custo constante.
IV. A complexidade do pior caso para o procedimento preordem() é O(n).
Assinale a opção correta.
(A) Apenas um item está certo.
(B) Apenas os itens I e IV estão certos.
(C) Apenas os itens I, II e III estão certos.
(D) Apenas os itens II, III e IV estão certos.
(E) Todos os itens estão certos.
1
QUESTÃO 2
Os números de Fibonacci constituem uma seqüência de números na qual os dois
primeiros elementos são 0 e 1 e os demais, a soma dos dois elementos imediatamente
anteriores na seqüência. Como exemplo, a seqüência formada pelos 10 primeiros
números de Fibonacci é: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34. Mais precisamente, é possível
definir os números de Fibonacci pela seguinte relação de recorrência:
fib (n) = 0, se n = 0
fib (n) = 1, se n = 1
fib (n) = fib (n - 1) + fib (n - 2), se n > 1
Abaixo, apresenta-se uma implementação em linguagem funcional para essa relação
de recorrência:
fib :: Integer -> Integer
fib 0 = 0
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)
Considerando que o programa acima não reutilize resultados previamente
computados, quantas chamadas são feitas à função fib para computar fib 5?
(A) 11
(B) 12
(C) 15
(D) 24
(E) 25
QUESTÃO 3
Algoritmo ENADE2008
variaveis
V[0..4] <- {2,0,4,3,1}:inteiro
I,J,A : inteiro
inicio
para I <- 0 ate 3 passo 1 faca
para J <- 0 ate 3-I passo 1 faca
se (V[J] > V[J+1] ) entao
A <- V[J]
V[J+1] <- V[J]
A <- V[J+1]
fim se
escreva V[0],V[1],V[2],V[3],V[4]
fim para
fim para
fim algoritmo
Com relação ao algoritmo acima, que manipula um vetor de inteiros, julgue os itens a
seguir:
I. Quando as variáveis I e J valerem, respectivamente, 0 e 1, a linha 13
apresentará a seqüência de valores 0,2,4,3,1.
II. Quando as variáveis I e J valerem, respectivamente, 1 e 0, a linha 13
apresentará a seqüência de valores 0,2,3,1,4.
III. Quando as variáveis I e J valerem, respectivamente, 1 e 2, a linha 13
apresentará a seqüência de valores 0,2,1,3,4.
2
Assinale a opção correta:
(A) Apenas um item está certo.
(B) Apenas os itens I e II estão certos.
(C) Apenas os itens I e III estão certos.
(D) Apenas os itens II e III estão certos.
(E) Todos os itens estão certos.
QUESTÃO 4
Algoritmo ENADE2008
variaveis
varA, varB, varC: inteiro
varF : real
varS : literal
varL : lógico
inicio
varS <- “1000”
varA <- 4
varF <- 3.5
varC <- 0
varL <- VERDADEIRO
se((varC < varA) E varL OU (varS > varC)) entao
varB <- varF/varA
senao
varB <- varA/varC
fim se
fim algoritmo
O código acima:
(A) não apresenta erros de nenhum tipo.
(B) apresenta erros de atribuição de tipo inválido, divisão por zero e expressão
relacional inválida.
(C) apresenta erros de atribuição de tipo inválido, divisão por zero e estrutura
condicional.
(D) apresenta erros de estrutura condicional e expressão relacional inválida.
(E) apresenta somente erro de divisão por zero.
3
QUESTÃO 5
funcao busca(V[0..9] : inteiro, K : inteiro): inteiro
variaveis
C, F, K, M : inteiro
Inicio
F <- 9
[________________________]
enquanto((V[M] <> K) ou (F > C))
[_________________________]
se(K < V[M]) então
F <- M – 1;
senão
[_________________________]
fim enquanto
se(V[M] <> K) então
retorne(0)
senão
retorne(M)
fim se
fim
O algoritmo representado pelo pseudocódigo acima está incompleto, pois faltam 3
linhas de código. A função busca desse algoritmo recebe um vetor ordenado de forma
crescente e um valor a ser pesquisado. A partir disso, essa função verificará se o
número armazenado no ponto mediano do vetor é o número procurado. Se for o
número procurado, retornará o índice da posição do elemento no vetor e encerrará a
busca. Se não for, a função segmentará o vetor em duas partes a partir do ponto
mediano, escolherá o segmento no qual o valor procurado está inserido, e o processo
se repetirá.
A partir dessas informações, assinale a opção que contém os comandos que
completam, respectivamente, as linhas 6, 8 e 12 do algoritmo.
(A)
(B)
(C)
(D)
(E)
C <- 0, M <- (C + F) / 2, C <- M + 1
C <- 1, M <- (C + F) / 2, C <- M - 1
C <- 0, C <- M + 1, M <- (C + F) / 2
C <- 1, C <- M + 1, M <- (C + F) / 2
C <- 1, M <- (C + F) / 2, C <- M + 1
QUESTÃO 6
Os métodos de projeto e análise de algoritmos são necessários para o
desenvolvimento de algoritmos eficientes, pois eles permitem que se resolva
problemas computacionais, reduzindo complexidade e tempo de execução. Acerca
desses métodos, assinale a opção incorreta.
(A) A abordagem de Divisão e Conquista propõe dividir o problema em vários
subproblemas, resolvendo-os e combinando suas soluções para criar a solução
final do problema original.
(B) A Programação Dinâmica é uma técnica tipicamente aplicada a problemas de
otimização em que pode haver várias soluções possíveis.
(C) O método Guloso nem sempre encontra a solução ótima, mas faz sempre a
melhor escolha momentânea.
4
(D) A Programação Dinâmica e o Método Guloso têm em comum o fato de que se
aplicam a problemas em que se observa a existência de sobreposição de
subproblemas, ou seja, subproblemas que se repetem.
(E) Os métodos de Divisão e Conquista e Programação Dinâmica apresentam a
mesma eficiência quando resolvem problemas combinando soluções de
subproblemas dependentes uns dos outros.
QUESTÃO 7
Suponha que T seja uma árvore AVL inicialmente vazia, e considere a inserçã dos
elementos 10,20,30,5,15,2 em T, nesta ordem. Qual das sequências abaixo
corresponde a um percurso de T em pré-ordem:
(A)
(B)
(C)
(D)
(E)
10,5,2,20,15,30
20,10,5,2,15,30
2,5,10,15,20,30
30,20,15,10,5,2
15,10,5,2,20,30
QUESTÃO 8
Uma árvore binária é declarada em C como:
onde esq e dir representam ligações para os filhos esquerdo e direito de um nó da
árvore, respectivamente. Qual das seguintes alternativas é uma implementação
correta da operação que inverte as posições dos filhos esquerdo e direito de um nó p
da árvore, onde t é um apontador auxiliar.
(A)
(B)
(C)
(D)
(E)
t = p; p -> esq = p -> dir; p -> dir = p -> esq
p -> dir = t; p -> esq = p -> dir; p -> dir = t
p -> esq = p -> dir; t = p -> esp p -> dir = t
t = p -> dir; p -> esq = p -> dir; p -> dir = t
t = p -> dir p -> dir = p -> esq; p -> esq = t
QUESTÃO 9
Em uma lista circular duplamente encadenada com n elementos, o espaço ocupado
apenas pelos apontadores é (assuma que um apontador ocupa p bytes):
(A) np
(B) 2np
(C) 4np
(D) 6np
(E) (np)2
5
QUESTÃO 10
Considere n chaves armazenadas:
I.
de maneira arbitrária suma lista encadeada simples,
II.
de maneira arbitrária
Considere também as mesmas chaves
III.
armazenadas de maneira ordenada numa lista encadeada simples,
IV.
armazenadas de maneira ordenada numa lista encadeada dupla.
Qual das alternativas preenche a seguinte tabela com a complexidade de busca no pior
caso, em cada uma das situações I, II, III e IV descritas acima?
(A)
(B)
(C)
(D)
(E)
QUESTÃO 11
Em um heap com n vértices existem:
(A) exatamente piso(n/5) folhas
(B) aproximadamente log n folhas
(C) não mais que piso(n/5) folhas
(D) exatamente teto(n/2) folhas
(E) não menos que 2n/3 folhas
QUESTÃO 12
Considere as afirmativas:
I. O modelo matemático de uma lista é a seqüência linear de itens, cuja principal
propriedade estrutural é a posição relativa dos elementos dentro da seqüência.
II. A fila e a pilha são consideradas casos especiais da lista
III. Numa fila a inserção e a retirada são feitas no mesmo extermo.
IV. Numa lista a inserção e a retirada podem ser feitas em qualquer posição.
V. Numa pilha apenas a inserção pode ser feita em qualquer posição.
Quais são as afirmativas verdadeiras?
(A) somente I e III.
(B) somente II, III e IV.
(C) somente I, II e IV.
(D) somente II, IV e V.
(E) todas.
6
QUESTÃO 13
Considere as seguintes estruturas de dados:
I.
II.
III.
IV.
Tabela hash
Fila
Árvore de pesquisa
Pilha
Qual ou quais das estruturas acima requer mais do que tempo médio constante para
inserção de um elemento?
(A) Somente I
(B) Somente II
(C) Somente III
(D) Somente IV
(E) Todas.
QUESTÃO 14
Qual das seguintes expressões posfixas é equivalente à expressão infixa A+(B/C)*((DE)/F)?
(A) ABC/-DE*F+/
(B) ABC/DE-/F+*
(C) ABC/DE-F/*+
(D) ABC/D-EF*/+
(E) ABD/CE+/F-*
QUESTÃO 15
Considere as seguintes definições de ordens de percurso de uma árvore binária:
Considere a seguinte árvore binária: O percurso da árvore binária apresentada em:
7
Ordem A resulta em qual seqüência de visitas?
(A)
(B)
(C)
(D)
(E)
ABDCEKLMFIJGH
ABCDEFGHIJKLM
ABDCEKLMFGHIJ
ABECDFKGILMHJ
ABDCEFIJGHKLM
QUESTÃO 16
Dada uma lista linear de n+1 elementos ordenados e alocados sequencialmente, qual é
o número médio (número esperado) de elementos que devem ser movidos para que
se faça uma inserção na lista, considerando-se igualmente prováveis as n+1 posições
de inserção?
(A) n/2
(B) (n+2)/2
(C) (n-1)/2
(D) n(n+3+2/n)/2
(E) (n+1)/2
QUESTÃO 17
Em uma estrutura de árvore binária de busca, foram inseridos os elementos
"h","a","b","c","i","j", nesta seqüência. O tamanho do caminho entre um nó qualquer
da árvore e a raiz é dado pelo número de arestas neste caminho. Qual o tamanho do
maior caminho na árvore, após a inserção dos dados acima?
(A) 2
(B) 6
(C) 4
(D) 5
(E) 3
QUESTÃO 18
Arvores binárias podem ser usadas para guardar e recuperar informações com número
de operações proporcional à altura da árvore. Quais das seguintes figuras representam
árvores binárias de altura balanceada ou do tipo AVL (Adelson-Velski e Landis):
(A) Somente (I) e (IV) são árvores binárias AVL.
(B) Somente (I) é árvore binária AVL.
(C) Somente (I), (II) e (III) são árvores binárias AVL.
(D) Somente (II) e (III) são árvores binárias AVL.
(E) Todas (I), (II), (III) e (IV) são árvores binárias AVL.
8
QUESTÃO 19
Dado um conjunto C contendo n inteiros distintos, qual das seguintes estruturas de
dados em memória principal permite construir um algoritmo para encontrar o valor
máximo de C em tempo constante?
(A) Um vetor não ordenado.
(B) Um vetor ordenado.
(C) Uma árvore binária de busca balanceada.
(D) Uma lista encadeada simples ordenada em ordem crescente.
(E) Uma árvore rubro-negra.
QUESTÃO 20
Suponha que a tabela a seguir apresenta a freqüência de cada letra de um alfabeto em
uma string. Quantos bits seriam necessários para representar essa string usando um
código de Huffman?
(A) 392
(B) 147
(C) 113
(D) 108
(E) Nenhuma das respostas anteriores.
QUESTÃO 21
Um estudante de computação precisa resolver um problema bastante importante, que
é executar as operações que estão descritas abaixo, cuja estrutura é uma pilha. Tão
logo ele retire algum elemento desta pilha, estes deverão ser inseridos em uma fila,
cuja entrada é pela esquerda e a saída, pela direita. Assinale a alternativa que contém
a sequência correta de entrada dos elementos na fila.
PUSH P
PUSH E
PUSH R
PUSH T
PUSH O
POP
POP
PUSH S
PUSH O
PUSH L
POP
POP
POP
(A) S - O - L - T – O
(B) O - T - R - E – P
(C) P - E - R - T – O
(D) O - T - L - O – S
(E) P - O - R - L – S
9
QUESTÃO 21
Os algoritmos a seguir representam os três caminhamentos para árvores binárias.
caminhamento(binário)
se binário.esquerda ≠ NULL então caminhamento(binário.esquerda)
escrever binário.valor
se binário.direita ≠ NULL então caminhamento(binário.direita)
caminhamento(binário)
escrever binário.dado
se binário.esquerda ≠ NULL então caminhamento(binário.esquerda)
se binário.direita ≠ NULL então caminhamento(binário.direita)
caminhamento(binário)
se binário.esquerda ≠ NULL então caminhamento(binário.esquerda)
se binário.direita ≠ NULL então caminhamento(binário.direita)
escrever binário.valor
Assinale a alternativa que contém os nomes dos 3 caminhamentos, respectivamente.
(A) pré-ordem, pós-ordem, em-ordem
(B) pré-ordem, em-ordem, pós-ordem
(C) pós-ordem, pré-ordem, em-ordem
(D) em-ordem, pré-ordem, pós-ordem
(E) em-ordem, pós-ordem, pré-ordem
QUESTÃO 23
A busca antecipada de instruções é uma técnica utilizada nos processadores dos
microcomputadores atuais, de forma a acelerar a execução de um programa. As
instruções são pré-carregadas da memória
A) cache para a memória principal.
B) cache para a memória virtual.
C) principal para a memória virtual.
D) principal para a memória cache.
E) virtual para a memória principal.
QUESTÃO 24
Considere as seguintes afirmativas sobre o algoritmo de pesquisa binária:
I. a entrada deve estar ordenada
II. uma pesquisa com sucesso é feita em tempo logarítmico na media
III. uma pesquisa sem sucesso é feita em tempo logarítmico na media
IV. o pior caso de qualquer busca é logarítmico
As afirmativas corretas são:
(A) Somente I e II.
(B) Somente I, II e III.
(C) Somente II e III.
(D) Somente III e IV.
(E) Todas as afirmativas estão corretas.
10
QUESTÃO 25
Seja V =< v1, . . . , vn > uma lista qualquer de inteiros distintos que se deseja ordenar
em ordem não descrescente. Analise as seguintes afirmativas.
I. Considere o algoritmo Quicksort. Suponha uma execução do algoritmo sobre V
tal que a cada sorteio do pivot, a mediana do (sub)problema em questão é
escolhida. Então, a complexidade dessa execução é O(n lg n).
II. Considere o algoritmo Quicksort. Suponha uma execução do algoritmo sobre V
tal que a cada sorteio do pivot, os dois subproblemas gerados têm tamanho
1/10 e 9/10 respectivamente do tamanho do (sub)problema em questão.
Então, a complexidade dessa execução é O(n2)
III. Considere o algoritmo Mergesort. A complexidade do pior caso do algoritmo é
O(n lg n) e a complexidade do melhor caso (vetor já está ordenado) é O(n).
IV. Considere o algoritmo Heapsort. A complexidade do pior caso do algoritmo é
O(n lg n) e a complexidade do melhor caso (vetor já está ordenado) é O(n).
V. Se para todo i, vi é O(n), então a complexidade do algoritmo Bucketsort é O(n).
A partir dos dados acima, pode-se concluir que estão CORRETAS
(A) apenas as afirmativas I e II.
(B) apenas as afirmativas I, II e III.
(C) apenas as afirmativas I, III e V.
(D) apenas as afirmativas III, IV e V.
(E) apenas as afirmativas I e V.
11