Рубрики

Часто задаваемые вопросы о структуре данных | Комплект 1

Что такое структура данных?
Структура данных — это способ организации данных, позволяющий эффективно использовать данные. Различные типы структур данных подходят для различных типов приложений, а некоторые являются высокоспециализированными для конкретных задач. Например, B-деревья особенно хорошо подходят для реализации баз данных, в то время как реализации компилятора обычно используют хеш-таблицы для поиска идентификаторов. (Источник: вики-страница )

Что такое линейные и нелинейные структуры данных?

  • Линейный: структура данных называется линейной, если ее элементы образуют последовательность или линейный список. Примеры: Массив. Связанный список, стеки и очереди
  • Нелинейный: структура данных называется нелинейной, если обход узлов является нелинейным по своей природе. Пример: График и Деревья.

Какие различные операции могут выполняться в разных структурах данных?

  • Вставка ? Добавьте новый элемент данных в заданную коллекцию элементов данных.
  • Удаление ? Удалить существующий элемент данных из заданной коллекции элементов данных.
  • Обход ? Получите доступ к каждому элементу данных ровно один раз, чтобы его можно было обработать.
  • Поиск ? Узнайте, где находится элемент данных, если он существует в данной коллекции элементов данных.
  • Сортировка ? Расположение элементов данных в некотором порядке, т.е. в порядке возрастания или убывания в случае числовых данных и в порядке словаря в случае буквенно-цифровых данных.

Чем массив отличается от связанного списка?

  • Размер массивов фиксированный, связанные списки имеют динамический размер.
  • Вставка и удаление нового элемента в массиве элементов стоит дорого, тогда как и вставка, и удаление могут быть легко выполнены в связанных списках.
  • Произвольный доступ запрещен в связанном списке.
  • Для каждого элемента связанного списка требуется дополнительное место в памяти для указателя.
  • Массивы имеют лучшую локальность кэша, что может существенно повлиять на производительность.

Что такое стек и где его можно использовать?

Стек — это линейная структура данных, которая для доступа к элементам имеет порядок LIFO (Last In First Out) или FILO (First In Last Out). Основные операции стека: Push, Pop, Peek

Применение стека:

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

Что такое очередь, чем она отличается от стека и как она реализована?

Очередь представляет собой линейная структура , которая соответствует порядку является Р рвого Н Ф О рвом ет (FIFO) к элементам доступа. В основном следующие являются основными операциями в очереди: постановка в очередь, удаление из очереди , фронт, тыл
Разница между стеками и очередями заключается в удалении. В стеке мы удаляем элемент, который был добавлен последним; в очереди удаляем элемент, наименее добавленный за последнее время. И очереди, и стеки могут быть реализованы с использованием массивов и связанных списков.

Что такое нотация Infix, префикс, Postfix?

  • Инфиксная запись: X + Y — операторы записываются между своими операндами. Это обычный способ написания выражений. Выражение, такое как
       A * ( B + C ) / D
  • Постфиксная запись (также известная как «обратная польская запись»): операторы XY + пишутся после своих операндов. Выражение инфикса, приведенное выше, эквивалентно
       A B C + * D/
  • Префиксная запись (также известная как «Польская запись»): + XY Операторы пишутся перед своими операндами. Выражения, приведенные выше, эквивалентны
       / * A + B C D

Преобразование между этими обозначениями: Нажмите здесь

Что такое связанный список и каковы его типы?

Связанный список — это линейная структура данных (например, массивы), где каждый элемент является отдельным объектом. Каждый элемент (то есть узел) списка состоит из двух элементов — данных и ссылки на следующий узел. Типы связанного списка:

  1. Одиночный связанный список: в этом типе связанного списка каждый узел хранит адрес или ссылку на следующий узел в списке, а последний узел имеет следующий адрес или ссылку как NULL. Например 1-> 2-> 3-> 4-> NULL
  2. Двусвязный список: здесь, Вот две ссылки, связанные с каждым узлом, одна из ссылок указывает на следующий узел, а другая на предыдущий узел. Например. NULL <-1 <-> 2 <-> 3-> NULL,
  3. Круговой Связанный список: Круговой связанный список связанного список , где все узлы соединены , чтобы сформировать круг. В конце нет NULL. Круговой связанный список может быть однократно круговым связанным списком или дважды круговым связанным списком. Например. 1-> 2-> 3-> 1 [Следующий указатель последнего узла указывает на первый]

Какие структуры данных используются для BFS и DFS графа?

Можно ли реализовать двусвязную связь, используя одну переменную-указатель в каждом узле?
Двусвязный список может быть реализован с помощью одного указателя. См. XOR Linked List — Двусвязный список с эффективным использованием памяти

Как реализовать стек с использованием очереди?

Стек может быть реализован с использованием двух очередей. Пусть для реализации стека будут 's', а для реализации используются очереди 'q1' и 'q2'. Стек 's' может быть реализован двумя способами:

Как реализовать очередь, используя стек?

Очередь может быть реализована с использованием двух стеков. Пусть реализуемая очередь будет q, а стеки, используемые для реализации q, будут stack1 и stack2. q может быть реализовано двумя способами:

Какая структура данных должна использоваться для реализации LRU-кэша?

Мы используем две структуры данных для реализации LRU-кэша.

  1. Очередь, которая реализована с использованием двусвязного списка. Максимальный размер очереди будет равен общему количеству доступных кадров (размер кэша). Последние использованные страницы будут располагаться ближе к задней части, а наименьшее количество последних страниц — ближе к передней
  2. Хеш с номером страницы в качестве ключа и адресом соответствующего узла очереди в качестве значения. См. Как реализовать схему кэширования LRU? Какие структуры данных следует использовать?

Как проверить, является ли данное двоичное дерево BST или нет?
Если обход по порядку двоичного дерева отсортирован, то двоичное дерево имеет тип BST. Идея состоит в том, чтобы просто выполнить обход по порядку и при обходе отслеживать предыдущее значение ключа. Если текущее значение ключа больше, продолжайте, иначе верните false. См . Программу, чтобы проверить, является ли двоичное дерево BST или нет, для получения более подробной информации.

Вопросы по связанному списку

Вопросы о обходе дерева

Конвертировать DLL в двоичное дерево на месте
См. Преобразование на месте отсортированной DLL в сбалансированный BST

Конвертировать двоичное дерево в DLL на месте
См. Преобразование данного двоичного дерева в двусвязный список | Установите 1 , конвертировать данное бинарное дерево в двусвязный список | Набор 2

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

Перевернуть связанный список
Напишите функцию для обратного связанного списка

Определить цикл в связанном списке
Напишите функцию C для обнаружения цикла в связанном списке .

Какая структура данных используется для словаря и проверки орфографии?
Структура данных для словаря и проверки орфографии?

Вам также может понравиться

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Часто задаваемые вопросы о структуре данных | Комплект 1

0.00 (0%) 0 votes