¿Alguien tiene la pregunta del examen final sobre estructura de datos? Préstamela como referencia y haré el examen pronto.

A:

06-07 Examen final del primer semestre

Código del examen: 03266A Horas de enseñanza: 112

Nombre del curso: Estructura de datos y algoritmo Objetos aplicables: Estudiantes de pregrado

1. Preguntas de opción única (Elija una respuesta correcta de las cuatro respuestas alternativas a cada una de las siguientes preguntas y escriba su código en la posición correspondiente de la respuesta hoja Respuesta No se otorgarán puntos por preguntas incorrectas o no seleccionadas. Cada pregunta vale 2 puntos, ***24 puntos)

1. La estructura de datos se define formalmente como (K, R), donde. K es un conjunto finito de elementos de datos, R es un conjunto finito de ___ en K.

A. Operación B. Imagen C. Almacenamiento D. Relación

2. Si la tabla lineal adopta una estructura de almacenamiento en cadena, se requiere la dirección de la unidad de almacenamiento disponible en la memoria ____.

A. Debe ser continuo B. Algunas direcciones deben ser continuas C. Debe ser no continuo D. Puede ser continuo o no continuo

3. La secuencia de inserción de un la pila es a, b, c, d, e, entonces la secuencia de salida imposible de la pila es ____.

A.edcba B.decba C.dceab D.abcde

4. La secuencia de entrada de una cola es 1, 2, 3, 4, luego la secuencia de salida de la cola es ____ .

A.4, 3, 2, 1 B.1, 2, 3, 4 C.1, 4, 3, 2 D.3, 2, 4, 1

5. La mayor similitud entre pilas y colas es ____.

A. Ambos son los primeros en entrar, los últimos en salir B. Ambos son los primeros en entrar, los primeros en salir

C Solo se permite la inserción y eliminación de elementos en los puntos finales D. No hay similitudes<. /p>

6. En una lista enlazada individualmente, se sabe que el nodo señalado por q es el nodo predecesor del nodo señalado por p. Si el nodo s se inserta entre q y p, se ejecutará ____.

A. s->siguiente = p->siguiente; p->siguiente=s; B. p->siguiente = s->siguiente = p;

C. q->next = s; s->next = p; D. p->next = s; s->next = q;

7. Sea la cadena s1='ABCDEFG ' , s2='PQRST', la función con (x, y) devuelve la cadena de conexión de las cadenas x e y, la función subs (s, i, j) devuelve una subcadena de j caracteres comenzando desde el carácter del número de secuencia i, el la función len(s) devuelve la longitud de la cadena s, entonces la cadena resultante de con (subs (s1, 2, len (s2)), subs (s1, len (s2), 2)) es ____.

A. BCDEF B. BCDEFG C. BCPQRST D. BCDEFEF

8. Supongamos que solo hay nodos con grado 0 y grado 2 en el árbol binario con altura h, entonces esto tipo de El número de nodos contenidos en un árbol binario es al menos ____.

A. 2h B. 2h-1 C. 2h +1 D. h +1

9. La secuencia de acceso a nodos de un determinado árbol binario en el recorrido de preorden es abdgcefh y recorrido en orden La secuencia de acceso al nodo es dgbaechf, luego la secuencia de acceso al nodo para el recorrido posterior es ____.

A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca

10. Un gráfico no dirigido con 6 vértices debe tener al menos ____ aristas para garantizar que sea un gráfico conectado.

A. 5 B. 6 C. 7 D. 8

11. Cuando se utiliza el método de búsqueda secuencial para encontrar una tabla lineal de longitud n, la longitud de búsqueda promedio de cada elemento es - .

A. n B. n/2 C. (n+1)/2 D. (n-1)/2

12. En el método de clasificación, la secuencia es nunca ordenado El método de seleccionar elementos de una secuencia y colocarlos en un extremo de la secuencia ordenada (nota: inicialmente vacío) se llama ____.

A. Clasificación por colinas B. Clasificación por combinación C. Clasificación por inserción D. Clasificación por selección

2. Complete los espacios en blanco (rellene el contenido correcto en la línea horizontal de cada pregunta). , 1 punto por cada espacio en blanco, ***7 puntos )

1. En la estructura de árbol, el nodo raíz no tiene nodos y cada uno de los demás nodos tiene exactamente un nodo predecesor.

2. Al realizar la clasificación de burbujas en una secuencia de n elementos, el número mínimo de comparaciones es.

3. La cadena vacía es y su longitud es igual a 0.

4. Un árbol binario completo con n nodos tiene *** nodos hoja.

5. En la función hash H(key)=key % p, p debe ser .

6. Se conoce la cadena de patrón t=‘abcaabbabc’ y el siguiente valor de función correspondiente a cada carácter obtenido por el método KMP es.

3. Preguntas de respuesta corta (esta pregunta principal tiene 3 preguntas pequeñas, cada pregunta tiene 5 puntos, 15 puntos)

1. En el procesamiento de mesas lineales, generalmente se utilizan dos estructuras de almacenamiento. estructura de almacenamiento secuencial utilizada y estructura de almacenamiento en cadena. Describa en qué circunstancias es mejor utilizar una lista de secuencia que una lista vinculada.

2. Describe brevemente qué es una clasificación estable y qué es una clasificación inestable.

3. ¿Cuál es la forma de sufijo correspondiente a la siguiente expresión infija?

(1) (A + B) * D + E / (F + A * D) + C

(2) A && B|| {Nota: Según la prioridad de C)

4. Preguntas de Verdadero o Falso (Esta pregunta mayor tiene 10 preguntas pequeñas. Si la proposición es correcta, escriba "T" entre paréntesis después de la pregunta, y si la proposición es incorrecta, escriba "T" entre paréntesis después de la pregunta. Escriba "F" adentro, 1 punto por cada pregunta, ***10 puntos)

1. El elemento de datos no es el. unidad de datos más pequeña ( ).

2. Conocer la secuencia de preorden y la secuencia de postorden de un árbol binario puede construir de forma única el árbol binario. ( )

3.La red AOE es un gráfico conectado acíclico ponderado. ( )

4. Para ingresar el mismo conjunto de códigos clave, aunque el orden de entrada de cada código clave es diferente, los árboles de búsqueda binarios obtenidos son los mismos ( ).

5. El número de hojas de un árbol debe ser igual al número de hojas del árbol binario correspondiente. ( )

6. Las listas de adyacencia solo se pueden usar para almacenar gráficos dirigidos, y las matrices de adyacencia son adecuadas para almacenar gráficos dirigidos y no dirigidos. ( )

7. La clasificación por inserción a mitad de camino es estable. ( )

8. En el método hash, el uso de funciones hash dobles puede garantizar que no habrá absolutamente ninguna colisión. ( )

9. Eliminar la recursividad no requiere necesariamente el uso de una pila ( )

10. La clasificación del montón es un tipo de clasificación de intercambio.

( )

5. Preguntas de aplicación de análisis (esta pregunta vale 26 puntos, las preguntas 1 y 4 valen 6 puntos cada una, las preguntas 2 y 3 valen 7 puntos cada una)

1 . Después de leer, analice la función del siguiente segmento del programa (6 puntos)

SeqStack S1, S2, tmp;

DataType x // Suponga que la pila tmp y S2 se han inicializado.

while ( ! StackEmpty (S1))

{ x=Pop(S1);

Push(tmp,x);

}

mientras ( ! StackEmpty (tmp) )

{ x=Pop(tmp);

Empujar( S2, x);

}

2. Solo pueden aparecer 8 tipos de caracteres en un determinado subsistema durante la comunicación, y sus probabilidades de aparición son 0,05, 0,29, 0,07, 0,08, 0,14, 0,23, 0,03 y 0,11. Diseño de codificación Huffman. (7 puntos)

3. Sea la tabla hash HT[13] y la función hash H (clave) = clave %13. Utilice detección lineal y luego hash para resolver conflictos y cree una tabla para la siguiente secuencia de claves 12, 23, 45, 57, 20, 03, 78, 31, 15, 36. Dibuje la tabla hash correspondiente y calcule la longitud de búsqueda promedio para una búsqueda exitosa con la misma probabilidad. (7 puntos)

4. Suponga que la secuencia del código de clasificación a ordenar es {12, 2, 16, 30, 28, 10, 16 *, 20, 6, 18}, intente escribir usando Hill El resultado después de cada paso de clasificación del método de clasificación (el incremento es 5, 2, 1). (6 puntos)

6. Preguntas de diseño de algoritmos (***18 puntos por esta pregunta, 10 puntos por la primera pregunta, 8 puntos por la segunda pregunta)

1. Escribir una frecuencia de algoritmo, cuenta la frecuencia de aparición de diferentes caracteres contenidos en una cadena de entrada. Valide el algoritmo con datos de prueba apropiados. (10 puntos)

2. En un árbol binario representado por una lista binaria enlazada, intente escribir un algoritmo que atraviese el árbol binario en orden jerárquico y cuente el número de nodos con grado 1 en el árbol. . Es necesario proporcionar la definición del tipo de lista enlazada binaria. (8 puntos)

Respuesta:

06-07 Primer semestre

Respuestas de referencia del examen final y estándares de puntuación

Código de examen: 03266A Horas lectivas: 112

Nombre del curso: Estructura de datos y algoritmo Objetos aplicables: Estudiantes de pregrado

1. Preguntas de opción múltiple (2 puntos por cada pregunta, ***24 puntos.)

1. D 2. D 3. C 4. B 5. C 6. C

7. D 8. B 9. D 10. A 11. C 12. D

2. Complete los espacios en blanco (1 punto por cada espacio en blanco, ***7 puntos.)

1. Padre (o precursor), 1

2 n- 1

3. Cadena que no contiene ningún carácter

4. (n+1)/2

5. Número primo

6 0111223123

3. Preguntas de respuesta corta (cada pregunta tiene 5 puntos, ***15 puntos)

1. Respuesta: ① Al almacenar secuencialmente, las direcciones de almacenamiento de los elementos de datos adyacentes también son adyacentes (unidad lógica y física); se requiere que las direcciones de las unidades de almacenamiento disponibles en la memoria sean continuas.

Ventajas: alta densidad de almacenamiento y alta utilización del espacio de almacenamiento. Desventajas: Inconveniente al insertar o eliminar elementos.

② Durante el almacenamiento en cadena, los elementos de datos adyacentes se pueden almacenar a voluntad, pero el espacio de almacenamiento ocupado se divide en dos partes, una parte almacena el valor del nodo y la otra parte almacena el puntero que indica la relación entre nodos

Ventajas: Es conveniente insertar o eliminar elementos y su uso es flexible. Desventajas: baja densidad de almacenamiento (<1), baja utilización del espacio de almacenamiento.

Las listas secuenciales son adecuadas para operaciones estáticas como búsquedas; las listas enlazadas son adecuadas para operaciones dinámicas como inserción y eliminación.

Si la longitud de la tabla lineal cambia poco y su operación principal es la búsqueda, utilice una tabla secuencial.

Si la longitud de la tabla lineal cambia mucho y su operación principal es la inserción; , eliminar operación, usar lista vinculada.

2. Respuesta: En la secuencia ordenada, dos palabras clave iguales Ki = Kj, si Ki está por delante de Kj en la secuencia antes de ordenar, si Ki todavía está por delante de Kj en la secuencia después de ordenar Kj, el método de clasificación utilizado se dice que es estable; por el contrario, si es posible hacer que Kj esté por delante de Ki en la secuencia ordenada, se dice que el método de clasificación utilizado es inestable.

3. Respuesta: La forma de sufijo de cada expresión infija es la siguiente:

(1)AB+D*EFAD*+/+C+

( 2 )AB&&EF>!||

4. Preguntas de verdadero o falso (***10 preguntas pequeñas en esta pregunta principal. Si la proposición es correcta, escriba "T" entre paréntesis después de la pregunta. Si la proposición es incorrecta, escriba "T" entre paréntesis después de la pregunta F", 1 punto por cada pregunta, ***10 puntos)

1.T 2.F 3.T 4.F. 5.F

6.F 7.T 8.F 9.T 10.F

5. Preguntas de aplicación de análisis (las preguntas 1 y 4 valen 6 puntos cada una, las preguntas 2 y 3 valen 7 puntos cada uno)

1. (6 puntos)

Respuesta: La función del segmento de programa es usar la pila tmp para copiar todos los elementos de una pila s1 no vacía a una pila s2 tal como está.

2. (7 puntos)

Respuesta: Por conveniencia, permita que los pesos de varios caracteres sean w={5,29,7,8,14,23,3,11}. Como n=8, el árbol de Huffman que se va a construir tiene m=2n-1=2*8-1=15 nodos.

El árbol de Huffman generado se muestra en la siguiente figura:

El código de Huffman es: el código de carácter con probabilidad 0,23 es: 00

El código de carácter con probabilidad 0,11 es: 010

La codificación de caracteres con probabilidad 0.05 es: 0110

La codificación de caracteres con probabilidad 0.03 es: 0111

La codificación de caracteres con probabilidad 0.29 es: 10

La codificación de caracteres con probabilidad 0,14 es: 110

La codificación de caracteres con probabilidad 0,07 es: 1110

La codificación de caracteres con probabilidad 0,08 es: 1111

3. (7 puntos)

Respuesta: Usando la función hash H(key)=key mod 13 hay:

H(12)=12, H(23) = 10, H(45)=6, H(57)=5, H(20)=7, H(03)=3, H(78)=0, H(31)=5, H(15)= 2 , H(36)=10

Utilice el método de exploración lineal para crear la tabla:

0 1 2 3 4 5 6 7 8 9 10 11 12

78 15 03 57 45 20 31 23 36 12

1 1 1 1 1 1 4 1 2 1

La duración promedio de una búsqueda exitosa es:

ASL= 1/10 (1+1+1+1+1+1+4+1+2+1)=14/10

4. (6 puntos)

Respuesta: Clasificación Hill (el incremento es 5, 2, 1)

6 preguntas de diseño de algoritmos (10 puntos por la primera pregunta, 8 puntos por la segunda pregunta)

1. ( 10 puntos)

incluir

incluir”string.h”

int charnumber=128;

frecuencia nula (string&s,int C[ ]){

for(int i=0;i< charnumber;i++) C[i]=0;

for( i=0;i < s.length();i++) C[atoi(s[i])]++;

for( i=0;i< charnumber;i++)

if( C[i]>0) cout<<”(”<

}

2. (8 puntos)

Definición de tipo (omitida)

int Level(BiTree bt) //Recorre el árbol binario jerárquicamente y cuenta el número de nodos con grado 1

{

int num=0; //El número de nodos con un grado estadístico numérico de 1

if(bt){

QueueInit(Q); QueueIn(Q,bt); //Q es una cola con punteros de nodos de árbol binario como elementos

while(!QueueEmpty(Q))

{ p= QueueOut(Q); printf(p->data); //Sacar de la cola, acceder al nodo

if(p->lchild && !p->rchild ||!p->lchild && p->rchild

)

num++;//Nodo con grado 1

if(p->lchild) QueueIn(Q,p->lchild); //El hijo izquierdo no vacío ingresa a la cola

if(p->rchild) QueueIn(Q,p->rchild); //Se agrega a la cola el hijo derecho no vacío

}

}

}

p>

return(num); //Devuelve el número de nodos con grado 1

}

B:

06-07 Examen final de un semestre

Código del examen: 03266B Horas lectivas: 112

Nombre del curso: Estructura de datos y algoritmo Objetos aplicables: Estudiantes de pregrado

1. Preguntas de opción múltiple (Elija una respuesta correcta de las cuatro respuestas alternativas a cada una de las siguientes preguntas y escriba su número de código en la posición correspondiente de la hoja de respuestas. Si el la respuesta es incorrecta o no se selecciona, la pregunta no se calificará. Cada pregunta vale 2 puntos, ** *24 puntos)

1. La estructura de datos se define formalmente como (K, R). donde K es un conjunto finito de ____ y ​​R es un conjunto finito de relaciones en K.

A. Algoritmo B. Elemento de datos C. Operación de datos D. Estructura lógica

2. En la estructura de datos, la estructura de datos se puede dividir lógicamente en ____.

A. Estructura dinámica y estructura estática B. Estructura compacta y estructura no compacta

C. Estructura lineal y estructura no lineal D. Estructura interna y estructura externa

3. Entre las siguientes afirmaciones, la correcta es ____.

A. La estructura de almacenamiento de una tabla lineal es mejor que una estructura de almacenamiento encadenada

B. Una matriz bidimensional es una tabla lineal cuyos elementos de datos son tablas lineales

C. El modo de operación de la pila es el primero en entrar, el primero en salir

D. El modo de operación de la cola es el primero en entrar, el último en salir

4. Si el La secuencia de inserción de una pila es 1, 2, 3,…, n, su secuencia de salida es p1, p2, p3,…, pn, si p1 = n, entonces pi es ____.

A. i B. n = i C. n - i +1 D. Incierto

5. Determinar las condiciones para una cola circular QU (el número máximo de elementos es m ) estar vacío sí____.

A. QU->delantero == QU->trasero B. QU->delantero != QU->trasero

C. QU->delantero == (QU-> rear+1)%m D. QU->front != (QU->rear+1)%m

6. En una lista enlazada individualmente, se sabe que el nodo señalado por p no es el último nodo, inserte el nodo señalado por s después de p, luego ejecute ____.

A. s->siguiente = p; p->siguiente=s; B. s->siguiente = p->siguiente; p->siguiente = s;

C s->next = p->next; p = s; D. p->next = s; s->next = p;

7. La cadena es una tabla lineal especial. reflejado en ____.

A. Se puede almacenar secuencialmente B. El elemento de datos es un carácter

C. Se puede vincular y almacenar D. El elemento de datos puede tener varios caracteres

8. Ya sabemos que la secuencia transversal posterior al orden de un determinado árbol binario es dabec, la secuencia transversal en orden es debac y la secuencia transversal de preorden es ____.

A. acbed B. decab C. deabc D. cedba

9. Para un árbol binario completo, m hojas, n nodos, profundidad h, luego ____.

A. n = h + m B. h + m = 2n C. m = h-1 D. n = 2h -1

10. Un vértice con n vértices An Un gráfico no dirigido tiene como máximo ____ aristas.

A. n B. n(n-1) C. n(n-1)/2 D. 2n

11. El método de búsqueda secuencial es adecuado para estructuras de almacenamiento de ___ Tabla lineal de _.

A. Almacenamiento hash B. Almacenamiento secuencial o almacenamiento vinculado

C Almacenamiento comprimido D. Almacenamiento de índice

12. La secuencia de elementos a ordenar es. Básicamente, bajo la premisa del orden, el método de clasificación más eficiente es____.

A. Ordenación por inserción B. Ordenación por selección C. Ordenación rápida D. Ordenación por combinación

2. Complete los espacios en blanco (llene el contenido correcto en la línea horizontal de cada pregunta). 1 punto por vacío, 7 puntos por ***)

1. En una estructura lineal, el primer nodo es un nodo predecesor y cada uno de los nodos restantes tiene un solo nodo predecesor.

2. En la matriz de adyacencia del gráfico no ponderado G, si A[i][j] es igual a 1, es igual a A[j][i] = .

3. Según la definición de árbol binario, un árbol binario con tres nodos tiene diferentes formas.

4. La cadena de espacio se refiere a y su longitud es igual a .

5. En el almacenamiento de hash, cuanto mayor sea el valor del factor de llenado α, mayor será la posibilidad de conflicto al almacenar elementos.

6. Se sabe que la cadena del patrón t= ‘abacabaaad’, el siguiente valor de función correspondiente a cada carácter obtenido por el método KMP es .

3. Preguntas de respuesta corta (esta pregunta principal tiene 3 preguntas pequeñas, cada pregunta tiene 5 puntos, máximo 15 puntos)

1. Compara la búsqueda estática y la búsqueda dinámica La principal diferencia ¿Cuáles son las diferencias en sus operaciones básicas?

2. ¿Cuáles son los tipos de estructuras lógicas y qué tipos de estructuras de almacenamiento existen?

3. Entre los árboles de diferentes formas con n (n>1) nodos, ¿cuál es la profundidad del árbol con la profundidad más pequeña? ¿Cuántos nodos foliares y no foliares tiene?

4. Preguntas de Verdadero o Falso (Esta pregunta principal tiene 10 preguntas pequeñas. Si la proposición es correcta, escriba "T" entre paréntesis después de la pregunta. Si la proposición es incorrecta, escriba "F" en los corchetes después de la pregunta. Por cada pregunta pequeña 1 punto, ***10 puntos)

1. Cada estructura de datos debe tener tres operaciones básicas: inserción, eliminación, búsqueda ().

2. Un árbol binario completo no es necesariamente un árbol binario completo. ( )

3. La suma de los pesos del árbol de expansión mínimo de un gráfico conectado ponderado debe ser menor que la suma de los pesos de sus otros árboles de expansión. ( )

4. El tiempo de búsqueda promedio de cualquier árbol de búsqueda binario es menor que el tiempo de búsqueda promedio de una lista secuencial que busca el mismo nodo usando el método de búsqueda secuencial. ( )

5. Todos los nodos de la lista enlazada lineal deben ser del mismo tipo. ( )

6. Cuando se utiliza una matriz de adyacencia para almacenar un gráfico, sin considerar el almacenamiento comprimido, el espacio de almacenamiento ocupado solo está relacionado con el número de vértices en el gráfico y no tiene nada que ver con el número de aristas en el gráfico ( ).

7. Al resolver conflictos en el método hash, el valor del factor de carga debe estar entre (0, 1). ( )

8. Si alguna actividad clave se retrasa, todo el proyecto se retrasará. ( )

9. El valor absoluto de la diferencia de profundidad entre los subárboles izquierdo y derecho de un árbol binario equilibrado no supera 1. ( )

10. Si un grafo dirigido con n nodos tiene n (n-1) aristas, debe estar fuertemente conexo. ( )

5. Preguntas de aplicación de análisis (esta pregunta vale 26 puntos, las preguntas 1 y 4 valen 6 puntos cada una, las preguntas 2 y 3 valen 7 puntos cada una)

1 Siguiente Siguiente ¿Cuál es la función del algoritmo anterior? (6 puntos)

LinkList Demo(LinkList L)

{ // L es una lista enlazada individualmente de nodos sin cabeza

ListNode *Q,*P;

if(L&&L->siguiente){

Q=L;

L=L->siguiente ;

P=L;

while (P->siguiente) P=P->siguiente;

P->siguiente=Q-> next=NULL;

}

return L;

}

2. Simplifique el gráfico dado en un árbol de expansión mínimo, que requiera que desde el vértice 1 Partir. (7 puntos)

3. Sea la tabla hash HT[13] y la función hash sea H (clave) = clave %13. Utilice doble hash para resolver conflictos y cree una tabla para la siguiente secuencia de claves 12, 23, 45, 57, 20, 03, 78, 31, 15, 36. La función de repetición es RH (clave) = (7*clave) % 10 + 1, y la fórmula para encontrar la siguiente dirección es Hi = (Hi-1 + RH (clave)) % 13, H1 = H (clave). Dibuje la tabla hash correspondiente y calcule la longitud de búsqueda promedio para una búsqueda exitosa con la misma probabilidad. (7 puntos)

4. Suponga que la secuencia del código de clasificación a ordenar es {12, 2, 16, 30, 28, 10, 16 *, 20, 6, 18}, escriba el código rápido método de clasificación El resultado después de cada paso de clasificación. (6 puntos)

6. Preguntas de diseño de algoritmos (***18 puntos por esta pregunta, 10 puntos por la primera pregunta, 8 puntos por la segunda pregunta)

1. Pruebe para diseñar un Implementar la función de operación de búsqueda Localizar como se requiere a continuación. Hay una lista L doblemente enlazada con un nodo de encabezado. Cada nodo tiene 4 miembros de datos: el puntero llink que apunta al nodo predecesor, el puntero rlink que apunta al nodo sucesor, los datos del miembro que almacena datos de caracteres y la frecuencia de acceso. . La frecuencia de todos los nodos es inicialmente 0. Siempre que se realiza una operación Locate(L, x) en la lista vinculada, la frecuencia de acceso del nodo cuyo valor de elemento es x aumenta en 1, y el nodo avanza y se vincula a la frecuencia de acceso igual a él. En el nodo, todos los nodos de la lista vinculada están organizados en orden de frecuencia de acceso decreciente, de modo que los nodos a los que se accede con frecuencia siempre están cerca del encabezado de la lista. (10 puntos)

2. Suponga que un árbol binario utiliza una lista binaria enlazada como estructura de almacenamiento y diseñe un algoritmo para intercambiar los subárboles izquierdo y derecho de todos los nodos en el árbol binario. Es necesario proporcionar la definición del tipo de lista enlazada binaria. (8 puntos)

Respuesta:

06-07 Primer semestre

Respuestas de referencia del examen final y estándares de puntuación

Código de examen: 03266B Horas lectivas: 112

Nombre del curso: Estructura de datos y algoritmo Objetos aplicables: Estudiantes de pregrado

1. Preguntas de opción múltiple (cada pregunta vale 2 puntos, ***24 puntos.

)

1. B 2. C 3. B 4. C 5. A 6. B

7. B 8. D 9. D 10.C 11. B 12. A

2. Complete los espacios en blanco (1 punto por cada espacio en blanco, ***7 puntos.)

1. Ninguno

2. 1

3. 5

4. Todos los caracteres de la cadena son espacios y el número de espacios es

5. Grande

6. 0112123422.

3. Preguntas de respuesta corta (esta gran pregunta tiene 5 preguntas pequeñas, cada pregunta son 5 puntos, 15 puntos)

1. Respuesta: La mayor diferencia entre los dos métodos de búsqueda es:

El método de búsqueda estática no modifica la tabla de búsqueda, la búsqueda dinámica inserta el nodo en la tabla de búsqueda cuando la búsqueda no tiene éxito, lo que significa que sí; es posible modificar la tabla de búsqueda;

Las operaciones básicas de la búsqueda estática incluyen la creación de tablas, la búsqueda y la lectura de elementos de la tabla, además de las operaciones básicas anteriores, la búsqueda dinámica también incluye operaciones de inicialización, inserción y eliminación; /p>

2. Respuesta: Según los datos Las diferentes características de la relación entre elementos generalmente incluyen las siguientes cuatro estructuras básicas: (1) conjuntos; (2) estructuras lineales (3) estructuras de árbol; estructuras de grafos o estructuras de redes. Hay dos estructuras de almacenamiento diferentes: estructura de almacenamiento secuencial y estructura de almacenamiento en cadena.

3. Respuesta: La profundidad del árbol con la profundidad más pequeña es 2. Para estos n nodos, excepto un nodo raíz, los n-1 nodos restantes son todos nodos hoja, por lo que su profundidad es 2. El número de nodos hoja de este árbol es n-1 y el número de nodos que no son hoja es 1.

4. Preguntas de Verdadero o Falso (1 punto por cada pregunta, ***10 puntos)

1. (V) 2. (F) 3. (V) 4. (F ) 5. (T)

6. (T) 7. (F) 8. (T) 9. (T ) 10. (T)

5. Análisis de preguntas de aplicación (***26 puntos por esta pregunta, 6 puntos cada una por las preguntas 1 y 4, 7 puntos cada una por las preguntas 2 y 3)

1. (6 puntos)

Respuesta: Este algoritmo La función es: eliminar el nodo inicial y vincularlo al nodo terminal para convertirse en el nuevo nodo terminal, y el segundo nodo original se convierte en el nuevo nodo inicial y devolver el puntero principal de la nueva lista vinculada.

2. (7 puntos)

Respuesta:

3. (7 puntos)

Respuesta: Utilice la función hash H( key)=key mod 13 tiene:

H(12)=12, H(23)=10, H(45)=6, H(57)=5, H(20)=7, H(03)=3, H(78)=0, H(31)=5, H(15)=2, H(36)=10

Utilice el método de doble hash para crear una tabla: Hola =（Hi-1+RH(tecla)）%13, Hola =H(tecla)

0 1 2 3 4 5 6 7 8 9 10 11 12

78 15 03 57 45 20 31 36 23 12

1 1 1 1 1 1 3 5 1 1

La longitud promedio de una búsqueda exitosa es: ASL =1/10 (1+ 1+1 +1+1+1+3+5+1+1)=16/10

4. (6 puntos)

Respuesta:

6. Preguntas de diseño de algoritmos (10 puntos por la primera pregunta, 8 puntos por la segunda pregunta)

1. (10 puntos)

Respuesta:

(1) Definir la estructura de la lista enlazada

struct DoubleListNode {

char data;

int freq;

DoubleListNode * llink, *rlink ;

};

Inicialmente, el valor del campo freq de todos los nodos es 0.

(2) Definir función

DoubleListNode * localizar ( DoubleListNode *f ; char &x ) {

DoubleListNode * p, *q;

p = f→rlink; /*Omitir el nodo de encabezado*/

while ( p != NULL && p→data != x ) p = p→rlink; p>

if ( p ) {

p→freq ++; q = p→lenlace;

p→renlace→lenlace = q; rlink; /*Elige p*/

while ( q != f &&q→freq < p→freq ) q =q→llink;

p→ llink = q; p>

p→rlink = q→rlink; q→rlink→llink = p;

q→rlink = p /*Insertar p después de q*/

}

devolver p;

}

2. (8 puntos)

Respuesta: Definición de tipo (omitida)

void exchange(BiTree bt)// Intercambia los subárboles izquierdo y derecho de todos los nodos del árbol binario bt

{

if(bt)

{ BiTree s;

s=bt->lchild; ; bt- >rchild=s; //Intercambia los hijos izquierdo y derecho

exchange(bt->lchild); //Intercambia los subárboles izquierdo y derecho de todos los nodos en el subárbol izquierdo