Cấu trúc dữ liệu và giải thuật - IT05 (255)
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];
Cho đoạn mô tả sau:
Bước 1: Khởi đầu tìm kiếm trên tất cả các phần tử của dãy
(left = 0 và right = n - 1)
Bước 2: Tính middle = (left + right)/2. So sánh a[middle] với x. Có 3 khả năng:
a[middle] = x thì thông báo Tìm thấy => Dừng
a[middle] > x thì right = middle - 1
a[middle] < x thì left = middle + 1
Bước 3:
Nếu left <= right và quay lại bước 2 để tìm kiếm tiếp
Ngược lại thông báo không tìm thấy và dừng thuật toán
A. Các đáp án đưa ra đều sai
B. Mô tả thuật toán tìm kiếm tuyến tính
C. Mô tả thuật toán tìm kiếm nhị phân
D. Các đáp án trên đều đúng
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 tăng dần bằng thuật toán Selection Sort
A. 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];
B. 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];
C. 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 }}
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 }}
Các bước thực hiện tìm kiếm nhị phân phần tử x trên dẫy sắp xếp tăng dần được mô tả như sau:
Bước 1: Khởi đầu tìm kiếm trên tất cả các phần tử của dãy c left = …………… và right = ………………
Bước 2: Tính middle = (left + right)/2. So sánh a[middle] với x. Có 3 khả năng:
- a[middle] = x => Tìm thấy => Dừng
- a[middle] > x => tiếp tục tìm x trong dãy con mới với right = middle - 1 (tìm trong nửa đầu)
- a[middle] < x => tiếp tục tìm x trong dãy con mới với left = middle + 1 (tìm trong nửa cuối)
Bước 3:
- Nếu left <= right => dãy còn phần tử, tiếp tục quay lại bước 2 để tìm kiếm tiếp
- Ngược lại => Dãy hiện hành hết phần tử và dừng thuật toán
Giá trị cần điền vào dấu ………….. là bao nhiêu để thuật toán thực hiện đúng
A. n và 0
B. 0 và n-1
C. n-1 và 0
D. 0 và n
Các bước thực hiện tìm kiếm nhị phân phần tử x trên dẫy sắp xếp tăng dần được mô tả như sau:
Bước 1: Khởi đầu tìm kiếm trên tất cả các phần tử của dãy <=> left = 0 và right = n-1
Bước 2: Tính middle = (left + right)/2. So sánh a[middle] với x. Có 3 khả năng:
- a[middle] = x => Tìm thấy => Dừng
- a[middle] > x => tiếp tục tìm x trong dãy con mới với right = middle - 1 (tìm trong nửa đầu)
- a[middle] < x => tiếp tục tìm x trong dãy con mới với ............................ (tìm trong nửa cuối)
Bước 3:
- Nếu left <= right => dãy còn phần tử, tiếp tục quay lại bước 2 để tìm kiếm tiếp
- Ngược lại => Dãy hiện hành hết phần tử và dừng thuật toán
Giá trị cần điền vào dấu ………….. là bao nhiêu để thuật toán thực hiện đúng
A. right = midle + 1
B. right = middle - 1
C. left = middle - 1
D. left = middle + 1
Đoạn mã sau đây làm nhiệm vụ gì?
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];
ds[i] = tg; } } }
A. 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
B. 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
C. 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
D. 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
Đ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 = x;
p -> ….. = NULL;
return p;
}
Điền phần còn thiếu vào chỗ …………..
A. next
B. data
C. link
D. infor
Đoạn mã cài đặt hủy phần tử đầu của danh sách liên kết đơn:
void RemoveHead ( LIST &Q ){
Node *p;
if (Q.Head != NULL)
{
p = Q.Head;
[1] …………………..
free(p);
if ( Q.Head == NULL )
Q.Tail = NULL;
}
}
Dòng lệnh cần thiết được đặt vào chỗ trống tại dòng số [1]:
A. Q.Head -> next = Q.Head;
B. Q.Head = NULL;
C. Q.Head -> next = NULL;
D. Q.Head = Q.Head -> next;
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ã để sắp xếp danh sách Cán bộ theo thứ tự giảm dần của hệ số lương (hsl);
A. void SXCBThanhTien(List &Q) { Node *p,*q; CB tg; for(p=Q.Head; p!=NULL; p=p->next) for(q=p->next; q!=NULL; q=q->next) if(p->info.hsl > q->info.hsl) { tg = p->info; p->info = q->info; q->info = tg; } }
B. void SXCBThanhTien(List &Q) { Node *p=Q.Head,*q; CB tg; while(p!=NULL) { q=p->next; while(q!=NULL) if(p->info.pc > q->info.pc) { tg = p->info; p->info = q->info; q->info = tg; } } }
C. void SXCBThanhTien(List &Q) { Node *p,*q; CB tg; for(p=Q.Head; p!=NULL; p=p->next) for(q=p->next; q!=NULL; q=q->next) if(p->info.pc < q->info.pc) { tg = p->info; p->info = q->info; q->info = tg; } }
D. void SXCBThanhTien(List &Q) { Node *p,*q; CB tg; for(p=Q.Head; p!=NULL; p=p->next) for(q=p->next; q!=NULL; q=q->next) if(p->info.hsl < q->info.hsl) { tg = p->info; p->info = q->info; q->info = tg; } }
Định nghĩa cấu trúc dữ liệu của danh sách liên kết đơn được mô tả như sau:
struct Node{
int Key;
Node *next;
}OneNode;
Trong đó, khai báo Node *next; dùng để mô tả
A. Con trỏ trỏ tới phần dữ liệu cuối của danh sách
B. Con trỏ trỏ tới phần dữ liệu
C. Vùng liên kết quản lý địa chỉ phần tử kế tiếp
D. Vùng liên kết quản lý địa chỉ phần tử kế tiếp của phần tử cuối
Cho đoạn mã sau:
struct CB{ int mcb; char hoten[20]; char ns[12]; float hsl,pc,tt;};struct Node{ CB info; struct Node *next;};
struct List { Node *head , *tail ; };
Khai báo Cấu trúc dữ liệu trên là khai báo CTDL dạng gì?
A. Danh sách liên kết vòng
B. Danh sách liên kết đơn
C. Danh sách liên kết đôi
D. Danh sách liên kết vòng đôi
Đoạn mã cài đặt chèn thêm một phần tử mới vào đầu của danh sách liên kết đơn:
void insertFirst ( LIST &Q, Node *new_element ){
if ( Q.Head == NULL ) //nếu danh sách rỗng
{
[1] ……..
[2] ……..
}
else//danh sách không rỗng
{
new_element -> next = Q.Head;
Q.Head = new_element;
}
}
Đoạn mã còn thiếu để đặt vào dòn số [1] và [2].
A. Q.Tail = Q.Head;
B. Q.Tail = NULL;
C. Q.Head = new_element;
D. Q.Head = Q.Head;
Cho khai báo cấu trúc như sau :
struct CB { int mcb ; char hoten [ 20 ]; char ns [ 12 ]; float hsl , pc , tt ; }; struct Node { CB info ; struct Node * next ; };
struct List { Node *head , *tail ; };
Đoạn mã sau đây thực hiện yêu cầu xử lý gì?
Node *TimCBMa( List Q, int k) { Node *p; for (p=Q. Head ; p!= NULL ; p=p-> next ) if (p-> info . mcb ==k) break ; return p; }
A. Thực hiện tìm kiếm trong DSLK đôi chứa các CanBo xem có CanBo nào có mã là k hay không? Trả lại thông tin nút chứa cán bộ nếu tìm thấy ngược lại trả lại giá trị NULL
B. Thực hiện tìm kiếm Cán bộ theo mã cán bộ
C. Thực hiện tìm kiếm trong DSLK đơn có chứa Cán bộ với tên là k nào đó hay không?
D. Thực hiện tìm kiếm trong DSLK đơn chứa các CanBo xem có CanBo nào có mã là k hay không? Trả lại thông tin nút chứa cán bộ nếu tìm thấy ngược lại trả lại giá trị NULL
Các loại danh sách liên kết gồm:
A. Danh sách liên kết đơn và danh sách liên kết kép
B. Danh sách liên kết kép và danh sách liên kết vòng
C. Danh sách liên kết đơn và danh sách liên kết vòng
D. Danh sách liên kết đơn, danh sách liên kết kép và danh sách liên kết vòng
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);
Đ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 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];
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ã để sắp xếp danh sách Cán bộ theo thứ tự tăng dần của hệ số lương (hsl);
A. void SXCBThanhTien(List &Q) { Node *p,*q; CB tg; for(p=Q.Head; p!=NULL; p=p->next) for(q=p->next; q!=NULL; q=q->next) if(p->info.hsl > q->info.hsl) { tg = p->info; p->info = q->info; q->info = tg; } }
B. void SXCBThanhTien(List &Q) { Node *p,*q; CB tg; for(p=Q.Head; p!=NULL; p=p->next) for(q=p->next; q!=NULL; q=q->next) if(p->info.hsl < q->info.hsl) { tg = p->info; p->info = q->info; q->info = tg; } }
C. void SXCBThanhTien(List &Q) { Node *p=Q.Head,*q; CB tg; while(p!=NULL) { q=p->next; while(q!=NULL) if(p->info.pc > q->info.pc) { tg = p- >info; p->info = q->info; q->info = tg; } } }
D. void SXCBThanhTien(List &Q) { Node *p,*q; CB tg; for(p=Q.Head; p!=NULL; p=p->next) for(q=p->next; q!=NULL; q=q->next) if(p->info.pc < q->info.pc) { tg = p->info; p->info = q->info; q->info = tg; } }
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ã để in ra màn hình thông tin đầy đủ của các Cán Bộ có trong danh sách liên kết.
A. void InDSCanBo (List Q) { Node *p; for (p=Q.Head; p!= NULL ; p=p->next) if(p->info.hsl > 4) { 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); }
B. void InDSCanBo (List Q) { Node *p; for (p=Q.Head; p!= NULL ; p=p->next) System.out.print(“%15s”, p->info.hoten);
C. void InDSCanBo (List Q) { float s; for (p=Q.Head; p!= NULL ; p=p->next) s = s + p->info.hsl;
D. 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); }
Mỗi nút trong danh sách đơn gồm có mấy phần:
A. 3 phần
B. 4 phần
C. 5 phần
D. 2 phần
