Cấu trúc dữ liệu và giải thuật - IT05 (255)
Cho dãy số sau: 30, 18, 35, 17, 40, 16, 32, 31, 43, 19. Cho biết kết quả khi duyệt cây được tạo lần lượt từ các phần tử trên bằng phương pháp duyệt RNL(Right Node Left):
A. 16, 17, 19, 18, 31, 32, 43, 40, 35, 30
B. 30, 18, 35, 17, 40, 16, 32, 31, 43, 19
C. 30, 35, 40, 43, 32, 31, 18, 19, 17, 16
D. 43, 40, 35, 32, 31, 30, 19, 18, 17, 16
Tổng các phần tử trên một hàng hoặc của một cột trong ma trận kề của đồ thị vô hướng G = <V,E> đúng bằng
A. Số cạnh liên thuộc với đỉnh của cột hoặc hàng đó
B. Hai lần số cạnh của đồ thị
C. Một nửa số cạnh của đồ thị
D. Tổng bán đỉnh bậc ra của tất cả các đỉnh
Tổng các phần tử hàng i, cột j của ma trận kề đồ thị vô hướng G = <V,E> đúng bằng
A. Hai lần số bậc của đỉnh i, đỉnh j
B. Bậc của đỉnh i, đỉnh j
C. Một nửa số bậc của đỉnh i, đỉnh j
D. Cả ba phương án đều sai
Cho khai báo cấu trúc đồ thị dạng danh sách cạnh như sau:
struct Canh
{
int dd,dc;
float ts;
};
struct DoThiCanh
{
int m;
Canh ds[max];
};
Đâu là đoạn mã để liệt kê danh sách tất cả các cạnh hiện có của đồ thị
A. void XuLy(DoThiCanh G)
B. void XuLy(DoThiCanh G,int k)
C. void XuLy(DoThi G, int k){ int i,j; printf("\n Cac dinh ke cua %d la:",k); for(i=1;i<=G.n;i++) if(G.C[k][i]>0) printf("%7d",i);}
D. void XuLy(DoThi G){ printf("\n Ma tran trong so la:\n"); for(int i =1; i<=G.n; i++) { for(int j=1;j<=G.n;j++) printf("%8.1f",G.C[i][j]); printf("\n"); }}
Ngăn xếp còn được gọi là danh sách
A. Cả hai đáp án đều sai
B. Cả hai đáp án đều đúng
C. FIFO
D. LIFO
Cho khai báo Stack như sau:
struct Stack
{
int top
int nut[max];
};
Cho biết phần tử đỉnh hiện tại của Stack là bao nhiều?
int a[] = {4, 5, 6, 7, 8};
int n = 5;
Stack s;
for(int i = 0; i<n; i++)
push(s, a[i]);
Cho khai báo Stack như sau:
struct Stack
{
char color[15];
int nut[max];
};
Cho biết kết quả giá trị được in ra màn hình là gì?
Push(s, “Red”);
Push(s, “Green”);
Push(s, “Blue”);
printf(“\n%15s”, Pop(s));
printf(“\n%15s”, Pop(s));
A. Red
B. Blue
C. Red
D. Green
Cho dãy số sau: 30, 18, 35, 17, 40, 16, 32, 31, 43, 19. Cho biết kết quả khi duyệt cây được tạo lần lượt từ các phần tử trên bằng phương pháp duyệt NLR (Node Left Right):
A. 30, 35, 40, 43, 32, 31, 18, 19, 17, 16
B. 30, 18, 35, 17, 40, 16, 32, 31, 43, 19
C. 30, 18, 17, 16, 19, 35, 32, 31, 40, 43
D. 16, 17, 18, 19, 30, 31, 32, 35, 40, 43
Các trường hợp có thể xảy ra khi xóa một phần tử khỏi cây NPTK gồm:
A. Nút xóa là nút lá, nút xóa có một nhánh con và nút xóa có hai nhánh con
B. Nút xóa là nút lá và nút xóa có một nhánh con
C. Nút xóa có một nhánh con và nút xóa có hai nhánh con
D. Nút xóa là nút lá và nút xóa có hai nhánh con
Cho đoạn chương trình như sau:
void AddAfter(DLIST &DQ, DNode *q, DNode *new_element)
{
DNode *p = q -> next;
if (q != NULL)
{
new_element -> next = p;
new_element -> pre = q;
q -> next = new_element;
if (p != NULL)
…[1]…
if (q == DQ.Tail)
DQ.Tail = new_element;
}
else
AddFirst( DQ, new_element);
}
Đoạn lệnh nào được điền vào [1] cho đúng?
A. p -> pre = new_element;
B. p -> next = new_element;
C. new_element = p -> pre;
D. p -> pre = NULL;
Đoạn mã khởi tạo danh sách rỗng sau:
void init( DList &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. Các đáp án đều sai
Định nghĩa nào đúng với danh sách liên kết
A. Danh sách liên kết là tập hợp các phần tử mà đặt kế cận với nhau trong vùng nhớ
B. Danh sách liên kết là cấu trúc dữ liệu dạng cây
C. Danh sách liên kết là cấu trúc dữ liệu tự định nghĩa
D. Danh sách liên kết là tập hợp các phần tử mà giữa chúng có sự kết nối với nhau dựa vào liên kết của chúng
Ma trận kề của đồ thị vô hướng G =<V, E> có tính chất
A. Là ma trận đường chéo trên
B. Là ma trận đối xứng
C. Là ma trận đơn vị
D. Là ma trận không đối xứng
Cây là đồ thị vô hướng liên thông
A. Không có cạnh cầu
B. Không có đỉnh treo
C. Không có chu trình
D. Không có đỉnh cô lập
Cho khai báo cấu trúc đồ thị dạng danh sách cạnh như sau:
struct Canh
{
int dd,dc;
float ts;
};
struct DoThiCanh
{
int m;
Canh ds[max];
};
Đâu là đoạn mã để liệt kê các đỉnh kề của một đỉnh k nào đó trong đồ thị
A. void XuLy(DoThi G, int k){ int i,j; printf("\n Cac dinh ke cua %d la:",k); for(i=1;i<=G.n;i++) if(G.C[k][i]>0) printf("%7d",i);}
B. void XuLy(DoThiCanh G)
C. void XuLy(DoThiCanh G,int k)
D. void XuLy(DoThi G){ printf("\n Ma tran trong so la:\n"); for(int i =1; i<=G.n; i++) { for(int j=1;j<=G.n;j++) printf("%8.1f",G.C[i][j]); printf("\n"); }}
Cho Danh sách liên kết đôi chứa danh sách Cán Bộ (CB), Đoạn mã sau đây thực hiện gì?
void InDSCanBo (DList Q)
{
Node *p;
for (p=Q.Tail; p!= NULL ; p=p->pre)
{
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. In đầy đủ thông tin tất cả các cán bộ đang chứa trong danh sách Q lần lượt từ đầu danh sách về cuối danh sách
B. In đầy đủ thông tin tất cả các cán bộ đang chứa trong danh sách Q lần lượt từ cuối danh sách về đầu danh sách
C. In đầy đủ thông tin tất cả các cán bộ đang chứa trong danh sách Q
D. In danh sách tên các cán bộ đang có trong danh sách Q lần lượt từ cuối danh sách về đầu danh sách
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 , *pre ; };
struct List { Node *head , *tail ; };
Khai báo CTDL 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
Cho các bước mô tả thuật toán như sau:
Nếu danh sách rỗng:
DQ.Head = new_element;
DQ.Tail = DQ.Head;
Ngược lại (d/s khác rỗng):
new_element -> next = DQ.Head;
DQ.Head -> pre = new_element;
DQ.Head = new_element;
Đây là mô tả của thuật toán chèn một phần tử vào danh sách liên kết đôi với vị trí chèn là?
A. Chèn sau phần tử đã biết
B. Chèn trước phần tử đã biết
C. Chèn vào đầu danh sách
D. Chèn vào cuối danh sách
Cho đoạn mã sau, cho biết kết quả của x?
Stack S;
InitStack(S);
Push(S, “Green”);
Push(S, “Red”);
Push(S, “Yellow”);
Pop(S,x);
A. Red
B. Green
C. Tất cả các phương án đều đúng
D. Yellow
Cho các phần tử sau: 31, 19, 36, 20, 41, 17, 33, 32. Tạo cây NPTK từ các phần tử trên. Hãy cho biết sau khi xóa phần tử 33 trên cây sau đó áp dụng phương pháp duyệt NRL thì kết quả thu được thứ tự các phần tử là như thế nào?
A. 31, 19, 36, 20, 41, 17, 32
B. 41, 36, 32, 31, 20, 19, 17
C. 41, 32, 36, 20, 17, 19, 31
D. 31, 36, 41, 32, 19, 20, 17
