2019-gate-computer-science-and-it-practice.pdf/Q15-alg1 — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Новая страница: « == Вопрос: Q15-alg1-31d68c == <blockquote> Вопрос из «Algorithms Test 1» где-то со страницы 222. Тут вставьте пер…») |
StasFomin (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
| − | |||
== Вопрос: Q15-alg1-31d68c == | == Вопрос: Q15-alg1-31d68c == | ||
| − | + | Пусть имеется два отсортированных списка размера ''K'' и ''L'' соответственно. | |
| − | + | ||
| − | + | Сколько потребуется сравнений элементов, для того чтобы получить отсортированный список размера ''K + L'', состоящий из элементов этих списков? | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
=== Ответы === | === Ответы === | ||
| − | < | + | * <m>O(K)</m> |
| − | ( | + | * <m>O(L)</m> |
| − | + | * Правильный ответ: <m>O(K + L)</m> | |
| − | * Правильный ответ: | + | * <m>O(K * L)</m> |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | < | + | |
| − | + | ||
| − | + | ||
| − | + | ||
=== Объяснение === | === Объяснение === | ||
| − | + | Для сравнения используется два указателя, каждый из которых проходится по своему списку. | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | {{ | + | {{cstest-source|2019-gate-computer-science-and-it-practice.pdf|223|15}} |
| − | { | + | {{question-ok|[[Участник:StasFomin|StasFomin]] 23:37, 24 декабря 2024 (UTC)}} |
| − | [[ | + | [[Категория:Sorting]] |
Текущая версия на 23:37, 24 декабря 2024
Вопрос: Q15-alg1-31d68c
Пусть имеется два отсортированных списка размера K и L соответственно.
Сколько потребуется сравнений элементов, для того чтобы получить отсортированный список размера K + L, состоящий из элементов этих списков?
Ответы
- Правильный ответ:
Объяснение
Для сравнения используется два указателя, каждый из которых проходится по своему списку.
Исходники — вопрос 15 на 223 странице книги «2019-gate-computer-science-and-it-practice.pdf»