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 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:
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
Khi cần thêm một phần tử có giá trị thành phần dữ liệu là NewData (là một số nguyên) vào đầu của danh sách liên kết đơn dùng thuật toán có mã giả mô tả như dưới đây? typedef struct Node { int Data; Node * NextNode; } OneNode; typedef OneNode * SLLPointer; SLLPointer SSList; B1: NewNode = new OneNode B2: IF (NewNode = NULL) Thực hiện BKT B3: NewNode ->NextNode = NULL B4: NewNode ->Data = NewData B5: NewNode->NextNode = SLList B6: SLList = NewNode BKT: Kết thúc Tìm mô tả chính xác cho B5
Giải bởi Vietjack
