Cấu trúc dữ liệu và giải thuật - IT05 (255)
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
Để 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
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
Đ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;
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
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); }
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 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);
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 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
Đ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 đ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
Đị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 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; } }
Đ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;
Đ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ã 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
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
