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"}