Đề thi cấu trúc dữ liệu và giải thuật

Chia sẻ: Nguyen Van Huan | Ngày: | Loại File: DOC | Số trang:6

Thêm vào BST

Báo xấu

521
lượt xem 135
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Đây là Đề thi cấu trúc dữ liệu và giải thuật gửi đến các bạn độc giả tham khảo.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Đề thi cấu trúc dữ liệu và giải thuật

CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Phần câu hỏi. I. Xác định độ phức tạp tính toán của đoạn chương trình con sau: 1. Function Tong(n:word): longint; Var i:word; S:longint; Begin I:=1; S:=0; While i
End; Var First: troTP; a. Viết thủ tục Procedure Xoa(Var first: troTP; Bthanhpho,Bdaily: st25); cho phép xóa một nút thuộc danh sách đại lý có tên đại lý bằng Bdaily thuộc thành phố Bthanhpho. Trong trường hợp, sau khi xóa xong, thành phố Bthanhpho không còn đại lý nào thì xóa tiếp thành phố đó khỏi danh sách thành phố. b. Viết hàm Function MaxDoanhThu (first:troTP; Bthanhpho: st25): longint ; trả về doanh thu cao nhất trong số các doanh thu c ủa các đại lý thu ộc thành ph ố Bthanhpho. Nếu không tìm thấy thành phố Bthanhpho thì trả về giá trị 0. c. Viết thủ tục Procedure InDSDaiLy(first: troTP); thực hiện việc in tên đại lý và số điện thoại tất cả các đại lý trên toàn quốc, theo mẫu: DANH SACH CAC DAI LY 1. HA NOI: Daily1 (812562), Daily2 (826956), Daily3 (889712) 2. HUE: Duynhat(586956) …………. Câu 2. Cho trước cây nhị phân Top (nút gốc trỏ bởi Top) có khai báo như sau: Type TroNutTrenCay = ^NutTrenCay; NutTrenCay = Record GiaTri: integer; Left, right: TroNutTrenCay; End; Var Top: TroNutTrenCay; a. Viết hàm Function Chieucao(top:TroNutTrenCay): word; trả về giá trị là chiều cao của cây nhị phân Top. b. Để biểu diễn một hàng đợi người ta có thể sử dụng một danh sách liên kết kép với nút đầu (l ối trước) và nút cuối (lối sau) lần lượt bởi trỏ First và Last. Ngoài ra mỗi nút trên danh sách này còn có thể lưu thông tin của một nút trên cây nhị phân Top. C ụ th ể ta có khai báo b ổ sung nh ư sau: Type TroNutTrenDS = ^NutTrenDS; NutTrenDS = record Info: NutTrenCay; Before, next: TroNutTrenDS; End; Var First, last: TroNutTrenDS; Viết hai thủ tục: Procedure ChenQ(var first, last: troNutTrenDS; X: NutTrenCay;); để bổ sung một nút mà trường info có giá trị bằng X tại vị trí lối sau Last Procedure DelQ(var first, last: TroNutTrenDS; var X: nutTrenCay); để loại bỏ một nút tại vị trí lối trước first và gán giá trị trường info của nút này cho tham biến X. c. Viết thủ tục Procedure LietKe(Top: TroNutTrenCay); nhằm liệt kê giá trị của info.giatri tại mỗi nút trên cây nhị phân Top với yêu cầu:
Thứ tự các nút được liệt kê giá trị là theo thứ tự tăng dần của mức các nút trên cây. - Các nút có cùng mức sẽ được liệt kê theo thứ tự từ trái sang phải. - CẤU TRÚC DỮ LIỆU & GIẢI THUẬT K25 (Đề lẻ). Phần câu hỏi: 1. Xác định độ phức tạp tính toán của đoạn chương trình sau theo n và p; I:=1; S:=0; While i
Câu 2. Xét cây nhị phân tìm kiếm, mỗi nút trong cây có dữ liệu kiểu Banghi có khai báo: Type contro: banghi; Banghi= record Left, right: contro; Info: real; End; a. Viết hàm GTLN(T: contro); cho kết quả là giá trị lớn nhất của trường info của tất cả các nút trong cây T (nút gốc trỏ bởi T), biết rằng T khác nil. b. Xét một danh sách nối kép có nút đầu và nút cuối trỏ bởi con tr ỏ first và last cùng có ki ểu CONTRO (trường Left trỏ đến nút trước và trường Right trỏ đến nút sau). Viết thủ tục Bosungdau(X: real; var first, last: contro); để bổ sung vào đầu danh sách này một nút mới sao cho trường Info có giá trị bằng X. c. Từ cây T ở trên, hãy viết thủ tục Tao_DS_Noikep(T: contro; Var first, Last: contro); để tạo mới một danh sách nối kép có nút đầu trỏ bởi con trỏ First, nút cuối trỏ bởi con trỏ Last, và trường Info c ủa các nút trong danh sách này phải được sắp xếp theo thứ từ giảm dần. CẤU TRÚC DỮ LIỆU & GIẢI THUẬT K25 (Đề 1). Câu 1. Tính độ phức tạp tính toán của giải thuật sau: Function NguyenTo(n:word): boolean; Var j,k: word; Begin K:=trunc(sqrt(n)); J:=2; While (j
Var first: TroMThi; Chú ý: danh sách các môn thi được sắp theo thứ tự tăng dần của tên môn thi. Viết các hàm và thủ tục sau: a. Function HCVang(first: troMThi; Bdoan:st20): byte; trả về số lượng huy chương vàng trong tất cả các môn thi của đoàn Bđoàn. b. Procedure Thanhtich( first:troMThi; Bmon: st20); in ra màn hình bảng thành tích của các đoàn có huy chương trong môn thi Bmon; c. Procedure Bosung (var first: TroMThi; Bmon, Bdoan: st20; ch: char); thực hiện việc bổ sung một huy chương loại Ch của đoàn Bdoan đối với các môn thi Bmon theo yêu cầu: - Ch là ‘V’,’B’,’D’ tương ứng là huy chương vàng, bạc, đồng. - Nếu môn thi Bmon chưa có trong danh sách thì bổ sung môn thi trước rồi mới bổ sung thành tích của đoàn sau này. CẤU TRÚC DỮ LIỆU TINK26 Câu 1. Ban chủ nhiệm khoa CNTT quản lý các lớp sinh viên bằng m ột danh sách liên k ết có nút đ ầu được trỏ bởi first. Cấu trúc danh sách khai báo như sau: Type st4 = string[4]; St6 = string[6]; St20 = string[20]; troSV= ^Sinhvien; sinhvien = record hoten: st20; email: string; tiep: troSV; end; troLop=^Lop; lop =record malop: st4; loptruong: st20; sdt: byte; next: troSV; down: troLop; end; Var first: troLop; Chú ý: các lớp sinh viên trong một lớp được sắp theo thứ tự h ọ tên (gi ả thi ết trong l ớp không có hai sinh viên cùng tên) và danh sách này luôn khác rỗng. Viết các thủ tục sau: a. Procedure Loaibo(bma: st4; bhten:st20); thực hiện việc xóa một sinh viên ở lớp có mã là bma với họ tên là bhten ra khỏi danh sách lớp. b. Procedure DSLoptruong; thực hiện in thông tin lớp trưởng của tất cả các lớp trong Khoa (gồm mã lớp, họ tên lớp trưởng, số điện thoại). c. Procedure DSSVien(bma: st4); in ra danh sách các sinh viên của lớp có mã là Bma, kể cả lớp trưởng (họ tên, số điện thoại hoặc email). Câu 2.
Tại một bệnh viện người ta lưu thông tin về các bệnh nhân đang đi ều tr ị theo các khoa c ủa bệnh viện bằng một cây nhị phân tìm kiếm theo khóa MaKhoa (mã khoa điều trị) và gốc của cây có địa chỉ là Top. Mỗi nút trong cây có cấu trúc như sau: Left Makhoa First Right First là địa chỉ đầu của một danh sách khác (luôn khác rỗng), danh sách này l ưu thông tin c ủa các b ệnh nhân đang điều trị tại khoa đó. Cấu trúc của cây này có thể khai báo như sau: Type st4 = string[4]; St20 = string[20]; troBN= ^BenhNhan; BenhNhan = record hoten: st20; tuoi: byte; next: troBN; end; troKhoa = ^Khoa; Khoa = record Makhoa: st4; First: troBN; Left, right: troKhoa; end; Var Top: troKhoa; Viết các hàm và thủ tục sau: a. Procedure Xuatvien(bma: st4; bhoten: st20); thực hiện việc loại bệnh nhân có tên bhoten ra khỏi danh sách bệnh nhân của khoa có mã bma (khi bệnh nhân này xuất viện). b. Procedure Nhapvien(bma: st4; bhoten: st20; tuoi: byte); thực hiện việc bổ sung một bệnh nhân. c. Function SoBN(bma: st4): word; trả về số lượng bệnh nhân đang điều trị tại khoa có bma. d. Function TongBN: longint; trả về tổng số bệnh nhân đang điều trị tại bệnh viện.