Câu hỏi ôn tập Cấu trúc dữ liệu và thuật giải

Chương 1: Các khái niệm mở đầu 1- Từ dữ liệu thực tế đến dữ liệu trong chương trình máy tính cần phải tượng hóa...
Nội dung trích xuất từ tài liệu:
Câu hỏi ôn tập Cấu trúc dữ liệu và thuật giải CTDL&TG - Câu hỏi ôn tập Câu hỏi ôn tập Cấu trúc dữ liệu và thuật giảiChương 1: Các khái niệm mở đầu 1- Từ dữ liệu thực tế đến dữ liệu trong chương trình máy tính cần phải tượng hóa như thế nào; 2- Định nghĩa mô hình dữ liệu, kiểu dữ liệu trừu tượng, cấu trúc dữ liệu; phân biệt sự khác nhau; V í dụ. 3- So sánh hiệu quả của thuật giải như thế nào, tại sao cần tính hiệu quả, ví dụ. 4- Định nghĩa kí hiệu O lớn, ý nghiã, ví dụ. 5- Thế nào là phép toán sơ cấp. Cách xác định thời gian thực hiện thuật giải bằng tổng số phép toán sơ cấp. Cho ví dụ. 6- Định nghĩa chi phí thời gian tối đa, tối thiểu, trung bình; Ví dụ.Chương 2: Sắp xếp - các thuật giải cơ sở 1- Mô tả các thủ tục sắp xếp nổi bọt, chèn trực tiếp, chọn trực tiếp; Phân tích ước lượng chi phí thời gian thực hiện của mỗi thủ tục 2- Mô tả thủ tục sắp xếp hoà nhập hai đường; Phân tích ước lượng chi phí thời gian thực hiện. 3- Mô tả thủ tục sắp xếp nhanh, ví dụ minh hoạ. Phân tích ước lượng chi phí thời gian thực hiện.Chương 3: Mô hình danh sách Mô hình danh sách là gì, đặc tả các phép toán cơ1-bản của một danh sách Cửa sổ truy cập các thành phần là gì, phân biệt2-của sổ truy cập hiển và cửa sổ truy cập ẩn. Ưu nhượcđiểm của chúng. Cấu trúc danh sách mảng; ưu nhược điểm của3-danh sách mảng. Tìm kiếm trong danh sách, so sánh tìm kiếm tuần4-tự và tìm kiếm nhị phân.__________________________Nguyễn Đình Hóa – ĐHQG HN1CTDL&TG - Câu hỏi ôn tậpChương 4: Kiểu ngăn xếp và kiểu hàng đợi. Định nghĩa kiểu ngăn xếp, các phép toán. Thực1-hiện ngăn xếp bằng mảng: khai báo kiểu ngăn xếp(bằng một ngôn ngữ lập trình cụ thể: Pascal, C, Java).Thời gian thực hiện các phép toán ngăn xếp. Định nghĩa kiểu hàng đợi, các phép toán. Thực2-hiện hàng đợi bằng mảng: khai báo kiểu hàng đợi(bằng một ngôn ngữ lập trình cụ thể: Pascal, C, Java),thời gian thực hiện các phép toán. Định nghĩa cách viết biểu thức trung tố, tiền tố,3-hậu tố, cho ví dụ. Nêu ưu điểm của cách viết hậu tố.Thủ tục tính gía trị biêu thức hậu tố. Ví dụ minh hoạ. Tại sao phải dùng ngăn xếp trong tổ chức thực4-hiện chương trình con, thủ tục đệ quy. Cách khử đệquy dùng ngăn xếp, ví dụ minh hoạ.Chương 5: Danh sách móc nối Mô tả cấu trúc danh sách móc nối đơn, khai báo1-kiểu danh sách móc nối đơn (bằng một ngôn ngữ lậptrình cụ thể: Pascal, C); Mô tả việc thực hiện các phéptoán, minh hoạ bằng hình vẽ, thời gian thực hiện cácphép toán. Phân tích so sánh việc thực hiện danh sách nối2-đơn có dùng và không dùng các nút đánh dấuBeforefirst, Afterlast. Nhược điểm của danh sách móc nối đơn, các3-cách khắc phục. Mô tả cấu trúc danh sách nối vòng, danh sách nối4-vòng chỉ thêm bớt tại một chỗ, danh sách nối kép. Môtả việc thực hiện các phép toán, minh hoạ bằng hìnhvẽ. Xây dựng ngăn xếp và hàng đợi bằng cấu trúc5-móc nối. Khai báo (bằng một ngôn ngữ lập trình cụthể: Pascal, C). Mô tả việc thực hiện các phép toán,minh hoạ bằng hình vẽ.Chương 6: Mô hình cây__________________________Nguyễn Đình Hóa – ĐHQG HN2CTDL&TG - Câu hỏi ôn tập Định nghĩa các khái niệm cơ bản trong mô hình1-cây, ví dụ minh hoạ. Đặc tả các phép toán trong môhình cây. Định nghĩa cây nhị phân, cây hoàn chỉnh, cây đầy2-đủ (trái), liên hệ giữa chiều cao của cây nhị phân vàkích thước (số nút) của cây. Cây nhị phân dùng cấu trúc mảng, khai báo kiểu3-(bằng một ngôn ngữ lập trình cụ thể: Pascal, C, Java);ví dụ minh hoạ, thời gian thực hiện các phép toán; ưunhược điểm. Cây nhị phân dùng danh sách nút. khai báo kiểu4-(bằng một ngôn ngữ lập trình cụ thể: Pascal, C, Java);thời gian thực hiện các phép toán; ưu nhược điểm. Cây nhị phân dùng cấu trúc móc nối, khai báo5-kiểu (bằng một ngôn ngữ lập trình cụ thể: Pascal, C);thời gian thực hiện các phép toán. Trình bày ba phép duyệt cây nhị phân, viết các6-thủ tục đệ quy. Phân tích cách khử đệ quy để chuyểnthành thủ tục lặp. Các cách khác nhau để biểu diễn cây nhiều7-nhánh; biểu diễn qua cây nhị phân tương đương. ví dụminh hoạ. Cây nhị phân biểu diễn biểu thức, thủ tục tính8-giá trị biểu thức; Mô tả cấu trúc Trie, ví dụ minh hoạ, phân tích9-ứng dụng của Trie. Định nghĩa Heap, ý nghĩa, ví dụ minh hoạ. Mô tả10-các thủ tục upheap, downheap, makeheap; ước lượngthời gian thực hiện của mỗi thủ tục. So sánh việc thựchiện hàng đợi ưu tiên bằng danh sách có thứ tự và bằngheap. Trình bày thủ tục sắp xếp vun đống, ví dụ minh11-hoạ; Phân tich ước lượng thời gian thực hiện.Chương 7: Cây tìm kiếm nhị phân Định nghĩa cây tìm kiếm nhị phân, ví dụ minh1-hoạ; mô tả việc thực hiện các phép toán tìm kiếm, thêm__________________________Nguyễn Đình Hóa – ĐHQG HN3CTDL&TG - Câu hỏi ôn tậpkhoá vào cây. Tạo cây tìm kiếm bằng cách thêm dầntừng khoá. Phân tích phép gỡ bỏ một khoá khỏi cây tìm2-kiếm, minh hoạ bằng hình vẽ, cho ví dụ cụ thể. Phân tích ước lượng thời gian thực hiện của các3-phép toán trên cây tìm kiếm. Định nghĩa cây cân đối AVL, ý nghĩa, ví dụ minh4-hoạ. Mô tả phép quay đơn, phép quay kép bằng hìnhvẽ; Trình bày thủ tục cân bằng lại sau phép thêm khoá;Ví dụ minh họa. Định nghĩa cây đỏ đen, ý nghĩa, ví dụ. Trình bày5-thủ tục cân bằng lại sau phép thêm khoá vào cây đỏđen. Định nghĩa cây tìm kiếm ngoài, ví dụ.6-Chương 8: Tập hợp, bảng, tự điển. Định nghĩa kiểu tập hợp và các phép toán; Phân1-biệt kiểu bảng và kiểu tự điển. Các cách biểu diễn tậphợp và thời gian thực hiện các phép toán. Định nghĩa bảng băm, địa chỉ băm, vấn đề xung2-đột địa chỉ, ví dụ minh hoạ, các cách giải quyết. Định nghĩa bảng băm mở, trình bày các phép toán3-của bảng băm mở; phân tích ước lượng thời gia ...