Sách Bài Tập Chuyên Tin Tin Học 2 - Cấu trúc dữ liệu và Thuật toán nâng cao

• Tác giả: Nguyễn Văn Hoàng
• Chuyên ngành: Tin học
• Đề tài: Bài tập chuyên tin học quyển 2
• Loại tài liệu: Tài liệu bài tập
• Địa điểm: Hà Nội

Tóm tắt

I. Tổng quan về Bài tập Chuyên Tin học Quyển 2

Bài tập Chuyên Tin học Quyển 2 là tài liệu chuyên sâu dành cho học sinh các trường chuyên, lớp chọn Trung học Phổ thông và Trung học Cơ sở. Bộ sách được biên soạn bởi các giáo viên đang giảng dạy tại các trường chuyên hoặc tham gia bồi dưỡng học sinh giỏi tin học quốc tế. Tài liệu nằm trong hệ thống sách Bài tập Chuyên Tin học Quyển 1, 2, 3, đi kèm bộ Giáo trình Chuyên Tin học tương ứng. Nội dung bao gồm hai phần chính: phần bài tập với các chuyên đề từ dễ đến khó, và phần hướng dẫn giải chi tiết. Sách phục vụ tốt đối tượng học sinh chuyên tin, sinh viên đại học, cao đẳng tham gia Olympic Tin học Sinh viên Toàn quốc và Kỳ thi Lập trình viên Quốc tế. Các bài tập được đánh số thống nhất với sách lý thuyết, giúp người học dễ dàng tra cứu và đối chiếu kiến thức.

1.1. Đối tượng sử dụng và mục đích

Tài liệu hướng đến nhiều đối tượng: học sinh trường chuyên lớp chọn cấp THPT và THCS, sinh viên đại học cao đẳng chuẩn bị cho các kỳ thi Olympic Tin học. Mục đích chính là xây dựng hệ thống bài tập có tính hệ thống, từ cơ bản đến nâng cao. Mỗi bài tập gắn liền với chương trình đào tạo chuyên tin do Bộ Giáo dục ban hành. Phần hướng dẫn giải cung cấp chi tiết hoặc gợi ý chương trình chính, giúp người đọc tự tìm ra lời giải. Đây là tài liệu thiết thực phục vụ giảng dạy và học tập hiệu quả.

1.2. Cấu trúc và cách sắp xếp nội dung

Mỗi cuốn Bài tập Chuyên Tin học có cấu trúc thống nhất gồm hai phần. Phần I tập hợp tất cả bài tập theo các chuyên đề của giáo trình tương ứng, kèm bài tập bổ sung. Các bài được sắp xếp từ dễ đến khó, từ đơn giản đến phức tạp. Phần II chứa hướng dẫn giải chi tiết, có thể là giải đầy đủ hoặc chỉ dẫn chương trình chính để người đọc tự hoàn thiện. Bài tập đánh số theo sách lý thuyết; bài tập bổ sung đánh số tiếp theo. Cách bố trí này tạo hệ thống liền mạch, dễ tra cứu.

II. Phân tích cấu trúc dữ liệu và thuật toán trong sách

Nội dung Bài tập Chuyên Tin học Quyển 2 tập trung vào các cấu trúc dữ liệu cơ bản và thuật toán xử lý. Các cấu trúc dữ liệu chính bao gồm danh sách liên kết đơn, danh sách liên kết đôi, ngăn xếp và hàng đợi. Bài tập yêu cầu cài đặt các thao tác chọn, xóa, tìm kiếm phần tử trên danh sách số nguyên đã sắp xếp. Phần thuật toán đồ thị chiếm vị trí quan trọng với bài toán đường đi ngắn nhất sử dụng thuật toán Dijkstra. Sách cũng đề cập đến các biến thể như đồ thị có trọng số âm, yêu cầu phân tích độ phức tạp thời gian. Các bài tập về cây và duyệt cây theo thứ tự Preorder, Inorder, Postorder giúp người học nắm vững cấu trúc phi tuyến tính. Việc chuyển đổi biểu thức từ dạng trung tố sang dạng hậu tố (RPN) cũng được giới thiệu với cài đặt cụ thể bằng ngôn ngữ Pascal.

2.1. Danh sách liên kết và thao tác cơ bản

Danh sách liên kết là cấu trúc dữ liệu nền tảng được khai thác sâu trong quyển 2. Bài tập yêu cầu cài đặt danh sách liên kết đơn và danh sách liên kết đôi để lưu trữ số nguyên. Các thao tác cơ bản gồm chèn, xóa, tìm kiếm phần tử cần được thực hiện trên danh sách đã sắp xếp tăng dần. Bài tập nối hai danh sách số nguyên đã sắp xếp thành danh sách mới cũng được đề cập. Việc hiểu rõ cách con trỏ hoạt động và quản lý bộ nhớ động là yếu tố quyết định để giải quyết tốt các bài tập này.

2.2. Thuật toán đồ thị và Dijkstra

Thuật toán Dijkstra tìm đường đi ngắn nhất là trọng tâm của phần đồ thị. Sách đặt ra bài toán tìm đường đi giữa n điểm tròn trên mặt phẳng, với chi phí di chuyển bằng khoảng cách giữa các tâm. Bài tập yêu cầu chứng minh thuật toán Dijkstra sai khi đồ thị có cạnh trọng số âm, kèm ví dụ minh họa. Các biến thể như đồ thị có trọng số trong phạm vi 0 đến k được khai thác để thiết kế thuật toán có độ phức tạp O(kn·m). Thuật toán Gabow cũng được giới thiệu với độ phức tạp O((m+n)log k).

III. Phương pháp giải bài tập và kỹ thuật lập trình

Phương pháp giải bài tập trong Chuyên Tin học Quyển 2 đòi hỏi tư duy thuật toán chặt chẽ và kỹ năng lập trình thành thạo. Mỗi bài tập thường đi kèm hướng dẫn giải chi tiết hoặc gợi ý chương trình chính để người đọc tự hoàn thiện. Kỹ thuật sử dụng ngăn xếp (stack) đóng vai trò quan trọng trong việc chuyển đổi biểu thức trung tố sang hậu tố. Chương trình cài đặt bằng Pascal với cấu trúc dữ liệu tự định nghĩa, sử dụng con trỏ và các hàm thao tác ngăn xếp. Việc xác định độ ưu tiên của toán tử logic (not, and, or, xor) được thực hiện qua hàm Priority. Quá trình phân tích biểu thức (Parsing) xử lý từng token, áp dụng quy tắc dấu ngoặc và độ ưu tiên để tạo biểu thức hậu tố đúng. Tư duy quy hoạch động và kỹ thuật chia để trị cũng được áp dụng trong nhiều bài tập nâng cao về tối ưu hóa.

3.1. Kỹ thuật chuyển đổi biểu thức bằng ngăn xếp

Chuyển đổi biểu thức từ trung tố sang hậu tố (RPN) là bài tập kinh điển trong tin học. Kỹ thuật sử dụng ngăn xếp để lưu trữ toán tử và xử lý theo độ ưu tiên. Chương trình Pascal cài đặt các hàm Push, Pop, Get để quản lý ngăn xếp liên kết. Hàm Priority xác định độ ưu tiên: not có mức cao nhất, tiếp theo là and, cuối cùng là or và xor. Quá trình Parsing duyệt từng token, gặp dấu mở ngoặc thì đẩy vào stack, gặp đóng ngoặc thì pop ra cho đến khi gặp ngoặc mở. Toàn bộ kết quả được in ra theo dạng hậu tố.

3.2. Thiết kế thuật toán với độ phức tạp tối ưu

Mục tiêu quan trọng trong các bài tập nâng cao là thiết kế thuật toán có độ phức tạp thời gian tối ưu. Bài tập yêu cầu xây dựng thuật toán độ phức tạp O(kn·m) cho đồ thị có trọng số trong phạm vi 0 đến k. Kỹ thuật bucket sort kết hợp với Dijkstra cải tiến giúp đạt được yêu cầu này. Thuật toán Gabow sử dụng cấu trúc heap đặc biệt đạt độ phức tạp O((m+n)log k). Việc phân tích và so sánh độ phức tạp giữa các phương pháp giúp người học phát triển tư duy tối ưu hóa. Mỗi thuật toán cần được kiểm chứng bằng nhiều bộ dữ liệu thử nghiệm khác nhau.

IV. Kết luận và ứng dụng thực tế của tài liệu

Bài tập Chuyên Tin học Quyển 2 là tài liệu không thể thiếu cho quá trình luyện thi tin học chuyên sâu. Hệ thống bài tập được xây dựng có tính hệ thống, bao phủ đầy đủ các cấu trúc dữ liệu và thuật toán quan trọng. Từ danh sách liên kết, ngăn xếp đến thuật toán đồ thị và chuyển đổi biểu thức, mỗi chủ đề đều có bài tập từ cơ bản đến nâng cao. Phần hướng dẫn giải chi tiết giúp người học kiểm tra và hoàn thiện kỹ năng giải quyết vấn đề. Tài liệu còn phục vụ giảng viên trong việc xây dựng giáo án và đánh giá năng lực học sinh. Các kiến thức từ sách có ứng dụng trực tiếp trong lập trình thi đấu, phát triển phần mềm và nghiên cứu khoa học máy tính. Sự kết hợp giữa lý thuyết và thực hành tạo nền tảng vững chắc cho người học tiến xa hơn trong lĩnh vực tin học.

4.1. Giá trị đối với luyện thi học sinh giỏi

4.2. Ứng dụng trong đào tạo và phát triển kỹ năng

Trích đoạn nội dung tài liệu

I A A TAI ilEU CHUYEN TIN H0c O I \i ,l BAI TAP H0 si DAM (chn bicn) oO or-tc oOtlc - lE vlNu HoANG - ttcuvEru THANH HUNG IA TAI IITU tl CHUYTN TIN HOC \rtl BAII TAP .]:-=l QUYEN 2 (Tdi bdn ldn tha nhiit) ruun xuAr aAn ctao ouc vtEr runvt Lor NoI nAu BO s6ch Tdj liau chuyan Tin hoc - Bdi hap Quydn I, 2, 3 duo. c vidt kdm v6i b0 Tdi hau' chuyan Tin hoc - Quydn 1, 2, 3 tuong rlng da duoc xudt ban. cdc tac'gid tham gia bien soan bo s6ch ld nhfrng thdy gi6o dd vd dang day b c6c trudng chuyen, l6p chon hoac.tham gia c5c kh5a bdi dudng thi tin hoc qudc te, bdi dudng gi6o vion tin muon cho c6c truong chuy6n theo chuong trinh cua BQ Gi6o duc vh Ddo tao' mong xay drrng duoc c6c tdi liOu c6 tfnh h0 thong phuc vu t6t cdc ddi tuong thuOc linh vuc chuyen tin hoc. C6c cudn Tdi IiAu chuy,n Tin hoc - Bdi ttfrp ddu c6 cAu trfc nhu nhau, gdm hai phdn: Phdn I - Biri tap bao g6m tdtcac6Lc bhi tap ffong nhirng chuyen dd cua s6chTiii hAu chuyAn Tin hoc tuong rlng vh c6c bdi tap bd sung, du-o. c s6p xdp til de den kh6, til don giin ddn Phrlc taP. Phdn II - Huong dan giii bii tAp c6 thd la nhfrng huong dan chi tiet dd gifp ban doc tim du-o.c ldi giii hoac chi lh doan chuong trinh chinh girip ban doc hidu vd tlm duoc ldi giai hoac chudng trinh.hohn chinh dd tham kh6o' Ddi vdi mOt so biri tQp thi c6 the chi lir drip rin hay huong d6n ngin gon. Hai bo sSch Tdi liau chuyan Tin hoc vd Tdi liau chuyan Tin hoc Bdi trip - Iao thhnh hC th6ng tdi li6u kh6 hohn chinh theo dinh huong Chuong trinh cdc chuyOn dd chuyen tin hoc dd duo. c B0 GiSo duc vd Dho tao ban hhnh. Do vAy cing v6i bO s(tchTdi liAu chuyAn Tin hoc, b0 s6ch Tdi tiAu chuy'n Tin hoc - Bdi tdp s6 ld tiri li6u thiet thuc phuc vu cho giSo vien, hoc sinh c6c trudng chuyen. l6p chon cd Trung hoc phd th6ng vh Trung hoc co so. Ngohi {a, b8 sSch cdn l)t t}ri liou tham khao bd fch cho vioc tap hudn sinh vion ci{c trudng Dai hoc, Cao ding tham gia c6c ki thi Olympic Tin hoc Sinh vien Tohn qudc vh Ki thi lAp trinh vien Quoc t€' Luu j khi srt dung b0 sdch: c6c bdi tap trong b6 s6ch nhy du-o.c d6nh s6 nhu trolg siich li thuyet; c6c bhi tap bd sung duo. c dd o muc neng vh d6nh so tiep theo. bo Mac dD c6c tdrc gia vd Ban bi6n tap dd cd g6ng hohn thien nhunq chac ch6n sdch cdn nhidu thidu s6t, c6c tltc gittmong nhAn du-o.c nhidu f kidn d6ng g6p dd s6ch s6 hodn thien hOn, phuc vu ban doc duoc hieu qua hon. c6c g6p y xin gur ve: BanTodn-Tin, c6ng ty cri phdn Dich vu xud't btin Gido duc Hd ^l6i' Nhd rud't bdn Gido duc vi€t Nam, tdng 4, toc) nhd Diamond Flower, 56' I Hodng DaoThuY, Hd Ndi' C6c tric eii ldoo # BAI TAP tl'tN DE 6. runu ntluuu rntlu rUQl\G vA cAu rRUc ntILrEU lal- -.-;t chuong trinh thgc hiQn c6c thu tqc chdn, xo6, vd tim ki6rn mQt phAn tu ::,:g danh sdch c6c s5 nguy€n da sAp x6p theo thfi'ru tang clAn bi€u di6n boi: :. \lang: : Danh s6ch n6i don; : Danh s6ch nOi kep. r i€t chuong trinh n6i hai danh s6ch s6 nguy€n da sAp x6p. l-,ng qu6t hcrn, hdy vi6t chuong trinh n6i k danh s6ch si5 nguy€n dd sat, ,.,-r: ,J€ dugc rnQt danh s6ch g6m t6t cit citc phAn tu dugc sip x6p' L-i- ,-l.a su chung ta bi6u di6n mQt da thuc p(x) = alxbr * a2xb'+ "'+ Qnxb', ::'-.: ,lanh sfch chira hg s6 d;, s6 mfr b; vd con tro tro toi nrit k6 ti€p (ntit . Hiy tim thuQt to6n cQhg vd nh1n hai da thirc theo bi6u di6n ndy. a{ \t"1t so nhi phin anen-r.a0,trong d6ai e {0,1}c6 gid tri bingfa,z' ' l=0 \guoi ta bi6u di6n s6 nhi phdn ndy bing rnot danh s6ch ndi don g6rn n :. c6 nirt dAu danh s6ch chua gi6 tfi Qn, m6i ntit trong danh s6ch chira :.\r cht s6 nhi phdn a; vd con tro tro t6i nrit ki5 tiep Id nirt chua chir sd nhi :hin as-1. :iir lqp chuong trinh thuc hiQn phdp todn "c6ng l" tr€n s6 nhi phdn dd cho '. r rJua ra bi6u di6n nhi phdn ctra k€t qua.' Su' dqng dg 6. Hdng dqi hai ddu (doubled-ended queue) ld m6t danh silch duoc trang.bi bdn thao t6c: PushF (u): DAy phAn tir y vdo dAu danh s6ch. PushR(v): E6y phAn tu u vdo cudi danh s6ch. PopF: Lo4i bo phAn tu dAu danh sdch. PopR: Loai bo phAn tu cu6i danh s6ch. H6y tim cAu truc df liQu thich hqp d6 cdi dflt ki6u dfr ligu truu tuong heng dqi hai dAu.6, C6 hai so d6 duong ray xe lta b6 tri nhu hinh sau: Ban dAu co ntoa tdu x€p theo thg ru tt I tdi n tu phdi qua trdi tr€n clucrng ray A. Ngucri ta mu6n x€p lai c6c toa tdu theo thri tu m6i tu phii qua rr6i (pr,pr,.,?n) l6n'duong ray C theo nguyOri tdc: Ctc toa tiu kh6ng dugc "vugt nhau" trdn ray, rn6i lAn chi dugc chuy6n mQt toa tiu tu A -- B, B+Cho{c4--+C. Hdy cho uict aieu d6 c6 th6 thuc hiqn dugc trcn so d6 dudng ray ndo trong hai so dO tren? 6. xdt hai nft x, y tr€n mQt cdy nhi phdn, ra n6i nrit x nim b6n tr6i nrit y (nrit y nim bOn phdi nrit x) n6u: o Hodc nrit x ndm trong nh6nh con tr6i cria nut y; o Ho{c nrit y nim trong nh6nh con phAi cira nrit x; o HoAc t6n t4i rnQt nirt z sao cho x nim trong nh6nh con trai v2r y nim 3bi trong nh6nh con Phii cua ntt z' cdy nhi ph6n (x + y) chi c6 Hdy chi ra ring v6i hai nut x,y uat ki tr€n mot tlung mQt trong bOn menh dd sau ld dung: ' i) x nim b€n tr6i Y; ii) x nim b€n Phai Y; iii) x ld ti€n b6i ttrgc su cua Y; tng iv) Y ld ti€n UOi ttrUc su cua x' c6c gi6 tri aJ. V6i m6i nut x tr6n cdy nhi phdn T, gia su ring ta bitit duqc tu duyQt truoc' preord.erlxf ,lnord"er[x] vd Postorderlx] lan lugt ld thu gita, sau cua x. hai nrit c6 quan hQ tiOn Tim c6ch chi dua viro c6c gri tr1 ndy dO ki6m tra UOi-nau duQ haY kh6ng. rdng trOn cay ,ei. BQc (degree) cia mot nirt ld s6 nirt con cua no. Chung minh m6t nirt' nhi phdn, sO ta nni6u hon sO nirt b4c 2 dung 6. Hdy chi ra ring cau truc cua mQt ciy nhi ph6n c6 ttr6 kh6i phgc mQt c6ch AonAintneutabi€tduqcthutgduyQttru6cvirgiiracuac6cnirt' phuc n6u ta bi6t duqc thil tg Tucrng tg nhu vQy, c6u truc cdy co th6 kh6i duYQt sau vd gita cua c6c nirt' 6.Haychoviduv€haiciynhiph6nkh6cnhaunhungc6thritgtluoccua gi6ng nhau' gi6ng nhau vir thir tU sau cfia c6c nut cfrng "e"nut 1 chirig han bi€u thuc bao g6m c, 6. X6t bi6u thric c6 th6 co d4ng phirc tap, phepl6ys6A6l(-x),ph6ptinhlulthria(xv)'hdmsovoimQthaynhi6u bi0n s6. ndy bing mqt caV t1n9 qudt vh Ta c6 tnti UiCu diSn nhirng bi6u thuc d4ng hay ki ph6p nghich dAo Ba tir d6 c6 the chuyi5n bi6u thuc v6 d4"g hOu t0 Lan (RPN) dC ttruc hiQn tinh to6n' s6 hQc (dang phuc tqp) vd Hdy,x6y dgng thudt to6n d€ chuy6n bi6u thuc thuc d6' d4ng RPN va thuflt to6n tinh gi6 tri biOu 6. vict chuong trinh chuy6n bi6u thuc logic d?ng trung t6 sang d4ng RPN' d andor' Vi du chuy6n: a and b or cand d thdnh: ab andc 6. Chuy6n ciic bi€u thric sau ddy ra dang RpN: a) Ax (B + C); 't\ B b). vdi mqt dnh den/tring kich thudc 2n xzn, nguoi ra dung phuong ph6p sau d€ md hoil rinh: r NOu Anh chi g6m todn di6m den thi rinh d6 c6 th6 duoc md hori bing .'xdu chi g6m mQt ki tu . N6u anh chi gdrn rodn di6rn tring thi inh dri c6 th€ ducyc m6 ho6 bing I xiiu chi gom mdt ki tu ,W,; . N6u P,Q,R,s ldn luqt ld x6u md ho6 cta b6n rinh kich thu6c bins nhau thi &PQR.9 lir x6u md horr cua dnh tao thdnh bing cdch aar uol dnh ban dAu theo so d6: Pa .dU "&B&BWWB&W&BWBW,' vd "&&BBBB&BWWB&W&BWBW" ld hai xdu md hori cua cung mQt rinh b6n" Bdi torln drt ra ld cho s6 nguy€n ducyng n vd hai xdu md ho6 cira hai 6nh kich thuoc 2n x zn. Hdy cho bi€t hai anh d6 c6 kh6c nhau kh6ng vd neu chring kh6c nhau thi chi ra mQt vi tri c6 mdu kh6c nhau rr6n hai 6nh. Qu6 irinh ti* ki6m ft6n cdy rthi ph6n tim ki6m (BST) c6 th6 coi nhu mQt ducrng di xu6t ph6t tu nrit gdc. Gi6o su X ph6t hi€n ra m6t tinh ch6t thir vi: N€u duong cli trong qu6 trinh tim ki6m kdt thric o mQt nrit ld, ki hieu t ld 6p c|c gi| tri chua rrong c6c nrit nim b€n tr6i ducng di vd R ld tflp c6c gi(t tri chria trong c6c nrit nim b6n ph6i duong di. Khi dovx l,,y e R, ta c6 F 8 x < y. Hdy chring rninh ph6t hiQn cira gi6o su X ld dring hoflc chi ra mQt Prl<ul vi phrin vl dq. iho BST g6m n nut, bit dAu tu nrit Mi.ntmum^, ngudi ta goi hirm Suc.cessor dC di sang nrit li€n sau cho tdi khi duyQt qua nrit Maxtmum^. Chirng minh ring thuat to6n ndy c6 thoi gian thuc hiqn O(n). Gqi y Th\Tc hiQn n loi gqi hdm Successor li€n ti6p dC duyQt qua c6c li6n k6t chalcon trOn BST, mdi licn t6t toi da hai lAn. Didu tuong tg c6 th6 chung minh dugc n6u ta bit dAu il n|lt ltLaxtmumn vd ggi liOn titip him Predecessor d6 di sang nrit li6n truoc. Cho BST c6 chi€u cao h. Bat dAu tu rnQt nf t p1, nguo'i ta tirn ntst p2ld nrit li6n saupl: pz.= Successor(p1), ti6p theo: l4i tim nritp, ld nirt li6n sau p2,. Chimg minh ring thtri gian thgc hiQnkltn loi gqi hdm Successor nhu vQy le O(k + h). Nguoi ta c6 th6 thqc hiQn viQc tip *5p mQt ddy kho6 bing cdy nhi phdn tim ki6m nhu sau: Chen lAn lugt c6c gi6 tri kho6 viro mQt cdy nhi phdn tim ki6m sau d6 duyQt cdy theo thu tg gita (thu4t to6n Tree Sort). Hdy d6nh gi6 thdi gian thgc hiQn thuat to6n trong truong hqp t6t nhAt, x6u nhj,t vd trung binh. Cdi dat thu{t to6n Tree Sort. Hay vitit thuflt tohnsearchLE(k) d6 tim nrit chua kho6 I6n nhat khdng vugt qu6 k trong BST.Hdy vitit thuat todnSearthcE(k) d6 tim nrit chria kho6 nho nh6t kh6ng nho hon k trong BST.Hdy viCt thu tuc MovetoRoot(p) nh{n vdo nrit p vd dirng c6c ph6p quay d6'chuy6n nirt p thdnh g6c cua cdy BST. Hdy vitit thtr tqc MovetoLeaf (p) nhAn.vdo nrit p vd dung c6c phep quay dti chuy,5n nft p thdnh mQt nrit 16 cira cAy BST. Cdy tirn kiLlm co sd lRodi* Tree) ld mQt cdy nh!