Тест по теории алгоритмов

1. Как называется графическое представление алгоритма:

a) последовательность формул;

b) блок-схема;

c) таблица;

d) словесное описание?

2. На рисунке представлена часть блок-схемы. Как она называется:

a) ветвление;

b) цикл;

c) вывод данных;

d) следование?

3. На рисунке представлена часть блок-схемы. Как она называется:

a) ветвление;

b) следование;

c) цикл с предусловием;

d) итерация?

4. На рисунке представлена часть блок-схемы. Как она называется:

a) альтернатива;

b) композиция;

c) цикл с предусловием;

d) цикл с постусловием?

5. На рисунке представлена часть блок-схемы. Как она называется:

a) альтернатива;

b) композиция;

c) цикл с постусловием;

d) цикл с предусловием?

6. Как называется конструкция блок-схемы, изображенная на рисунке:

a) выполнение операций;

b) начало-конец алгоритма;

c) вызов вспомогательного алгоритма;

d) ввод/вывод данных?

7. Как называется конструкция блок-схемы, изображенная на рисунке:

a) выполнение операций;

b) начало-конец алгоритма;

c) вызов вспомогательного алгоритма;

d) повторение в цикле со счетчиком?

8. Как называется конструкция блок-схемы, изображенная на рисунке:

a) выполнение операций;

b) начало-конец алгоритма;

c) вызов вспомогательного алгоритма;

d) ввод/вывод данных?

9. Как называется конструкция блок-схемы, изображенная на рисунке:

a) выполнение операций;

b) начало-конец алгоритма;

c) вызов вспомогательного алгоритма;

d) ввод/вывод данных?

10. Как называется конструкция блок-схемы, изображенная на рисунке:

a) выполнение операций;

b) начало-конец алгоритма;

c) вызов вспомогательного алгоритма;

d) ввод/вывод данных?

11. Как называется конструкция блок-схемы, изображенная на рисунке:

a) выполнение операций;

b) ввод/вывод данных

c) вызов вспомогательного алгоритма;

d) разветвление алгоритма?

12. Свойство алгоритма записываться в виде упорядоченной совокупности отделенных друг от друга предписаний (директив):

a) понятность;

b) определенность;

c) дискретность;

d) массовость.

13. Свойство алгоритма записываться в виде только тех команд, которые находятся в Системе Команд Исполнителя, называется:

a) понятность;

b) определенность;

c) дискретность;

d) результативность.

14. Свойство алгоритма записываться только директивами однозначно и одинаково интерпретируемыми разными исполнителями:

a) дискретность;

b) понятность

c) определенность;

d) результативность

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

a) понятность;

b) определенность;

c) дискретность;

d) результативность.

16. Свойство алгоритма обеспечения решения не одной задачи, а целого класса задач этого типа:

a) понятность;

b) определенность;

c) дискретность;

d) массовость.

17. Команда машины Поста имеет структуру п K m, где:

a) п – действие, выполняемое головкой; К – номер следующей команды, подлежащей выполнению; т – порядковый номер команды;

b) п – порядковый номер команды; К – действие, выполняемое головкой; т – номер следующей команды, подлежащей выполнению;

c) п – порядковый номер команды; К – номер следующей команды, подлежащей выполнению; т – действие, выполняемое головкой;

d) п – порядковый номер команды; К – действие, выполняемое головкой; т – номер клетки, с которой данную команду надо произвести.

18. Сколько существует команд у машины Поста:

a) 2;

b) 4;

c) 6;

d) 8?

19. В машине Поста останов будет результативным:

a) при выполнении недопустимой команды;

b) если машина не останавливается никогда;

c) если результат выполнения программы такой, какой и ожидался;

d) по команде «Стоп».

20. В программе для машины Тьюринга используются команды вида S K Q, где:

a) S – символ в текущей ячейке, K – действие, выполняемое головкой, Q – ячейка в которой необходимо выполнить действие

b) S – символ, который нужно поместить в текущую ячейку, K – действие, выполняемое головкой, Q – состояние, в которое нужно перевести головку

c) S – состояние, в которое нужно перевести головку, K – действие, выполняемое головкой, Q – символ, который нужно поместить в текущую ячейку

d) S – символ, который нужно поместить в текущую ячейку, K – состояние, в которое нужно перевести головку, Q – действие, выполняемое головкой

21. В машине Поста:

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

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

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

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

22. В алгоритме Маркова ассоциативным исчислением называется:

a) совокупность всех слов в данном алфавите;

b) совокупность всех допустимых систем подстановок;

c) совокупность всех слов в данном алфавите вместе с допустимой системой подстановок;

d) когда все слова в алфавите являются смежными.

23. В ассоциативном счислении два слова называются смежными:

a) если одно из них может быть преобразовано в другое применением подстановок;

b) если одно из них может быть преобразовано в другое однократным применением допустимой подстановки;

c) когда существует цепочка от одного слова к другому и обратно;

d) когда они дедуктивные.

24. В алгоритме Маркова дана цепочка Р, Р₁, Р₂ ... Р_к., , R. Если слова P, P₁, Р₂ , … Р_к, …R смежные, то цепочка называется:

a) ассоциативной;

b) эквивалентной;

c) индуктивной;

d) дедуктивной.

25. В алгоритме Маркова дана цепочка Р Р₁, Р₂ ... Р_к. Если слова Р, P₁, Р₂, ..., Р_к смежные и цепочка существует и в обратную сторону, то слова Р и Р_к называют:

a) ассоциативными;

b) эквивалентными;

c) индуктивными;

d) дедуктивными.

26. В алгоритмах Маркова дана система подстановок в алфавите A = {а, Ь, с}: abc ® с, ba ® cb, ca ® ab. Преобразуйте с помощью этой системы слово bacaabc:

a) cbc;

b) ccbcbbc;

c) cbacba;

d) cbabc.

27. В алгоритмах Маркова дана система подстановок в алфавите А = {а, b, с}: cb ® abc, bас ® ас, cab ® b. Преобразуйте с помощью этой системы слово bcabacab:

a) ccb;

b) cab;

c) cbc;

d) bcaab.

28. Алгоритм, в котором команды выполняются последовательно в том порядке, как они записаны, называется:

a) линейным алгоритмом

b) алгоритмом с ветвлением

c) алгоритмом с повторениями

d) алгоритмом с итерацией

29. Алгоритм, в котором выполнение той или группы команд зависит от выполнения некоторого условия, называется:

a) линейным алгоритмом

b) алгоритмом с полным ветвлением

c) циклическим алгоритмом с параметром

d) циклическим алгоритмом с условием

30. Алгоритм, в котором выполнение группы команд зависти от выполнения некоторого условия, называется:

a) линейным алгоритмом

b) алгоритмом с полым ветвлением

c) алгоритмом с неполным ветвлением

d) циклическим алгоритмом

31. Алгоритм, в котором группа команд выполняется заранее известное число раз, называют:

a) линейным алгоритмом

b) алгоритмом с ветвлением

c) циклическим алгоритмом с параметром

d) циклическим алгоритмом с условием

32. Алгоритм, в котором группа команд выполняется несколько раз в зависимости от выполнения некоторого условия, называют:

a) линейным алгоритмом

b) алгоритмом с ветвлением

c) циклическим алгоритмом с параметром

d) циклическим алгоритмом с условием

33. Как может передвигаться головка машины Тьюринга:

a) вдоль ленты влево и вправо в соседнюю ячейку

b) вдоль ленты влево и вправо на произвольное количество ячеек

c) вдоль ленты по диагонали на определенное число ячеек

d) вдоль ленты вверх и вниз

34. Как может передвигаться головка машины Поста:

a) вдоль ленты влево и вправо в соседнюю ячейку

b) вдоль ленты влево и вправо на произвольное количество ячеек

c) вдоль ленты по диагонали на определенное число ячеек

d) вдоль ленты вверх и вниз

35. Сколько лент у машины Поста?

a) 0

b) 1

c) 2

d) 3

36. Сколько ячеек на ленте машины Поста?

a) 1024

b) 16

c) 4096

d) бесконечное число

37. В каком году Эмиль Пост изобрел абстрактную машину для формализации понятия алгоритм:

a) 1736

b) 1836

c) 1936

d) 1636

38. В каком году Алан Тьюринг изобрел абстрактную машину для формализации понятия алгоритм:

a) 1637

b) 1737

c) 1837

d) 1937

39. В каком году А.А. Марков предложил алгоритмическую схему, в последствии названную нормальным алгоритмом Маркова?

a) 1753

b) 1953

c) 1653

d) 1853

40. Требуется ли для нормального алгоритма Маркова лента?

1) нет

2) да, необходима бесконечная лента

3) да, необходима конечная лента, содержащая 65525 ячеек

4) да, необходима лента, имеющая начало, но не имеющая конца

41. 42. Сколько символов используется для кодирования команд машины Поста?

1) 2

2) 4

3) 6

5) 8

42. Какой символ не используется для кодирования команд машины Поста:

1) !

2) ?

3) «

6) \/

43. Максимальное количество адресов перехода в команде машины Поста равно:

1) 4

2) 3

3) 2

4) 1

44. Задачи, не имеющие решения, приято называть:

1) алгоритмически не решаемые

2) алгоритмически неразрешимые

3) трудные задачи

4) таких задач не существует

45. Алгоритм – это:

1) правила дорожного движения;

2) понятное и точное предписание исполнителю совершить последовательность действий, направленных на достижение поставленных целей;

3) набор команд для компьютера;

4) протокол вычислительной сети.

46. Суть такого свойства алгоритма как результативность заключается в том, что:

1) алгоритм должен иметь дискретную структуру (должен быть разбит на последовательность отдельных шагов);

2) записывая алгоритм для конкретного исполнителя, можно использовать лишь те команды, что входят в систему его команд;

3) при точном исполнении всех команд алгоритма процесс должен прекратиться за конечное число шагов, приведя к определенному результату;

4) исполнитель алгоритма не должен принимать решения, не предусмотренные составителем алгоритма.

47. Суть такого свойства алгоритма как дискретность заключается в том, что:

1) алгоритм должен быть разбит на последовательность отдельных шагов;

2) записывая алгоритм для конкретного исполнителя, можно использовать лишь те команды, что входят в систему его команд;

3) алгоритм должен обеспечивать решение не одной конкретной задачи, а некоторого класса задач данного типа;

4) исполнитель алгоритма не должен принимать решения, не предусмотренные составителем алгоритма.

48. Алгоритм называется линейным:

1) если он составлен так, что его выполнение предполагает многократное повторение одних и тех же действий;

2) если ход его выполнения зависит от истинности тех или иных условий;

3) если его команды выполняются в порядке их естественного следования друг за другом независимо от каких-либо условий;

4) если он включает в себя вспомогательный алгоритм.

49. Определите значение переменной a после выполнения алгоритма:

1) 8

2) 16

3) 32

4) 12

50. Укажите наиболее полный перечень способов записи алгоритмов:

1) словесный, графический, программный, табличный;

2) словесный, схематичный, табличный, графический;

3) графический, программный;

4) словесный, программный;

51. Суть такого свойства алгоритма как массовость заключается в том, что:

1) алгоритм должен иметь дискретную структуру (должен быть разбит на последовательность отдельных шагов);

2) записывая алгоритм для конкретного исполнителя, можно использовать лишь те команды, что входят в систему его команд;

3) алгоритм должен обеспечивать решение не одной конкретной задачи, а некоторого класса задач данного типа;

4) исполнитель алгоритма не должен принимать решения, не предусмотренные составителем алгоритма.

52. Суть такого свойства алгоритма как понятность заключается в том, что:

1) алгоритм должен иметь дискретную структуру (должен быть разбит на последовательность отдельных шагов);

2) записывая алгоритм для конкретного исполнителя, можно использовать лишь те команды, что входят в систему его команд;

3) алгоритм должен обеспечивать решение не одной конкретной задачи, а некоторого класса задач данного типа;

4) при точном исполнении всех команд алгоритма процесс должен прекратиться за конечное число шагов, приведя к определенному результату;

53. Характерным признаком линейного алгоритма является:

1) строго последовательное выполнение команд в порядке их записи;

2) наличие в каждой строке только одной команды;

3) использование в нем исключительно команд с формулами;

4) присутствие в ней команд условного и безусловного перехода;

54. Какой из объектов может являться исполнителем алгоритма?

1) ножницы;

2) книга;

3) персональный компьютер;

4) карта.

55. Определите значение переменной m после выполнения фрагмента алгоритма.

1) 2

2) 10

3) 52

4) 70

56. В результате выполнения машины Поста следующих команд – 1 ® 2, 2 ? 3, 1, 3 ! 3:

1) головка сдвинется вправо вдоль пустых ячеек и остановится над первой меткой

2) головка сдвинется вправо вдоль массива меток и остановиться над первой пустой ячейкой

3) головка сдвинется на две ячейки вправо и остановиться

4) головка останется на месте, поставит метку в текущую ячейку и остановиться

57. В результате выполнения машины Поста следующих команд – 1 2, 2 ? 1, 3, 3 ! 3:

1) головка сдвинется влево вдоль пустых ячеек и остановится над первой меткой

2) головка сдвинется влево вдоль массива меток и остановиться над первой пустой ячейкой

3) головка сдвинется на две ячейки влево и остановиться

4) головка останется на месте, поставит метку в текущую ячейку и остановиться

Не нашли, что искали? Воспользуйтесь поиском по сайту: