Reciba preguntas reales

06-07 Documento de examen final del primer semestre

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

Nombre del curso: Estructura de datos y algoritmo Audiencia aplicable: Pregrado

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

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

A Operación b. Almacenar Relación

2. estructura de almacenamiento en cadena, se requiere la dirección de la unidad de almacenamiento disponible en la memoria.

A. Debe ser continuo. Algunas direcciones deben ser consecutivas. c. Debe ser discontinuo. Puede ser continua o discontinua

3. Si la secuencia de entrada de una pila es A, B, C, D, E, entonces la secuencia de salida imposible de esta pila es _ _ _ _.

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

4. Si el orden de entrada a la cola es 1, 2, 3 y 4, el orden 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. Las similitudes entre pila y cola son _ _ _ _.

R. Todos son los primeros en entrar, los últimos en salir. b. Todo es el primero en entrar, el primero en salir.

C. Sólo se puede insertar o eliminar el elemento D en el punto final. *No* hay puntos en común.

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 se inserta un nodo S entre Q y P, ejecute _ _ _ _.

A. s-& gt; siguiente = s-& gt; siguiente = p;

C.q->; siguiente = s-& gt; siguiente = p;

7. Supongamos que la cadena S1 ='abcdefg', S2 ='pqrst', la función con (x, Y) devuelve la cadena de concatenación de las cadenas X e Y, y la función subs (s, I, j) devuelve la secuencia de A subcadena de la cadena S compuesta por j caracteres comenzando desde el número de carácter I. La función len (s) devuelve la longitud de la cadena S, y luego con

A.BCDEF b. BCDEFG c . BCPQRST d . BCDEFEF

8. Si un árbol binario con altura h solo tiene nodos con grado 0 y grado 2, entonces el número de nodos contenidos en dicho árbol binario es al menos _ _ _ _.

A.2h b . 2h-1 c . 2h+1d

9. El nodo transversal intermedio es dgbaechf, los nodos transversales posteriores son _ _ _ _.

A.bdgcefha b . gdbecfha c . bdgaechf d . gdbehfca

10. Un gráfico no dirigido con seis 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 buscar una lista lineal de longitud n, la longitud de búsqueda promedio de cada elemento. es - .

A.Nota: n/2 c .(n+1)/2d .(n-1)/2

12. El método para seleccionar elementos y colocarlos en un extremo de la secuencia ordenada (nota: el comienzo está vacío) se llama _ _ _ _.

A. Clasificación por colinas b. Clasificación por fusión c. Clasificación por inserción d. Clasificación por selección

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

)

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

2. Al ordenar una secuencia de n elementos por burbuja, el número mínimo de comparaciones es.

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

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

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

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

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

1. El procesamiento de tablas lineales generalmente utiliza dos métodos. Hay tres estructuras de almacenamiento, estructura de almacenamiento secuencial y estructura de almacenamiento en cadena. Intente describir una situación en la que usar una lista secuencial es mejor que usar una lista enlazada.

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

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

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

(2)A &B||! (E & gtf){Nota: Basado en la prioridad de C)

Cuatro. Preguntas de Verdadero o Falso (esta pregunta principal es * * 10, escriba "T" entre paréntesis después de la pregunta si es correcta, y "F" entre paréntesis después de la pregunta si es incorrecta, 1 punto por cada pregunta pequeña, * *10 puntos).

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

2. Dada la secuencia de preorden y la secuencia de postorden de un árbol binario, se puede construir un árbol binario de forma única. ( )

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, el árbol de búsqueda binaria resultante es el mismo ().

5. El número de hojas de un árbol debe ser igual al número de hojas de su á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 plegable es estable. ( )

8. En el método hash, el uso de una función hash doble puede garantizar que no haya colisiones. ( )

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

10. La clasificación en montón es un tipo de clasificación de intercambio. ( )

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

1. Pensamientos después de la lectura ¿Cuál es la función del siguiente segmento del programa? (6 puntos)

S2, tmp, seq stack s 1;

Tipo de datos x; //La pila tmp y S2 se han inicializado.

Y (!StackEmpty (S1))

{ x = Pop(s 1);

Push(tmp, x);

}

Y (!StackEmpty (tmp))

{ x = Pop(tmp);

Empujar (S2, x);

}

2. Sólo pueden aparecer 8 caracteres en la comunicación de un subsistema, y ​​sus probabilidades de aparición son 0,05, 0,29, 0,07, 0,08, 0,14, 0,23, 0,03, 0,11. Intente diseñar la codificación Huffman. (7 puntos)

3. Sea la tabla hash HT[13] y la función hash sea H (clave) = clave %13. Los conflictos se resuelven mediante repetición de sonda lineal, con la secuencia de teclas 12, 23, 45, 57, 20, 03, 78, 31, 15, 36 que se enumeran a continuación. Dibuje la tabla hash correspondiente y calcule la duración promedio de una búsqueda exitosa con la misma probabilidad.

(7 puntos)

4. Suponga que el orden de los códigos de clasificación a ordenar es {12, 2, 16, 30, 28, 10, 16 *, 20, 6, 18}, intente utilice el método de clasificación Hill (los incrementos son 5, 2, 668) (6 puntos) Escriba un texto

6. Problemas de diseño de algoritmos (***18 puntos por esta pregunta, 10 puntos por el primer elemento, 8. puntos para el segundo elemento)

1. Escriba una frecuencia de algoritmo para calcular la frecuencia de los diferentes caracteres contenidos en la cadena de entrada. El algoritmo fue validado 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. Se requiere una definición de tipo para una 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 Tiempo de enseñanza: 112

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

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

1.D 2. D3. Dinamita C 4. B5. C6. C

7.D 8. B9. D10. A11. C12. D

2. Rellena los espacios en blanco (65438 + 0 puntos por cada casilla, ***7 puntos.)

1.

2 .n-1

3.Cadena sin caracteres

4.(n+1)/2

5.Número primo

6.0111223123

Tres. Preguntas de respuesta corta (5 puntos por cada pregunta, ***15 puntos)

1. Respuesta: ① En el almacenamiento secuencial, las direcciones de almacenamiento de los elementos de datos adyacentes también son adyacentes (se requiere integración lógica y física); que las direcciones de las unidades de almacenamiento disponibles en la memoria deben ser consecutivas.

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

② En 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 representa la relación entre nodos.

Ventajas: Es conveniente insertar o eliminar elementos y su uso es flexible. Desventajas: baja densidad de almacenamiento (

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

Si la longitud del lineal la lista no cambia mucho, si la operación principal es la búsqueda, use una lista secuencial;

Si la longitud de la tabla lineal varía mucho y su operación principal es la inserción y eliminación, entonces use una lista vinculada.

2. En la secuencia de clasificación, dos palabras clave iguales Ki = Kj. Si Ki está por delante de Kj en la secuencia antes de la clasificación y Ki todavía está por delante de Kj en la secuencia después de la clasificación. se dice que el método de clasificación utilizado es estable; otro Por otro lado, si es posible clasificar Kj antes que Ki en la secuencia ordenada, se dice que el método de clasificación utilizado es inestable

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

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

(2)AB & ampEF & gt! ||

Cuatro Pregunta * * 10, escribe "T" entre paréntesis después de la pregunta correcta, escribe "F" entre paréntesis después de la pregunta incorrecta, cada pregunta vale 1 punto, * * 10 puntos)

1. .T2. F3. t8. t10. , 2 y 3 puntos menores cada uno)

1. 6 puntos)

Respuesta: La función del segmento del programa es usar la pila tmp para copiar todos los elementos de una pila no vacía s1 en una pila s2. 7 puntos)

Respuesta: Por conveniencia, suponga que los pesos de varios caracteres son w = {5, 29, 7, 8, 14, 23, 3, 11}. Debido a que n=8, Huffmann. El árbol a construir tiene m = 2n-1 = 2 * 8-1 = 15 nodos. El árbol de Hoeffmann generado es el siguiente:

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.

El código de carácter con probabilidad 0,05 es: 0110.

La codificación de caracteres con probabilidad 0,03 es: 0111.

El código de carácter con probabilidad 0,29 es: 10.

El código de carácter 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: Utilice la función hash H(key)=key mod 13 que incluye:

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

Crear una tabla mediante exploración lineal;

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+4+1+2+1)= 14/10

4. : Clasificación por colinas (en incrementos de 5, 2, 1).

6. Preguntas de diseño de algoritmos (1 ítem 10 puntos, 2do ítem 8 puntos)

1 (10 puntos)

Incluyendo & ltiostream.h & gt.

Incluye "string.h"

int char number = 128;

frecuencia vacía (cadena y amplificadores, int C[]){

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

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

for(I = 0;i<charnumberi++)

if(C[I]>0)cout <<" ("<<I<<"):"t"<<c [I]<<"\t";

}

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; con número de grado estadístico de 1

If (bt){

queue init(Q); QueueIn(Q, Bt); //Q es una cola con un puntero de nodo de árbol binario. como elemento

And (!QueueEmpty(Q))

{ p = queue out(Q); printf( p->data); nodo

if(p->child&health.&!p->rchild ||!p->child&health .

&p->rchild)

num++; //Nodo con grado 1

If (p->lchild) QueueIn(Q, p->lchild) ;//No vacío el niño izquierdo se une al equipo

If (p->;rchild) QueueIn(Q, p->rchild); //El niño derecho no vacío se une al equipo

}

}

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

}

B:

06-07 Documento de examen final del primer semestre

Código del documento de examen: 03266B Tiempo de enseñanza: 112

Nombre del curso: Estructura de datos y algoritmo Objetivo aplicable: estudiantes universitarios

1. Preguntas de opción múltiple (Elija una respuesta correcta de las cuatro respuestas alternativas a las siguientes preguntas y escriba su código en la posición correspondiente de la hoja de respuestas. Si la respuesta es incorrecta o no está seleccionada, la pregunta no será calificada. *** 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 _ _ _ _. es un conjunto finito de relaciones en K..

A. Algoritmo b. Operación de datos d. dividirse 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. >3. Entre las siguientes afirmaciones, la correcta es _ _ _ _.

A. La estructura de almacenamiento de la mesa lineal es mejor que la estructura de almacenamiento en cadena.

Una matriz bidimensional es una lista lineal y sus elementos de datos son listas lineales.

C. El modo de funcionamiento de la pila es FIFO.

D. El modo de operación de la cola es FIFO.

4. Si el orden de pila de una pila es 1, 2, 3,..., n, su orden de salida es p1, p2, p3,..., pn. entonces pi es _ _ _ _.

A.ib.n = i.c.n-i+1 d.

5. La condición para juzgar si una cola circular qu (el elemento máximo es m) está vacía es _ _ _ _.

A. Qu-& gt; delantero = = QU-& gt; trasero b. = QU->;atrás

C Qu->frente = =(QU->trasero+1)% m d. =(QU->;Rear +1)%m

6. En una lista individualmente enlazada, se sabe que el nodo señalado por P no es el último nodo. Si el nodo señalado por S se inserta después de P, entonces se ejecutará _ _ _ _.

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