TAILIEUCHUNG - Baøi taäp Toång hôïp CTDL 1 (Phaàn 2) Nguyeãn Tri Tuaán – Khoa CNTT, ñaïi hoïc KHTN

Baøi taäp Toång hôïp CTDL 1 (Phaàn 2) Nguyeãn Tri Tuaán – Khoa CNTT, ñaïi hoïc KHTN ---oOo--Baøi 13: Cho moät caây nhò phaân tìm kieám t coù caáu truùc nuùt laø BST_NODE ñöôïc khai baùo nhö sau: struct BST_NODE { int Key; // Khoaù cuûa nuùt int So_lan; // Soá laàn xuaát hieän cuûa khoaù trong caây struct BST_NODE *Left, *Right; } struct BST_TREE { struct BST_NODE *pRoot; // Nuùt goác cuûa caây } struct BST_TREE t; // Caây t a. Haõy vieát thuû tuïc/haøm thöïc hieän thao taùc xoaù phaàn töû coù khoaù X. Caùch xoaù nhö. | Bài tập Tông hợp CTDL 1 Phan 2 Nguyen Tri Tuàn - Khôà CNTT đài hoc KHTN ---oOo--- Bài 13 Cho một cay nhị phan tìm kiem t co cấu trúc nut la BST_NODE được khai bao như sau struct BST_NODE int Key Khoa cúa nút int So_lan Số lan xuất hiện cúa khoa trong cay struct BST_NODE Left Right struct BST_TREE struct BST_NODE pRoot Nút goc cúa cay struct BST_TREE t Cay t a. Hay viết thú tục hàm thực hiện thao tac xoa phan tư co khoa X. Cach xoa như saú Nếú phan tự X co ton tai giam field So_lan cúa no 1 đôn vị. Nếú phan tự X khong ton tai thong bao. b. Hay viết 1 thú túc ham in len man hình gia trị cúa cac phan tự đang ton tai trong cay theo thự tự NLR. Ghi chu mọt phan tự đựợc goi la co ton tai trong cay nếú So_lan 0. Bài 14 Cho thúật toan nhự saú for i 0 i n-1 i max i 1 for j i 1 j n j if a j a max max j if a max a i Temp a max a max a i a i Temp Hay tính chi phí cho thúật toan tren trong cac trựông hợp tot nhất xấú nhất trúng bình Bài 15 Cho mot hang đợi q va 1 đoan chựợng trình nhự saú struct QUeUe q int x 5 y 3 EnQueue q 8 EnQueue q 9 EnQueue q y DeQueue q x EnQueue q 18 DeQueue q x EnQueue q 22 Nguyen Tri Tuan - Khoa CNTT ĐHKHTN 1 3 while IsEmpty q 0 DeQueue q y printf d y Hay cho biết kết qua in ra man hình khi thi hanh đoạn chương trình trên la gì Bài 16 a. Hay nêu 1 ưu điếm va 1 khuyết điếm ma theo ban la tiêu biêu nhất cua phương phap sap xếp Quick-sort khi cài đặt bàng đệ qui. b. Hay nếu 1 điếm khac biệt cơ ban nhất thêo ban cua cấu truc Danh sách liên kết đơn so vơi cấu truc Máng động. Bài 17 Xêt thuật toan tìm tuan tư một sô nguyên X cho trươc trong một mang à gom 1000 sô nguyên. Trong tưng trưòng hơp sau hay cho biết số phan tư toi đa co thê đươc duyêt trong qua trình tìm kiếm a. Trương hơp 1 cac phan tư cua mang à chưa đươc sap xếp. b. Trương hơp 2 cac phan tư cua mang à đươc sap xếp tang dan. c. Trương hơp 3 cac phan tư cua mang à đươc sap xếp giam dan. Bài 18 Cho 2 xau liên kết T1 va T2. Gia thiết moi phan tư cua chung chỉ co 2 thong tin - Khoa cua

• Kĩ thuật Viễn thông
• Baøi taäp Toång hôïp