Đề thi học kỳ năm 2010 môn Cấu trúc dữ liệu và giải thuật giúp các bạn học sinh có thêm tài liệu ôn tập, luyện tập nhằm nắm vững được những kiến thức, kĩ năng cơ bản, đồng thời vận dụng kiến thức để giải các bài tập một cách thuận lợi. | ĐỀ THI CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Thời gian 90 Mã đề CDK54-2010-01 Sinh viên được sử dụng tài liệu Bài 1. a Kích thước của 1 biến kiểu char là 1 Byte biến kiểu int là 4 byte kiểu double là 8 byte. Kích thước của 1 con trỏ kiểu char là con trỏ kiểu double là Gợi ý Kích thước của con trỏ không phụ thuộc vào kiểu dữ liệu mà phụ thuộc vào từng dòng máy. Máy 32 bit thì là 4 byte máy 64 bit thì là 8 byte. Kiểu int sẽ có kích thước bằng số bit của kiểu máy đó nếu mà kiểu int là 32 bit tức là đó là máy 32 bit. Như vậy kích thước con trỏ ở đây là 4 byte 32 bit . b Đánh giá thời gian thực hiện của thuật toán đệ quy sau theo mô hình O-lớn Cho ma trận A kích thước ma trận B kích thước for i 0 i lt n i for k 0 k lt m k for j 0 j lt l j C i j A i k B k j Hãy đánh giá độ phức tạp của đoạn chương trình trên theo O-lớn Lệnh cơ sở là lệnh C i j A i k B k j Có 3 vòng lặp lồng nhau thời gian thực hiện 1 1 1 1 1 1 1 1 . . 0 0 0 0 0 Vậy độ phức tạp cỡ Bài 2. Trả lời các câu hỏi sau a Trong các phương pháp sắp xếp lựa chọn chèn đổi chỗ nổi bọt quicksort sắp xếp nhanh mergesort sắp xếp trộn thì phương pháp nào là phù hợp nhất để sắp xếp trên danh sách liên kết đơn Giải thích lựa chọn của bạn. Các thuật toán trên được chia thành 2 loại là cơ bản 2 và nâng cao log Sắp xếp trên danh sách liên kết đơn thì mergesort là phù hợp hơn vì Thời gian trung bình trong trường hợp tồi nhất cỡ log Cài đặt đơn giản hơn QuickSort b Danh sách tên của 1000 sinh viên được lưu trữ trong mảng nhưng không theo 1 thứ tự nêu những ưu điểm và nhược điểm của phương pháp lưu trữ này các tiêu chí đánh giá bộ nhớ thời gian tìm kiếm thêm xóa https tailieudientucntt Ưu điểm Chỉ lưu mỗi tên không cần lưu thêm thông tin phụ con trỏ Có thể truy cập trực tiếp từng phần tử thông qua chỉ số Nhược điểm Có thể lãng phí bộ nhớ nếu không dùng hết Vì không cần sắp xếp theo thứ tự nên việc thêm phần tử đơn giản chỉ cần thêm vào cuối . Tuy nhiên việc tìm kiếm mất nhiều thời gian hơn do chỉ có
