Chương 6 : Các thuật toán sắp xếp

Câu 152: Nếu sắp xếp các phần tử theo kinh nghiệm của người chơI bài. Thì đó là kiểu sắp xếp?
a. Thêm dần
Câu 153: Bảng khóa đựoc duyệt từ đáy lên đỉnh. Dọc đương nếu gặp hai khoá kế cận ngược thứ tự thì đổi chỗ chúng cho nhau. Đó là giải thuật sắp xếp nào?
a .Sắp xếp đổi chỗ
Câu 154: Ý tưởng phương pháp sắp xếp nổi bọt (bubble sort) là:
a. So sánh hai phần tử kề nhau nếu chưa đúng thì đổi chỗ
Câu 156: Ý tưởng phương pháp sắp xếp chọn (select sort)
a. Chọn phần tử bé nhất xếp vào vị trí thứ nhất,tương tự đối với phần tử nhỏ thứ hai,ba..
Câu 157: cho dãy a = (12,2,8,5,1,6,4,15)
các bước sắp xếp như sau:
"Bước 1: 1 2 8 5 12 6 4 15"
"Bước 2: 1 2 8 5 12 6 4 15"
"Bước 3: 1 2 4 5 12 6 8 15"
"Bước 4: 1 2 4 5 12 6 8 15"
"Bước 5: 1 2 4 5 6 12 8 15"
"Bước6: 1 2 4 5 6 8 12 15"
"Bước 7: 1 2 4 5 6 8 12 15"
Các bước trêndựa theo phương pháp sắp xếp kiểu gì:
a. Sắp xếp chọn(selection sort)
Câu 158: cho dãy a = (12,2,8,5,)"
"các bước sắp xếp như sau:"
"bước 1: 2,12,8,5"
"bước 2: 2,8,12,5"
"bước 3:2,8,5,12"
"bước 4:2,8,5,12"
"buớc5:2,5,8,12"
"Các bước sắp xếp trên dựa vào tư tưởng của sắp xếp"
a. Sắp xếp nổi bọt(bubble sort)
Câu 159: Cho dãy a= (32, 17,49,98,06,25,53,61)
Khi sử dụng thuật toán sắp xếp chọn đến bước mấy ta được dãy số sau: (06,17,25,32,98,49,53,61).
a. Bước 4
Câu 160: Cho dãy a= (32, 17,49,98,06,25,53,61)
Khi sử dụng thuật toán sắp xếp nổi bọt đến bước mấy ta được dãy số sau:
a= (06,17,32,25,49,98,53,61)
a. Bước 2
Câu 161: Cho dãy a= (32, 17,49,98,06,25,53,61)
Khi sử dụng thuật toán sắp xếp nổi bọt đến bước mấy ta được dãy số sau:
a= (06,17,25,32,49,53,98,61)
a. Bước 3
Câu 162 : Độ phức tạp của thuật toán sắp xếp chọn là :
a. O(n2)
Câu 163: Độ phức tạp của thuật toán sắp xếp chèn là :
a. O(n2)
Câu 164: Độ phức tạp của thuật toán sắp xếp nổi bọt là :
a. O(n2)
Câu 165: Độ phức tạp của thuật toán sắp xếp quick sort là :
a. O(NlogN)
Câu 166: Độ phức tạp của thuật toán sắp xếp heap sort là :
a. O(NlogN)
Câu 167: Ý tưởng của thuật toán Quicksort là :
c. Dựa vào tư tưởng chia để trị
Câu 168: Ý tưởng của thuật toán Heapsort là :
a. Thực hiện sắp xếp thông qua việc tạo các heap, trong đó heap là 1 cây nhị phân hoàn chỉnh có tính chất là khóa ở nút cha bao giờ cũng lớn hơn khóa ở các nút con.
Câu 169 : Ý tưởng của thuật toán Merge sort là :
a. Trộn 2 danh sách đã được sắp xếp thành 1 danh sách mới cũng được sắp.
Câu 170: Sắp xếp:
a. Là quá trình bố trí lại các phần tử của 1 tập hợp theo thứ tự nào đó
Câu 171: Các giải thuật sắp xếp được chia làm mấy loại:
a. 2
Câu 172: Giải thuật sắp xếp mà được cài đặt càng đơn giản thì :
a. Không hiệu quả vì phải sử dụng nhiều thao tác
Câu 173: Khi sử dụng bài toán sắp xếp đối với các tập dữ liệu ít phần tử nên sử dụng:
a. Giải thuật sắp xếp được cài đặt đơn giản.
Câu 174: Giải thuật sắp xếp mà được cài đặt càng phức tạp thì :
a. Hiệu quả hơn về mặt tốc độ.
Câu 175: Khi sử dụng bài toán sắp xếp đối với các tập dữ liệu nhiều phần tử nên sử dụng:
a. Giải thuật sắp xếp được cài đặt phức tạp.
Câu 176: Các đối tượng dữ liệu cần sắp xếp thường có nhiều thuộc tính, và ta cần chọn một thuộc tính làm gì để sắp xếp dữ liệu theo đối tượng này.
a. Khóa
Câu 177: Một vấn đề nữa cần phải chú ý khi thực hiện sắp xếp là :
a. Tính ổn định của giải thuật sắp xếp.
Câu 178*: Đoạn chương trình sau mô tả giải thuật sắp xếp nào?
void selection_sort(){
int i, j, k, temp;
for (i = 0; i< N; i++){
k = i;
for (j = i+1; j < N; j++){
if (a[j] < a[k]) k = j;
}
temp = a[i]; a[i] =a [k]; a[k] = temp;
}
}
a. Giải thuật sắp xếp chọn.
Câu 179*: Đoạn chương trình sau mô tả giải thuật sắp xếp nào?
void insertion_sort(){
int i, j, k, temp;
for (i = 1; i< N; i++){
temp = a[i];
j=i-1;
while ((a[j] > temp)&&(j>=0)) {
a[j+1]=a[j];
j--;
}
a[j+1]=temp;
}
}
a. Giải thuật sắp xếp chèn.
Câu 180*: Đoạn chương trình sau mô tả giải thuật sắp xếp nào?
void bubble_sort(){
int i, j, temp, no_exchange;
i = 1;
do{
no_exchange = 1;
for (j=n-1; j >= i; j--){
if (a[j-1] > a[j]){
temp=a[j-1];
a[j-1]=a[j];
a[j]=temp;
no_exchange = 0;
}
}
i++;
} until (no_exchange || (i == n-1));
}
a. Giải thuật sắp xếp nổi bọt.
Câu 181*: Đoạn chương trình sau mô tả giải thuật sắp xếp nào?
void quick(int left, int right) {
int i,j;
int x,y;
i=left; j=right;
x= a[left];
do {
while(a[i]<x && i<right) i++;
while(a[j]>x && j>left) j--;
if(i<=j){
y=a[i];a[i]=a[j];a[j]=y;
i++;j--;
}
}while (i<=j);
if (left<j) quick(left,j);
if (i<right) quick(i,right);
}
a. Giải thuật sắp xếp quick sort
Câu 182*: Đoạn chương trình sau mô tả giải thuật sắp xếp nào?
void merge(int *c, int cl, int *a, int al, int ar, int *b, int bl, int br){
int i=al, j=bl, k;
for (k=cl; k< cl+ar-al+br-bl+1; k++){
if (i>ar){
c[k]=b[j++];
continue;
}
if (j>br){
c[k]=a[i++];
continue;
}
if (a[i]<b[j]) c[k]=a[i++];
else c[k]=b[j++];
}
}
a. Giải thuật sắp xếp merge sort.
Câu 183*: Nhược điểm của Quick sort là :
a. Là hoạt động rất kém hiệu quả trên những dãy đã được sắp sẵn.
Câu 184*: Thủ tục của thuật toán sắp xếp chèn sử dụng mấy vòng lặp?
a. 2
Câu 185* : Để cài đặt giải thuật Quicksort, trước hết ta xây dựng một thủ tục để sắp một phân đoạn của dãy. Thủ tục này là 1 thủ tục sử dụng phương pháp nào?
a. Đệ qui.
a. 2.
Câu 187*: Đối với thuật toán heapsort việc đầu tiên cần làm là:
a. Tạo được 1 heap từ 1 dãy phần tử cho trước.
Câu 188*: Thủ tục sau mô tả thao tác nào?
void SetupHeap(int a[], int k, int n) // điều chỉnh phần tử thứ k
{
int x=a[k];
while (k<n/2){
int j=2*k+1;
if (j+1<n && a[j]<a[j+1]) j++;
if (x>a[j]) break;
a[k]=a[j];k=j;
}
a[k]=x;
}
a. Setup heap.
Câu 189*: Thủ tục sau mô tả thao tác nào?
void MakeHeap(int a[], int n){ // tạo đống
for (int i=n/2-1;i>=0;i--)
SetupHeap(a, i, n);
}

a. Make heap.
Câu 190*: Thủ tục sau mô tả thao tác nào?
void Heapsort()
{
int tmp;
makeheap(a,n)
for (int i=n-1;i>0;i--){
tmp=a[0];a[0]=a[i];a[i]=tmp;
setupHeap(a,0,i);
}
}
a. Heap sort.
Câu 191*: Ưu điểm của thuật toán Heapsort so với Quick sort:
a. Là thời gian thực hiện thuật toán luôn là O(NlogN) trong mọi trường hợp, bất kể dữ liệu đầu vào có tính chất như thế nào.
Câu 192*: Trong mọi trường hợp cả 2 thuật toán heap sort và merge sort đều có thời gian là :
a. O(NlogN).
Câu 193**:
int remove_node(){
int temp;
temp=a[0];
a[0]=a[m];
m--;
downheap(0);
return temp;
}
Trong đoạn thủ tục trên , hàm remove() sẽ trả về giá trị là:
a. Nút gốc của heap.
Câu 194**:
void downheap(int k){
int j, x;
x=a[k];
while (k<=(m-2)/2){
j=2*k+1;
if (j<m-1) if (a[j]<a[j+1]) j++;
if (x>=a[j]) break;
a[k]=a[j]; k=j;
}
a[k]=x;
}
Thủ tục trên mô tả thao tác nào trên heap?
a. Chỉnh lại heap khi nút k không thoả mãn định nghĩa heap.
Câu 195**: Thủ tục sau mô tả thao tác:
void upheap(int m){
int x;
x=a[m];
while ((a[(m-1)/2]<=x) && (m>0)){
a[m]=a[(m-1)/2];
m=(m-1)/2;
}
a[m]=x;
}

void insert_heap(int x){
a[m]=x;
upheap(m);
m++;
}
a. Để chèn một phần tử x vào 1 heap đã có k phần tử
Câu 196**: Đối với đoạn chương trình sau:
void bubble_sort(){
int i, j, temp, no_exchange;
i = 1;
do{
no_exchange = 1;
for (j=n-1; j >= i; j--){
if (a[j-1] > a[j]){
temp=a[j-1];
a[j-1]=a[j];
a[j]=temp;
no_exchange = 0;
}
}
i++;
} until (no_exchange || (i == n-1));
}
Sau lần duyệt đầu tiên cần khoảng:
a. N-1 phép so sánh.
Câu 197**: Đoạn thủ tục sau mô tả:
void quick(int left, int right) {
int i,j;
int x,y;
i=left; j=right;
x= a[left];
do {
while(a[i]<x && i<right) i++;
while(a[j]>x && j>left) j--;
if(i<=j){
y=a[i];a[i]=a[j];a[j]=y;
i++;j--;
}
}while (i<=j);
if (left<j) quick(left,j);
if (i<right) quick(i,right);
}
a. Phân đoạn được giới hạn bởi 2 tham số là left và right cho biết chỉ số đầu và cuối của phân đoạn.

Câu 19**8: Trong 1 heap, các phần tử có chỉ số [n/2],…,n-1 được gọi là :
a. Nút lá
Câu 199**: Để thực hiện sắp xếp trộn thì 2 dãy được trộn không phải là 2 dãy riêng biệt, mà nằm ở vị trí nào?
a. Trên cùng 1 mảng.
Câu 200**: Đoạn chương trình sau mô tả thuật toán Merge sort sử dụng:
void merge_sort(int *a, int left, int right){
int middle;
if (right<=left) return;
middle=(right+left)/2;
merge_sort(a, left, middle);
merge_sort(a, middle+1, right);
merge(a, left, middle ,right);
}
a. Đệ quy