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

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

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

Список вопросов:

# В некоторых первых компьютерах использовалась привычная для человека десятичная система счисления. Кнут в своем знаменитом труде "Искусство программирования" рассматривал машину MIX, работавшую в троичной системе. В Советском Союзе в МГУ под руководством профессора Брусенцова была построена и успешно работала троичная машина "Сетунь". Сегодня все компьютеры используют только двоичную систему, в которой данные представляются последовательностями битов. Укажите причины, сделавшие двоичную систему столь популярной при построении компьютеров?
# Какие типы данных можно использовать в языке Eiffel для сущностей, представляющих тексты?
# В отличие от математики целые и вещественные числа в программировании всегда представляются конечным множеством из некоторого фиксированного интервала. В зависимости от потребностей можно выбрать тот или иной арифметический тип, характеризующий определенный интервал числовых значений. Укажите, какой арифметический тип не используется в языке Eiffel:
# В привычном для нас мире десятичной системы счисления незыблемой истиной считается, что 2 * 2 = 4. В двоичной системе счисления такая запись просто невозможна, поскольку нет ни цифр 2, ни 4. А в какой системе счисления с основанием p справедлива запись 2 * 2 = 11?
# Компьютер выполнил сложение двух чисел в двоичной системе 1010 + 11011, и результат вывел на печать в привычной для нас десятичной системе. Чему равен результат?
# Компьютер выполнил умножение двух чисел в двоичной системе 1010 * 11011, и результат вывел на печать в привычной для нас десятичной системе. Чему равен результат?
# Гибибайт (GiB) - это?
# Какие утверждения являются корректными по отношению к представлению чисел в памяти компьютера?
# Выполнение в компьютере арифметических операций (сложение, вычитание, умножение) над целыми числами:
# Какое утверждение справедливо о выполнении в компьютере арифметических операций (сложение, вычитание, умножение) над вещественными числами?
# Рассмотрим два фрагмента программ: -- fragment 1 from x := low until x >= high loop Result := Result + f(x) x := x + step end -- fragment 2 from x := low; i := 0 until x >= high loop Result := Result + f(x) i := i + 1; x := low + i * step end Какие высказывания справедливы для этих фрагментов?
# Отрицательные целые числа хранятся в памяти компьютера в дополнительном коде. Предположим, что для хранения целых отведен один байт памяти. Как будет выглядеть в этом случае представление отрицательного числа -127?
# Представление вещественного числа в памяти компьютера состоит из нескольких частей. Какая часть не входит в это представление?
# RAM -память со случайным доступом это:
# Какие виды памяти компьютера относятся к устройствам постоянной памяти?
# Какие определения применяются по отношению к памяти?
# Для современных настольных компьютеров примерно во сколько раз скорость доступа к регистрам превышает скорость доступа к дискам?
# Какой из видов памяти не является чисто электронным устройством?
# Команда сложения 32-х битного процессора PowerPC выполняет операцию над данными, которые?
# Какие утверждения не являются справедливыми для ассемблера?
# Какие группы команд выполняет центральный процессор компьютера?
# Что справедливо для закона Мура?
# Какие утверждения является некорректными?
# Какие утверждения являются корректными?
# Пять великих шахматистов прошлых лет встретились и сыграли между собой несколько партий. Алехин проиграл Фишеру, но выиграл у Ласкера. Ботвинник проиграл Капабланке, но также выиграл у Ласкера? Полагая, что проигрыш рассматривается как предшествование, укажите, какие последовательности соответствуют топологической сортировке игроков по результатам этих встреч?
# На теннисном турнире Уимблдон 2011 Федерер проиграл Тсонга, Томич - Джоковичу, Лопес - Маррею, Фиш - Надалю. В полуфиналах Джокович выиграл у Тсонга, а Надаль - у Маррея. Финал выиграл Джокович. Полагая, что проигрыш рассматривается как предшествование, по результатам встреч этих 8 спортсменов укажите, сколько можно построить различных топологически отсортированных последовательностей?
# Какие утверждения справедливы относительно понятия "отношение"?
# Какими свойствами обладает отношение строгого порядка? Отношение строгого порядка:
# Какими свойствами обладает отношение строгого полного (тотального) порядка на множестве ? Отношение полного строгого порядка:
# В игровых видах спорта отношение "выиграл" чаще всего не является транзитивным - лидер может проиграть аутсайдеру. Для отношений такого рода характерны циклы. Но их может и не быть. Пять великих шахматистов прошлых лет встретились и сыграли между собой несколько партий. Укажите, в каких случаях отношение, построенное по результатам их встреч, является ациклическим, - не образует цикл:
# Укажите, какие утверждения справедливы для топологической сортировки:
# Пусть для конечного множества элементов задано ациклическое отношение r множеством пар , принадлежащих отношению. На множестве А можно построить n! различных последовательностей этих элементов - перечислений элементов. Какие утверждения справедливы относительно этих перечислений и их топологической отсортированности?
# Рассмотрим конечное множество из пяти элементов. Пусть на этом множестве задано отношение r, содержащее только одну пару элементов. Сколько различных топологически отсортированных отношением r последовательностей можно построить?
# Рассмотрим некоторые задачи. Какие отношения, введенные в этих задачах, являются ациклическими?
# Рассмотрим множество А из пяти элементов. Из какого числа пар состоит множество, задающее строгий полный порядок на А?
# Какие утверждения справедливы для ациклического отношения и отношения порядка?
# "Инженерное" решение задачи о топологической сортировке, применимое в различных проблемных областях, предполагает, что на входе множество ограничений задает:
# Какие утверждения справедливы о числе решений в задаче о топологической сортировке?
# Какие утверждения справедливы о сложности решения задачи о топологической сортировке?
# Предлагаемый алгоритм топологической сортировки позволяет построить последовательность, упорядоченную по возрастанию - элементы в последовательности расположены в соответствии с их предшествованием. Пусть требуется строить последовательность, упорядоченную по убыванию, где элементы расположены в порядке следования. Какие стратегии может применять программист?
# Какие операции можно считать базисными для алгоритма построения топологической сортировки?
# Какие утверждения справедливы относительно представления исходных данных задачи?
# Структуры данных, используемые в алгоритме топологической сортировки, работают не с самими элементами множества, а с их номерами. Какие утверждения справедливы относительно возможного типа сортируемых элементов в предлагаемой реализации алгоритма?
# Реализация алгоритма топологической сортировки включала такой прием, как предварительная трансляция исходных данных в форму, удобную для эффективной реализации алгоритма. Что справедливо о применении этого приема в других программистских задачах? Этот прием следует применять:
# В ходе работы алгоритма на каждом шаге алгоритма находится элемент, не имеющий предшественников, добавляемый в перечисление, задающее сортировку элементов. Кандидатов на эту роль может быть несколько. Какую структуру данных следует выбрать для хранения кандидатов, чтобы клиент мог управлять процессом выбора кандидатов?
# Какие утверждения являются справедливыми?
# Какие утверждения не справедливы для класса, спроектированного в ходе решения задачи о топологической сортировке?
# Какие утверждения справедливы?
# В контекст рекурсивного метода, дающего решение задачи о Ханойской башне, входят 5 величин - 4 аргумента метода (имена трех башен и число переносимых дисков) и одна локальная переменная. Сколько величин достаточно сохранять в записи активации при оптимальной реализации рекурсивного метода?
# Историю программирования и людей, создававших эту историю, следует знать. Кто руководил разработкой по созданию первого признанного языка программирования Fortran и компилятора для него?
# Историю программирования и людей, создававших эту историю, следует знать. Кто внес основной вклад в создание формальной нотации, позволяющей описать синтаксис языка, получившей название БНФ?
# Какое из высказываний является некорректным по отношению к понятиям языка программирования и его грамматики?
# Какие высказывания являются корректными по отношению к понятию грамматики языка программирования?
# Какая часть не является частью грамматики языка, описывающей синтаксис с помощью БНФ?
# Укажите причины, по которым грамматика языка не использует правила БНФ для определения синтаксиса построения лексем?
# Какой символ не принадлежит к символам метаязыка БНФ?
# Правила БНФ будем называть продукциями. Какие утверждения справедливы для продукций?
# Ограничители языка являются лексемами, у которых есть только единственный образец - сам ограничитель, в то время как у таких лексем как Целое или Идентификатор число образцов бесконечно. Укажите, какие элементы не может содержать продукция БНФ?
# БНФ-Е - это вариант БНФ, используемый при описании грамматики Eiffel. Какой вид продукций не применяется в БНФ-Е?
# Какие высказывания справедливы для продукций в БНФ-Е?
# Составной оператор можно определить как последовательность из нуля или нескольких операторов, где каждый оператор отделяется от следующего, если он есть, символом точка с запятой. Какое правило грамматики БНФ-Е соответствует этому определению?
# Вершинный (начальный, основной) символ грамматики это:
# Какие утверждения справедливы для грамматики и языка, порожденного грамматикой?
# Какие утверждения справедливы по отношению к рекурсивным грамматикам?
# Будем полагать, что поезд - это локомотив, за которым следует один или несколько вагонов. Какие грамматики корректно описывают понятие "поезд"?
# Будем полагать, что поезд - это локомотив, за которым следует один или несколько вагонов. Какая грамматика корректно описывающая понятие "поезд" является рекурсивной?
# Будем полагать, что поезд - это локомотив, за которым следует один или несколько вагонов. Какая грамматика, корректно описывающая понятие "поезд" является регулярной и использует одно регулярное выражение?
# Чем отличается регулярная грамматика от грамматики БНФ?
# Какое утверждение не является справедливым для регулярного языка?
# Какие утверждения справедливы для конечных автоматов?
# Какие утверждения справедливы для синтаксиса реальных языков программирования?
# Какой тип языков по классификации Хомского задают БНФ грамматики?
# Какие утверждения являются корректными?
# Для поддержки процесса проектирования, как промышленных изделий, так и программных продуктов, создается специальный инструментарий - мощные программные системы. Какой инструментарий в первую очередь следует выбрать программисту, создающему прикладное ПО на языке Eiffel?
# Для поддержки процесса проектирования, как промышленных изделий, так и программных продуктов, создается специальный инструментарий - мощные программные системы. Какой инструментарий в первую очередь следует выбрать программисту, создающему прикладное ПО на языке C#?
# Для поддержки процесса проектирования, как промышленных изделий, так и программных продуктов, создается специальный инструментарий - мощные программные системы. Какой инструментарий в первую очередь следует выбрать программисту, который совместно с инженерами работает над созданием современного авиалайнера?
# За 55 лет, прошедших с момента появления первого языка программирования, создано большое число языков, точного числа которых никто не знает. Языки программирования могут отличаться по многим критериям. Укажите критерий, который не применяется при сравнении языков программирования?
# За 55 лет, прошедших с момента появления первого языка программирования, создано большое число языков, точного числа которых никто не знает. Языки программирования могут отличаться по многим критериям. Укажите критерии, которые применяются при сравнении языков программирования?
# Укажите языки, которые обладают следующим набором свойств: объектно-ориентированные, императивные, общецелевые, могут использоваться на разных этапах жизненного цикла, с высоким уровнем абстракции:
# Укажите свойства, характерные для процедурного стиля программирования?
# Какие утверждения о стиле программирования характерны для современных языков программирования?
# Укажите свойства, характерные для функционального стиля программирования?
# Какие утверждения, подтверждаемые примером обращения списка, справедливы для современного функционального языка программирования Haskell?
# Историю программирования и людей, делающих эту историю, следует знать. Укажите авторов первого объектно-ориентированного языка Симула?
# Какие языки относятся к ОО языкам?
# Сравнивая компиляцию и интерпретацию программы, укажите, какие свойства характерны для процесса компиляции:
# Сравнивая компиляцию и интерпретацию программы, укажите, какие свойства характерны для процесса интерпретации:
# Какие утверждения справедливы по отношению к компиляции и интерпретации в реальной практике программирования?
# Какие утверждения справедливы для JIT(Just In Time) - компилятора?
# Никлас Вирт впервые применил двухэтапную компиляцию при построении транслятора с языка Паскаль, транслируя код программы на Паскале в P-код, который затем транслировался в машинный код для компьютеров с разной архитектурой. Эта схема получила второе рождение с появлением языка Java. Какие утверждения справедливы для виртуальной машины Java и байт-кода?
# Какие преимущества дает схема двухэтапной компиляции?
# Укажите, на каких этапах работы компилятора идет работа с абстрактным или конкретным синтаксическим деревом?
# Какие утверждения не являются справедливыми по отношению к инструментарию, называемому "лексером" и "парсером"?
# Какие утверждения справедливы по отношению к числу проходов компилятора?
# Программа, записанная в машинном коде и выполняемая компьютером, оперирует с адресами памяти компьютера. Какие утверждения справедливы относительно формирования адресов памяти такой программы.
# Скомпонованной, загруженной на выполнение программе требуется инструментальная поддержка и в период выполнения. Поэтому над операционной системой создается специальная надстройка, называемая исполняемой средой или системой времени выполнения (runtime system). Какие функции выполняет эта система?
# Какую возможность не предоставляет современный отладчик?
# Укажите свойства, которыми обычно обладают общецелевые редакторы текстов, но которые не характерны для специализированных редакторов программ?
# Укажите свойства, которыми обычно обладают специализированные редакторы программ, но которые не характерны для общецелевых редакторов текстов?
# Какие утверждения верны относительно редактора, в котором создается текст программ?
# Какие утверждения верны относительно конфигурирования программной системы?
# При обсуждении конфигурации сборки рассматриваются три измерения, приводящие к проблемам. Какое четвертое измерение при этом не рассматривается?
# Программная система разрабатывается коллективом программистов. Этот процесс проистекает во времени. Программисты разрабатывают некоторое множество модулей. В модули вносятся изменения. Эти различные аспекты разработки могут приводить к ошибкам при построении сборки системы. На какие вопросы должна отвечать система конфигурирования:
# Команда Make операционной системы Unix, разработанная более 30 лет назад, является классическим примером инструментария, позволяющего автоматизировать процесс сборки программной системы. Какие выражения справедливы для файла, называемого makefile, задающего описание сборки?
# При компоновке системы командой make системы Unix описание компоновки задается с помощью зависимостей вида target: source1, …, source. Данная зависимость говорит, что цель target зависит от нескольких источников. Укажите, в каких случаях зависимость будет применяться, перестраивая цель target?
# Укажите, как осуществляется сборка в среде EiffelStudio?
# Система контроля версий должна поддерживать как процесс локальных изменений каждого модуля, выполняемых многократно, так и процесс развития программной системы в целом, в котором можно выделить определенные этапы. Какие утверждения справедливы для типичных систем поддержки версий?
# Какое утверждение справедливо относительно способа хранения версий программной системы?
# Какие утверждения справедливы для системы контроля версий?
# При разработке ПО коллективом разработчиков возможны ситуации, когда над одним модулем одновременно работает несколько человек, каждый из которых вносит свои изменения. Укажите правильную стратегию работы для таких ситуаций:
# Система управления версиями является частью общей системы управления проектом. На примере системы ORIGO укажите возможные свойства таких систем:
# Полезным инструментарием разработчика является браузер (просмотр) классов, позволяющий анализировать отношения, связывающие классы системы. Какое из приведенных высказываний является некорректным по отношению к такому браузеру?
# Большие программные системы относятся к наиболее сложным творениям, создаваемым человеком. Их разработка требует управления, а, следовательно, наблюдения и проведения количественных измерений атрибутов, как создаваемого продукта, так и самого процесса разработки. Какие измеряемые атрибуты характеризуют процесс разработки?
# Большие программные системы относятся к наиболее сложным творениям, создаваемым человеком. Их разработка требует управления, а, следовательно, наблюдения и проведения количественных измерений атрибутов, как создаваемого продукта, так и самого процесса разработки. Какие измеряемые атрибуты характеризуют программный продукт?
# Какие утверждения справедливы по отношению к интегрированной среде разработки?
# Интегрированная среда разработки - ИСР EiffelStudio:
# Что не может делать компилятор языка Eiffel, входящий в EiffelStudio:
# Какие утверждения справедливы по отношению к технологии "тающего льда" в EiffelStudio?
# Укажите корректные высказывания:
# Укажите корректные высказывания:
# Укажите корректные высказывания:
# Когда мы говорим, что язык программирования является языком со статической типизацией, то это означает:
# Какие утверждения справедливы для универсального класса?
# Какие утверждения верны относительно понятий "правильность" и "корректность"?
# Какое из утверждений является справедливым?
# Классы и типы это близкие понятия. Какое утверждение, связанное с этими понятиями, не является справедливым?
# Укажите, какое утверждение является корректным для универсально порожденного типа:
# Классы ARRAY и LIST являются универсальными классами с одним родовым параметром. Класс STUDENT является обычным классом. Какие объявления являются корректными в языке Eiffel?
# Какие утверждения справедливы для контейнеров?
# Большинство контейнерных классов имеют общие для всех запросы. Укажите, какое из приведенных выражений не является запросом?
# Рассмотрим контейнерный класс, в котором метод вставки элементов put имеет следующую сигнатуру: put (key:STRING; i: G), где key - ключ элемента, i - сам элемент. Какие постусловия должны включаться для этого метода?
# Какие утверждения справедливы относительно имен методов для контейнерных классов, включенных в библиотеки классов EiffelStudio?
# Контейнерные классы задают некоторое хранилище элементов. Как всякая структура данных, контейнер содержит в процессе работы конечное число элементов. Укажите утверждение, справедливое по отношению размера контейнеров:
# При решении одной и той же задачи можно использовать разные алгоритмы. На практике часто важно, сколько времени и сколько памяти требуется для решения этой задачи. Понятно, что эти характеристики зависят от входных данных, которые определяют "размер" задачи. Для контейнеров естественным "размером" может служить n- число элементов, хранимых в контейнере. Самый простой путь определения для алгоритма характеристик требуемой памяти и времени - это проведение экспериментов и вычисление характеристик на основе наблюдений с последующим усреднением данных. Укажите утверждения, корректные относительно данного способа вычисления характеристик алгоритма:
# Для оценки качества алгоритма принято использовать абстрактную сложность алгоритма, не связанную с его реализацией. Чаще всего используют две меры сложности - временную и емкостную, характеризующие время работы алгоритма и память, требуемую для его работы. Укажите утверждения, справедливые для абстрактной сложности алгоритма:
# Для некоторых алгоритмов получены оценки сложности. Из приведенных формул укажите две, задающие эквивалентные оценки?
# Гарри Поттер ищет важную для него информацию. Он надеется, что она может быть в одной из книг библиотеки Хогварда, содержащей книг. Гарри наугад выбирает книгу и просматривает ее содержимое, на что у него уходит минут. При неудаче он повторяет поиск, выбирая новую книгу. Для такого алгоритма поиска каковы значения времени поиска: минимальное, максимальное, в среднем?
# В языке Eiffel для работы с массивами используется библиотечный класс ARRAY, являющийся универсальным классом. Какие объявления массивов являются корректными, полагая, что существуют классы INTEGER, REAL, STUDENT?
# В классе ARRAY для чтения элемента массива существует запрос item(i:INTEGER), для записи - команда put(v: like item; i: INTEGER). Какое предусловие задается для item и put?
# Какие утверждения справедливы для массивов в языке Eiffel:
# В класс ARRAY добавлен "синтаксический сахар", позволяющий наряду с чтением и записью элементов массива в объектном стиле использовать и привычную скобочную запись. Отметьте допустимые фрагменты кода Eiffel при работе с массивом ar:
# Какие утверждения справедливы для метода force при работе с массивами в Eiffel?
# Какие операции недоступны при работе с кортежами в языке Eiffel:
# Укажите корректные высказывания для кортежей в языке Eiffel:
# Пусть задано объявление объекта кортежного типа: stud1:TUPLE[who: STUDENT; facultet: STRING; group: INTEGER), пусть также уже создан объект petrov класса STUDENT. Укажите корректные фрагменты Eiffel кода, полагая, что они записаны пв последовательном порядке:
# Какие операции над элементами массива имеют сложность O(n):
# Какие операции над элементами списка имеют сложность O(n):
# Какие операции над элементами списка имеют сложность O(1):
# Какой из библиотечных классов Eiffel является родительским классом для всех библиотечных классов, задающих различные реализации списков?
# Какие утверждения справедливы для библиотечного класса LIST, определяющего понятие "список"?
# Какие утверждения являются справедливыми для понятия "список с курсором"?
# Какие утверждения не являются справедливыми для понятия "список с курсором"?
# Какие утверждения справедливы для курсора?
# Укажите, какие из запросов не связаны с курсором?
# Каково число возможных позиций курсора для пустого списка?
# Дан список с курсором, в котором курсор установлен на некотором элементе списка. Каково минимальное число команд достаточно выполнить, чтобы стал истинным запрос after?
# Дан список с курсором, в котором курсор установлен на некотором элементе списка. Какие две команды нужно выполнить, чтобы стал истинным запрос before?
# Под итерированием списка понимается:
# Пусть объект your_list задает непустой список с курсором, элементы которого являются целыми числами. Какой из фрагментов кода задает итерирование списка, в результате которого значением переменной temp станет индекс первого в списке элемента со значением 5 или 0, если такового элемента в списке нет.
# Пусть объект your_list задает непустой список с курсором, элементы которого являются целыми числами. Какой из фрагментов кода задает итерирование списка, в результате которого переменная temp содержит максимальный элемент списка.
# Какие утверждения справедливы для связных списков?
# Укажите правильные последовательности действий при вставке элемента в односвязный список класса LINKED_LIST при условии, что элемент вставляется после существующего в списке элемента, назовем его current:
# При реализации алгоритма обращения списка на том же месте, требующего O(count) времени, на каждом шаге цикла достаточно выполнить несколько операторов ссылочного присваивания. Сколько требуется операторов?
# Какие операции над связным списком из класса LINKED_LIST выполняются за время O(1)?
# Какие операции над связным списком из класса LINKED_LIST выполняются в среднем за время O(count)?
# Какие утверждения справедливы для односвязных и двусвязных списков, реализуемых классами TWO_WAY_LIST и LINKED_LIST?
# Одним из наследников класса LIST является библиотечный класс ARRAYED_LIST. Какие утверждения справедливы для этого класса?
# Укажите корректные высказывания для мультимассивных списков:
# Укажите корректные высказывания:
# Что такое хеширование?
# Хеш-функция f(k) отображает множество ключей в целочисленный интервал: K -> [a, b]. Пусть ключами являются имена, которые должны отображаться в интервал [0, 9]. В качестве хеш-функции выберем функцию, которая вычисляет сумму позиций в алфавите кириллицы первой и последней буквы имени, прибавляет длину имени и вычисляет остаток от деления на 10 (взятие по модулю от длины интервала). Для имени Яша эта функция выдаст значение 7. Каково число коллизий возникнет при применении этой функции для следующих 10 имен: Анна, Инна, Нина, Ольга, Екатерина, Владимир, Владислав, Виктор, Михаил, Яков?
# Какие утверждения справедливы для совершенной хеш-функции?
# Какие утверждения справедливы для хеш-таблицы?
# Эффективность работы с хеш-таблицами зависит от выбора хеш-функции (степени ее совершенства) и от способа разрешения конфликтов при совпадении значений. Укажите, как разрешаются конфликты в Eiffel библиотечном классе HASH_TABLE?
# Какие из операций над хеш-таблицами в классе HASH_TABLE имеют временную сложность O(count), а не O(1)?
# Распределитель - это контейнер - структура данных, характеризуемая тем, что:
# Проведение экзамена можно рассматривать как работу с двумя контейнерами. В одном контейнере находятся студенты, сдающие экзамен, в другом - преподаватели кафедры (их может быть несколько), принимающие экзамен. В каких вариантах проведения экзамена оба контейнера можно отнести к распределителям?
# Проведение экзамена можно рассматривать как работу с двумя контейнерами. В одном контейнере находятся студенты, сдающие экзамен, в другом - преподаватели кафедры (их может быть несколько), принимающие экзамен. В каких вариантах проведения экзамена контейнер "студент" можно отнести к распределителю, а контейнер "преподаватель" таковым не является?
# Какие из структур данных относятся к распределителям?
# Какая из структур данных относится к распределителям с политикой "первым пришел, первым ушел"?
# Какая из структур данных относится к распределителям с политикой "первым пришел в своей группе приоритетности, первым уйдешь в своей группе приоритетности"?
# Пусть дано арифметическое выражение с бинарными операциями, записанное в обратной польской записи: "2 3 4 5 + * - 6 7 8 - * +". Для его вычисления используется стандартная техника со стеком операндов. Сколько раз при вычислении этого выражения будет выполняться операция put-записи операнда в стек?
# Пусть дано арифметическое выражение с бинарными операциями, записанное в обратной польской записи: "2 3 4 5 + * - 6 7 8 - * +". Для его вычисления используется стандартная техника со стеком операндов. Сколько раз при вычислении этого выражения будет выполняться операция item-чтения операнда из стека?
# Какие из утверждений справедливы в Eiffel для реализации стека на массивах?
# Для эффективного использования памяти на одном массиве можно реализовать стеков:
# Какие операции, определенные для библиотечного класса ARRAYED_STACK, задающего реализацию стека на массиве, являются запросами?
# Какие утверждения справедливы для стеков в Eiffel?
# Какие утверждения являются частью постусловия операции вталкивания элемента в вершину стека - put(x)?
# Какие утверждения справедливы для очереди, реализуемой связным списком класса LINKED_QUEUE?
# Какие утверждения справедливы для реализации очереди на массиве классом ARRAYED_QUEUE?
# Какие утверждения справедливы для очереди с приоритетами?
# Укажите корректные высказывания:
# Какими правилами можно характеризовать политику, применяемую для стеков:
# Какое утверждение о рекурсии является некорректным?
# Что можно определить рекурсивно?
# Напомним, что идентификатором называется любая последовательность букв, цифр и символа подчеркивания, начинающаяся с буквы. Заметьте, это определение не рекурсивно. Какие из БНФ определений идентификатора являются корректными рекурсивными определениями?
# Для каких понятий нельзя дать корректного рекурсивного определения?
# Рассмотрим язык программирования с двумя операторами - присваивания и цикла. Присваивание рассматривается в классическом варианте variable := expression и считается терминальным, не определяемым далее понятием. Грамматика языка такова: Какие утверждения являются справедливыми относительно правил этой грамматики?
# Представим себе, что при определении ссылочного класса PERSON заданы два атрибута (поля класса) mother и father класса PERSON. Какие утверждения справедливы относительно порождения объектов этого класса?
# Укажите некорректные варианты определения рекурсивной версии программы fibonacci:
# Какие утверждения справедливы относительно сравнения циклического и рекурсивного варианта вычисления чисел Фибоначчи?
# Преобразование рекурсивного определения в циклическое может быть не простой задачей. Зная рекурсивное решение задачи о Ханойской башне, укажите, какой первый ход следует сделать для произвольного значения n:
# Рекурсивное определение напоминает фокус. Рассмотрим рекурсивное определение известной в математике функции: Совершенно очевидно, какие значения принимает эта функция при . А каковы ее значения при ? Оказывается, для таких функция имеет одно и то же значение. Какое?
# Наряду с четырьмя классическими стратегиями решения задач - последовательность, выбор, цикл и процедура - рекурсия представляет пятую классическую стратегию. Какое из утверждений не является справедливым для этой стратегии?
# Какие утверждения справедливы для бинарного дерева?
# Какие утверждения справедливы для узла бинарного дерева?
# Какие утверждения справедливы для задачи "Ханойская башня"?
# Сколько времени понадобится вашему персональному компьютеру для решения задачи о "ханойской башне" в ее оригинальном варианте с 64 дисками (для корректности постановки будем полагать, что ваш ПК хотя и не является суперкомпьютером, но способен выполнить за секунду 1 миллиард переносов дисков)?
# Пусть - полное бинарное дерево (каждый узел не являющийся листом дерева имеет двух потомков) число листьев в котором равно . Для обхода дерева применяется инфиксная процедура обхода (обойти левое дерево, обойти корень, обойти правое дерево). Каким по счету будет посещен корень дерева, если счет узлов начинается с 1)?
# В соответствии с определением бинарного дерева поиска для него справедливо?
# Какие утверждения справедливы о сложности операции вставки элемента в дерево поиска с n элементами?
# Пусть разыскивается путь в графе. Содержательно можно рассматривать города, соединенные сетью дорог. Задача состоит в том, чтобы найти путь из города А в город В. Для поиска пути применяется алгоритм перебора с возвратами, реализованный в виде процедуры поиска find(path), где path - это построенный путь, начинающийся в городе А и заканчивающийся приходом в некоторый ранее не встречавшийся на построенном пути город N. Из города N дороги ведут в n городов - , не вошедшие в путь path. Какие утверждения справедливы для процедуры поиска?
# Пусть разыскивается путь в графе. Содержательно можно рассматривать города, соединенные сетью дорог. Задача состоит в том, чтобы найти путь из города А в город В. Для поиска пути применяется алгоритм перебора с возвратами, реализованный в виде процедуры поиска find(path), где path - это построенный путь, начинающийся в городе А и заканчивающийся приходом в некоторый ранее не встречавшийся на построенном пути город N. Из города N дороги ведут в n городов - , не входящие в путь path. Какие утверждения справедливы относительно вызовов процедуры поиска?
# Пусть разыскивается путь в графе. Содержательно можно рассматривать города, соединенные сетью дорог. Задача состоит в том, чтобы найти путь из города А в город В. Для поиска пути применяется алгоритм перебора с возвратами, реализованный в виде процедуры поиска find(path), где path - это построенный путь, начинающийся в городе А и заканчивающийся приходом в некоторый ранее не встречавшийся на построенном пути город N. Из города N дороги ведут в n городов - , не входящие в путь path. Какие утверждения справедливы относительно возвратов в процессе поиска?
# Алгоритм перебора с возвратами, реализованный рекурсивной процедурой find(path) исключает зацикливание (каждый город на пути встречается только один раз), что позволяет исходный граф рассматривать как дерево. Какие утверждения справедливы для графов, перебора с возвратом, и связанных с ними деревьев вариантов?
# Рассмотрим игру, в которой применяется минимаксная стратегия. Напомним, это означает, что в игре участвуют два противника, поочередно выполняющие ходы. Существует оценочная функция, которая выдает оценку (число) для каждой позиции после очередного хода. Положительное значение этой оценки рассматривается как выигрыш для одного игрока и как проигрыш для другого (игра с нулевой суммой). Рассмотрим дерево конкретной игры, в узлах которого записываются оценки позиций. Дерево зададим скобочной записью: (((5, 3) (6, -1, 8))((10, 6, 2) (-2, -4, -7)) ) Здесь цифры, заключенные в скобки - это оценки в листьях, принадлежащих одному родителю. Игрок на нижнем уровне выбирает минимальную оценку. Каково значение цены игры для этого дерева?
# Рассмотрим игру, в которой применяется минимаксная стратегия. Напомним, это означает, что в игре участвуют два противника, поочередно выполняющие ходы. Существует оценочная функция, которая выдает оценку (число) для каждой позиции после очередного хода. Положительное значение этой оценки рассматривается как выигрыш для одного игрока и как проигрыш для другого (игра с нулевой суммой). Зададим дерево конкретной игры, в узлах которого записаны оценки позиций. Дерево зададим скобочной записью: ( ((5, 3) (6, -1, 8)) ((10, 6, 2) (-2, -4, -7)) ) Здесь цифры, заключенные в скобки - это оценки в листьях, принадлежащих одному родителю. Игрок на нижнем уровне выбирает минимальную оценку. При вычислении цены игры применяется альфа-бета стратегия отсечения вариантов. Сколько вариантов (в данном случае листьев дерева) будет отсечено при применении этой стратегии?
# Каким свойством не обладает корректно определенный рекурсивный метод?
# Какие свойства являются необходимыми свойствами корректного рекурсивного метода?
# Какие свойства справедливы для варианта рекурсивного метода
# Какие утверждения справедливы относительно связи между циклами и рекурсией?
# Все рекурсивные вызовы в рекурсивном методе должны отличаться контекстом вызова - это необходимое условие корректно определенного рекурсивного метода. А что определяет контекст вызова?
# Необходимыми условиями корректно определенного рекурсивного метода является существование у метода ветви без рекурсии и разные контексты у каждого рекурсивного вызова. Рассмотрим метод с циклом: 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 Какие утверждения справедливы относительно корректности такой замены?
# Креативное понятие - это творческое понятие, несущее новую информацию, которая не может быть выведена из уже известных понятий. Укажите, какие понятия относятся к креативным понятиям?
# Для рекурсивно определенной функции можно дать другое определение, не использующее рекурсию, основанное на подходе "снизу -вверх". Для простоты будем полагать, что рассматривается функция одного целочисленного аргумента. Какие утверждения справедливы для такого подхода?
# Рекурсивное определение функции можно рассматривать как уравнение неподвижной точки . Какие утверждения справедливы для этого уравнения?
# Рекурсивное определение можно рассматривать как уравнение неподвижной точки . Пусть функция является решением этого уравнения. Какие утверждения справедливы для этой функции?
# Как выглядит граф функции "91", придуманной Маккарти?
# Пусть аргументом функции является множество пар целых чисел. Пусть также функция : добавляет в множество пару [0,0];если в множестве есть пара и , то в множество добавляется пара Для какой рекурсивно определенной функции , где , функция является решением уравнения неподвижной точки ?
# Пусть членами семьи являются муж, жена, их родители и их дети. Определим рекурсивно понятие родственника. Члены семьи являются родственниками - родственниками уровня 0. Это не рекурсивная ветвь определения. Определим теперь рекурсивно понятие родственника - родственника некоторого уровня. Некто N является родственником уровня , если он не является родственником уровня k или более низкого уровня, но является родственником уровня 0 любого из родственников уровня k. К какому уровню по отношению к Вам относится внук брата дедушки?
# Пусть функция является решением уравнения неподвижной точки . Это позволяет дать не рекурсивное определение функции , аналогично тому, как определяется предел последовательности. Рассмотрим последовательность графов и связанных с ними функций . Какие утверждения не являются справедливыми относительно такого определения ?
# Рассмотрим рекурсивное определение понятия "идентификатор": Пусть алфавит языка содержит две буквы - x и y и одну цифру -1. Индуцируя построение идентификаторов в стиле неподвижной точки, на нулевом уровне можно построить два идентификатора в соответствии с нерекурсивной частью определения, а сколько идентификаторов можно построить, принадлежащих уровню 2:
# Какие утверждения справедливы относительно контракта рекурсивного метода? Для рекурсивного метода следует:
# В контракт рекурсивного метода может входить инвариант метода. Какие утверждения справедливы относительно инварианта?
# Какие утверждения справедливы относительно выполнения предусловия и постусловия рекурсивного метода?
# Пусть метод pвызывает метод q, тот вызывает метод r с косвенной рекурсией, - метод r вызывает метод s, который в свою очередь вызывает метод r. Какие утверждения справедливы относительно завершения методов в цепочке вызовов?
# Поскольку рекурсивный метод прямо или косвенно вызывает сам себя, то в цепочке вызовов этот метод будет присутствовать в нескольких экземплярах. Какие утверждения справедливы относительно понятия "экземпляр метода"?
# Пусть метод p вызывает метод q, тот вызывает метод r с косвенной рекурсией, - метод r вызывает метод s, который в свою очередь вызывает метод r. Какие утверждения справедливы относительно процесса вызова методов?
# В контекст рекурсивного метода, дающего решение задачи о Ханойской башне, входят 5 величин - 4 аргумента метода (имена трех башен и число переносимых дисков) и одна локальная переменная. При оптимальной реализации рекурсивного метода достаточно сохранять в записи активации?
# В контекст рекурсивного метода, дающего решение задачи о Ханойской башне, входят 5 величин - 4 аргумента метода (имена трех башен и число переносимых дисков) и одна локальная переменная. Сколько величин достаточно сохранять в записи активации при оптимальной реализации рекурсивного метода?
# При выполнении рекурсивного метода создаются экземпляры метода, каждому из которых требуется информация, характеризующая данный экземпляр. Число экземпляров может быть большим, так, например, в задаче о Ханойской башне при n, равном, двадцати, более миллиона одновременно существующих экземпляров. Какие утверждения справедливы относительно способов представления информации, необходимой экземпляру метода?