Introducción a las estructuras de datos

Examen Nacional de Autoestudio de Educación Superior en octubre de 2010

Preguntas de Introducción a la Estructura de Datos

Código del Curso: 02142

1. Preguntas de elección (esta pregunta principal tiene 15 preguntas pequeñas, cada pregunta vale 2 puntos y vale 30 puntos)

Solo una de las cuatro alternativas enumeradas en cada pregunta pequeña cumple con los requisitos de la pregunta. en el código entre paréntesis después de la pregunta. No habrá puntos por selecciones incorrectas, selecciones múltiples o ninguna selección.

1. ¿Cuál de las siguientes descripciones es correcta ( )

A. El elemento de datos es la unidad más pequeña de datos

B. La estructura de datos es un objeto de datos con estructura

C. 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í.

D No existe, en principio, diferencia entre algoritmos y programas, y ambos son comunes cuando se habla de estructuras de datos.

2. La complejidad temporal de la clasificación por combinación es ( )

A. O(n2)

B.O(nlog2n)

C.O(n)

D.O(log2n)

3. La complejidad temporal de la búsqueda binaria es ( )

A. O(n2)

B.O(nlog2n)

C.O(n)

D.O(log2n)

4. Hay 90.000 elementos en la tabla almacenada secuencialmente, que se han organizado en orden ascendente por valor de palabra clave. Suponga que la probabilidad de buscar cada elemento es la misma y que el valor de palabra clave de cada elemento es diferente cuando se realiza una búsqueda secuencial. método, un promedio El número de comparaciones es ( )

A. 25000

B.30000

C.45000

D.90000

5. Un archivo hash es un tipo de ( )

A. Archivo secuencial

B. Archivo de índice

C. Archivo de enlace

D. Archivo de direccionamiento computacional

6. La complejidad temporal de multiplicar dos matrices A: m×n y B: n×p es ( )

A. O(n)

B.O(mnp)

C.O(n2)

D.O(mp)

7. llamadas La estructura de datos es ( )

A.pila

cola

C lista enlazada

D. p>

8． La matriz bidimensional A[n][m] se almacena en orden de columna principal. Cada elemento de la matriz A ocupa 1 byte. A[1][1] es el primer elemento y su dirección es 0. Entonces el elemento. A[i][ La dirección de j] es ( )

A (i-1)×m+(j-1)

B.(j-1)×n+. (i-1)

C.(j-1)×n+i

D.j×n+i

9. La búsqueda en amplitud del gráfico es ( )

A. Cola

B. Árbol

C. Pila

D. La secuencia (21, 19, 37, 5, 2) se ordena de pequeña a grande mediante el método de clasificación de burbujas. Después de realizar el primer intercambio, el resultado es ( )

A. (19, 21, 37, 5, 2)

B (21, 19, 5, 37, 2)

C. )

D. (2, 21, 19, 37, 5)

11. Cuando los datos se representan en la memoria de la computadora, la dirección de almacenamiento del nodo se calcula directamente en función de la palabra clave del nodo. Este método se llama ( )

A. Método de almacenamiento de índice

B. Método de almacenamiento secuencial

C. Método de almacenamiento en cadena

D. En una lista enlazada individualmente, cada nodo se almacena en dos campos, uno es el campo de datos y el otro es el campo de puntero. El campo de puntero apunta a () del nodo

A. Predecesor directo

B. Sucesor directo

C. Nodo inicial

D. En una lista enlazada individualmente con un puntero principal conocido, para insertar un nuevo nodo en su cola, la complejidad temporal del algoritmo es ( )

A. O(1)

B.O(log2n)

C.O(n)

D.O(n2)

14. Realice la operación de puesta en cola en la cola en cadena, ( )

A. Es necesario determinar si el equipo está vacío

B Es necesario determinar si el equipo está lleno

p>C. Restringir a p al principio de la lista enlazada

D. Restringir a p al final de la lista enlazada

15. La secuencia de enteros 26, 59, 77, 31, 51, 11, 19, 42 se ordena de pequeña a grande mediante una clasificación de combinación bidireccional. El resultado de la combinación de la primera etapa es ( )

A. .31, 51 , 11, 42, 26, 77, 59, 19

B.26, 59, 31, 77, 11, 51, 19, 42

C.11 , 19, 26 , 31, 42, 59, 51, 77

D.26, 11, 19, 31, 51, 59, 77, 42

2. espacios en blanco (esta pregunta principal* **13 preguntas, cada pregunta vale 2 puntos, ***26 puntos)

Complete la respuesta correcta en el espacio en blanco de cada pregunta. No habrá puntos por entradas incorrectas o incompletas.

16. La complejidad temporal del siguiente segmento del programa es _______.

i=0; s=0;

mientras (s

{i++;

}

17． La estructura de almacenamiento de datos se divide en cuatro tipos: estructura de almacenamiento secuencial, _______, estructura de almacenamiento hash y estructura de almacenamiento de índice.

18． Al eliminar el i-ésimo elemento (1≤i≤n) de una lista de secuencia de longitud n, debe avanzar _______ elementos.

19． En una lista enlazada individualmente, insertar un nuevo nodo requiere modificar los punteros _______.

20. En una estructura de cola, el final que permite la inserción se llama _______.

21. El método de almacenamiento por compresión utilizado para matrices dispersas es _______.

22. Al insertar un nuevo nodo *p en una pila de enlaces cuyo puntero superior es superior, se deben realizar las operaciones p->next=top y _______.

23. El número de nodos de un árbol de Huffman con m nodos de hoja es _______.

24. En un árbol binario completo con n nodos, todos los nodos se numeran desde la raíz del árbol, de arriba a abajo y de izquierda a derecha. Sea 1 el número del nodo raíz. Si el nodo numerado i tiene un hijo derecho, entonces el número de su hijo derecho es _______.

25． En un árbol, el nodo _______ no tiene ningún nodo predecesor.

26. El número de arcos de un grafo completo dirigido con n vértices es _______.

27. El gráfico no dirigido G con n vértices se almacena con la matriz de adyacencia A[n][n], en la que la suma de todos los elementos de la i-ésima columna es igual al _______ del vértice Vi.

28. La complejidad temporal promedio de la clasificación por selección es _______.

3. Preguntas de aplicación (esta pregunta principal consta de 5 preguntas pequeñas, de 6 puntos cada una, 30 puntos)

29. El orden de entrada de los elementos en el extremo de entrada de la pila es 1, 2, 3, 4, 5, 6. La pila se puede extraer durante el proceso de apilamiento. ¿Se puede organizar en la secuencia 3, 2, 5,? 6, 4, 1 cuando salió? y 1, 5, 4, 6, 2, 3. Si es posible, escriba el proceso de empujar y desapilar. Si no, describa brevemente el motivo. (Utilice push(x) para empujar x hacia la pila y pop(x) para empujar x fuera de la pila)

30. Se sabe que la secuencia transversal de la raíz media de un árbol binario es CBEDFAGH y la secuencia transversal de la raíz posterior es CEFDBHGA.

31. Dada una tabla (15, 11, 8, 20, 14, 13), intente insertar los elementos en un árbol de clasificación binaria que inicialmente está vacío en el orden en que están en la tabla y dibuje la clasificación binaria una vez completada la inserción. Árbol y determine si el árbol de clasificación binario es un árbol de clasificación binario equilibrado. Si es un árbol de clasificación binario desequilibrado, ajústelo a un árbol de clasificación binario equilibrado.

32． Como se muestra en el gráfico no dirigido de la pregunta 32, (1) escriba su matriz de adyacencia; (2) escriba tres métodos de optimización profunda a partir del vértice A.

Busque primero la secuencia de vértices.

Imagen de la pregunta 32

33. Utilice el método de clasificación de burbujas para ordenar la secuencia de datos (49, 38, 65, 97, 76, 134, 27, 49) y escriba el proceso de clasificación. Y explique si la clasificación de burbujas es una clasificación estable.

4. Preguntas de diseño de algoritmos (esta pregunta principal tiene 2 preguntas pequeñas, cada pregunta vale 7 puntos y la puntuación total es 14 puntos)

34. Nodo hoja en el árbol binario Algoritmo de número de puntos.

35. La definición de tipo de la tabla hash abierta es la siguiente:

typedef struct tagnode

{keytype key;

struct tagnode*next;

}*pointer,node;

typedef pointer openhash［n］;

Intenta escribir el algoritmo de búsqueda en la tabla hash abierta.