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

29.05.2014 Ответы нет комментариев

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

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

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

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

	37
	110111010
	43
	25

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

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

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

	CHARACTER
	CHARACTER_8
	CHARACTER_32
	STRING

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

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

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

	Никлас Вирт
	Дональд Кнут
	Джон Бэкус
	Питер Наур

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

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

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

	$\text{Поезд }\triangleq\text{ Локомотив }\{\text{ Вагон }\}^+$
	$\text{Поезд }\triangleq\text{ Локомотив }\text{Вагоны}\\ \text{Вагоны }\triangleq\text{ Вагон \| Вагоны Вагон}$
	$\text{Поезд }\triangleq\text{ Локомотив }\{\text{ Вагон }\}^*$
	$\text{Поезд }\triangleq\text{ Локомотив Вагоны}\\ \text{Вагоны }\triangleq\text{ Вагон }\{\text{Вагон}\}^*$
	$\text{Поезд }\triangleq\text{ Локомотив Вагоны}\\ \text{Вагоны }\triangleq\text{ Вагон }\{\text{Вагон}\}^+$

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

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

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

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

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

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

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

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

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

	декларативный (аппликативный) стиль программ
	императивный стиль программ
	вычисление по программе рассматривается как вычисление значения функции по вычисленным значениям аргументов без изменения состояния
	основан на использовании понятия «состояние»
	вычисления рассматриваются как переходы из одного состояния в другое

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

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

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

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

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

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

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

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

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

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

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

	обнаружить синтаксические ошибки, не отвечающие синтаксису, заданному БНФ грамматикой
	исходный код на языке Eiffel компилировать в машинный код
	обнаружить контекстно-зависимые ошибки, выполняя статический контроль типов и другие проверки
	исходный код на языке Eiffel компилировать в код на языке С для исполняемой среды Eiffel
	исходный код на языке Eiffel компилировать в промежуточный код на CIL для .Net исполняемой среды

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

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

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

	для контейнерных классов EiffelStudio выделяет начальный объем памяти, определяемый аргументом n, если он был задан при создании контейнера. Когда в процессе работы с контейнером отведенная ему память близка к исчерпыванию, происходит автоматическая перестройка контейнера с отведением дополнительной памяти
	для контейнерных классов EiffelStudio выделяет максимально возможный объем памяти независимо от того, задавался ли аргумент n при создании контейнера
	многие контейнерные классы, реализованные в EiffelStudio, имеют процедуру создания с общим именем make и сигнатурой make(n:INTEGER). Размер контейнера в этом случае фиксирован и определяется пользователем в момент создания контейнера заданием значения фактического аргумента n
	многие контейнерные классы, реализованные в EiffelStudio, имеют процедуру создания с общим именем make. Размер контейнера в этом случае фиксирован и определяется классом

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

	для работы с кортежами Eiffel предоставляет библиотечный универсальный класс TUPLE
	тип TUPLE согласован со всеми кортежными типами, содержащими произвольное число полей. Объекту такого типа можно присвоить значение любого кортежного типа
	тип TUPLE[STUDENT, STRING, INTEGER] позволяет описать запись из трех полей, первое из которых задает объект класса STUDENT, второе — может содержать название факультета, а третье поле — номер курса (или номер группы), где учится наш студент
	TUPLE — это тип, а не универсальный класс

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

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

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

	minor: STUDENT; minor := stud1
	stud1:= [petrov, "computer science", 22]
	major : STUDENT; major := stud1.who
	stud1:= TUPLE
	stud1. group:= 32

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

	remove_right
	forth
	back
	finish
	put_right
	start

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

	temp: INTEGER your_list.start temp := your_list.item from your_list.forth until your_list.after loop temp := temp + your_list.item your_list.forth end
	temp: INTEGER from temp := 0 your_list.start until your_list.after loop if (your_list.item = 5) temp := your_list.index end your_list.forth end
	temp: INTEGER your_list.start temp := your_list.item from your_list.forth until your_list.after loop if (temp < your_list.item) temp := your_list.item end your_list.forth end
	5.4. temp: INTEGER finish: BOOLEAN from your_list.start temp := 0 finish := FALSE until your_list.after or else finish loop if (your_list.item = 5) finish := TRUE temp:= your_list.index end your_list.forth end

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

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

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

	запись значения элемента, зная его номер
	удаление элемента в позиции, определяемой курсором
	вставка нового элемента в позицию, определяемую курсором
	чтение значения элемента, зная его номер

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

	count
	count + 1
	1
	0
	2

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

Создать новый элемент класса LINKABLE;

Определить связь нового элемента, присвоив ей значение current.right;

Изменить связь current.right, чтобы она стала ссылкой на вновь созданный элемент;

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

Создать новый элемент класса LINKABLE;

Определить связь нового элемента, присвоив ей значение current.right;

Изменить связь current.right, чтобы она стала ссылкой на вновь созданный элемент;

Создать новый элемент класса LINKABLE;

Изменить связь current.right, чтобы она стала ссылкой на вновь созданный элемент;

Определить связь нового элемента, присвоив ей значение current.right;

Изменить связь current.right, чтобы она стала ссылкой на вновь созданный элемент;

Создать новый элемент класса LINKABLE;

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

	очередь
	массив
	очередь с приоритетом
	стек
	хеш-таблица
	список

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

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

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

	13
	6
	12
	7

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

	очередь с приоритетом
	список
	массив
	очередь
	хеш-таблица
	стек

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

(((5, 3) (6, -1, 8))((10, 6, 2) (-2, -4, -7)) )

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

	5
	-7
	2
	3
	-1
	10

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

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

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

	менее секунды
	менее суток
	менее часа
	более 100 лет
	менее наносекунды

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

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

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

	циклический вариант, как правило, работает быстрее
	циклический вариант имеет временную сложность O(n)
	рекурсивный вариант, как правило, работает быстрее
	при эффективной реализации рекурсии сложность рекурсивного варианта O(n)

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

	$\text{Идентификатор }\triangleq\text{ Буква \| Идентификатор }\{\text{Буква \| Цифра \| Знак подчеркивания}\}$
	$\text{Идентификатор }\triangleq\text{Идентификатор Буква \| Идентификатор Цифра\| Идентификатор Знак подчеркивания}$
	$\text{Идентификатор }\triangleq\text{ Буква }\{\text{Буква \| Цифра \| Знак подчеркивания}\}^*$
	$\text{Идентификатор }\triangleq\text{Буква \| Идентификатор Буква \| Идентификатор Цифра \| Идентификатор Знак подчеркивания}$
	$\text{Идентификатор }\triangleq\text{ Буква \| }\{\text{Буква \| Цифра \| Знак подчеркивания}\}\text{ Идентификатор}$

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

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

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

	сущность RESULT, определенная в языке Eiffel по умолчанию для всех методов, вычисляющих некоторую функцию
	поля класса, в котором объявлен метод, представляющие глобальную информацию для метода
	фактические аргументы, задаваемые при вызове метода
	локальные переменные, объявленные в методе

Рассмотрим рекурсивное определение понятия «идентификатор»:

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

	4
	24
	8.
	16
	18

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

	1
	5
	3
	2
	4

Пусть аргументом функции является множество пар целых чисел. Пусть также функция :

добавляет в множество пару [0,0];
если в множестве есть пара и , то в множество добавляется пара

	$F(n)=\sum\limits_{i=1}^n i$
	функции Маккарти «91″
	$F(n)=\prod\limits_{i=1}^n i$
	функции Фибоначчи

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

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

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

	стек
	массив
	хеш-таблицу
	очередь с приоритетами
	список
	очередь

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

	элементы должны иметь тип INTEGER
	элементы должны иметь арифметический тип
	элементы должны иметь арифметический или строковый тип
	допускается любой тип элементов
	тип элементов должен допускать хеширование

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

	(Ботвинник, Капабланка,Ласкер, Фишер, Алехин)
	(Ласкер, Ботвинник, Капабланка, Алехин, Фишер)
	(Ласкер, Алехин, Ботвинник, Фишер, Капабланка)
	(Ласкер, Ботвинник, Алехин, Капабланка, Фишер)
	(Ласкер, Алехин, Капабланка, Ботвинник, Фишер)
	(Ласкер, Ботвинник, Капабланка, Алехин, Фишер)

Добавить комментарий Отменить ответ

Для отправки комментария вы должны авторизоваться.

	$\text{Идентификатор }\triangleq\text{ Буква \| Идентификатор }\{\text{Буква \| Цифра \| Знак подчеркивания}\}$
	$\text{Идентификатор }\triangleq\text{Идентификатор Буква \| Идентификатор Цифра\| Идентификатор Знак подчеркивания}$
	$\text{Идентификатор }\triangleq\text{ Буква }\{\text{Буква \| Цифра \| Знак подчеркивания}\}^*$
	$\text{Идентификатор }\triangleq\text{Буква \| Идентификатор Буква \| Идентификатор Цифра \| Идентификатор Знак подчеркивания}$
	$\text{Идентификатор }\triangleq\text{ Буква \| }\{\text{Буква \| Цифра \| Знак подчеркивания}\}\text{ Идентификатор}$