Trắc nghiệm cấu trúc dữ liệu và giải thuật

Chia sẻ: Trần Thế Quỳnh | Ngày: | Loại File: PDF | Số trang:7

Thêm vào BST

Báo xấu

1.953
lượt xem 246
download

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

Đây là bài tập trắc nghiệm cấu trúc dữ liệu và giải thuật gửi đến các bạn độc giả tham khảo.

Chủ đề:

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

Lưu

Nội dung Text: Trắc nghiệm cấu trúc dữ liệu và giải thuật

1. Kế t quả nào đúng khi thực hiện giả i thuật sau: long lt(int n) A. lt(12) = 2010 {if (n==0) return 1; B. lt(12) = 1024 e lse return (2*lt(n-1); C. lt(7) = 720 } D. lt(6) = 64 2. Kế t quả nào đúng khi thực hiện giả i thuật sau với a[]= {1, 3, 5}; n= 5, k= 3 : void ToHopKe(int a[], int n, int k) A. 2 3 4 { int i, j, tmp = 0; B. 1 2 3 for (i= 1;i= n -k+i) i--; a[i]= a[i] + 1; for (j= i+1;j left == NULL) B. (L->ìnfor == NULL) C. (L->next == NULL) D. (L == NULL) 1
5. Kế t quả nào đúng khi thực hiện giả i thuật sau với a[]= {1, 3, 5, 4, 2}; n= 5: void HoanViKe(int a[],int n) A. 1 4 2 3 5 { int i, k, r, s, tmp = 0; B. 5 4 3 2 1 for(i=1;ia[i+1]) i= i - 1; k= n; while(a[k]< a[i]) k= k - 1; tmp= a[i]; a[i]= a[k]; a[k]=t mp; r= i+1; s= n; while(r< s) {tmp = a[r]; a[r]= a[s]; a[s]= tmp; r++; s--; } for(i= 1; i giá trị của lối sau B. Lố i sau nhận giá tr ị = 0 C. Lối trước có giá trị < giá trị của lối sau D. Lố i trước nhận giá trị = 0 8. Thao tác nào dướ i đây thực hiện trên ngăn xếp (stack): A. Thêm phần tử vào vị trí bất kỳ B. Loại bỏ phần tử tại vị trí bất kỳ C. Thêm và loại bỏ phần tử luôn D. Thêm và loại bỏ phần tử có thể thực hiện tại vị trí đỉnh (top) thực hiện tạ i vị trí bất kỳ 9. Nút có khóa lớn nhất trong cây nhị phân tìm kiế m khác rỗng là: A. Nút con bên phải nhất B. Nút con bên trái nhất C. Nút gốc D. Tất cả các n út 10. Trong phép duyệt cây nhị phân có 24 nút theo thứ tự sau, nút gốc có thứ tự: A. Thứ 1 B. Thứ 2 C. Thứ 23 D. Thứ 24 11. Nút có khóa nhỏ nhất trong cây nhị phân tìm kiế m khác rỗng là: A. Nút gốc B. Tất cả các nút C. Nút con bên phả i nhất D. Nút con bên trái nhất 2
12. Cây nhị phân khác rỗng là cây: A. Mỗi nút (trừ nút lá) đều có hai nút con B. Tất cả các nút đều có nút con C. Mỗi nút có không quá 2 nút con D. Tất cả các nút đều có nút cha 13. Đồ thị G có n đỉnh và m cạnh vớ i m  n thì ma trận kề của G luôn có dạ ng : A. là ma trận vuông cấp n B. là ma trận cấp nxm C. là ma trận vuông cấp m D. là ma trận cấp mxn 14. Đồ thị vô hướng G có chu trình Euler khi và chỉ khi : A. G liên thông và mọ i đỉnh  G có bậc chẵn B. mọ i đỉnh  G có bậc chẵn C. G có chu trình Hamilton D. G là liên thông 15. Đồ thị G là liên thông khi và chỉ khi: A. G là đồ thị có hướng B. G là đồ thị vô hướng D. G có đường đi Euler C. Có đường đi giữa hai đỉnh bất kỳ  G 16. Hãy viết các thao tác chuyển tháp khi thực hiện hàm dưới đây vơi n= 3, a= 3 và b = 1 : void MOVE(int n, int a, int b) 1) 2) { if(n==0) return; 3) MOVE(n -1, a, 6-a-b); 4) cout
21. Viết các phần tử của cây nhị phân tìm kiế m được tạo từ các nút có khóa là các số nguyên 2, 10, 15, -5, -2, 13, -12 khi thực hiện phép duyệt cây theo thứ tự sau: 22. Viết các phần tử của cây nhị phân tìm kiế m được tạo từ các nút có khóa là các số nguyên 2, 10, 15, -5, -2, 13, -12 khi thực hiện phép duyệt cây theo thứ tự giữa 23. Viết các phần tử của cây nhị phân tìm kiế m được tạo từ các nút có khóa là các số nguyên 2, 10, 15, -5, -2, 12, -12 khi thực hiện phép duyệt cây theo thứ tự trước: 24. Viết xâu mã Huffman của 4 chữ cái A, B, C, D trong bản tin M, biết tần số xuất hiện của chúng trong M tương ứng là: 0,45; 0,15; 0,30 và 0,10: 25. Viết thứ tự được duyệt của các đỉnh thuộc đồ thị G khi thực hiện tìm kiế m theo chiều sâu bắt đầu từ đỉnh 1, trong đó G được biểu diễn dưới dạng ma trận kề sau: 0 1 1 1 1 1  1 0 0 1 1 0    1 0 0 0 0 1 A=  1 1 0 0 0 0   1 1 0 0 0 0   1 0 1 0 0 0 26. Viết thứ tự được duyệt của các đỉnh thuộc đồ thị G khi thực hiện tìm kiế m theo chiều rộng bắt đầu từ đỉnh 1, trong đó G được biểu diễn dưới dạng ma trận kề sau: 0 1 1 1 1 1  1 0 0 1 1 0    1 0 0 0 0 1 A=   1 1 0 0 0 0 1 1 0 0 0 0   1 0 1 0 0 0 4
27. Viết đường đi Euler của đồ thị vô h ướng G biểu d iễn bởi ma trận kề sau: 0 1 1 1 1 0  1 0 0 1 1 1   1 0 0 1 0 0 A=   1 1 1 0 0 1 1 1 0 0 0 0   0 1 0 1 0 0  28. Viết độ dài đường đi ngắn nhất từ đ ỉnh 1 đến đỉnh 5 và các đỉnh nằm trên đường đ i đó trong đồ thị G biểu diễn bởi ma trận trọng số A với A[i,j]= 0 nếu không có cạnh nối i đến j: 0 10 0 15 0  0 0 1 0 2    A = 25 0 0 2 0 0 3 0 0 1    1 0 5 0 0    29. Tìm hai đ ỉnh i  j của đồ th ị G sao cho tổng độ dài đường đi từ i đến j và từ j về i là nhỏ nhất, G biểu diễn bởi ma trận trọng số A với A[i,j]= 0 nếu không có cạnh nố i i đến j: i= 0 12 10 19 j= 3 0 1 10    A= 0 0 0 5  0 1 0 0    30. Viết tổng trọng số WT của cây khung nhỏ nhất T trong đồ thị G biểu d iễn bởi ma trận trọng số A với A[i,j]= 0 nếu không có cạnh nối i đến j: WT= 0 7 3 0 1  T= 7 0 10 3 1   A = 3 1 0 5 0  0 3 5 0 1    1 1 0 1 0    30. Nhân tố nào là nhân tố chính ảnh hưởng đến thờ i gian tính của một giả i thuật a. Máy tính b. Thuật toán được sử dụng c. Chương trình dịch d. Kích thước của dữ liệu đầ u vào của thuật toán 5
31.Chọn phát biểu đúng trong các phát biểu dưới đây: bằng cách chạy thử 1 thuật toán với 1 bộ dữ liệu, ta có thể : a. Khẳng đ ịnh thuật toán đúng nếu nó cho kết quả đúng b. Khẳng định thuật toán sai nếu cho kết quả sai c. Khẳng đ ịnh thuật toán tốt nếu cho kết quả nhanh d. Khẳng định thuật toán hiệu quả nếu cho kết quả đúng 32.Trong các mệnh đề sau đây, mệnh đề nào sai: a. Kiểu d ữ liệu là một tập hợp nào đó các phần tử dữ liệ u cùng chung một thuộc tính b. Hệ kiểu của một ngôn ngữ bao gồ m các kiể u dữ liệu đơn và các phương pháp cho phép ta từ các kiểu dữ liệu đã có xây dựng nên các kiểu dữ liệu mới c. Cấu trúc dữ liệu là các dữ liệu phức tạp, được xây dựng nên từ các kiểu dữ liệu đã có, đơn giản hơn bằng các phương pháp liên kết nào đó d. Mộ t trong ba mệnh đề trên là sai 33. Tìm mệnh đề sai trong các mệnh đề sau: Một cấu trúc dữ liệu bao gồm… a. Một tập hợp nào đó các dữ liệu thành phần b. Các dữ liệu thành phần đặt sát nhau trong bộ nhớ ĐÁP ÁN-MÔN CẤU TRÚC DỮ LIỆU & GIẢI THUẬT 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 D D D D A A A C A D D C A A C 17 : E = -546 19 : 20 : 16 :1)3  1 (i= 5) 40 27 5 57 -7 (i= 1) 40 27 -7 5 57 2)3  2 18 : (i= 4) 40 27 57 5 -7 (i= 2) 40 27 -7 5 57 3)1  2 (i= 1) 57 27 -7 5 40 (i= 3) 40 57 27 5 -7 (i= 3) 40 27 5 -7 57 4)3  1 (i= 2) 57 40 -7 5 27 (i= 2) 57 40 27 5 -7 (i= 4) 57 40 27 5 -7 5)2  3 (i= 3) 57 40 27 -7 5 6)2  1 (i= 4) 57 40 27 5 -7 7)3  1 21 : -12 -2 -5 13 15 10 22 : -12 -5 -2 2 10 13 23 : 2 -5 -12 -2 10 15 6
2 15 13 24: A B C D 0 101 11 100 25: 1 2 4 5 3 6 26: 1 2 3 4 5 6 27: 1 2 4 1 3 4 6 2 5 1 28: 12 29: i = 2 j=3 125 30: WT= 6 T= (1, 3), (1, 5), (2, 5), (4, 5) Trần_Thế Quỳnh 08CTH02 Add :tranthequynh10091990@yahoo.com Or tranthequynh10091990@gmail.com 7