ĐỀ THI SAU ĐẠI HỌC NĂM 2008

Chia sẻ: Thuy Ha | Ngày: | Loại File: PDF | Số trang:4

Thêm vào BST

Báo xấu

1.642
lượt xem 228
download

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

PHẦN A: CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT (2.5 điểm) Câu 1 (1.5 điểm). Thí sinh trả lời ngắn gọn 6 câu hỏi sau đây, mỗi câu 0.25 điểm: 1.1 Đề giải bài toán Tháp Hà Nội bằng một lời giải thuật đệ quy, người ta hay dùng chiến lược thiết kế giải thuật nào sau đây: a tham lam b quay lui c chia để trị d cả ba câu trên đều sai

Chủ đề:

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

Lưu

Nội dung Text: ĐỀ THI SAU ĐẠI HỌC NĂM 2008

TSSĐH-B02 ĐẠI HỌC QUỐC GIA TP. HỒ CHÍ MINH TRƯỜNG ĐẠI HỌC BÁCH KHOA HỘI ĐỒNG TUYỂN SINH SĐH ------- oOo ------- ĐỀ THI SAU ĐẠI HỌC NĂM 2008 Tuyển sinh: CAO HỌC NGHIÊN CỨU SINH Chuyên ngành: KHOA HỌC MÁY TÍNH Môn Thi: CƠ BẢN CƠ SỞ CHUYÊN NGÀNH Thời gian làm bài: 180 phút (Không được phép dùng tài liệu) Đề thi số: 01 Đề thi gồm 4 trang ⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯ PHẦN A: CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT (2.5 điểm) Câu 1 (1.5 điểm). Thí sinh trả lời ngắn gọn 6 câu hỏi sau đây, mỗi câu 0.25 điểm: 1.1 Để giải bài toán Tháp Hà Nội bằng một giải thuật đệ quy, người ta hay dùng chiến lược thiết kế giải thuật nào sau đây: a. tham lam b. quay lui c. chia để trị d. cả ba câu trên đều sai 1.2 Haõy neâu ñoä phöùc taïp cuûa caùc thao taùc laøm vieäc treân caáu truùc heap. 1.3 Có hai cách diễn tả đồ thị: (1) ma trận kế cận và (2) tập danh sách kế cận. Hãy nêu trường hợp nào nên dùng cách 1 và trường hợp nào nên dùng cách 2). 1.4 Haõy so saùnh phöông phaùp tìm kieám baèng kyõ thuaät baêm vaø tìm kieám baèng caây tìm kieám nhò phaân, phöông phaùp naøo toát hôn. Taïi sao? 1.5 Taïi sao ñoái vôùi moät maûng ñaõ gaàn coù thöù töï, ta khoâng neân aùp duïng Quicksort? 1.6 Trong giải thuật Quicksort để sắp thứ tự một dãy, người ta hay chọn phần tử chốt (pivot) là: a. phần tử tận cùng trái của dãy b. phần tử tận cùng phải của dãy c. phần tử trung vị của 3 phần tử tận cùng phải, tận cùng trái và phần tử ở vị trí chính giữa dãy. d. một trong 3 cách trên đều đúng. Câu 2 (0.5 điểm) Hãy vẽ từng bước quá trình xây dựng cây tìm kiếm nhị phân khi ta đưa vào cây (lúc đầu rỗng) những trị khoá như sau: E, A, R, C, H, N, M, P, L. Và cây tìm kiếm nhị phân sẽ trở thành như thế nào khi ta xóa trị khóa E ra khỏi cây. Caâu 3 (0.5 ñieåm) Hãy chạy từng bước giải thuật sắp thứ tự bằng phương pháp trộn (merge sort) để sắp thứ tự dãy số 53, 59, 56, 52, 58, 51, 57, 54. PHẦN B: NGÔN NGỮ LẬP TRÌNH (2.5 điểm) Câu 1 (1 điểm) a. (0.25điểm) Giả sử kích thước của một đối tượng kiểu integer là 2, real là 4, boolean là 1 (theo đơn vị byte). Kiểu tập hợp lưu trữ dạng chuỗi bit. Cho biết kích thước phần mô tả bằng 0, hãy tính (và giải thích) kích thước của một đối tượng dữ liệu có kiểu được định nghĩa như sau: record a: set of 0..15; b: boolean; case b of true: (c:integer) false: (e:real; f:integer; g:boolean) ⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯ Ghi chú: ................................................................................. Ký tên: ........................................................................................Trang: 1
TSSĐH-B02 end b. (0.75điểm) Vẽ khối lưu trữ với năm phần tử đầu tiên và tính địa chỉ truy xuất phần tử A[I,J,K] của dãy sau (cho biết công thức tổng quát và sau đó thay số cụ thể). Giả sử dãy được lưu trữ dùng phương pháp đánh thứ tự theo row-major. A: array [2..4,-1..2,4..6] of real; Câu 2 (1.5 điểm) Cho chương trình viết bằng ngôn ngữ tựa PASCAL (ngôn ngữ cấu trúc khối) như sau: program main; var a: array [1..5] of integer; i,j: integer; procedure swap(a, b,c: integer); var t: integer; begin t := a; a := b; b := c; c:=(i+t) div 2; {div là phép toán lấy phần nguyên phép chia} end ; begin for i := 1 to 5 do a[i] := 6 – i; i := 2;j:=3; swap(i, a[i],j); end. 2.a. Hãy vẽ chồng trung tâm ở thời điểm vừa thực hiện xong các phép gán trong swap. Cho biết địa chỉ của lệnh gọi swap trong main là I1, địa chỉ của lệnh sau lệnh gọi này là I2, các thông số a, b và c được truyền bằng trị. 2.b. Cho biết giá trị của các phần tử của dãy a và các biến i, j sau lệnh gọi swap trong các trường hợp sau: b1. Thông số a và b được truyền theo trị-kết quả. b2. Thông số a và b được truyền theo tham khảo. b3. Thông số a và b được truyền theo tên. PHẦN C: CƠ SỞ DỮ LIỆU (2.5 điểm) Câu 1 (0,5 điểm). Phát biểu định nghĩa khóa (key) của một lược đồ quan hệ R. Cho một ví dụ về lược đồ quan hệ có ý nghĩa trong thực tế (ví dụ sinh viên, khách hàng …) vừa có khóa đơn (simple key) vừa có khóa phức hợp (composite key) và giải thích ý nghĩa của các khóa này. Câu 2 (1 điểm). Cho lược đồ quan hệ R(A,B,C,D,E,F,G,H) và tập phụ thuộc hàm {B → E, D → AEF, E → CG, A → CG, F → D, C → H}. Hãy tìm tất cả các khóa của R. Câu 3 (1 điểm). Cho lược đồ cơ sở dữ liệu sau đây: sinhviên (mãsv, họtên, tuổi) mônhọc (mãmh, tênmh) học (mãsv, mãmh, điểmthi) Các thuộc tính được gạch dưới là các thuộc tính khóa. Tất cả các khóa ngoại đều chứa giá trị khác rỗng (khác null). Ý nghĩa của các lược đồ quan hệ này như sau: sinhviên - một sinh viên có các thuộc tính: mã sinh viên (mãsv), họ tên (họtên), tuổi (tuổi). mônhọc - một môn học có các thuộc tính: mã môn học (mãmh), tên môn học (tênmh). học - một sinh viên (mãsv) học một môn học (mãmh) có điểm thi (điểmthi). 3.a Hãy viết một biểu thức đại số quan hệ cho kết quả tương đương với kết quả của lệnh select sau đây: ⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯ Ghi chú: ................................................................................. Ký tên: ........................................................................................Trang: 2
TSSĐH-B02 select mãsv, họtên from sinhviên where mãsv not in (select mãsv from học); Ký hiệu của các phép toán đại số quan hệ: σF(r) - Phép chọn trên r theo điều kiện F r×s - Phép tích Descartes của r và s ΠX(r) - Phép chiếu r trên tập thuộc tính X r∩s - Phép giao của r và s r ∪ s - Phép hợp của r và s r θ s - Phép kết-θ của r và s r − s - Phép hiệu của r cho s r s - Phép kết tự nhiên của r và s (0.5 điểm) 3.b Viết lệnh select trả lời câu hỏi: “Cho biết mã và họ tên của các sinh viên có tuổi lớn hơn 20 tuổi và có học 10 môn học”. (0.5 điểm) PHẦN D: CẤU TRÚC MÁY TÍNH (2.5 điểm) Câu 1 (1 điểm) Hình vẽ D.1 trình bày sơ đồ chân của IC SRAM 7489 của hãng Signetics. IC này có khả năng lưu trữ 16 từ có độ rộng 4 bit. a. Liệt kê các chế độ hoạt động của IC cho mỗi xung CS được cho trong hình D.3 b. Liệt kê nội dung của các từ trong bộ nhớ từ vị trí 0 đến vị trí 6 sau xung thứ n c. Chỉ ra trạng thái ngõ xuất dữ liệu đối với các xung từ h đến m ⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯ Ghi chú: ................................................................................. Ký tên: ........................................................................................Trang: 3
TSSĐH-B02 Câu 2 (1.5 điểm) Viết chương trình con hợp ngữ INTEL 8086 để tính 15 phần tử đầu tiên của dãy số sau: U0 = 1 U1 = 2 Un = Un–2 +Un–1 + 2 (n ≥ 2) Các phép toán thực hiện trên dữ liệu 16 bit. Kết quả được lưu lần lượt vào bộ nhớ có địa chỉ bắt đầu từ 4800h:0400h ⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯ Ghi chú: ................................................................................. Ký tên: ........................................................................................Trang: 4