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

Cho biết các nút có bậc bằng 2 trong hình ảnh sau:

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 RLN thì kết quả thu được thứ tự các phần tử là như thế nào

Bậc của nút trong cây có nghĩa là gì?

Đoạn mô tả này thuộc thuật toán nào:

Bước 1: i = 0

Bước 2: tính các giá trị j = i + 1

Bước 3: Trong khi j<n thực hiện

- nếu a[j] < a[i] thì hoán đổi a[i] với a[j]

- j = j + 1;

Bước 4: i = i +1

nếu i<n-1 thì lặp lại bước 2, ngược lại thì dừng

Cho mảng a gồm các phẩn tử có giá trị như sau:

3126

Số lần hoán vị 2 phần tử khác nhau khi áp dụng thuật toán đổi chỗ trực tiếp (Interchange Sort) để sắp xếp mảng tăng dần là:

Cho hàm tìm kiếm tuyến tính trong mảng 1 chiều có n phần tử

int Search( int a[], int n, int x)

{

int i;

for(i=0; i<n; i++)

if(a[i] == x) return i;

return(-1);

}

Chọn phát biểu đúng nhất trong các phát biểu sau

Để sắp xếp các phần tử của danh sách liên kết đơn sử dụng phương án nào?

Các trường hợp thực hiện hủy phần tử khỏi danh sách liên kết đơn gồm:

Danh sách liên kết là gì?

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.

Đ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].

Các thành phần của danh sách đơn gồm:

Danh sách được cài đặt bằng cách nào:

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

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

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?

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

Đ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;}

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:

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