2011-gre-cs-practice-book.pdf/Q03 — различия между версиями
| Строка 1: | Строка 1: | ||
== Вопрос: Q03-08c765 == | == Вопрос: Q03-08c765 == | ||
| + | |||
| + | Assume that any n-bit positive integer x is stored as a linked list of bits so that the first element of the list | ||
| + | is the least significant bit. For example, 2 x 14 1110 is stored as the linked list 0, 1, 1, 1 of size n 4. | ||
| + | For this data structure, the operation that replaces x by 8 | ||
| + | x can be done in | ||
| + | (A) 1 steps | ||
| + | (B) log n steps | ||
| + | (C) n steps | ||
| + | (D) n n log steps | ||
| + | (E) 2 | ||
| + | n steps | ||
<i>Тут вставьте перевод вопроса. | <i>Тут вставьте перевод вопроса. | ||
| Строка 15: | Строка 26: | ||
(префикс «Правильный ответ:» — это дословно, для правильного ответа, неважно, какой он будет в списке)</i> | (префикс «Правильный ответ:» — это дословно, для правильного ответа, неважно, какой он будет в списке)</i> | ||
| − | * Правильный ответ: | + | * Правильный ответ: <m>\Theta(1)<m> steps |
| − | * | + | * O(log n) steps |
| − | * | + | * O(n) steps |
| − | * | + | * |
| − | * | + | * |
<i>Если ответы длинные, многострочные, или там графы, используйте | <i>Если ответы длинные, многострочные, или там графы, используйте | ||
| Строка 25: | Строка 36: | ||
Но такое очень редко встречается. </i> | Но такое очень редко встречается. </i> | ||
| + | ответ А | ||
=== Объяснение === | === Объяснение === | ||
<i>Сначала заполните номер страницы с этим вопросом | <i>Сначала заполните номер страницы с этим вопросом | ||
| − | {{cstest-source|2011-gre-cs-practice-book.pdf| | + | {{cstest-source|2011-gre-cs-practice-book.pdf|15|3}} |
Если все сделаете правильно, по ссылке выше будет открываться правильная страница в правильном PDFе. | Если все сделаете правильно, по ссылке выше будет открываться правильная страница в правильном PDFе. | ||
| Строка 38: | Строка 50: | ||
</i> | </i> | ||
{{reserve-task|[[Участник:Markvernikov|Markvernikov]] 10:19, 18 декабря 2024 (UTC)}} | {{reserve-task|[[Участник:Markvernikov|Markvernikov]] 10:19, 18 декабря 2024 (UTC)}} | ||
| − | |||
Версия 10:24, 18 декабря 2024
Вопрос: Q03-08c765
Assume that any n-bit positive integer x is stored as a linked list of bits so that the first element of the list is the least significant bit. For example, 2 x 14 1110 is stored as the linked list 0, 1, 1, 1 of size n 4.
For this data structure, the operation that replaces x by 8
x can be done in (A) 1 steps (B) log n steps (C) n steps (D) n n log steps (E) 2 n steps
Тут вставьте перевод вопроса. Используйте возможности разметки, включая формулы и т.п, если будут графы — посмотрите как задать их текстом https://wiki.4intra.net/Graphviz . Если код — теги «code-pascal», «code-c» или «code-python».
Старайтесь нетривиальные понятия, особенно незнакомые вам, найти ссылку на википедию и вставить (нейросети лажают!). Это важно, чтобы найти корректный перевод (то, что в википедии, или на худой конец — точно массово гуглится).
Потом конечно сотрите инструкции, которые тут курсивом.
Ответы
Если ответы простые, однострочные, используйте простой способ задания ответов списком, типа так (префикс «Правильный ответ:» — это дословно, для правильного ответа, неважно, какой он будет в списке)
- Правильный ответ: