CPXA
Algorithm Analysis Quiz
Test your knowledge in algorithm analysis with this comprehensive quiz! It covers various aspects of computational theory, from time complexity to heap structures, ensuring a well-rounded understanding of algorithm performance.
- Multiple-choice questions
- Focus on time complexity, data structures, and algorithm efficiency
- Ideal for students and enthusiasts in computer science
En supposant 𝑇(1) = Θ(1) , la solution de 𝑇(𝑛) = 𝑇(𝑛/3) + √𝑛 , est :
Θ(𝑛^3 log 𝑛)
Θ(𝑛^2 )
Θ(𝑛 log 𝑛)
Θ(1)
Θ(𝑛^2 log 𝑛)
Θ(𝑛^3)
Θ(√𝑛)
Θ(𝑛)
Θ(log 𝑛)
En supposant 𝑇(1) = Θ(1) , , la solution de 𝑇(𝑛) = 4𝑇(𝑛/2) + 3𝑛 2, est :
Θ(𝑛^3 log 𝑛)
Θ(𝑛^2 )
Θ(𝑛 log 𝑛)
Θ(1)
Θ(𝑛^2 log 𝑛)
Θ(𝑛^3)
Θ(√𝑛)
Θ(𝑛)
Θ(log 𝑛)
Si 𝑇(1) = Θ(1), et 𝑇(𝑛) ≤ 3𝑇(𝑛/5) + Θ(1), for 𝑛 > 1, , quelle est la chose la plus précise que lʼon peut dire pour 𝑇(𝑛)?
Н��(𝑛) = Θ(𝑛^2 )
Н��(𝑛) = Θ(𝑛^log{3} 5)
Н��(𝑛) = Θ(𝑛^log{5} 3 )
Н��(𝑛) = Θ((𝑛^ log{3} 5) log 𝑛)
Н��(𝑛) = Θ((n^log{5} 3) log 𝑛)
Н��(𝑛) = Θ(𝑛 log 𝑛)
Н��(𝑛) = Θ(𝑛)
Н��(𝑛) = Ω(𝑛^2 )
Н��(𝑛) = Ω(𝑛^log{3} 5 )
Н��(𝑛) = Ω(𝑛^log{5} 3 )
Н��(𝑛) = Ω((𝑛^log{3} 5) log 𝑛)
Н��(𝑛) = Ω((𝑛^log{5} 3) log 𝑛)
Н��(𝑛) = Ω(𝑛 log 𝑛)
T(n) = Ω(n)
Si 𝑇(1) = Θ(1), et 𝑇(𝑛) ≤ 3𝑇(𝑛/4) + Θ(1), for 𝑛 > 1, , quelle est la chose la plus précise que lʼon peut dire pour 𝑇(𝑛)?
Н��(𝑛) = Θ(𝑛^2 )
Н��(𝑛) = Θ(𝑛^log{3} 4)
Н��(𝑛) = Θ(𝑛^log{4} 3 )
Н��(𝑛) = Θ((𝑛^ log{3} 4) log 𝑛)
Н��(𝑛) = Θ((n^log{4} 3) log 𝑛)
Н��(𝑛) = Θ(𝑛 log 𝑛)
Н��(𝑛) = Θ(𝑛)
Н��(𝑛) = O(𝑛^2 )
Н��(𝑛) = O(𝑛^log{3} 4 )
Н��(𝑛) = O(𝑛^log{4} 3 )
Н��(𝑛) = O((𝑛^log{3} 4) log 𝑛)
Н��(𝑛) = O((𝑛^log{4} 3) log 𝑛)
Н��(𝑛) = O(𝑛 log 𝑛)
T(n) = O(n)
Lʼalgorithme qui suit calcule \(x^{p}\) pour un entier \(p>0\) . FastPower \((x,p)\) if \(p=0\) then return \(1\) if \(odd(p)\) then return \(x\times\) FastPower \((x\times x,\,\lfloor p/2\rfloor)\) else return FastPower \((x\times x,\,p/2)\) En supposant que les multiplications sʼy font en temps constant, notons \(T(p)\) la complexité temporelle de FastPower. Quelle est la caractérisation la plus précise de \(T(p)\) ?
\(\Theta(1)\)
\(\Theta(\log p)\)
\(\Theta(p)\)
\(\Theta(p\log p)\)
\(\Theta(p^{2})\)
\(\Theta(p!)\)
\(\Theta(p^{p})\)
\(\mathrm{O}(\log p)\)
\(\mathrm{O}(p)\)
\(\mathrm{O}(p\log p)\)
\(\mathrm{O}(p^{2})\)
\(\mathrm{O}(p!)\)
\(\mathrm{O}(p^{p})\)
La fonction Procedure qui suit travaille sur un tableau \(A\) de taille \(n\) en appelant la fonction BuildHeap vue en cours pour construire un tas "max" Est-ce un algorithme de tri valide? C'est-à-dire, est-ce que cela trie vraiment le tableau? \(A\) ?
Yes
No
La fonction Procedure qui suit travaille sur un tableau \(A\) de taille \(n\) en appelant la fonction BuildHeap vue en cours pour construire un tas "max" Est-ce un algorithme de tri valide? C'est-à-dire, est-ce que cela trie vraiment le tableau? \(A\) ?
Yes
No
La Procedure qui suit travaille sur un tableau \(A\) de taille \(n\) en appelant des fonctions vues en cours. Quelle est sa complexité ?
\(\Theta(n\log n)\)
\(\Theta(n^{2})\)
\(\Theta(n)\)
\(\Theta(n^{2}\log n)\)
La Procedure qui suit travaille sur un tableau \(A\) de taille \(n\) en appelant des fonctions vues en cours. Quelle est sa complexité ? Attention, que la boucle de la seconde ligne s'arrête à \(i=\lfloor\frac{n}{2}\rfloor\) , et l'appel à SelectionSort ligne 5 ne concerne qu'une moitié du tableau.
\(\Theta(n\log n)\)
\(\Theta(n^{2})\)
\(\Theta(n)\)
\(\Theta(n^{2}\log n)\)
Quelle est la complexité du pire cas du meilleur algorithme pour trouver la valeur minimale dans un "tas min" de \(n\) éléments?
\(\Theta(n\log n)\)
\(\Theta(\log n)\)
\(\Theta(n)\)
\(\Theta(1)\)
Quelle est la complexité du pire cas du meilleur algorithme pour trouver la valeur minimale dans un "tas max" de \(n\) éléments?
\(\Theta(n\log n)\)
\(\Theta(\log n)\)
\(\Theta(n)\)
\(\Theta(1)\)
Dans un tas stocké dans un tableau dont les indices commencent à \(1\) (c'est-à-dire que la racine est à l'indice \(1\) ), le fils gauche du nœud à l'indice \(i\) est à l'indice…
\(2i\)
\(2i+2\)
\(2i-2\)
\(2i-1\)
\(i+2\)
\(2i+1\)
Dans un tas stocké dans un tableau dont les indices commencent à \(0\) (c'est-à-dire que la racine est à l'indice \(0\) ), le fils droit du nœud à l'indice \(i\) est à l'indice…
\(2i\)
\(2i+2\)
\(2i-2\)
\(2i-1\)
\(i+2\)
\(2i+1\)
On considère le tas “max” correspondant au tableau suivant: |9 |7| 8| 6| 4| 2| 5| 3| 1| . Donnez lʼétat de ce tas après les suppressions successives de ses trois plus grandes valeurs. (Saissiez les chiffres les uns après les autres, dans lʼordre où ils apparaissent dans le tableau, comme sʼil sʼagissait dʼun nombre. Par exemple si vous pensez que le tableau contient encore les 6 plus petites valeurs lʼordre décroissant, saisissez 123456.)
On considère le tas “max” correspondant au tableau suivant: |9 |8| 5| 7| 6| 4| 3| 1| 2| . Donnez lʼétat de ce tas après les suppressions successives de ses trois plus grandes valeurs. (Saissiez les chiffres les uns après les autres, dans lʼordre où ils apparaissent dans le tableau, comme sʼil sʼagissait dʼun nombre. Par exemple si vous pensez que le tableau contient encore les 6 plus petites valeurs lʼordre décroissant, saisissez 123456.)
{"name":"CPXA", "url":"https://www.quiz-maker.com/QPREVIEW","txt":"Test your knowledge in algorithm analysis with this comprehensive quiz! It covers various aspects of computational theory, from time complexity to heap structures, ensuring a well-rounded understanding of algorithm performance.Multiple-choice questionsFocus on time complexity, data structures, and algorithm efficiencyIdeal for students and enthusiasts in computer science","img":"https:/images/course8.png"}
More Quizzes
E-Lasse9 TG
6370
Python
1167
Heroic Preferences Quiz
6316
World Boston What in the World? Weekly Quiz – February 27-March 5, 2023
1050
Free Project Management Software Certification
201021590
Free Geometry Chapter 4 Test & Unit 4 Review
201023069
Past Life Lovers Test: Discover Your Lost Love Now
201025054
7 Signs Your Crush Doesn't Like You? Take the!
201029332
BTS Ideal Type: Which Member's Ideal Type Are You?
201031448
Free Gift of the Magi Answer Key
201023434
How Well Do You Know Florence Nightingale? Take the!
201054319
What Christmas Character Are You? Take Our Nightmare
201027812