Лист заданий по школьным темам
Выберите тему, решите вопросы самостоятельно и сверьтесь с объяснением. Готовый лист можно распечатать.
Методы алгоритмов: углубление
Информатика · Вопросов: 10
Имя: ____________________ Дата: __________
В строке«uvuvw»из позиции 2 начинается«uvw». Каково Z[2]?
- 0
- 2
- 3
Из строки «мост» требуется получить «ост». Какова минимальная стоимость при единичных вставке, удалении и замене?
- 4
- 1
- 0
Есть только значения 1 и 1000001. Сколько ячеек нужно прямой таблице для всех целых от минимума до максимума?
- 1000001
- 2
- 1000000
Есть один предмет массы 3 с полезностью 7. Вместимость 6, повторы запрещены. Каков максимум полезности?
- 0: рюкзак заполнен не полностью
- 7
- 14
Какое свойство удовлетворяет семантической части условий теоремы Райса?
- Вычисляемая функция определена на входе 0
- Имя файла начинается с a
- В исходнике есть комментарий
Какой узел будет корнем дерева выражения 8×(4−1)+2 при обычном приоритете операций?
- Вычитание
- Умножение
- Сложение
Достаточно ли выбрать одно неудобное разбиение слова и показать его провал?
- Да, одного разбиения достаточно
- Нет, должны провалиться все допустимые разбиения
- Да, если слово длинное
Два префикса приводят в одно состояние ДКА. Может ли общее продолжение быть принято только после одного из них?
- Да, если продолжение пустое
- Нет
- Да, если префиксы разной длины
После стабильного прохода по единицам получен список [31, 21, 42, 12, 23, 33]. Каков результат следующего стабильного прохода по десяткам?
- [31, 21, 42, 12, 23, 33]
- [12, 23, 21, 33, 31, 42]
- [12, 21, 23, 31, 33, 42]
Станки делают деталь за 3 и 5 минут. За сколько минимум целых минут они изготовят четыре детали при одновременном старте?
- 9
- 10
- 8
Ответы и пояснения
- 2
Начальные u и v совпадают, затем w сравнивается с u и даёт различие. Успешных совпадений ровно два.
- 1
Достаточно удалить начальную м. Строки не совпадают, поэтому нулевая стоимость невозможна; одно действие оптимально.
- 1000001
Ширина полного диапазона равна 1000001−1+1=1000001. Два различных ключа не означают две ячейки без отдельного сжатия координат.
- 7
Единственный экземпляр даёт полезность 7. Свободное место допустимо; значение 14 означало бы незаконно использовать один предмет дважды.
- Вычисляемая функция определена на входе 0
Определённость результата на конкретном входе зависит от поведения программы. Комментарии и имя файла относятся к представлению.
- Сложение
Сначала внутри левого операнда выполняются вычитание и умножение. Последнее объединение всей левой части с 2 — сложение, поэтому оно стоит в корне.
- Нет, должны провалиться все допустимые разбиения
Регулярность обещает существование хотя бы одного подходящего разбиения. Чтобы опровергнуть обещание, нельзя оставить непроверенные допустимые варианты.
- Нет
Из одного состояния одинаковое продолжение даёт одинаковое конечное состояние. Поэтому принятие не может различаться.
- [12, 21, 23, 31, 33, 42]
По десяткам образуются группы [12], [21, 23], [31, 33], [42]. Внутри каждой сохраняется порядок предыдущего прохода. Их последовательное объединение даёт [12, 21, 23, 31, 33, 42]; перестановка равных десятков разрушила бы уже установленный порядок единиц.
- 9
В момент 8 готовы floor(8/3)+floor(8/5)=2+1=3 детали, в момент 9 — 3+1=4. Монотонность выпуска подтверждает минимальность девяти минут.
Частые вопросы
Где посмотреть правильные ответы?
Включите «Показать ответы и пояснения» над вопросами. Тогда ответы будут видны на экране и попадут в печатный лист. Без этой отметки печатаются только задания.
Почему вопросов меньше выбранного количества?
Лист использует доступные вопросы выбранной темы и уровня, без повторения одного вопроса внутри набора. Если их меньше, количество не дополняется выдуманными или дублирующими заданиями.