2011-gre-cs-practice-book.pdf/Q03 — различия между версиями
| Строка 4: | Строка 4: | ||
Для этой структуры данных операция, которая заменяет x на ⌊x/8⌋ (целочисленное деление x на 8 с округлением вниз), может быть выполнена за: | Для этой структуры данных операция, которая заменяет x на ⌊x/8⌋ (целочисленное деление x на 8 с округлением вниз), может быть выполнена за: | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
=== Ответы === | === Ответы === | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | + | * (A) <m>\Theta(1) шагов</m> | |
| + | * (B) <m>\Theta(log n) шагов</m> | ||
| + | * (C) <m>\Theta(n) шагов</m> | ||
| + | * (D) <m>\Theta(n log n) шагов</m> | ||
| + | * (E) <m>\Theta(n²) шагов</m> | ||
=== Объяснение === | === Объяснение === | ||
Версия 10:32, 18 декабря 2024
Вопрос: Q03-08c765
Предположим, что любое n-битное положительное целое число x хранится в виде связного списка битов так, что первый элемент списка является наименее значимым битом. Например, x = 14 = 11102 хранится как связный список (0,1,1,1) размера n = 4.
Для этой структуры данных операция, которая заменяет x на ⌊x/8⌋ (целочисленное деление x на 8 с округлением вниз), может быть выполнена за:
Ответы
- (A)
- (B)
- (C)
- (D)
- (E)
Объяснение
Сначала заполните номер страницы с этим вопросом Исходники — вопрос 3 на 15 странице книги «2011-gre-cs-practice-book.pdf»
Если все сделаете правильно, по ссылке выше будет открываться правильная страница в правильном PDFе.
Ну и наконец, вики-разметкой напишите ваше понимание, почему правильный ответ — правильный, а неправильные варианты — неправильны. Тут тоже могут быть полезны ссылки на википедию, решение вами рекуррентных уравнений в sympy.
Задача зарезервирована: Markvernikov 10:19, 18 декабря 2024 (UTC)