Crie sua conta grátis para liberar esse material. 🤩
Já tem uma conta?
Ao continuar, você aceita os Termos de Uso e Política de Privacidade
Prévia do material em texto
Gabarito Semana 9 Escreva um pseudocódigo que, dados n inteiros com valores entre 1 e k, pré-processe esses inteiros e então responda perguntas da forma: “dados a, b, quantos dos n inteiros estão no intervalo [a , b]?” A resposta a esse tipo de perguntas deve ser feita em tempo O(1) e o pré-processamento deve ser feito em tempo O(n+k). O nome para cada um dos métodos deve ser ResponderQuery e PreProcessar, respectivamente. Resposta do aluno Renato Banzai levemente modificada PreProcessar(A, n, k) 1 para i ← 0 até k faça //Bastou usar o primeiro trecho de COUNTING-SORT (aula 10) 2 C[i] ← 0 //Θ(k) 3 para j ← 1 até n faça 4 C[A[j]] ← C[A[j]] + 1 //Θ(n) 5 para i ← 1 até k faça 6 C[i] ← C[i] + C[i − 1] //Θ(k) 7 devolva C // Total: Θ(n + k) ResponderQuery(A, n, k, a, b) 1. C = PreProcessar(A, n, k) //Θ(n+k) 2. devolva (C[b] - C[a-1]) //Θ(1) Observação: Assume 1 ≤ a ≤ b ≤ k e que o C é indexado a partir do 0.
Mais conteúdos dessa disciplina
Qual e a funcao da diretiva #include em C?
a) Inserir arquivos de cabecalho e bibliotecas
b) Criar variaveis
c) Declarar funcoes
d) Iniciar loops- Qual das opcoes representa corretamente a declaracao de uma estrutura em C?
a) struct Pessoa { char nome[50]; int idade; };
b) struct Pessoa ( char...
- Em C, qual instrucao permite selecionar entre multiplos casos?
a) if-else
b) switch-case
c) while
d) for
- Qual das seguintes instrucoes em C representa uma estrutura condicional?
a) if
b) for
c) switch
d) loop
- Em C, qual operador e utilizado para bitwise AND?
a) &
b) &&
c) |
d) ~
- Qual palavra-chave em C define uma variavel constante?
a) constant
b) const
c) final
d) immutable
- Qual funcao e utilizada para liberar memoria alocada dinamicamente em C?
a) free()
b) delete()
c) release()
d) remove()
- Em C, qual funcao e utilizada para alocar memoria dinamicamente?
a) malloc()
b) new()
c) alloc()
d) memory()
- Qual das opcoes abaixo representa um ponteiro para inteiro?
a) int* p;
b) int p*;
c) pointer int p;
d) int &p;
- Qual operador permite acessar membros de uma estrutura em C?
a) .
b) ->
c) &
d) *
- Qual das alternativas abaixo representa corretamente a declaracao de um array de 10 inteiros em C?
a) int arr[10];
b) int arr(10);
c) array int arr...
- Em C, qual e o valor de sizeof(int) em um sistema de 32 bits?
a) 2 bytes
b) 4 bytes
c) 8 bytes
d) Depende do compilador
- Qual operador e usado para incrementar o valor de uma variavel em 1?
a) ++
b) +=
c) =+
d) --
- ATIVIDADE 4
- modelo_lógico_hotel