Estrutura de dados e Algoritmos Flashcards
(14 cards)
Com base no contexto apresentado, quanto à principal característica de uma lista encadeada simples, assinale a alternativa correta:
a) A inserção de novos elementos é sempre realizada no final da lista.
b) A busca por elementos na lista tem complexidade O(log n).
c) Cada elemento da lista contém um ponteiro para o próximo elemento na sequência.
d) Ela possui um tamanho fixo definido no momento da criação
c) Cada elemento da lista contém um ponteiro para o próximo elemento na sequência.
Quanto ao princípio fundamental do algoritmo de ordenação QuickSort, assinale a alternativa correta:
a) Ordenação por inserção
b) Divide e conquista
c) Busca binária
d) Troca de elementos adjacentes.
b) Divide e conquista
No que descreve uma característica fundamental da estrutura de dados em árvore, assinale a alternativa correta:
a) As árvores são estruturas de dados estáticas, o que significa que não é possivel adicionar ou remover elementos após sua criação
b) Em uma árvore, cada elemento pode ter múltiplos prodecessores, o que permite uma organização complexa dos dados.
c) Na estrutura de árvore, um elemento especial chamado de “raiz” está no topo e não possui nenhum antecessor.
d) Uma árvore é uma estrutura de dados multilinear, onde cada elemento possui uma referência para o próximo na sequência.
c) Na estrutura de árvore, um elemento especial chamado de “raiz” está no topo e não possui nenhum antecessor.
Após a exploração dessa estrutura, sobre a principal vantagem de uma lista duplamente encadeada em relação a uma lista encadeada simples, assinale a alternativa correta:
a) Diminuição da complexidade temporal ao buscar elementos
b) Utilização de menor quantidade de memória devido à presença de apenas um ponteiro por nó
c) Facilidade e rapidez na inserção e remoção de elementos em qualquer ponto da lista.
d) Simplificação na implementação de algoritmos de ordenação.
c) Certo - Isso permite navegar em ambas as direções, facilitando operações como inserção e remoção, especialmente quando se tem um ponteiro direto para o nó de interesse
a) Errado - A busca continua sendo O(n) em ambas as listas (simples e dupla). A vantagem não está na complexidade de busca.
b) Errado - Essa seria uma vantagem da lista simples, não da lista duplamente encadeada (que usa mais memória por nó).
d) Errado - A estrutura dupla pode ajudar, mas não simplifica significativamente os algoritmos de ordenação em relação à simples.
Quando estamos manipulando uma pilha, podemos empilhar ou desempilhar dados a qualquer momento, entretanto o que poderá acontecer se tentarmos desempilhar um elemento de uma pilha que esteja vazia?
a) Remove o elemento da pilha sem retornar qualquer valor.
b) Retorna NULL.
c) Retorna o último elemento que foi removido da pilha.
d) Apresenta uma mensagem de alerta de pilha vazia.
d) Apresenta uma mensagem de alerta de pilha vazia.
[CESPE/CEBRASPE] Acerca de codificação de voz, imagens e vídeo, julgue o item que se segue.
O algoritmo de Huffman é um método de codificação sem perdas.
( ) Certo
( ) Errado
(X) Certo
O algoritmo de Huffman é um método de codificação sem perdas. Isso significa que ele permite a compressão de dados de maneira que nenhuma informação é descartada durante o processo, garantindo que a informação original possa ser perfeitamente recuperada a partir dos dados comprimidos.
[CESPE/CEBRASPE]
inteiro pontuacaoFinal (inteiro n)
inteiro i, valor;
inicio
valor <- 0;
para i de 1 até n faça
valor <- valor + i * i * i;
fim para
retorne valor;
fim
Tendo como referência o algoritmo precedente, julgue o próximo item.
O algoritmo em apreço é O(n), ou seja, um algoritmo de complexidade linear, porque realiza um total de 6n + 4 unidades de tempo.
( ) Certo
( ) Errado
(X) Certo
- As declarações não tomam tempo nenhum.
- A linha 7 também não toma tempo nenhum.
- As linhas 4 e 8 contam uma unidade de tempo cada.
- A linha 6 conta 4 unidades de tempo (2 multiplicações, uma adição e uma atribuição) e é executada n vezes, contando com um total de 4n unidades de tempo.
- A linha 5 possui custos implícitos de de inicializar o i ,testar se é menor que n e incrementá-lo. Contamos 1 unidade para sua inicialização, n + 1 para todos os testes e n para todos os incrementos, o que perfaz 2n + 2 unidades de tempo.
- O total perfaz 6n + 4 unidades de tempo, o que indica que o algoritmo é O(n), da Ordem de Complexidade n, ou seja, linear.
[CESPE/CEBRASPE]
inteiro pontuacaoFinal (inteiro n)
inteiro i, valor;
inicio
valor <- 0;
para i de 1 até n faça
valor <- valor + i * i * i;
fim para
retorne valor;
fim
Tendo como referência o algoritmo precedente, julgue o próximo item.
A linha 5 do algoritmo em apreço demanda 2n + 2 unidades de tempo.
,
( ) Certo
( ) Errado
(X) Errado
Linha 5: para 1 de i até n faça
- para 1 = 1 unidade de tempo
- de i até n = n + 1 unidade de tempo
- <incremento implícito de 1> faça = n unidade de tempo
[CESPE/CEBRASPE] Com referência à matemática computacional e à ciência da computação aplicadas, julgue o item a seguir.
A notação Big O é utilizada para descrever o comportamento assintótico de um algoritmo, fornecendo um limite superior para o tempo de execução ou uso de memória em função do tamanho da entrada.
( ) Certo
( ) Errado
(X) Certo
A notação Big O (O-grande) é usada para descrever o comportamento assintótico de algoritmos, ou seja, como seu tempo de execução ou uso de memória cresce em relação ao tamanho da entrada (n) nos piores casos. Ela fornece um limite superior, ignorando constantes e termos de menor ordem, para indicar a eficiência e escalabilidade de um algoritmo.
[CESPE/CEBRASPE] Julgue o item que se segue, relativo às estruturas de dados em árvores.
Para um dígrafo D (V, E) conexo, em que cada vértice possua pelo menos uma aresta de saída, ao se aplicar a busca em profundidade a partir de um vértice , todos os vértices de serão visitados.
( ) Certo
( ) Errado
(X) Errado
No contexto de dígrafos, o termo “conexo” não implica que exista um caminho direcionado entre todos os pares de vértices. Isso só ocorre em dígrafos fortemente conexos.
[CESPE/CEBRASPE] Julgue o próximo item, relativo a matemática computacional e ciência da computação aplicada.
Ao se comparar os algoritmos de busca linear e de busca binária em um array ordenado com elementos, verifica-se que a busca binária tem complexidade temporal O(log n), enquanto a busca linear tem complexidade temporal O(n).
( ) Certo
( ) Errado
(X) Certo
Busca Linear (ou Sequencial): Percorre cada elemento do array, um por um, até encontrar o valor ou chegar ao final.
Busca Binária: A cada passo, elimina metade dos elementos do array.
[CESPE/CEBRASPE] A análise de componente principal (PCA — principal component analysis) é uma técnica utilizada no processo de análise e classificação por aprendizagem de máquina. A PCA
a) é equivalente à realização da transformada de Dropout, quando aplicada no conjunto de validação.
b) transforma variáveis discretas em coeficientes descorrelacionados, sendo, também, conhecida como transformada discreta de KLT (Karhunen-Loève).
c) habilita, no modelo, o uso do early stopping.
d) realiza a transformação de uma variável do domínio do tempo discreto para o domínio da frequência complexa.
e) é utilizada para permitir o sobreajuste nos dados de treinamento.
b) transforma variáveis discretas em coeficientes descorrelacionados, sendo, também, conhecida como transformada discreta de KLT (Karhunen-Loève).
A PCA (Principal Component Analysis) é uma técnica de redução de dimensionalidade que transforma um conjunto de variáveis possivelmente correlacionadas em um novo conjunto de componentes principais que são não correlacionados entre si (ortogonais). Ela faz isso encontrando as direções de máxima variância nos dados.
Essa transformação é matematicamente equivalente à Transformada de Karhunen-Loève (KLT), que é uma técnica usada em compressão de dados e sinais, especialmente para sinais discretos, e é baseada na decomposição espectral da matriz de covariância.
[CESPE/CEBRASPE] Acerca de estrutura de dados e algoritmos, julgue o item a seguir.
O algoritmo quicksort possui complexidade de tempo de pior caso O(n2), contudo a complexidade de tempo médio desse algoritmo é O(n log n).
( ) Certo
( ) Errado
(X) Certo
O pior caso do Quicksort ocorre quando o pivô escolhido é sempre o menor ou o maior elemento, resultando em partições extremamente desequilibradas. Nesse cenário, a complexidade de tempo do Quicksort é O(n²). Isso significa que, em condições desfavoráveis, o tempo necessário para ordenar os elementos cresce quadraticamente com o número de elementos.
Em média, o Quicksort realiza partições mais equilibradas. Quando o algoritmo divide os elementos de forma razoavelmente balanceada, a complexidade de tempo é O(n log n). Essa é a complexidade esperada na maioria dos casos, tornando o Quicksort eficiente na prática.
[CESPE/CEBRASPE] Acerca dos conceitos e características de estrutura de dados e autômatos, julgue os itens a seguir.
Autômatos finitos são usualmente apresentados na forma de um grafo dirigido. A figura abaixo representa uma transição que pode ocorrer se o autômato estiver em um estado Si e se o símbolo da string de entrada for a. Caso a entrada para o autômato seja a string prova, é correto afirmar que ocorrerá a transição de Si para Sf .
Si -a> Sf
( ) Certo
( ) Errado
(X) Certo
De fato, a string contém a letra ‘a’ no final. Se o autômato, em algum momento do processamento, estiver no estado Si justamente quando o caractere ‘a’ for o símbolo lido, então essa transição será válida.
A banca está considerando que, como existe o símbolo ‘a’ na string, então existe a possibilidade da transição Si —a→ Sf ocorrer, o que faz sentido se entendermos que não há mais contexto (como o autômato completo).
