1. (CCV-UFC 2016) Com relação à uma árvore binária de busca, assinale a alternativa
correta.
A) Por ser uma
árvore binária, uma árvore binária de busca somente pode ter 0 (zero) ou 1 (um)
filho.
B) A complexidade
de pior caso do processo de busca em uma árvore binária de busca é sempre maior
do que a busca em uma árvore binária qualquer.
C) Uma
característica comum nas árvores binárias de busca é que todas são cheias, ou
seja, todas as sub-árvores vazias pertencem aos nós do último nível.
D) Uma árvore binária de busca é
caracterizada por seus elementos estarem organizados seguindo alguma ordem
pré-definida, sendo também conhecidas como árvore binária ordenada.
E) Como em uma
árvore binária de busca os elementos estão fora de ordem, quando se deseja
buscar um elemento, é necessário percorrer todos os elementos presentes na
árvore até encontrar o elemento buscado.
2. (FUMARC 2014) Analise as seguintes afirmativas sobre a análise de complexidade das
operações possíveis em estruturas de dados do tipo Pilha:
I. A operação de
inserção de um elemento na pilha precisa reorganizar a estrutura de dados,
podendo gastar um tempo de execução de O( n).
II. A operação de
retirada de um elemento da pilha é uma operação de tempo constante O(1).
III. Na operação
de consultar toda a pilha, todos os elementos são percorridos, gastando-se um
tempo de execução de O( n).
Estão CORRETAS as afirmativas:
A) I e II,
apenas.
B) I e III, apenas
C) II e III, apenas.
D) I, II e III,
apenas.
3. (IF-SC 2014) A análise de complexidade de algoritmos é importante para o projeto de
algoritmos eficientes desde sua concepção. Assinale a alternativa CORRETA.
A) A eficiência de algoritmos é medida em termos
de tempo de execução ou em quantidade de memória utilizada.
B) Considerar o
tempo absoluto de execução é a medida mais adequada na análise da complexidade
de algoritmos, pois está diretamente ligado à máquina onde o algoritmo será
executado de fato.
C) O algoritmo
f1(n) = 10n 2 + 10n é mais eficiente que o algoritmo f2(n) = 500n + 5000,
independente do valor de n.
D) O termo
limite superior ( upper bound ) indica o algoritmo menos eficiente para um
determinado problema, sendo o limite inferior usado ( lower bound ) para
indicar o algoritmo mais eficiente.
E) Algoritmos
com complexidade O(n) é polinomial e é considerado mais eficiente que
algoritmos com complexidade O(n 2 ) que são exponenciais.
4. (CCV-UFC 2013) No pior caso, a complexidade do algoritmo conhecido como Busca Linear
é:
A) O(n²)
B) O(1)
C) O(n)
D) O(log n)
E) O(n log n)
5. (CESGRANRIO 2012) Um programador recebeu a tarefa de elaborar um algoritmo para criar uma
única lista encadeada, não necessariamente ordenada, a partir de duas listas
encadeadas ordenadas já existentes.
Cada uma das listas originais possui
ponteiros para o primeiro e para o último elementos. Qual é a complexidade do
algoritmo mais eficiente que esse programador pode produzir?
A) O(n)
B) O(2n)
C) O(log n)
D) O(n log n)
E) O(1)
GABARITO
1:D - 2:C - 3:A - 4:C - 5:E
0 Comentários