Cấu trúc dữ liệu và giải thuật

Ưu điểm của việc cài đặt danh sách bằng mảng:

• Có thể thay đổi phần tử theo ý muốn của người dùng

• Có thể bổ sung hoặc xóa phần tử bất kỳ trong mảng

• Việc truy cập vào phần tử trong mảng được thực hiện trực tiếp dựa vào địa chỉ tính được (chỉ số), nên tốc độ nhanh và đồng đều với mọi phần tử.

• Tất cả các ý trên đều đúng

Danh sách tuyến tính là:

• Danh sách được lưu dưới dạng mảng

• Danh sách tuyến tính là một danh sách rỗng

• Danh sách mà quan hệ lân cận giữa các phần tử được xác định

• Danh sách tuyến tính là một danh sách có dạng (a1, a2, a3,..., an)

Hãy cho biết tư tưởng nào sau đây nói về 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ị phân 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 bên trái, ngược lại ta tìm kiếm trên cây con bên phải

• Lần lượt chia dãy phần tử thành  hai dãy con bởi một phần tử khóa, sau đó thực hiện việc tìm kiếm trên hai phân đ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

Hãy cho biết ý tưởng nào sau đây nói về tưởng phương pháp sắp xếp Trộn (Merge sort)?

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

• Bắt đầu từ cuối dãy đến đầu dãy, ta làm 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.

• 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 cho đến phần tử cuối cùng.

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

Phương pháp nào sau đây chính là phương pháp sắp xếp nhanh (Quick sort)?

• Phương pháp trộn

• Phương pháp vun đống

• Phương pháp chèn

• Phương pháp phân đoạn.

Hãy cho biết ý tưởng nào sau đây nói về phương pháp sắp xếp nhanh (Quick sort)?

• 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 cho đến phần tử cuối cùng

• Bắt đầu từ cuối dãy đến đầu dãy, ta làm 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.

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

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

Hãy cho biết ý tưởng nào sau đây nói về phương pháp sắp xếp chèn (insertion sort)?

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

• Lần lượt lấy phần tử 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

• 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 cho đến phần tử cuối cùng.

• Bắt đầu từ cuối dãy đến đầu dãy, ta làm 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.

Hãy cho biết ý tưởng nào sau đây nói về phương pháp sắp xếp nổi bọt (bubble sort)?

• Phân đoạn thành nhiều dãy con và lần lượt trộn hai dãy con thành nhiều 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àm 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.

• Lần lượt lấy phần tử 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

• 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 cho đến phần tử cuối cùng.

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

• Quick sort, Heap sort

• Quick sort, Merge sort

• Quick sort, Bubble sort

• Quick sort, Insert sort

Hãy cho biết phát biểu nào đúng nhất về Giải thuật đệ quy?

• Trong giải thuật của nó có lời gọi tới một giải thuật khác đã biết kết quả.

• Trong giải thuật của nó có lời gọi tới chính nó nhưng phạm vi lớn hơn

• Trong giải thuật của nó có lời gọi tới chính nó nhưng phạm vi nhỏ hơn

• Trong giải thuật của nó có lời gọi tới chính nó