Тест по теме "Графы"
Оценка 4.6

Тест по теме "Графы"

Оценка 4.6
Контроль знаний
docx
математика
Взрослым
10.06.2019
Тест по теме "Графы"
Тестовая работа направлена на проверку и контроль знаний, умений и навыков обучающихся после изучения темы "Графы". В тесте 88 заданий, что позволит преподавателю выбрать для своего пользования такие, которые будут соответствовать уровню подготовки обучающихся. Тестовая работа проводится среди студентов СПО.
Тест по теме - Графы.docx
Тест: Основы теории графов Задание №1 Графом называется… 1) + пара двух конечных множеств: множество точек и множество линий, соединяющих некоторые пары точек; 2) 3) 4) ­ ­ ­ пара двух бесконечных множеств: множество точек и множество линий, соединяющих некоторые пары точек; множество линий, соединяющих некоторые пары точек; пара двух конечных множеств: множество точек и множество линий. Задание №2 Точки графа называются… 1) Ответ: узлами Задание №3 Линии графа называются…  1) Ответ: ребрами Задание №4 Если ребро графа   соединяет две его вершины, то говорят, что это ребро им…  1) Ответ: инцидентно Задание №5 Если существует ребро, инцидентное двум вершинам графа, то эти вершины являются…  1) Ответ: смежными Задание №6 Ребро, имеющее совпадающие начало и конец, называется…  1) Ответ: петлей Задание №7 Ребра называются смежными, если они... инцидентны одной и той же вершине; параллельны; являются кратными. 1) + 2) 3) ­ ­ Задание №8 Какие из графов являются подграфами данного графа G: 1) + 2) + 3) + 4) ­ Задание №9 Эйлеров цикл… 1) 2) 3) + ­ ­ содержит каждое ребро только один раз; содержит каждую вершину только один раз; проходит через все вершины и ребра графа только один раз. Задание №10 Гамильтонов цикл… 1) ­ содержит каждое ребро только один раз; 2) 3) + ­ содержит каждую вершину только один раз; проходит через все вершины и ребра графа только один раз. Задание №11 В эйлеровом графе все вершины  1) 2) + ­ четной степени; нечетной степени. Задание №12 В полуэйлеровом графе допускаются 1) 2) 3) ­ + ­ 3 вершины нечетной степени; 2 вершины нечетной степени; 1 вершина нечетной степени. Задание №13 Какой   из   циклов   графа   с   множеством   вершин   {a,b,c,d,e,f}   является гамильтоновым? 1) 2) 3) 4) ­ ­ + ­  abeca fbecdf abecdfa abcdfca Задание №14 Какой граф является гамильтоновым: 1) ­ 2) + 3) + Задание №15 Граф содержит 7 дуг. Его эйлеров цикл будет состоять из: 1) 2) 3) 4) ­ + ­ ­ 6 дуг; 7 дуг; 8 дуг; 5 дуг. Задание №16 Простая цепь это: 1) 2) 3) 4) ­ ­ ­ + маршрут минимальной стоимости; маршрут, где нет повторяющихся вершин; маршрут, где нет повторяющихся ребер; маршрут, где нет повторяющихся вершин и ребер. Задание №17 Расстояние между вершинами есть... 1) 2) ­ + сумма длин ребер, входящих в путь; длина кратчайшего пути. Задание №18 Дерево есть... 1) 2) 3) 4) ­ ­ ­ + связный граф; граф без циклов; остовный подграф графа; связный граф без циклов. Задание №19 Если любые две вершины графа можно соединить простой цепью, то граф называется: 1) 2) 3) 4) + ­ ­ ­ связным; несвязным; деревом; остовом. Задание №20 Сколько вершин содержит гамильтонов цикл графа с 5 вершинами? 1) 2) 3) 4) + ­ ­ ­ 5; 4; 6; 7. Задание №21 Ребра называются кратными, если они... 1) 2) 3) 4) ­ ­ ­ + инцидентны одной и той же вершине; параллельны; являются смежными; имеют одинаковые направления. Задание №22 Расстояние до вершины дерева называют: 1) 2) 3) 4) + ­ ­ ­ ярусом вершины; высотой вершины; удаленностью вершины; этажом. Задание №23 Конечный   связный   граф   с   выделенной   вершиной   (корнем),   не   имеющий циклов, называют…  1) Ответ: деревом Задание №24 . Глубина элемента а2 в дереве    равна: а2 1) 2) 3) 4) ­ ­ + ­ 0; 1; 2; 3. Задание №25 а2 Степень вершины а2 в графе    равна: 1) 2) 3) 4) ­ ­ ­ + 0; 1; 2; 3. Задание №26 В графе из n вершин остов содержит: 1) 2) 3) ­ + ­  n+1 ребро; n­1 ребро; n ребер; 4) ­ 2n ребер. Задание №27 Упорядоченное   объединение   деревьев,   представляющее   собой   несвязный граф, называется…  1) Ответ: лесом Задание №28 Дерево,   в   котором   поддеревья   каждого   узла   образуют   упорядоченное подмножество называется..  1) Ответ: упорядоченным Задание №29 Если   каждая   из   вершин   неориентированного   графа   соединена   рёбрами   с остальными, то такой граф называется: 1) 2) 3) 4) ­ ­ ­ + гиперграфом; мультиграфом; цепью; полным графом. Задание №30 Последовательность   ребер,  в   которой   каждые   два   соседних   ребра  имеют общую вершину, и никакое ребро не встречается более одного раза – это… 1) 2) 3) 4) ­ + ­ ­ цикл; путь; дорога; прекция. Задание №31 После удаления из дерева одной из концевых вершин вместе с инцидентным ей ребром  получается: 1) 2) 3) 4) ­ + ­ ­ орграф; дерево; цепь; связь. Задание №32 Ребро   графа   является   |____|   тогда   и   только   тогда,   когда   в   графе   нет циклов,содержащих это ребро. 1) 2) 3) 4) ­ ­ + ­ связным мостом; связным графом; мостом; орграфом; Задание №33 Ребро связного графа G называется _____, если после его удаления G станет несвязным и распадется на два связных графа G’ и G".  1) Ответ: мост Задание №34 Бинарное дерево уровня n называется ____, если каждый его узел уровня n является листом, а каждый узел уровня меньше, чем n, имеет непустое левое и правое поддеревья.  1) Ответ: полным Задание №35 Висячие вершины дерева, за исключением корневой, называются... 1) Ответ: листьями Задание №36 Любой граф, изоморфный плоскому называется: 1) 2) 3) 4) ­ ­ ­ + Кратный Симметрический Хроматический Планарный Задание №37 Граф   называется   |____|,   если   существует   такое   разбиение   множества   его вершин на две части, что концы каждого ребра принадлежат разным частям. 1) 2) 3) 4) ­ + ­ ­ 2­хроматичным Двудольным Двойным Симметричным Задание №38 Для того, чтобы конечный связный граф был деревом, необходимо и достаточно, чтобы число его ребер было: 1) 2) 3) 4) ­ ­ ­ + Больше или равно числу его вершин Равно числу его вершин На единицу больше числа его вершин На единицу меньше числа его вершин Задание №39 Выберите верные утверждения: 1) 2) 3) 4) + + ­ ­ Цикломатическое число дерева равно нулю. Цикломатическое число леса равно нулю. Цикломатическое число леса равно всегда положительно Для   остальных   графов   цикломатические   числа   — отрицательные. Задание №40 Некоторое множество вершин графа такое, что для любых двух вершин из этого множества существует путь из одной в другую, и не существует пути из вершины этого множества в вершину не из этого множества, называется… 1) 2) 3) 4) ­ ­ + ­ Цикломатическим числом Кольцевой суммой Компонентой связности Степенью  Задание №41 Для того чтобы связный граф G являлся простым циклом, необходимо и достаточно, чтобы каждая его вершина имела степень, равную: 1) 2) 3) 4) ­ ­ ­ + 2; 1; 3; 0. Задание №42 Способы задания графа: 1) 2) 3) 4) + ­ ­ + Геометрический Указание вершин Перечисление ребер Матричный Задание №43 Геометрическое представление плоского графа называется его…  1) Ответ: реализацией Задание №44 Если   граф   имеет   матрицу   смежности   и   не   имеет   петель,   на   главной диагонали у него всегда стоят: 1) 2) + ­ нули; единицы. Задание №45 Выберите верные утверждения. В матрице инцидентности для неориентированного графа: 1) 2) 3) 4) + ­ ­ + bij = 1, если вершина Vi инцидентна ребру Xj; bij = 0, если вершина Vi  инцидентна ребру Xj; bij = ­1, если вершина Vi не инцидентна ребру Xj; bij = 0, если вершина Vi не инцидентна ребру Xj. Задание №46 Выберите верные утверждения. В матрице инцидентности для ориентированного графа: 1) 2) 3) 4) + + ­ + bij = 1, если вершина Vi является началом дуги Xj; bij = ­1, если вершина Vi является концом дуги Хj; bij = 0, если вершина Vi является концом дуги Хj; bij = 0, если вершина Vi не инцидентна дуге Xj. Задание №47 Выберите верные утверждения. 1) + 2) ­ 3) + 4) ­ Матрица   смежности   неориентированного   графа   является симметрической. Матрица   смежности   неориентированного   графа   меняется   при транспонировании Матрица смежности неориентированного графа не меняется при транспонировании. Матрица   смежности   неориентированного   графа     не   является симметрической. Задание №48 Граф называется ______, если каждому его ребру поставлено в соответствие некоторое число.  1) Ответ: сеть Задание №49 Минимально возможное описание сущности некоторого явления, объекта, события или процесса называется… 1) 2) 3) 4) ­ + ­ ­ Слот; Фрейм; Сеть; Вес. Задание №50 Набор   стандартных   единиц, информации о содержании и назначении фрейма  ­ это...   содержащих   определенный   минимум 1) Ответ: слот Задание №51 Любой   подграф   связного графа G, содержащий все вершины графа G и являющийся деревом, называется…  1) Ответ: остов Задание №52 Если вершине инцидентна петля, то степень этой вершины равна (запишите число):  1) Ответ: 2 Задание №53 Вершина графа, имеющая степень, равную нулю, называется: 1) 2) ­ ­ нулевой; отдельной; 3) 4) + ­ изолированной; висячей. Задание №54 Граф, состоящий из изолированных вершин, называется... 1) Ответ: нуль­граф Задание №55 Вершина графа, имеющая степень, равную 1, называется: 1) 2) 3) 4) ­ + ­ ­ изолированной; висячей; свободной; связной. Задание №56 Число нечетных вершин любого графа — … 1) Ответ: четно Задание №57 На рисунке ­ схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Ж? 1) Ответ: 33 Задание №58 На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л.   По   каждой   дороге   можно   двигаться   только   в   одном   направлении, указанном стрелкой. Сколько существует различных путей из города А в город Л? 1) Ответ: 36 Задание №59 На рисунке ­ схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З. По каждой дороге  можно  двигаться  только в одном направлении,  указанном стрелкой. Сколько существует различных путей из города А в город З? 1) Ответ: 14 Задание №60 На рисунке ­ схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К? 1) Ответ: 12 Задание №61 На рисунке ­ схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К ? 1) Ответ: 12 Задание №62 На рисунке ­ схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге  можно  двигаться  только в одном направлении,  указанном стрелкой. Сколько существует различных путей из города А в город К?  1) Ответ: 13 Задание №63 Рыцарь, находясь в пункте А, узнал, что Прекрасной Даме, в пункте К, через 14   часов   может   грозить   опасность.   Взяв   с   собой   карту,   он   немедленно выехал на помощь. Числа на рисунке обозначают время движения (в часах) от пункта до пункта. Успеет ли рыцарь спасти Прекрасную Даму?  (Ответ запишите в форме: Нет АБЕК 17 или Да АБЕК 17) 1) Ответ: Да АБВЖГИЗК 14 Задание №64 Винни­Пух   вышел   на   прогулку,   взяв   с   собой   карту.   Числа   на   рисунке обозначают   время  движения  (в минутах)  от  пункта  до  пункта. Помогите Винни­Пуху найти кратчайший путь от своего дома в пункте А до дома Пятачка в пункте К. Перечислите пункты, через которые должен пройти Винни­Пух, и подсчитайте время, которое он затратит на весь путь. (Ответ запишите в форме: АВЖЗДК 80) 1) Ответ: АБЕДЗК 60 Задание №65 Атос поскакал в гости к Портосу, взяв с собой карту. Числа на рисунке обозначают время движения (в часах) от пункта до пункта. Помогите Атосу найти кратчайший путь от своего поместья в пункте Е до поместья Портоса в пункте Д. Перечислите пункты, через которые должен проехать Атос, и подсчитайте время, которое он затратит на весь путь. (Ответ запишите в форме:  ЕКЗИГД 20)  1) Ответ: ЕЖВБАД 12 Задание №66 Рыцарь, находясь в пункте А, узнал, что Прекрасной Даме, в пункте О, ровно через сутки может грозить опасность. Взяв с собой карту,  он немедленно выехал на помощь. Числа на рисунке обозначают время движения (в часах) от   пункта   до   пункта.   Успеет   ли   рыцарь   спасти   Прекрасную   Даму? Обоснуйте ответ, указав кратчайший маршрут и время, затраченное на весь путь. (Ответ запишите в форме: Нет АБВГО 38 или Да АБВГО 38) 1) Ответ: Нет АКЛДО 25 Задание №67 Во дворе живут 4 пёсика: Бобик, Робик, Тобик и Толстолобик. Каждому из них случалось драться с кем­нибудь из остальных, причём у Бобика, Робика и Тобика число тех, с кем они дрались – разное. Со сколькими собаками двора дрался Толстолобик?  1) Ответ: 2 Задание №68 Лес состоит из 10 деревьев. Всего в лесу 200 вершин. В нём ___ребер.  1) Ответ: 190 Задание №69 Каждое ребро графа покрасили в синий или зелёный цвет так, что ни из одной вершины не выходит двух одноцветных рёбер. Синих рёбер оказалось на 5 больше, чем зелёных. Какое наименьшее число компонент связности может иметь этот граф? 1) Ответ: 5 Задание №70 Сколько всего рёбер в графе, степени вершин которого равны 3, 4, 5, 3, 4, 5, 3, 4, 5? 1) 2) 3) ­ ­ + 10; 20; 18. Задание №71 В деревне Вишкиль  9 домов. Из каждого дома тянется четыре шланга к четырём другим домам. Сколько шлангов в деревне? 1) 2) 3) ­ + ­ 16; 18; 36. Задание №72 Какое минимальное количество рёбер нужно убрать из полного графа с 15 вершинами, чтобы он перестал быть связным? 1) 2) 3) ­ + ­ 18; 14; 15. Задание №73 Сколько рёбер в полном графе с 20 вершинами? 1) 2) 3) ­ ­ + 180 200 190 Задание №74 Цикломатическое число графа рассчитывается по формуле: v(G) = m(G) + c(G) – n(G), где: 1) 2) 3) 3 1 2 m(G) c(G) n(G) число   связных   компонент графа число вершин число его ребер 1) 2) 3) Задание №75 Соотнесите понятия  и определения: Цепь 1) 2 Цикл 2) 4 Последовательность   ребер неориентированного графа, в 1) которой   вторая   вершина ребра предыдущего   совпадает с первой вершиной следующего 2) Маршрут , в котором ребро встречается только один раз Маршрут 3) 1 Путь 4) 3 Задание №76 Соотнесите понятия  и определения: Связные графы 1) 2 2) 3) 3 1 Упорядоченная последовательность ребер   ориентированного 3) графа,   в   которой   конец предыдущего ребра     совпадает   началом следующего   и   все   ребра с единственны Путь, у которого совпадают начало и конец Любые   подграфы   связного   содержащие   все графа, вершины   графа   G   и являющиеся деревом   между   любыми Графы, двумя   вершинами   которых есть маршрут 4) 1) 2) Планарные(плоские) графы Остовы 3) Графы,   которые   имеют изоморфные   им   графы,   в изображении   которых   на ребра плоскости пересекаются   только   в вершинах Графы,   имеющие   взаимно­ однозначное   соответствие между   их   ребрами   и вершинами,   причем   со­ 4) ответствующие ребра соединяют   соответствующие   вершины Изоморфные графы 4) 4 Задание №77 Установите соответствие: Объединение графов 1) 3 1) Пересечение графов 2) 2 2) Подграф  3) 3 3) Кольцевая сумма 4) 4 4) Задание №78 Установите соответствие: Граф   со   смежными вершинами Полный граф Граф   со   смежными ребрами Граф с петлей 1) 2) 3) 4) 1) 4 2) 3 3) 1 4) 2 Задание №79 Соотнесите понятия и определения: 1) 4 Строго бинарное дерево 1) Бинарное   дерево,   каждый узел   уровня   n   которого является   листом,   а   каждый узел   уровня   меньше,   чем   n, имеет   непустое   левое   и Полное бинарное дерево правое поддеревья. подмножество   множества деревьев, когда каждый узел 2) либо  является  листом,  либо образует   два   поддерева: левое и правое. Бинарное дерево дерево,   в   котором 3) поддеревья   каждого   узла образуют   упорядоченное подмножество. Упорядоченное дерево такой   граф,   у   которого каждый узел, не являющийся листом,   содержит   два   и 4) только   два   поддерева   — левое и правое. 2) 1 3) 2 4) 3 Задание №80 Укажите степени вершин графа  1) V1 2) V2 2 5 3) V3 4) V4 5) V5 6) V6 7) V7 3 3 3 4 4 Задание №81 Укажите степени вершин графа  1) V1 2) V2 3) V3 4) V4 5) V5 6) V6 5 4 5 6 4 5 Задание №82 Укажите степени вершин графа 1) V1 2) V2 3) V3 4) V4 5) V5 6) V6 7) V7 4 4 4 4 5 5 6 Задание №83 Укажите степени вершин графа  1) V1 2) V2 3) V3 4) V4 5) V5 6) V6 4 3 5 2 3 4 7) V7 5 Задание №84 Найдите цикломатическое число графа G  1) Ответ: 6 Задание №85 Найдите цикломатическое число графа G  1) Ответ: 9 Задание №86 Найдите цикломатическое число графа G  1) Ответ: 10 Задание №87 Найдите цикломатическое число графа G  1) Ответ: 7 Задание №88 Найдите цикломатическое число графа G 1) Ответ: 0

Тест по теме "Графы"

Тест по теме "Графы"

Тест по теме "Графы"

Тест по теме "Графы"

Тест по теме "Графы"

Тест по теме "Графы"

Тест по теме "Графы"

Тест по теме "Графы"

Тест по теме "Графы"

Тест по теме "Графы"

Тест по теме "Графы"

Тест по теме "Графы"

Тест по теме "Графы"

Тест по теме "Графы"

Тест по теме "Графы"

Тест по теме "Графы"

Тест по теме "Графы"

Тест по теме "Графы"

Тест по теме "Графы"

Тест по теме "Графы"

Тест по теме "Графы"

Тест по теме "Графы"

Тест по теме "Графы"

Тест по теме "Графы"

Тест по теме "Графы"

Тест по теме "Графы"

Тест по теме "Графы"

Тест по теме "Графы"

Тест по теме "Графы"

Тест по теме "Графы"

Тест по теме "Графы"

Тест по теме "Графы"

Тест по теме "Графы"

Тест по теме "Графы"

Тест по теме "Графы"

Тест по теме "Графы"

Тест по теме "Графы"

Тест по теме "Графы"

Тест по теме "Графы"

Тест по теме "Графы"

Тест по теме "Графы"

Тест по теме "Графы"

Тест по теме "Графы"

Тест по теме "Графы"

Тест по теме "Графы"

Тест по теме "Графы"

Тест по теме "Графы"

Тест по теме "Графы"

Тест по теме "Графы"

Тест по теме "Графы"

Тест по теме "Графы"

Тест по теме "Графы"

Тест по теме "Графы"

Тест по теме "Графы"

Тест по теме "Графы"

Тест по теме "Графы"

Тест по теме "Графы"

Тест по теме "Графы"

Тест по теме "Графы"

Тест по теме "Графы"

Тест по теме "Графы"

Тест по теме "Графы"

Тест по теме "Графы"

Тест по теме "Графы"

Тест по теме "Графы"

Тест по теме "Графы"

Тест по теме "Графы"

Тест по теме "Графы"

Тест по теме "Графы"

Тест по теме "Графы"
Скачать файл