De thi CTDL

Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down

De thi CTDL

Bài gửi by nguyenhi on Wed 20 Oct 2010, 10:12 am

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).


 Very Happy  Smile 

 

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


Về Đầu Trang Go down

Re: De thi CTDL

Bài gửi by nhuhaipt2004 on Thu 21 Oct 2010, 7:48 am

Đề 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ề

nhuhaipt2004
Administrator
Administrator

Tổng số bài gửi : 96
Join date : 26/08/2010

Về Đầu Trang Go down

Re: De thi CTDL

Bài gửi by nhuhaipt2004 on Thu 21 Oct 2010, 10:06 am

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:

nhuhaipt2004
Administrator
Administrator

Tổng số bài gửi : 96
Join date : 26/08/2010

Về Đầu Trang Go down

Re: De thi CTDL

Bài gửi by nhuhaipt2004 on Thu 21 Oct 2010, 10:09 am

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

nhuhaipt2004
Administrator
Administrator

Tổng số bài gửi : 96
Join date : 26/08/2010

Về Đầu Trang Go down

Re: De thi CTDL

Bài gửi by Sponsored content


Sponsored content


Về Đầu Trang Go down

Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang


 
Permissions in this forum:
Bạn không có quyền trả lời bài viết