tài liệu võ tấn dũng votandung

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (122.2 KB, 2 trang )

(1)<div class='page_container' data-page=1>

TRƯỜNG CAO ĐẲNG CÔNG NGHỆ THÔNG TIN TP. HCM
KHOA CÔNG NGHỆ THÔNG TIN

CÂU HỎI & BÀI TẬP ÔN TẬP

MÔN CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT

(Khóa 9)

Câu 1: Cho dãy số 23 21 30 40 15 19 25 21

a. Hãy minh hoạ kết quả thực hiện từng bước sắp xếp theo thứ tự tăng bằng giải thuật đổi
chỗ trực tiếp(Interchange Sort).

b. Hãy viết giải thuật bằng mã tự nhiên hoặc cài đặt hàm bằng ngôn ngữ C/ C++ cho giải
thuật đổi chỗ trực tiếp.

c. Giả sử cần tìm phần tử có giá trị 21, hãy cho biết vị trí tìm thấy khi áp dụng giải thuật
tìm nhị phân trên dãy số đã được sắp xếp ở câu a(Dãy được đánh chỉ số bắt đầu từ 0).
Ôn tập kỹ các giải thuật sắp xếp khác (minh họa từng bước và cài đặt hàm):

- Chọn trực tiếp (Selection Sort)
- Chèn trực tiếp (Insertion Sort)
- Nổi bọt (Bubble Sort)

Câu 2: Cho khai báo cấu trúc danh sách liên kết đơn số nguyên và các hàm được cài đặt sẵn
bằng ngôn ngữ C++ như sau:

struct tnode
{

int data;

struct tnode *pNext;
};

typedef struct tnode NODE;

struct tlist
{

NODE *pHead, *pTail;
};

typedef struct tlist LIST;

Stt Mẫu hàm Mơ tả

1 void XoaDau(LIST &list); Xóa node đầu tiên (pHead) của danh sáchlist
2 void XoaCuoi(LIST &list); Xóa node cuối cùng (pTail) của danh sáchlist
3 void XoaNode(LIST &list, NODE *pDel); Xóa node pDel có trong danh sách list
Hãy cài đặt bổ sung các hàm sau:

Stt Mẫu hàm Mô tả

1 int DemX(LIST list, int x); Đếm và trả về số lượng node có giá trị lớn hơn x cho
trước

</div>
(2)<div class='page_container' data-page=2>

- Duyệt danh sách để xác định số lượng node, tìm kiếm node, xuất giá trị của node, tính tổng hoặc giá
trị trung bình các node trong danh sách.

- Xóa node khỏi danh sách

Câu 3: Cho khai báo cấu trúc hàng đợi số nguyên (quece) được tổ chức bằng mảng một chiều
như sau:

typedef struct QUEUE 
{

int *QArray; //Maảng chứa hàng đợi

int QMax; //Sốố lượng phầần tưả tốối đa

int QNumItems; //Sốố lượng phầần tưả trong hàng đợi

int QFront; //Vị trí phầần tưả đầầu cuảa hàng đợi

int QRear; //Vị trí phầần tưả cuốối cuảa hàng đợi
};

Giả sử có hàng đợi với các thơng tin như sau:

Chỉ số mảng 0 1 2 3 4 5 6

Qarray 15 7 9 21 8

QMax 7
QNum
Items

5
QFront 1

QRear 5

Hãy cho biết thông tin của cấu trúc hàng đợi khi lần lượt thực hiện các thao tác (sử dụng
phương pháp hàng đợi xoay vòng để tránh hàng đợi bị “tràn giả”):

a. Thêm giá trị 111 vào hàng đợi
b. Lấy một giá trị khỏi hàng đợi
c. Thêm giá trị 555 vào hàng đợi

Câu 4: Sử dụng lại dãy số ban đầu của câu 1, hãy thực hiện các yêu cầu sau:
a. Vẽ cây nhị phân tìm kiếm (theo thứ tự nhập từ trái sang phải).

b. Vẽ lại cây nhị phân tìm kiếm khi lần lượt chèn thêm các nút có giá trị: 10, 14 và 35.
c. Sau khi vẽ lại cây ở câu 4b, cho biết:

- Cho biết các nút có đúng 1 cây con trái.
- Các đường đi xuất phát từ gốc có độ dài là 3.
- Độ cao của cây.

d. Trình bày từng bước duyệt cây ở (câu 4b) theo thứ tự trước (NLR).
e. Trình bày từng bước khi xóa lần lượt các nút có giá trị: 21 và 23.
Ơn tập thêm về cây nhị phân tìm kiếm:

- Các khái niệm về bậc của nút, nút lá, nút nhánh, độ dài đường đi (tính bằng số nhánh cần phải đi
qua), độ cao của cây, các nút trên cùng một mức (nút gốc được tính là mức 0)

- Các thao tác duyệt cây: NLR, LNR và LRN

</div>