Documento sulla Struttura Dati (1)
1. Domande a scelta multipla (2 punti per domanda, 20 punti in totale)
1. Le caratteristiche comuni degli stack e delle code sono ( ).
A. Consentire solo l'inserimento e la cancellazione di elementi all'endpoint
B. Tutti primi in entrata, ultimi eliminati
C. È tutto primo in entrata, primo in uscita
D. Non c'è un terreno comune
2. La coda memorizzata in modo collegato viene inserita durante l'operazione di inserimento ( ).
A. Solo il puntatore di testa è modificato B. Gli puntatori di testa e coda devono essere modificati
C. Modificare solo il puntatore di coda D. I puntatori di testa e coda potrebbero dover essere modificati
3. Quale delle seguenti strutture dati è una struttura non lineare? ( )
A. Coda B. Pila C. Tabella lineare D. Albero binario
4. Se esiste un array bidimensionale A[m][n], assumendo che A[0][0] sia memorizzato a 644 (10), e A[2][2] sia memorizzato a 676 (10), ogni elemento occupa uno spazio, dove è memorizzato A[3][3][3](10)? La nota a piè di pagina (10) indica che è espresso in decimale.
A.688 B.678 C.692 D.696
5. Gli alberi sono meglio usati per rappresentare ( ).
A. Elementi dati ordinati B. Elementi dati non ordinati
C. Dati con relazioni gerarchiche ramificate tra elementi D. Dati senza connessione tra elementi
6. Il numero massimo di nodi nel k-esimo strato dell'albero binario è ( ).
A.2k-1 B.2K+1 C.2K-1 D. 2k-1
7. Se esiste una tabella ordinata di 18 elementi memorizzati in un array unidimensionale A[19], il primo elemento viene posizionato in A[1], e ora viene effettuata una ricerca binaria, allora il pedice della sequenza di confronto per trovare A[3] è ( )
A. 1,2,3 B. 9,5,2,3
C. 9,5,3 D. 9,4,2,3
8. Ordinare rapidamente i file di n record e lo spazio di archiviazione ausiliario richiesto è più o meno lo stesso
A. O(1) B. O(n) C. O(1og2n) D. O(n2)
9. Per le tabelle lineari (7, 34, 55, 25, 64, 46, 20, 10) per l'archiviazione hash, se H(K)=K%9 viene selezionato come funzione hash, ci sono elementi ( ) con indirizzo hash pari a 1.
A.1 B.2 C.3 D.4
10. Un grafo non orientato con 6 nodi, e il grafo dovrebbe avere almeno ( ) spigoli per garantire un grafo connesso.
A.5 B.6 C.7 D.8
2. Compilare i vuoti (1 punto per ogni blank, 26 punti in totale)
1. La qualità dell'algoritmo viene solitamente valutata da quattro aspetti: _________, _________, _________ e _________.
2. La complessità temporale di un algoritmo è (n3+n2log2n+14n)/n2, e il suo ordine di grandezza è espresso come ________.
3. Assumendo che la tabella generalizzata di un albero sia rappresentata come A(C,D(E,F,G),H(I,J)), allora il numero di nodi contenuti nell'albero è __________, la profondità dell'albero è ___________ e il grado dell'albero è _________.
4. Il valore della formula del suffisso 9 2 3 +- 10 2 / - è __________. La formula del suffisso corrispondente alla formula centrale (3+4X)-2Y/3 è _______________________________.
5. Se un albero binario è memorizzato con una lista collegata, ogni nodo ha due puntatori al figlio sinistro e al figlio destro oltre al campo dati. In questa struttura di archiviazione, l'albero binario con n nodi ha un totale di ________ campi puntatori, dei quali ________ campi puntatori memorizzano indirizzi e ________________ puntatori sono puntatori vuoti.
6. Per un grafo orientato e un grafo non orientato con n vertici e archi a barra E, ci sono rispettivamente _______ e ________ nodi di spigoli nella sua tabella di adiacenza corrispondente.
7. La rete AOV è un grafo ___________________.
8. In un grafo completo non orientato con n vertici, ci sono ________ archi, e in un grafo completo orientato con n vertici, ci sono ________ archi.
9. Assumendo che una tabella lineare sia (12,23,74,55,63,40), se gli elementi dello stesso resto diventano una sottotabella secondo la condizione Key % 4, le quattro sottotabelle ottenute sono ____________________________, ___________________, _______________________ e __________________________.
10. Nel processo di inserimento degli elementi in un albero B_, se il nodo radice dell'albero viene finalmente diviso, l'altezza del nuovo albero è ___________ rispetto a quella dell'albero originale.
11. Nel processo di ordinamento degli heap, la complessità temporale per setacciare qualsiasi nodo di ramo è ________, e la complessità temporale dell'intero processo di ordinamento degli heap è ________.
12. Nell'ordinamento rapido, nell'ordinamento a cumuli e nell'ordinamento da fusione, _________ l'ordinamento è stabile.
Documento sulla struttura dati (2)
1. Domande a scelta multipla (24 punti)
1. La seguente descrizione delle tabelle lineari è errata ().
(A) Le tabelle lineari sono memorizzate in sequenza e devono occupare uno spazio di archiviazione contiguo
(B) Le tavole lineari sono concatenate e non occupano uno spazio di archiviazione continuo
(C) Le tabelle lineari sono implementate con storage concatenato per facilitare le operazioni di inserimento e cancellazione
(d) Le tabelle lineari sono implementate con memoria sequenziale per facilitare operazioni di inserimento e cancellazione
2. Supponiamo che il numero totale di nodi foglia nell'albero di Huffman sia m, e se viene usata una lista binaria collegata come struttura di archiviazione, ci sono in totale ( ) campi puntatori vuoti nell'albero di Huffman.
(A) 2m-1 (B)2m (C)2m+1 (D)4m
3. Se i puntatori testa e coda della coda a loop sequenziale Q[0:M-1] sono rispettivamente F e R, il puntatore testa F punta sempre alla posizione precedente dell'elemento testa, e il puntatore di coda R punta sempre alla posizione attuale dell'elemento di coda, allora il numero di elementi nella coda loop è ( ).
(A) R-F (B) F-R (C) (R-F+M)%M (D) (F-R+M)%M
4. Se la sequenza di attraversamento di ordine medio di un albero binario è ABCD e la sequenza precedente è CABD, allora la sequenza ottenuta attraversando l'albero binario nell'ordine successivo è ().
(A) BADC (B)BCDA (C) CDAB (D) CBDA
5. Supponiamo che ci siano n vertici in un grafo completamente non orientato, allora ci sono ( ) archi nel grafo completamente non orientato.
(A) n(n-1)/2 (B) n(n-1) (C) n2 (D) n2-1
6. Supponiamo che ci siano 2000 nodi in un albero binario, allora l'altezza minima dell'albero binario è ( ).
(A) 9 (B) 10 (C) 11 (D) 12
7. Supponiamo che ci siano n vertici in un grafo diretto, allora ci sono ( ) nodi header nella tabella di adiacenza corrispondenti al grafo diretto.
(A) n-1 (B) n (C) n+1 (D) 2n-1
8. Impostare un insieme di sequenze di parole chiave iniziali di record (5, 2, 6, 3, 8), e il risultato di un ordinamento rapido basato sulla prima parola chiave di record 5 è ( ).
(A) 2,3,5,8,6 (B) 3,2,5,8,6
(C) 3,2,5,6,8 (D) 2,3,6,5,8
2. Compila gli spazi vuoti (24 punti)
1. Per applicare efficacemente la tecnologia di ricerca HASH, due problemi che devono essere risolti sono ____________________ e __________________________.
2. La funzione del segmento di programma successivo realizza i dati x nello stack e richiede che l'istruzione corretta venga riempita sotto sottoline.
typedefstruct {int s[100]; int top; } stack quadrato;
Vuoto Push(sqstack&stack,int x)
{
if (stack.top==m-1) printf("overflow");
altrimenti {____________________; _________________; }
}
3. La sequenza ottenuta attraversando l'albero binario di ordinamento nell'ordine intermedio è una sequenza ___________ (completata ordinata o non ordinata).
4. La peggiore complessità temporale dell'ordinamento rapido è ___________, e la complessità temporale media è __________.
5. Se il numero di nodi con grado 0 in un albero binario è N0 e il numero di nodo con grado 1 è N1, allora il numero di nodi con grado 2 nell'albero binario è _________; Se una lista binaria collegata viene utilizzata come struttura di archiviazione dell'albero binario, ci sono _______ campi puntatori vuoti nell'albero binario.
6. Supponiamo che il numero di vertici e archi in un certo grafo non orientato sia rispettivamente n ed e, e la somma dei gradi di tutti i vertici sia d, allora e = _______.
7. Se la sequenza iniziale delle parole chiave del record è (55, 63, 44, 38, 75, 80, 31, 56), allora l'heap iniziale stabilito dal metodo di screening è ___________________________.
8. È noto che la struttura di archiviazione della tabella di adiacenza di un grafo diretto è la seguente: Dal vertice 1, la sequenza di uscita del percorso-DFS è:
, la sequenza di uscita del percorso-de-scorrimento BFS è
Articolo sulla struttura dati (3)
1. Domande a scelta multipla (1 punto per domanda, 20 punti in totale)
1. Se la forma binaria di una struttura dati è espressa come A=(D,R),D={01,02,03,04,05,06,07,08,09}, R={r},r={<01,02>,<01,03>,<01,04>,<02,05>,<02,06>,<03,07>,<03,08>,<03,09>}, allora la struttura dati A è ( ).
(A) Struttura lineare (B) Struttura ad albero (C) Struttura fisica (D) Struttura grafica
2. Il complesso temporale del seguente programma è ()
per (i=1,s=0; i<=n; i++) {t=1;for(j=1;j<=i; j++) t=t*j; s=s+t; }
(A) O(n) (B) O(n2) (C) O(n3) (D) O(n4)
3. Imposta la variabile puntatore p per puntare al nodo A in una singola lista collegata; se elimini il nodo A in una singola lista collegata, devi cambiare la sequenza operativa del puntatore a ().
(A) q=p->successivo; p->data=q->data; p->successivo=q->successivo; libero(q);
(B) q=p->il prossimo; q->data=p->data; p->successivo=q->successivo; libero(q);
(C) q=p->successivo; p->successivo=q->successivo; libero(q);
(D) q=p->il prossimo; p->data=q->data; libero(q);
4. Se ci sono n parole chiave di record da ordinare, ( ) sono necessarie unità di record ausiliarie nell'ordinamento del heap.
(A) 1 (B) n (C) nlog2n (D) n2
5. Se le parole chiave iniziali registrate sono (20, 15, 14, 18, 21, 36, 40, 10), allora il risultato dopo la fine di un quick sort registrato con 20 come benchmark è ( ).
(A) 10,15,14,18,20,36,40,21
(B) 10,15,14,18,20,40,36,21
(C) 10,15,14,20,18,40,36,2l
(D) 15,10,14,18,20,36,40,21
6. Supponiamo che ci siano n nodi nell'albero di ordinamento binario, allora la lunghezza media della ricerca nell'albero di ordinamento binario è ( ).
(A) O(1) (B) O(log2n) (C) (D) O(n2)
7. Supponiamo che ci siano n spigoli di vertice e nel grafo non orientato G, allora il numero di nodi header e nodi della tabella nella tabella di adiacenza corrispondente è ( ).
(A) n,e (B) e,n (C) 2n,e (D) n,2e
8. Supponiamo che ci siano n vertici in un grafo di connessione forte, allora ci sono almeno ( ) archi nel grafo di connessione forte.
(A) n(n-1) (B) n+1 (C) n (D) n(n+1)
9. Ci sono 5000 parole chiave di record da ordinare; se devi usare il metodo più veloce per selezionare le parole chiave più piccole di 10 record, puoi usare il seguente metodo ( ) per raggiungere questo scopo.
(A) Ordinamento rapido (B) Ordinamento heap (C) Ordinamento di fusione (D) Inserimento di ordinamento
10. I seguenti quattro tipi di ( ) hanno la maggiore complessità spaziale.
(A) Ordinamento tramite inserzione (B) Ordinamento a bubble (C) Ordinamento heap (D) Ordinamento tramite fusione
2. Compilare gli spazi vuoti (1 punto per ogni spazio, 20 punti in totale)
1. La struttura fisica dei dati comprende principalmente due situazioni: _____________ e ______________.
2. Se ci sono 500 nodi in un albero binario completo, la profondità dell'albero binario è __________; Se usi una lista binaria collegata come struttura di archiviazione per l'albero completamente binario, ci sono ___________ campi puntatori vuoti.
3. Se la sequenza di input è 1, 2, 3, allora ___________ sequenze di output diverse possono essere ottenute dopo l'azione dello stack.
4. Se la matrice di adiacenza A[n][n] è usata come struttura di archiviazione per il grafo G, allora la somma di tutti gli elementi sulla riga i nella matrice di adiacenza è uguale al ________ del vertice i, e la somma di tutti gli elementi sulla colonna i è uguale al ________ del vertice i.
5. Se ci sono n nodi nell'albero di Huffman, ci sono ________ nodi con grado 1 nell'albero di Huffman.
6. Se ci sono n vertici e nel grafo direzionale G con archi direzionali, e la somma di tutti i vertici che entrano in grado è d, allora la relazione tra e d è _________.
7. __________ attraversando i nodi nell'albero binario di ordinamento può ottenere una sequenza incrementale di parole chiave (riempito, centrale o posteriore).
8. Se ci sono 100 elementi nella tabella di ricerca, se usi il metodo di ricerca dicotomica per trovare l'elemento dati X, devi confrontarlo fino a ________ volte per determinare se l'elemento dati X è presente nella tabella di ricerca.
9. Che si tratti di uno stack con una struttura di storage sequenziale o di uno stack con una struttura di storage a catena, la complessità temporale delle operazioni in-stack e out-stack è ____________.
10. Un albero binario completo con n nodi, se numerati dall'alto verso il basso e da sinistra a destra partendo da 1, il nodo genitore dell'i-esimo nodo è numerato ____________, e il numero del nodo figlio destro è ___________.
11. Se il set iniziale di parole chiave registrate è (72, 73, 71, 23, 94, 16, 5), allora il risultato di un ordinamento rapido basato sulla parola chiave record 72 è ___________________________.
12. Se esiste un insieme di archi diretti nel grafo direzionale G E={<1,2>,<2,3>,<1,4>,<4,2>,<4,3>}, allora una sequenza topologica del grafo è ____________________.
13. Il seguente algoritmo implementa la parola chiave con valore x nella lista di hash sequenziali, si prega di compilare l'istruzione corretta nel sottolineo.
struct record{int key; in altri; };
inthashsqsearch(struct record hashtable[ ],int k)
{
inti,j; j=i=k % p;
mentre (hashtable[j].key!=k&&hashtable[j].flag!=0){j=(____) %m; se (i==j) return(-1); }
se (_______________________ ) ritorno (j); altrimenti return(-1);
}
14. Il seguente algoritmo implementa il valore chiave k nell'albero binario di ordinamento, si prega di compilare l'istruzione corretta nel sottolineamento.
typedefstruct node{int key; nodo struct *lchild; nodo struct *rchild; }bitree;
bitree *bstsearch(bitree *t, int k)
{
se (t==0) ritorna(0); altrimenti mentre (t!=0)
se (t->key==k)_____________; altrimenti se (t->key>k) t=t->lchild; else_____________;
}
Prova di test sulla struttura dati (1) Riferisci la risposta
1. Domande a scelta multipla (2 punti per domanda, 20 punti in totale)
1.A 2.D 3.D 4.C 5.C 6.D 7.D 8.C 9.D 10.A
2. Compilare i vuoti (1 punto per ogni blank, 26 punti in totale)
1. Correttezza, leggibilità, resistenza ed alta efficienza
2.O(n)
3.9 3 3
4.-1 3 4 X * + 2 Y * 3 / -
5.2n n-1 n+1
6.e 2e
7. Direzionale e non circuituale
8.n(n-1)/2 n(n-1)
9.（12，40） （ ） （74） （23,55，63）
10. Aggiungi 1
11.O(log2n) O(nlog2n)
12. Consolidamento
Le risposte ad altre domande del test si possono vedere:
Turisti, se volete vedere il contenuto nascosto di questo post, vi prego Risposta
|
Pubblicato su 25/11/2014 12:46:30
|
|
|
Pubblicato su 30/12/2014 00:10:55
|
