Cấu trúc dữ liệu và giải thuật - IT05 (217)

Cho khai báo cấu trúc đồ thị dạng ma trận trọng số như sau:

struct DoThi{ int n; float C[max][max];};

Đâu là đoạn mã để liệt kê các đỉnh kề của một đỉnh k nào đó trong đồ thị

Cho đồ thị vô hướng như hình vẽ. Đỉnh nào dưới đây là đỉnh treo của đồ thị:

Cho cây NPTK, Cho biết kết quả duyệt cây theo thứ tự LNR là:

Cho cây NPTK, Cho biết kết quả duyệt cây theo thứ tự LRN là:

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?

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);

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à?

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ì?

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);

}

}

Cho đồ thị sau:

Cho biết ma trận kề biểu diễn đồ thị trên là gì?

Cho đồ thị trọng số G = <V,E> như hình vẽ. Hãy cho biết đâu là tập cạnh của cây bao trùm ngắn nhất được xây dựng theo thuật toán Prim. Giả sử bắt đầu từ đỉnh 1

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ị

Cây là đồ thị vô hướng liên thông

Ma trận kề của đồ thị vô hướng G =<V, E> có tính chất

Định nghĩa nào đúng với danh sách liên kết

Đ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ì

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?

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:

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):

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));