Đề cương môn Cấu trúc dữ liệu- Trường Đại học bách khoa - Đại học đà nẵng.

Cách đo hiệu quả thuật toán gián tiếp qua hiệu quả chương trình máy tính không đủ
tin cậy khi so sánh thuật toán vì
Thời gian chạy phụ thuộc nhiều vào cấu hình phần cứng
Ngôn ngữ lập trình ảnh hưởng đến hiệu quả chương trình
Kinh nghiệm của người lập trình sẽ ảnh hưởng tới hiệu quả chương trình
Việc so sánh thuật toán sẽ mất nhiều thời gian
Khó có thể tận dụng lại các kết quả đã có khi so sánh với 1 thuật toán mới Correct 1/1 Points 2
Ưu điểm của cách đánh giá thuật toán trực tiếp là
Có thể đánh giá thuật toán ngay từ mô tả
Không phụ thuộc vào cấu hình phần cứng máy tính
Có thể tái sử dụng đánh giá cũ khi so sánh thuật toán
Đánh giá đơn giản và dễ dàng hơn mô hình gián tiếp Correct 1/1 Points 3
A và B là 2 thuật toán có thời gian thực hiện trong trường hợp tồi nhất tương ứng là
TA(n) = 100n^2 + n+6 , và TB(n) = n^3 +n. Những kết luận nào sau đây là đúng
Thuật toán B luôn cho thời gian thực hiện tồi hơn A
Thuật toán A thường nhanh hơn B trong trường hợp tổng quát
Trong một số trường hợp, thuật toán A có thể chậm hơn thuật toán B
Thuật toán A luôn nhanh hơn thuật toán B Correct 1/1 Points 4
Trong đánh giá hiệu quả về thời gian thực hiện của thuật toán trong trường hợp tồi
nhất theo O-lớn thì những khẳng định nào sau đây là đúng
Quan tâm đến lệnh cơ bản = lệnh được thực hiện nhiều nhất
Mọi giả sử về dữ liệu đầu vào sẽ được tạm thời bỏ qua
Nếu trong hàm có nhiều lệnh dừng hoặc return thì quan tâm đến lệnh return nào
dẫn tới thời gian thực hiện tồi nhất
Chỉ cần đếm 1 lệnh cơ bản là đủ Incorrect 0/1 Points 5
Khi kích thước đầu vào bài toán cỡ n=1000000 phần tử thì ta nên chọn thuật toán có
độ phức tạp cỡ nào để thời gian thực hiện là chấp nhận được O(n^3) O(nlogn) O(n^2) O(n!) O(2^n) O(nloglogn) Correct 1/1 Points 6
Khẳng định nào sau đây về các lớp hàm theo O-lớn là đúng
Các thuật toán thuộc các lớp hàm khác nhau có tốc độ tăng khác nhau
Các thuật toán thuộc lớp hàm hằng có độ phức tạp KHÔNG phụ thuôc vào kích
thước dữ liệu đầu vào
Các thuật toán thuộc các lớp hàm càng phức tạp (càng lớn) thì thời gian thực hiện càng nhanh
Các thuật toán thuộc cùng một lớp hàm có thời gian thực hiện khi cài đặt
Hai thuật toán thuộc cùng một lớp hàm sẽ có thời gian thực hiện trong thực tế là
như nhau trên cùng 1 bộ dữ liệu đầu vào
Thuật toán thuộc lớp hàm O(n) luôn có thời gian thực hiện nhỏ hơn 1 thuật toán
thuộc lớp hàm O(n^2) trên cùng 1 bộ dữ liệu đầu vào Correct 1/1 Points 7
Khẳng định nào sau về thời gian thực hiện theo O-lớn của thuật toán sau là đúng (hàm func1)
Thời gian thực hiện của func1 trong trường hợp tồi nhất là O(n^2)
Thời gian thực hiện của func1 trong trường hợp tốt nhất là O(n^2)
Thời gian thực hiện của func1 trong trường hợp tốt nhất là O(n)
Thời gian thực hiện của func1 trong trường hợp tốt nhất là O(1) Correct 1/1 Points 8
Đặc điểm của mô hình RAM là
Đếm số lần thực hiện các câu lệnh cơ bản
Chỉ quan tâm chính đến thời gian thực hiện - thời gian CPU
Chỉ có thể đánh giá thuật toán được mô tả bằng giả ngôn ngữ hoặc ngôn ngữ lập trình cụ thể
mất nhiều thời gian để đánh giá vì phải xét từng câu lệnh đơn lẻ Incorrect 0/1 Points 9
Tại sao cần xây dựng thuật toán hiệu quả
Vì máy tính không thể tăng tốc độ bộ xử lý lên mãi được
Vì kích thước dữ liệu của bài toán mà máy tính cần xử lý ngày càng tăng
Vì chúng ta muốn rút ngắn thời gian phải chờ đợi
Vì chi phí xây dựng thuật toán hiệu quả sẽ rẻ hơn
Vì chi phí để đầu tư nâng cao tốc độ máy tính thường đắt hơn nhiều so với chi phí
đầu tư cải tiến thuật toán Correct 1/1 Points 10
Thời gian thực hiện của thuật toán có đặc điểm là gì? Hãy chọn các đáp án đúng
Phụ thuộc vào kích thước đầu vào
Phụ thuộc vào giá trị đầu vào cụ thể của dữ liệu
Thời gian thực hiện tồi nhất là thời gian được quan tâm nhất
Thời gian trung bình là trung bình cộng của thời gian tồi nhất và tốt nhất Tuần 2 1
Phương pháp nào sau đây dùng để giải công thức đệ quy tổng quát Phương pháp quy nạp Phương pháp phân rã Phương pháp thay thế Định lý thợ Cây đệ quy Cây nhị phân Incorrect 0/1 Points 2
Đâu là các chi phí phụ trội mà khi cài đặt thuật toán dạng đệ quy người lập trình thường bỏ qua
chi phí xử lý lời gọi hàm đệ quy
chi phí tổng hợp lời giải chi phí bộ nhớ phụ
chi phí chia nhỏ bài toán Correct 1/1 Points 3
Những khẳng định nào sau đây về thuật toán đệ quy là đúng
Thuật toán đệ quy thường ngắn gọn hơn thuật toán dùng vòng lặp
Thuật toán đệ quy thường khó gỡ lỗi hơn
Thuật toán đệ quy thường hiệu quả hơn vòng lặp
Thuật toán đệ quy thường ít sử dụng bộ nhớ phụ hơn thuật toán lặp Correct 1/1 Points 4
Cho đoạn hàm tính số fibonacci sau.
Đâu là khẳng định đúng
Thời gian thực hiện là O(n)
Thời gian thực hiện là O(nlogn)
Thời gian thực hiện là O(logn) Correct 1/1 Points 5
Đâu là các trường hợp công thức đệ quy tổng quát có thể áp dụng định lý thợ T(n) = 2T(n/2)+n T(n) = T(n/2) + T(n/3) + n T(n) = 2T(n-1)+1 T(n) = T(n/3) + nlogn Incorrect 0/1 Points 6
Có nhưng cách nào để cải thiện hiệu quả của thuật toán được cài đặt đệ quy
dùng biến phụ để giảm số lần phải gọi đệ quy
khử đệ quy (biểu diễn lại thuật toán dùng dạng vòng lặp)
Chia bài toán thành nhiều bài toán con nhỏ hơn nữa
dùng bảng tra để lưu các kết quả trùng lặp
mở rộng số trường hợp cơ sở để thuật toán nhanh dừng hơn Incorrect 0/1 Points 7
Cho hàm đệ quy sau, những khẳng định nào sau dây là đúng
Thời gian thực hiện trong trường hợp tồi nhất là O(n)
Thời gian thực hiện trong trường hợp tồi nhất là O(n^3)
Việc chia thành 3 bài toán con hoặc nhiều hơn sẽ làm tăng tốc độ thực hiện (theo
thời gian vật lý trên máy)
Việc chia thành nhiều bài toán con sẽ làm thời gian thực hiện bị tồi đi so với chỉ
chia 2 (theo thời gian vật lý trên máy) Incorrect 0/1 Points 8
Trong đánh giá thuật toán trong trường hợp tồi nhất ta sẽ bỏ qua những yếu tố nào
bỏ qua những lệnh return sớm
bỏ qua những trường hợp của dữ liệu mà làm thuật toán dừng sớm
bỏ qua những trường hợp dữ liệu đầu vào nhỏ
bỏ qua kích thước đầu vào bài toán
bỏ qua những lệnh ít được thực hiện Incorrect 0/1 Points 9
Cho hàm đệ quy tìm đoạn con tăng dài nhất sau
Đâu là khẳng định đúng
Thời gian thực hiện là O(n^2)
Thời gian thực hiện là O(logn)
Không có khẳng định nào ở trên là đúng Correct 1/1 Points 10
Cho đoạn hàm tìm số có tần số xuất hiện lớn nhất trong mảng sau
Đâu là khẳng định đúng
Thời gian thực hiện là O(n)
Thời gian thực hiện là O(nlogn)
Thời gian thực hiện là O(logn)