Câu hỏi về giải thuật và danh sách chương 2

Cài đặt danh sách bằng mảng có nghĩa là

• Dùng bản ghi có hai thành phần để lưu trữ các phần tử của danh sách

• Dùng biến con trỏ lưu trữ các phần tử của danh sách.

• Tất cả đều đúng.

• Dùng một mảng (array) để lưu trữ liên tiếp các phần tử của danh sách bắt đầu từ vị trí đầu tiên của mảng.

Tư tưởng của giải thuật tìm kiếm nhị phân:

• So sánh X lần lượt với các phần tử thứ nhất, thứ hai,… của dãy cho đến khi gặp phần tử có khóa cần tìm.

• Lần lượt chia dãy thành hai dãy con dựa vào phần tử khoá, sau đó thực hiện việc tìm kiếm trên hai đoạn đã chia.

• Tại mỗi bước tiến hành so sánh X với phần tử ở giữa của dãy, dựa vào bước so sánh này quyết định giới hạn dãy tìm kiếm nằm ở nửa trên, hay nửa dưới của dãy hiện hành.

• Tìm kiếm dựa vào cây nhị tìm kiếm.

Tư tưởng của giải thuật tìm kiếm tuần tự

• So sánh X lần lượt với các phần tử thứ nhất, thứ hai,... của dãy cho đến khi gặp phần tử có khóa cần tìm.

• Tìm kiếm dựa vào cây nhị tìm kiếm: Nếu giá trị cần tìm nhỏ hơn gốc thì thực hiện tìm kiếm trên cây con trái, ngược lại ta việc tìm kiếm được thực hiện trên cây con phải.

• Tại mỗi bước tiến hành so sánh X với phần tử ở giữa của dãy, Dựa vào bước so sánh này quyết định giới hạn dãy tìm kiếm nằm ở nửa trên, hay nửa dưới của dãy hiện hành.

• Lần lượt chia dãy thành hai dãy con dựa vào phần tử khoá, sau đó thực hiện việc tìm kiếm trên hai đoạn đã chia.

Danh sách Đặc là:

• Một tập hợp mà không cần khai báo trước số lượng phần tử khi sử dụng

• .  Một tập hợp có thứ tự gồm một số xác định n phần tử cùng kiểu dữ liệu liên tục trong bộ nhớ và có cùng một tên (với n được gọi là độ dài hay kích thước của mảng).

• .  Một các phần từ được xác định trước, có cùng kiểu dữ liệu và nằm rải rác trong vùng nhớx

• Một tập các hợp phần tử có cùng kiểu dữ liệu và được sắp xếp theo thứ tự tăng dần.

Ý tưởng phương pháp sắp xếp nổi bọt (bubble sort) là:

• Phân đoạn dãy thành nhiều dãy con và lần lượt trộn hai dãy con thành dãy lớn hơn, cho đến khi thu được dãy ban đầu đã được sắp xếp.

• Chọn phần tử bé nhất xếp vào vị trí thứ nhất bằng cách đổi chỗ phần tử bé nhất với phần tử thứ nhất; Tương tự đối với phần tử nhỏ thứ hai, ba...

• Lần lượt lấy phần tử của danh sách chèn vị trí thích hợp của nó trong dãy bằng cách đẩy các phần tử lớn hơn xuống.

• Bắt đầu từ cuối dãy đến đầu dãy, ta lần lượt so sánh hai phần tử kế tiếp nhau, nếu phần tử nào nhỏ hơn được đứng vị trí trên.

Ý tưởng phương pháp sắp xếp nhanh (Quicksort) là:

• Lần lượt chia dãy phần tử thành hai dãy con bởi một phần tử khoá (dãy con trước khoá gồm các phần tử nhỏ hơn khoá và dãy còn lại gồm các phần tử lớn hơn khoA..

• Chọn phần tử bé nhất xếp vào vị trí thứ nhất bằng cách đổi chổ phần tử bé nhất với phần tử thứ nhất; Tương tự đối với phần tử nhỏ thứ hai, ba...

• Phân đoạn dãy thành nhiều dãy con và lần lượt trộn hai dãy con thành dãy lớn hơn, cho đến khi thu được dãy ban đầu đã được sắp xếp.

• Bắt đầu từ cuối dãy đến đầu dãy, ta lần lượt so sánh hai phần tử kế tiếp nhau, nếu phần tử nào nhỏ hơn được đứng vị trí trên.

Trong các giải thuật sắp xếp, giải thuật nào áp dụng phương pháp "Chia để trị"?

• Quick sort, Bubble sort

• Quick sort, Insert sort

• Quick sort, Merge sort

• Quick sort, Heap sort

Cho dãy số {6 1 3 0 5 7 9 2 8 4}. Áp dụng phương pháp sắp xếp lựa chọn (Select sort) sau lần lặp đầu tiên của giải thuật ta có kết quả: {0 1 3 6 5 7 9 2 8 4}. Dãy số thu được sau lần lặp thứ năm là:

• {0 1 2 3 5 7 9 4 8 6}

• {0 1 2 3 6 5 7 9 8 4}

• {0 1 2 3 4 7 9 6 8 5}

• {0 1 2 3 4 5 6 7 8 9}

Trong thuật toán sắp xếp nổi bọt kết thúc khi nào?

• Khi các phần tử đã nằm đúng thứ tự mong muốn.

• Không còn bất kì cặp liền kề trái thứ tự mong muốn

• Không còn xảy ra đổi chỗ lần nào nữa

• Cả A, B và C đều đúng

Cho dãy số {6 1 3 0 5 7 9 2 8 4}. Áp dụng phương pháp sắp xếp lựa chọn (Select sort) sau lần lặp đầu tiên của giải thuật ta có kết quả: {0 1 3 6 5 7 9 2 8 4}. Dãy số thu được sau lần lặp thứ tư là:

• {0 1 2 3 5 7 9 6 8 4}

• {0 1 2 3 4 5 6 7 8 9}

• {0 1 2 3 6 5 7 9 8 4}

• {0 1 2 3 5 7 9 4 8 6}