Đị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 * NextNode; } OneNode; Trong đó, khai báo Node * NextNode; dùng để mô tả
A. Con trỏ trỏ tới phần dữ liệu
B. Vùng liên kết quản lý địa chỉ phần tử kế tiếp
Đáp án chính xác
C. Con trỏ trỏ tới phần dữ liệu cuối của danh sách
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 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 thuật toán sau: int LinearSearch (int M[], int N, int X) { int k = 0; while (M[k] != X k < N ) k++; if (k < N ) return (k); return (-1); } Chọn câu đúng nhất trong trường hợp xấu nhất khi không tìm thấy phần tử nào có giá trị bằng X:
Cho thuật toán sau: int LinearSearch (float M[], int N, float X) { int k = 0; M[N] = X; while (M[k] != X) //n+1 lan (M[k] != X) //n+1 lan k++; if (k < N) return (k); return (-1); } Chọn câu đúng nhất trong trường hợp xấu nhất khi không tìm thấy phần tử nào có giá trị bằng X:
Chiều dài đường đi của một cây (path’s length of the tree) được định nghĩa là tổng tất cả các chiều dài đường đi của tất cả các nút trên cây. Xét cây sau:
Cho thuật toán sắp xếp Bubble Sort như sau: void BubbleSort(int M[], int N) { for (int I = 0; I < N-1; I++) for (int J = N-1; J > I; J--) if (M[J] < M[J-1]) Swap(M[J], M[J-1]); return; } Chọn câu đúng nhất cho hàm Swap
Tìm kiếm xem trong danh sách liên kết đơn có tồn tại nút có thành phần dữ liệu là SearchData hay không. Thao tác này chúng ta vận dụng thuật toán tìm tuyến tính để tìm kiếm: typedef struct Node { int Data; Node * Link; } OneNode;' typedef OneNode * Pointer; Pointer SSList; // Quản lý danh sách liên kết đơn bởi 1 phần tử đầu B1: CurNode = SLList B2: IF (………………………………………………) Thực hiện BKT B3: CurNode = CurNode->Link B4: Lặp lại B2 BKT: Kết thúc Chọn điều kiện hợp lý cho mã giả ở B2
Biểu diễn và tổ chức ngăn xếp (Stack) bằng danh sách liên kết giả sử bề mặt của ngăn xếp là đầu danh sách liên kết: typedef struct SElement { T Key; SElement *Next; } SOneElement; typedef struct SOneElement *SSTACK; SSTACK SSP; Thêm 1 phần tử vào ngăn xếp (dùng cấu trúc dữ liệu mô tả ở trên) B1: NewElement = Khởi tạo nút mới (dùng toán tử new) B2: if (NewElement == NULL) Thực hiện BKT B3: if (SSP == NULL) B3.1: SSP = NewElement B3.2: Thực hiện BKT B4: ………………………………………… B5: ………………………………………… BKT: Kết thúc Chọn câu lệnh chính xác cho B4 và B5