Cola de estructura de datos
Tarea
Capítulo 1
1. Escriba un algoritmo para determinar si hay un miembro en la matriz de punto flotante a[] con un valor mayor que 1000. Si es así, proporcione el subíndice del miembro con el subíndice más pequeño entre los miembros mayores que 1000. Señale las operaciones básicas y las operaciones clave del algoritmo, analice la complejidad temporal de su algoritmo y expréselo en notación Big O.
2. La secuencia de Fibonacci se define como: proporcione un algoritmo no recursivo para calcular el número de Fibonacci, señale las operaciones básicas en el algoritmo, analice la complejidad temporal de su algoritmo y expréselo en notación O grande.
Capítulo 2
1. Para la lista lineal (18, 8, 21, 7, 3), dibuje la lista enlazada circular bidireccional correspondiente con el nodo principal.
2. Escriba un algoritmo para insertar un nodo con un valor en una lista enlazada individualmente ordenada con un nodo de encabezado y mantenga la nueva lista enlazada en orden.
Capítulo 3
1. Escriba un algoritmo para invertir una cola. En el algoritmo, se puede usar la pila y se pueden llamar las operaciones básicas de la pila y la cola, pero no se permite que los elementos de la pila y la cola se procesen directamente.
2. Para colas circulares,
(1) Intente escribir un algoritmo para encontrar la longitud de la cola
(2) Intente escribir un algoritmo para determinar si la cola está vacía.
Capítulo 4
1. Suponiendo que la matriz tridimensional se almacena secuencialmente en el orden de las columnas principales, obtenga la fórmula de cálculo de dirección para ella.
2. Escriba un algoritmo para contar el número de apariciones de la subcadena S2 en la cadena S1.
Capítulo 5
1. Proporcione las secuencias de preorden, postorden y recorrido jerárquico del árbol que se muestra en la siguiente figura.
2. Se sabe que la secuencia de preorden y la secuencia de orden de un árbol binario son ABDECFGH y DBEAGFHC respectivamente. Dibuje el árbol binario y escriba su secuencia de postorden.
3. Dado un árbol binario almacenado como una lista binaria enlazada, la raíz apunta a su raíz. Escriba un algoritmo para encontrar la altura de un árbol binario.
4. Dado un árbol binario almacenado como una lista binaria enlazada, la raíz apunta a su raíz. Escriba un algoritmo para encontrar la cantidad de nodos con valor x en el árbol binario.
5. Se sabe que el árbol binario que se muestra en la figura siguiente se convierte a partir de un determinado bosque. Por favor, proporcione el bosque original.
6. Suponiendo que hay ocho caracteres, sus probabilidades de aparición son: 0,07, 0,09, 0,14, 0,19, 0,23, 0,44, 0,58 y 0,77.
(1) Indique el árbol de Huffman y la codificación de Huffman de estos 8 caracteres.
(2) ¿Cuál es el significado real del WPL del árbol de codificación?
Capítulo 6
1. Para el gráfico dirigido que se muestra a continuación, proporcione
(1) el grado de entrada y salida de cada vértice
(2) el componente fuertemente conectado y el componente débilmente conectado
p>(3) Matriz de adyacencia
(4) Lista de adyacencia y lista de adyacencia inversa
2. Suponiendo que un gráfico dirigido se almacena como una matriz de adyacencia, escriba un algoritmo que encuentre el grado de entrada y salida de un vértice específico.
3. Para el gráfico no dirigido que se muestra en la figura siguiente, dibuje los árboles generados por la búsqueda en profundidad y la búsqueda en amplitud, respectivamente.
4. Aplique el algoritmo de Floyd para encontrar el camino más corto al siguiente gráfico ponderado no dirigido, encuentre el camino más corto entre cada par de vértices y escriba cada matriz obtenida durante la ejecución del algoritmo.
5. Para el gráfico ponderado no dirigido que se muestra en la figura siguiente, encuentre el árbol de expansión mínimo según el algoritmo de Kruskal y dibuje los resultados intermedios obtenidos en cada paso.
Capítulo 7
1. Intente comparar las características, ventajas y desventajas del algoritmo de búsqueda secuencial y el algoritmo de búsqueda binaria.
2. Escriba un algoritmo de búsqueda binaria recursivo.
3. A partir de un árbol de búsqueda vacío, inserte los valores clave 71, 32, 103, 66, 135, 82, 57, 91 en secuencia, dibuje el árbol de búsqueda obtenido después de cada inserción y luego elimine 57, 82, 71 en secuencia. Dibuje el árbol de búsqueda obtenido después de cada eliminación y calcule la longitud promedio de búsqueda exitosa con igual probabilidad para el árbol de búsqueda final.
4． Escriba un algoritmo para determinar si un árbol binario T es un árbol de búsqueda, suponiendo que el árbol binario T está almacenado en forma estándar.
5. A partir de una tabla hash vacía, inserte las palabras clave enero, febrero, marzo, abril, mayo, junio, julio, agosto, septiembre, octubre, noviembre, diciembre en secuencia. La función hash es la primera letra del número de serie de la palabra clave. , por ejemplo, la longitud de la tabla hash es 17. Utilice
(1) método de detección lineal
(2) método de dirección en cadena
para crear una tabla hash respectivamente. Dibuje las tablas hash respectivamente y encuentre la longitud promedio de búsqueda exitosa con la misma probabilidad.
Capítulo 8
1. Utilice los siguientes algoritmos de clasificación para ordenar las secuencias de palabras clave (49, 7, 50, 5, 94, 16, 90, 29, 71) respectivamente y escriba los resultados intermedios obtenidos en cada pasada de clasificación.
(1) Ordenación por inserción directa
(2) Ordenación en colina
(3) Ordenación por burbujas mejorada
(4 ) Ordenación rápida
(5) Ordenación por selección directa
(6) Ordenación en montón
(7) Ordenación por combinación
2. Un algoritmo de clasificación de burbujas es el llamado "flotante", es decir, cada operación de clasificación "hace flotar" palabras clave más pequeñas hacia la parte superior (el lado con el subíndice de matriz más pequeño). Escriba un algoritmo mejorado de clasificación de burbujas "hundidas".
3. Dé ejemplos para ilustrar que el algoritmo de clasificación por selección directa, el algoritmo de clasificación rápida y el algoritmo de clasificación en montón no son estables.