Инструменты, алгоритмы и структуры данных

В привычном для нас мире десятичной системы счисления незыблемой истиной считается, что 2 * 2 = 4. В двоичной системе счисления такая запись просто невозможна, поскольку нет ни цифр 2, ни 4. А в какой системе счисления с основанием p справедлива запись 2 * 2 = 11?

• p = 16
• p = 4
• p = 8
• (Правильный ответ) p = 3

Какое утверждение справедливо о выполнении в компьютере арифметических операций (сложение, вычитание, умножение) над вещественными числами?

• (Правильный ответ) выполнимо, только если операнды и результат операции принадлежат фиксированному диапазону и могут быть записаны в памяти компьютера. Представление операндов без потери точности не гарантирует, что результат не будет иметь погрешности вычисления
• всегда выполнимо, и дает точные результаты, если операнды принадлежат фиксированному диапазону и могут быть без потери точности записаны в памяти компьютера
• всегда выполнимо, и дает точные результаты
• всегда выполнимо, если операнды принадлежат фиксированному диапазону и могут быть без потери точности записаны в памяти компьютера, но результат может иметь погрешность

Какие группы команд выполняет центральный процессор компьютера?

• (Правильный ответ) операции обмена данными между разными уровнями памяти
• операции языка ассемблера
• (Правильный ответ) операции — арифметические, логические, сравнения
• (Правильный ответ) операции перехода (условного и безусловного), когда управление в зависимости от выполнения некоторых условий передается той или иной команде программы

В некоторых первых компьютерах использовалась привычная для человека десятичная система счисления. Кнут в своем знаменитом труде «Искусство программирования» рассматривал машину MIX, работавшую в троичной системе. В Советском Союзе в МГУ под руководством профессора Брусенцова была построена и успешно работала троичная машина «Сетунь». Сегодня все компьютеры используют только двоичную систему, в которой данные представляются последовательностями битов. Укажите причины, сделавшие двоичную систему столь популярной при построении компьютеров?

• (Правильный ответ) бит просто реализуется
• (Правильный ответ) удается создать относительно дешевую память на битах большого объема
• (Правильный ответ) последовательности битов легко сохраняются и легко читаются
• компьютеры плохо соображают. Они, как Митрофанушка в Недоросле, способны выучить только простейшую систему умножения — «единожды нуль -нуль», «Единожды один — один»

Отрицательные целые числа хранятся в памяти компьютера в дополнительном коде. Предположим, что для хранения целых отведен один байт памяти. Как будет выглядеть в этом случае представление отрицательного числа -127?

• 11111111
• в одном байте это число невозможно представить
• — 127
• (Правильный ответ) 10000001

Какие типы данных можно использовать в языке Eiffel для сущностей, представляющих тексты?

• (Правильный ответ) CHARACTER
• (Правильный ответ) CHARACTER_8
• (Правильный ответ) CHARACTER_32
• STRING

Какой тип языков по классификации Хомского задают БНФ грамматики?

• (Правильный ответ) тип 2 (контекстно-свободные языки)
• тип 1 (контекстно-зависимые, неукорачивающие языки)
• тип 0 (неограниченные языки, распознаваемые машиной Тьюринга)
• тип 3 (регулярные языки)

Историю программирования и людей, создававших эту историю, следует знать. Кто руководил разработкой по созданию первого признанного языка программирования Fortran и компилятора для него?

• Никлас Вирт
• Дональд Кнут
• (Правильный ответ) Джон Бэкус
• Питер Наур

Какое из высказываний является некорректным по отношению к понятиям языка программирования и его грамматики?

• грамматика языка задает описание его синтаксиса
• в роли элементарных единиц, из которых строятся предложения языка, выступают лексемы
• (Правильный ответ) грамматика языка позволяет определить, какие предложения являются семантически правильными для этого языка
• лексемы строятся из символов, составляющих алфавит языка
• грамматика языка позволяет определить, какие предложения являются синтаксически правильными для этого языка

Какие высказывания справедливы для продукций в БНФ-Е?

• (Правильный ответ) каждая продукция определяет одну нетерминальную категорию
• (Правильный ответ) каждая продукция должна быть одного вида
• допускаются правила, состоящие из смеси продукций разного вида
• (Правильный ответ) каждая нетерминальная категория определяется одной продукцией

За 55 лет, прошедших с момента появления первого языка программирования, создано большое число языков, точного числа которых никто не знает. Языки программирования могут отличаться по многим критериям. Укажите критерий, который не применяется при сравнении языков программирования?

• стиль описания — императивный или декларативный
• учет жизненного цикла — возможность использования на этапах спецификации проекта, проектирования и реализации
• (Правильный ответ) энергоемкость — уровень потребляемой энергии
• область применения — общецелевой или проблемно-ориентированный язык

За 55 лет, прошедших с момента появления первого языка программирования, создано большое число языков, точного числа которых никто не знает. Языки программирования могут отличаться по многим критериям. Укажите критерии, которые применяются при сравнении языков программирования?

• элитность — языки, ориентированные на элиту программирования
• (Правильный ответ) архитектурный стиль — функциональные, логические языки, процедурно-ориентированные языки
• (Правильный ответ) верифицируемость — ориентация на обнаружение ошибок на этапе трансляции или на этапе выполнения
• (Правильный ответ) уровень абстракции — на нижнем уровне находятся ассемблеры, близкие к машинному коду

Для поддержки процесса проектирования, как промышленных изделий, так и программных продуктов, создается специальный инструментарий — мощные программные системы. Какой инструментарий в первую очередь следует выбрать программисту, который совместно с инженерами работает над созданием современного авиалайнера?

• (Правильный ответ) CADCAM
• EiffelStudio
• VisualStudio
• CASE

Какие утверждения справедливы по отношению к компиляции и интерпретации в реальной практике программирования?

• (Правильный ответ) в современном программировании применяется двухэтапная схема, сочетающая компиляцию и интерпретацию. На первом этапе выполняется компиляция исходного кода в код виртуальной машины, не зависящей от особенностей процессора. На втором этапе возможна эффективная интерпретация кода виртуальной машины в машинный код
• (Правильный ответ) современные компиляторы обладают возможностями интерпретации кода, что крайне удобно в процессе отладки
• (Правильный ответ) практически любой интерпретатор выполняет частичную компиляцию кода, создавая необходимые структуры данных
• когда строится интерпретатор, то он не содержит элементов компиляции
• когда строится компилятор, то он не содержит элементов интерпретации

Укажите корректные высказывания:

• инструментарий «контроля версий» должен полностью сохранять весь код всех версий программной системы
• (Правильный ответ) технология «тающего льда» позволяет интерпретировать части программы, подвергшиеся изменениям, оставляя скомпилированной оставшуюся часть системы
• (Правильный ответ) инструментарий ПО играет ту же роль для программиста, что и инструментарий CAD для инженера в машиностроении
• компиляторы и интерпретаторы не относятся к инструментам разработки ПО

При компоновке системы командой make системы Unix описание компоновки задается с помощью зависимостей вида target: source1, …, source. Данная зависимость говорит, что цель target зависит от нескольких источников. Укажите, в каких случаях зависимость будет применяться, перестраивая цель target?

• когда выясняется, что зависимость следует применить, то она непосредственно применяется
• если указана зависимость, то она всегда будет применяться
• (Правильный ответ) когда выясняется, что зависимость следует применить, то перед непосредственным ее применением проверяется, не являются ли источники целями других зависимостей. Если источники являются целями, то процесс рекурсивно применяется к этим целям
• (Правильный ответ) зависимость будет применяться только тогда, когда хотя бы один из источников был перестроен и дата его создания более поздняя, чем дата создания цели target

Полезным инструментарием разработчика является браузер (просмотр) классов, позволяющий анализировать отношения, связывающие классы системы. Какое из приведенных высказываний является некорректным по отношению к такому браузеру?

• (Правильный ответ) возможен анализ отношения предпочтения (влюбленности), позволяющий выяснить для данного класса, каким классам нравится использовать данный класс, какие классы предпочитает анализируемый класс. Поскольку отношение транзитивно, то можно анализировать эти связи на любом уровне
• возможен анализ отношения клиент — поставщик, позволяющий выяснить для данного класса, какие классы являются его непосредственными клиентами, какие — клиентами. Поскольку отношение транзитивно, то можно анализировать эти связи на любом уровне
• возможен анализ отношения родитель — потомок, позволяющий выяснить для данного класса, какие классы являются его непосредственными родителями, какие — потомками. Поскольку отношение транзитивно, то можно анализировать эти связи на любом уровне
• для наследуемого метода F можно выяснить, какой класс впервые создал версию метода F
• для наследуемого метода F можно выяснить, какой класс создал используемую версию метода F

Команда Make операционной системы Unix, разработанная более 30 лет назад, является классическим примером инструментария, позволяющего автоматизировать процесс сборки программной системы. Какие выражения справедливы для файла, называемого makefile, задающего описание сборки?

• (Правильный ответ) файл состоит из описания зависимостей одних модулей от других и команд, которые нужно выполнить, если зависимость следует применить
• порядок предложений в файле определяет порядок сборки
• (Правильный ответ) этот файл можно рассматривать как программу на языке программирования декларативного типа
• этот файл содержит типичные конструкции языка программирования — условный оператор и оператор цикла

Укажите корректные высказывания:

• (Правильный ответ) инструментарий контроля версий сохраняет последовательные версии частей программы, храня различия между версиями
• код, созданный компилятором, может быть непосредственно выполнен процессором компьютера
• (Правильный ответ) загрузчик загружает программу в память, преобразуя относительные адреса в абсолютные
• (Правильный ответ) редакторы и CASE-инструментарий позволяют строить программу из текстового и графического описания

Какие утверждения верны относительно конфигурирования программной системы?

• (Правильный ответ) программная система строится из модулей — кластеров, классов, методов
• (Правильный ответ) сборка может корректно работать только для определенных сочетаний версий, входящих в нее модулей
• задачей системы конфигурирования является обеспечение работоспособности сборки, собранной в любом сочетании версий модулей
• (Правильный ответ) в процессе разработки модуля в него практически ежедневно вносятся изменения, что порождает существование версий одного модуля
• (Правильный ответ) собранная из модулей система называется сборкой

Большинство контейнерных классов имеют общие для всех запросы. Укажите, какое из приведенных выражений не является запросом?

• is_empty : BOOLEAN
• item: G
• (Правильный ответ) is_empty = (count = 0)
• has(v : G): BOOLEAN
• count : INTEGER

Гарри Поттер ищет важную для него информацию. Он надеется, что она может быть в одной из книг библиотеки Хогварда, содержащей книг. Гарри наугад выбирает книгу и просматривает ее содержимое, на что у него уходит минут. При неудаче он повторяет поиск, выбирая новую книгу. Для такого алгоритма поиска каковы значения времени поиска: минимальное, максимальное, в среднем?

• (Правильный ответ)

При решении одной и той же задачи можно использовать разные алгоритмы. На практике часто важно, сколько времени и сколько памяти требуется для решения этой задачи. Понятно, что эти характеристики зависят от входных данных, которые определяют «размер» задачи. Для контейнеров естественным «размером» может служить n- число элементов, хранимых в контейнере. Самый простой путь определения для алгоритма характеристик требуемой памяти и времени — это проведение экспериментов и вычисление характеристик на основе наблюдений с последующим усреднением данных. Укажите утверждения, корректные относительно данного способа вычисления характеристик алгоритма:

• (Правильный ответ) этот способ не эффективен, поскольку результаты зависят от масштабирования. Алгоритмы, хорошо работающие при малых размерах, могут плохо работать с увеличением размера задачи
• (Правильный ответ) этот способ не эффективен, поскольку результаты зависят не только от алгоритма, но и от окружения — компьютера, операционной системы, компилятора, выполняемых автоматически оптимизаций
• такой способ является самым надежным и самым точным способом оценки характеристик алгоритма
• (Правильный ответ) этот способ не эффективен, поскольку знание «средних» величин недостаточно информативно при отсутствии данных о законе распределения

Классы и типы это близкие понятия. Какое утверждение, связанное с этими понятиями, не является справедливым?

• универсальный класс описывает множество типов данных
• тип представляет описание множества значений (объектов) периода выполнения. Типы характеризуют динамику — период выполнения
• класс представляет статическое описание структуры объектов (поля класса) и их поведения (методы класса)
• (Правильный ответ) каждый класс описывает конкретный тип данных

Какие утверждения справедливы относительно имен методов для контейнерных классов, включенных в библиотеки классов EiffelStudio?

• у каждого контейнерного класса общий по смыслу метод имеет свое оригинальное имя
• (Правильный ответ) у каждого контейнерного класса общий по смыслу метод имеет имя, используемое всеми классами, но сигнатуры методов могут отличаться
• методы с одинаковой сигнатурой должны иметь одно и то же имя
• у каждого контейнерного класса общий по смыслу метод имеет одно и то же имя и одну и ту же сигнатуру

Какие утверждения справедливы для метода force при работе с массивами в Eiffel?

• (Правильный ответ) позволяет записать в массив элемент, индекс которого выходит за установленные границы
• минимальная временная сложность — O(count)
• (Правильный ответ) метод всегда применим, потому не имеет предусловия
• (Правильный ответ) максимальная временная сложность — O(count)
• вызывает исключительную ситуацию при попытке записать в массив элемент, индекс которого выходит за установленные границы
• временная сложность в среднем — O(count)

Какие операции недоступны при работе с кортежами в языке Eiffel:

• чтение элемента кортежа
• (Правильный ответ) удаление элемента кортежа
• (Правильный ответ) вставка элемента кортежа
• запись элемента кортежа

Какие утверждения справедливы для контейнеров?

• существует контейнерный класс, который наиболее эффективно реализует все общие операции
• (Правильный ответ) контейнерный класс — это класс, задающий некоторое хранилище элементов, имеющее свою специфику
• (Правильный ответ) для практически всех контейнерных классов определены такие операции как добавление и удаление элементов хранилища, поиск элемента, запросы о числе элементов в хранилище, пусто ли хранилище
• (Правильный ответ) контейнерные классы отличаются спецификой выполнения операций
• все контейнерные классы одинаково реализуют операции, общие для контейнерных классов

Для оценки качества алгоритма принято использовать абстрактную сложность алгоритма, не связанную с его реализацией. Чаще всего используют две меры сложности — временную и емкостную, характеризующие время работы алгоритма и память, требуемую для его работы. Укажите утверждения, справедливые для абстрактной сложности алгоритма:

• (Правильный ответ) константные множители можно не учитывать при оценке абстрактной сложности
• (Правильный ответ) для функции, характеризующей сложность не требуется задание точной формулы, — достаточно определить ее с точностью до порядка, что позволяет использовать математическую нотацию О-большое
• (Правильный ответ) абстрактная сложность рассматривается как функция, зависящая от размера задачи
• (Правильный ответ) константные слагаемые можно не учитывать при оценке абстрактной сложности
• функция, характеризующая сложность, должна быть строго определена

Какие операции над связным списком из класса LINKED_LIST выполняются в среднем за время O(count)?

• remove_right
• forth
• (Правильный ответ) back
• (Правильный ответ) finish
• put_right
• start

Укажите корректные высказывания для мультимассивных списков:

• такие списки могут быть реализованы только на мультиядерных компьютерах
• реализация такого списка построена на многомерном массиве — мультимассиве
• (Правильный ответ) реализация такого списка построена на двусвязном списке, каждый элемент которого является списком, построенным на массиве
• реализация такого списка построена на многосвязном списке — мультисписке

Проведение экзамена можно рассматривать как работу с двумя контейнерами. В одном контейнере находятся студенты, сдающие экзамен, в другом — преподаватели кафедры (их может быть несколько), принимающие экзамен. В каких вариантах проведения экзамена контейнер «студент» можно отнести к распределителю, а контейнер «преподаватель» таковым не является?

• экзамен принимают несколько преподавателей. Каждый из них вызывает по фамилии студента и принимает у него экзамен
• студенты по очереди заходят в аудиторию, где несколько преподавателей принимают экзамен. Студент сдает экзамен первому свободному преподавателю
• (Правильный ответ) экзамен принимают несколько преподавателей. Студент выбирает, какому из преподавателей он хочет сдавать экзамен, и записывается к нему в очередь
• экзамен принимает один преподаватель, выбираемый по решению заведующего кафедрой. Студенты устанавливают очередность сдачи и, согласно очереди заходят к преподавателю и сдают ему экзамен

Какими правилами можно характеризовать политику, применяемую для стеков:

• LILO — последний пришел — последний ушел
• FIFO — первый пришел — первый ушел
• (Правильный ответ) FILO — первый пришел — последний ушел
• (Правильный ответ) LIFO — последний пришел — первый ушел

Эффективность работы с хеш-таблицами зависит от выбора хеш-функции (степени ее совершенства) и от способа разрешения конфликтов при совпадении значений. Укажите, как разрешаются конфликты в Eiffel библиотечном классе HASH_TABLE?

• хеш-таблица представляется массивом. Когда возникает коллизия, изменяетсяключ элемента, получая значение ключа свободной ячейки массива
• хеш-таблица представляется массивом. Когда возникает коллизия, то выполняется последовательный перебор элементов массива в поисках первой свободной ячейки, куда и записывается пришедший элемент
• хеш-функция выдает индекс элемента массива, содержащего ссылку на список, в который помещаются все элементы с одинаковым значением индекса
• (Правильный ответ) хеш-таблица представляется массивом. Когда возникает коллизия, то в поисках первой свободной ячейки выполняется перебор элементов массива с некоторым шагом, вычисление значения которого определяется с помощью хеш-функции

Укажите корректные высказывания:

• (Правильный ответ) стеки и очереди широко используются как при решении задач, специфических для программирования — в операционных системах, в компиляторах, так и при моделировании задач в различных проблемных областях
• стеки и очереди — это распределители с одинаковой политикой доступа к элементам
• (Правильный ответ) распределители позволяют получать доступ, вставку и удаление элементов в строго определенном месте контейнера
• (Правильный ответ) каждый вид распределителя задает свою политику, куда помещать приходящие элементы и какой элемент следует выдавать по запросу

Рассмотрим язык программирования с двумя операторами — присваивания и цикла. Присваивание рассматривается в классическом варианте variable := expression и считается терминальным, не определяемым далее понятием. Грамматика языка такова:

Какие утверждения являются справедливыми относительно правил этой грамматики?

• определение понятия «Оператор» является явно рекурсивным определением
• определение понятия «Цикл» не является рекурсивным определением
• определение понятия «Цикл» является явно рекурсивным определением
• (Правильный ответ) определение понятия «Оператор» является определением с косвенной рекурсией

Преобразование рекурсивного определения в циклическое может быть не простой задачей. Зная рекурсивное решение задачи о Ханойской башне, укажите, какой первый ход следует сделать для произвольного значения n:

• перенос с А на В
• (Правильный ответ) если n — нечетно, то перенос на В, иначе перенос на С
• не имеет значения, куда переносить на А или на С
• перенос с А на С

Рассмотрим игру, в которой применяется минимаксная стратегия. Напомним, это означает, что в игре участвуют два противника, поочередно выполняющие ходы. Существует оценочная функция, которая выдает оценку (число) для каждой позиции после очередного хода. Положительное значение этой оценки рассматривается как выигрыш для одного игрока и как проигрыш для другого (игра с нулевой суммой). Рассмотрим дерево конкретной игры, в узлах которого записываются оценки позиций. Дерево зададим скобочной записью:

(((5, 3) (6, -1, 8))((10, 6, 2) (-2, -4, -7)) ) Здесь цифры, заключенные в скобки — это оценки в листьях, принадлежащих одному родителю. Игрок на нижнем уровне выбирает минимальную оценку. Каково значение цены игры для этого дерева?

• 5
• -7
• (Правильный ответ) 2
• 3
• -1
• 10

Наряду с четырьмя классическими стратегиями решения задач — последовательность, выбор, цикл и процедура — рекурсия представляет пятую классическую стратегию. Какое из утверждений не является справедливым для этой стратегии?

• рекурсия, подобно стратегии цикла, в большинстве случаев задает последовательное приближение к решению задачи
• рекурсия использует стратегию вызова процедуры с тем отличием, что вызывает саму себя, но при других значениях аргументов, приближающих, как правило, к цели
• корректно определенное рекурсивное определение всегда включает выбор, по крайней мере, одна ветвь которого содержит нерекурсивную часть определения
• (Правильный ответ) в отличие от цикла until (while), который может не иметь варианта и описывать не завершающийся процесс (зацикливаться), рекурсивное определение всегда гарантирует завершаемость

Рекурсивное определение функции можно рассматривать как уравнение неподвижной точки . Какие утверждения справедливы для этого уравнения?

• функция , также как и функция , является рекурсивной
• (Правильный ответ) решением уравнения неподвижной точки является функция , которая, будучи примененной к графу функции оставляет этот граф (множество пар) неизменным.
• (Правильный ответ) если известно решение уравнения неподвижной точки — функция , то можно функцию определить без использования рекурсии
• (Правильный ответ) рекурсивное определение позволяет построить функцию

При выполнении рекурсивного метода создаются экземпляры метода, каждому из которых требуется информация, характеризующая данный экземпляр. Число экземпляров может быть большим, так, например, в задаче о Ханойской башне при n, равном, двадцати, более миллиона одновременно существующих экземпляров. Какие утверждения справедливы относительно способов представления информации, необходимой экземпляру метода?

• (Правильный ответ) сократить объем данных, хранимых в записи активации, можно за счет увеличения времени работы метода, — когда экземпляру требуется некоторое данное, то можно вычислять его значение, не храня его в записи активации. Этот прием называется «вычислить, а не хранить»
• (Правильный ответ) сократить объем данных, хранимых в записи активации, можно за счет увеличения времени работы метода. Требуемое экземпляру данное следует хранить в поле класса -общей памяти всех экземпляров. Когда экземпляру требуется некоторое данное, то значение, хранимое в поле, преобразуется в соответствии с требованиями экземпляра. Когда экземпляр заканчивает свою работу, то выполняется «обратное преобразование», восстанавливающее исходное значение. Этот прием называется «преобразования в общей памяти»
• прием «преобразования в общей памяти» всегда применим
• прием «вычислить, а не хранить» всегда применим
• для хранения всей информации, необходимой экземпляру метода, в момент его вызова создается специальная запись — запись активации, размещаемая в стеке. Когда экземпляр заканчивает свою работу, запись выталкивается из стека, освобождая память

Пусть членами семьи являются муж, жена, их родители и их дети. Определим рекурсивно понятие родственника. Члены семьи являются родственниками — родственниками уровня 0. Это не рекурсивная ветвь определения. Определим теперь рекурсивно понятие родственника