Makalah Struktur Data (1)
1. Pertanyaan pilihan ganda (2 poin per pertanyaan, total 20 poin)
1. Karakteristik umum tumpukan dan antrian adalah ( ).
A. Hanya izinkan penyisipan dan penghapusan elemen di titik akhir
B. Semua masuk pertama, keluar terakhir
C. Semuanya pertama masuk, pertama keluar
D. Tidak ada kesamaan
2. Antrean yang disimpan dengan cara yang ditautkan dimasukkan saat melakukan operasi penyisipan ( ).
A. Hanya penunjuk kepala yang dimodifikasi B. Penunjuk kepala dan ekor harus dimodifikasi
C. Ubah hanya penunjuk ekor D. Penunjuk kepala dan ekor mungkin perlu dimodifikasi
3. Manakah dari struktur data berikut yang merupakan struktur nonlinier? ( )
A. Antrean B. Tumpukan C. Tabel linier D. Pohon biner
4. Jika ada array dua dimensi A[m][n], dengan asumsi bahwa A[0][0] disimpan pada 644 (10), dan A[2][2] disimpan pada 676 (10), setiap elemen menempati ruang, di mana A[3][3][3](10) disimpan? Catatan kaki (10) menunjukkan bahwa itu dinyatakan dalam desimal.
A.688 B.678 C.692 D.696
5. Pohon paling baik digunakan untuk mewakili ( ).
A. Elemen data yang diurutkan B. Elemen data yang tidak berurutan
C. Data dengan hubungan hierarkis percabangan antar elemen D. Data tanpa koneksi antar elemen
6. Jumlah maksimum node di lapisan ke-k pohon biner adalah ( ).
A.2K-1 B.2K+1 C.2K-1 D. 2K-1
7. Jika ada tabel berurutan dari 18 elemen yang disimpan dalam array satu dimensi A[19], elemen pertama ditempatkan di A[1], dan sekarang pencarian biner dilakukan, maka subskrip dari urutan perbandingan untuk menemukan A[3] adalah ( )
A. 1,2,3 B. 9,5,2,3
C. 9,5,3 D. 9,4,2,3
8. Urutkan file n catatan dengan cepat, dan ruang penyimpanan tambahan yang dibutuhkan kira-kira sama
A. O(1) B. O(n) C. O(1og2n) D. O(n2)
9. Untuk tabel linier (7, 34, 55, 25, 64, 46, 20, 10) untuk penyimpanan hash, jika H(K)=K %9 dipilih sebagai fungsi hash, ada elemen ( ) dengan alamat hash 1.
A.1 B.2 C.3 D.4
10. Grafik tidak terarah dengan 6 node, dan grafik harus memiliki setidaknya ( ) tepi untuk memastikan grafik yang terhubung.
A.5 B.6 C.7 D.8
2. Isi kekosongan (1 poin per kosong, total 26 poin)
1. Kualitas algoritma biasanya dievaluasi dari empat aspek: _________, _________, _________, dan _________.
2. Kompleksitas waktu algoritma adalah (n3+n2log2n+14n)/n2, dan urutan besarnya dinyatakan sebagai ________.
3. Dengan asumsi bahwa tabel umum pohon direpresentasikan sebagai A(C,D(E,F,G),H(I,J)), maka jumlah simpul yang terkandung dalam pohon adalah __________, kedalaman pohon adalah ___________, dan derajat pohon adalah _________.
4. Nilai rumus akhiran 9 2 3 +- 10 2 / - adalah __________. Rumus akhiran yang sesuai dengan rumus tengah (3+4X)-2Y/3 adalah _______________________________.
5. Jika pohon biner disimpan dengan daftar tertaut, setiap simpul memiliki dua penunjuk ke anak kiri dan anak kanan selain bidang data. Dalam struktur penyimpanan ini, pohon biner dengan n simpul memiliki total ________ bidang penunjuk, di mana bidang penunjuk ________ menyimpan alamat dan penunjuk ________________ adalah penunjuk kosong.
6. Untuk grafik terarah dan grafik tidak terarah dengan n simpul dan tepi E-bar, masing-masing ada simpul tepi _______ dan ________ dalam tabel kedekatan yang sesuai.
7. Jaringan AOV adalah grafik ___________________.
8. Dalam grafik lengkap tidak terarah dengan n simpul, ada ________ tepi, dan dalam grafik lengkap terarah dengan n simpul, ada ________ tepi.
9. Dengan asumsi bahwa tabel linier adalah (12,23,74,55,63,40), jika unsur-unsur dari sisa yang sama menjadi subtabel sesuai dengan kondisi Kunci % 4, empat subtabel yang diperoleh adalah ____________________________, ___________________, _______________________ dan __________________________.
10. Dalam proses memasukkan elemen ke dalam pohon B_, jika simpul akar pohon akhirnya terbelah, ketinggian pohon baru ___________ dari pohon asli.
11. Dalam proses penyortiran timbunan, kompleksitas waktu menyaring simpul cabang apa pun ________, dan kompleksitas waktu dari seluruh proses penyortiran tumpukan ________.
12. Dalam penyortiran cepat, penyortiran tumpukan, dan penyortiran gabungan, penyortiran _________ stabil.
Makalah Struktur Data (2)
1. Pertanyaan pilihan ganda (24 poin)
1. Deskripsi tabel linier berikut tidak benar ().
(A) Tabel linier disimpan secara berurutan dan harus menempati ruang penyimpanan yang berdekatan
(B) Tabel linier dirantai dan tidak memakan ruang penyimpanan yang terus menerus
(C) Tabel linier diimplementasikan dengan penyimpanan berantai untuk memfasilitasi operasi penyisipan dan penghapusan
(d) Tabel linier diimplementasikan dengan penyimpanan berurutan untuk memfasilitasi operasi penyisipan dan penghapusan
2. Misalkan jumlah total simpul daun di pohon Huffman adalah m, dan jika daftar tertaut biner digunakan sebagai struktur penyimpanan, ada total ( ) bidang penunjuk kosong di pohon Huffman.
(A) 2m-1 (B)2m (C)2m+1 (D)4m
3. Jika penunjuk kepala dan ekor dari antrean loop berurutan Q[0:M-1] masing-masing adalah F dan R, penunjuk kepala F selalu menunjuk ke posisi sebelumnya dari elemen kepala, dan penunjuk ekor R selalu menunjuk ke posisi elemen ekor saat ini, maka jumlah elemen dalam antrean loop adalah ( ).
(A) R-F (B) F-R (C) (R-F+M)%M (D) (F-R+M)%M
4. Jika urutan traversal orde tengah dari pohon biner adalah ABCD dan urutan traversal urutan sebelumnya adalah CABD, maka urutan yang diperoleh dengan melintasi pohon biner dalam urutan berikutnya adalah ().
(A) BADC (B) BCDA (C) CDAB (D) CBDA
5. Misalkan ada n simpul dalam grafik yang sama sekali tidak terarah, maka ada ( ) tepi dalam grafik yang sama sekali tidak terarah.
(A) n(n-1)/2 (B) n(n-1) (C) n2 (D) n2-1
6. Misalkan ada 2000 node dalam pohon biner, maka tinggi minimum pohon biner adalah ( ).
(A) 9 (B) 10 (C) 11 (D) 12
7. Misalkan ada n simpul dalam grafik terarah, maka ada ( ) simpul header dalam tabel berdekatan yang sesuai dengan grafik terarah.
(A) n-1 (B) n (C) n+1 (D) 2n-1
8. Atur serangkaian urutan kata kunci catatan awal (5, 2, 6, 3, 8), dan hasil pengurutan cepat berdasarkan kata kunci catatan pertama 5 adalah ( ).
(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. Isi bagian yang kosong (24 poin)
1. Untuk menerapkan teknologi pencarian HASH secara efektif, dua masalah yang harus diselesaikan adalah ____________________ dan __________________________.
2. Fungsi segmen program berikut mewujudkan data x ke dalam tumpukan, dan membutuhkan pernyataan yang benar untuk diisi di garis bawah.
typedefstruct {int s[100]; int atas; } tumpukan persegi;
dorong kosong (sqstack &stack, int x)
{
if (stack.top==m-1) printf("meluap");
else {____________________; _________________; }
}
3. Urutan yang diperoleh dengan melintasi pohon penyortiran biner dalam urutan tengah adalah urutan ___________ (diisi dalam urutan atau tidak berurutan).
4. Kompleksitas waktu terburuk dari penyortiran cepat adalah ___________, dan kompleksitas waktu rata-rata __________.
5. Jika jumlah simpul dengan derajat 0 dalam pohon biner adalah N0 dan nomor simpul dengan derajat 1 adalah N1, maka jumlah simpul dengan derajat 2 dalam pohon biner adalah _________; Jika daftar tertaut biner digunakan sebagai struktur penyimpanan pohon biner, _______ ada bidang penunjuk kosong di pohon biner.
6. Misalkan jumlah simpul dan tepi dalam grafik tidak terarah tertentu masing-masing adalah n dan e, dan jumlah derajat semua simpul adalah d, maka e = _______.
7. Jika urutan kata kunci catatan awal adalah (55, 63, 44, 38, 75, 80, 31, 56), maka tumpukan awal yang ditetapkan oleh metode penyaringan adalah ___________________________.
8. Diketahui bahwa struktur penyimpanan tabel berdekatan dari grafik terarah adalah sebagai berikut: Dari simpul 1, urutan keluaran traversal DFS adalah:
, urutan keluaran traversal BFS adalah
Makalah Struktur Data (3)
1. Pertanyaan pilihan ganda (1 poin per pertanyaan, total 20 poin)
1. Jika bentuk biner dari struktur data dinyatakan sebagai 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>}, maka struktur data A adalah ( ).
(A) Struktur linier (B) Struktur pohon (C) Struktur fisik (D) Struktur grafis
2. Kompleks waktu dari program berikut adalah ()
for(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. Atur variabel penunjuk p untuk menunjuk ke simpul A dalam satu daftar tertaut, jika Anda menghapus simpul A dalam satu daftar tertaut, Anda perlu mengubah urutan operasi penunjuk menjadi ().
(A) q=p->next; p->data=q->data; p->berikutnya=q->berikutnya; Gratis (Q);
(B) q=p->next; q->data=p->data; p->berikutnya=q->berikutnya; Gratis (Q);
(C) q=p->next; p->berikutnya=q->berikutnya; Gratis (Q);
(D) q=p->next; p->data=q->data; Gratis (Q);
4. Jika ada n kata kunci rekaman yang akan diurutkan, ( ) unit catatan tambahan diperlukan dalam penyortiran tumpukan.
(A) 1 (B) n (C) nlog2n (D) n2
5. Jika kata kunci catatan kata kunci awal adalah (20, 15, 14, 18, 21, 36, 40, 10), maka hasil setelah akhir pengurutan cepat dicatat dengan 20 sebagai tolok ukurnya adalah ( ).
(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. Misalkan ada n node di pohon pengurutan biner, maka panjang pencarian rata-rata di pohon pengurutan biner adalah ( ).
(A) O(1) (B) O(log2n) (C) (D) O(n2)
7. Misalkan ada n simpul e tepi dalam grafik tidak terarah G, maka jumlah simpul header dan simpul tabel dalam tabel yang berdekatan adalah ( ).
(A) n,e (B) e,n (C) 2n,e (D) n,2e
8. Misalkan ada n simpul dalam grafik koneksi yang kuat, maka setidaknya ada ( ) tepi dalam grafik koneksi yang kuat.
(A) n(n-1) (B) n+1 (C) n (D) n(n+1)
9. Ada 5000 kata kunci rekaman yang akan diurutkan, jika Anda perlu menggunakan metode tercepat untuk memilih 10 kata kunci rekaman terkecil, Anda dapat menggunakan metode ( ) berikut untuk mencapai tujuan ini.
(A) Pengurutan cepat (B) Pengurutan tumpukan (C) Pengurutan gabungan (D) Sisipkan pengurutan
10. Empat jenis ( ) berikut memiliki kompleksitas spasial terbesar.
(A) Penyortiran penyisipan (B) Penyortiran menggelegak (C) Penyortiran tumpukan (D) Penyortiran gabungan
2. Isi kekosongan (1 poin per kosong, total 20 poin)
1. Struktur fisik data terutama mencakup dua situasi: _____________ dan ______________.
2. Jika ada 500 node dalam pohon biner lengkap, kedalaman pohon biner adalah __________; Jika Anda menggunakan daftar tertaut biner sebagai struktur penyimpanan untuk pohon biner sepenuhnya, ___________ ada bidang penunjuk kosong.
3. Jika urutan input adalah 1, 2, 3, maka urutan output ___________ berbeda dapat diperoleh setelah aksi tumpukan.
4. Jika matriks kedekatan A[n][n] digunakan sebagai struktur penyimpanan untuk grafik G, maka jumlah semua elemen pada baris i dalam matriks kedekatan sama dengan ________ simpul i, dan jumlah semua elemen pada kolom i sama dengan ________ simpul i.
5. Jika ada n node di pohon Huffman, ada ________ node dengan derajat 1 di pohon Huffman.
6. Jika ada n simpul e dalam grafik arah G dengan tepi arah, dan jumlah semua simpul yang memasuki derajat adalah d, maka hubungan antara e dan d adalah _________.
7. __________ melintasi node di pohon penyortiran biner dapat memperoleh urutan kata kunci bertahap (terisi, tengah, atau posterior).
8. Jika ada 100 elemen dalam tabel pencarian, jika Anda menggunakan metode pencarian dikotomi untuk menemukan elemen data X, Anda perlu membandingkannya hingga ________ kali untuk menentukan apakah elemen data X ada dalam tabel pencarian.
9. Apakah itu tumpukan dengan struktur penyimpanan berurutan atau tumpukan dengan struktur penyimpanan rantai, kompleksitas waktu operasi in-stack dan out-stack ____________.
10. Pohon biner lengkap dengan n node, jika diberi nomor secara berurutan dari atas ke bawah dan dari kiri ke kanan mulai dari 1, node induk dari node ke-i diberi nomor ____________, dan nomor node anak kanan adalah ___________.
11. Jika kumpulan awal kata kunci yang direkam adalah (72, 73, 71, 23, 94, 16, 5), maka hasil pengurutan cepat berdasarkan kata kunci catatan 72 adalah ___________________________.
12. Jika ada satu set tepi terarah dalam grafik arah G E={<1,2>,<2,3>,<1,4>,<4,2>,<4,3>}, maka urutan topologi grafik adalah ____________________.
13. Algoritma berikut mengimplementasikan kata kunci dengan nilai x dalam daftar hash berurutan, silakan isi pernyataan yang benar di garis bawah.
struct record{int key; int orang lain; };
inthashsqsearch(struct record hashtable[ ],int k)
{
inti, j; j=i=k % p;
sementara (hashtable[j].key!=k&&hashtable[j].flag!=0){j=(____) %m; jika (i==j) mengembalikan(-1); }
jika (_______________________) kembali(j); else return(-1);
}
14. Algoritma berikut mengimplementasikan nilai kunci k dalam pohon pengurutan biner, silakan isi pernyataan yang benar di garis bawah.
typedefstruct node{int key; struct node *lchild; struktur simpul *rchild; }bitree;
bitree *bstsearch(bitree *t, int k)
{
jika (t==0) mengembalikan(0); else while (t!=0)
jika (t->kunci==k)_____________; else if (t->key>k) t=t->lchild; else_____________;
}
Makalah uji struktur data (1) Lihat jawabannya
1. Pertanyaan pilihan ganda (2 poin per pertanyaan, total 20 poin)
1.A 2.D 3.D 4.C 5.C 6.D 7.D 8.C 9.D 10.A
2. Isi kekosongan (1 poin per kosong, total 26 poin)
1. Kebenaran, keterbacaan, kekuatan, dan efisiensi tinggi
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. Arah dan non-sirkuit
8.n(n-1)/2 n(n-1)
9.（12，40） （ ） （74） （23,55，63）
10. Tambahkan 1
11.O (log2n) O (nlog2n)
12. Konsolidasi
Jawaban atas pertanyaan tes lainnya dapat dilihat:
Wisatawan, jika Anda ingin melihat konten tersembunyi dari posting ini, silakan Jawab
|
Diposting pada 25/11/2014 12.46.30
|
|
|
Diposting pada 30/12/2014 00.10.55
|
