Preguntas frecuentes sobre la entrevista sobre estructura de datos

Preguntas de la entrevista sobre estructura de datos

La estructura de datos es la forma en que las computadoras almacenan y organizan los datos. Una estructura de datos se refiere a una colección de elementos de datos que tienen una o más relaciones específicas entre sí. A continuación se muestran las preguntas de entrevistas sobre estructura de datos comunes que compilé.

Preguntas frecuentes de la entrevista sobre estructura de datos, parte 1

El contenido de la estructura de datos y el algoritmo es realmente enorme y no es fácil cubrirlos todos. Es posible que necesitemos aprender cada estructura y algoritmo durante el período de estudio escolar, pero cuando buscamos trabajo en una prueba escrita o en una entrevista, debemos examinar la capacidad de una persona en esta área en un corto período de tiempo y hacer preguntas sobre cada estructura. y algoritmo. No muy realista. Por lo tanto, la situación real es que las empresas generalmente examinan algunos conceptos y algoritmos aparentemente básicos, o algunas modificaciones, y luego le permiten implementarlos. Puede parecer simple, pero si le piden que complete rápidamente un algoritmo en papel o en una computadora, diseñe un caso de prueba y finalmente lo ejecute, encontrará que es muy difícil. Esto requiere que estemos familiarizados y dominemos firmemente los algoritmos de uso común, especialmente aquellos algoritmos aparentemente simples. Son estos algoritmos de uso común los que requieren que tengamos una comprensión sólida y mejoremos la eficiencia del trabajo. Cuando se encuentre con algoritmos complejos, mediante análisis y sólidas habilidades básicas, debería poder desarrollarlos rápidamente.

Sin más, vayamos al grano.

1. Parte de la estructura de datos.

1. La diferencia entre matrices y listas enlazadas. (Prueba muy simple, pero muy común, recuerde responder de manera integral)

En lenguaje C, las matrices se pueden usar para procesar un conjunto de datos del mismo tipo de datos, pero el tamaño de la matriz no está permitido. para definirse dinámicamente, es decir, antes de usar la matriz, se debe determinar el tamaño de la matriz. En aplicaciones reales, los usuarios a veces no pueden determinar con precisión el tamaño de la matriz antes de usarla. Solo pueden definir la matriz a un tamaño suficiente. De esta manera, es posible que no se use parte del espacio en la matriz, lo que resulta en una pérdida de espacio de memoria. . La lista vinculada es una forma de organización de datos común, que se implementa mediante la asignación dinámica de memoria. Puede utilizar nuevo para asignar espacio de memoria cuando sea necesario y liberar el espacio asignado cuando no sea necesario, lo que no provocará una pérdida de espacio de memoria.

Desde la perspectiva de la estructura lógica: la matriz debe tener una longitud fija (número de elementos) definida de antemano y no puede adaptarse al aumento o disminución dinámica de datos, es decir, el tamaño de la matriz no puede modificarse una vez definido. Cuando los datos aumentan, puede exceder la cantidad de elementos definidos originalmente; cuando los datos disminuyen, la memoria se desperdicia y asigna almacenamiento dinámicamente, lo que puede adaptarse al aumento y disminución dinámica de los datos y puede insertar y eliminar datos fácilmente; elementos. . (Al insertar o eliminar elementos de datos en la matriz, es necesario mover otros elementos de datos).

Desde la perspectiva del almacenamiento de memoria: las matrices (estáticas) asignan espacio de la pila (creada con NUEVO en el montón), lo cual es conveniente y rápido para los programadores, pero el grado de libertad de las listas vinculadas es pequeño; Asigne espacio desde el montón. El grado de libertad es grande, pero la administración de aplicaciones es problemática.

1 Desde la perspectiva del método de acceso: las matrices se almacenan continuamente en la memoria, por lo que los índices de subíndices se pueden usar de forma aleatoria. acceso; las listas vinculadas son estructuras de almacenamiento vinculadas. Al acceder a elementos, solo se puede acceder a ellos secuencialmente de adelante hacia atrás de manera lineal, por lo que la eficiencia de acceso es menor que la de las matrices.

2. Algunas operaciones en listas enlazadas, como inversión de listas enlazadas, determinación de bucles en listas enlazadas (punteros rápidos y lentos), listas doblemente enlazadas y operaciones relacionadas con listas enlazadas circulares.

3. Cola (especial como cola prioritaria), aplicación de pila. (Por ejemplo, las colas se usan en colas de mensajes y las pilas se usan en llamadas recursivas)

4. Operaciones básicas de árboles binarios

Tres métodos transversales de árboles binarios (preorden, inorden). , postorder ) y sus implementaciones recursivas y no recursivas, las principales aplicaciones de los tres métodos transversales (como expresiones de sufijo, etc.). La complejidad temporal de las operaciones relevantes.

5. Relacionado con cadenas

Conversión entre enteros, números de punto flotante y cadenas (atoi, atof, itoa)

Preste atención a la verificación de excepciones al copiar cadenas. como puntero nulo, superposición de cadenas, autoasignación, terminador de cadena '/0', etc.

2. Parte del algoritmo

1. Algoritmo de clasificación:

La clasificación puede considerarse como el algoritmo más básico y más utilizado, y también es el más comúnmente probado en entrevistas escritas al algoritmo. La clasificación por burbujas, la clasificación por selección y la clasificación por inserción más básicas deben implementarse rápidamente con código. Estos prueban principalmente su capacidad de codificación real. Clasificación en montón, clasificación por fusión y clasificación rápida: estos algoritmos requieren estar familiarizados con las ideas principales y los detalles que necesitan atención. Requiere estar familiarizado con la complejidad temporal y espacial de los algoritmos de clasificación utilizados habitualmente.

Resumen del alcance de uso de varios algoritmos de clasificación:

(1) Cuando el tamaño de los datos es pequeño, se pueden utilizar algoritmos de clasificación simples, como la clasificación por inserción directa o la clasificación por selección directa. .

(2) Cuando el estado inicial del archivo está básicamente en orden, se puede utilizar la clasificación por inserción directa o la clasificación por burbujas.

(3) Cuando el tamaño de los datos es relativamente grande, utilice un algoritmo de clasificación rápido. Considere utilizar la clasificación rápida. Cuando los registros se distribuyen aleatoriamente, el tiempo promedio de clasificación rápida es el más corto, pero puede ocurrir el peor de los casos. La complejidad del tiempo en este momento es O (n ^ 2), la profundidad de recursión es n y el espacio de pila requerido es. En).

(4) La clasificación en montón no provocará el peor de los casos, como la clasificación rápida, y la clasificación en montón requiere menos espacio auxiliar que la clasificación rápida. Sin embargo, ambos algoritmos no son estables. Si se requiere que la clasificación sea estable, se puede considerar la clasificación por combinación.

(5) La clasificación por combinación se puede utilizar para clasificación interna o externa. Cuando se realiza una clasificación externa, generalmente se usa la combinación de rutas múltiples, y se utilizan medidas como resolver la combinación de cadenas secuenciales largas para generar cadenas iniciales largas y mejorar las capacidades paralelas del host y los periféricos para reducir la cantidad de accesos a la memoria externa. y mejorar la eficiencia de la clasificación externa.

2. Algoritmo de búsqueda

Ser capaz de escribir o codificar hábilmente un programa de búsqueda binaria en una computadora.

3. Algoritmo hash

4. Algunas ideas de diseño de algoritmos.

Algoritmo codicioso, algoritmo de divide y vencerás, algoritmo de programación dinámica, algoritmo de aleatorización, algoritmo de retroceso, etc. Estos se pueden revisar basándose en programas de ejemplo específicos.

5. STL

STL (Biblioteca de plantillas estándar) es una estructura de datos y una biblioteca de algoritmos implementada utilizando tecnología de plantillas en el campo C. Se ha incluido en la biblioteca estándar de C. Vecor, lista, pila, cola y otras estructuras no solo tienen funciones más potentes, sino que también tienen mayor seguridad. Además de las estructuras de datos, STL también contiene iteradores generalizados y varios algoritmos prácticos que se ejecutan en iteradores. Estos son muy tentadores para aplicaciones que no tienen requisitos de alto rendimiento pero no quieren implementar el algoritmo desde abajo. Preguntas frecuentes de la entrevista sobre estructura de datos, parte 2

1. ¿Qué es una estructura de datos?

La estructura de datos es la forma en que se organizan (almacenan) y manipulan los datos para su recuperación y acceso. También define cómo los diferentes conjuntos de datos se relacionan entre sí, estableciendo relaciones y formando algoritmos.

2. Describe el tipo de estructura de datos.

Lista: colección de cosas relacionadas que están vinculadas a elementos de datos anteriores y/o posteriores.

Matriz: Colección de todos los valores idénticos.

Registros: una colección de campos, cada campo contiene datos de un único tipo de datos.

Árbol: Estructura de datos que organiza los datos en un marco jerárquico. Esta forma de estructura de datos sigue el orden en que se insertan, eliminan y modifican los elementos de datos.

Tabla: Los datos se guardan en forma de filas y columnas. Estos son comparables a los registros en que los resultados o cambios en los datos se reflejan en toda la tabla.

3. ¿Qué es una estructura de datos lineal? Por favor dé un ejemplo

Una estructura de datos es lineal si todos sus elementos o elementos de datos están organizados en orden secuencial o lineal. Los elementos se almacenan de forma no jerárquica, por lo que cada elemento tiene un sucesor y un predecesor, excepto el primer y el último elemento de la lista. Las matrices, pilas, cadenas, colas y listas enlazadas son todas estructuras de datos lineales.

4. ¿Cuáles son las aplicaciones de las estructuras de datos?

Análisis numérico, sistemas operativos, inteligencia artificial, diseño de compiladores, gestión de bases de datos, gráficos, análisis estadístico y simulación.

5. ¿Cuál es la diferencia entre estructura de archivos y estructura de almacenamiento?

La diferencia radica en el área de memoria a la que se accede. Las estructuras de almacenamiento se refieren a estructuras de datos en la memoria del sistema informático, mientras que las estructuras de archivos se refieren a estructuras de almacenamiento en la memoria auxiliar.

6. ¿Qué es una matriz multidimensional?

Matriz multidimensional significa una matriz con tres dimensiones o más. Las matrices tridimensionales tienen los conceptos de alto, ancho y profundidad, o los conceptos de filas, columnas y capas, es decir, las matrices anidadas en matrices alcanzan tres dimensiones y más. Es la matriz multidimensional más común y se usa ampliamente porque puede usarse para describir la posición o el estado en un espacio tridimensional.

7. ¿Qué es una estructura de datos de lista enlazada?

Esta es una de las preguntas de entrevista sobre estructura de datos más comunes y el entrevistador espera que pueda dar una respuesta completa. ¡Intenta explicar tanto como sea posible en lugar de completar tu respuesta en una oración!

Es una estructura de datos lineal o una secuencia de objetos de datos en los que los elementos no se almacenan en ubicaciones de memoria adyacentes. Los elementos se vinculan mediante punteros para formar una cadena. Cada elemento es un objeto separado llamado nodo. Cada nodo tiene dos elementos: un campo de datos y una referencia al siguiente nodo. El punto de entrada en la lista enlazada se llama encabezado. Si la lista está vacía, el encabezado tiene una referencia nula y el último nodo tiene una referencia nula.

Una lista enlazada es una estructura de datos dinámica en la que el número de nodos no es fijo. Este ejemplo tiene la capacidad de expandirse y contraerse según sea necesario.

Es adecuado para las siguientes situaciones:

Estamos tratando con un número desconocido de objetos o no sabemos cuántos elementos hay en la lista;

Necesitamos hacer un tiempo constante desde la inserción/eliminación de la lista, como en la computación en tiempo real donde la previsibilidad temporal es crucial

No se requiere acceso aleatorio a ningún elemento

El algoritmo; requiere una estructura de datos, independientemente de la dirección física del objeto en la memoria, necesitamos almacenar el objeto allí

Necesitamos insertar elementos en el medio de la lista, al igual que en la prioridad; cola;

Algunas implementaciones son pilas y colas, gráficos, directorios de nombres, asignación de memoria dinámica y realización de operaciones aritméticas con números enteros largos

8. ¿Qué es una lista doblemente enlazada? Por favor, dé un ejemplo.

Es un tipo complejo de lista enlazada (LL de dos extremos), en la que un nodo tiene dos enlaces, uno al siguiente nodo de la secuencia y el otro al nodo anterior. Esto permite atravesar elementos de datos en ambas direcciones.

Ejemplos:

Lista de reproducción de música con botones de navegación siguiente y anterior

Caché del navegador de las páginas visitadas con ATRÁS

Función Deshacer activada navegador

9. ¿Por qué necesitamos el análisis de algoritmos?

Un problema se puede resolver de muchas maneras utilizando múltiples algoritmos de resolución. El análisis algorítmico proporciona una estimación de los recursos requeridos por un algoritmo para resolver un problema computacional específico. También se determina la cantidad de recursos de tiempo y espacio necesarios para la ejecución.

La complejidad temporal de un algoritmo mide el tiempo que lleva ejecutar el algoritmo en función de la longitud de entrada. La complejidad del espacio mide la cantidad de espacio o memoria que ocupa un algoritmo para ejecutarse en función de la longitud de entrada. ;