Тест по теме «Алгоритмы и структуры данных» помогает системно оценить понимание ключевых принципов разработки программ и эффективной организации данных.
алгоритмы и структуры данных
Вопросы охватывают базовые алгоритмические конструкции, линейные и нелинейные структуры данных, принципы работы со списками, стеками, очередями, деревьями и графами. Такой тест позволяет проверить не только теоретические знания, но и способность применять их для решения практических задач.
Материал ориентирован на учащихся, студентов технических специальностей и всех, кто изучает программирование. Тест помогает укрепить фундаментальные навыки построения алгоритмов, выбора подходящей структуры данных и анализа сложности операций. Он будет полезен как для подготовки к экзаменам и зачётам, так и для самостоятельной проверки уровня знаний перед изучением более сложных тем.
1. Структура данных представляет собой: | ||
1) | набор правил и ограничений, определяющих связи между отдельными элементами и группами данных | |
2)+ | набор правил и ограничений, определяющих связи между отдельными элементами данных | |
3) | набор правил и ограничений, определяющих связи между отдельными группами данных | |
4) | некоторую иерархию данных | |
ⓘ Набор правил и ограничений, определяющих связи между отдельными элементами данных. Это фундаментальное определение показывает, как элементы взаимосвязаны и организованы для эффективной обработки информации | ||
2. В чём особенности очереди? | ||
1)+ | открыта с обеих сторон | |
2) | открыта с одной стороны на вставку и удаление | |
3) | доступен любой элемент | |
ⓘ Очередь реализует принцип FIFO: первый добавленный элемент извлекается первым. Это используется в обработке задач и потоках данных | ||
3. В чём особенности стека? | ||
1) | открыт с обеих сторон на вставку и удаление | |
2) | доступен любой элемент | |
3)+ | открыт с одной стороны на вставку и удаление | |
ⓘ Стек работает по принципу LIFO: доступен только верхний элемент для добавления или удаления. Применяется для управления вызовами функций, обработки выражений и undo-операций | ||
4. Какую дисциплину обслуживания принято называть FIFO? | ||
1) | стек | |
2)+ | очередь | |
3) | дек | |
ⓘ FIFO (First In, First Out) — это очередь, где первый добавленный элемент извлекается первым. Применяется в буферах и планировании задач | ||
5. Какая операция читает верхний элемент стека? | ||
1) |
| |
2) |
| |
3)+ |
| |
ⓘ Операция pop извлекает верхний элемент стека. Для просто просмотра используют peek. Это основной метод работы со стеком | ||
6. Каково правило выборки элемента из стека? | ||
1) | первый элемент | |
2)+ | последний элемент | |
3) | любой элемент | |
ⓘ Стек работает по принципу LIFO — последний добавленный элемент выбирается первым. Используется в рекурсии и undo-функциях | ||
7. Структуры данных делятся на статические и динамические. Статические — это: | ||
1)+ | структуры фиксированного размера | |
2) | структуры, выделяемые в куче | |
3) | структуры с автоматическим освобождением | |
ⓘ Статические структуры имеют фиксированный размер, заданный при компиляции. Они просты, но менее гибкие, чем динамические | ||
8. Как называется принцип работы стека? | ||
1)+ | LIFO | |
2) | FIFO | |
3) | LILO | |
ⓘ Принцип LIFO — Last In, First Out: последний добавленный элемент извлекается первым | ||
9. Как называется операция добавления элемента в очередь? | ||
1) |
| |
2)+ |
| |
3) |
| |
ⓘ Вставка элемента в очередь называется enqueue, удаление — dequeue. Это стандартные операции FIFO | ||
10. Какая структура данных обеспечивает доступ к элементам по индексу? | ||
1)+ | массив | |
2) | стек | |
3) | очередь | |
ⓘ Массив обеспечивает прямой доступ к элементам по индексу за O(1), что отличается от последовательного доступа в списках | ||
11. Что определяет интерфейс структуры данных? | ||
1)+ | набор допустимых операций | |
2) | физический способ хранения | |
3) | размер памяти | |
ⓘ Интерфейс определяет набор допустимых операций с объектом, независимо от конкретной реализации или способа хранения | ||
12. Что такое абстрактный тип данных (АТД)? | ||
1) | описание байтовой структуры хранения | |
2)+ | описание набора операций и их поведения | |
3) | минимальный набор полей объекта | |
4) | структура для компиляции | |
ⓘ АТД описывает набор операций и их поведение без указания способа хранения. Это позволяет менять реализацию без изменения интерфейса | ||
13. Что определяет реализация структуры данных? | ||
1) | только набор операций | |
2)+ | конкретный способ хранения данных и выполнения операций | |
3) | только интерфейс | |
4) | объём оперативной памяти | |
ⓘ Реализация определяет конкретный способ хранения и выполнения операций, обеспечивая физическую организацию данных | ||
14. Какая структура данных обеспечивает минимальное время доступа по индексу? | ||
1)+ | массив | |
2) | связный список | |
3) | очередь | |
4) | дек | |
ⓘ Массив предоставляет прямой доступ к любому элементу за O(1), в отличие от списков с последовательным доступом | ||
15. Какая характеристика относится к структурам данных с последовательным доступом? | ||
1) | операции доступа выполняются за O(1) | |
2)+ | для получения элемента требуется пройти элементы по порядку | |
3) | всегда хранятся в статической памяти | |
4) | поддерживают доступ с конца только | |
ⓘ Для последовательного доступа нужно проходить элементы по порядку. Это характерно для списков и очередей, где прямой доступ по индексу отсутствует | ||
16. Какая структура данных обеспечивает гарантированную упорядоченность по ключу? | ||
1)+ | дерево поиска | |
2) | стек | |
3) | очередь | |
4) | массив | |
ⓘ Дерево поиска автоматически поддерживает порядок ключей, что ускоряет поиск, вставку и удаление | ||
1. Линейный список, в котором доступен только последний элемент, называется: | ||
1)+ | стеком | |
2) | очередью | |
3) | деком | |
4) | массивом | |
5) | кольцом | |
ⓘ Стек обеспечивает доступ только к верхнему элементу (последнему добавленному), что реализует принцип LIFO — Last In, First Out | ||
2. Структура данных, работа с элементами которой организована по принципу FIFO, это: | ||
1) | Стек | |
2) | Дек | |
3)+ | Очередь | |
4) | Список | |
ⓘ Очередь работает по принципу «первый пришёл — первый ушёл» (FIFO), обеспечивая последовательную обработку данных | ||
3. Линейный последовательный список, в котором включение и исключение элементов возможно с обоих концов, называется: | ||
1) | стеком | |
2) | очередью | |
3)+ | деком | |
4) | кольцевой очередью | |
ⓘ Дек (double-ended queue) позволяет вставлять и удалять элементы с двух концов, объединяя возможности стека и очереди | ||
4. С помощью какой структуры данных наиболее рационально реализовать очередь? | ||
1) | стек | |
2)+ | список | |
3) | дек | |
ⓘ Связный список позволяет динамически добавлять и удалять элементы в начале и конце, что удобно для реализации очереди без ограничения размера | ||
5. Какая операция помещает элемент в стек? | ||
1)+ |
| |
2) |
| |
3) |
| |
ⓘ Операция push добавляет новый элемент на верх стека, соблюдая принцип LIFO | ||
6. Какая операция удаляет элемент из очереди? | ||
1) |
| |
2)+ |
| |
3) |
| |
ⓘ Операция dequeue удаляет элемент, который был добавлен первым, обеспечивая FIFO-обслуживание | ||
7. Что является недостатком реализации стека на массиве? | ||
1)+ | ограниченный размер | |
2) | сложность доступа к элементам | |
3) | высокая стоимость pop | |
ⓘ Стек на массиве имеет фиксированный размер, и при переполнении нельзя добавить новые элементы без изменения структуры | ||
8. Что происходит при переполнении очереди в массиве? | ||
1)+ | невозможность вставки нового элемента | |
2) | удаление всех элементов | |
3) | очередь превращается в дек | |
ⓘ Если массив для очереди заполнен, вставить новый элемент невозможно, так как размер статичен | ||
9. Что обеспечивает дек? | ||
1)+ | вставку и удаление с обоих концов | |
2) | доступ по индексу | |
3) | только удаление | |
ⓘ Дек позволяет вставлять и удалять элементы с обоих концов, комбинируя свойства стека и очереди | ||
10. Как называется очередь, в которой используется кольцевой буфер? | ||
1)+ | кольцевая очередь | |
2) | двусторонняя очередь | |
3) | динамическая очередь | |
ⓘ Кольцевая очередь использует циклический буфер, что позволяет эффективно повторно использовать память без сдвига элементов | ||
11. Как называется операция просмотра верхнего элемента стека без удаления? | ||
1)+ |
| |
2) |
| |
3) |
| |
ⓘ Операция peek позволяет получить значение верхнего элемента, не удаляя его, что важно для проверки текущего состояния стека | ||
12. Как работает приоритетная очередь? | ||
1)+ | удаляет элемент с наибольшим или наименьшим приоритетом | |
2) | всегда удаляет первый добавленный | |
3) | работает только как стек | |
ⓘ Приоритетная очередь извлекает элемент с наивысшим или наинизшим приоритетом, а не по порядку добавления, что важно для алгоритмов планирования | ||
13. Что произойдёт, если выполнить pop для пустого стека? | ||
1)+ | ошибка | |
2) | очистка стека | |
3) | возврат произвольного значения | |
ⓘ Попытка извлечь элемент из пустого стека вызывает ошибку underflow — недостаток элементов для операции | ||
14. Какая структура данных является обобщением и стека, и очереди? | ||
1)+ | дек | |
2) | массив | |
3) | список | |
ⓘ Дек объединяет возможности стека и очереди, позволяя работать с обоих концов | ||
15. Для чего используется двойная очередь ввода-вывода (deque)? | ||
1)+ | для эффективных операций на обоих концах списка | |
2) | для хранения уникальных элементов | |
3) | для блокировки доступа по индексу | |
ⓘ Deque позволяет эффективно выполнять операции вставки и удаления с двух концов, что полезно в алгоритмах с обеих сторон очереди | ||
1. Как освободить память от удаленного из списка элемента? | ||
1) |
| |
2) |
| |
3)+ |
| |
4) |
| |
ⓘ Операция freenode(p) освобождает память, занятую узлом, предотвращая утечки памяти при работе со связными структурами | ||
2. Как создать новый элемент списка с информационным полем | ||
1) |
| |
2)+ |
| |
3) |
| |
ⓘ Сначала выделяется память для узла через getnode, затем в поле info(p) помещается значение D, что обеспечивает корректное хранение данных | ||
3. Как создать пустой элемент с указателем | ||
1)+ |
| |
2) |
| |
3) |
| |
4) |
| |
ⓘ Операция p=getnode выделяет память для нового узла и инициализирует указатель, готовя элемент к дальнейшему использованию | ||
4. Сколько указателей используется в конструкции узла односвязного списка? | ||
1)+ | 1 | |
2) | 2 | |
3) | сколько угодно | |
ⓘ Односвязный список содержит один указатель next, который указывает на следующий узел, обеспечивая линейную последовательность элементов | ||
5. При удалении элемента из кольцевого списка | ||
1) | список разрывается | |
2) | в списке образуется дыра | |
3)+ | список становится короче на один элемент | |
ⓘ Удаление узла просто сокращает список на один элемент, при этом сохраняется кольцевая структура | ||
6. Для чего используется указатель в кольцевых списках? | ||
1)+ | для ссылки на следующий элемент | |
2) | для запоминания номера сегмента расположения элемента | |
3) | для ссылки на предыдущий элемент | |
4) | для расположения элемента в списке памяти | |
ⓘ Указатель в кольцевых списках указывает на следующий элемент, обеспечивая непрерывное циклическое прохождение по узлам | ||
7. Чем отличается кольцевой список от линейного? | ||
1)+ | в кольцевом списке последний элемент является одновременно и первым | |
2) | в кольцевом списке указатель последнего элемента пустой | |
3) | в кольцевых списках последнего элемента нет | |
4) | в кольцевом списке указатель последнего элемента не пустой | |
ⓘ В кольцевом списке последний элемент ссылается на первый, создавая замкнутую структуру без начала и конца | ||
8. Сколько указателей используется при программировании односвязного кольцевого списка? | ||
1)+ | 1 | |
2) | 2 | |
3) | сколько угодно | |
ⓘ Для односвязного кольцевого списка достаточно одного указателя на следующий элемент, чтобы организовать циклическую структуру | ||
9. В каких направлениях можно перемещаться в кольцевом двунаправленном списке? | ||
1)+ | в обоих | |
2) | влево | |
3) | вправо | |
ⓘ Двусвязный кольцевой список позволяет перемещаться как вперёд, так и назад, используя два указателя: на следующий и на предыдущий узел | ||
10. Какое преимущество связного списка перед массивом? | ||
1)+ | динамическое изменение размера | |
2) | быстрый доступ по индексу | |
3) | меньший расход памяти | |
ⓘ Связные списки позволяют динамически изменять размер, вставлять и удалять элементы без сдвига всех остальных, в отличие от массивов фиксированного размера | ||
11. Где удобнее всего использовать кольцевой список? | ||
1)+ | в циклических очередях и повторяющихся процессах | |
2) | в стековых вычислениях | |
3) | в индексных таблицах | |
ⓘ Кольцевые списки идеально подходят для циклических очередей и повторяющихся процессов, где нужно бесконечно перебирать элементы | ||
12. Что содержит каждый узел двусвязного списка? | ||
1)+ | данные, указатель на следующий, указатель на предыдущий | |
2) | только данные | |
3) | только один указатель | |
ⓘ Двусвязный узел содержит данные и два указателя: на следующий и предыдущий элементы, что позволяет двустороннюю навигацию | ||
13. Где находится конец у кольцевого списка? | ||
1)+ | его нет, последний элемент указывает на первый | |
2) | последний элемент указывает на | |
3) | зависит от реализации | |
ⓘ У кольцевого списка нет конца: последний узел ссылается на первый, создавая замкнутую структуру | ||
14. Что происходит при вставке нового элемента в начало односвязного списка? | ||
1)+ | новый элемент указывает на старый первый | |
2) | новый элемент указывает на | |
3) | все элементы сдвигаются | |
ⓘ Новый элемент указывает на старый первый узел, сохраняя последовательность и корректную работу списка | ||
15. В чём недостаток односвязного списка по сравнению с двусвязным? | ||
1)+ | невозможно эффективно перемещаться назад | |
2) | занимает больше памяти | |
3) | сложнее реализовать вставку в начало | |
ⓘ Односвязный список нельзя эффективно перемещаться назад, что ограничивает функциональность по сравнению с двусвязным | ||
16. Какова сложность поиска элемента в односвязном списке? | ||
1)+ | O(n) | |
2) | O(1) | |
3) | O(log n) | |
ⓘ Поиск в односвязном списке требует пройти элементы по порядку, что даёт сложность O(n) | ||
17. Что произойдёт, если в кольцевом списке потерять указатель на голову? | ||
1)+ | доступ ко всему списку становится невозможным | |
2) | список сам восстановится | |
3) | создастся новый список | |
ⓘ Если потерять указатель на голову, доступ ко всем элементам станет невозможен, так как нет точки входа в циклическую структуру | ||
18. Какой список позволяет эффективно вставлять элементы в середину при наличии указателя? | ||
1)+ | двусвязный | |
2) | массив | |
3) | стек | |
ⓘ Двусвязный список позволяет вставлять элементы в середину за O(1), используя указатели на соседние узлы | ||
19. Зачем в кольцевых списках используется sentinel-узел? | ||
1)+ | для упрощения обработки граничных случаев | |
2) | для хранения дополнительной информации | |
3) | для ускорения поиска по индексу | |
ⓘ Sentinel-узел упрощает обработку граничных случаев, таких как вставка или удаление первого и последнего узла, без дополнительных проверок | ||
1. В чём отличительная особенность динамических объектов? | ||
1) | порождаются непосредственно перед выполнением программы | |
2)+ | возникают уже в процессе выполнения программы | |
3) | задаются в процессе выполнения программы | |
ⓘ Динамические объекты создаются во время выполнения программы, а не на этапе компиляции, что позволяет гибко управлять памятью | ||
2. Что делает операция выделения динамической памяти? | ||
1)+ | резервирует область памяти под объект | |
2) | освобождает память | |
3) | создаёт новый процесс | |
ⓘ Операция резервирует область памяти под объект, чтобы программа могла использовать её для хранения данных | ||
3. Что происходит при утечке памяти? | ||
1)+ | память остаётся занята и недоступна | |
2) | операционная система автоматически удаляет утечки | |
3) | данные обнуляются | |
ⓘ Если программа не освобождает память, она остаётся занятой и недоступной, что может привести к исчерпанию ресурсов | ||
4. Как называется область памяти, используемая для динамического размещения? | ||
1)+ | куча (heap) | |
2) | стек (stack) | |
3) | регистры | |
ⓘ Куча (heap) используется для динамических объектов, выделяемых во время выполнения программы | ||
5. Что необходимо сделать после удаления узла списка? | ||
1) | ничего, память освободится сама | |
2)+ | вызвать | |
3) | пересоздать весь список | |
ⓘ После удаления узла нужно вызвать freenode или free, чтобы освободить память и предотвратить утечки | ||
6. Что возвращает операция getnode? | ||
1)+ | указатель на выделенный узел | |
2) | адрес стека | |
3) | значение информационного поля | |
ⓘ getnode выделяет память для нового узла и возвращает указатель на него, позволяя работать с новым объектом | ||
7. Почему динамические объекты гибкие? | ||
1)+ | их можно создавать и удалять по мере необходимости | |
2) | они занимают меньше памяти | |
3) | они всегда быстрее статических | |
ⓘ Их можно создавать и удалять по мере необходимости, что позволяет экономно использовать память и адаптироваться к размеру данных | ||
8. Что произойдёт при попытке доступа к освобождённому узлу? | ||
1) | корректное чтение данных | |
2)+ | неопределённое поведение | |
3) | автоматическое восстановление | |
ⓘ Доступ к освобождённой памяти приводит к неопределённому поведению и возможной ошибке выполнения | ||
9. Как называется ошибка, когда программа забывает освободить память? | ||
1)+ | утечка памяти | |
2) | переполнение буфера | |
3) | сегментация | |
ⓘ Утечка памяти возникает, когда программа не освобождает динамическую память, что снижает доступные ресурсы | ||
10. Какая операция безопаснее? | ||
1)+ | инициализация указателя значением | |
2) | оставлять указатель как есть | |
3) | удалять указатель без очистки | |
ⓘ После вызова free указатель нужно обнулить, чтобы предотвратить случайный доступ к освобождённой памяти | ||
11. Как называется ошибка, когда программа использует память после free? | ||
1)+ | use-after-free | |
2) | overflow | |
3) | double-free | |
ⓘ Use-after-free возникает при попытке работы с уже освобождённой памятью, что ведёт к неопределённому поведению | ||
12. Что делает realloc? | ||
1)+ | изменяет размер ранее выделенного блока памяти | |
2) | освобождает память | |
3) | удаляет указатель | |
ⓘ realloc изменяет размер ранее выделенного блока памяти, позволяя увеличить или уменьшить участок без потери данных | ||
13. Что гарантирует исключение double-free? | ||
1)+ | обнуление указателя после free | |
2) | повторный вызов free | |
3) | использование стека | |
ⓘ Обнуление указателя после free предотвращает повторное освобождение одной и той же области памяти | ||
14. Какой риск возникает при использовании необнулённого указателя? | ||
1)+ | доступ к мусорному адресу | |
2) | автоматическое выделение памяти | |
3) | потеря всех данных | |
ⓘ Необнулённый указатель может ссылаться на мусорный адрес, что приводит к ошибкам и непредсказуемому поведению программы | ||
15. Что такое сегментационная ошибка (segmentation fault)? | ||
1)+ | доступ к памяти вне допустимого адресного пространства | |
2) | ошибка нехватки памяти | |
3) | слишком большой массив | |
ⓘ Сегментационная ошибка возникает при доступе к памяти за пределами допустимого адресного пространства, что нарушает целостность программы | ||
generated at geetest.ru