WorksheetsCS316 Chapter 2 Solid Linked list
Total questions: 20
Worksheet time: 10mins
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) a1a2…an 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ử ai thì ta sẽ biết được vị trí của các phần tử ai+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ử ai là vị trí phần tử ai+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
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ó khoá 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ó khoá 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.
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, Bubble sort
Qucick sort, Insert 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ứ hai là:
{0 1 2 6 5 7 9 3 4 8}
{0 1 3 6 5 7 9 2 8 4}
{0 1 2 6 5 7 9 3 8 4}
{0 1 2 3 4 5 6 7 8 9}
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 6 5 7 9 8 4}
{0 1 2 3 5 7 9 4 8 6}
{0 1 2 3 4 5 6 7 8 9}
{0 1 2 3 5 7 9 6 8 4}
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 4 7 9 6 8 5}
{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 5 6 7 8 9}
Cho dãy số: "5 1 4 2 7 3" và các bước sắp xếp sau:
Bước 1: 1 5 4 2 7 3”
Bước 2: 1 4 5 2 7 3
Bước 3: 1 2 4 5 7 3
Bước 4: 1 2 4 5 7 3
Bước 5: 1 2 3 4 5 7
Các bước trên dựa theo giải thuật sắp xếp nào?
Bubble sort
Insert sort
Select sort
Quick sort
Cho đoạn chương trình sau:
int a, *p, *q;
float *t;
a=5; p=&a;
p=q;
t=p;
printf(“%d%f”,a,t);
Dịch và chạy đoạn chương trình trên, nhận được kết quả nào sau đây.
5-12
5
Chương trình lỗi
Kết quả khác
Để thực hiện tìm kiếm nhị phân thì mảng dữ liệu phải là:
Mảng gồm các số nguyên dương
Mảng phải được sắp xếp tăng dần hoặc giảm dần.
Mảng không chứa số âm.
Tất cả đều đúng.
Để thực hiện việc tìm giá trị lớn nhất trong mảng thì biến max được khởi gán giá trị nào sau đây:
Max = 0
Max bằng phần tử đầu tiên của mảng
Max =-9999
Tất cả đều đúng
