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

Количество вопросов - 241

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

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

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

Будем полагать, что поезд - это локомотив, за которым следует один или несколько вагонов. Какая грамматика корректно описывающая понятие "поезд" является рекурсивной?

Программная система разрабатывается коллективом программистов. Этот процесс проистекает во времени. Программисты разрабатывают некоторое множество модулей. В модули вносятся изменения. Эти различные аспекты разработки могут приводить к ошибкам при построении сборки системы. На какие вопросы должна отвечать система конфигурирования:

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

Рассмотрим конечное множество из пяти элементов. Пусть на этом множестве задано отношение r, содержащее только одну пару элементов. Сколько различных топологически отсортированных отношением r последовательностей можно построить?

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

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

Хеш-функция f(k) отображает множество ключей в целочисленный интервал: K -> [a, b]. Пусть ключами являются имена, которые должны отображаться в интервал [0, 9]. В качестве хеш-функции выберем функцию, которая вычисляет сумму позиций в алфавите кириллицы первой и последней буквы имени, прибавляет длину имени и вычисляет остаток от деления на 10 (взятие по модулю от длины интервала). Для имени Яша эта функция выдаст значение 7. Каково число коллизий возникнет при применении этой функции для следующих 10 имен: Анна, Инна, Нина, Ольга, Екатерина, Владимир, Владислав, Виктор, Михаил, Яков?

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

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

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

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

Рассмотрим рекурсивное определение понятия "идентификатор":
\text{идентификатор }\triangleq\text{ буква | идентификатор буква | идентификатор цифра}
Пусть алфавит языка содержит две буквы - x и y и одну цифру -1. Индуцируя построение идентификаторов в стиле неподвижной точки, на нулевом уровне можно построить два идентификатора в соответствии с нерекурсивной частью определения, а сколько идентификаторов можно построить, принадлежащих уровню 2:

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

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

Что можно определить рекурсивно?

Одним из наследников класса LIST является библиотечный класс ARRAYED_LIST. Какие утверждения справедливы для этого класса?

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

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

Какие утверждения являются частью постусловия операции вталкивания элемента в вершину стека - put(x)?

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

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

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

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

Компьютер выполнил умножение двух чисел в двоичной системе 1010 * 11011, и результат вывел на печать в привычной для нас десятичной системе. Чему равен результат?

Алгоритм перебора с возвратами, реализованный рекурсивной процедурой find(path) исключает зацикливание (каждый город на пути встречается только один раз), что позволяет исходный граф рассматривать как дерево. Какие утверждения справедливы для графов, перебора с возвратом, и связанных с ними деревьев вариантов?

Команда сложения 32-х битного процессора PowerPC выполняет операцию над данными, которые?

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

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

Компьютер выполнил сложение двух чисел в двоичной системе 1010 + 11011, и результат вывел на печать в привычной для нас десятичной системе. Чему равен результат?

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

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

RAM -память со случайным доступом это:

Какой из видов памяти не является чисто электронным устройством?

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

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

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

Какой символ не принадлежит к символам метаязыка БНФ?

БНФ-Е - это вариант БНФ, используемый при описании грамматики Eiffel. Какой вид продукций не применяется в БНФ-Е?

Будем полагать, что поезд - это локомотив, за которым следует один или несколько вагонов. Какая грамматика, корректно описывающая понятие "поезд" является регулярной и использует одно регулярное выражение?

Чем отличается регулярная грамматика от грамматики БНФ?

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

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

Укажите языки, которые обладают следующим набором свойств: объектно-ориентированные, императивные, общецелевые, могут использоваться на разных этапах жизненного цикла, с высоким уровнем абстракции:

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

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

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

Какие утверждения не являются справедливыми по отношению к инструментарию, называемому "лексером" и "парсером"?

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

Укажите свойства, которыми обычно обладают специализированные редакторы программ, но которые не характерны для общецелевых редакторов текстов?

Система управления версиями является частью общей системы управления проектом. На примере системы ORIGO укажите возможные свойства таких систем:

Какие утверждения справедливы по отношению к технологии "тающего льда" в EiffelStudio?

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

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

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

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

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

Для некоторых алгоритмов получены оценки сложности. Из приведенных формул укажите две, задающие эквивалентные оценки?

В классе ARRAY для чтения элемента массива существует запрос item(i:INTEGER), для записи - команда put(v: like item; i: INTEGER). Какое предусловие задается для item и put?

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

Какие операции над элементами списка имеют сложность O(n):

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

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

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

Пусть объект your_list задает непустой список с курсором, элементы которого являются целыми числами. Какой из фрагментов кода задает итерирование списка, в результате которого переменная temp содержит максимальный элемент списка.

При реализации алгоритма обращения списка на том же месте, требующего O(count) времени, на каждом шаге цикла достаточно выполнить несколько операторов ссылочного присваивания. Сколько требуется операторов?

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

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

Какие из операций над хеш-таблицами в классе HASH_TABLE имеют временную сложность O(count), а не O(1)?

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

Какие из структур данных относятся к распределителям?

Пусть дано арифметическое выражение с бинарными операциями, записанное в обратной польской записи: "2 3 4 5 + * - 6 7 8 - * +". Для его вычисления используется стандартная техника со стеком операндов. Сколько раз при вычислении этого выражения будет выполняться операция item-чтения операнда из стека?

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

Напомним, что идентификатором называется любая последовательность букв, цифр и символа подчеркивания, начинающаяся с буквы. Заметьте, это определение не рекурсивно. Какие из БНФ определений идентификатора являются корректными рекурсивными определениями?

Для каких понятий нельзя дать корректного рекурсивного определения?

Какие утверждения справедливы относительно сравнения циклического и рекурсивного варианта вычисления чисел Фибоначчи?

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

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

Пусть Т - полное бинарное дерево (каждый узел не являющийся листом дерева имеет двух потомков) число листьев в котором равно 2^m. Для обхода дерева применяется инфиксная процедура обхода (обойти левое дерево, обойти корень, обойти правое дерево). Каким по счету будет посещен корень дерева, если счет узлов начинается с 1)?

Пусть разыскивается путь в графе. Содержательно можно рассматривать города, соединенные сетью дорог. Задача состоит в том, чтобы найти путь из города А в город В. Для поиска пути применяется алгоритм перебора с возвратами, реализованный в виде процедуры поиска find(path), где path - это построенный путь, начинающийся в городе А и заканчивающийся приходом в некоторый ранее не встречавшийся на построенном пути город N. Из города N дороги ведут в n городов - N_1, N_2,… N_n, не вошедшие в путь path. Какие утверждения справедливы для процедуры поиска?

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

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

Все рекурсивные вызовы в рекурсивном методе должны отличаться контекстом вызова - это необходимое условие корректно определенного рекурсивного метода. А что определяет контекст вызова?

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

Как выглядит граф функции "91", придуманной Маккарти?

Пусть членами семьи являются муж, жена, их родители и их дети. Определим рекурсивно понятие родственника. Члены семьи являются родственниками - родственниками уровня 0. Это не рекурсивная ветвь определения. Определим теперь рекурсивно понятие родственника - родственника некоторого уровня. Некто N является родственником уровня k + 1, если он не является родственником уровня k или более низкого уровня, но является родственником уровня 0 любого из родственников уровня k. К какому уровню по отношению к Вам относится внук брата дедушки?

Пусть метод pвызывает метод q, тот вызывает метод r с косвенной рекурсией, - метод r вызывает метод s, который в свою очередь вызывает метод r. Какие утверждения справедливы относительно завершения методов в цепочке вызовов?

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

На теннисном турнире Уимблдон 2011 Федерер проиграл Тсонга, Томич - Джоковичу, Лопес - Маррею, Фиш - Надалю. В полуфиналах Джокович выиграл у Тсонга, а Надаль - у Маррея. Финал выиграл Джокович. Полагая, что проигрыш рассматривается как предшествование, по результатам встреч этих 8 спортсменов укажите, сколько можно построить различных топологически отсортированных последовательностей?

Какими свойствами обладает отношение строгого порядка? Отношение строгого порядка:

Укажите, какие утверждения справедливы для топологической сортировки:

Рассмотрим множество А из пяти элементов. Из какого числа пар состоит множество, задающее строгий полный порядок на А?

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

Какие утверждения справедливы относительно представления исходных данных задачи?

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

Какие утверждения не справедливы для класса, спроектированного в ходе решения задачи о топологической сортировке?

В контекст рекурсивного метода, дающего решение задачи о Ханойской башне, входят 5 величин - 4 аргумента метода (имена трех башен и число переносимых дисков) и одна локальная переменная. Сколько величин достаточно сохранять в записи активации при оптимальной реализации рекурсивного метода?

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

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

Контейнерные классы задают некоторое хранилище элементов. Как всякая структура данных, контейнер содержит в процессе работы конечное число элементов. Укажите утверждение, справедливое по отношению размера контейнеров:

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

Пусть разыскивается путь в графе. Содержательно можно рассматривать города, соединенные сетью дорог. Задача состоит в том, чтобы найти путь из города А в город В. Для поиска пути применяется алгоритм перебора с возвратами, реализованный в виде процедуры поиска find(path), где path - это построенный путь, начинающийся в городе А и заканчивающийся приходом в некоторый ранее не встречавшийся на построенном пути город N. Из города N дороги ведут в n городов - N_1, N_2,… N_n, не входящие в путь path. Какие утверждения справедливы относительно вызовов процедуры поиска?

Какие утверждения справедливы по отношению к числу проходов компилятора?

Какие определения применяются по отношению к памяти?

Укажите, как осуществляется сборка в среде EiffelStudio?

В класс ARRAY добавлен "синтаксический сахар", позволяющий наряду с чтением и записью элементов массива в объектном стиле использовать и привычную скобочную запись. Отметьте допустимые фрагменты кода Eiffel при работе с массивом ar:

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

Какая часть не является частью грамматики языка, описывающей синтаксис с помощью БНФ?

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

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

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

Необходимыми условиями корректно определенного рекурсивного метода является существование у метода ветви без рекурсии и разные контексты у каждого рекурсивного вызова. Рассмотрим метод с циклом:
cicle   do      from Init until Exit loop Body end   end
Заменим его методом
recursive    do Init; loop_eqviv end
с вызовом рекурсивного метода:
loop_eqviv   do      if not Exit then        Body; loop_eqviv     end   end
Какие утверждения справедливы относительно корректности такой замены?

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

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

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

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

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

Какие операции можно считать базисными для алгоритма построения топологической сортировки?

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

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

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

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

Пусть функция h является решением уравнения неподвижной точки F = h(F). Это позволяет дать не рекурсивное определение функции F, аналогично тому, как определяется предел последовательности. Рассмотрим последовательность графов и связанных с ними функций F_0, F_1, … , F_n. Какие утверждения не являются справедливыми относительно такого определения F?

Пусть аргументом функции h является множество пар целых чисел. Пусть также функция h:
  • добавляет в множество пару [0,0];
  • если в множестве есть пара [i, S] и i<n, то в множество добавляется пара [i+1, S+ i +1]
  • Для какой рекурсивно определенной функции F(n), где n>=0, функция h является решением уравнения неподвижной точки F = h(F)?

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

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

    Укажите некорректные варианты определения рекурсивной версии программы fibonacci:

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

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

    Какие утверждения справедливы для реализации очереди на массиве классом ARRAYED_QUEUE?

    Для эффективного использования памяти на одном массиве можно реализовать стеков:

    Пусть дано арифметическое выражение с бинарными операциями, записанное в обратной польской записи: "2 3 4 5 + * - 6 7 8 - * +". Для его вычисления используется стандартная техника со стеком операндов. Сколько раз при вычислении этого выражения будет выполняться операция put-записи операнда в стек?

    Какая из структур данных относится к распределителям с политикой "первым пришел, первым ушел"?

    Распределитель - это контейнер - структура данных, характеризуемая тем, что:

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

    Каково число возможных позиций курсора для пустого списка?

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

    Какие операции над элементами массива имеют сложность O(n):

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

    Классы ARRAY и LIST являются универсальными классами с одним родовым параметром. Класс STUDENT является обычным классом. Какие объявления являются корректными в языке Eiffel?

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

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

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

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

    При обсуждении конфигурации сборки рассматриваются три измерения, приводящие к проблемам. Какое четвертое измерение при этом не рассматривается?

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

    Укажите, на каких этапах работы компилятора идет работа с абстрактным или конкретным синтаксическим деревом?

    Сравнивая компиляцию и интерпретацию программы, укажите, какие свойства характерны для процесса компиляции:

    Укажите свойства, характерные для процедурного стиля программирования?

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

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

    Будем полагать, что поезд - это локомотив, за которым следует один или несколько вагонов. Какие грамматики корректно описывают понятие "поезд"?

    Вершинный (начальный, основной) символ грамматики это:

    Составной оператор можно определить как последовательность из нуля или нескольких операторов, где каждый оператор отделяется от следующего, если он есть, символом точка с запятой. Какое правило грамматики БНФ-Е соответствует этому определению?

    Историю программирования и людей, создававших эту историю, следует знать. Кто внес основной вклад в создание формальной нотации, позволяющей описать синтаксис языка, получившей название БНФ?

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

    Представление вещественного числа в памяти компьютера состоит из нескольких частей. Какая часть не входит в это представление?

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

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

    Пусть для конечного множества элементов A ={a_1, a_2,… a_n} задано ациклическое отношение r множеством пар [a_k, a_j], принадлежащих отношению. На множестве А можно построить n! различных последовательностей этих элементов - перечислений элементов. Какие утверждения справедливы относительно этих перечислений и их топологической отсортированности?

    Рассмотрим два фрагмента программ:

    -- fragment 1

    from x := low until x >= high loop   Result := Result + f(x)   x := x + stepend  
    -- fragment 2
    from x := low; i := 0 until x >= high loop    Result := Result + f(x)    i := i + 1; x := low + i * stepend 
    Какие высказывания справедливы для этих фрагментов?

    Укажите правильные последовательности действий при вставке элемента в односвязный список класса LINKED_LIST при условии, что элемент вставляется после существующего в списке элемента, назовем его current:

    Гибибайт (GiB) - это?

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

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

    Рекурсивное определение напоминает фокус. Рассмотрим рекурсивное определение известной в математике функции:
    F(n) = n – 10,\text{ если }n > 100\\ F(n) = F(F(n + 11),\text{ если }n <= 100
    Совершенно очевидно, какие значения принимает эта функция при n> 100. А каковы ее значения при n< 101? Оказывается, для таких n функция имеет одно и то же значение. Какое?

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

    Рассмотрим язык программирования с двумя операторами - присваивания и цикла. Присваивание рассматривается в классическом варианте variable := expression и считается терминальным, не определяемым далее понятием. Грамматика языка такова:
    \text{Оператор }\triangleq\text{ Присваивание | Цикл}\\ \text{Цикл }\triangleq \text{ until (Условие) Оператор}
    Какие утверждения являются справедливыми относительно правил этой грамматики?

    Какие операции, определенные для библиотечного класса ARRAYED_STACK, задающего реализацию стека на массиве, являются запросами?

    Реализация алгоритма топологической сортировки включала такой прием, как предварительная трансляция исходных данных в форму, удобную для эффективной реализации алгоритма. Что справедливо о применении этого приема в других программистских задачах? Этот прием следует применять:

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

    Какие утверждения, подтверждаемые примером обращения списка, справедливы для современного функционального языка программирования Haskell?

    Укажите свойства, которыми обычно обладают общецелевые редакторы текстов, но которые не характерны для специализированных редакторов программ?

    Какие из утверждений справедливы в Eiffel для реализации стека на массивах?

    Какие утверждения справедливы для библиотечного класса LIST, определяющего понятие "список"?

    Какие языки относятся к ОО языкам?

    Укажите, какие из запросов не связаны с курсором?

    Правила БНФ будем называть продукциями. Какие утверждения справедливы для продукций?

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

    В соответствии с определением бинарного дерева поиска для него справедливо?

    Какие преимущества дает схема двухэтапной компиляции?

    Что справедливо для закона Мура?

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

    Ограничители языка являются лексемами, у которых есть только единственный образец - сам ограничитель, в то время как у таких лексем как Целое или Идентификатор число образцов бесконечно. Укажите, какие элементы не может содержать продукция БНФ?

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

    Историю программирования и людей, делающих эту историю, следует знать. Укажите авторов первого объектно-ориентированного языка Симула?

    Сравнивая компиляцию и интерпретацию программы, укажите, какие свойства характерны для процесса интерпретации:

    Какие утверждения справедливы для JIT(Just In Time) - компилятора?

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

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

    Дан список с курсором, в котором курсор установлен на некотором элементе списка. Каково минимальное число команд достаточно выполнить, чтобы стал истинным запрос after?

    Какие утверждения справедливы для хеш-таблицы?

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

    Какие утверждения справедливы о сложности операции вставки элемента в дерево поиска с n элементами?

    Пусть разыскивается путь в графе. Содержательно можно рассматривать города, соединенные сетью дорог. Задача состоит в том, чтобы найти путь из города А в город В. Для поиска пути применяется алгоритм перебора с возвратами, реализованный в виде процедуры поиска find(path), где path - это построенный путь, начинающийся в городе А и заканчивающийся приходом в некоторый ранее не встречавшийся на построенном пути город N. Из города N дороги ведут в n городов - N_1, N_2,… N_n, не входящие в путь path. Какие утверждения справедливы относительно возвратов в процессе поиска?

    Креативное понятие - это творческое понятие, несущее новую информацию, которая не может быть выведена из уже известных понятий. Укажите, какие понятия относятся к креативным понятиям?

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

    В игровых видах спорта отношение "выиграл" чаще всего не является транзитивным - лидер может проиграть аутсайдеру. Для отношений такого рода характерны циклы. Но их может и не быть. Пять великих шахматистов прошлых лет встретились и сыграли между собой несколько партий. Укажите, в каких случаях отношение, построенное по результатам их встреч, является ациклическим, - не образует цикл:

    Рассмотрим некоторые задачи. Какие отношения, введенные в этих задачах, являются ациклическими?

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

    Пять великих шахматистов прошлых лет встретились и сыграли между собой несколько партий. Алехин проиграл Фишеру, но выиграл у Ласкера. Ботвинник проиграл Капабланке, но также выиграл у Ласкера? Полагая, что проигрыш рассматривается как предшествование, укажите, какие последовательности соответствуют топологической сортировке игроков по результатам этих встреч?

    Рассмотрим контейнерный класс, в котором метод вставки элементов put имеет следующую сигнатуру: put (key:STRING; i: G), где key - ключ элемента, i - сам элемент. Какие постусловия должны включаться для этого метода?

    Какие утверждения справедливы для односвязных и двусвязных списков, реализуемых классами TWO_WAY_LIST и LINKED_LIST?

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

    Пусть задано объявление объекта кортежного типа: stud1:TUPLE[who: STUDENT; facultet: STRING; group: INTEGER), пусть также уже создан объект petrov класса STUDENT. Укажите корректные фрагменты Eiffel кода, полагая, что они записаны пв последовательном порядке:

    Какие утверждения справедливы для задачи "Ханойская башня"?

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

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

    Какая из структур данных относится к распределителям с политикой "первым пришел в своей группе приоритетности, первым уйдешь в своей группе приоритетности"?

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

    Для современных настольных компьютеров примерно во сколько раз скорость доступа к регистрам превышает скорость доступа к дискам?

    Укажите причины, по которым грамматика языка не использует правила БНФ для определения синтаксиса построения лексем?

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

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

    Интегрированная среда разработки - ИСР EiffelStudio:

    Когда мы говорим, что язык программирования является языком со статической типизацией, то это означает:

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

    Какие операции над элементами списка имеют сложность O(1):

    Пусть объект your_list задает непустой список с курсором, элементы которого являются целыми числами. Какой из фрагментов кода задает итерирование списка, в результате которого значением переменной temp станет индекс первого в списке элемента со значением 5 или 0, если такового элемента в списке нет.

    Что такое хеширование?

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

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

    Какими свойствами обладает отношение строгого полного (тотального) порядка на множестве А? Отношение полного строгого порядка:

    "Инженерное" решение задачи о топологической сортировке, применимое в различных проблемных областях, предполагает, что на входе множество ограничений задает:

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

    Скомпонованной, загруженной на выполнение программе требуется инструментальная поддержка и в период выполнения. Поэтому над операционной системой создается специальная надстройка, называемая исполняемой средой или системой времени выполнения (runtime system). Какие функции выполняет эта система?

    Что не может делать компилятор языка Eiffel, входящий в EiffelStudio:

    Под итерированием списка понимается:

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

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

    Пусть метод p вызывает метод q, тот вызывает метод r с косвенной рекурсией, - метод r вызывает метод s, который в свою очередь вызывает метод r. Какие утверждения справедливы относительно процесса вызова методов?

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

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

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

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

    В языке Eiffel для работы с массивами используется библиотечный класс ARRAY, являющийся универсальным классом. Какие объявления массивов являются корректными, полагая, что существуют классы INTEGER, REAL, STUDENT?

    Представим себе, что при определении ссылочного класса PERSON заданы два атрибута (поля класса) mother и father класса PERSON. Какие утверждения справедливы относительно порождения объектов этого класса?

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

    В контекст рекурсивного метода, дающего решение задачи о Ханойской башне, входят 5 величин - 4 аргумента метода (имена трех башен и число переносимых дисков) и одна локальная переменная. Сколько величин достаточно сохранять в записи активации при оптимальной реализации рекурсивного метода?