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

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

Вариант 2891252713.


Ваше имя*:


Вопрос 1

Шаблон проектирования Singleton используется, чтобы гарантировать, что может быть создан только один экземпляр класса

Что из приведенного ниже верно для этого шаблона проектирования?

  • Класс Singleton имеет статический фабричный метод для cоздания своего экземпляра
  • Класс Singleton может быть подклассом другого класса
  • У класса Singleton есть собственный конструктор
  1.  Только 1
  2.  Только 3
  3.  1, 2, 3
  4.  Только 2
  5.  1 и 3

Вопрос 2

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

  • По крайней мере три из верны
  • Ровно три из верны
  • Чётное число из верны
  1.  Только 3
  2.  Только 1
  3.  Только 2
  4.  1 и 3
  5.  2 и 3

Вопрос 3

Чтобы найти решение уравнения для полинома степени с производной , метод Ньютона делает итерации вида

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 4

Пусть T — дерево поиска в глубину связного неориентированного графа G Для каждой вершины v из T пусть:

  • prev(v) — количество посещенных узлов до v включительно во время обхода T по предварительному обходу, и
  • prev(v) — количество посещенных узлов до v включительно во время обхода T после обхода

Наименьшим общим предком вершин u и v в T является вершина w из T, такая, что w является предком как u, так и v, и ни один дочерний элемент w не является предком, как u, так и v

Пусть (u, v) — ребро в G, которого нет в T, такое, что pre(u) < pre(v)

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

  • post(u) < post(v)
  • u является предком v в T
  • Если w является наименьшим общим предком u и v в T, то w = u
  1.  Только 2
  2.  1 и 2
  3.  2 и 3
  4.  Только 3
  5.  Только 1

Вопрос 5

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

Input

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

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

Definition

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

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

Если для всех

Problem

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

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

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

Тогда

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

для и

для всех

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 6

Сортировка слиянием выполняется путем разделения списка из n чисел пополам, рекурсивной сортировки каждой половины и объединения двух половин

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

  • Односвязный список
  • Двусвязный список
  • Массив
  1.  Нет правильного ответа
  2.  2 и 3
  3.  1, 2, 3
  4.  Только 3
  5.  1 и 2

Вопрос 7

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

Рассмотрим бухгалтерскую операцию, состоящую из двух транзакций — и , — которые необходимы для сохранения суммы A + B + C неизменной

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

 Lock A;        Lock B;
 A = A - 10;    B = B - 20;
 Unlock A;      Unlock B;
 B = B + 10;    C = C + 20;
 A = A - 10;    Lock B;
 Lock B;        B = B - 20;
 B = B + 10;    Unlock B;
 Unlock B;      C = C + 20;
 Lock A;        Lock A;
 A = A - 10;    B = B - 20;
 Unlock A;      Unlock A;
 B = B + 10;    C = C + 20;
  1.  Только 1
  2.  Только 3
  3.  2 и 3
  4.  Только 2
  5.  1 и 2

Вопрос 8

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

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

Что из приведенного ниже не является часть корневого набора в типичном сборщике мусора?

  1.  Значения в машинных регистрах
  2.  Фактические параметры активных процедур
  3.  Динамически выделяемые объекты в куче
  4.  Локальные переменные в стеке вызовов
  5.  Глобальные переменные программы

Вопрос 9

Какой из следующих протоколов, относящихся к набору интернет-протоколов (IP), наилучшим образом описывает назначение протокола разрешения адресов (Address Resolution Protocol)?

  1.  Чтобы определить подходящий маршрут для дейтаграммы
  2.  Чтобы определить IP-адрес заданного имени хоста
  3.  Чтобы определить аппаратный адрес заданного имени хоста
  4.  Для определения аппаратного адреса данного IP-адреса
  5.  Для преобразования веб-адресов в имена хостов

Вопрос 10

Инвариантом для приведенного ниже цикла является и

  x := b; k := n; z := 1;
  while (k != 0)
  {
    if odd(k) then z := z*x;
    x := x*x;
    k := [k/2];
  }

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

  1.  
  2.  
  3.  
  4.  
  5.