Bài tập Cấu trúc dữ liệu và giải thuật

Bài tập Cấu trúc dữ liệu và giải thuật cung cấp đến các bạn sinh viên những câu hỏi gồm 4 chương với các nội dung đó là tổng quan về cấu trúc dữ liệu và giải thuật; tìm kiếm và sắp xếp; cấu trúc danh sách liên kết; cấu trúc cây.
Nội dung trích xuất từ tài liệu:
Bài tập Cấu trúc dữ liệu và giải thuậtBàitậpcấutrúcdữliệuvàgiảithuật Trang1Chương1 TổngquanvềcấutrúcdữliệuvàgiảithuậtViếtchươngtrìnhhoànchỉnhchocácbàitoánsauđây(cácbàitậpvềôntập,cácbàitậpvềrènluyệncáchlựachọnmộtcấutrúc dữliệuthíchhợp;mộtthuậttoánthíchhợpchovấnđềbàitoán)BT11.Chonsốnguyêndươnga0,a1,a2,...,an1. a.Chènphầntửxvàovịtríkcủadãy. b.Xóatấtcảcácsốnguyêntốtrongdãy.BT12.Chomatrậnvuôngndòngncột;mỗiphầntửcủamatrậnlàmộtphânsố(giảthiếtrằngtửsốvàmẫusốcủacácphânsốnàylàcácsốnguyên).Hãythựchiệncácyêucầusau: a.Tìmphânsốcógiátrịnhỏnhấtnằmtrongkhoảng.(0;1). b.Đếmsố lượngphânsố nằmtrongmatrậntamgiáctrêncógiátrị nằmtrongkhoảng(0,1) c.Sắpxếpcácphânsố trongmatrậntăngdầntừ tráiquaphảivàtừ trên xuốngdưới.BT13.Viếtchươngtrìnhtạomộttậptinvănbản cótênlà“DAYSO.INP”cócấutrúcnhưsau: Dòngđầutiênghin(nlàsốnguyêndươngnhậptừbànphím). Trongcácdòngtiếptheoghinsố nguyênngẫunhiêntrongphạmvitừ 1 đến10000,mỗidòng10số(cácsốcáchnhauítnhấtmộtdấucách).Hãythựchiệncáccôngviệcsauđây: a.TìmgiátrịlớnnhấtcủacácsốtrongtậptinDAYSO.INP. b.Đếmsốlượngsốchẵn,sốlượngsốlẻtrongtậptinDAYSO.INP. c.Hãyđếmsố lượngsố nguyêntố,số chínhphương,số hoànhảo,sốAmstrongtrongtậptinDAYSO.INP. Hãy ghi kết quả của các câu a,b,c trên vào tập tin văn bản có tên là “DAYSO.OUT”.Bàitậpcấutrúcdữliệuvàgiảithuật Trang2BT14.Viếtchươngtrình tạotậptinvănbảncótênlà“BANGSO.INP”cócấutrúcnhưsau: Dòngđầutiênghihaisốmvàn(m,nlàcácsốnguyêndươngnhậptừbàn phím) Trongmdòngtiếptheomỗidòngghinsốnguyênngẫunhiêntrongphạm vitừ0đến1000(cácsốcáchnhauítnhấtmộtdấucách) Hãythựchiệncáccôngviệcsau: a.Hãychobiếtchỉ số cácdòngcóchứasố nguyêntố (giả thiếtcácdòng trongtậptinvănbảnđượcđánhsốtừ0đếnm1). b.Xoayvòngcáccộtquaphảimộtvịtrí(cột0sẽquacột1,cột1quacột 2,...cộtn1vềcột0). c.Sắpxếpcácphầntửtăngdầntrêntừngcột. Hãyghicáckếtquảtrênvàofilevănbảncótênlà“BANGSO.OUT”.BT15. Chomảngmộtchiềugồmntọađộ điểm(giả sử hoànhđộ vàtungđộcủacácđiểmlàcácsốnguyên). a.Hãytìmmộtđiểmtrongmảngxagốctọađộnhất. b.Hãytìmtọađộhaiđiểmgầnnhaunhất. c.Hãyxácđịnhtọađộ củahìnhchữnhậtnhỏnhấtbaohếtcảnđiểmtrên (tọađộgóctrênbêntráivàtọađộgócdướibênphảicủahìnhchữnhật). Vídụn=5vàtọađộ5điểmlà:(0,0);(0,3);(3,3);(4,1);(4,4). Thìkếtquảcâualàđiểm(4,4),kếtquảcâublà(3,3)và(4,4),kếtquảcâu clà(0,4);4(,0).BT16.Chodãynsố nguyêna0,a1,...,an1.Hãychuyểnkphầntửđầutiêncủadãyvềcuốidãy.BT17.Giả sửn 1vàxlàsố thực.Hãyviếthàmtínhgiátrị củabiểuthứcsauđây(vớiđộphứctạptuyếntính): x x2 x3 xn S ( n, x ) ... ( 1) n 1 1 1 1 1 1 1 1 1 1 ... 2 2 3 2 nBT1.8.TìmsốhạngthứncủadãyFibonasci(giảiquyếtkhinlàmộtsốlớn–khi đótakhôngthểsửdụngđệquyvàcũngkhôngthểsửdụngmảngđểlưutrữ).Bàitậpcấutrúcdữliệuvàgiảithuật Trang3BT19.Giảsửn 0vàxlàsốthực.Hãytínhgiátrịcủabiểuthứcsauđây. x x2 x3 xn S(n,x)=1 ... 1! 2! 3! n!BT110.a.Chodãynsốnguyêna0,a1,...,an1.Hãytìmdãyconliêntiếptăngdàinhất. b.Chodãynsốnguyêna0,a1,...,an1.Hãytìmđoạncondàinhấtchứatoànsố0. c.Chodãynsố nguyêna0,a1,...,an1.Hãytìmdãycontăngchứa nhiềusốnguyêntốnhất.BT111.a.Cộnghaisốnguyênlớnavàb,trongđósốacómchữsốvàsốbcónchữsố.Số nguyênlớn ở đâylàsố cóthể cóđếnvàitrămchữ số.Để lưutrữ cácsốnguyênlớnnàytacóthểdùngchuỗi(mỗikýtự củachuỗilàmộtchữ số)hoặcdùngmảngmộtchiều(mỗiphầntử củamảngmộtchiềulàmộtchữ số).Tuy nhiêntronghaiphươngánnàythìphươngándùngmảngmộtchiềuđểlưutrữsẽcóthuậttoántốthơn.b.Thựchiệ ...