Cấu trúc dữ liệu và giải thuật - IT05 (255)
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
Đoạn mã cài đặt hủy bỏ một phần tử đứng sau một phần tử q trong danh sách liên kết đơn:
void RemoveAfter ( LIST &Q , Node *q ){
Node *p;
if (q != NULL)
{
p = q -> next;
if (p != NULL)
{
if (p == Q.Tail)
{
q->next = NULL;
Q.Tail = q;
}
[1] ………………….
free(p);
}
}
else RemoveHead(Q);
}
Dòng lệnh cần thiết được đặt vào chỗ trống tại dòng số [1]:
A. q -> next = p -> next;
B. p = q;
C. q = p;
D. p -> next = q -> next;
Các thao tác cơ bản trên danh sách gồm thao tác gì:
A. bổ sung, loại bỏ, cập nhật
B. tách, ghép, …
C. tìm kiếm, sắp xếp, sao chép
D. Tất cả các thao tác trên
Để tiến hành tìm kiếm một phần tử trong danh sách liên kết đơn sử dụng phương pháp tìm kiếm gì?
A. Tìm kiếm tuyến tính và tìm kiếm nhị phân
B. Tìm kiếm nhị phân
C. Tất cả các đáp án đều đúng
D. Tìm kiếm tuyến tính
Trong một nút của danh sách liên kết đơn, thành phần infor là thành phần gì?
A. Cả hai phát biểu trên đều đúng
B. Để lưu trữ hay mô tả thông tin được lưu trữ trong nút của danh sách
C.
Cả hai phát biểu trên đều sai
D. Để lưu trữ địa chỉ của nút kế tiếp hoặc giá trị NULL nếu không liên kết đến phần tử nào
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
Đ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 biết kết quả của đoạn chương trình sau:
int F(int a[], int n)
{
if (n==1)
return a[0];
else
return 1 + F(a,n-1);
}
int main()
{
int a[] = {2, 3, 4, 5, 6};
printf("%d",F(a,5));
getch();
}
Cho đoạn chương trình:
void QuickSort( int a[ ], int L , int R )
{
int i,j,x;
x= a[(L+R)/2];
i =…;
j = ...;
do
{
while ( a[i] < x ) i++;
while ( a[j] > x ) j--;
if ( i <= j )
{
Hoanvi (a[i], a[j]);
i++; j--;
}
} while(i<j);
if (L<j) QuickSort(a,L,j);
if (i<R) QuickSort(a,i,R);
}
Điền giá trị nào vào đoạn …. cho đúng
A. i=0; j=n-1;
B. i=0; j=R;
C. i=L; j=n-1;
D. i=L; j=R;
Cho thuật toán tìm nhị phân không đệ quy sau:
int NrecBinarySearch( int M[], int N, int X)
{
int First = 0;
int Last = N -1;
while ( First <= Last)
{
int Mid = (First + Last)/2;
if ( X == M[Mid]) return Mid;
if ( X < M[Mid]) Last = Mid - 1;
else First = Mid + 1;
}
return -1;
}
Chọn câu đúng nhất trong trường hợp tốt nhất khi phần tử ở giữa của mảng có giá trị bằng X:
A. Số phép gán: Gmin = 3 Số phép so sánh: Smin = 2
B. Số phép gán: Gmin = 2 Số phép so sán: Smin = 3
C. Số phép gán: Gmin = 0 Số phép so sánh: Smin = 2
D. Số phép gán: Gmin = 2 Số phép so sánh: Smin = 2
Đoạn mã sau đây thực hiện yêu cầu xử lý gì?
int TK_SV_Ten_Tuyentinh(int n, SV ds[], char ht[]){ for(int i = 0; i<n; i++) if ( strcmp(ds[i].HoTen, ht)==0) break; if (i<n) return 1; else return -1;}
A. Thực hiện tìm kiếm trong danh sách ds có SV có mã là ht hay không? Nếu có trả lại giá trị 1 nếu không có trả lại giá -1
B. Thực hiện tìm kiếm trong danh sách (ds) có SV có tên là ht hay không? Nếu có thì trả lại giá trị là 1, ngược lại không có trả lại giá trị là -1, thuật toán sử dụng là thuật toán tìm kiếm tuyến tính
C. Thực hiện tìm kiếm trong danh sách ds có SV có mã là ht hay không? Nếu có trả lại giá trị 1 nếu không có trả lại giá -1, thuật toán sử dụng là thuật toán tìm kiếm nhị phân
D. Thực hiện tìm kiếm trong danh sách ds có SV có mã là ht hay không? Nếu có trả lại giá trị vị trí của phần tử tìm thấy nếu không có trả lại giá -1
Đoạn mã sau đây sử dụng thuật toán Sắp xếp 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]. DTB >x. DTB )) { ds[pos+ 1 ] = ds[pos]; pos--; } ds[pos+ 1 ] = x; //chèn x vào dãy } }
A. Quick Sort
B. Interchange Sort
C. Selection Sort
D. Insertion Sort
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
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 khai báo CTDL 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 ; };
Đâu là đoạn mã tìm kiếm CanBo theo mã cán bộ trong DSLK đơn
A. Node *TimCBMa(List Q,char k[]){ Node *p; for(p=Q.Head; p!=NULL; p=p->next) if(strcmp(p->info.ns,k)==0) break; return p;}
B. Node *TimCBMa(List Q,int k) { Node *p; for (p=Q.Head; p!= NULL ; p=p->next) if (p->info .mcb == k ) break ;
C. Node *TimCBMa( List Q,char k[]) { Node *p; for (p=Q. Head ; p!= NULL ; p=p-> next ) if (strcmp ( p-> info .hoten, k) ==0) break ; return p; }
D. void TimCBMa(List Q,char k[]){ Node *p; for(p=Q.Head; p!=NULL; p=p->next) if(p->mcb == k) break;}
Danh sách được cài đặt bằng cách nào:
A. Cài đặt bằng mảng
B. Cài đặt bằng danh sách liên kết
C. Cả hai đáp án đều sai
D. Cả hai đáp án đều đúng
Các thành phần của danh sách đơn gồm:
A. Dữ liệu (data)
B. Liên kết (link)
C. Số phần tử của danh sách (number)
D. Dữ liệu (data) và liên kết (link)
Đ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
{
Q.Head = new_element;
Q.Tail = Q.Head;
}
else//danh sách không rỗng
{
[1] ……………
[2] ……………
}
}
Đoạn mã còn thiếu để đặt vào dòn số [1] và [2].
A. Q.Head = new_element;
B. new_element -> next = Q.Head;
C. new_element -> next = Q.Head;
D. new_element -> next = NULL;
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);
