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

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

Вариант 1631077031.


Прошло 00:00:04.
Ваше имя*:


Вопрос 1

Центральный процессор имеет арифметический модуль, который складывает байты, а затем устанавливает свои флаговые биты V, C и Z следующим образом

Бит V устанавливается, если происходит арифметическое переполнение (в арифметике с двумя дополнениями)

Бит C устанавливается, если во время операции генерируется перенос из самого старшего бита

Бит Z устанавливается, если результат равен нулю

Каковы значения флагов битов V, C и Z после добавления 8-битных байтов 1100 1100 и 1000 1111 ?

  1.  V = 1 °C = 1 Z = 0
  2.  V = 0 °C = 1 Z = 0
  3.  V = 0 °C = 0 Z = 0
  4.  V = 1 °C = 1 Z = 1
  5.  V = 0 °C = 0 Z = 1

Вопрос 2

Из следующих задач, касающихся данного неориентированного графа G, о котором в настоящее время известно, что он разрешим за полиномиальное время?

  1.  Нахождение кратчайшего цикла в G
  2.  Нахождение крупнейшей клики в G
  3.  Нахождение всех прямых деревьев G
  4.  Нахождение самого длинного простого цикла в G
  5.  Нахождение раскраски вершин G (в которой соседние вершины имеют разные цвета) с минимальным количеством цветов

Вопрос 3

Предположим, что отладчик устанавливает точку останова на инструкции загрузки по виртуальному адресу 0x77E81234 (шестнадцатеричная запись) в отлаживаемом процессе P

Если текстовый сегмент P начинается по адресу с 0x77E80000 в виртуальном адресном пространстве P и если отладчик сопоставил этот же текстовый сегмент на 0x010000000 в своем виртуальном адресном пространстве

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

  1.  0x01001234; страница, отображаемая с доступом для ЧТЕНИЯ/ЗАПИСИ
  2.  0x01001234; страница, отображаемая с доступом к КОПИРОВАНИЮ ПРИ ЗАПИСИ
  3.  0x76E81234; страница, отображаемая с доступом для ЧТЕНИЯ/ЗАПИСИ
  4.  0x76E81234; страница, отображаемая с доступом к КОПИРОВАНИЮ ПРИ ЗАПИСИ
  5.  0x77E81234; страница, отображаемая с доступом для ЧТЕНИЯ/ЗАПИСИ

Вопрос 4

Пусть N — множество всех натуральных чисел.

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

  • Совокупность всех функций от N до {0, 1}
  • Набор всех функций от {0, 1} до N
  • Наибольшее подмножество из N
  1.  Нет правильных ответов
  2.  2 и 3
  3.  1 и 3
  4.  1 и 2
  5.  1, 2, 3

Вопрос 5

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

Input

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

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

Definition

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

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

Если для всех

Problem

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

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

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

Тогда

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

для и

для всех

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 6

Согласно стандарту IEEE, 32-разрядное число с плавающей запятой одинарной точности N определяется как

где S — знаковый бит, F — дробная мантисса, а E — смещенный показатель степени

Число с плавающей запятой хранится в формате S : E : F, где S, E и F хранятся в 1 бите, 8 битах и 23 битах соответственно

Каково десятичное значение числа с плавающей запятой C1E00000 (шестнадцатеричная система счисления)?

  1.  −26
  2.  26
  3.  −59
  4.  −15
  5.  −28

Вопрос 7

Два процессора, M-5 и M-7, реализуют один и тот же набор инструкций

Процессор M5 использует 5-ступенчатый конвейер и тактовый цикл 10 наносекунд

Процессор M-7 использует 7-ступенчатый конвейер и тактовый цикл 7,5 наносекунд

Что из приведенного ниже верно?

  • М-7 имеет лучшую максимальную пропускную способность, чем М-5
  • Задержка выполнения одной инструкции в M-7 меньше, чем в M-5
  • Программы, выполняемые на M-7, всегда будут выполняться быстрее, чем программы, выполняемые на M-5
  1.  2 и 3
  2.  Только 2
  3.  1 и 3
  4.  Только 1
  5.  1, 2, 3

Вопрос 8

Что из перечисленного НЕ является разумным обоснованием выбора режима активного ожидания для асинхронного события?

  1.  Процессору не нужно выполнять никакой другой задачи
  2.  Цикл ожидания занятости проще в программировании, чем обработчик прерываний
  3.  Программа выполняется в системе с разделением времени
  4.  Задача должна быть выполнена в сжатые сроки в режиме реального времени
  5.  Ожидается, что ожидание будет недолгим

Вопрос 9

Схема Эйлера неориентированного графа — это схема, в которой каждое ребро графа встречается ровно один раз

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

  • Полный граф с 12 вершинами
  • Полный граф с 13 вершинами
  • Дерево с 13 вершинами
  1.  1 и 2
  2.  1 и 3
  3.  Только 1
  4.  Только 3
  5.  Только 2

Вопрос 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.