Una pregunta de opción múltiple (esta gran pregunta * * * Pregunta pequeña * * Puntos de bonificación por cada pregunta pequeña) Solo una de las cuatro opciones enumeradas en cada pregunta pequeña cumple con los requisitos del tipo pregunta. Por favor escriba la letra de la opción correcta entre paréntesis después de la pregunta.
El propósito del análisis del algoritmo es (?c?)
a. Descubrir la racionalidad de la estructura de datos; B. Estudiar la relación entrada-salida en el algoritmo.
La eficiencia del algoritmo de análisis C es mejorar la legibilidad del algoritmo de análisis D.
Usar (?b) es más apropiado
Lista enlazada individualmente b Lista enlazada doble
c Lista de secuencia d Lista enlazada circular
Lo siguiente es sobre listas lineales. La declaración incorrecta es (?d?)
La tabla de secuencia es una lista lineal implementada con una matriz unidimensional
La tabla de secuencia debe ocupar una lista continua. unidad de almacenamiento.
La utilización de espacio de la lista de secuencia C es mayor que la de la lista enlazada.
Cada nodo de la lista enlazada tiene un solo dominio de enlace.
La condición de juicio para el encabezado vacío de la lista enlazada individualmente del primer nodo es (b)
¿Cabeza = cero? B cabeza gtnext=zero
C cabeza gtnext=cabeza? D head lt gtNone
La cola generalmente usa dos estructuras de almacenamiento: (a)
a Estructura de almacenamiento secuencial y estructura de almacenamiento de lista vinculada b Modo hash y modo índice
c estructura de almacenamiento de lista enlazada y matriz D estructura de almacenamiento lineal y estructura de almacenamiento no lineal
Según la definición de árbol binario, un árbol binario con nodos es una especie (?c?)
¿Respuesta? ¿b? ¿do? D
La estructura del árbol binario se muestra en la siguiente figura, en la que el orden del recorrido secuencial es (?)
A a b d g c e f h
Royal Airways
C g d b e h f c a
D a b c d e f g h
La profundidad es como máximo (?c?) nodos (m)
¿Respuesta? ¿b? ¿do? D
Para un gráfico no dirigido con n vértices, si se representa mediante una lista de adyacencia, el tamaño de la matriz que almacena el nodo principal es (? ¿Respuesta?)
¿Un n? ¿Bn? ¿Cn? D n Número de aristas
En un gráfico no dirigido con n vértices, se requieren al menos (?c?) aristas
Una n? ¿Bn? ¿Cn? dNo aplicable
La diferencia fundamental entre las tablas de búsqueda estáticas y las tablas de búsqueda dinámicas es (?b?)
Sus estructuras lógicas son diferentes.
b tiene diferentes operaciones.
c contiene diferentes tipos de elementos de datos.
La implementación del almacenamiento D es diferente.
Los archivos hash utilizan la función hash para calcular el valor clave del registro en la dirección de almacenamiento del registro. Debido a que la función hash no tiene una correspondencia uno a uno, se elige un buen (?d). ?) El método es aplicar hash a la clave.
¿Función hash? bNúmeros primos en división
¿Manejo de conflictos? Función hash y manejo de conflictos
Para ordenar archivos grandes, es necesario estudiar la tecnología de clasificación en los periféricos, es decir (C?)
¿Método de clasificación rápida? b-Método de clasificación interno
cMétodo de clasificación externo? Método de clasificación cruzada tridimensional
Hay elementos desordenados y esperamos seleccionar el primer elemento más grande lo más rápido posible.
Es mejor elegir el método (?c?)
Clasificación de burbujas b Clasificación rápida
c Clasificación de montón d Clasificación de Radix
2 Pregunta de verdadero o falso. (en el enunciado de la pregunta, coloque un √ entre los siguientes corchetes para determinar si las siguientes preguntas son correctas. Califique * * * para cada elemento)
La estructura lógica de los datos se refiere a la relación lógica entre los elementos de datos ( ?)
En una estructura lineal, cada nodo tiene un predecesor inmediato y un sucesor inmediato(?)
La inserción y la eliminación son las dos operaciones básicas del array(?) p>
Nodo principal (?)
Inserte un nodo en el árbol binario para que el árbol binario ya no sea un árbol binario (?)
La estructura lógica del la tabla de búsqueda es un conjunto (?)
La recuperación y modificación de tablas de búsqueda estáticas se divide en dos fases separadas. )
Al insertar nuevos registros en un archivo de secuencia indexada, se debe copiar todo el archivo (?)
Si un determinado algoritmo de clasificación es inestable, este método no tiene ningún valor de aplicación práctica. )
En el peor de los casos, se necesita (n)(?)
Rellene los espacios en blanco (dé * * * puntos a cada pequeña pregunta)
Programación La esencia es _ _ _ _ _ y_ _ _ _ _ _
Supongamos que la cadena a='data' b='structure' c= ' ', luego A está conectada a C y luego conectada a B El resultado es _ _ _ _ _ _ _ _ _.
Por lo general, el nodo principal de una lista enlazada individualmente se refiere a _ _ _ _ _ _El nodo principal de una lista enlazada individualmente se refiere a _ _ _ _ _ _ _.
El orden de entrada de una cola es a b c d y el orden de salida de la cola es _ _ _ _ _ _ _ _ _.
Las dos estructuras de almacenamiento comúnmente utilizadas en estructuras de pila son _ _ _ _ _ _ y _ _ _ _ _
La profundidad de un árbol binario completo con n nodos es _ _ _ _ _ _ _ _ _
Las tres formas principales de atravesar un árbol son _ _ _ _ _ _ _ _ _ _ _ _ _ _ y atravesar niveles.
En la matriz de adyacencia A del grafo no dirigido, si a [i j] es igual, entonces a [i j] es igual a _ _ _ _ _ _ _ _ _.
Al implementar una tabla hash utilizando tecnología hash, las dos cuestiones principales a considerar son construir _ _ _ _ _ _ _ y resolver _ _ _ _ _ _.
La búsqueda en la tabla de secuencia de índice se divide en dos etapas ()_ _ _ _ _ _ _ () _ _ _ _ _ _ _
Los registros en el archivo hash Generalmente son almacenamiento grupal para formar una unidad de almacenamiento llamada _ _ _ _ _ _ _ _.
En lo que respecta a archivos, la unidad de almacenamiento básica determinada desde la perspectiva del usuario se llama_ _ _ _ _ _La unidad de almacenamiento básica determinada desde la perspectiva del dispositivo periférico se llama_ _ _ _ _ _ _ _ _ _
Hay tres formas de recuperar documentos_ _ _ _ _ _ _acceso_ _ _ _ _acceso y acceso por palabra clave.
El método de clasificación de intercambio más simple es _ _ _ _ _ _ _ _ _sort.
El método básico de clasificación externa es _ _ _ _ _ _ _ _ _
Cuatro preguntas de aplicación (cada pregunta pequeña recibe * * * puntos)
Supongamos que los archivos de los estudiantes contienen el nombre, el número del estudiante, la edad y el sexo. Si se utiliza una tabla lineal como estructura de datos para implementar la administración de archivos, se proporcionan respectivamente las definiciones de tipo de la tabla lineal bajo implementación secuencial e implementación de enlaces.
Hay un mensaje * * * que utiliza cinco caracteres a b c d e, y su frecuencia de aparición está en orden. Construya el árbol de Huffman correspondiente (el peso del nodo raíz del subárbol izquierdo es menor o igual que el peso del nodo raíz del subárbol derecho) y busque el código Huffman de cada carácter.
Hay una secuencia inicial desordenada que da {} los resultados de cada combinación y clasificación (orden ascendente)
Cinco problemas de diseño (cada pequeño problema * * * puntos)
Supongamos que se utiliza una lista circular enlazada individualmente para representar la cola (llamada cola en cadena circular). Solo hay un puntero de cola en esta cola, pero no hay ningún puntero de cola de cola. Escriba el proceso de inserción de un elemento X en la cola de cadena circular.
Algoritmo de búsqueda en profundidad para escribir gráficos conectados utilizando listas de adyacencia como estructuras de almacenamiento
Hay un conjunto de palabras clave {} y la función hash H(key)=key MOD es utilizado para resolver conflictos. Intente construir una tabla hash para esta secuencia de palabras clave en el espacio de direcciones hash de ~
Respuestas de referencia a las preguntas de introducción a la estructura de datos
1 pregunta de opción múltiple (puntuación para cada pregunta* * *punto)? ¿do? ¿b? ¿d? ¿b? ¿A
c? ¿b? ¿do? ¿respuesta? C
Inglés de negocios
2. Preguntas de verdadero o falso (cada pequeña pregunta vale * * * puntos)
× ?× ?×?× ?× ?
√ ?√ ?× × √?Rellene los espacios en blanco (* * *puntos por cada pregunta)? ()¿Representación de datos? ()¿Proceso de datos? ¿"estructura de datos"? () Agregue un nodo del mismo tipo antes del primer nodo de la lista enlazada individualmente.
()¿El primer nodo del nodo de la tabla? abcd? () ¿Estructura de almacenamiento secuencial? () Estructura de almacenamiento de lista vinculada
[Registro N]
() ¿Recorrido de raíz primero? ()Atravesar después de la raíz
()¿Función hash? ()Conflicto
() Determina el bloque en el que se encuentra el elemento a verificar () Encuentra el elemento a verificar en el bloque.
Estructura lógica del cubo
()? ()Estructura física
()¿Orden? ()¿Clasificación directa
de burbujas? ¿Combina preguntas de cuatro palabras (cada pregunta vale * * * puntos)? Implementación secuencial
const maxsize:; =; {capacidad de la tabla de secuencia}? Escriba tipo de datos = registro {tipo de datos de archivo}
nombre: cadena『cadena』; {nombre}
Número: entero {número de estudiante}
Género; ∶Booleano; {género}
Edad: entero; {edad}
Fin;
Tipo slist = registro
Tipo de datos Datos : Matriz [maxsize]
último: entero;
Fin;
Implementación del enlace
Tipo puntero = ↑ nodo;
p>
Nodo = registro
nombre: cadena『cadena』; {nombre}
Número: entero {número de estudiante}
Género: booleano; {Género}
Edad: entero; {Edad}
siguiente: puntero; {Puntero posterior del nodo}
Fin;
list = pointer;
El árbol de Huffman es
El código de Huffman correspondiente es
Respuesta:? b:? do:? d:? e:
Dibuje el árbol de Huffman correcto y escriba el código de Huffman correspondiente.
Secuencia inicial desordenada
{ } { } { } { } { } { } { }{ } { }{ }
Primera fusión{ } {} ? { }?{ }
¿Segunda fusión? { } { ?}?{ }
La tercera fusión{? }?{ }
La cuarta fusión{}
Cinco preguntas de diseño (cada pequeña pregunta * * * puntos)
Inserción de proceso (puntero ∶ trasero VAR; data⊙= x;
Si (rear = nil) entonces {la cola circular está vacía, el nuevo nodo es el primer nodo de la cola}
Inicio
Trasero: ⊙= tmp;
Trasero ↑Siguiente≑= tmp;
Fin
De lo contrario {la cola no está vacía. Insertar un nuevo nodo al final de la cola}
Inicio
Head≑=Atrás ↑Siguiente;
Atrás ↑Siguiente≑= tmp;
Trasero: ⊙= tmp;
Trasero ↑next≑=head;
Fin
Fin;
Programa dfs (g: lista de ajuste; v: número entero);
{Gráfico transversal en profundidad G desde V}
Inicio
Escribir (5); p>
p>
Visitado(v)∴= verdadero;? {bandera visitada v}
p = g〔v〕link;? {Encontrar el primer punto adyacente de V}
Y p lt gt no
[Si no (visitó el vértice [p]]
entonces dfs (g p ↑ vértice);
p:= p = next {Encontrar el siguiente punto adyacente de V}
Fin;
Usar lista de adyacencia como almacenamiento Primero en profundidad La búsqueda de un gráfico conectado de una estructura es una búsqueda secuencial de una lista enlazada.
El proceso de construcción es el siguiente
H( )= MOD =
H( )= MOD =
H( )= MOD =
H( )= MOD =(conflicto)
H( )=( ) MOD =
H( )= MOD =
H( )= MOD =
H( )= MOD =(conflicto)
H( )=( ) MOD =(aún conflicto)
H( )=( ) MOD =
H( )= MOD =(conflicto)
H( )=( ) MOD =(conflicto)
H( ) =( ) MOD =(aún en conflicto)
H( )=( ) MOD =
H( )= MOD =(en conflicto)
H( ) =( ) MOD =(aún en conflicto)
H( )=( ) MOD =
H( )= MOD =
H( ) = MOD = (conflicto)
H( )=( ) MOD =(aún conflicto)
H( )=( ) MOD =
H( ) = MOD = (Conflicto)
H( )=( ) MOD =
Por lo tanto, la dirección correspondiente a cada palabra clave se asigna de la siguiente manera
Dirección () =
Dirección()=
Dirección()=
Dirección()=
Dirección()=
Dirección()=
Dirección()=
Dirección()=
Dirección()=
Dirección()=
Dirección()=
Dirección()=
Lishi Xinzhi/Article/program/sjjg/201404/30585