Font size
WorksheetsMối quan hệ giữa cấu trúc dữ liệu và giải thuật
Total questions: 48
Worksheet time: 24mins
Xác định thời gian thực hiện của chương trình là:
A. Xác định các bước thực hiện của giải thuật
B. Xác định sai sót trong kết quả của giải thuật
C. Xác định độ phức tạp của giải thuật.
D. Tất cả đều đúng
Trong qui tắc tổng quát, thời gian thực hiện của mỗi lệnh gán, scanf, printf là:
A. C(0)
B. C(1)
C. O(0)
D. O(1)
Thời gian thực hiện của một chuỗi tuần tự các lệnh được xác định bằng:
A. Qui tắc cộng
B. Qui tắc trừ
C. Qui tắc nhân
D. Tất cả đều đúng
Có thể tính độ phức tạp của một giải thuật theo nguyên tắc:
A. Qui tắc cộng
B. Qui tắc nhân
C. Qui tắc tổng quát để phân tích một chương trình
D. Tất cả đều đúng
Khi nói đến độ phức tạp của giải thuật là ta muốn nói đến
Kết quả thu được sau khi thực hiện của chương trình
Hiệu quả của thời gian thực hiện của chương trình
Các bước tính toán trong quá trình thực hiện chương trình
Tất cả đều đúng
Mối quan hệ giữa cấu trúc dữ liệu và giải thuật có thể minh họa bằng đẳng thức:
A. Cấu trúc dữ liệu + Giải thuật = Chương trình
B. Cấu trúc dữ liệu + Chương trình = Giải thuật
C. Chương trình + Giải thuật = Cấu trúc dữ liệu
D. Cấu trúc dữ liệu = Chương trình
Đoạn mã giả dưới đây mô tả thuật toán gì?
Sắp xếp dãy khóa theo thứ tự giảm dần bằng phương pháp lựa chọn
Sắp xếp dãy khóa theo thứ tự tăng dần bằng phương pháp lựa chọn
Sắp xếp dãy khóa theo thứ tự giảm dần bằng phương pháp thêm dần
Sắp xếp dãy khóa theo thứ tự tăng dần bằng phương pháp thêm dần
Sắp xếp một dãy theo thứ tự tăng dần bằng phương pháp sắp xếp lựa chọn là
Lặp lại quá trình chọn phần tử nhỏ nhất trong số các phần tử chưa được sắp
Lặp lại quá trình chọn phần tử trung bình trong số các phần tử chưa được sắp
Lặp lại quá trình chọn phần tử lớn nhất trong số các phần tử chưa được sắp
Lặp lại quá trình chọn phần tử lớn nhất trong số các phần tử đã được sắp
Lệnh gán x:=15 tốn một hằng thời gian hay O(1), Lệnh đọc dữ liệu READ(x) tốn một hằng thời gian hay O(1).Vậy thời gian thực hiện cả hai lệnh trên nối tiếp nhau là:
O(max(1,1))=O(1)
O(max(0,0))=O(1)
O(min(1,1))=O(1)
O(min(0,0))=O(1)
Dấu hiệu nào dưới đây cho biết danh sách liên kết đơn L là rỗng:
L ->left == NULL
L ->infor == NULL
L ->next == NULL
L == NULL
Phép 'hòa nhập hai đường' chỉ có thể áp dụng cho 2 dãy con thỏa mãn tính chất:
Đều là dãy tăng dần
Đều là dãy giảm dần
Hai dãy đã được sắp xếp
Hai dãy bất kỳ
Để đánh giá một cấu trúc dữ liệu ta thường dựa vào một số tiêu chí
A. Cấu trúc dữ liệu phải tiết kiệm tài nguyên (bộ nhớ trong),
B. Cấu trúc dữ liệu phải phản ảnh đúng thực tế của bài toán,
C. Cấu trúc dữ liệu phải dễ dàng trong việc thao tác dữ liệu.
D. Cả a, b, c đều đúng
Trong qui tắc nhân, Nếu T1(n) và T2(n) là thời gian thực hiện của hai đoạn chương trình P1và P2 và T1(n) = O(f(n)), T2(n) = O(g(n)) thì thời gian thực hiện của hai đoạn chương trình đó lồng nhau là:
T(n)=O(min(f(n),g(n)))
T(n)=O(max(f(n),g(n)))
T(n) = O(f(n).g(n))
T(n2) = O(f(n).g(n))
Giải thuật sắp xếp kiểu nổi bọt Thủ tục sw thực hiện nhiệm vụ gì?
Tìm min(k[j], k[j-1])
Tìm max(k[j], k[j-1])
Đổi chỗ k[j], k[j-1]
Không có phương án nào đúng.
Chọn phát biểu đúng trong các phát biểu sau: Sau khi thực hiện đoạn lệnh trên ta thu được:
a[k] mang giá trị lớn nhất trong mảng
a[k] mang giá trị nhỏ nhất trong mảng
k mang giá trị lớn nhất trong mảng
k mang giá trị nhỏ nhất trong mảng
Ta nói rằng hàm không âm T(n) có tỷ suất tăng (growth rate) f(n) nếu tồn tại các hằng số C và N0 sao cho :
T(n) ≤ Cf(n) với mọi n ≥ N0
T(n) ≥ Cf(n) với mọi n ≥ N0
T(n) ≤ Cf(n) với mọi n ≤ N0
T(n) ≥ Cf(n) với mọi n ≥ N0
Theo qui tắc cộng, nếu T1(n) và T2(n) là thời gian thực hiện của hai đoạn chương trình P1 và P2; và T1(n) = O(f(n)), T2(n) = O(g(n)) thì thời gian thực hiện của đoạn hai chương trình đó nối tiếp nhau là:
A. T(n) = O(min(f(n),g(n)))
B. T(n) = O(max(f(n),g(n)))
C. T(n) = O(f(n).g(n))
D. T(n) = max(O(f(n)), O(g(n)))
Cấu trúc dữ liệu nào tương ứng với LIFO (Last In First Out)
Queue
Linked List
Tree
Stack
Thường ta coi T(n) là thời gian thực hiện chương trình trong trường hợp xấu nhất trên dữ liệu vào có kích thước n, tức T(n) là:
A. Thời gian nhỏ nhất để thực hiện chương trình đối với mọi dữ liệu vào có cùng kích thước T
B. Thời gian nhỏ nhất để thực hiện chương trình đối với mọi dữ liệu vào có cùng kích thước n
C. Thời gian lớn nhất để thực hiện chương trình đối với mọi dữ liệu vào có cùng kích thước n.
D. Thời gian lớn nhất để thực hiện chương trình đối với mọi dữ liệu vào có cùng kích thước T
Đoạn mã giả dưới đây mô tả thuật toán gì?
Tìm kiếm nhị phân phần tử có giá trị X
Tìm phần tử nhỏ nhất của mảng
Tìm kiếm tuyến tính phần tử có giá trị X
Tìm phần tử lớn nhất của mảng
Cây nhị phân khác rỗng là cây:
Mỗi nút (trừ nút lá) đều có hai nút con
Tất cả các nút đều có nút con
Mỗi nút có không quá 2 nút con
Tất cả các nút đều có nút cha
Mục đích của việc sắp xếp là:
Sử dụng khả năng truy nhập ngẫu nhiên của bộ nhớ để truy nhập được thực hiện nhanh
Tổ chức lại các mẩu tin sao cho các khóa của chúng được sắp thứ tự tương ứng với quy luật sắp xếp
Tìm kiếm một đối tượng trong một danh sách
Trong bài toàn sắp xếp, sắp xếp ngoài là:
A. Sự sắp xếp dữ liệu được tổ chức trong bộ nhớ trong của máy tính
B. Là sự sắp xếp được sử dụng khi số lượng đối tượng cần sắp xếp lớn không thể lưu trữ trong bộ nhớ trong mà phải lưu trữ trên bộ nhớ ngoài
C. Là sự sắp xếp dữ liệu được tổ chức sắp xếp dữ liệu được lưu trữ trong các tập tin
D. Tất cả đều sai
Thời gian thực hiện chương trình là
Một hàm của kích thước dữ liệu vào, ký hiệu T(n) trong đó n là kích thước (độ lớn) của dữ liệu vào.
Một hàm của độ dài dữ liệu vào, ký hiệu N(x) trong đó x là độ dài của dữ liệu vào.
Thời gian ngắn nhất để thực hiện chương trình đối với mọi dữ liệu vào có cùng kích thước n.
Thời gian thực hiện chương trình trong trường hợp nhanh nhất trên dữ liệu vào có kích thước n
Trong bài toàn sắp xếp, sắp xếp trong là:
A. Sự sắp xếp dữ liệu được tổ chức trong bộ nhớ trong của máy tính
B. Là sự sắp xếp được sử dụng khi số lượng đối tượng cần sắp xếp lớn không thể lưu trữ trong bộ nhớ trong mà phải lưu trữ trên bộ nhớ ngoài
C. Là sự sắp xếp dữ liệu được tổ chức sắp xếp dữ liệu được lưu trữ trong các tập tin
D. Tất cả đều sai
Trong giải thuật, Ta nói rằng hàm không âm T(n) có tỷ suất tăng (growth rate) f(n) nếu tồn tại các hằng số C và N0 sao cho :
T(n) ≤ Cf(n) với mọi n ≥ N0
T(n) ≥ Cf(n) với mọi n ≥ N0
T(n) ≤ Cf(n) với mọi
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ự:
Thứ 1
Thứ 2
Thứ 23
Thứ 24
Ðơn vị đo thời gian thực hiện là:
A. Đơn vị đo thời gian bình thường giờ, phút ,giây...
B. Không phải là đơn vị đo thời gian bình thường như giờ, phút, giây....
C. Được xác định bởi thời gian được thực hiện trong một máy tính lý tưởng
D. Tất cả đều sai
Hàm thể hiện độ phức tạp có dạng thường gặp là:
log2n, n, nlog2n
n2 , n3
2n, 3n , n! , nn
Tất cả đều đúng
Nút có khóa nhỏ nhất trong cây nhị phân tìm kiếm khác rỗng là:
Nút gốc
Tất cả các nút
Nút bên phải cùng
Nút bên trái cùng
Để đánh giá giải thuật ta sử dụng khái niệm:
A. Quy tắc cộng, quy tắc nhân và quy tắc chung
B. Phương trình đệ quy, nghiệm của phương trình đệ quy
C. Độ phức tạp và ký hiệu ô lớn
D. Phương pháp truy hồi hoặc phương pháp đoán nghiệm.
Nút có giá trị khóa lớn nhất trong cây nhị phân tìm kiếm khác rỗng là:
Nút bên phải cùng
Nút bên trái cùng
Nút gốc
Tất cả các nút
Để lựa chọn một giải thuật tốt, ta sẽ căn cứ vào tiêu
Giải thuật đúng đắn
Giải thuật đơn giản
Giải thuật thực hiện nhanh
Tất cả đều đúng
Định nghĩa nào là đúng với danh sách liên kết
Danh sách liên kết là cấu trúc dữ liệu dạng cây.
Danh sách liên kết là cấu trúc dữ liệu tự định nghĩa.
Danh sách liên kết là tập hợp các phần tử mà giữa chúng có một sự nối kết với nhau thông qua vùng liên kết của chúng.
Danh sách liên kết là tập hợp các phần tử mà đặt kề cận với nhau trong vùng nhớ.
Để đánh giá một thuật toán ta thường dựa vào một số tiêu chí
Tính hiệu quả
Tính hữu hạn
Tính đúng
cả a,b,c đều đúng
Chọn định nghĩa đúng nhất về hàng đợi (Queue)
Hàng đợi còn được gọi là danh sách FILO và cấu trúc dữ liệu này còn được gọi cấu trúc FILO (First In Last Out)
Hàng đợi là một danh sách mà trong đó thao tác thêm 1 phần tử vào trong danh sách được thực hiện 1 đầu này và lấy 1 phần tử trong danh sách lại thực hiện bởi đầu kia.
Hàng đợi là một danh sách mà trong đó thao tác thêm 1 phần tử hay hủy một phần tử trong danh sách được thực hiện 1 đầu.
Hàng đợi phải là một danh sách liên kết đơn.
Trong giải thuật sắp xếp Quicksort, phần tử chốt tốt nhất là:
Phần tử đầu tiên trong dãy.
Phần tử cuối cùng trong dãy.
Phần tử ở giữa
Tìm câu đúng trong các câu sau:
A. Việc thêm, bớt các phần tử trong danh sách đặc thuận lợi
B. Việc truy xuất và tìm kiếm các phần tử của mảng dễ dàng.
C. Kích thước mảng có thể thay đổi tùy ý.
D. Sử dụng mảng thuận lợi hơn sử dụng danh sách liên kết.
Trong giải thuật sắp xếp Quicksort, phần tử chốt tốt nhất là:
Phần tử đầu tiên trong dãy
Phần tử cuối cùng trong dãy
Phần tử ở giữa dãy
Phần tử trung vị của dãy
Giả sử ta có hai giải thuật P1 và P2 với thời gian thực hiện tương ứng là T1(n) = 100n2 (với tỷ suất tăng là n2) và T2(n) = 5n3 (với tỷ suất tăng là n3 ) . Với n < 20 , giải thuật nào sẽ thực hiện nhanh hơn?
Hai giải thuật P1 và P2 có thời gian thực hiện bằng nhau tương ứng (T2 = T1)
Giải thuật P1 có thời gian thực hiện nhanh hơn giải thuật P2 (T1)
Giải thuật P2 có thời gian thực hiện nhanh hơn giải thuật P1 (T2)
Câu trả lời phụ thuộc vào kích thước dữ liệu vào
Chọn phát biểu sai trong các phát biểu sau:
Thuật toán tìm kiếm nhị phân áp dụng được trên dãy sắp xếp.
Thuật toán tìm kiếm nhị phân áp dụng được trên dãy sắp xếp tăng.
Thuật toán tìm kiếm nhị phân áp dụng được trên dãy sắp xếp giảm.
Thuật toán tìm kiếm nhị phân chỉ áp dụng được trên dãy tăng.
Theo ký pháp nghich đảo BaLan, biểu thức T = 2 3 4 * 5 6 / - + là biểu thức dạng nào?
Trung tố
Tiền tố
Hậu tố
Biểu thức trên không hợp lệ.
Cho cây biểu thức sau Chọn biểu thức trung tố tương ứng với cây
(2 * (4 + (5 + 3)))
(4 * (2+ (5 + 3)))
(2 * (3 + (5 +4)))
(2 * (5 + (4+ 3)))
Giả sử ta có hai giải thuật P1 và P2 với thời gian thực hiện tương ứng là T1(n) = 100n2 (với tỷ suất tăng là n2) và T2(n) = 5n3 (với tỷ suất tăng là n3 ) . Với n > 20 , giải thuật nào sẽ thực hiện nhanh hơn?
Hai giải thuật P1 và P2 có thời gian thực hiện bằng nhau tương ứng (T2 = T1)
Giải thuật P1 có thời gian thực hiện nhanh hơn giải thuật P2 (T1)
Giải thuật P2 có thời gian thực hiện nhanh hơn giải thuật P1 (T2)
Câu trả lời phụ thuộc vào kích thước dữ liệu vào
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ể:
Khẳng định thuật toán đúng nếu nó cho kết quả đúng
Khẳng định thuật toán sai nếu cho kết quả sai
Khẳng định thuật toán tốt nếu cho kết quả nhanh
Khẳng định thuật toán hiệu quả nếu cho kết quả đúng
Cấu trúc dữ liệu nào tương ứng nguyên tắc làm việc FIFO (First In First Out)
Stack
Queue
Linked list
Tree
Cho biểu thức trung tố Q = a + (b*c - (d/e^f)*g)*h, chuyển Q sang biểu thức dạng hậu tố ta được kết quả nào sau đây?
A. a b c* + d e f /^ g * - h * +
B. a b c * d e f ^ / g - * h +*
C. a b c+ * d e^ f / g * - h * +
D. a b c * d e f ^ / g * - h * +
Đoạn mã giả dưới đây thực hiện công việc gì? Function F(n) If n = 0 then return 1 Else return n + F(n-1);
Tính n!
Tính tổng n số nguyên đầu tiên
Tính tổng n số nguyên lẻ đầu tiên
Tính tổng n số nguyên chẵn đầu tiên
