Đề Thi Trắc Nghiệm Cấu Trúc Dữ Liệu - Trương Thị Thanh Tuyền

Chia sẻ: Dfjd Jdfjd Jf Nghia | Ngày: | Loại File: PDF | Số trang:7

Thêm vào BST

Báo xấu

1.331
lượt xem 188
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Trong danh sách đặc, , khi thêm phần tử vào vị trí P trong danh sách ta cần phải: a Luôn luôn dịch chuyển các phần tử từ đến L.Lát ra sau một vị trí. b Có thể dịch chuyển các phần từ từ p đến L.Last ra sau một vị trí. c Luôn luôn dịch chuyển các phần tử từ p+1 đến L.Last ra sau một vị trí. d Có thể dịch chuyển các phần tử từ p+1 đến L.Last ra sau một vị trí

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Đề Thi Trắc Nghiệm Cấu Trúc Dữ Liệu - Trương Thị Thanh Tuyền

1. Trong danh sách ñ c, khi thêm ph n t vào v trí p trong danh sách ta c n ph i: a. Luôn luôn d ch chuy n các ph n t t p ñ n L.Last ra sau m t v trí. b. Có th d ch chuy n các ph n t t p ñ n L.Last ra sau m t v trí. c. Luôn luôn d ch chuy n các ph n t t p+1 ñ n L.Last ra sau m t v trí. d. Có th d ch chuy n các ph n t t p+1 ñ n L.Last ra sau m t v trí. 2. Cho cây nh phân sau: H Cây nh phân ñã cho là cây tìm ki m nh phân a. ðúng D K b. Sai A F T I B E J 3. Danh sách duy t NLR c a cây nh phân câu 2 là: a. A, B, D, E, F, H, I, J, K, T b. H, D, A, B, E, F, K, I, J, T c. H, D, A, B, F, E, K, I, J, T d. B, A, E, F, D, J, I, T, K, H 4. Danh sách duy t LRN c a cây nh phân câu 2 là: a. A, B, D, E, F, H, I, J, K, T b. H, D, A, B, E, F, K, I, J, T c. B, A, D, H , F, E, K, I, J, T d. B, A, E, F, D, J, I, T, K, H 5. Danh sách duy t trung t t ng quát c a cây nh phân câu 2 là: a. B, A, D, E, F, H, J, I, K, T b. B, A, D, E, F, H, I, J, K, T c. A, B, D, E, F, H, I, J, K, T d. A, B, D, E, F, H, J, I, K, T 6. Giá tr bi u th c ti n t : /, *, -, 2, 1, +, 3, 4, *, 7, -, 6, 5 là a. -7 b. -1 c. 1 d. 7 7. Khi thêm ph n t ñ u tiên vào danh sách liên k t L r ng có ô ñ u m c thì a. L luôn luôn thay ñ i b. L có th thay ñ i c. L luôn luôn không ñ i 8. V trí ñ thêm ph n t vào hàng là a. V trí ñ u hàng b. V trí cu i hàng c. V trí b t kỳ trong hàng 9. Khi xóa ph n t ra kh i danh sách ñ c L không r ng thì ta ph i luôn luôn th c hi n câu l nh: d. T t c ñ u sai a.L.Last--; b. L->Last--; c. L->Last++; 10. Giá tr bi u th c h u t 1, 2, -, 3, 4, +, *, 7, 6, 5, -, *, / là: a. -1 b. 1 c. 7 d. M t giá tr khác 11. L y n i dung ph n t t i v trí p trong danh sách liên k t kép L không có ô ñ u m c ta th c hi n l nh: a. return L->Element; b. return L->Next->Element; c. return p->Element; Trang 1
d. return p->Next->Element; 12. Sau khi thêm ph n t X vào v trí p trong danh sách ñ c L, ta luôn luôn có m nh ñ sau là ñúng: a. L.Elements[p-1]==X; b. L.Elements[p]==X; c. L.Elements[p+1]==X; d. T t c ñ u sai. 13. Khi thêm ph n t X vào b ng băm m , ta s xen ph n t ñó vào ñ u c a danh sách v trí: a. Bucket 0. b. Bucket B-1 c. Bucket b t kỳ d. Bucket H(X) 14. Cho hàng cài ñ t b ng m ng t nh ti n như sau: Front A B Rear C Hình nh hàng sau khi thêm 2 ph n t E, F và xóa ñi 1 ph n t là: Front A B Front B Front A Front B E C B C Rear F E E E Rear F Rear F Rear F a. b. c. d. 15. Khi thêm ph n t vào danh sách ñ c không ñ y, ta luôn luôn ph i th c hi n l nh a. L.Last++; b. L->Last ++; c. L->Last--; d. T t c ñ u sai 16. Khi xóa ph n t ra kh i hàng cài ñ t b ng m ng vòng thì a. Front luôn luôn thay ñ i và Rear luôn luôn không ñ i b. Front luôn luôn thay ñ i và Rear có th thay ñ i c. Front có th thay ñ i và Rear có th thay ñ i d. Front có th thay ñ i và Rear luôn luôn không ñ i 17. V trí ph n t c n xóa ra kh i danh sách ñ c trong phép toán Delete_List (p,L) ch h p l khi: a. 0 ≤ p ≤ L.Last +1 b. 0 < p ≤ L.Last+1 c. 1≤ p ≤ L.Last+1 d. 1≤p< L.Last+1 Trang 2
18. Cho cây v i nhãn là các s nguyên như sau: 30 12 21 52 5 27 25 80 45 95 1 20 34 29 75 24 B c c a cây là: a. 1 b. 2 c. 3 d. 4 19. Danh sách duy t theo m c c a cây câu 18 là: a. 24, 1, 34, 20, 29, 75, 5, 25, 27, 95, 45, 80, 12, 52, 21, 30 b. 1, 34, 5, 25, 24, 20, 29, 27, 12, 95, 52, 45, 75, 80, 21, 30 c. 30, 12, 52, 21, 5, 25, 27, 95, 45, 80, 1, 34, 20, 29, 75, 24 d. T t c ñ u sai 20. Hãy minh h a cây câu 18 theo phương pháp cài ñ t b ng m ng Cach 1 : -1 0 0 0 1 1 1 2 3 3 4 4 6 6 9 12 Parent 30 12 52 21 5 25 27 95 45 80 1 34 20 29 75 24 Data 0123 45 6 7 8 9 10 11 12 13 14 15 16 17 … 50 Ch s m ng Maxnode=16 Cach 2 : Parent -1 0 1 2 2 1 1 6 7 6 0 10 0 12 12 14 Data 30 12 5 1 34 25 27 20 24 29 52 95 21 45 80 75 Ch 01 234 5 6 7 8 9 10 11 12 13 14 15 16 17 … 50 s m ng Maxnode=16 21. Cây tìm ki m nh phân là cây nh phân v i a. Nhãn c a nút l n hơn nhãn c a nút con trái và nh hơn nhãn c a nút con ph i b. Nhãn c a nút l n hơn nhãn c a nút con ph i và nh hơn nhãn c a nút con trái c. Nhãn c a nút l n hơn nhãn c a t t c các nút cây con trái và nh hơn nhãn c a t t c các nút cây con ph i d. Nhãn c a nút l n hơn nhãn c a t t c các nút cây con ph i và nh hơn nhãn c a t t c các nút cây con trái 22. Trong chương trình chính, ñ thêm ph n t x vào cu i danh sách L ta th c hi n l i g i hàm như sau: a. InsertList (x, Last(L), L); b. InsertList (x, Last(*L),L); c. InsertList (x, EndList(&L),&L); d. InsertList (x, EndList(L),&L); Trang 3
23. Khi xóa nút 27 ra kh i cây tìm ki m nh phân, ta th c hi n như sau: 35 a. Thay nút 27 b i nút 24 và quay v xóa nút 24. 12 52 b. Thay nút 27 b i nút 20 và quay v xóa nút 20. 5 c. Cho con ph i c a nút 12 tr xu ng nút 20. 27 80 40 d. Cho con ph i c a nút 12 tr xu ng nút 24. 1 20 37 75 24 24. S bư c c n duy t ñ tìm nút 25 trên cây câu 23 theo gi i thu t Search(x,T) là: a. 3 b. 4 c. 5 d. 6 25. Xóa nút 52 trên cây câu 23, ta c n: a. Thay nút 52 b i nút 37 và quay v xóa nút 37. b. Thay nút 52 b i nút 40 và quay v xóa nút 40. c. Thay nút 52 b i nút 80 và quay v xóa nút 80. d. C 2 câu b,c ñ u ñúng 26. Thêm nút 42 vào cây câu 23, ta th c hi n: a. Không thêm ñư c b. G n nút 42 vào con ph i c a 37. c. G n nút 42 vào con trái c a 75. d. G n nút 42 vào con ph i c a 40. 27. Hãy cho bi t thao tác nào không ñư c phép dùng trên c u trúc ngăn x p a. Thêm m t ph n t vào ñ nh ngăn x p. v trí b t kì kh i ngăn x p. b. Xóa m t ph n t c. Thêm m t ph n t vào v trí b t kì trong ngăn x p. d. C b và c. 28. Cho bi u th c trung t : (a * (5 + b) – 2 * c) + 4, bi u th c nào sau ñây là d ng h u t c a nó ? a. a 5 * b + 2 – c * 4 + b. a 5 b + * 2 – c * 4 + d. T t c ñ u sai c. a 5 b + * 2 c * - 4 + 29. Cho danh sách liên k t như hình X Y Z T U Header q K t qu trên màn hình sau khi th c hi n ño n l nh là p=First(Header); while (p->next!=q){ printf(“%c “,p->next->data); p=p->next; } a) X Y Z T U b) X Y Z T c) X Y Z d) Y Z T Trang 4
30. Cho b ng băm ñóng v i s bucket B=10 và hàm băm h(x)= x mod B v i phương pháp gi i quy t ñ ng ñ là băm l i bình phương (h(x)= (x+i2) mod B). K t qu b ng băm sau khi th c hi n các thao tác thêm 3, 5, 9, 12, 15, 16, 25 là: 0 0 0 0 1 1 1 1 2 12 2 12 2 12 2 12 3 3 3 3 3 3 3 3 4 4 4 4 25 5 5 5 5 5 5 5 5 6 16 6 15 6 15 6 15 7 15 7 25 7 16 7 16 a) 8 25 8 16 8 25 8 b) c) d) 9 9 9 9 9 9 9 9 31. Danh sách duy t LRN c a cây nh phân cho b i c p danh sách duy t sau NLR: A, B, C, D, G, E, F và LNR: C, B, D, G, A, E, F là: a. C, B, G, E, D, A, F b. C, G, D, B, F, E, A c. C, G, D, B, E, F, A d. C p danh sách ñã cho không h p l . 32. Danh sách duy t m t cây nh phân theo phương pháp duy t trung t nh phân và trung t t ng quát luôn luôn khác nhau khi và ch khi a. Có t n t i nút b khuy t con trái trên cây b. Có t n t i nút b khuy t con ph i trên cây c. Có t n t i nút có con ph i mà b khuy t con trái trên cây. d. Có t n t i nút có con trái mà b khuy t con ph i trên cây 33. Cho danh sách liên k t sau : B E A R p1 L p3 p3->Next->Next = p1->Next; L->Next = p3->Next; p1->Next = NULL; p3->Next = p1; p1->Element=Retrieve(p3,L); PrintList(L); // Hàm in danh sách ra màn hình K t qu hi n th trên màn hình là: a. REAB b. BEAR c. REAR d. M t danh sách khác 34. Khi thêm ph n t vào hàng cài ñ t b ng m ng vòng không r ng thì: a. Front luôn luôn không ñ i và Rear luôn luôn thay ñ i b. Front luôn luôn không ñ i và Rear có th thay ñ i c. Front có th thay ñ i và Rear luôn luôn thay ñ i d. Front có th thay ñ i và Rear có th thay ñ i 35. Danh sách duy t trung t t ng quát c a cây nh phân cho b i hai danh sách LRN: 5, 6, 4, 2, 9, 10, 8, 7, 3, 1 và LNR: 2, 5, 4, 6, 1, 7, 9, 8, 10, 3 là a. 5, 4, 2, 6, 1, 9, 8, 10, 3, 7 Trang 5
b. 5, 4, 6, 2, 1, 9, 8, 10, 7, 3 c. 2, 5, 4, 6, 3, 1, 8, 7, 9, 10 d. 4, 5, 6, 2, 1, 3, 7, 9, 8, 10 36. Cây câu 35 có s nút trung gian là: a. 4 b. 5 c. 6 d. 7 37. Cây câu 35 có nút 7 là a. Nút lá b. Nút trung gian có 2 con c. Nút trung gian có 1 con ph i d. Nút trung gian có 1 con trái 38. Chi u cao c a cây câu 35 là: a. 2 b. 3 c. 4 d. 5 39. Hàm sau ñư c thi t k trong danh sách liên k t v i n i dung là: Position NONAME (ElementType x, List L) { Position p=First(L); while (p!= Endlist(L)) if (Retrieve (P,L)==x) return 1; else p=Next(p,L); return 0; } Hàm này th c hi n ñư c không và làm nhi m v gì? a. Hàm tr v tìm v trí ph n t ñ u có n i dung là x và không b l i. b. Hàm trên b l i ki u d li u tr v cho hàm. c. Hàm ki m tra xem có ph n t X trong danh sách hay không và hàm không b l i. d. Hàm luôn tr v giá tr 0. 40. Nguyên t c làm vi c c a ngăn x p là: a. FIFO b. FILO d. Câu a và c cùng ñúng. c. LILO II.Ph n t lu n Câu 1: (1.5 ñi m) a. V cây tìm ki m nh phân A t danh sách ñã cho: (0.5 ñi m) 50, 70, 20, 30, 90, 35, 15, 45, 30, 100, 60, 75, 80, 5, 25, 40 50 20 70 15 30 90 60 5 35 100 25 75 45 80 40 b. Vi t danh sách duy t trung t t ng quát c a cây A (0.25 ñi m) 5, 15, 20, 25, 30, 40, 45, 35, 50, 60, 70, 80, 75, 90, 100 Trang 6
c. V l i cây sau khi th c hi n các thao tác xóa nút 30, 70, 45 và thêm vào nút 30, 20, 10 (0.75 ñi m) Cách 1: Cách 2: 50 50 20 20 60 70 15 15 25 35 90 90 60 5 5 35 100 40 100 25 75 80 10 30 10 40 80 30 Câu 2: (1.5 ñi m) Vi t hàm xác ñ nh s nút trong c a m t cây nh phân. Cho phép s d ng các phép toán cơ b n trên cây. (Sinh viên có th làm nhi u cách khác nhau và ñư c hư ng tr n ñi m khi xây d ng hàm th a yêu c u ñ t ra) - Xây d ng hàm tính t ng s nút trên cây: 0.5 ñi m - Xây d ng hàm xác ñ nh s nút lá trên cây: 0.5 ñi m -Tính s nút trung gian (có xét ñ n trư ng h p cây r ng, cây có 1 nút và trư ng h p cây có nhi u nút : 0.5 ñi m. Trang 7