De thi CTDL

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

Về Đầu Trang


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