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 Surveys
Make your own Survey
- it's free to start.
- it's free to start.