Preguntas de la entrevista sobre estructura de datos compiladas por estudiantes

Preguntas reales de la entrevista Preguntas y respuestas de la entrevista sobre la estructura de datos

1. ¿Qué es una estructura de datos?

Una estructura de datos es la forma en que una computadora almacena y organiza 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í. La estructura incluye estructura lógica y estructura física.

La estructura lógica de los datos incluye 4 tipos

(1) Conjunto: no existe otra relación entre los elementos de datos excepto que tienen el mismo tipo de datos

(2) Estructura lineal: existe una relación uno a uno entre los elementos de datos: lista lineal, pila, cola

(3) Estructura de árbol: existe una relación de uno a muchos entre los elementos de datos

(4) Estructura del gráfico: existe una relación de muchos a muchos entre los elementos de datos.

La estructura física incluye una estructura de almacenamiento secuencial y una estructura de almacenamiento en cadena.

2. Explique el almacenamiento secuencial y el almacenamiento en cadena.

La estructura de almacenamiento secuencial utiliza un espacio de almacenamiento continuo para almacenar elementos de datos, a los que se puede acceder aleatoriamente y tiene una alta eficiencia de acceso. La estructura de almacenamiento encadenado utiliza espacio de almacenamiento arbitrario para almacenar elementos de datos, a los que no se puede acceder aleatoriamente y tiene una baja eficiencia de acceso.

3. ¿Cuál es la diferencia entre el puntero principal y el nodo principal?

Puntero principal: es un puntero a la ubicación de almacenamiento del primer nodo. Tiene una función de identificación. El puntero principal es un elemento necesario de la lista vinculada. Independientemente de si la lista vinculada está vacía, el puntero principal existe.

Nodo principal: se coloca antes del nodo del primer elemento para facilitar las operaciones de inserción y eliminación antes del nodo del primer elemento. El nodo principal no es un elemento necesario de la lista vinculada y es opcional. el nodo principal no necesita almacenar ninguna información.

IV.Características de la estructura lineal

(1) Debe haber un "primer elemento" único en el conjunto.

(2) Debe haber un; "primer elemento" único en el conjunto Sólo hay un "último elemento"

(3) Excepto el último elemento, otros elementos de datos tienen un "sucesor" único

; (4) Excepto el primero Además del elemento, otros elementos de datos tienen un "predecesor" único.

5. ¿Cuál es la diferencia entre una matriz y una lista enlazada?

Desde la perspectiva de la estructura lógica: la longitud de almacenamiento de una matriz es fija y no puede adaptarse a la aumento o disminución dinámica de datos. Las listas vinculadas pueden asignar dinámicamente espacio de almacenamiento para adaptarse al aumento y disminución dinámica de datos, y son fáciles de realizar operaciones de inserción y eliminación.

Desde la perspectiva del método de acceso: la matriz es un espacio de almacenamiento continuo en la memoria. Se puede acceder a la matriz aleatoriamente a través del subíndice de la matriz y la eficiencia del acceso es alta. Una lista vinculada es una estructura de almacenamiento vinculada. El espacio de almacenamiento no tiene por qué ser continuo y puede ser arbitrario. El acceso debe realizarse de adelante hacia atrás y la eficiencia del acceso es menor que la de una matriz.

Si se insertan varios elementos desde la posición i-ésima, para la matriz, cada inserción requiere mover los elementos hacia atrás y la complejidad temporal de cada vez es O (n), mientras que para una lista enlazada individualmente La complejidad temporal de encontrar solo la posición de i por primera vez es O (n), y la complejidad temporal del resto de las operaciones de inserción y eliminación es O (1), lo que mejora la eficiencia de la inserción y eliminación.

6. ¿Cuál es la diferencia entre una estructura de lista enlazada individualmente y una estructura de almacenamiento secuencial?

Al insertar y eliminar operaciones, la estructura de almacenamiento secuencial necesita mover elementos cada vez, y la complejidad temporal total es O (n ^ 2), y después de que la estructura de almacenamiento en cadena determina el puntero de la posición i, su complejidad temporal es solo O (1). Dado que la estructura de almacenamiento secuencial requiere espacio de almacenamiento preasignado, es fácil provocar desperdicio o desbordamiento de espacio. La estructura de almacenamiento en cadena no requiere asignación previa de espacio de almacenamiento y la cantidad de elementos no está limitada.

7. La diferencia entre pila y cola

Una cola es una lista lineal que permite la inserción en un extremo y la eliminación en el otro. Los elementos que ingresan a la cola se procesan de acuerdo con el. Regla "primero en entrar, primero en salir", eliminar en el encabezado de la tabla e insertar al final de la tabla.

La pila es una lista lineal que solo puede realizar operaciones de inserción y eliminación al final de la tabla. Adjuntas a los datos del elemento reproducidos en la pila, las operaciones de procesamiento, inserción y eliminación de reglas de "último en entrar, primero en salir" se realizan en la parte superior de la pila.

Dado que empujar y hacer estallar se realizan en la parte superior de la pila, hay una variable de tamaño

para registrar el tamaño de la pila actual. Al empujar hacia la pila, el tamaño no puede exceder. la longitud de la matriz.

tamaño+1, la pila no está vacía cuando se abre, tamaño-1.

8. Introduzca el algoritmo de coincidencia de cadenas:

Algoritmo de coincidencia simple y algoritmo KMP

1. Algoritmo BF (BruteForce)

·. Cadena de destino t (cadena que debe coincidir)

·Cadena de patrón p (la cadena corta)

①Compare el primer carácter de t con el primer carácter de S, si son iguales Continuar a t-2VSp-2, si es igual, ¿continuar a t-3VSp?

②Si no es igual, continuar a t-1VSp-2, t-2VSp-3

2.KMP algoritmo: rápido desde Encuentre la subcadena de la cadena principal

①Haga coincidir los prefijos de subcadena superior e inferior

②Encuentre el *** público y los sufijos (tome el más largo y el menor que la longitud de se comparan las cadenas superior e inferior)

(3 Mueva el siguiente prefijo de subcadena p a la posición del sufijo

El algoritmo de fuerza bruta compara varios caracteres en la cadena del patrón con varios caracteres consecutivos en la cadena principal, pero al final Cuando una comparación de caracteres no es igual, la posición de comparación de la cadena principal debe revertirse. En el caso anterior, el algoritmo KMP no necesita revertir la posición de la cadena principal, lo que puede ser en gran medida. mejorar la eficiencia

9. Búsqueda en profundidad y ¿Cómo se implementa la búsqueda en amplitud?

Búsqueda en profundidad: (1) Visite el punto de partida v0

(2) Si no se ha visitado el primer punto adyacente de v0, recorra el punto adyacente en profundidad;

(3) Si se ha visitado el primer punto adyacente de v0, visite su segundo punto adyacente y realice un recorrido profundo; repita los pasos anteriores hasta que se hayan visitado todos los nodos. Hasta que se visite

Búsqueda en amplitud: (1) Visite el punto de partida v0

(2). ) Recorra todos los puntos adyacentes no visitados de v0 en secuencia

( 3) Luego visite los puntos adyacentes no visitados en la siguiente capa por turno, repita los pasos anteriores hasta que se hayan visitado todos los vértices

10. ¿Cómo construir un árbol de Huffman?

Encuentre la suma más pequeña de w, y luego encuentre la w más pequeña, la izquierda es pequeña y la derecha es grande después de la construcción, izquierda 0 y derecha 1 <; /p>

11. Árbol de expansión mínimo

Árbol de expansión mínimo Es encontrar el borde más pequeño que pueda conectar todos los nodos, y el camino más corto es el camino más corto desde un determinado nodo a otros nodos.

El árbol bruto mínimo:

En un gráfico no dirigido dado G = (V, E), (u, v) representa el borde que conecta el vértice u y el vértice v (es decir), y w (u, v) representa el peso de este borde, si hay un subconjunto de E (es decir) y un gráfico acíclico tal que w (T) es el más pequeño, entonces este T es el árbol de expansión mínimo de G.

w(t). =w(u,u)

El árbol de expansión mínimo es en realidad el mínimo (u, u)et

La idea básica de ​​El algoritmo Prim es: establecer los vértices en otros puntos. Para el borde con el peso más pequeño, agregue un nuevo conjunto de vértices y luego encuentre el borde... hasta atravesar todos los puntos

A partir de un determinado vértice u0 en la red Unicom N = {V, E}, seleccione el peso más pequeño asociado con su borde de valor, agregue su vértice al conjunto de vértices S, luego seleccione el borde con el peso más pequeño de todos los vértices con un vértice en el establezca S y el otro vértice que no esté en el conjunto S, y agregue el vértice correspondiente al conjunto S hasta Hasta que todos los vértices se agreguen al conjunto S.

La idea básica del algoritmo de Kruskal es: seleccionar los bordes más pequeños para que no tenga bucles y finalizar el recorrido de todos los puntos

Supongamos que hay una red conectada con n vértices N = {V, E], en la prueba inicial, se establece un gráfico T no conectado con solo n vértices y sin aristas. Cada vértice en T se considera como una rama conectada, y la arista con el peso más pequeño es. seleccionado del conjunto de bordes E. Si los dos puntos finales del borde no están en una rama conectada, agregue el borde a T; de lo contrario, seleccione un borde con el peso más pequeño hasta que todos los vértices estén en una rama conectada.

12. Algoritmo de ruta más corta

La complejidad temporal de Dijkstra es O(n~2)

La complejidad temporal de Fly od es O(n^3) La complejidad espacial es O(n^2);

Ruta más corta: se utiliza para calcular la ruta más corta desde un nodo a todos los demás nodos. La característica principal es que se expande capa por capa desde el punto inicial hasta llegar al punto final.

Algoritmo Dij Astra

El clásico algoritmo de ruta más corta de fuente única se basa principalmente en la idea de programación dinámica que adopta.

Algoritmo de Floyd

El método clásico de encontrar el camino más corto entre cualquier vértice, utilizando el pensamiento codicioso.

13. ¿Introducir la clasificación topológica y cómo implementarla?

Pasos de la clasificación topológica:

(1) Seleccione cualquiera en la salida del nodo del gráfico dirigido sin predecesor

(2) Eliminar el nodo y los bordes conectados a él del gráfico

(3) Repita los pasos anteriores hasta que se generen todos los vértices o el actual Hasta que no haya ningún predecesor -Sin vértices en el gráfico, esto último significa que el gráfico es un gráfico cíclico, por lo que se puede utilizar la clasificación topológica para determinar si un gráfico tiene un ciclo.

14. Describa brevemente varios métodos de búsqueda

La búsqueda se divide en tabla de búsqueda estática y tabla de búsqueda dinámica

La tabla de búsqueda estática incluye: búsqueda secuencial y búsqueda media. búsqueda de bloques;

La búsqueda dinámica incluye: árbol de clasificación binaria y árbol binario equilibrado.

(1) Búsqueda secuencial: coloque la clave de palabra clave que se buscará en la posición centinela (i = 0) y luego compare los elementos de la tabla con la clave de atrás hacia adelante si es el valor de retorno. es 0, la búsqueda falla, no existe tal valor clave en la tabla. Si el valor de retorno es la posición i (il = 0) del elemento, la búsqueda es exitosa. La posición del centinela se establece para acelerar la ejecución. La complejidad temporal es O (n). Sus características son: Estructura simple, adecuada tanto para estructuras secuenciales como para estructuras encadenadas, pero la eficiencia de búsqueda es demasiado baja

(2) Media búsqueda: se requiere la tabla de búsqueda. ser una estructura de almacenamiento secuencial y ordenada, y si la palabra clave está en la tabla, se devolverá. La posición de la palabra clave Una señal típica para detener la búsqueda cuando la palabra clave no está en la tabla es: el límite superior de la búsqueda. rango <= el límite inferior del rango de búsqueda

(3) Búsqueda en bloque: primero divida la tabla de búsqueda en Para varias subtablas, se requiere que los elementos de cada subtabla sean más pequeños que el elementos de las siguientes subtablas, es decir, para garantizar que los bloques estén en orden (pero no necesariamente en orden dentro de las subtablas), y la palabra clave más grande en cada subtabla es Se forma una tabla de índice, que también contiene la dirección inicial de cada subtabla. Las características son: orden entre bloques, desorden dentro de bloques, búsqueda indexada entre bloques durante el tiempo de búsqueda y búsqueda secuencial dentro de bloques.

(4) Árbol de clasificación binaria: la definición de árbol de clasificación binaria es: un árbol vacío o un árbol con las siguientes características: si el árbol tiene un subárbol izquierdo, entonces su subárbol izquierdo Todos los valores de los nodos del árbol son menores que el valor de la raíz; si el árbol tiene un subárbol derecho, entonces todos los valores de los nodos del subárbol derecho son mayores que el valor de la raíz de sus subárboles izquierdo y derecho también están ordenados en binario; árboles

(5) Árbol binario equilibrado: un árbol binario equilibrado también se denomina árbol AVL. Es un árbol vacío o tiene las siguientes características: el valor absoluto de la diferencia de altura entre su subárbol izquierdo y. su subárbol derecho no puede ser mayor que 1, y sus subárboles izquierdo y derecho también son árboles binarios equilibrados.

Si insertar un nodo en un árbol binario equilibrado puede causar un desequilibrio, entonces se debe ajustar la estructura del árbol, es decir, rotación equilibrada. Incluyendo 4 situaciones: rotación unidireccional hacia la derecha al insertar un nodo en el subárbol izquierdo del subárbol izquierdo; rotación unidireccional hacia la izquierda al insertar un nodo en el subárbol derecho del subárbol derecho; izquierda al insertar un nodo en el subárbol derecho del subárbol izquierdo Al insertar un nodo en el árbol, primero gire hacia la izquierda y luego hacia la derecha cuando inserte un nodo en el subárbol izquierdo del subárbol derecho; derecha y luego a la izquierda.

15. Breve descripción de varios algoritmos de clasificación (1)

La clasificación interna incluye: clasificación por inserción, clasificación por selección, clasificación por intercambio, clasificación por fusión y clasificación por base.

La clasificación por inserción incluye: clasificación por inserción directa, clasificación por media inserción, clasificación Hill;

La clasificación por selección incluye: clasificación por selección simple, clasificación por intercambio en montón incluye: clasificación por burbujas, clasificación rápida.

(1) Clasificación por inserción directa (estable): la idea básica es: dividir la secuencia en una parte ordenada y una parte desordenada, seleccionar elementos de la parte desordenada y compararlos con la parte ordenada para encontrar la posición apropiada. Mueva el elemento original hacia atrás e inserte el elemento en la posición correspondiente.

La complejidad del tiempo es: O (n ~ 2), la complejidad del espacio es O (1)

(2) Clasificación de inserción media (estable): la idea básica es: establecer tres variables bajo alto medio, dejemos que

mid=(low+high) /2, si es una tecla [mid] >, entonces establezca high=mid-1; de lo contrario, configure low=mid+1, deje de hacer el bucle hasta low>high, right Perform Realice el procesamiento anterior en cada elemento de la secuencia, encuentre una posición adecuada y mueva otros elementos hacia atrás para su inserción. El número de comparaciones es O (nlog2n), pero debido a que es necesario retroceder, la complejidad temporal es O (n ~ 2) y la complejidad espacial es O (1). La ventaja es que el número de comparaciones se reduce considerablemente.

(3) Clasificación Hill (inestable): la idea básica es: primero dividir la secuencia en varias subsecuencias, realizar una clasificación por inserción directa en cada subsecuencia y luego ordenar la secuencia completa cuando la secuencia esté básicamente en orden. Realizar una clasificación por inserción directa. La ventaja es que los elementos con valores clave pequeños se pueden mover rápidamente al frente, y cuando la secuencia está básicamente ordenada, la eficiencia del tiempo de la clasificación por inserción directa mejorará enormemente y la complejidad del espacio es O (1).

(4) Clasificación por selección simple (inestable): la idea básica es: dividir la secuencia en 2 partes, encontrar un valor mínimo en la parte desordenada después de cada pasada y luego combinarlo con el primer valor de los elementos de la parte desordenada intercambian posiciones. La ventaja es que es fácil de implementar, pero la desventaja es que solo se puede determinar la posición de un elemento en cada pasada y la eficiencia del tiempo es baja. La complejidad del tiempo es O (n ^ 2) y la complejidad del espacio es O (1).

(5) Clasificación de montón (inestable): dada una secuencia arbitraria, k1, k2, "

kn, se llama montón cuando se cumplen las siguientes características: deja que esta secuencia Organizado en un árbol binario completo. Este árbol tiene las siguientes características. Cualquier nodo en el árbol es más grande o más pequeño que sus hijos izquierdo y derecho. es el valor máximo o

p>

Valor mínimo. La ventaja es que la eficiencia mejora significativamente para archivos grandes, pero la eficiencia no es obvia para archivos pequeños

El. la complejidad del tiempo es O (nlog2n) y la complejidad del espacio es O (1).

16. Breve descripción de varios algoritmos de clasificación (1)

La clasificación interna incluye: clasificación por inserción. clasificación por selección, clasificación por intercambio, clasificación por fusión y clasificación por base.

La clasificación por inserción incluye: clasificación por inserción directa, clasificación por media inserción, clasificación Hill;

La clasificación por selección incluye: clasificación por selección simple, clasificación de montón; clasificación de intercambio incluye: clasificación de burbujas, clasificación rápida

(6) Clasificación de burbujas (estable): la idea básica es: comparar elementos en pares en cada pasada e intercambiarlos de acuerdo con la regla de " pequeño primero, grande último". La ventaja es: cada pasada. No solo puede encontrar el elemento más grande y colocarlo al final de la secuencia, sino que también puede enderezar otros elementos. Si no se produce ningún intercambio en la siguiente clasificación, la clasificación se puede finalizar antes. La complejidad del tiempo es O (n ~ 2) y la complejidad del espacio es O. (1) Clasificación rápida (inestable): la idea básica es: arbitrariamente. seleccione un elemento en la secuencia como centro, los elementos más grandes se moverán hacia atrás y los elementos más pequeños se moverán hacia atrás hacia adelante uniformemente para formar dos subsecuencias a la izquierda y a la derecha, y luego ajuste las subsecuencias de acuerdo con. Las operaciones anteriores hasta que todas las subsecuencias tengan solo un elemento. La ventaja es que no solo se puede determinar un elemento en cada pasada. La eficiencia del tiempo es alta. La complejidad del tiempo es O (nlog2n) y la complejidad del espacio es O (log2n).

(8) Ordenación por combinación (estable): la idea básica es: colocar dos o más. La complejidad temporal de fusionar las listas ordenadas en una nueva lista ordenada es O (n logn) y la complejidad espacial es igual que el número de elementos a ordenar.

(9) Clasificación por base: complejidad temporal El grado es: la complejidad temporal de la clasificación por base en cadena para n registros es O(d(n+rd). ), en el que la complejidad temporal de cada asignación es O (n) y la complejidad temporal del reciclaje es O (rd).

La ventaja de la regla "pequeño delante y grande detrás" es. que cada pasada no solo puede encontrar el elemento más grande y colocarlo al final de la secuencia, sino también enderezar otros elementos. Si no se produce ningún intercambio, la clasificación puede terminar antes. La complejidad del tiempo es O (n^2). la complejidad del espacio es O (1).