Έγγραφο Δομής Δεδομένων (1)
1. Ερωτήσεις πολλαπλής επιλογής (2 βαθμοί ανά ερώτηση, 20 βαθμοί συνολικά)
1. Τα κοινά χαρακτηριστικά των στοίβων και των ουρών είναι ( ).
Α. Να επιτρέπεται μόνο η εισαγωγή και η διαγραφή στοιχείων στο τελικό σημείο
Β. Όλα τα πρώτα μέσα, τελευταία έξω
Γ. Είναι όλα πρώτα μέσα, πρώτα έξω
Δ. Δεν υπάρχει κοινό έδαφος
2. Η ουρά που είναι αποθηκευμένη με συνδεδεμένο τρόπο εισάγεται κατά την εκτέλεση της λειτουργίας εισαγωγής ( ).
Α. Μόνο ο δείκτης κεφαλής τροποποιείται Β. Οι δείκτες κεφαλής και ουράς πρέπει να τροποποιηθούν
Γ. Τροποποιήστε μόνο τον δείκτη της ουράς Δ. Οι δείκτες της κεφαλής και της ουράς μπορεί να χρειαστεί να τροποποιηθούν
3. Ποια από τις παρακάτω δομές δεδομένων είναι μη γραμμική δομή; ( )
Α. Ουρά Β. Στοίβα Γ. Γραμμικός πίνακας Δ. Δυαδικό δέντρο
4. Εάν υπάρχει ένας δισδιάστατος πίνακας A[m][n], υποθέτοντας ότι το A[0][0] αποθηκεύεται στο 644 (10) και το A[2][2] αποθηκεύεται στο 676 (10), κάθε στοιχείο καταλαμβάνει ένα χώρο, όπου αποθηκεύεται το A[3][3][3](10); Η υποσημείωση 10 δείχνει ότι εκφράζεται σε δεκαδικό ψηφίο.
Α.688 Β.678 Γ.692 Δ.696
5. Τα δέντρα χρησιμοποιούνται καλύτερα για να αναπαραστήσουν το ( ).
Α. Διατεταγμένα στοιχεία δεδομένων Β. Μη ταξινομημένα στοιχεία δεδομένων
Γ. Δεδομένα με διακλαδιζόμενες ιεραρχικές σχέσεις μεταξύ στοιχείων Δ. Δεδομένα χωρίς σύνδεση μεταξύ στοιχείων
6. Ο μέγιστος αριθμός κόμβων στο kο στρώμα του δυαδικού δέντρου είναι ( ).
Α.2Κ-1 Β.2Κ+1 Γ.2Κ-1 Δ. 2Κ-1
7. Εάν υπάρχει ένας διατεταγμένος πίνακας 18 στοιχείων αποθηκευμένων σε έναν μονοδιάστατο πίνακα A[19], το πρώτο στοιχείο τοποθετείται στο A[1] και τώρα εκτελείται μια δυαδική αναζήτηση, τότε ο δείκτης της ακολουθίας σύγκρισης για την εύρεση του A[3] είναι ( )
Α. 1,2,3 Β. 9,5,2,3
Γ. 9,5,3 Δ. 9,4,2,3
8. Ταξινομήστε γρήγορα τα αρχεία n εγγραφών και ο βοηθητικός χώρος αποθήκευσης που απαιτείται είναι περίπου ο ίδιος
Α. Ο(1) Β. Ο(ν) Γ. Ο(1og2n) Δ. Ο(n2)
9. Για γραμμικούς πίνακες (7, 34, 55, 25, 64, 46, 20, 10) για αποθήκευση κατακερματισμού, εάν έχει επιλεγεί H(K)=K %9 ως συνάρτηση κατακερματισμού, υπάρχουν στοιχεία ( ) με διεύθυνση κατακερματισμού 1.
Α.1 Β.2 Γ.3 Δ.4
10. Ένα μη κατευθυνόμενο γράφημα με 6 κόμβους και το γράφημα πρέπει να έχει τουλάχιστον ( ) ακμές για να εξασφαλίσει ένα συνδεδεμένο γράφημα.
Α.5 Β.6 Γ.7 Δ.8
2. Συμπληρώστε τα κενά (1 βαθμός ανά κενό, 26 βαθμοί συνολικά)
1. Η ποιότητα του αλγορίθμου αξιολογείται συνήθως από τέσσερις πτυχές: _________, _________, _________ και _________.
2. Η χρονική πολυπλοκότητα ενός αλγορίθμου είναι (n3+n2log2n+14n)/n2 και η τάξη μεγέθους του εκφράζεται ως ________.
3. Υποθέτοντας ότι ο γενικευμένος πίνακας ενός δέντρου αναπαρίσταται ως A(C,D(E,F,G),H(I,J)), τότε ο αριθμός των κόμβων που περιέχονται στο δέντρο είναι __________, το βάθος του δέντρου είναι ___________ και ο βαθμός του δέντρου είναι _________.
4. Η τιμή του τύπου επιθήματος 9 2 3 +- 10 2 / - είναι __________. Ο τύπος επιθήματος που αντιστοιχεί στον μεσαίο τύπο (3+4X)-2Y/3 είναι _______________________________.
5. Εάν ένα δυαδικό δέντρο είναι αποθηκευμένο με μια συνδεδεμένη λίστα, κάθε κόμβος έχει δύο δείκτες προς το αριστερό παιδί και το δεξί παιδί εκτός από το πεδίο δεδομένων. Σε αυτή τη δομή αποθήκευσης, το δυαδικό δέντρο με n κόμβους έχει συνολικά ________ πεδία δείκτη, εκ των οποίων ________ πεδία δείκτη αποθηκεύουν διευθύνσεις και ________________ δείκτες είναι κενοί δείκτες.
6. Για ένα κατευθυνόμενο γράφημα και ένα μη κατευθυνόμενο γράφημα με n κορυφές και ακμές E-bar, υπάρχουν κόμβοι ακμής _______ και ________ στον αντίστοιχο πίνακα γειτνίασης, αντίστοιχα.
7. Το δίκτυο AOV είναι ένα ___________________ γράφημα.
8. Σε ένα μη κατευθυνόμενο πλήρες γράφημα με n κορυφές, υπάρχουν ________ ακμές και σε ένα κατευθυνόμενο πλήρες γράφημα με n κορυφές, υπάρχουν ________ ακμές.
9. Υποθέτοντας ότι ένας γραμμικός πίνακας είναι (12,23,74,55,63,40), εάν τα στοιχεία του ίδιου υπολοίπου γίνουν υποπίνακας σύμφωνα με τη συνθήκη Key % 4, οι τέσσερις υποπίνακες που λαμβάνονται είναι ____________________________, ___________________, _______________________ και __________________________.
10. Κατά τη διαδικασία εισαγωγής στοιχείων σε ένα B_ δέντρο, εάν τελικά χωριστεί ο ριζικός κόμβος του δέντρου, το ύψος του νέου δέντρου είναι ___________ από αυτό του αρχικού δέντρου.
11. Στη διαδικασία ταξινόμησης σωρού, η χρονική πολυπλοκότητα του κοσκινίσματος οποιουδήποτε κόμβου διακλάδωσης είναι ________ και η χρονική πολυπλοκότητα ολόκληρης της διαδικασίας ταξινόμησης σωρού είναι ________.
12. Στη γρήγορη ταξινόμηση, τη διαλογή σωρού και τη συγχώνευση, _________ ταξινόμηση είναι σταθερή.
Έγγραφο δομής δεδομένων (2)
1. Ερωτήσεις πολλαπλής επιλογής (24 βαθμοί)
1. Η ακόλουθη περιγραφή των γραμμικών πινάκων είναι λανθασμένη ().
(Α) Οι γραμμικοί πίνακες αποθηκεύονται διαδοχικά και πρέπει να καταλαμβάνουν ένα συνεχόμενο κομμάτι αποθηκευτικού χώρου
(Β) Τα γραμμικά τραπέζια είναι αλυσιδωτά και δεν καταλαμβάνουν συνεχή αποθηκευτικό χώρο
(Γ) Οι γραμμικοί πίνακες υλοποιούνται με αλυσιδωτή αποθήκευση για τη διευκόλυνση των λειτουργιών εισαγωγής και διαγραφής
(δ) Οι γραμμικοί πίνακες υλοποιούνται με διαδοχική αποθήκευση για τη διευκόλυνση των λειτουργιών εισαγωγής και διαγραφής
2. Ας υποθέσουμε ότι ο συνολικός αριθμός των κόμβων φύλλων στο δέντρο Huffman είναι m και εάν χρησιμοποιείται μια δυαδική συνδεδεμένη λίστα ως δομή αποθήκευσης, υπάρχουν συνολικά ( ) κενά πεδία δείκτη στο δέντρο Huffman.
(Α) 2μ-1 (Β)2μ (Γ)2μ+1 (Δ)4μ
3. Εάν οι δείκτες κεφαλής και ουράς της ουράς διαδοχικού βρόχου Q[0:M-1] είναι F και R αντίστοιχα, ο δείκτης κεφαλής F δείχνει πάντα την προηγούμενη θέση του στοιχείου κεφαλής και ο δείκτης ουράς R δείχνει πάντα την τρέχουσα θέση του στοιχείου ουράς, τότε ο αριθμός των στοιχείων στην ουρά βρόχου είναι ( ).
(Α) Ρ-Φ (Β) Φ-Ρ (Γ) (Ρ-Φ+Μ)%Μ (Δ) (Φ-Ρ+Μ)%Μ
4. Εάν η ακολουθία διέλευσης μεσαίας τάξης ενός δυαδικού δέντρου είναι ABCD και η προηγούμενη ακολουθία διέλευσης αλληλουχίας είναι CABD, τότε η ακολουθία που προκύπτει από τη διέλευση του δυαδικού δέντρου με την επόμενη σειρά είναι ().
(Α) BADC (Β) BCDA (Γ) CDAB (Δ) CBDA
5. Ας υποθέσουμε ότι υπάρχουν n κορυφές σε ένα εντελώς μη κατευθυνόμενο γράφημα, τότε υπάρχουν ( ) ακμές στο εντελώς μη κατευθυνόμενο γράφημα.
(Α) n(n-1)/2 (B) n(n-1) (C) n2 (D) n2-1
6. Ας υποθέσουμε ότι υπάρχουν 2000 κόμβοι σε ένα δυαδικό δέντρο, τότε το ελάχιστο ύψος του δυαδικού δέντρου είναι ( ).
(Α) 9 (Β) 10 (Γ) 11 (Δ) 12
7. Ας υποθέσουμε ότι υπάρχουν n κορυφές σε ένα κατευθυνόμενο γράφημα, τότε υπάρχουν ( ) κόμβοι κεφαλίδας στον πίνακα γειτνίασης που αντιστοιχούν στο κατευθυνόμενο γράφημα.
(Α) ν-1 (Β) ν (Γ) ν+1 (Δ) 2ν-1
8. Ορίστε ένα σύνολο αρχικών ακολουθιών λέξεων-κλειδιών εγγραφής (5, 2, 6, 3, 8) και το αποτέλεσμα μιας γρήγορης ταξινόμησης με βάση την πρώτη λέξη-κλειδί εγγραφής 5 είναι ( ).
(Α) 2,3,5,8,6 (Β) 3,2,5,8,6
γ) 3,2,5,6,8 δ) 2,3,6,5,8
2. Συμπληρώστε τα κενά (24 βαθμοί)
1. Για την αποτελεσματική εφαρμογή της τεχνολογίας αναζήτησης HASH, δύο προβλήματα που πρέπει να επιλυθούν είναι ____________________ και __________________________.
2. Η συνάρτηση του ακόλουθου τμήματος προγράμματος πραγματοποιεί τα δεδομένα x στη στοίβα και απαιτεί τη συμπλήρωση της σωστής δήλωσης στην υπογράμμιση.
typedefstruct {int s[100]; int κορυφή; } sqstack;
void push (sqstack&stack,int x)
{
if (stack.top==m-1) printf("υπερχείλιση");
αλλιώς {____________________; _________________; }
}
3. Η αλληλουχία που προκύπτει διασχίζοντας το δυαδικό δέντρο ταξινόμησης στη μεσαία σειρά είναι μια ___________ ακολουθία (συμπληρωμένη με ή χωρίς σειρά).
4. Η χειρότερη χρονική πολυπλοκότητα της γρήγορης ταξινόμησης είναι ___________ και η μέση χρονική πολυπλοκότητα είναι __________.
5. Εάν ο αριθμός των κόμβων με βαθμό 0 σε ένα δυαδικό δέντρο είναι N0 και ο αριθμός κόμβου με βαθμό 1 είναι N1, τότε ο αριθμός των κόμβων με βαθμό 2 στο δυαδικό δέντρο είναι _________. Εάν μια δυαδική συνδεδεμένη λίστα χρησιμοποιείται ως δομή αποθήκευσης του δυαδικού δέντρου, υπάρχουν _______ κενά πεδία δείκτη στο δυαδικό δέντρο.
6. Ας υποθέσουμε ότι ο αριθμός των κορυφών και των ακμών σε ένα συγκεκριμένο μη κατευθυνόμενο γράφημα είναι n και e, αντίστοιχα, και το άθροισμα των μοιρών όλων των κορυφών είναι d, τότε e = _______.
7. Εάν η αρχική ακολουθία λέξεων-κλειδιών εγγραφής είναι (55, 63, 44, 38, 75, 80, 31, 56), τότε ο αρχικός σωρός που καθορίζεται με τη μέθοδο διαλογής είναι ___________________________.
8. Είναι γνωστό ότι η δομή αποθήκευσης του πίνακα γειτνίασης ενός κατευθυνόμενου γραφήματος είναι η εξής: Από την κορυφή 1, η ακολουθία εξόδου της διέλευσης DFS είναι:
, η ακολουθία εξόδου της διέλευσης BFS είναι
Έγγραφο Δομής Δεδομένων (3)
1. Ερωτήσεις πολλαπλής επιλογής (1 βαθμός ανά ερώτηση, 20 βαθμοί συνολικά)
1. Εάν η δυαδική μορφή μιας δομής δεδομένων εκφράζεται ως 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>}, τότε η δομή δεδομένων Α είναι ( ).
(Α) Γραμμική δομή (Β) Δομή δέντρου (Γ) Φυσική δομή (Δ) Γραφική δομή
2. Το χρονικό σύμπλεγμα του παρακάτω προγράμματος είναι ()
for(i=1,s=0; i<=n; i++) {t=1;for(j=1;j<=i; j++) t=t*j; s=s+t; }
(Α) Ιε(ν) (Β) Ο(ιδ2) (Γ) Ο(ιδ3) (Δ) Ο(ιδ4)
3. Ρυθμίστε τη μεταβλητή δείκτη p ώστε να δείχνει στον κόμβο Α σε μια ενιαία συνδεδεμένη λίστα, εάν διαγράψετε τον κόμβο Α σε μια ενιαία συνδεδεμένη λίστα, πρέπει να αλλάξετε την ακολουθία λειτουργίας του δείκτη σε ().
(Α) q=p->επόμενο; p->δεδομένα=q->δεδομένα; p->επόμενο=q->επόμενο; ελεύθερο(q);
(Β) q=p->επόμενο; q->δεδομένα=p->δεδομένα; p->επόμενο=q->επόμενο; ελεύθερο(q);
(Γ) q=p->επόμενο; p->επόμενο=q->επόμενο; ελεύθερο(q);
(Δ) q=p->επόμενο; p->δεδομένα=q->δεδομένα; ελεύθερο(q);
4. Εάν υπάρχουν n λέξεις-κλειδιά εγγραφής προς ταξινόμηση, ( ) απαιτούνται βοηθητικές μονάδες εγγραφής στην ταξινόμηση σωρού.
(Α) 1 (Β) ν (Γ) nlog2n (D) n2
5. Εάν οι αρχικές λέξεις-κλειδιά εγγραφής λέξεων-κλειδιών είναι (20, 15, 14, 18, 21, 36, 40, 10), τότε το αποτέλεσμα μετά το τέλος μιας γρήγορης ταξινόμησης που καταγράφηκε με σημείο αναφοράς το 20 είναι ( ).
(Α) 10,15,14,18,20,36,40,21
β) 10,15,14,18,20,40,36,21
(Γ) 10,15,14,20,18,40,36,2l
δ) 15,10,14,18,20,36,40,21
6. Ας υποθέσουμε ότι υπάρχουν n κόμβοι στο δέντρο δυαδικής ταξινόμησης, τότε το μέσο μήκος αναζήτησης στο δέντρο δυαδικής ταξινόμησης είναι ( ).
α) Ιε(1) (Β) Ο(log2n) (Γ) (Δ) Ο(ν2)
7. Ας υποθέσουμε ότι υπάρχουν n ακμές κορυφής e στο μη κατευθυνόμενο γράφημα G, τότε ο αριθμός των κόμβων κεφαλίδας και των κόμβων πίνακα στον αντίστοιχο πίνακα γειτνίασης είναι ( ).
(Α) n,e (B) e,n (C) 2n,e (D) n,2e
8. Ας υποθέσουμε ότι υπάρχουν n κορυφές σε ένα γράφημα ισχυρής σύνδεσης, τότε υπάρχουν τουλάχιστον ( ) ακμές στο γράφημα ισχυρής σύνδεσης.
(Α) n(n-1) (Β) ν+1 (Γ) ν (Δ) ν(ν+1)
9. Υπάρχουν 5000 λέξεις-κλειδιά εγγραφής προς ταξινόμηση, εάν πρέπει να χρησιμοποιήσετε την ταχύτερη μέθοδο για να επιλέξετε τις μικρότερες 10 λέξεις-κλειδιά εγγραφής, μπορείτε να χρησιμοποιήσετε την ακόλουθη μέθοδο ( ) για να επιτύχετε αυτόν τον σκοπό.
(Α) Γρήγορη ταξινόμηση (Β) Ταξινόμηση σωρού (Γ) Ταξινόμηση συγχώνευσης (Δ) Εισαγωγή ταξινόμησης
10. Τα ακόλουθα τέσσερα είδη ( ) έχουν τη μεγαλύτερη χωρική πολυπλοκότητα.
(Α) Ταξινόμηση εισαγωγής (Β) Ταξινόμηση με φυσαλίδες (Γ) Ταξινόμηση σωρού (Δ) Ταξινόμηση συγχώνευσης
2. Συμπληρώστε τα κενά (1 βαθμός ανά κενό, 20 βαθμοί συνολικά)
1. Η φυσική δομή των δεδομένων περιλαμβάνει κυρίως δύο καταστάσεις: _____________ και ______________.
2. Εάν υπάρχουν 500 κόμβοι σε ένα πλήρες δυαδικό δέντρο, το βάθος του δυαδικού δέντρου είναι __________. Εάν χρησιμοποιείτε μια δυαδική συνδεδεμένη λίστα ως δομή αποθήκευσης για το πλήρως δυαδικό δέντρο, υπάρχουν ___________ κενά πεδία δείκτη.
3. Εάν η ακολουθία εισόδου είναι 1, 2, 3, τότε μπορούν να ληφθούν ___________ διαφορετικές ακολουθίες εξόδου μετά τη δράση της στοίβας.
4. Εάν ο πίνακας γειτνίασης A[n][n] χρησιμοποιείται ως δομή αποθήκευσης για το γράφημα G, τότε το άθροισμα όλων των στοιχείων στη σειρά i στον πίνακα γειτνίασης είναι ίσο με το ________ της κορυφής i και το άθροισμα όλων των στοιχείων στη στήλη i είναι ίσο με το ________ της κορυφής i.
5. Εάν υπάρχουν n κόμβοι στο δέντρο Huffman, υπάρχουν ________ κόμβοι με βαθμό 1 στο δέντρο Huffman.
6. Εάν υπάρχουν n κορυφές e στο κατευθυντικό γράφημα G με κατευθυντικές ακμές και το άθροισμα όλων των κορυφών που εισέρχονται σε μοίρες είναι d, τότε η σχέση μεταξύ e και d είναι _________.
7. __________ διασχίζοντας τους κόμβους στο δυαδικό δέντρο ταξινόμησης μπορεί να αποκτήσει μια σταδιακή ακολουθία λέξεων-κλειδιών (γεμάτη, μεσαία ή μεταγενέστερη).
8. Εάν υπάρχουν 100 στοιχεία στον πίνακα αναζήτησης, εάν χρησιμοποιείτε τη διχοτομική μέθοδο αναζήτησης για να βρείτε το στοιχείο δεδομένων X, πρέπει να το συγκρίνετε έως και ________ φορές για να προσδιορίσετε εάν το στοιχείο δεδομένων X βρίσκεται στον πίνακα αναζήτησης.
9. Είτε πρόκειται για στοίβα με διαδοχική δομή αποθήκευσης είτε για στοίβα με δομή αποθήκευσης αλυσίδας, η χρονική πολυπλοκότητα των λειτουργιών εντός και εκτός στοίβας είναι ____________.
10. Ένα πλήρες δυαδικό δέντρο με n κόμβους, εάν αριθμηθεί με σειρά από πάνω προς τα κάτω και από αριστερά προς τα δεξιά ξεκινώντας από το 1, ο γονικός κόμβος του i κόμβου αριθμείται ____________ και ο αριθμός του δεξιού θυγατρικού κόμβου είναι ___________.
11. Εάν το αρχικό σύνολο των καταγεγραμμένων λέξεων-κλειδιών είναι (72, 73, 71, 23, 94, 16, 5), τότε το αποτέλεσμα μιας γρήγορης ταξινόμησης με βάση τη λέξη-κλειδί εγγραφής 72 είναι ___________________________.
12. Εάν υπάρχει ένα σύνολο κατευθυνόμενων ακμών στο κατευθυντικό γράφημα G E={<1,2>,<2,3>,<1,4>,<4,2>,<4,3>}, τότε ____________________ μια τοπολογική ακολουθία του γραφήματος.
13. Ο ακόλουθος αλγόριθμος υλοποιεί τη λέξη-κλειδί με την τιμή x στη διαδοχική λίστα κατακερματισμού, συμπληρώστε τη σωστή δήλωση στην υπογράμμιση.
struct record{int key; σε άλλους? };
inthashsqsearch(κατακερματισμός εγγραφής δομής[ ],int k)
{
inti,j; j=i=k % p;
ενώ (hashtable[j].key!=k&&hashtable[j].flag!=0){j=(____) %m; αν (i==j) επιστροφή(-1); }
εάν (_______________________ ) επιστροφή (ι)· else return(-1);
}
14. Ο ακόλουθος αλγόριθμος υλοποιεί την τιμή κλειδιού k στο δυαδικό δέντρο ταξινόμησης, συμπληρώστε τη σωστή δήλωση στην υπογράμμιση.
typedefstruct node{int κλειδί; κόμβος δομής *lchild; κόμβος δομής *rchild; }bitree;
bitree *bstsearch(bitree *t, int k)
{
αν (t==0 ) επιστροφή(0); αλλιώς ενώ (t!=0)
αν (t->key==k)_____________; αλλιώς αν (t->κλειδί>k) t=t->lchild; else_____________;
}
Χαρτί δοκιμής δομής δεδομένων (1) Ανατρέξτε στην απάντηση
1. Ερωτήσεις πολλαπλής επιλογής (2 βαθμοί ανά ερώτηση, 20 βαθμοί συνολικά)
1.Α 2.Δ 3.Δ 4.Γ 5.Γ 6.Δ 7.Δ 8.Γ 9.Δ 10.Α
2. Συμπληρώστε τα κενά (1 βαθμός ανά κενό, 26 βαθμοί συνολικά)
1. Ορθότητα, αναγνωσιμότητα, αντοχή και υψηλή απόδοση
2.Ξ(ν)
3.9 3 3
4.-1 3 4 Χ * + 2 Υ * 3 / -
5.2β ν-1 ν+1
6.ε 2ε
7. Κατευθυντικό και μη κύκλωμα
8.n(n-1)/2 n(n-1)
9.（12，40） （ ） （74） （23,55，63）
10. Προσθέστε 1
11.Ο(log2n) Ο(nlog2n)
12. Ενοποίηση
Μπορείτε να δείτε τις απαντήσεις σε άλλες ερωτήσεις του τεστ:
Τουρίστες, αν θέλετε να δείτε το κρυφό περιεχόμενο αυτής της ανάρτησης, παρακαλώ Απάντηση
|
Δημοσιεύτηκε στις 25/11/2014 12:46:30 μ.μ.
|
|
|
Δημοσιεύτηκε στις 30/12/2014 12:10:55 π.μ.
|
