De thi CTDL
Trang 1 trong tổng số 1 trang
De thi CTDL
câu 1 (3 đ):
Minh hoạ quá trình sắp xếp trên tập tin chứa dữ liệu có các khoá kiểu số nguyên dưới đây:
12, 21, 35, 34, 56, 45, 13, 0, 9, 76, 92, 85, 102, 93
a) Bằng phương pháp trộn trực tiếp
b) Bằng phương pháp trộn tự nhiên.
Câu 2: (3 đ):
Cho B- cây cấp 6 chứa các nút có khoá kiểu ký tự như sau:
a, f, g, h, l, m, x, y, z, o, k, b, c, e, j.
Sau đó xoá lần lượt cac phần tử có các khoá sau: y, g, e.
Câu 3: (2 đ):
Xây dựng bảng băm kích thước M= 10 bằng phương pháp dò bậc hai để lưu trữ dữ liệu có các khoá kiểu chuỗi dưới đây:
AF, hk, Lm, Fg, DH, LM, KF, gE, cA, lK (e lờ K).
Với hàm băm: f(key)=(mã ASCII của ký tự 1+ mã ASCII của ký tự 2) %M.
Hàm băm lại lần i: fi(key)= (f(key)+i^2)%M (i bình phương)
Câu 4: (2 đ):
Viết hàm tìm kiếm một phần tử có khoá bằng x trên bảng băm được xây dựng theo phương pháp dò tuyến tính, với hàm băm f(key)= key%M (M là số nguyên dương).
Các bạn tham khảo đề thi này nha.Chúc các bạn thi tốt
Minh hoạ quá trình sắp xếp trên tập tin chứa dữ liệu có các khoá kiểu số nguyên dưới đây:
12, 21, 35, 34, 56, 45, 13, 0, 9, 76, 92, 85, 102, 93
a) Bằng phương pháp trộn trực tiếp
b) Bằng phương pháp trộn tự nhiên.
Câu 2: (3 đ):
Cho B- cây cấp 6 chứa các nút có khoá kiểu ký tự như sau:
a, f, g, h, l, m, x, y, z, o, k, b, c, e, j.
Sau đó xoá lần lượt cac phần tử có các khoá sau: y, g, e.
Câu 3: (2 đ):
Xây dựng bảng băm kích thước M= 10 bằng phương pháp dò bậc hai để lưu trữ dữ liệu có các khoá kiểu chuỗi dưới đây:
AF, hk, Lm, Fg, DH, LM, KF, gE, cA, lK (e lờ K).
Với hàm băm: f(key)=(mã ASCII của ký tự 1+ mã ASCII của ký tự 2) %M.
Hàm băm lại lần i: fi(key)= (f(key)+i^2)%M (i bình phương)
Câu 4: (2 đ):
Viết hàm tìm kiếm một phần tử có khoá bằng x trên bảng băm được xây dựng theo phương pháp dò tuyến tính, với hàm băm f(key)= key%M (M là số nguyên dương).
Các bạn tham khảo đề thi này nha.Chúc các bạn thi tốt
nguyenhi- Khách viếng thăm
Re: De thi CTDL
Đề thi thử csdl chuyên ngành do các bạn trong lớp biên soạn nè. Các bạn tải về tham khảo nhé.
Tải về
Tải về
nhuhaipt2004- Administrator
- Tổng số bài gửi : 96
Join date : 26/08/2010
Re: De thi CTDL
một cách tính mã ASCII nhanh, Các bạn tham khảo:
Đâu tiên viết ra 26 chữ cái từ A đến Z, sau đó đánh số từ 0 đến 25, thời gian viết cái này chắc khoảng 3 phút gì đó ( mình nghĩ vậy, nếu học thuộc 26 chữ cái, chắc đọc rồi viết 2 - 3 lần gì là nhớ thôi mà)
Sau khi đánh số thì chỉ cần nhớ chữ a thường là 97, chữ A là 65.
OK.
Bây giờ ví dụ một cái:
như AF đi:
A được đánh số 0,
F được đánh số 5,
A với F đều là chữ hoa.
==> tổng mã ASCII = 65 + 65 + 0 + 5
vậy là bằng 135
Vậy f(AF) = 5.
Đơn giản vậy thôi, mấy bạn làm mấy cái là thấy dễ à.:15:
Đâu tiên viết ra 26 chữ cái từ A đến Z, sau đó đánh số từ 0 đến 25, thời gian viết cái này chắc khoảng 3 phút gì đó ( mình nghĩ vậy, nếu học thuộc 26 chữ cái, chắc đọc rồi viết 2 - 3 lần gì là nhớ thôi mà)
Sau khi đánh số thì chỉ cần nhớ chữ a thường là 97, chữ A là 65.
OK.
Bây giờ ví dụ một cái:
như AF đi:
A được đánh số 0,
F được đánh số 5,
A với F đều là chữ hoa.
==> tổng mã ASCII = 65 + 65 + 0 + 5
vậy là bằng 135
Vậy f(AF) = 5.
Đơn giản vậy thôi, mấy bạn làm mấy cái là thấy dễ à.:15:
nhuhaipt2004- Administrator
- Tổng số bài gửi : 96
Join date : 26/08/2010
Re: De thi CTDL
Minh hoạ quá trình sắp xếp trên tập tin chứa dữ liệu có các khoá kiểu số nguyên dưới đây:
12, 21, 35, 34, 56, 45, 13, 0, 9, 76, 92, 85, 102, 93
a) Bằng phương pháp trộn trực tiếp
·P=1:
Chia a vào b, c:
b: 12, 35, 56, 13, 9, 92, 102
c: 21, 34, 45, 0, 76, 85, 93.
Trộn vào a: 12, 21, 34, 35, 45, 56, 0, 13, 9, 76, 85, 92, 93, 102. (trộn từng cặp, sắp tăng dần từng cặp đó)
·P= p*2= 1*2= 2.
b: 12, 21, 45, 56, 9, 76, 93, 102
c: 34, 35, 0, 13 , 85, 92.
Trộn vào a: 12, 21, 34, 35, 0, 13, 45, 56, 9, 76, 85, 92, 93, 102
·P= 2*2= 4:
b: 12, 21, 34, 35, 9, 76, 85, 92
c: 0, 13, 45, 56, 93, 102
Trộn vào a: 0, 12, 13, 21, 34, 35, 45, 56, 9, 76, 85, 92, 93, 102
·P=4*2= 8
b: 0, 12, 13, 21, 34, 35, 45, 56
c: 9, 76, 85, 92, 93, 102
Trộn vào a: 0, 9, 12, 13, 21, 34, 35, 45, 56, 76, 85, 92, 93, 102
·P= 8*2= 16> n= 14. Dừng (n=14, số phần tử của dãy số)
Vậy dãy a sau khi được sắp xếp là: 0, 9, 12, 13, 21, 34, 35, 45, 56, 76, 85, 92, 93, 102
--------------------------
b) Bằng phương pháp trộn tự nhiên.
(trộn run)
12, 21, 35, 34, 56, 45, 13, 0, 9, 76, 92, 85, 102, 93
đưa vào Run ta có:
12, 21, 35, 34, 56, 45, 13, 0, 9, 76, 92, 85, 102, 93
=> có 7 Run (Run là 1 dãy các số có thứ tự tăng dần)
·M= 7 (M là Run)
Đưa a lần lượt vào b, c theo Run:
b: 12, 21, 35, 45, 0, 9, 76, 92, 93
c: 34, 56, 13, 85, 102
Tiến hành đưa số vào Run: (thấy những Run cạnh nhau mà tăng dần thì nhập làm 1)
b: 12, 21, 35, 45, 0, 9, 76, 92, 93
c: 34, 56, 13, 85, 102
trộn vào a: (trộn từng cặp trên dưới, theo thứ tự tăng dần)
a: 12, 21, 34, 35, 45, 56, 0, 9, 13, 76, 85, 92, 93, 102
·M= 2:
b: 12, 21, 34, 35, 45, 56
c: 0, 9, 13, 76, 85, 92, 93, 102
trộn vào a:
a: 0, 9,12, 13, 21, 34, 35, 45, 56, 76, 85, 92, 93, 102
Vậy dãy a sau khi được sắp xếp là: 0, 9, 12, 13, 21, 34, 35, 45, 56, 76, 85, 92, 93, 102
12, 21, 35, 34, 56, 45, 13, 0, 9, 76, 92, 85, 102, 93
a) Bằng phương pháp trộn trực tiếp
·P=1:
Chia a vào b, c:
b: 12, 35, 56, 13, 9, 92, 102
c: 21, 34, 45, 0, 76, 85, 93.
Trộn vào a: 12, 21, 34, 35, 45, 56, 0, 13, 9, 76, 85, 92, 93, 102. (trộn từng cặp, sắp tăng dần từng cặp đó)
·P= p*2= 1*2= 2.
b: 12, 21, 45, 56, 9, 76, 93, 102
c: 34, 35, 0, 13 , 85, 92.
Trộn vào a: 12, 21, 34, 35, 0, 13, 45, 56, 9, 76, 85, 92, 93, 102
·P= 2*2= 4:
b: 12, 21, 34, 35, 9, 76, 85, 92
c: 0, 13, 45, 56, 93, 102
Trộn vào a: 0, 12, 13, 21, 34, 35, 45, 56, 9, 76, 85, 92, 93, 102
·P=4*2= 8
b: 0, 12, 13, 21, 34, 35, 45, 56
c: 9, 76, 85, 92, 93, 102
Trộn vào a: 0, 9, 12, 13, 21, 34, 35, 45, 56, 76, 85, 92, 93, 102
·P= 8*2= 16> n= 14. Dừng (n=14, số phần tử của dãy số)
Vậy dãy a sau khi được sắp xếp là: 0, 9, 12, 13, 21, 34, 35, 45, 56, 76, 85, 92, 93, 102
--------------------------
b) Bằng phương pháp trộn tự nhiên.
(trộn run)
12, 21, 35, 34, 56, 45, 13, 0, 9, 76, 92, 85, 102, 93
đưa vào Run ta có:
12, 21, 35, 34, 56, 45, 13, 0, 9, 76, 92, 85, 102, 93
=> có 7 Run (Run là 1 dãy các số có thứ tự tăng dần)
·M= 7 (M là Run)
Đưa a lần lượt vào b, c theo Run:
b: 12, 21, 35, 45, 0, 9, 76, 92, 93
c: 34, 56, 13, 85, 102
Tiến hành đưa số vào Run: (thấy những Run cạnh nhau mà tăng dần thì nhập làm 1)
b: 12, 21, 35, 45, 0, 9, 76, 92, 93
c: 34, 56, 13, 85, 102
trộn vào a: (trộn từng cặp trên dưới, theo thứ tự tăng dần)
a: 12, 21, 34, 35, 45, 56, 0, 9, 13, 76, 85, 92, 93, 102
·M= 2:
b: 12, 21, 34, 35, 45, 56
c: 0, 9, 13, 76, 85, 92, 93, 102
trộn vào a:
a: 0, 9,12, 13, 21, 34, 35, 45, 56, 76, 85, 92, 93, 102
Vậy dãy a sau khi được sắp xếp là: 0, 9, 12, 13, 21, 34, 35, 45, 56, 76, 85, 92, 93, 102
nhuhaipt2004- Administrator
- Tổng số bài gửi : 96
Join date : 26/08/2010
Trang 1 trong tổng số 1 trang
Permissions in this forum:
Bạn không có quyền trả lời bài viết