Free Printable 156-236

1.

Пост машинасының автоматын іске қосқанда төмендегі жағдайдың қайсысы туындамайды

a)

автомат лента аяғына дейін жетті; программа жұмысы тоқтайды, автомат тоқтайды, нәтижесіз тоқтау болады

b)

автомат орындалмайтын командаға дейін орындап жетті (бос емес ұяшыққа белгіні жазу, бос ұяшықта белгіні өшіру); программаның орындалуы тоқтатылады, автомат тоқтайды, нәтижесіз тоқтату болады

c)

автомат тоқта командасына дейін жетті, программа орындалды деп есептеледі, нәтижесі бар тоқтату болады

d)

автомат нәтижелі де, нәтижесіз де тоқтатуға жетпеді, шексіз жұмыс істеу болады (автомат «тұрып қалады»)

e)

автомат лентада белгіні жазуды жүзеге асырды және келесі команданы орындауға көшеді

2.

Тьюринг машинасының конфигурациясы дегеніміз

a)

qa түріндегі тізбек, мұндағы a- лентаның құрамы, q– бастиектің ағымдағы күйі, ал оның орны  және  арасындағы көрінетін ұяшықты нұсқайды  и 

b)

{0, 1, ..., N-1} алфавитінің символдары

c)

операциялық орындайтын құрылғының дискретті күйлерінің жиыны

d)

cDq символдарының үштігі, мұндағы c – машинаның сыртқы алфавитінің символы, q - машинаның ішкі алфавитінің символы жңне D – қозғалысты сипаттайтын алфавиттің символы, яғни {R, L, S} жиыны

e)

a түріндегі тізбек, яғни бұл жағдайда бастиек лентаның сол жақ шетіне қозғалған

3.

Тьюринг машинасының сыртқы алфавиті дегеніміз

a)

{0, 1, ..., N-1} алфавитінің символдары

b)

операциялық орындайтын құрылғының дискретті күйлерінің жиыны

c)

cDq символдарының үштігі, мұндағы c – машинаның сыртқы алфавитінің символы, q - машинаның ішкі алфавитінің символы және D – қозғалысты сипаттайтын алфавиттің символы, яғни {R, L, S} жиыны

d)

qa түріндегі тізбек, мұндағы a- лентаның құрамы, q– бастиектің ағымдағы күйі, ал оның орны  және  арасындағы көрінетін ұяшықты нұсқайды  и 

e)

a түріндегі тізбек, яғни бұл жағдайда бастиек лентаның сол жақ шетіне қозғалған

4.

Тьюринг машинасының ішкі алфавиті дегеніміз

a)

операциялық орындайтын құрылғының дискретті күйлерінің жиыны

b)

{0, 1, ..., N-1} алфавитінің символдары

c)

cDq символдарының үштігі, мұндағы c – машинаның сыртқы алфавитінің символы, q - машинаның ішкі алфавитінің символы жңне D – қозғалысты сипаттайтын алфавиттің символы, яғни {R, L, S} жиыны

d)

qa түріндегі тізбек, мұндағы a- лентаның құрамы, q– бастиектің ағымдағы күйі, ал оның орны  және  арасындағы көрінетін ұяшықты нұсқайды  и 

e)

a түріндегі тізбек, яғни бұл жағдайда бастиек лентаның сол жақ шетіне қозғалған

5.

Пост машинасы үшін келтірілген программа көмегімен қандай есеп шешіледі

1. М 2

2. $\longrightarrow$ 3

3. М 4

4. тоқта

a)

бос лентаға екі белгі жазу

b)

бастиекті солға бірінші бос позицияға дейін қозғалту

c)

бірнеше санның біреуіне бірді қосу

d)

екі көрші ұяшыққа анализ жасау (кіріс ұяшықтары) және үшінші ұяшықты өзгерту (шығыс ұяшығы). Егер кіріс ұяшықтары белгіленген болса, онда шығысында белгі өшіріледі; егер кіріс ұяшықтарының ең болмағанда біреуінде белгі болмаса, онда шығыс ұяшықта белгі қойылады

e)

лентада кез келген ара қашықтықта жазылған a және b екі санын қосу

6.

Егер функцияның мәнін есептейтін алгоритм бар болса ол қалай аталады?

a)

Есептелінетін

b)

Шешілетін

c)

Шығарылатын

d)

рекурентті

e)

мақсатты

7.

Түрлі есептер шешімінің алгоритмі бар немесе жоқ екендігін дәлелдеу

a)

Тьюринг машинасының пайдасы

b)

Пост машинасының пайдасы

c)

Тьюринг машинасының мақсаты

d)

Марков алгоритмі пайдасы

e)

Марков машинасының пайдасы

8.

Тьюринг машинасына қойылатын талаптардың бірі:

a)

машина толықтай детерминенделген (есептеулер нақты және жалпы түсінікті) болуы қажет

b)

тапсырылған ережелер жүйесі негізінде әрекет етпеуі керек;

c)

«бастапқы мәліметтерді» енгізуге мүмкіндік берілмеуі керек;

d)

есептеулер түсінікті болуы қажет;

e)

берілген машинаның жұмыс жасау ережелерінің жүйесі және шешілетін есептердің класы машина жұмысы нәтижесін оқи алмайтындай болып келістірілуі керек.

9.

Абстрактілі Пост машинасы

a)

шексіз лента түрінде болады, ол жеке ұяшықтарға бөлінген, оған белгіні енгізеді немесе бастиек көмегімен белгіні жазады немесе оқиды.

b)

Шекті лента түрінде болады, ол жеке ұяшықтарға бөлінген, оған белгіні енгізеді немесе бастиек көмегімен белгіні жазады немесе оқиды.

c)

шексіз лента түрінде болады, оған белгіні енгізеді немесе бастиек көмегімен белгіні жазады немесе оқиды.

d)

шексіз лента түрінде болады, ол жеке ұяшықтарға бөлінген, белгіні жазады.

e)

ол жеке ұяшықтарға бөлінген, оған белгіні енгізеді немесе бастиек көмегімен белгіні жазады немесе оқиды.

10.

Тьюринг машинасы неден тұрады (қате жауапты табыңыз)?

a)

Шексіз ұяшықтардан

b)

ақпаратты лентадан;

c)

кареткадан (оқитын және жазатын бастиектен);

d)

лентаны тартатын механизмнен;

e)

операцияны орындайтын құрылғыдан тұрады.

11.

Алгоритмдердің жалпы қасиеттері мен заңдылықтарын, олардың ұғымдарының формальды модельдерін оқытатын ғылым

a)

Алгоритмдер теориясы

b)

Ақпараттар теориясы

c)

Сандар теориясы

d)

кибернетика

e)

Информатиканың теориялық негіздері

12.

Евклид алгоритмідеген не?

a)

екі санның ең үлкен ортақ бөлгішін табу

b)

екі санның ең кіші ортақ еселігін табу

c)

үш санның ең үлкен ортақ бөлгішін табу

d)

екі санның ең үлкен ортақ бөліндісін табу

e)

екі санның ең кіші ортақ бөлгішін табу

13.

Бастапқы алгоритмдер теориясының заманауи жұмысын кім жазды?

a)

Курт Гёдель (1931 жылы)

b)

Евклид

c)

А.Тьюринг

d)

Э.Пост

e)

А.Черч

14.

1950-жылдары алгоритмдер теориясына көп үлес қосқан ғалымдар

a)

Колмогоров және Марков

b)

Евклид пен Архимед

c)

А.Тьюринг пен Э.Пост

d)

А.Черч пен Курт Гёдель

e)

Марков пен Колмогоров

15.

Алгоритмдер теориясы пәнінің жүйелі зерттеулерінің объектісі

a)

Алгоритм

b)

Машина

c)

Ленте

d)

Программа

e)

Блок схема

16.

Кілті кіші элемент таңдалады. Ол бірінші элементпен ауыстырылады. Одан кейін қалған n –1 элементпен, n –2 элементпен, және т.б., осылайша бір ең үлкен элемент табылғанша. Сұрыптаудың қандай әдісі сипатталған?

a)

Тура таңдау әдісімен

b)

Көпіпшікті

c)

Шелл

d)

Шейкерлік

e)

тура қосу арқылы

17.

Алгоритм элементтердің көрші тұрған жұптары үшін салыстыру және орындарын ауыстыруға негізделген және осы процессті барлық элементтер реттелгенше жалғастыру керек. Сұрыптаудың қандай әдісі сипатталған?

a)

Көпіршікті

b)

Шелл

c)

Шейкерлік

d)

Таңдау арқылы

e)

Тура таңдау әдісімен

18.

Элементтер ойша “дайын” болған тізбектеріне және берілген тізбектерге бөлінеді. i = 2-ден бастап әрбір қадамда және i –ді әрдайым бірге өсіре отырып берілген тізбектен i –ші элемент алынады да, дайын тізбекке орналастырылады және де қажетті орынға қосылады. Сұрыптаудың қандай әдісі сипатталған?

a)

Тура қосу арқылы

b)

Көпіршікті

c)

Шелл

d)

Шейкерлік

e)

Тура таңдау әдісімен

19.

Бүкіл тізім элементтері араластырылған ішкі тізімдердің жиынтығы деп қарастырылады. Бірінші қадамда бұл ішкі тізімдір тек элементтер жұбы ретінде қарастырылады. Екінші қадамда әрбір топ төрт элементтен қарастырылады. Процессті қайталағанда әрбір ішкі тізімдегі элементтер саны өседі, ал сәйкес ішкі тізімдір саны азаяды. Ішкі тізімдерді сұрыптау тура қосу көмегімен сұрыптауды бір рет қолдану арқылы орындалады. Сұрыптаудың қандай әдісі сипатталған?

a)

Шелл

b)

Тура қосу арқылы

c)

Көпіршікті

d)

Шейкерлік

e)

Тура таңдау әдісі

20.

Алгоритм екі көрші элементтер жұбын салыстыру және қарастырған тізбектің бағытын алма кезек ауыстырып отыруға негізделген. Соңғы ауыстырудың орнын(индексін) сақтай отырып сұрыпталған және сұрыпталмаған тізімнің сол және оң жақ шетін өзгертеді. Процесс сол және оң жақ шеттері қиылысқанша жалғастырылады. Сұрыптаудың қандай әдісі сипатталған?

a)

шейкерлік

b)

шелл

c)

тура қосу арқылы

d)

көпіршікті

e)

тура таңдау әдісі

21.

Ақпарат термині латын тілінің «informatio» сөзінен аударылғанда қандай ұғымды білдіреді?

a)

баяндау, түсіндіру, мәлімет

b)

есептеу, мәлімдеу

c)

орындау, өңдеу

d)

басып шығару

e)

сақтау

22.

Ақпараттыңсапалыққасиетіне жатпайды:

a)

есте сақтау

b)

деректілік;

c)

дәлдік;

d)

объективтік;

e)

толықтылық;

23.

Хабарды беруді қамтамасыз ететін қандай да бір физикалы шаманың уақыт барысында өзгеруі

a)

сигнал

b)

хабар

c)

ақпарат

d)

мәлімет

e)

уақыт

24.

Алгоритмнің тиімділік түрлері:

a)

жүйелік тиімділік, кеңістіктің тиімділігі, есептеу тиімділігі

b)

жүйелік тиімділік, кеңістіктің тиімділігі, бағалау тиімділігі

c)

жүйелік тиімділік, математикалық тиімділік, есептеу тиімділігі

d)

сапалық тиімділік, кеңістіктің тиімділігі, есептеу тиімділігі

e)

жүйелік тиімділік, есептеу тиімділігі

25.

Бір есепті орындауға арналған екі немесе бірнеше алгоритмдердің орындалу жылдамдығын салыстыру үшін қолданылатын тиімділік

a)

жүйелік тиімділік

b)

кеңістіктің тиімділік

c)

есептеу тиімділігі

d)

бағалау тиімділігі

e)

математикалық тиімділік

26.

Қандай да бір алгоритм пайдаланатын ішкі жадтың салыстырмалы санының өлшемі

a)

кеңістіктің тиімділік

b)

жүйелік тиімділік

c)

есептеу тиімділігі

d)

бағалау тиімділігі

e)

математикалық тиімділік

27.

Алгоритмнің ішкі құрылымын қарастырады, оның жасалуын және алгоритмде қолданылатын итерациялар мен меншіктеу операторларын салыстыратын тесттердің санын да талдайды

a)

есептеу тиімділігі

b)

кеңістіктің тиімділік

c)

жүйелік тиімділік

d)

бағалау тиімділігі

e)

математикалық тиімділік

28.

Сұрыптау алгоритмдерінде алгоритм тиімділігін өлшемі ретінде не қолданылады?

a)

Салыстыру

b)

Талдау

c)

Бағалау

d)

іздеу

e)

Сұрыптау

29.

Алгоритм көмегімен есепті шешуге арналған элементар операциялардың саны

a)

Алгоритмнің қиындығы

b)

Алгоритмнің тиімділігі

c)

Алгоритмнің күрделілігі

d)

Алгоритмнің нақтылығы

e)

Алгоритмнің бар болуы

30.

егер есептi полиномдық уақытта асимптотикалық жолмен Тьюринг машинасында шешетiн алгоритм табылса, онда есепті

a)

уақыттық күрделi дейді

b)

логарифмдiк күрделi дейді

c)

сызықтық күрделi дейді

d)

экпоненциалдық күрделi дейді

e)

кубтық күрделi дейді

31.

Ақпараттық жүйе дегеніміз

a)

мәтіндік, фактографиялық және т.б. информацияны жинауға, сақтауға, іздеуге, өңдеуге және т.б. амалдарды орындауға арналған қолданбалы программалық жүйе. Ақпараттық жүйе пайдаланушымен диалог түрінде жұмыс істейді.

b)

қарапайым тізім, онда элементті қосу тізімнің бір жақ бөлігінде (кезек соңы), ал өшіру немесе элементпен жұмыс істеу тізімнің екінші бөлігінде (кезектің басы) орындалады.

c)

"Соңынан келіп - бірінші шығу" принципі бойынша ұйымдастырылған мәліметтер құрылымын сақтайтын компьютердің жедел жадының түрі.

d)

элементтерді тізбектің соңына да, алдына да қосуға мүмкіндік беретін, яғни кезек пен кезек қасиеттерін иемденген тізім түріндегі жад қүрылымы; екі шетгі кезек.

e)

дұрыс жауап жоқ

32.

Кезек дегеніміз …

a)

қарапайым тізім, онда элементті қосу тізімнің бір жақ бөлігінде (кезек соңы), ал өшіру немесе элементпен жұмыс істеу тізімнің екінші бөлігінде (кезектің басы) орындалады.

b)

"Соңынан келіп - бірінші шығу" принципі бойынша ұйымдастырылған мәліметтер құрылымын сақтайтын компьютердің жедел жадының түрі.

c)

элементтерді тізбектің соңына да, алдына да қосуға мүмкіндік беретін, яғни кезек пен кезек қасиеттерін иемденген тізім түріндегі жад қүрылымы; екі шетгі кезек.

d)

мәтіндік, фактографиялық және т.б. информацияны жинауға, сақтауға, іздеуге, өңдеуге және т.б. амалдарды орындауға арналған қолданбалы программалық жүйе. Ақпараттық жүйе пайдаланушымен диалог түрінде жұмыс істейді.

e)

дұрыс жауап жоқ

33.

Стек – бұл …

a)

дұрыс жауап жоқ

b)

"Соңынан келіп - бірінші шығу" принципі бойынша ұйымдастырылған мәліметтер құрылымын сақтайтын компьютердің жедел жадының түрі.

c)

элементтерді тізбектің соңына да, алдына да қосуға мүмкіндік беретін, яғни кезек пен кезек қасиеттерін иемденген тізім түріндегі жад қүрылымы; екі шетгі кезек.

d)

қарапайым тізім, онда элементті қосу тізімнің бір жақ бөлігінде (кезек соңы), ал өшіру немесе элементпен жұмыс істеу тізімнің екінші бөлігінде (кезектің басы) орындалады.

e)

мәтіндік, фактографиялық және т.б. информацияны жинауға, сақтауға, іздеуге, өңдеуге және т.б. амалдарды орындауға арналған қолданбалы программалық жүйе. Ақпараттық жүйе пайдаланушымен диалог түрінде жұмыс істейді.

34.

Дек – бұл …

a)

элементтерді тізбектің соңына да, алдына да қосуға мүмкіндік беретін, яғни кезек пен кезек қасиеттерін иемденген тізім түріндегі жад қүрылымы; екі шетгі кезек.

b)

дұрыс жауап жоқ

c)

"Соңынан келіп - бірінші шығу" принципі бойынша ұйымдастырылған мәліметтер құрылымын сақтайтын компьютердің жедел жадының түрі.

d)

қарапайым тізім, онда элементті қосу тізімнің бір жақ бөлігінде (кезек соңы), ал өшіру немесе элементпен жұмыс істеу тізімнің екінші бөлігінде (кезектің басы) орындалады.

e)

мәтіндік, фактографиялық және т.б. информацияны жинауға, сақтауға, іздеуге, өңдеуге және т.б. амалдарды орындауға арналған қолданбалы программалық жүйе. Ақпараттық жүйе пайдаланушымен диалог түрінде жұмыс істейді.

35.

Алгоритмнің күрделілігін талдаудың неше тәсілі бар?

a)

2

b)

3

c)

4

d)

5

e)

6

36.

Іздеу алгоритмдерінің күрделілігі түрлері (қате жауапты табыңыз)

a)

циклдік

b)

сызықты

c)

логарифмдік

d)

квадраттық

e)

кубтық

37.

Экспоненциальды күрделілік

a)

О(2^п)

b)

О(п)

c)

log2n

d)

О(п2)

e)

О(n3)

38.

Логарифмдік күрделілік

a)

О(n3)

b)

log2n

c)

О(2п)

d)

О(п)

e)

О(п²)

39.

Сызықты күрделілік

a)

О(п²)

b)

О(п)

c)

О(2^п)

d)

log₂n

e)

О(n³)

40.

«Информатика» терминінің ұғымдары:

a)

кибернетика

b)

инженерлік ғылым

c)

жинақтау ғылымы

d)

астрофизика

e)

экономика

41.

Ақпараттың өлшем бірлігі:

a)

байт

b)

3байт

c)

Лбайт

d)

Вбайт

e)

Фбайт

42.

Әлеуметтік талдауда қарастырылатын ақпараттың қасиеті:

a)

толықтық

b)

ерекшелік

c)

заттық

d)

сенімділік

e)

қымбаттық

43.

Ақпараттық ресурстың қасиеті:

a)

есте сақталуы

b)

өсуі

c)

төмендеуі

d)

ескерілуі

e)

жоғарылауы

44.

Логикалық алгебраның негізін қалаушы

a)

Буль

b)

Тьюринг

c)

Пост

d)

Колмогоров

e)

Ньютон

45.

A=1, B=0, С=1, болса, келесі өрнектің ақиқаттық мәні нешеге тең: (A∧B)∨C=

a)

1

b)

2

c)

3

d)

4

e)

0

46.

A=1, B=0, С=1, болса, келесі өрнектің ақиқаттық мәні нешеге тең: (A ∨C) ∧ B

a)

0

b)

1

c)

2

d)

3

e)

4

47.

A=1, B=0, С=1, болса, келесі өрнектің ақиқаттық мәні нешеге тең: A/(B∧C)

a)

1

b)

0

c)

-1

d)

2

e)

3

48.

A=1, B=0, С=1, F=0 болса, келесі өрнектің ақиқаттық мәні нешеге тең: (A∨B)∧(C∨F)

a)

1

b)

2

c)

3

d)

4

e)

0

49.

A=1, B=0, С=1, болса, келесі өрнектің ақиқаттық мәні нешеге тең: A∧ (B∧C)

a)

0

b)

1

c)

2

d)

3

e)

4

50.

Берілген қасиеттердің қайсысы ақпараттың сапалық қасиетіне жатпайды?

a)

өзектілігі;

b)

толықтылық;

c)

дәлдік;

d)

құндылық;

e)

түсініліктілік;

156-236

Total questions: 50

Worksheet time: 25mins

Similar Resources on Wayground