Cấu trúc dữ liệu và giải thuật - IT05 (255)
Đoạn mô tả này thuộc thuật toán nào:
Bước 1: i = 0
Bước 2: tính các giá trị j = i + 1
Bước 3: Trong khi j<n thực hiện
- nếu a[j] < a[i] thì hoán đổi a[i] với a[j]
- j = j + 1;
Bước 4: i = i +1
nếu i<n-1 thì lặp lại bước 2, ngược lại thì dừng
B. Tìm kiếm tuyến tính
C. Sắp xếp chèn trực tiếp
D. Sắp xếp đổi chỗ trực tiếp
Cho mảng a gồm các phẩn tử có giá trị như sau:
3126
Số lần hoán vị 2 phần tử khác nhau khi áp dụng thuật toán đổi chỗ trực tiếp (Interchange Sort) để sắp xếp mảng tăng dần là:
Cho hàm tìm kiếm tuyến tính trong mảng 1 chiều có n phần tử
int Search( int a[], int n, int x)
{
int i;
for(i=0; i<n; i++)
if(a[i] == x) return i;
return(-1);
}
Chọn phát biểu đúng nhất trong các phát biểu sau
A. Hàm trả về vị trí phần tử đầu tiên có giá trị bằng x, ngược lại trả về -1
B. Hàm luôn luôn trả về vị trí phần tử cuối cùng có giá trị bằng x
C. Hàm trả về vị trí phần tử cuối cùng có giá trị bằng x, ngược lại trả về n
D. Hàm trả về vị trí phần tử cuối cùng có giá trị bằng x, ngược lại trả về -1
Để sắp xếp các phần tử của danh sách liên kết đơn sử dụng phương án nào?
A. Tất cả các đáp án đều sai
B. Hoán vị nội dung của phần tử
C. Cả hai phương án trên đều đúng
D. Thay đổi mối liên kết của phần tử
Các trường hợp thực hiện hủy phần tử khỏi danh sách liên kết đơn gồm:
A. Hủy phần tử đầu danh sách, hủy phần tử đứng sau phần tử q và hủy phần tử có giá trị xác định k
B. Hủy phần tử có giá trị xác định k và hủy phần tử đứng sau phần tử q
C. Hủy phần tử đầu danh sách và hủy phần tử đứng sau phần tử q
D. Hủy phần tử đầu danh sách và hủy phần tử có giá trị xác định k
Danh sách liên kết là gì?
A. là tập hợp các phần tử liên kết móc nối liên tiếp với nhau, có kiểu truy cập ngẫu nhiên. Mỗi phần tử là một nút.
B. Cả hai phát biểu đều đúng
C. Cả hai phát biểu đều sai
D. là tập hợp các phần tử liên kết móc nối liên tiếp với nhau, có kiểu truy cập tuần tự. Mỗi phần tử là một nút.
Cho khai báo CTDL như sau:
struct CB { int mcb; char hoten[20]; char ns[12]; float hsl,pc,thanhtien ; }; struct Node { CB info; struct Node *next; };
struct List { Node *head , *tail ; };
Đâu là đoạn mã tính tổng tiền lương của các CanBo trong DSLK đơn.
A. float TinhTongLuong (List Q ) { Node *p; float s = 0; for (p=Q.Head; p!= NULL ; p=p->next) s = s + p->info.hsl;
B. float TinhTongLuong (List Q ) { Node *p; float s = 0; for (p=Q.Head; p!= NULL ; p=p->next) s = s + p->info.pc;
C. float TinhTongLuong (List Q ) { Node *p; float s = 0; for (p=Q.Head; p!= NULL ; p=p->next) s = s + p->info.thanhtien;
D. void TinhTongLuong (List Q) { Node *p; for (p=Q.Head; p!= NULL ; p=p->next) printf(“%7.1f”, p->info.tt);
Cho thông tin của SV gồm: MaSV, HoTen, Tuoi, DTB
Đâu là đoạn mã để Sắp xếp danh sách SV theo ĐTB giảm dần bằng thuật toán Selection Sort
A. void SXDSV_InsertionSort( int n, SV ds[]){ int pos,i; SV x; for(i=1;i<n;i++) { x = ds[i]; pos = i-1; while((pos>=0)&&(ds[pos].DTB<x.DTB)) { ds[pos+1] = ds[pos]; pos--; } ds[pos+1] = x; //chèn x vào dãy }}
B. void SXDSSV( int n, SV ds[]) { int max , i, j; SV tg; for ( i=0 ; i<n-1 ; i++ ) { max = i; for ( j=i+1 ; j<n ; j++ ) if ( ds[j].DTB > ds[ max ].DTB ) max = j; if ( max != i ) { tg = ds[ max ]; ds[ max ] = ds[i];
C. void SXDSSV( int n, SV ds[]) { int min, i, j; SV tg; for ( i=0 ; i<n-1 ; i++ ) { min = i; for ( j=i+1 ; j<n ; j++ ) if ( ds[j].DTB < ds[min].DTB ) min = j; if ( min != i ) { tg = ds[min]; ds[min] = ds[i];
D. void SXDSV_InsertionSort( int n, SV ds[]){ int pos,i; SV x; for(i=1;i<n;i++) { x = ds[i]; pos = i-1; while((pos>=0)&&(ds[pos].DTB>x.DTB)) { ds[pos+1] = ds[pos]; pos--; } ds[pos+1] = x; //chèn x vào dãy }}
Cho dãy sau: 42, 23, 74, 11, 65, 58. Dùng phương pháp sắp xếp đổi chỗ trực tiếp (Interchange Sort) để sắp xếp tăng dần, sau 4 lần lặp kết quả của dãy là thế nào?
A. 11, 23, 42, 74, 65, 58
B. 11, 23, 42, 65, 58, 74
C. 11, 23, 42, 58, 65, 74
D. 11, 23, 42, 58, 74, 65
Đoạn mã khởi tạo danh sách rỗng sau:
void init( List &Q ){
Q.Head = ......;
Q.Tail = NULL;
}
Phần còn thiếu điền vào dấu ……. là gì
A. NILL
B. O
C. NULL
D. Không phải các đáp án trên
Cho Danh sách liên kết đơn chứa danh sách Cán Bộ (CB), Đoạn mã sau đây thực hiện gì?
void InDSCanBo (List Q)
{
Node *p;
for (p=Q.Head; p!= NULL ; p=p->next)
{
System.out.print(“%5d”, p->info.mcb);
System.out.print(“%15s”, p->info.hoten);
System.out.print(“%10s”, p->info.ns);
System.out.print(“%7.1f”, p->info.hsl);
System.out.print(“%7.0f”, p->info.pc);
}
}
A. Nhập vào từ bàn phím thông tin đầy đủ của các cán bộ vào danh sách Q
B. In thông tin của các cán bộ có trong danh sách mà có hệ số lương lớn hớn 3.5
C. In đầy đủ thông tin tất cả các cán bộ đang chứa trong danh sách Q
D. In họ tên và mã của các cán bộ đang chứa trong danh sách
Cho thông tin của Hang Hoa gồm: mã hàng, tên hàng, số lượng và đơn giá.
Đâu là đoạn mã khai báo Cấu trúc dữ liệu dạng danh sách liên kết đơn để lưu trữ danh sách Hang Hoa
A. struct HH { int mHang ; char tenHang [20]; float soLuong, donGia ; }; struct Node { HH info; struct Node *next, *pre; };
B. struct HH{ int mHang; char tenHang [20]; float soLuong, donGia;};struct List{ HH *head, *tail;};
C. struct HH { int mHang ; char tenHang [20]; float soLuong, donGia ; }; struct Node { HH info; struct Node *next; };
D. struct HH { int mHang ; char tenHang [20]; float soLuong, donGia ; }; HH ds[10];
Đoạn mã để tạo ra nút mới có thành phần là x trong danh sách liên kết đơn với mỗi nút gồm hai thành phần (infor, next) sau:
Node* get_node( Data x ){
Node *p;
p = (Node*)malloc(sizeof(Node));
if ( p == NULL )
{
printf(“Ko du bo nho”);
exit(1);
}
p -> infor = ……;
p -> next = NULL;
return p;
}
Điền phần còn thiếu vào chỗ …………..
Cho khai báo CTDL như sau:
struct CB { int mcb; char hoten[20]; char ns[12]; float hsl,pc ; }; struct Node { CB info; struct Node *next; };
struct List { Node *head , *tail ; };
Đâu là đoạn mã để tính tổng phụ cấp của tất cả các cán bộ và in ra màn hình?
A.
void TinhPC (List Q) { Node *p; float s=0; for (p=Q.Head; p!= NULL ; p=p->next) s = s + p->info.pc; }
B.
void TinhPC (List Q) { Node *p; float s=0; for (p=Q.Head; p!= NULL ; p=p->next) printf(“%10.0f”, p->info.pc) }
C.
void TinhPC (List Q) { Node *p; float s=0; for (p=Q.Head; p!= NULL ; p=p->next) s = s + p->info.pc; printf(“\n Tong phu cap:%f”, s);
D.
void TinhPC (List Q) { Node *p; float s=0; for (p=Q.Head; p!= NULL ; p=p->next) s = s + p->info.hsl; printf(“\n Tong phu cap:%f”, s);
Cho thông tin của SV gồm: MaSV, HoTen, Tuoi, DTB
Đâu là đoạn mã để Sắp xếp danh sách SV theo Tuổi tăng dần bằng thuật toán Selection Sort
A. void SXDSV_InsertionSort( int n, SV ds[]){ int pos,i; SV x; for(i=1;i<n;i++) { x = ds[i]; pos = i-1; while((pos>=0)&&(ds[pos].Tuoi<x.Tuoi)) { ds[pos+1] = ds[pos]; pos--; } ds[pos+1] = x; //chèn x vào dãy }}
B. void SXDSV_InsertionSort( int n, SV ds[]){ int pos,i; SV x; for(i=1;i<n;i++) { x = ds[i]; pos = i-1; while((pos>=0)&&(ds[pos].Tuoi>x.Tuoi)) { ds[pos+1] = ds[pos]; pos--; } ds[pos+1] = x; //chèn x vào dãy }}
C. void SXDSSV( int n, SV ds[]) { int min, i, j; SV tg; for ( i=0 ; i<n-1 ; i++ ) { min = i; for ( j=i+1 ; j<n ; j++ ) if ( ds[j].Tuoi < ds[min].Tuoi ) min = j; if ( min != i ) { tg = ds[min]; ds[min] = ds[i];
D. void SXDSSV( int n, SV ds[]) { int max , i, j; SV tg; for ( i=0 ; i<n-1 ; i++ ) { max = i; for ( j=i+1 ; j<n ; j++ ) if ( ds[j].Tuoi > ds[ max ].Tuoi) max = j; if ( max != i ) { tg = ds[ max ]; ds[ max ] = ds[i];
Đoạn mã sau đây thực hiện nhiệm vụ gì
void SXDSV_InsertionSort( int n, SV ds[]) { int pos,i; SV x; for (i= 1 ;i<n;i++) { x = ds[i]; pos = i- 1 ; while ((pos>= 0 )&&(ds[pos].Tuoi>x.Tuoi)) { ds[pos+ 1 ] = ds[pos]; pos--; } ds[pos+ 1 ] = x; //chèn x vào dãy } }
A. Thực hiện sắp xếp danh sách SV theo Tuoi giảm dần bằng thuật toán Insertion
B. Thực hiện sắp xếp danh sách SV theo Tuoi giảm dần bằng thuật toán Selection
C. Thực hiện sắp xếp danh sách SV theo Tuoi tăng dần bằng thuật toán Insertion
D. Thực hiện sắp xếp danh sách SV theo Tuoi tăng dần bằng thuật toán Selection
Cho thuật toán sắp xếp Bubble Sort như sau:
void BubbleSort( int M[], int N)
{
for( int i = 0; i< N-1; i++)
for( int j = N-1; j>I; j--)
if( M[j] <M[j-1]) Swap( M[j], M[j-1]);
return ;
}
Chọn câu đúng nhất cho hàm Swap:
A. void Swap( int *X, int *Y)
B. void Swap( int X, int Y)
C. void Swap( floatX, float Y)
D. void Swap( int &X, int &Y)
Cho dãy sau: 42, 23, 74, 11, 65, 58. Dùng phương pháp sắp xếp phân hoạch (Quick Sort), điểm chốt a[middle] ban đầu là:
A. Các đáp án đưa ra đều không đúng
B. a[middle] = 11
C. a[middle] = 23
D. a[middle] = 74
Cho dãy 10, 5, 7, 3, 9, 2, 15, 1. Cho biết kết quả sau lần duyệt thứ nhất của thuật toán sắp xếp tăng dần bằng QuickSort
A. 1, 2, 3, 5, 9, 7, 15, 10
B. 1, 2, 3, 5, 7, 9, 15, 10
C. 1, 2, 5, 7, 9, 3, 15, 10
D. 1, 2, 3,7,9, 5, 15, 10
Một chương trình cài đặt trên máy tính được xác định bởi thành phần nào
A. Cấu trúc dữ liệu
B. Cả hai thành phần
C. Không phải là các thành phần
D. Thuật toán
