Preguntas de prueba de algoritmo y estructura de datos, puntuaciones altas, responda
3? Dado un árbol binario no vacío, los resultados de atravesar la primera raíz y la raíz media son:
La primera raíz: ABCDEFGHI?
La raíz media :CBEDAGFHI
Construye este árbol binario.
Respuesta:? A / \
B F / \?/ \? C D?
/ \
I? /p>
4. Analice el tiempo de ejecución de los siguientes programas:
A)? void?(int n)
{int? for( i=1； ilt；n； i ) for(j=i 1； jlt；=n； j ) for(k=1； klt；=j； k )
{¿alguna declaración? ? requiriendo ? O(1)? tiempo;}
}
Mi respuesta es n3 pero no estoy seguro
B) podd(int? n) {int? I, j, x, y;
for(I=1; Ilt;=n; I) if( impar(I)) {for(j=I; jlt;= n; j )
x=x 1; para(j=1; jlt;=I; j ) y=y }
}
n2 también ¿No estás seguro?
5? Se sabe que la expresión matemática es (3 b)sin(x 5)—a/x2. Encuentra la representación del prefijo y el sufijo de esta expresión en notación polaca (obligatorio). para dar proceso).
El árbol binario correspondiente a la expresión es
Entonces el prefijo correspondiente es: -* 3bsin x5/a*xx
El sufijo es: 3b x5 sin *axx* /-
Tres implementan el siguiente algoritmo
En la lista lineal L implementada por punteros, elimina el nodo con la clave x en la lista lineal L.
Respuesta:
int visitado[n];?
void dfs(Graph g, int i)
{edgeNode *t ;
printf(“4d”,i);?
visitado[i]=1;?
t=g[i];? p>
mientras(t!=NULL) {
si (visita[t-gt;vno]= =0)?
dfs(g,t- gt; vno);
t=t-gt;next;
}
}
En el árbol binario de pistas, el El nodo Punto P encuentra el sucesor de la secuencia raíz.
Respuesta:
typedef enum {lLINK, THREAD} PointerTag;? // LINK==0; puntero,
THREAD==1; /p>
typedef struct BinThrNode {?
TElemType data;?
struct BinThrNode *lchilid, *rchild PointerTag ltag, rtag;
} ? BinThrNode, * BinThrTree;?
Recorrido en orden del árbol binario de pistas
¿Cómo encontrar el predecesor del nodo señalado por p:?
Cuando p-gt; ltag= =THREAD, el predecesor es p-gt;lchild;?
Cuando p-gt;ltag==LINK, el predecesor es el nodo inferior derecho de p-gt; niño.
En el árbol de búsqueda binaria F, inserte el registro R.
Respuesta:
Void INSERT(registros R, BST y F)
{if(F= =NULL) {F=nuevo tipo de celda;
p>
F-gt; datos=R; lchild=NULL;
F-gt=NULL; if(R, keylt ;F-gt;data.key) INSERT(R,F-gt;lchild);
else if(R,keygt;F-gt;data.key)
INSERT (R, F-gt; rchild);
}
4. Para el siguiente gráfico no dirigido conectado ponderado, utilice el algoritmo de Prim para construir un árbol de expansión mínimo. Dibuja cada paso del proceso de construcción. (12 puntos)
Supongamos que los datos a clasificar se almacenan en la matriz A
3 1 4 1 5 9 2 6 5 3
Necesita ser acumulado Para clasificar, primero debe construir un montón inicial para ello. Intente dibujar los cambios en el árbol binario y los cambios en la matriz A durante el proceso de construcción del montón inicial.