Тест по Computer Science — вопросы

Материал из DISCOPAL
Перейти к: навигация, поиск
12345678910
Тест по Computer Science, подготовил Участник:Akazikov

Вариант 1310956002.

Ваше имя*:

Вопрос 1

Рассмотрим следующую грамматику

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

  • Грамматика неоднозначна
  • Грамматика подходит для нисходящего анализа
  • Грамматика подходит для восходящего анализа
  1.  2 и 3
  2.  Только 1
  3.  1, 2, 3
  4.  Только 3
  5.  Только 2

Вопрос 2

Предположим, что у некоторого программного продукта средняя наработка на отказ составляет 10 000 часов, а среднее время на ремонт — 20 часов.

Если продуктом пользуются 100 клиентов, какова его доступность?

  1.  90%
  2.  100%
  3.  99.8%
  4.  80%
  5.  98%

Вопрос 3

Логическая схема имеет три входных бита: где  — младший бит, а  — старший бит

Выход схемы равен 1, если на ее входе указано любое из трехбитовых чисел 1, 4, 5 или 6; в противном случае выход схемы равен 0

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 4

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

  1.  Преобразование типов
  2.  Длина идентификатора
  3.  Совместимость типов
  4.  Максимальный уровень вложенности
  5.  Приоритет оператора

Вопрос 5

На конвейерном RISC-компьютере, где все арифметические команды имеют одинаковый CPI (cycles per instruction), какие из следующих действий улучшат время выполнения типичной программы?

  • Увеличение частоты тактового цикла
  • Запрещение любой переадресации в конвейере
  • Удвоение размеров кэша интсрукций и кэша данных без изменения времени такта
  1.  1 и 3
  2.  Только 3
  3.  Только 1
  4.  1 и 2
  5.  Только 2

Вопрос 6

Какой из следующих алгоритмов имеет время выполнения O(n²) в наихудшем случае, но O(nlog(n)) в среднем?

  1.  Сортировка слиянием
  2.  Пузырьковая сортировка
  3.  Пирамидальная сортировка (сортировка кучей)
  4.  Быстрая сортировка
  5.  Турнирная (Tournament) сортировка

Вопрос 7

Пусть T(n) определяется как и для всех целых чисел

Какое из следующих утверждений представляет порядок роста T(n) как функции n?

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 8

Рассмотрите следующие два языка

Что из нижеследующего верно в отношении и  ?

  1.   является контекстно-свободным, но не регулярным, и не является контекстно-свободным
  2.   регулярный, а контекстно-свободный, но не регулярный
  3.  Ни , ни не являются регулярными, но оба они не зависят от контекста
  4.   и являются регулярными
  5.  Ни , ни не являются контекстно-свободными

Вопрос 9

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

  • Нахождение минимального остовного дерева в неориентированном графе с целыми положительными весами ребер
  • Нахождение максимальной клики в неориентированном графе
  • Нахождение максимального потока от узла-источника к узлу-приемнику в ориентированном графе с целыми положительными значениями пропускной способности ребер
  1.  1, 2, 3
  2.  Только 3
  3.  Только 1
  4.  Только 2
  5.  1 и 2

Вопрос 10

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

Input

Направленный граф , где

Стоимость для всех , где тогда и только тогда, когда

Definition

длина кратчайшего пути от до для всех

Если нет пути от до , то

Если для всех

Problem

Определить для всех

Алгоритм Флойда-Уоршалла дает решение динамического программирования для определения массива для и по следующим условиям

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

Тогда

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

для и

для всех

Каково время работы алгоритма Флойда-Уоршалла ?

  1.  
  2.  
  3.  
  4.  
  5.  
Источник — «https://discopal.ispras.ru/Служебная:MediawikiQuizzer/GRE-CS-kazikov»