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

Nếu T1(n) và T2(n) là thời gian chạy của 2 đoạn chương trình P1 ,P2. Thời gian chạy của hai chuơng trình P1, P2 nối nhau là:

Mối quan hệ giữa cấu trúc dữ liệu và giải thuật có thể minh họa bằng đẳng thức:

Để dịch chuyển các đĩa từ cọc B sang cọc C với cọc A là trung gian, lệnh gọi hàm nào là đúng?

Thời gian thực hiện các lệnh đơn (gán, đọc, viết) là bao nhiêu trong các phương án sau?

Bước tổng quát của Phương pháp sắp xếp kiểu nổi bọt (bubble sort)?

Cây 5 phân có nghĩa là gì?

Đặc trưng nào của thuật toán thể hiện: Tất cả các phép toán có mặt trong các bước của thuật toán phải đủ đơn giản:

Xét thủ tục sau:

int TimKiemNP (int M[], int First, int Last, int X)

{

if (First > Last)

return (-1);

int Mid = (First + Last)/2;

if (X == M[Mid])

return (Mid);

if (X < M[Mid])

return(TimKiemNP (M, First, Mid – 1, X));

else

return(TimKiemNP (M, Mid + 1, Last, X));

}

Lựa chọn câu đúng nhất để mô tả thủ tục trên:

Trong giải thuật sắp xếp vun đống, ta có 4 thủ tục con (Insert - thêm 1 phần tử vào cây; Downheap - vun đống lại sau khi loại một phần tử khỏi Heap, Upheap- vun đống sau khi thêm một phần tử vào cây; Remove - loại 1 phần tử khỏi cây nhị phân). Để sắp xếp các phần tử trong dãy theo phương pháp vun đống, ta thực hiện 4 thủ tục trên theo thứ tự như thế nào?

Cơ chế heap trong sắp xếp vun đống là:

Thao tác nào dưới đây thực hiện trên hàng đợi (queue):

Tư tưởng của giải thuật tìm kiếm nhị phân:

Phát biểu sau đúng hay sai: Khi nói tới giải thuật phải xem xét nó sẽ tác động trên dữ liệu nào?
 

Miền giá trị của Kiểu số nguyên là:

Cho dãy số {6 1 3 0 5 7 9 2 8 4}. áp dụng phương pháp sắp xếp lựa chọn (Select sort) sau lần lặp đầu tiên của giải thuật ta có kết quả: {0 1 3 6 5 7 9 2 8 4}. Dãy số thu được sau lần lặp thứ tư là:

Cấu trúc dữ liệu biểu diễn hàng đợi bằng danh sách liên kết:

typedef struct QElement

{ T Key;

QElement *Next;

} QOneElement;

typedef QElement *QType;

Cấu trúc dữ liệu quản lý hàng đợi bằng hai phần tử đầu (Front) và cuối (Rear):

typedef struct QPElement

{ QType Font;

QType Rear; 

} SQUEUE;

SQUEUE SQList;

Thêm phần tử vào sau phần tử Rear. Giả sử dữ liệu đưa vào hàng đợi là NewData, mã giả được mô tả như sau:

B1: NewElement = Khởi tạo nút mới có thành phần NewData

B2: IF (NewElement == NULL)

Thực hiện BKT

B3: IF (SQList.Front == NULL) // hàng đợi dang rỗng

B3.1: SQList.Front = SQList.Rear = NewElement

B3.2: Thực hiện BKT

B4: …………………………………………..

B5: …………………………………………..

BKT: Kết thúc

Chọn câu đúng nhất cho bước B4, B5

Hãy chọn định nghĩa đúng nhất về danh sách kiểu hàng đợi (Queue)?

Với cấu trúc dữ liệu như sau:

typedef struct DNode

{ 

int Key;

DNode * NextNode;

DNode * PreNode;

} DOneNode

typedef DLLOneNode * DPointerType;

typedef struct DPairNode

{ DPointerType DLLFirst;

DPointerType DLLLast;

} DPType;

Hàm thêm phần tử vào cuối danh sách liên kết đôi quản lý bởi 2 phần tử đầu và cuối

DPointerType DLLAddLast(DPType &DList, int NewData)

{ 

DPointerType NewNode = gọi hàm tạo nút mới có vùng dữ liệu là NewData ;

if (NewNode == NULL)

return (NULL);

if (DList.DLLLast == NULL)

DList.DLLFirst = DList.DLLLast = NewNode;

else

{

……………………………………………….

……………………………………………….

………………………………………………

}

return (NewNode);

} Hãy lựa chọn câu đúng nhất để điền vào chỗ trống ở trên

Để thêm một đối tượng x bất kỳ vào Stack, ta dùng hàm nào sau đây?

Thế nào là ngôn ngữ giả?