CS316 Chapter 2 Solid Linked list

Chọn phát biểu đúng nhất về định nghĩa danh sách

• Danh sách là một tập hợp gồm nhiều phần tử (element) a₁a₂…a_n mà tính chất cấu trúc của nó là mối liên hệ tương đối giữa các phần tử với nhau: nếu biết được phần tử a_i thì ta sẽ biết được vị trí của các phần tử a_i+1

• Số phần tử của danh sách được gọi là chiều dài của danh sách. Một danh sách có chiều dài bằng 0 là một danh sách rỗng.

• Một tính chất quan trọng của danh sách là các phần tử có thể được sắp xếp tuyến tính theo vị trí của chúng trong danh sách.

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

Danh sách đặc là

• Một danh sách mà các phần tử được sắp xếp có thứ tự kế tiếp nhau trong bộ nhớ, đứng ngay sau vị trí phần tử a_i là vị trí phần tử a_i+1.

• Một danh sách mà các phần tử của nó có kiểu dữ liệu là int.

• Một danh sách các phần tử của nó được kết nối với nhau thông qua mối nối của nó.

• Tất cả đều sai

Mảng là:

• 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 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.

• 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ớ

• 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

ý tưởng phương pháp sắp xếp chọn tăng dần (select 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,ba...

• 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 bé hơn được cho lên vị trí trên.

• 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.

• 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.

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

• 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.

• 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ươ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.

ý tưởng phương pháp sắp xếp chèn (insertion sort) là:

• 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.

• 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.

• 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ương tự đối với phần tử nhỏ thứ hai,ba...

ý tưởng phương pháp sắp xếp nhanh (Quick sort) là:

• 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ương tự đối với phần tử nhỏ thứ hai,ba...

• 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 khoá).

• 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.

Phương pháp sắp xếp nhanh (Quick sort) chính là phương pháp:

• Phân đoạn

• Vun đống

• Trộn

• Chèn

ý tưởng phương pháp sắp xếp vun đống (Heap sort) là:

• 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ạo đống cho cây nhị phân (cây nhị phân đã được sắp xếp giảm dần).

• 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 khoá).

• Lần lượt tạo đống cho cây nhị phân (phần tử gốc có giá trị lớn nhất) và loại phần tử gốc ra khỏi cây đưa vào dãy sắp xếp

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

Cơ chế heap trong sắp xếp vun đống là:

• Cây nhị phân đầy đủ với tính chất giá trị của nút cha luôn lớn hơn giá trị hai nút con.

  Cây nhị phân đầy đủ với tính chất giá trị của nút cha lớn luôn lớn hơn giá trị các nút trong cây con trái và nhỏ hơn giá trị các nút trong cây con phải.

• Cây nhị phân hoàn chỉnh với tính chất giá trị của nút cha luôn lớn hơn giá trị hai nút con.

• Cây nhị phân hoàn chỉnh với tính chất giá trị của nút cha lớn luôn lớn hơn giá trị các nút trong cây con trái và nhỏ hơn giá trị các nút trong cây con phải.

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